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

(* Last modified on Tue Feb 11 20:48:05 PST 1992 by muller                   *)

GENERIC MODULE Set (Hash, HashSetADT);

(* The set 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;
           e: Hash.T; END;

REVEAL
  T = HashSetADT.T OBJECT METHODS
        new (minSize: CARDINAL := 0): T; END
      BRANDED OBJECT
        a: REF ARRAY OF Node;
      OVERRIDES
        new     := new;
        member  := member;
        insert  := insert;
        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 HashSetADT.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 member (self: T; x: Hash.T): BOOLEAN =
  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;
    RETURN (cur # NIL);
  END member;


PROCEDURE insert (self: T; x: Hash.T): BOOLEAN =
  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
        head := NEW (Node, next := head, e := x);
        RETURN FALSE;
      ELSE
        RETURN TRUE; END; END;
  END insert;

PROCEDURE delete (self: T; x: Hash.T): BOOLEAN =
  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 FALSE;
      ELSE
        IF prev = NIL THEN
          head := cur.next;
        ELSE
          prev.next := cur.next; END;
        RETURN TRUE; END; END;
  END delete;

PROCEDURE equal (self: T; t: HashSetADT.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 NOT t.member (cur.e) THEN
          RETURN FALSE; END;
        INC (size);
        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 := cur.next; END; END;
    RETURN size;
  END size;

PROCEDURE copy (self: T): HashSetADT.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), 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: HashSetADT.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 := cur.next; END; END;
  END map;

BEGIN
END Set.