StructuralComparisonDataStructure.Mesa
Last Edited by: Spreitzer, May 7, 1986 4:18:50 pm PDT
DIRECTORY Asserting, HashTable, IntHashTableThreaded, IO, Rope;
StructuralComparisonDataStructure: CEDAR DEFINITIONS =
BEGIN
LORA: TYPE = LIST OF REF ANY;
LOLORA: TYPE = LIST OF LORA;
ROPE: TYPE = Rope.ROPE;
RopeList: TYPE = LIST OF ROPE;
SymbolTable: TYPE = HashTable.Table;
Assertions: TYPE = Asserting.Assertions;
ColorTable: TYPE = IntHashTableThreaded.Table;
GraphID: TYPE = {A, B, Unspecified};
RealGraphID: TYPE = GraphID[A .. B];
OtherGraph: ARRAY RealGraphID OF RealGraphID = [A: B, B: A];
graphIDToRope: ARRAY GraphID OF ROPE;
Color: TYPE = INT;
noColor: Color = LAST[Color];
someColor: Color = 871;
FilterColor: PROC [color: Color] RETURNS [filtered: Color] = INLINE {
filtered ← IF color # noColor THEN color ELSE someColor};
VertexClass: TYPE = {net, cell};
OtherClass: ARRAY VertexClass OF VertexClass = [net: cell, cell: net];
CellType: TYPE = REF CellTypeRep;
CellTypeRep: TYPE = RECORD [
name: ROPENIL,
color: Color ← noColor,
ports: PortS ← NIL,
internalsKnown: BOOLFALSE,
firstPart: Vertex ← NIL,
size: INT ← 0, --number of parts
mirror: Vertex ← NIL, --the outside world, as seen from the inside
AM1: A mirror is not entered in its parent's parts list.
AM2: A mirror is not linked in as an instance of its type.
netCount, cellCount: NAT ← 0,
Counts are redundant with parts and asArray.
otherPublic, otherPrivate: Assertions ← NIL];
IsMirror: PROC [v: Vertex] RETURNS [is: BOOL] = INLINE {is ← v.isMirror};
EnumerateParts: PROC [ct: CellType, Consume: PROC [Vertex], mirrorToo: BOOL] = INLINE {
next: Vertex;
FOR v: Vertex ← ct.firstPart, next WHILE v # NIL DO
next ← v.nextPart;
Consume[v]
ENDLOOP;
IF mirrorToo THEN Consume[ct.mirror];
};
PortS: TYPE = REF PortSeq;
PortSeq: TYPE = RECORD [ports: SEQUENCE length: PortIndex OF Port];
PortIndex: TYPE = NAT;
NullPortIndex: PortIndex = LAST[PortIndex];
Port: TYPE = RECORD [name: ROPENIL, net: Vertex ← NIL, other: Assertions ← NIL, color: Color ← noColor];
VertexList: TYPE = LIST OF Vertex;
Vertex: TYPE = REF VertexRep;
VertexRep: PRIVATE TYPE = RECORD [
name: ROPE,
QNext: Vertex ← notInQ,
nextPart: Vertex ← NIL,
colorNext, equiv: Vertex ← NIL,
firstEdge, lastEdge: Edge ← NIL,
type: CellType ← NIL,
other: Assertions ← NIL,
oldColor, curColor: Color ← noColor,
graph: GraphID ← Unspecified,
class: VertexClass,
unique, suspect, isMirror: BOOLFALSE];
Edge: TYPE = REF EdgeRep;
EdgeRep: TYPE = RECORD [
sides: ARRAY VertexClass OF RECORD [v: Vertex, next, prev: Edge],
color: Color];
notInQ: Vertex --don't look:-- = NIL --you looked!--;
endOfQ: Vertex;
ColorData: TYPE = REF ColorDataPrivate;
ColorDataPrivate: TYPE = RECORD [
color: Color,
nextColor: ColorData ← NIL,
firstVertex: Vertex ← NIL,
count: ARRAY RealGraphID OF CARDINAL ← [0, 0],
newColor: Color ← noColor,
suspect, multicolored: BOOLFALSE
];
newColor and multicolored are indexed by oldColor; the rest by curColor.
EnumerateEdges: PROC [v: Vertex, Consume: PROC [Color, Vertex], includeMirror: BOOL] = INLINE {
FOR e: Edge ← v.firstEdge, e.sides[v.class].next WHILE e # NIL DO
w: Vertex = e.sides[OtherClass[v.class]].v;
IF e.sides[v.class].v # v THEN ERROR;
IF includeMirror OR NOT IsMirror[w] THEN Consume[e.color, w];
ENDLOOP;
};
InitialColor: PROC [v: Vertex] RETURNS [Color];
VName: PROC [v: Vertex] RETURNS [r: ROPE] = INLINE {r ← v.name};
OldColor: PROC [v: Vertex] RETURNS [c: Color] = INLINE {c ← v.oldColor};
SetOldColor: PROC [v: Vertex, c: Color] = INLINE {v.oldColor ← c};
CurColor: PROC [v: Vertex] RETURNS [c: Color] = INLINE {c ← v.curColor};
SetCurColor: PROC [v: Vertex, c: Color] = INLINE {v.curColor ← c};
GetGraph: PROC [v: Vertex] RETURNS [g: GraphID] = INLINE {g ← v.graph};
SetGraph: PROC [v: Vertex, g: GraphID] = INLINE {v.graph ← g};
GetUnique: PROC [v: Vertex] RETURNS [b: BOOL] = INLINE {b ← v.unique};
SetUnique: PROC [v: Vertex, b: BOOL] = INLINE {v.unique ← b};
GetSuspect: PROC [v: Vertex] RETURNS [b: BOOL] = INLINE {b ← v.suspect};
SetSuspect: PROC [v: Vertex, b: BOOL] = INLINE {v.suspect ← b};
GetQNext: PROC [v: Vertex] RETURNS [w: Vertex] = INLINE {w ← v.QNext};
SetQNext: PROC [v: Vertex, w: Vertex] = INLINE {v.QNext ← w};
GetColorNext: PROC [v: Vertex] RETURNS [w: Vertex] = INLINE {w ← v.colorNext};
SetColorNext: PROC [v: Vertex, w: Vertex] = INLINE {v.colorNext ← w};
GetEquiv: PROC [v: Vertex] RETURNS [w: Vertex] = INLINE {w ← v.equiv};
SetEquiv: PROC [v: Vertex, w: Vertex] = INLINE {v.equiv ← w};
END.