# Idea and core implementation taken from the book `Programming in Lua` by Roberto Ierusalimschy, 2nd Edition, Lua.org, p. 102.

package.checkclib('bags');  # has C dynamic link library been found ?

bags.initstring :=
   'bags (multisets) package v0.3.3 as of July 25, 2014\n';

bags.aux := [];

# set user-defined `bags` type and the corresponding metamethods to a table
bags.aux.setattribs := proc(t :: table) is
   setmetatable(t, bags.aux.mt);
   settype(t, 'bag');
   return t
end;

if unassigned(skycrane) then import skycrane fi;  # Agena 1.12.8 patch/hotfix XXX

# metamethods for the pretty printer, and the operators: `union` = union, `minus` = difference set, 
# and `intersect` = intersection, `in` = search for multiset members
bags.aux.mt := [
   # `pretty printer`
   '__tostring' ~ proc(bag :: bag) is
      local r, indices;
      create table r(size bag);
      indices := skycrane.sorted(tables.indices(bag));  # Agena 1.12.8 patch/hotfix XXX
      for i in indices do
         insert tostring(i) & ' ~ ' & tostring(bag[i]) into r
      od;
      return 'bag(' & join(r, ', ') & ')'
   end,
   # `union`
   '__union' ~ proc(a :: bag, b :: bag) is
      local A, B, all, r;
      A, B := bags.bagtoset(a), bags.bagtoset(b);  # patched 2.2.6
      all := A union B;
      create table r(size all);
      for i in all do
         r[i] := (a[i] or 0) + (b[i] or 0)
      od;
      return bags.aux.setattribs(r)
   end,
   # difference set, `minus`; note that if an element x in B has more occurrences than the same element x in A, it is deleted from the result
   '__minus' ~ proc(a :: bag, b :: bag) is
      local A, r;
      A := bags.bagtoset(a);  # patched 2.2.6
      create table r(size A);
      for i in A do
         r[i] := a[i] - (b[i] or 0);
         if r[i] < 1 then r[i] := null fi
      od;
      return bags.aux.setattribs(r)
   end,
   # intersection, `intersect`
   '__intersect' ~ proc(a :: bag, b :: bag) is
      local A, B, all, r;
      A, B := bags.bagtoset(a), bags.bagtoset(b);  # patched 2.2.6
      all := A intersect B;
      create table r(size all);
      for i in all do
         r[i] := a[i] + b[i]  # add occurrences
      od;
      return bags.aux.setattribs(r)
   end,
   # search for an element in the bag, `in`
   '__in' ~ proc(x, bag :: bag) is
      return assigned(bag[x])  # tuned Agena 1.7.4, patched 1.7.6a
   end
];


# backward compatibility

bags.attribs := bags.attrib;

