(* 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 INTERFACE BagADT (Elt);

(* The Bag abstract data type.

   The type 'T' defines the basic operations available from all 
   implementations of bags.  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 Bag may require actual 
   arguments that are more strict than Elt.

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

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

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

        count (x: Elt.T): CARDINAL;
          (* the number of occurrences of x in self *)
        add (x: Elt.T; occ: CARDINAL := 1): CARDINAL;
          (* add 'occ' occurrences of x to self; return the number of 
             occurrences of x in self after the insertion *)
        delete (x: Elt.T; occ: CARDINAL := 1): CARDINAL;
          (* remove 'occ' occurrences of x from self; RETURN the NUMBER OF
             occurrences OF x IN self after the deletion.  If occ is
             greater than self.count (x), THEN self.count (x) occurrences 
             are removed. *)

        equal (s: T): BOOLEAN;
          (* TRUE iff self and s are equal *)
        isEmpty (): BOOLEAN;
          (* TRUE iff self is empty *)
        size (): CARDINAL;
          (* return the number of occurrences 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 BagADT.