PartialOrdersImpl.Mesa
Spreitzer, December 7, 1985 5:17:55 pm PST
Last tweaked by Mike Spreitzer on July 19, 1988 3:46:49 pm PDT
DIRECTORY Basics, PartialOrders, RedBlackTree;
PartialOrdersImpl:
CEDAR
PROGRAM
IMPORTS RedBlackTree
EXPORTS PartialOrders
= BEGIN OPEN PartialOrders;
PartialOrder: TYPE = REF PartialOrderPrivate;
PartialOrderPrivate:
PUBLIC
TYPE =
RECORD [
extreme: ARRAY Direction OF Vertex
];
VertexList: TYPE = LIST OF Vertex;
Vertex: TYPE = REF VertexPrivate;
VertexPrivate:
PUBLIC
TYPE =
RECORD [
elt: Element,
succs: ARRAY Direction OF VertexList ← ALL[NIL],
rank:
ARRAY Direction
OF
INT ←
ALL[0],
Length of longest path in given direction to here.
directDominator: Vertex ← NIL,
directDominees: VertexList ← NIL
];
IsPartialOrder:
PUBLIC
PROC [ra:
REF
ANY]
RETURNS [b:
BOOL] = {
b ← ISTYPE[ra, PartialOrder]};
NarrowToPartialOrder:
PUBLIC
PROC [ra:
REF
ANY]
RETURNS [po: PartialOrder] = {
po ← NARROW[ra]};
IsVertex:
PUBLIC
PROC [ra:
REF
ANY]
RETURNS [b:
BOOL] = {
b ← ISTYPE[ra, Vertex]};
NarrowToVertex:
PUBLIC
PROC [ra:
REF
ANY]
RETURNS [v: Vertex] = {
v ← NARROW[ra]};
Create:
PUBLIC
PROC
RETURNS [po: PartialOrder] = {
v0: Vertex =
NEW [VertexPrivate ← [
elt: NIL,
rank: [increasing: 0, decreasing: 1]
]];
vf: Vertex =
NEW [VertexPrivate ← [
elt: NIL,
rank: [decreasing: 0, increasing: 1]
]];
v0.succs[increasing] ← LIST[vf];
vf.succs[decreasing] ← LIST[v0];
po ←
NEW [PartialOrderPrivate ← [
extreme: [increasing: vf, decreasing: v0]
]];
};
Insert:
PUBLIC
PROC [po: PartialOrder, elt: Element, lesser, greater: Vertex ←
NIL]
RETURNS [v: Vertex] = {
IF lesser = NIL THEN lesser ← po.extreme[decreasing];
IF greater = NIL THEN greater ← po.extreme[increasing];
v ←
NEW [VertexPrivate ← [
elt: elt,
succs: [
increasing: LIST[greater],
decreasing: LIST[lesser]],
rank: [
increasing: lesser.rank[increasing]+1,
decreasing: greater.rank[decreasing]+1]
]];
IF lesser = po.extreme[increasing] OR greater = po.extreme[decreasing] THEN ERROR;
lesser.succs[increasing] ← CONS[v, lesser.succs[increasing]];
greater.succs[decreasing] ← CONS[v, greater.succs[decreasing]];
UpdateRank[increasing, greater, v];
UpdateRank[decreasing, lesser, v];
};
UpdateRank:
PROC [direction: Direction, v, prec: Vertex] = {
IF v.rank[direction] <= prec.rank[direction]
THEN {
v.rank[direction] ← prec.rank[direction] + 1;
FOR sl: VertexList ← v.succs[direction], sl.rest
WHILE sl #
NIL
DO
UpdateRank[direction, sl.first, v];
ENDLOOP;
v ← v;
};
prec ← prec;
};
Relate:
PUBLIC
PROC [po: PartialOrder, lesser, greater: Vertex] = {
IF lesser = po.extreme[increasing] OR greater = po.extreme[decreasing] THEN ERROR;
lesser.succs[increasing] ← CONS[greater, lesser.succs[increasing]];
greater.succs[decreasing] ← CONS[lesser, greater.succs[decreasing]];
UpdateRank[increasing, greater, lesser];
UpdateRank[decreasing, lesser, greater];
};
IsSource:
PUBLIC
PROC [po: PartialOrder, v: Vertex, dir: Direction]
RETURNS [
BOOL] ~ {
RETURN [v.rank[dir]=1]};
Enumerate:
PUBLIC
PROC [po: PartialOrder, direction: Direction, start: Vertex ←
NIL, consume: Consumer] = {
inOrder: RedBlackTree.Table =
SELECT direction
FROM
increasing => RedBlackTree.Create[GetKey, IncCompare],
decreasing => RedBlackTree.Create[GetKey, DecCompare],
ENDCASE => ERROR;
ExploreFrom:
PROC [v: Vertex, insert:
BOOL] = {
IF v = po.extreme[direction] THEN RETURN;
IF insert THEN inOrder.Insert[v, v !RedBlackTree.DuplicateKey => GOTO Old];
FOR vl: VertexList ← v.succs[direction], vl.rest
WHILE vl #
NIL
DO
ExploreFrom[vl.first, TRUE];
ENDLOOP;
v ← v;
};
PerVertex:
PROC [data:
REF
ANY]
RETURNS [stop:
BOOL ←
FALSE]
--RedBlackTree.EachNode-- = {
v: Vertex = NARROW[data];
consume[v.rank[direction], v.elt, v];
};
IF start #
NIL
THEN ExploreFrom[start, TRUE]
ELSE ExploreFrom[po.extreme[Opposite[direction]], FALSE];
inOrder.EnumerateIncreasing[PerVertex];
};
Opposite: ARRAY Direction OF Direction = [increasing: decreasing, decreasing: increasing];
GetKey:
PROC [data:
REF
ANY]
RETURNS [k:
REF
ANY]
--RedBlackTree.GetKey-- = {
k ← data;
};
IncCompare:
PROC [k, data:
REF
ANY]
RETURNS [c: Basics.Comparison] = {
k1: Vertex = NARROW[k];
k2: Vertex = NARROW[data];
c ←
SELECT k1.rank[increasing]-k2.rank[increasing]
FROM
< 0 => less,
= 0 =>
SELECT
LOOPHOLE[k1,
INT]-
LOOPHOLE[k2,
INT]
FROM
< 0 => less,
= 0 => equal,
> 0 => greater,
ENDCASE => ERROR,
> 0 => greater,
ENDCASE => ERROR;
};
DecCompare:
PROC [k, data:
REF
ANY]
RETURNS [c: Basics.Comparison] = {
k1: Vertex = NARROW[k];
k2: Vertex = NARROW[data];
c ←
SELECT k1.rank[decreasing]-k2.rank[decreasing]
FROM
< 0 => less,
= 0 =>
SELECT
LOOPHOLE[k1,
INT]-
LOOPHOLE[k2,
INT]
FROM
< 0 => less,
= 0 => equal,
> 0 => greater,
ENDCASE => ERROR,
> 0 => greater,
ENDCASE => ERROR;
};
EnumerateNeighbors:
PUBLIC
PROC [po: PartialOrder, direction: Direction, vertex: Vertex ←
NIL, consume: Consumer] = {
nextRank: INT;
IF vertex = NIL THEN vertex ← po.extreme[Opposite[direction]];
nextRank ← vertex.rank[direction] + 1;
FOR sl: VertexList ← vertex.succs[direction], sl.rest
WHILE sl #
NIL
DO
next: Vertex = sl.first;
IF next.rank[direction] = nextRank AND next # po.extreme[direction] THEN consume[nextRank, next.elt, next];
ENDLOOP;
};
GotIt: ERROR = CODE;
ComputeDirectDominance:
PUBLIC
PROC [po: PartialOrder] = {
ClearDominance:
PROC [rank:
INT, elt: Element, v: Vertex] = {
v.directDominator ← NIL;
v.directDominees ← NIL;
};
SetDominance:
PROC [rank:
INT, elt: Element, v: Vertex] = {
ENABLE GotIt => GOTO Dun;
y: Vertex = v;
yRank: INT = rank;
curRank: INT ← rank;
seenHere: INT ← 2;
x: Vertex ← NIL;
SeeGreater:
PROC [rank:
INT, elt: Element, v: Vertex] = {
IF rank = curRank
THEN seenHere ← seenHere + 1
ELSE {
IF seenHere = 1
THEN {
y.directDominator ← x;
x.directDominees ← CONS[y, x.directDominees];
GotIt;
};
seenHere ← 1;
curRank ← rank;
};
x ← v;
};
Enumerate[po, increasing, v, SeeGreater];
SeeGreater[curRank+1, po.extreme[increasing].elt, po.extreme[increasing]];
SeeGreater[curRank+1, NIL, NIL];
ERROR;
EXITS Dun => v ← v;
};
Enumerate[po, increasing, NIL, ClearDominance];
ClearDominance[0, NIL, po.extreme[increasing]];
ClearDominance[0, NIL, po.extreme[decreasing]];
Enumerate[po, increasing, NIL, SetDominance];
};
EnumerateDirectDominees:
PUBLIC
PROC [po: PartialOrder, vertex: Vertex ←
NIL, consume: Consumer] = {
IF vertex = NIL THEN vertex ← po.extreme[increasing];
FOR vl: VertexList ← vertex.directDominees, vl.rest
WHILE vl #
NIL
DO
v: Vertex = vl.first;
consume[v.rank[decreasing], v.elt, v];
ENDLOOP;
po ← po;
};
END.