Sets.mesa
Last Edited by: Arnon, April 28, 1987 9:22:37 am PDT
Finite subsets of some Structure. Also, create Structures which are such sets. OrderedSets are a subclass.
DIRECTORY
Rope,
IO,
AlgebraClasses;
Sets: CEDAR DEFINITIONS
~ BEGIN OPEN Rope, AC: AlgebraClasses;
Set Representation
Set: TYPE = AC.Object;
SetData: TYPE = LIST OF AC.Object;
The elements of SetData are assumed to be distinct.
The empty set is represented by NIL SetData.
For OrderedSets, the elements of SetData are assumed to be in increasing order.
Instance Data for Family of Sets Structures
FamilyOfSetsStructureData: TYPE = REF FamilyOfSetsStructureDataRec;
FamilyOfSetsStructureDataRec:
TYPE =
RECORD [
universe: AC.Object -- the elements of the Structure are the subsets of universe
];
Operations for Family of Sets Structures
MakeFamilyOfSetsStructure:
AC.SequenceStructureConstructor;
FamilyOfSetsPrintName:
AC.ToRopeOp;
FamilyOfSetsShortPrintName:
AC.ToRopeOp;
IsFamilyOfSetsStructure:
AC.UnaryPredicate;
Universe:
AC.UnaryOp;
arg is a Family of Sets Structure; result is its universe
Conversion and IO for Elements of Family of Sets Structures
FamilyOfSetsRecast:
AC.BinaryOp;
FamilyOfSetsCanRecast:
AC.BinaryPredicate;
FamilyOfSetsToExpr:
AC.ToExprOp;
FamilyOfSetsLegalFirstChar:
AC.LegalFirstCharOp;
FamilyOfSetsRead:
AC.ReadOp;
FamilyOfSetsFromRope:
AC.FromRopeOp;
FamilyOfSetsToRope:
AC.ToRopeOp;
FamilyOfSetsWrite: AC.WriteOp;
Constructor for Family of Sets Structures
MakeSet:
AC.ListImbedOp;
Currently no checks for repetitions of elements, or for proper ordering if OrderedSet.
Does check that supplied elements actually belong to universe (recasts if necessary).
data = NIL => empty set.
Instance Data for Single Set Structures
SingleSetStructureData: TYPE = REF SingleSetStructureDataRec;
SingleSetStructureDataRec:
TYPE =
RECORD [
underlyingSet: AC.Object -- the elements of the Structure are the elements of underlyingSet
];
Elements of SingleSetStructures are represented as elements of the universe of the FamilyOfSets Structure to which underlyingSet belongs (i.e. same rep as elements of underlyingSet), except that their class fields are reset to point to the SingleSetStructure
Operations for Single Set Structures
MakeSingleSetStructure:
AC.StructureFromSetConstructor;
SingleSetPrintName:
AC.ToRopeOp;
SingleSetShortPrintName:
AC.ToRopeOp;
IsSingleSetStructure:
AC.UnaryPredicate;
UnderlyingSet:
AC.UnaryOp;
arg is a SingleSetStructure; result is its underlyingSet
Conversion and IO for Elements of Single Set Structures
SingleSetRecast:
AC.BinaryOp;
SingleSetCanRecast:
AC.BinaryPredicate;
SingleSetToExpr:
AC.ToExprOp;
SingleSetLegalFirstChar:
AC.LegalFirstCharOp;
SingleSetRead:
AC.ReadOp;
SingleSetFromRope:
AC.FromRopeOp;
SingleSetToRope:
AC.ToRopeOp;
SingleSetWrite:
AC.WriteOp;
UnderlyingSetUniverseEltFromSSSElt:
AC.UnaryOp;
SSSEltFromUnderlyingSetUniverseElt:
AC.BinaryOp;
secondArg is a Single Set Structure, firstArg is an element of its underlyingSet represented as an element of the underlyingSet's universe. result is (a copy of) firstArg with its class reset to secondArg
IsVariable:
AC.UnaryPredicate;
check whether arg is a variable represented as an element of a SingleSetStructure
VariableFromRope:
AC.FromRopeOp;
Get a variable from a rope, and recast it as an element of the SingleSetStructure consisting of itself as the only element
Set Predicates
IsElement:
AC.BinaryPredicate;
firstArg is an Object, and secondArg is a Set. Returns TRUE if firstArg is an element of secondArg.
IsSubset:
AC.BinaryPredicate;
firstArg and secondArg are Sets. Returns TRUE if firstArg is a subset of secondArg.
Set Operations
Cardinality:
AC.ElementRankOp;
Equal:
AC.BinaryPredicate;
Intersection:
AC.BinaryOp;
MapUnaryElementOp:
AC.BinaryMixedOp;
firstArg is a Set, secondArg is REF to UnaryOp on its elementStructure, result is Set of results of applications of UnaryOp to elements of firstArg.
Note that, by elimination of duplicates, cardinality of result may be less that cardinality of argument.
It is assumed that the values of application of UnaryOp to elements of firstArg all belong to the same Structure. If this is an ordered structure, then the elements of the result set should be sorted to give a proper OrderedSet representation.
Set Selection (OrderedSets only)
Select:
AC.BinaryOp;
firstArg is an OrderedSet, secondArg is an Ints.Int specifying position to select. Returns NIL if can't do.
First:
AC.UnaryOp;
firstArg = OrderedSet, return first element. Return NIL if empty.
Last:
AC.UnaryOp;
firstArg = OrderedSet, return last element. Return NIL if empty.
Public Structure
VariableSets: AC.Object; -- public structure that has special $variable method for variable eval (see impl)
END.