IMPLEMENTATION MODULE Bag;

FROM List IMPORT List;
IMPORT SYSTEM;

  CLASS BagElement (Element);
    VAR
      Card: INTEGER;
      El: Element;
      
    REDEFINE METHOD CREATE (El: Element);
      BEGIN
      THIS.El := El;
      END CREATE;
      
    METHOD Get: Element;
      BEGIN
      RESULT := El;
      END Get;
      
    METHOD Cardinal: INTEGER;
      BEGIN
      RESULT := Card;
      END Cardinal;
      
    METHOD SetCardinal (TheCard: INTEGER);
      BEGIN
      Card := TheCard;
      END SetCardinal;
      
    METHOD IncCardinal (TheInc: INTEGER);
      BEGIN
      Card := Card + TheInc;
      END IncCardinal;
      
  END BagElement;

  ------------------------
  -- The Bag container class is a generalization
  -- of the Set class; where each element can also
  -- have a cardinality indicator. A set is basically
  -- a Bag where this cardinality indicator can only
  -- hold two values: 0 and 1.
  ------------------------
  CLASS Bag(Element);
  
    VAR
      TheList: List(BagElement);
      
    REDEFINE METHOD CREATE;
      BEGIN
      TheList.CREATE;
      END CREATE;
      
    METHOD Find(El: Element): INTEGER;
      POST
        NO_CHANGE_HC;
      BEGIN
      RESULT := -1;
      FOR i := 0 TO TheList.Size - 1 WHILE RESULT < 0 DO
        WHAT TheList.Get(i) OF
          IN BagElement (Element):
            IF TAG.Get = El THEN
              IF i <> 0 THEN
                TheList.Delete (i);
                TheList.Insert (0, TAG);
                END;
              RESULT := 0;
              END;
            END;
          END;
        END;
      END Find;
      
    METHOD FindElement(El: Element): BagElement(Element);
      VAR
        i: INTEGER;
      BEGIN
      i := Find (El);
      IF i >= 0 THEN
        WHAT TheList.Get(i) OF
          IN BagElement (Element):
            RESULT := TAG;
            END;
          END;
       ELSE
        RESULT.CREATE (El);
        TheList.Insert(0,RESULT);
        END;
      END FindElement;
      
    METHOD Add(El: Element);
      BEGIN
      FindElement(El).IncCardinal (1);
      ASSERT Cardinality(El) > 0;
      END Add;
      
    METHOD Cardinality (El: Element): INTEGER;
      VAR
        i: INTEGER;
      BEGIN
      i := Find (El);
      IF i >= 0 THEN
        RESULT := TheList.Get(i).Cardinal;
        END;      
      ASSERT RESULT >= 0;
      END Cardinality;
      
    METHOD Remove(El: Element);
      VAR
        i: INTEGER; 
        BagEl: BagElement;
      BEGIN
      i := Find (El);
      IF i >= 0 THEN
        BagEl := TheList.Get(i);
        IF BagEl.Cardinal < 2 THEN
          TheList.Delete (i);
         ELSE
          BagEl.IncCardinal (-1);
          END;
        END;      
      END Remove;
      
    METHOD RemoveAll(El: Element);
      VAR
        i: INTEGER; 
      BEGIN
      i := Find (El);
      IF i >= 0 THEN
        TheList.Delete (i);
        END;      
      END RemoveAll;
      
    -----------------------
    -- The Row method returns an array of Elements where
    -- each element is represented as many times as its
    -- attached cardinality.
    -----------------------
    METHOD Row: ARRAY OF Element;
      VAR
        TotalSize: INTEGER;
         j, Idx: INTEGER;
      BEGIN
      FOR i := TheList.Size - 1 TO 0 BY - 1 DO
        j := TheList.Get(i).Cardinal;
        IF j <= 0 THEN
          TheList.Delete (i);
         ELSE
          TotalSize := TotalSize + j;
          END;
        END;
      RESULT.CREATE (TotalSize);
      Idx := 0;
      FOR i := 0 TO TheList.Size - 1 DO
        WHAT TheList.Get(i) OF
          IN BagElement(Element):
            FOR k := 1 TO TAG.Cardinal DO
              RESULT [Idx] := TAG.Get;
              Idx := Idx + 1;
              END;
            END;
          END;
        END;
      ASSERT Idx = TotalSize;
      END Row;
      
    METHOD Intersects (Other: Bag(Element)): BOOLEAN;
      BEGIN
      FOR i := 0 TO TheList.Size - 1 WHILE NOT RESULT DO
        WHAT TheList.Get(i) OF
          IN BagElement (Element):
            RESULT := Other.Find (TAG.Get) >= 0;
            END;
          END;
        END;
      END Intersects;
      
    METHOD Intersection (Other: Bag(Element)): Bag(Element);
      VAR
        El: BagElement(Element);
        NewCard: INTEGER;
      BEGIN
      RESULT := THIS.CLONE;
      RESULT.TheList.CREATE;
      FOR i := TheList.Size - 1 TO 0 BY -1 DO
        IF TheList.Get(i).Cardinal <= 0 THEN
          TheList.Delete (i);
         ELSE
          WHAT TheList.Get(i) OF
            IN BagElement (Element):
              IF Other.Find (TAG.Get) >= 0 THEN
                El := Other.FindElement (TAG.Get);
                NewCard := SYSTEM.MIN (TAG.Cardinal, El.Cardinal);
                ASSERT NewCard >= 0;
                El.CREATE (TAG.Get);
                El.SetCardinal (NewCard);
                RESULT.TheList.Append (El);
                END;
              END;
            END;
          END;
        END;
      END Intersection;
      
    METHOD AddBag (Other: Bag(Element));
      BEGIN
      FOR i := 0 TO Other.TheList.Size - 1 DO
        WHAT Other.TheList.Get(i) OF
          IN BagElement (Element):
            FindElement (TAG.Get).IncCardinal (TAG.Cardinal);
            END;
          END;
        END;
      END AddBag;
      
    METHOD Union (Other: Bag(Element)): Bag(Element);
      VAR
        TempList: List(BagElement);      
      BEGIN
      TempList := TheList;
      TheList.CREATE;
      RESULT := THIS.CLONE;
      TheList := TempList;
      RESULT.TheList.CREATE;
      RESULT.AddBag (THIS);
      RESULT.AddBag (Other);            
      ASSERT RESULT.Size >= Size;
      ASSERT RESULT.Size >= Other.Size;
      ASSERT RESULT.Size <= Size + Other.Size;
      END Union;
      
    METHOD DoUnion (Other: Bag(Element));
      BEGIN
      AddBag (Other);
      END DoUnion;
      
    REDEFINE METHOD CLONE (Other: Bag(Element));
      BEGIN
      Other.TheList := TheList.CLONE;
      END CLONE;
      
    METHOD Size: INTEGER;
      BEGIN
      FOR i := 0 TO TheList.Size - 1 DO
        RESULT := RESULT + TheList.Get(i).Cardinal;
        END;      
      END Size;
      
  END Bag;

END Bag;
