SETSUMI.DEF

(*
13			The Unbounded Set

This chapter presents the unbounded implementation of the set abstraction described in
Chapter 11.  As with the other unbounded modules, given previously, the size of the set
structure will vary dynamically as items are added and removed.  This particular form has
the properties: Sequential, Unbounded, Managed, and Iterator.  These describe specific
aspects of the implementation as follows:

Sequential:	Can only be used in a non-tasking environment, or by only one task.
Unbounded:	The size of a set varies dynamically as items are added and removed from
		the set.
Managed:	Memory space for items and objects is returned to the system when no
		longer needed.
Iterator:	Routines for looping over each of the set items are provided.

The unbounded set interface follows in Section 13.1 while the actual implementation
appears in Section 13.2.



13.1	SetSUMI Interface
*)


DEFINITION MODULE SetSUMI;
(*==========================================================
    Version  : 1.00  30 Apr 1989  C. Lins
    Compiler : TopSpeed Modula-2
    Component: Monolithic Structures - Set
               Sequential Unbounded Managed Iterator

    INTRODUCTION
    This module provides the interface for the unbounded Set
    abstraction for generic Items.

    REVISION HISTORY
    v1.00  30 Apr 1989  C. Lins
      Initial implementation for TopSpeed Modula-2.

    (C) Copyright 1989 Charles A. Lins
==========================================================*)

FROM Items IMPORT
    (*--Type*) Item, AccessProc, LoopAccessProc;

FROM ErrorHandling IMPORT
    (*--Proc*) HandlerProc;

FROM SetEnum IMPORT
    (*--Type*) Exceptions;

FROM TypeManager IMPORT
    (*--Type*) TypeID;


    (*-----------------------*)

TYPE  Set;
CONST NullSet = Set(NIL);


(*
13.2.1			Exceptions

The ModuleID is used by the exception handling mechanism to distinguish this module
from other modules.

SetError returns the exception code from the most recent set operation.  A result of noerr 
indicates successful completion of the operation.

GetHandler returns the exception handler routine associated with the given exception. 
Though the routine is a function procedure returning a procedure as its result, the
HandlerProc may not be called from within the GetHandler call itself.  The procedure
result must be first assigned to a procedure variable before invocation.  Exception handlers
are given an initial value of ExitOnError except for the handler for noerr which is
initialized to the null exception handler.

SetHandler associates an exception handler routine with the given exception and is the
inverse of GetHandler.  This routine may be used to override the default settings for the
exception handlers.
*)

CONST ModuleID = 7;

PROCEDURE SetError    ()             : Exceptions  (*-- out   *);

PROCEDURE GetHandler  (    ofError   : Exceptions  (*-- in    *))
                                     : HandlerProc (*-- out   *);

PROCEDURE SetHandler  (    ofError   : Exceptions  (*-- in    *);
                           toHandler : HandlerProc (*-- in    *));


(*
13.1.2			Constructors

Create attempts to define a new, empty unbounded set of the given type, raising the
undefined exception if it is unable to successfully complete the set.

Destroy takes the given set, clears it of any items, and then destroys the set itself. 
Where Create makes a defined set, Destroy is its inverse, making the set undefined.

Clear takes the given set and removes all of its items.  theType attribute of the set 
(assigned when the set was created) is used to retrieve the item deallocation routine for the
items of the set.  Clearing the set returns it to the empty state.

The Assign operation attempts to generate a duplicate of the source set (theSet) in the
target set (toSet).  The target set is automatically created using the data type attribute of
the source set, if necessary.  If this step is unnecessary, (the target set has been previously
created), the target is cleared of its present contents, and its data type is changed to that of
the source set.

The Include operation adds items to the given set.  If the routine is unable to expand the
set for the new item the overflow exception will be raised and the set remains unchanged. 
If the item is already a member of the set the iteminset  exception is quietly ignored.

The Exclude operation removes the specified item from the given set.  If the given set is 
empty on entry to Exclude, or the given item is not a member of the set  the notinset 
exception is silently ignored and the set remains unchanged.

Union, Intersection, Difference, and SymDifference (symmetric difference) operations all
implement the standard set operations of the same name as defined in the set abstraction
chapter (11).
*)

PROCEDURE Create        (    theType : TypeID (*-- in    *))
                                     : Set    (*-- out   *);

PROCEDURE Destroy       (VAR theSet  : Set    (*-- inout *));

PROCEDURE Clear         (VAR theSet  : Set    (*-- inout *));

PROCEDURE Assign        (    theSet  : Set    (*-- in    *);
                         VAR toSet   : Set    (*-- inout *));

PROCEDURE Include       (    theItem : Item   (*-- in    *);
                         VAR inSet   : Set    (*-- inout *));

PROCEDURE Exclude       (    theItem : Item   (*-- in    *);
                         VAR fromSet : Set    (*-- inout *));

PROCEDURE Union         (    left    : Set    (*-- in    *);
                             right   : Set    (*-- in    *);
                         VAR toSet   : Set    (*-- inout *));

PROCEDURE Intersection  (    left    : Set    (*-- in    *);
                             right   : Set    (*-- in    *);
                         VAR toSet   : Set    (*-- inout *));

PROCEDURE Difference    (    left    : Set    (*-- in    *);
                             right   : Set    (*-- in    *);
                         VAR toSet   : Set    (*-- inout *));

PROCEDURE SymDifference (    left    : Set    (*-- in    *);
                             right   : Set    (*-- in    *);
                         VAR toSet   : Set    (*-- inout *));



(*
13.1.3			Selectors

IsDefined attempts to determine whether the given set is valid, e.g., has been created and
not yet destroyed.  How this is accomplished may be as simple or complicated as the
implementer desires and the requirements of the application.

IsEmpty returns true if the given set contains no items; in other words, its cardinality is
zero.  Undefined sets are always considered empty.

IsEqual returns true if the left and right sets contain the same items.  Obviously, both
must also have the same data type and have been created.  An undefined set is not equal to
any other set, including itself.

The TypeOf routine returns the current TypeID value given the set when it was created or
assigned, and is provided so the user of the module need not maintain a separate variable
recording this information.

NumMembers returns the number of items present on the given set.  Undefined sets are
considered to have no members.

IsAMember returns true if the given item is present in the given set, and false otherwise.

IsSubset and IsProperSubset both implement standard logical set operations as defined in
the Set Abstraction (chapter 11).
*)

PROCEDURE IsDefined     (    theSet  : Set      (*-- in    *))
                                     : BOOLEAN  (*-- out   *);

PROCEDURE IsEmpty       (    theSet  : Set      (*-- in    *))
                                     : BOOLEAN  (*-- out   *);

PROCEDURE IsEqual       (    left    : Set      (*-- in    *);
                             right   : Set      (*-- in    *))
                                     : BOOLEAN  (*-- out   *);

PROCEDURE TypeOf        (    theSet  : Set      (*-- in    *))
                                     : TypeID   (*-- out   *);

PROCEDURE NumMembers    (    theSet  : Set      (*-- in    *))
                                     : CARDINAL (*-- out   *);

PROCEDURE IsAMember     (    theItem : Item     (*-- in    *);
                             theSet  : Set      (*-- in    *))
                                     : BOOLEAN  (*-- out   *);

PROCEDURE IsSubset      (    left    : Set      (*-- in    *);
                             right   : Set      (*-- in    *))
                                     : BOOLEAN  (*-- out   *);

PROCEDURE IsProperSubset(    left    : Set      (*-- in    *);
                             right   : Set      (*-- in    *))
                                     : BOOLEAN  (*-- out   *);



(*
13.1.4			Iterators

The iterator routine LoopOver provides the facility for looping over some or all items of
a set, with read-only access to each item.  theProcess procedure parameter to this routine
returns a BOOLEAN function result where TRUE allows the iteration to proceed to the
next item and FALSE causes the iteration to be terminated.

The Traverse iterator provides the facility for looping over all items of a set, with
read-only access to each item.

Both iterators traverse the given set from the first item towards the last item in ascending
order.  Obviously, if given an empty set the processing procedure will not be invoked.
*)

PROCEDURE LoopOver   (    theSet  : Set            (*-- in    *);
                          process : LoopAccessProc (*-- in    *));

PROCEDURE Traverse   (    theSet  : Set            (*-- in    *);
                          process : AccessProc     (*-- in    *));

END SetSUMI.