6.3 Sets Interface

ORIGIN 'collection';
LIB_DEF 'contsets' '../lib';
BODY 'private/setsBody';
(*
 * COPYRIGHT
 *       Copyright (C) Mjolner Informatics, 1992-94
 *       All rights reserved.
 *)
--- lib: attributes ---
multiSet: collection
  (* MultiSet is a data structure for collecting elements (dublicates
   * are allowed of the same element).  Defines no new operations.
   * MultiSet is the superpattern for Set, which ignores dublicates.
   * The available subpatterns are (indentation specifies
   * specialization): 
   *       multiSet
   *          set
   *             classification
   *)
  (# <<SLOT multiSetLib: attributes>>;
     theScanner::<  (* private *)
       (# 
       ...
       #);
     find::
       (# 
       ...
       #);
     copy::<(# 
       ...
       #);
     empty::<
       (# 
       ...
       #);
     capacity::<
       (# 
       ...
       #);
     has::<
       (# myEqual:@equal;
       ...
       #);
     clear::< (# ... #);
     size::< (# ... #);
     insert::< 
       (* inserting in a multiSet is somewhat dependent on the
        * particular subpattern.  In some cases, insertion in only
        * done if the element is not already in the multiSet
        * (e.g. sets).  The local attribute, allowedToInsert, controls
        * whether the element is actually inserted in the multiSet.
        *)
       (# allowedToInsert: @boolean;
          multiSetInsertPrivate: @ (* O(1) amort. *)
            ...
       do true->allowedToInsert; 
          INNER; 
          (if allowedToInsert then multiSetInsertPrivate if)
       #);
     delete::< 
       (# multiSetDeletePrivate: @... 
       do multiSetDeletePrivate; 
          INNER 
       #);
     theCellType::< (* Private *)
       (# pred, succ: (* Private *) ^theCellType;
       do INNER #);
     doEnter::<
       (# containerType::<multiSet;
       ...
       #);
     private:@...;
  do INNER
  #) (* multiSet *);

(*------------------------------------------------------------*)
(*--- set: multiSet ------------------------------------------*)
(*------------------------------------------------------------*)

set: multiSet
  (* A set is a multiSet in which dublicates are removed (ie. not inserted).  
   * Defines no new operations.
   *)
  (# <<SLOT setLib: attributes>>;
     insert::< 
       (* Inserts only the element if it is not in the set already *)
       (# ... #);
     doEnter::<
       (# containerType::<Set;
       do INNER
       #);
  do INNER
  #)