biagioni@unc.UUCP (Edoardo Biagioni) (11/06/86)
(***************************************************************************)
(*** ***)
(*** ***)
(*** O S S I ***)
(*** ========== ***)
(*** ***)
(**) DEFINITION MODULE SISets; (**)
(*** ======================== ***)
(*** ***)
(*** Defines sets of cardinals with any number of elements. ***)
(*** ***)
(***---------------------------------------------------------------------***)
(*** ***)
(*** Hardware: independent ***)
(*** Operating System: independent ***)
(*** Compiler: independent ***)
(*** ***)
(*** Version: 2.0 ***)
(*** Implemented: see copyright ***)
(*** Date: 1986-02-28 ***)
(*** ***)
(***---------------------------------------------------------------------***)
(*** ***)
(*** Copyright 1984, 1985, 1986 by ***)
(*** E. S. Biagioni ***)
(*** G. Heiser ***)
(*** K. Hinrichs ***)
(*** C. Muller ***)
(*** ***)
(*** Institut fuer Informatik ***)
(*** ETH Zuerich ***)
(*** CH 8092 Zuerich ***)
(*** Switzerland ***)
(*** ***)
(*** Department of Computer Science ***)
(*** University of North Carolina ***)
(*** Chapel Hill, North Carolina 27514 ***)
(*** U.S.A. ***)
(*** ***)
(***---------------------------------------------------------------------***)
(*** ***)
(*** Updates: ***)
(*** ***)
(*** ***)
(***************************************************************************)
(* "Set"s are sets of almost any size. The maximum allowable
size is determined by the machine's range of cardinals and
available memory space, not by the machine word length.
SISets allow programs which use large sets to be portable.
The range of a geven Set is defined by the numerical values
of the smallest and of the largest elements the Set can hold.
The cardinality of a Set is defined as the number of elements
it contains. Thus an empty Set has a cardinality of 0, a
full Set (a set that contains all elements that fit in its
declared range) has the cardinality given by the largest
value minus the smallest value + 1.
A set must be allocated using CreateSet before it can be
used. When it is no longer needed, it must be returned
using ReturnSet.
Set elements may range in value from 0 to MaxElement
inclusive. Sets must be created using CreateSet before
being used, and returned using ReturnSet when they are
no longer needed. Individual elements may be set by using
Include, and reset (taken out of the Set) by using Exclude.
IncludeRange and ExcludeRange are used to set or reset
several elements with a single procedure call and are
provided for convenience. The presence or absence
of an element in a Set can be tested by using IsIncluded.
The operations Union, Intersection, SetDiff and SymmetricDiff
function as the corresponding set operations if their Set
arguments all have the same range. If Sets of different ranges
are used, the result for each case is the same as if all Sets
were extended to the maximum size, without including any new
elements, then the result Set truncated to fit its original
size. Copying of Sets is not explicitly provided since it
may be achieved by the union of a Set with itself.
The procedures SetToBytes and BytesToSet allow the storage
of Sets on storage systems external to the module SISets.
The function SetStorage returns the number of bytes required
to store a given Set. Any assumptions about how much storage
a Set uses are nonportable and should not be used.
RangeIs returns the smallest and largest values that can be
stored in a given Set, as they were defined in the call to
CreateSet. LeastElement returns the lowest-valued element stored
in the given Set, LargestElement the element with the highest
value. Predecessor and Successor can be used to obtain the next
higher or lower element of the Set. *)
FROM SISystem IMPORT
SIResult,
BYTE;
EXPORT QUALIFIED
Set,
CreateSet,
ReturnSet,
SetRangeIs,
IsIncluded,
Include,
Exclude,
IncludeRange,
ExcludeRange,
Union,
Intersection,
SetDiff,
SymmetricDiff,
Complement,
Cardinality,
LeastElement,
LargestElement,
Predecessor,
Successor,
SetStorage,
SetToBytes,
BytesToSet;
TYPE Set;
PROCEDURE CreateSet (VAR set: Set; first, last: CARDINAL;
VAR result: SIResult);
(* must be called before ANY use of the variable "set". The returned
set is empty, "Complement" can be used to make it full.
result will be SISystem.SIDone if enough memory was available for the
set, something else otherwise *)
PROCEDURE ReturnSet (VAR set: Set);
(* must be called to return the storage used by the variable "set" *)
PROCEDURE SetRangeIs (set: Set; VAR first, last: CARDINAL);
(* Returns the range of the set. *)
PROCEDURE IsIncluded (element: CARDINAL; set: Set): BOOLEAN;
(* Returns TRUE if and only if the element is in the set *)
PROCEDURE Include (element: CARDINAL; VAR set: Set);
(* Includes 'element' in the set, if it falls within the given
range. If not, nothing happens *)
PROCEDURE Exclude (element: CARDINAL; VAR set: Set);
(* Excludes 'element' from the set, if the element is in the
correct range for the set. If not, nothing happens *)
PROCEDURE IncludeRange (fromElement, toElement: CARDINAL;
VAR set: Set);
(* includes the range fromElement..toElement (inclusive) in
the set. Any elements which would lie outside the set's
range are not included *)
PROCEDURE ExcludeRange (fromElement, toElement: CARDINAL;
VAR set: Set);
(* excludes the range fromElement..toElement (inclusive)
from the set. *)
(* In the following 4 operations, the result set MUST
have been created using CreateSet *)
PROCEDURE Union (set1, set2: Set; VAR union: Set);
(* returns the union of set1 and set2. An element is in union if
it is in set1 or in set2 or in both, and if it falls within
the range of union. It is legal to have union be the same
variable as set1 or set2 or both. *)
PROCEDURE Intersection (set1, set2: Set; VAR intersection: Set);
(* returns the intersection of set1 and set2. An element is in
intersection if and only if it is in both set1 and set2,
and if it falls within the range of intersection. It is
legal to have intersection be the same variable as set1 or
set2 or both. *)
PROCEDURE SetDiff (set1, set2: Set; VAR difference: Set);
(* returns the difference of set1 and set2. An element is in
difference if and only if it is in set1 but not in set2,
and it falls within the range of difference. It is legal
to have difference be the same variable as set1 or set2 or
both. *)
PROCEDURE SymmetricDiff (set1, set2: Set; VAR xor: Set);
(* returns the symmetric set difference of set1 and set2.
An element is in xor if it is in set1 or in set2
but not in both, and if it falls within the range of
xor. It is legal to have xor be the same
variable as set1 or set2 or both. *)
PROCEDURE Cardinality (set: Set): CARDINAL;
(* returns the number of elements in the set *)
PROCEDURE Complement (VAR set: Set);
(* returns the complement of set. An element is in the
complement if it is not in set, and vice versa *)
PROCEDURE LeastElement (set: Set; VAR element: CARDINAL;
VAR notEmpty: BOOLEAN);
(* This finds the set element with lowest ordinal number, if any.
and returns it in element. If the set is empty, notEmpty is
returned FALSE and element is undefined. *)
PROCEDURE LargestElement (set: Set; VAR element: CARDINAL;
VAR notEmpty: BOOLEAN);
(* This finds the set element with largest ordinal number, if any.
and returns it in element. If the set is empty, notEmpty is
returned FALSE and element is undefined. *)
PROCEDURE Predecessor (set: Set; VAR element: CARDINAL;
VAR hasPredecessor: BOOLEAN);
(* finds next element included in the "set" with ordinal number
greater than "element"; if no such element exists the value of
"hasPredecessor" will be FALSE *)
PROCEDURE Successor (set: Set; VAR element: CARDINAL;
VAR hasSuccessor: BOOLEAN);
(* finds next element included in the "set" with ordinal number
greater than "element"; if no such element exists the value of
"hasSuccessor" will be FALSE *)
PROCEDURE SetStorage (set: Set): CARDINAL;
(* this value is the number of bytes required to store the set
when using SetToBytes. The amount of storage is independent
of the contents of the set and only depends on the set's range *)
PROCEDURE SetToBytes (set: Set; VAR bytes: ARRAY OF BYTE;
startIndex: CARDINAL; VAR result: SIResult);
(* stores the set set into the buffer Bytes beginning at startIndex.
result is different from SISystem.SIDone if the set is invalid or
if it doesn't fit into the buffer. The storage required is
SetStorage (set) bytes. *)
PROCEDURE BytesToSet (VAR set: Set; VAR bytes: ARRAY OF BYTE;
startIndex: CARDINAL; VAR result: SIResult);
(* creates a new set equal to the one that was previously stored
in the buffer bytes starting at startIndex (The data may have
been copied around, and the buffer need not be the same as was
used for SetToBytes. Only the data needs to be the same).
If these conditions are observed and enough storage is available,
result will be SIDone, it will be something else otherwise.
Notice the Set "set" will be created by this call, so if it
is a preexisting set some storage will become inaccessible. *)
END SISets.