GraphsImpl.Mesa
Mike Spreitzer September 27, 1986 3:13:40 pm PDT
DIRECTORY Asserting, Graphs, Rope;
GraphsImpl:
CEDAR
PROGRAM
IMPORTS Asserting, Rope
EXPORTS Graphs =
BEGIN OPEN Graphs;
Error: PUBLIC ERROR [code: ErrorCode, msg: ROPE ← NIL] = CODE;
ErrorCodeName: PUBLIC ARRAY ErrorCode OF ROPE ← ["Cant", "BadArgs"];
DeleteVertex:
PUBLIC
PROC [vertex: Vertex]
--VertexDestroyer-- = {
IF vertex.class.Delete # NIL THEN vertex.class.Delete[vertex] ELSE Error[Cant];
};
EqualVertices:
PUBLIC
PROC [v1, v2: Vertex]
RETURNS [eq:
BOOL]
--VertexEqualityTester-- = {
eq ← IF v1.class.Equal # NIL THEN v1.class.Equal[v1, v2] ELSE IF v2.class.Equal # NIL THEN v2.class.Equal[v2, v1] ELSE Error[Cant];
};
HashVertex:
PUBLIC
PROC [v: Vertex]
RETURNS [hash:
CARDINAL]
--VertexHasher-- = {
hash ← IF v.class.Hash # NIL THEN v.class.Hash[v] ELSE Error[Cant];
};
GetVertexOther:
PUBLIC
PROC [v: Vertex]
RETURNS [other: Asserting.Assertions]
--VertexGetOtherProc-- = {
Give: PROC [got: Asserting.Assertions] RETURNS [Asserting.Assertions] = {RETURN [other ← got]};
IF v.class.GetOther # NIL THEN other ← v.class.GetOther[v] ELSE IF v.class.ChangeOther # NIL THEN v.class.ChangeOther[v, Give] ELSE other ← NIL;
};
ChangeVertexOther:
PUBLIC
PROC [v: Vertex,
Change:
PROC [Asserting.Assertions]
RETURNS [Asserting.Assertions]]
--VertexChangeOtherProc-- = {
IF v.class.ChangeOther # NIL THEN v.class.ChangeOther[v, Change] ELSE Error[Cant];
};
GetVertexLabel:
PUBLIC
PROC [vertex: Vertex]
RETURNS [label: Label]
--VertexGetLabelProc-- = {
label ← IF vertex.class.GetLabel # NIL THEN vertex.class.GetLabel[vertex] ELSE unlabeled;
};
Expand:
PUBLIC
PROC [vertex: Vertex,
Consume: EdgeConsumer, filter: DirectionFilter ← allDirections]
--ExpandProc-- = {
IF vertex.class.Expand # NIL THEN vertex.class.Expand[vertex, Consume, filter] ELSE Error[Cant];
};
EnumerateForLabels:
PUBLIC
PROC [vertex: Vertex,
Consume: LabelConsumer, filter: DirectionFilter ← allDirections]
--LabelEnumerator-- = {
(IF vertex.class.EnumerateForLabels # NIL THEN vertex.class.EnumerateForLabels ELSE EnumerateForLabelsFromExpand)[vertex, Consume, filter]
};
EnumerateForLabelsFromExpand:
PUBLIC
PROC [vertex: Vertex,
Consume: LabelConsumer, filter: DirectionFilter ← allDirections]
--LabelEnumerator-- = {
PerEdge:
PROC [edge: Edge, direction: Direction, otherSide: Vertex] = {
Consume[direction, GetEdgeLabel[edge], GetVertexLabel[otherSide]]};
Expand[vertex, PerEdge, filter];
};
GetNeighbor:
PUBLIC
PROC [vertex: Vertex, filter: DirectionFilter ← allDirections, edgeLabel, vertexLabel: Label ← unlabeled, index: Index ← noIndex, goal: Vertex ← nullVertex]
RETURNS [edge: Edge, neighbor: Vertex]
--NeighborGetter-- = {
[edge, neighbor] ← (IF vertex.class.GetNeighbor # NIL THEN vertex.class.GetNeighbor ELSE GetNeighborFromExpand)[vertex, filter, edgeLabel, vertexLabel, index, goal];
};
GetNeighborFromExpand:
PUBLIC
PROC [vertex: Vertex, filter: DirectionFilter ← allDirections, edgeLabel, vertexLabel: Label ← unlabeled, index: Index ← noIndex, goal: Vertex ← nullVertex]
RETURNS [edge: Edge, neighbor: Vertex]
--NeighborGetter-- = {
i: INT ← 0;
ans: Edge ← nullEdge;
PerEdge:
PROC [edge: Edge, direction: Direction, otherSide: Vertex] = {
IF NOT filter[direction] THEN ERROR;
IF index # noIndex AND index # (i ← i + 1) THEN RETURN;
{inconsistent:
BOOL =
goal # nullVertex AND NOT EqualVertices[otherSide, goal] OR
edgeLabel # unlabeled AND NOT GetEdgeLabel[edge].Equal[edgeLabel] OR
vertexLabel # unlabeled AND NOT GetVertexLabel[otherSide].Equal[vertexLabel];
IF index # noIndex
THEN {
IF inconsistent THEN Error[BadArgs, "Inconsistent edge specification"];
ans ← edge;
neighbor ← goal;
Abort};
IF inconsistent THEN RETURN;
IF goal # nullVertex OR edgeLabel # unlabeled OR vertexLabel # unlabeled THEN {ans ← edge; neighbor ← otherSide; Abort};
}};
neighbor ← nullVertex;
Expand[vertex, PerEdge, filter !Abort => CONTINUE];
edge ← ans;
};
Abort: ERROR = CODE;
GetNeighborCount:
PUBLIC
PROC [vertex: Vertex, filter: DirectionFilter ← allDirections]
RETURNS [neighborCount:
INT]
--NeighborCountProc-- = {
neighborCount ← (IF vertex.class.GetNeighborCount # NIL THEN vertex.class.GetNeighborCount ELSE IF vertex.class.EnumerateForLabels # NIL THEN GetNeighborCountFromLabels ELSE GetNeighborCountFromExpand)[vertex, filter];
};
GetNeighborCountFromLabels:
PUBLIC
PROC [vertex: Vertex, filter: DirectionFilter ← allDirections]
RETURNS [neighborCount:
INT]
--NeighborCountProc-- = {
PerLabel:
PROC [direction: Direction, edgeLabel, vertexLabel: Label] = {
neighborCount ← neighborCount + 1;
};
neighborCount ← 0;
vertex.class.EnumerateForLabels[vertex, PerLabel, filter];
};
GetNeighborCountFromExpand:
PUBLIC
PROC [vertex: Vertex, filter: DirectionFilter ← allDirections]
RETURNS [neighborCount:
INT]
--NeighborCountProc-- = {
PerEdge:
PROC [edge: Edge, direction: Direction, otherSide: Vertex] = {
neighborCount ← neighborCount + 1;
};
neighborCount ← 0;
vertex.class.Expand[vertex, PerEdge, filter];
};
AddEdge:
PUBLIC
PROC [v1, v2: Vertex, direction: Direction, label: Label, other: Asserting.Assertions]
RETURNS [edge: Edge]
--EdgeAdder-- = {
IF v1.class.AddEdge # NIL THEN edge ← v1.class.AddEdge[v1, v2, direction, label, other] ELSE IF v2.class.AddEdge # NIL THEN edge ← v2.class.AddEdge[v2, v1, ReverseDirection[direction], label, other] ELSE Error[Cant];
};
NewVertexClass:
PUBLIC
PROC [vtp: VertexClassPrivate]
RETURNS [vt: VertexClass] = {
vt ← NEW [VertexClassPrivate ← vtp];
};
DeleteEdge:
PUBLIC
PROC [e: Edge]
--EdgeDeleter-- = {
IF e.class.Delete # NIL THEN e.class.Delete[e] ELSE Error[Cant]};
GetEdgeLabel:
PUBLIC
PROC [e: Edge]
RETURNS [l: Label]
--EdgeGetLabelProc-- = {
l ← IF e.class.GetLabel # NIL THEN e.class.GetLabel[e] ELSE unlabeled};
GetEdgeOther:
PUBLIC
PROC [e: Edge]
RETURNS [other: Asserting.Assertions]
--EdgeGetOtherProc-- = {
Get: PROC [got: Asserting.Assertions] RETURNS [Asserting.Assertions] = {RETURN [other ← got]};
IF e.class.GetOther # NIL THEN other ← e.class.GetOther[e] ELSE IF e.class.ChangeOther # NIL THEN e.class.ChangeOther[e, Get] ELSE other ← NIL
};
ChangeEdgeOther:
PUBLIC
PROC [e: Edge,
Change:
PROC [Asserting.Assertions]
RETURNS [Asserting.Assertions]]
--EdgeChangeOtherProc-- = {
IF e.class.ChangeOther # NIL THEN e.class.ChangeOther[e, Change] ELSE Error[Cant];
};
NewEdgeClass:
PUBLIC
PROC [ecp: EdgeClassPrivate]
RETURNS [ec: EdgeClass] = {
ec ← NEW [EdgeClassPrivate ← ecp]};
dullEdgeClass: EdgeClass = NewEdgeClass[[Delete: NIL, ChangeOther: NIL]];
dullEdge: PUBLIC Edge ← [NIL, dullEdgeClass];
GetGraphOther:
PUBLIC
PROC [g: Graph]
RETURNS [other: Asserting.Assertions]
--GraphOtherGetter-- = {
Get: PROC [got: Asserting.Assertions] RETURNS [Asserting.Assertions] = {RETURN [other ← got]};
IF g.class.GetOther # NIL THEN other ← g.class.GetOther[g] ELSE IF g.class.ChangeOther # NIL THEN g.class.ChangeOther[g, Get] ELSE other ← NIL;
};
ChangeGraphOther:
PUBLIC
PROC [g: Graph,
Change:
PROC [Asserting.Assertions]
RETURNS [Asserting.Assertions]]
--GraphOtherChanger-- = {
IF g.class.ChangeOther # NIL THEN g.class.ChangeOther[g, Change] ELSE Error[Cant]};
EnumerateVertices:
PUBLIC
PROC [graph: Graph,
Consume:
PROC [Vertex]] = {
graph.class.EnumerateVertices[graph, Consume];
};
DestroyGraph:
PUBLIC
PROC [graph: Graph] = {
IF graph.class.Destroy # NIL THEN graph.class.Destroy[graph];
};
NewGraphClass:
PUBLIC
PROC [gp: GraphClassPrivate]
RETURNS [g: GraphClass] = {
g ← NEW [GraphClassPrivate ← gp];
};
AssertOtherProc:
PUBLIC
PROC [key:
ATOM, proc: Proc, inAdditionTo: Asserting.Assertions ←
NIL]
RETURNS [allTogetherNow: Asserting.Assertions] = {
allTogetherNow ← Asserting.AssertFn1[key, NEW [Proc ← proc], inAdditionTo]};
GetOtherProc:
PUBLIC
PROC [key:
ATOM, from: Asserting.Assertions]
RETURNS [proc: Proc] = {
rp: REF ANY = Asserting.FnVal[key, from];
proc ←
WITH rp
SELECT
FROM
x: REF Proc => x^,
ENDCASE => NIL;
};
END.