StructuralComparisonDataStructureImpl.Mesa
Last tweaked by Mike Spreitzer on March 24, 1987 2:51:44 pm PST
DIRECTORY Asserting, Rope, StructuralComparisonDataStructure, StructuralComparisonOps;
StructuralComparisonDataStructureImpl:
CEDAR
PROGRAM
IMPORTS Asserting, Rope, StructuralComparisonDataStructure
EXPORTS StructuralComparisonDataStructure, StructuralComparisonOps =
BEGIN OPEN StructuralComparisonDataStructure;
graphIDToRope: PUBLIC GraphDescriptions ← [A: "A", B: "B", Unspecified: "Unspecified"];
transistorTolerancesKey: PUBLIC ATOM ← $StructuralComparisonTransistorTolerances;
defaultTransistorTolerances: PUBLIC TransistorTolerances ~ NEW [TransistorTolerancesPrivate ← ALL[[1.0E-6, 1.0E6]]];
TransistorDimName: PUBLIC ARRAY TransistorDim OF ROPE ← ["length", "width"];
endOfQ: PUBLIC Vertex ← NEW [VertexRep];
initialNetColor: Color ← 1;
mirrorColor: Color ← 2;
InitialColor:
PUBLIC
PROC [v: Vertex]
RETURNS [initialColor: Color] = {
SELECT v.class
FROM
net => initialColor ← initialNetColor;
cell => initialColor ← IF IsMirror[v] THEN mirrorColor ELSE v.type.color;
ENDCASE => ERROR;
initialColor ← FilterColor[initialColor];
};
MergeVertices:
PUBLIC
PROC [parent: CellType, v1, v2: Vertex]
RETURNS [merged, doomed: Vertex] =
BEGIN
MoveToMerged:
PROC [e: Edge] = {
e.sides[net].v ← merged;
};
IF v1 = v2 THEN RETURN [v1, NIL];
merged ← v1;
doomed ← v2;
IF merged.deleted OR doomed.deleted THEN ERROR;
IF merged.class # doomed.class THEN ERROR;
doomed.better ← merged;
merged.name ← UnionNames[merged.name, doomed.name];
SELECT merged.class
FROM
net => {
EnumerateFullEdges[doomed, MoveToMerged, FALSE];
IF doomed.firstEdge #
NIL
THEN {
IF merged.lastEdge # NIL THEN merged.lastEdge.sides[net].next ← doomed.firstEdge ELSE merged.firstEdge ← doomed.firstEdge;
merged.lastEdge ← doomed.lastEdge;
doomed.firstEdge.sides[net].prev ← merged.lastEdge;
doomed.firstEdge ← NIL;
doomed.lastEdge ← NIL;
};
};
cell => -- If they're cells, the caller asserts that they are connected identically — i.e., nothing needs to be done but delete the doomed vertex and the edges touching it.-- NULL;
ENDCASE => ERROR;
DeleteVertex[parent, doomed];
merged.other ← Asserting.Union[merged.other, doomed.other];
END;
UnionNames:
PROC [n1, n2:
ROPE]
RETURNS [un:
ROPE] = {
un ← IF n1.Length[] = 0 THEN n2 ELSE IF n2.Length[] = 0 THEN n1 ELSE n1.Cat["|", n2];
};
DeleteVertex:
PUBLIC
PROC [parent: CellType, v: Vertex] = {
Killit:
PROC [e: Edge] = {
RemoveEdge[e];
};
EnumerateFullEdges[v, Killit, FALSE];
v.deleted ← TRUE;
SELECT v.class
FROM
cell => parent.cellCount ← parent.cellCount - 1;
net => parent.netCount ← parent.netCount - 1;
ENDCASE => ERROR;
parent.size ← parent.size - 1;
};
RemoveEdge:
PUBLIC
PROC [e: Edge] = {
FOR dir: VertexClass
IN VertexClass
DO
[e.sides[dir].v.firstEdge, e.sides[dir].v.lastEdge] ← UnlinkEdge[e.sides[dir].v.firstEdge, e.sides[dir].v.lastEdge, e, dir];
ENDLOOP;
};
UnlinkEdge:
PROC [head, tail, e: Edge, dir: VertexClass]
RETURNS [newHead, newTail: Edge] = {
newHead ← head; newTail ← tail;
IF e.sides[dir].next # NIL THEN e.sides[dir].next.sides[dir].prev ← e.sides[dir].prev ELSE newTail ← e.sides[dir].prev;
IF e.sides[dir].prev # NIL THEN e.sides[dir].prev.sides[dir].next ← e.sides[dir].next ELSE newHead ← e.sides[dir].next;
};
END.