PartialOrders.Mesa
Spreitzer, May 10, 1986 6:40:14 pm PDT
Last tweaked by Mike Spreitzer on July 19, 1988 3:44:27 pm PDT
PartialOrders: CEDAR DEFINITIONS
= BEGIN
PartialOrder: TYPE = REF PartialOrderPrivate;
PartialOrderPrivate: TYPE;
IsPartialOrder: PROC [REF ANY] RETURNS [BOOL];
NarrowToPartialOrder: PROC [REF ANY] RETURNS [PartialOrder];
Element: TYPE = REF ANY;
Vertex: TYPE = REF VertexPrivate;
VertexPrivate: TYPE;
IsVertex: PROC [REF ANY] RETURNS [BOOL];
NarrowToVertex: PROC [REF ANY] RETURNS [Vertex];
Create: PROC RETURNS [PartialOrder];
Insert: PROC [po: PartialOrder, elt: Element, lesser, greater: Vertex ← NIL] RETURNS [Vertex];
Relate: PROC [po: PartialOrder, lesser, greater: Vertex];
IsSource: PROC [po: PartialOrder, v: Vertex, dir: Direction] RETURNS [BOOL];
Direction: TYPE = {increasing, decreasing};
Consumer:
TYPE =
PROC [rank:
INT, elt: Element, v: Vertex];
rank is length of maximal path in relevent direction from some source to this vertex; sources have rank 1.
Enumerate:
PROC [po: PartialOrder, direction: Direction, start: Vertex ←
NIL, consume: Consumer];
Enumerates the vertices greater than (or less than) the start vertex, nearer first.
start=NIL means to enumerate the whole graph.
Don't change graph during enumeration.
EnumerateNeighbors:
PROC [po: PartialOrder, direction: Direction, vertex: Vertex ←
NIL, consume: Consumer];
Enumerate only the vertices immediately greater or lesser than the given vertex.
Don't change graph during enumeration.
ComputeDirectDominance: PROC [po: PartialOrder];
EnumerateDirectDominees: PROC [po: PartialOrder, vertex: Vertex ← NIL, consume: Consumer];
END.