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

(* Created by Jorge Stolfi   on Thu Sep  6  1:38:51 PDT 1990   *)
(* Based on Table.def by John Ellis                            *)
(* Last modified on Sat Jun 27 15:46:04 PDT 1992 by muller     *)
(*      modified on Tue May 14 13:22:44 PDT 1991 by stolfi     *)

INTERFACE RefanySet;

(* Dynamic sets of REFANY's.

This module implements dynamic sets of REFANY's.

The sets grow and shrink automatically so as to provide reasonable
access time without wasting too much space.

All operations on a given set are internally serialized by a private
MUTEX.

Index: set, set, REFANY. 

*)

IMPORT List;

IMPORT Word;

TYPE
  Key = REFANY;

TYPE
  T = OBJECT METHODS 

      in (key: Key): BOOLEAN RAISES {}; 
        (* 
          TRUE iff /key/ is in the set. *)

      put (key: Key): BOOLEAN RAISES {};
        (* 
          Adds /key/ to the set; Returns TRUE iff already there. *)

      delete (key: Key): BOOLEAN RAISES {};
        (* 
          Removes /key/ from the set. Returns TRUE iff was indeed there. *)

      clear () RAISES {};
        (*
          Removes all entries from the set. *)

      copy (): T RAISES {};
        (*
          Makes a copy of the set and its contents. *)

      toList (): List.T RAISES {};
        (*
          Returns a list of all the elements in the set, as REFANY, in no
          particular order.  *)

      enumerate  (
          proc: EnumerateProc; 
          data: REFANY; 
          VAR (*OUT*) key: Key; 

        ): BOOLEAN;
        (*

          Invokes /proc(data, key)/ for each /key/ in the set.  If
          /proc/ returns TRUE, the enumeration is terminated, the
          terminating entry is stored into /key/, and TRUE is returned.
          If /proc/ never returns TRUE, /key/ is set to
          /NIL/, and FALSE is returned.

  
          The client procedure /proc/ is called with /T.lock/ held.
          Therefore, all other operations on the same set will block
          until Enumerate returns (or is aborted by the /proc/ raising an exception).
          Also, the /proc/ itself sshould not attempt to perform any
          operation on the same set, or a deadlock will result.

          of visited entries.

          However, it must not modify the contents of the record

          *)

    END;

  HashProc = PROCEDURE(key: Key): Word.T;
    (* A function that maps a key into a hashing code. *)

  EqualProc = PROCEDURE(a, b: Key): BOOLEAN;
    (* A procedure that tests whether two keys are equal. *)

PROCEDURE New(

    hashProc: HashProc;

    equalProc: EqualProc;

    initialSize: CARDINAL := 1;
  ): T RAISES {};
(*
  Constructs a new set, initially containing /initialSize/ buckets.

  The key hashing function /hashProc/ should distribute the expected
  set of keys over a much larger subrange of INTEGER or CARDINAL, as
  uniformly as possible.  

  Note that LOOPHOLE(REFANY, INTEGER) is not a valid hash function
  in implementations that use relocating garbage collectors.

  The key comparison procedure /equalProc/ must be compatible
  with the /hashProc/; specifically, equal keys must be mapped to
  the same hash code.

  *)

TYPE

  EnumerateProc = PROCEDURE(data: REFANY; key: Key): BOOLEAN;
  (*
    A client-defined procedure called by Enumerate on each element
    in the set.

    The /data/ parameter is the client data passed to
    Enumerate.  An EnumerateProc should return true to halt the
    enumeration, false to continue it.  *)

END RefanySet.