(* 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:45 PST 1992 by muller                   *)

GENERIC INTERFACE SetADT (Elt);

(* The Set abstract data type.

   The type 'T' defines the basic operations available from all 
   implementations of sets.  The 'new' operation may be redefined with
   a different signature in subtypes of 'T'.  Also, subtypes may
   define additional methods.  

   Interfaces that define implementations of Set may require actual 
   arguments that are more strict than Elt.

   A simple implementation is provided by the SimpleSet interface. *)


TYPE 
  F = PROCEDURE (x: Elt.T) RAISES ANY;
        (* to iterate over the elements of a set *)

  T = OBJECT METHODS
         new (): T := new;
           (* create (self = NIL) or initialize (self # NIL) a Set.T *)

         member (x: Elt.T): BOOLEAN;
           (* TRUE iff x is a member of self *)
         insert (x: Elt.T): BOOLEAN;
           (* insert x in self.  Return TRUE iff x was there already *)
         delete (x: Elt.T): BOOLEAN;
           (* delete x from self.  Return TRUE iff x was there before *)

         equal (s: T): BOOLEAN;
           (* TRUE iff self and s are equal *)
         isEmpty (): BOOLEAN;
           (* TRUE iff self is empty *)
         size (): CARDINAL;
           (* return the number of elements in self *)
         copy (): T;
           (* return a copy of self. *)
         map (f: F) RAISES ANY;
           (* apply f to each element in self.  It is an unchecked runtime 
              error to modify self while this procedure is active *)
       END;

PROCEDURE new (self: T): T;

END SetADT.