(* Copyright (C) 1992, Digital Equipment Corporation                         *)
(* All rights reserved.                                                      *)
(* See the file COPYRIGHT for a full description.                            *)

(* Last modified on Tue Feb 11 20:47:13 PST 1992 by muller                   *)

GENERIC MODULE Bag (Hash, HashBagADT);

(* The bag elements are stored in a hash table, with collison resolution 
   by chaining.  In this simple implementation, the size of the hash table
   is fixed and is equal to MAX (initialSize, MinSize) *)


TYPE
  Node = REF RECORD 
           next: Node;
           c: CARDINAL;
           e: Hash.T; END;

REVEAL
  T = HashBagADT.T OBJECT METHODS
         new (minSize: CARDINAL := 0): T; END
      BRANDED OBJECT
        a: REF ARRAY OF Node;
      OVERRIDES
        new     := new;
        count   := count;
        add     := add;
        delete  := delete;
        equal   := equal;
        isEmpty := isEmpty;
        size    := size;
        copy    := copy;
        map     := map; END;


CONST
  MinSize = 100;

PROCEDURE new (self: T; minSize: CARDINAL := 0): T =
  BEGIN
    IF self = NIL THEN
      self := NEW (T); END;

    EVAL HashBagADT.T.new (self);

    self.a := NEW (REF ARRAY OF Node, MAX (minSize, MinSize));
    FOR i := FIRST (self.a^) TO LAST (self.a^) DO 
      self.a [i] := NIL; END;

    RETURN self;
  END new;


PROCEDURE count (self: T; x: Hash.T): CARDINAL =
  VAR cur: Node;
  BEGIN
    cur := self.a [Hash.Hash (x, NUMBER (self.a^))];
    WHILE cur # NIL AND NOT Hash.Equal (cur.e, x) DO
      cur := cur.next; END;
    IF cur = NIL THEN
      RETURN 0;
    ELSE
      RETURN cur.c; END;
  END count;

PROCEDURE add (self: T; x: Hash.T; occ: CARDINAL := 1): CARDINAL =
  VAR cur: Node;
  BEGIN
    WITH head = self.a [Hash.Hash (x, NUMBER (self.a^))] DO 
      cur := head;
      WHILE cur # NIL AND NOT Hash.Equal (cur.e, x) DO
        cur := cur.next; END;
      IF cur = NIL THEN
        cur := NEW (Node, next := head, e := x, c := occ);
        head := cur;
      ELSE
        INC (cur.c, occ); END;
      RETURN cur.c; END;
  END add;

PROCEDURE delete (self: T; x: Hash.T; occ: CARDINAL := 1): CARDINAL =
  VAR cur, prev: Node;
  BEGIN
    WITH head = self.a [Hash.Hash (x, NUMBER (self.a^))] DO 
      cur := head;
      prev := NIL;
      WHILE cur # NIL AND NOT Hash.Equal (cur.e, x) DO
        prev := cur;
        cur := cur.next; END;
      IF cur = NIL THEN
        RETURN 0;
      ELSE
        DEC (cur.c, occ);
        IF cur.c = 0 THEN 
          IF prev = NIL THEN
            head := cur.next;
          ELSE 
            prev.next := cur.next; END; END;
        RETURN cur.c; END; END;
  END delete;

PROCEDURE equal (self: T; t: HashBagADT.T): BOOLEAN =
  VAR cur: Node;
      size: CARDINAL := 0;
  BEGIN
    FOR b := FIRST (self.a^) TO LAST (self.a^) DO
      cur := self.a [b];
      WHILE cur # NIL DO
        IF t.count (cur.e) # cur.c THEN
          RETURN FALSE; END;
        INC (size, cur.c);
        cur := cur.next; END; END;
    RETURN size = t.size ();
  END equal;

PROCEDURE isEmpty (self: T): BOOLEAN =
  BEGIN
    FOR b := FIRST (self.a^) TO LAST (self.a^) DO
      IF self.a [b] # NIL THEN
        RETURN FALSE; END; END;
    RETURN TRUE;
  END isEmpty;

PROCEDURE size (self: T): CARDINAL =
  VAR size: CARDINAL := 0;
      cur: Node;
  BEGIN
    FOR b := FIRST (self.a^) TO LAST (self.a^) DO
      cur := self.a [b];
      WHILE cur # NIL DO 
        INC (size, cur.c);
        cur := cur.next; END; END;
    RETURN size;
  END size;

PROCEDURE copy (self: T): HashBagADT.T =
  VAR cp := new (NIL, NUMBER (self.a^));
      prevN, cur: Node;
  BEGIN
    FOR b := FIRST (self.a^) TO LAST (self.a^) DO
      cur := self.a [b];
      WHILE cur # NIL DO
        WITH n = NEW (Node, e := Hash.Copy (cur.e), c := cur.c, next := NIL) DO
          IF prevN = NIL THEN
            cp.a [b] := n;
          ELSE
            prevN.next := n; END;
          prevN := n;
          cur := cur.next; END; END; END;
    RETURN cp;
  END copy;


PROCEDURE map (self: T; f: HashBagADT.F) RAISES ANY =
  VAR cur: Node;
  BEGIN
    FOR b := FIRST (self.a^) TO LAST (self.a^) DO
      cur := self.a [b];
      WHILE cur # NIL DO
        f (cur.e, cur.c);
        cur := cur.next; END; END;
  END map;

BEGIN
END Bag.