DIRECTORY CCG; CCGImpl: CEDAR PROGRAM EXPORTS CCG = BEGIN OPEN CCG; Ref: TYPE = REF Rep; Rep: PUBLIC TYPE = RECORD[size: NAT _ 0, vertices: ARRAY NodeIndex OF ChNode]; ChNode: TYPE = RECORD[ ch: REF _ NIL, negEdges, posEdges: Edges _ NIL, negPosition: INT _ LAST[INT], posPosition: INT _ FIRST[INT], negInCount, posInCount: NAT _ 0]; Edges: TYPE = REF EdgesRep; EdgesRep: TYPE = RECORD[size: NAT _ 0, edgeArray: ARRAY EdgeIndex OF Edge]; Edge: TYPE = RECORD[node: NodeIndex, wt: INT]; EdgeIndex: TYPE = [1..MaxEdges]; InvalidNode: PUBLIC ERROR = CODE; FindRootError: PUBLIC ERROR[reason: Reasons1] = CODE; AssignNodeError: PUBLIC ERROR[reason: Reasons2] = CODE; Create: PUBLIC PROC[] RETURNS[Ref] = {RETURN[NEW[Rep]]}; -- Create -- CreateNode: PUBLIC PROC[grph: Ref, ch: REF _ NIL] RETURNS[NodeIndex] = { grph.size _ grph.size + 1; grph.vertices[grph.size] _ ChNode[ch: ch, negEdges: NEW[EdgesRep], posEdges: NEW[EdgesRep]]; RETURN[grph.size] }; -- CreateNode -- DestroyNode: PUBLIC PROC[grph: Ref, node: NodeIndex, p: CleanUpChsProc] = { size: NodeIndex = grph.size; IF node > size THEN ERROR InvalidNode; p[grph.vertices[node].ch, grph.vertices[size].ch]; grph.vertices[node] _ grph.vertices[size]; grph.vertices[size] _ ChNode[]; grph.size _ size - 1; }; -- DestroyNode -- Size: PUBLIC PROC [grph: Ref] RETURNS [NAT] ={RETURN [grph.size]}; --Size-- ConstrainNodes: PUBLIC PROC[grph: Ref, negNd, posNd: NodeIndex, wt: INT] = { posEdges: Edges _ grph.vertices[negNd].posEdges; pDone: BOOL _ FALSE; negEdges: Edges _ grph.vertices[posNd].negEdges; nDone: BOOL _ FALSE; FOR i: EdgeIndex IN [1..posEdges.size] DO IF posEdges.edgeArray[i].node = posNd THEN { posEdges.edgeArray[i].wt _ MAX[wt, posEdges.edgeArray[i].wt]; pDone _ TRUE; EXIT} ENDLOOP; IF NOT pDone THEN { posEdges.size _ posEdges.size + 1; posEdges.edgeArray[posEdges.size] _ Edge[posNd, wt]; grph.vertices[posNd].posInCount _ grph.vertices[posNd].posInCount.SUCC}; FOR i: EdgeIndex IN [1..negEdges.size] DO IF negEdges.edgeArray[i].node = negNd THEN { negEdges.edgeArray[i].wt _ MAX[wt, negEdges.edgeArray[i].wt]; nDone _ TRUE; EXIT} ENDLOOP; IF NOT nDone THEN { negEdges.size _ negEdges.size +1; negEdges.edgeArray[negEdges.size] _ Edge[negNd, wt]; grph.vertices[negNd].negInCount _ grph.vertices[negNd].negInCount.SUCC}; }; --ConstrainNodes-- CyclicConstrainp: PUBLIC PROC [grph: Ref, negNd, posNd: NodeIndex] RETURNS [cyclic: BOOL] ={ posNdNbrs: ARRAY NodeIndex OF NodeIndex; nbrsCount: NAT _ 0; findNbrs: PROC RETURNS [BOOL] ={ nd: NodeIndex; IF nbrsCount = 0 THEN {cyclic _ FALSE; RETURN[TRUE]} ELSE {nd _ posNdNbrs[nbrsCount]; nbrsCount _ nbrsCount.PRED}; FOR nbrNo: NAT _ grph.vertices[nd].posEdges.size, nbrNo.PRED UNTIL nbrNo = 0 DO ndNbr: NodeIndex _ grph.vertices[nd].posEdges.edgeArray[nbrNo].node; IF ndNbr = negNd THEN {cyclic _ TRUE; RETURN[TRUE]} ELSE {posNdNbrs[(nbrsCount _ nbrsCount.SUCC)] _ ndNbr} ENDLOOP; RETURN [FALSE]; }; --findNbrs-- posNdNbrs[(nbrsCount _ nbrsCount.SUCC)] _ posNd; THROUGH [0..grph.size * MaxEdges) DO IF findNbrs[] THEN RETURN ENDLOOP; ERROR; --Implies that there is already a loop in the constraint graph-- }; --CyclicConstrainp-- ResetNode: PUBLIC PROC[grph: Ref, nd: NodeIndex] = { ch: REF _ grph.vertices[nd].ch; posEdges: Edges _ grph.vertices[nd].posEdges; negEdges: Edges _ grph.vertices[nd].negEdges; posEdges.size _ 0; negEdges.size _ 0; grph.vertices[nd] _ ChNode[ch: ch, negEdges: negEdges, posEdges: posEdges]; }; --ResetNode-- ResetAllNodes: PUBLIC PROC[grph: Ref] ={ FOR nd: NodeIndex IN [1..grph.size] DO ResetNode[grph, nd] ENDLOOP; }; --ResetAllNodes-- PosAssignNodePosition: PUBLIC PROC[grph: Ref, root: NodeIndex] ={ nodes: ARRAY NodeIndex OF NodeIndex; indexHd, indexTl: NAT _ 0; IF grph.vertices[root].posInCount # 0 THEN ERROR AssignNodeError[NotARoot]; nodes[indexTl _ indexTl + 1] _ root; THROUGH [0..grph.size) DO { n0: NodeIndex _ nodes[indexHd _ indexHd +1]; edges: Edges; nodePstn: INT; IF indexHd > indexTl THEN ERROR AssignNodeError[CyclicGraph]; edges _ grph.vertices[n0].posEdges; nodePstn _ grph.vertices[n0].posPosition; FOR i: EdgeIndex IN [1..edges.size] DO{ nbdNode: NodeIndex _ edges.edgeArray[i].node; newPstn: INT _ nodePstn + edges.edgeArray[i].wt; oldPstn: INT _ grph.vertices[nbdNode].posPosition; IF newPstn > oldPstn THEN grph.vertices[nbdNode].posPosition _ newPstn; IF (grph.vertices[nbdNode].posInCount _ grph.vertices[nbdNode].posInCount - 1) = 0 THEN {nodes[indexTl _ indexTl +1] _ nbdNode}; } ENDLOOP; grph.vertices[n0].posEdges.size _ 0; -- Remove all the edges -- } ENDLOOP; }; -- PosAssignNodePosition-- NegAssignNodePosition: PUBLIC PROC[grph: Ref, root: NodeIndex] ={ nodes: ARRAY NodeIndex OF NodeIndex; indexHd, indexTl: NAT _ 0; IF grph.vertices[root].negInCount # 0 THEN ERROR AssignNodeError[CyclicGraph]; nodes[indexTl _ indexTl + 1] _ root; THROUGH [0..grph.size) DO { n0: NodeIndex _ nodes[indexHd _ indexHd +1]; edges: Edges; nodePstn: INT; IF indexHd > indexTl THEN ERROR AssignNodeError[CyclicGraph]; edges _ grph.vertices[n0].negEdges; nodePstn _ grph.vertices[n0].negPosition; FOR i: EdgeIndex IN [1..edges.size] DO{ nbdNode: NodeIndex _ edges.edgeArray[i].node; newPstn: INT _ nodePstn - edges.edgeArray[i].wt; oldPstn: INT _ grph.vertices[nbdNode].negPosition; IF newPstn < oldPstn THEN grph.vertices[nbdNode].negPosition _ newPstn; IF (grph.vertices[nbdNode].negInCount _ grph.vertices[nbdNode].negInCount - 1) = 0 THEN {nodes[indexTl _ indexTl +1] _ nbdNode}; } ENDLOOP; grph.vertices[n0].negEdges.size _ 0; -- Remove all the edges -- } ENDLOOP; }; -- NegAssignNodePosition-- NodePosition: PUBLIC PROC[grph: Ref, nd: NodeIndex, which: GraphDirection] RETURNS[INT] = { SELECT which FROM pos => RETURN[grph.vertices[nd].posPosition]; neg => RETURN[grph.vertices[nd].negPosition]; ENDCASE => ERROR; }; --NodePosition-- SetNodePosition: PUBLIC PROC[grph: Ref, nd: NodeIndex, which: GraphDirection, position: INT] = { SELECT which FROM pos => grph.vertices[nd].posPosition _ position; neg => grph.vertices[nd].negPosition _ position; ENDCASE => ERROR; }; --SetNodePosition -- FindRoot: PUBLIC PROC[grph: Ref, which: GraphDirection] RETURNS[nd: NodeIndex] = { found: BOOL _ FALSE; SELECT which FROM pos => FOR i: NAT IN [1..grph.size] DO IF grph.vertices[i].posInCount = 0 THEN { IF found THEN { ERROR FindRootError[MulitpleRoots]} ELSE {found _ TRUE; nd _ i}} ENDLOOP; neg => FOR i: NAT IN [1..grph.size] DO IF grph.vertices[i].negInCount = 0 THEN { IF found THEN { ERROR FindRootError[MulitpleRoots]} ELSE {found _ TRUE; nd _ i}} ENDLOOP; ENDCASE => ERROR; IF found THEN NULL ELSE {ERROR FindRootError[NoRoot]}; }; -- FindRoot -- GetCh: PUBLIC PROC[grph: Ref, nd: NodeIndex] RETURNS [REF] ={ RETURN [grph.vertices[nd].ch]}; --GetCh-- Chs: PUBLIC PROC [grph: Ref, p: EachChAction] RETURNS [BOOL] ={ FOR i: NAT IN [1..grph.size] DO IF p[grph.vertices[i].ch] THEN RETURN [FALSE] ENDLOOP; RETURN[TRUE]}; --Chs-- END. ¸-- File: CCGImpl.mesa -- Last Edited by: CSChow, January 17, 1985 10:57:00 pm PST -- Note: CCG = ChannelConstraintGraph -- Update positive Edges -- -- Updatge negative Edges -- Ê˜Jšœ™Jšœ;™;J˜Jšœ%™%J˜šÏk ˜ Jšœ˜—J˜J˜šœ œ˜Jš œœœœœ˜J˜Jšœœœ˜Jš œœœœœœœ ˜NJ˜šœœœ˜Jšœœœ˜Jšœœ˜ Jš œ œœœœœœ˜K– "Cedar" stylešœ#˜#K– "Cedar" stylešœ)˜)– "Cedar" stylešœœœ˜'K– "Cedar" stylešœ-˜-K– "Cedar" stylešœ œ$˜0K– "Cedar" stylešœ œ&˜2K– "Cedar" stylešœœ.˜GK– "Cedar" stylešœQœ)˜€K– "Cedar" stylešœœ˜ —K– "Cedar" stylešœ%Ÿ˜?K– "Cedar" style˜K– "Cedar" stylešœ˜—K– "Cedar" stylešœŸœŸœ˜—K– "Cedar" style˜K– "Cedar" style˜– "Cedar" stylešžœœœ˜AK– "Cedar" stylešœœœ˜$K– "Cedar" stylešœœ˜K– "Cedar" stylešœ$œœ˜OK– "Cedar" style˜$– "Cedar" stylešœœ˜K– "Cedar" stylešœ,˜,K– "Cedar" stylešœ ˜ K– "Cedar" stylešœ œ˜K– "Cedar" stylešœœœ˜>K– "Cedar" stylešœ#˜#K– "Cedar" stylešœ)˜)– "Cedar" stylešœœœ˜'K– "Cedar" stylešœ-˜-K– "Cedar" stylešœ œ$˜0K– "Cedar" stylešœ œ&˜2K– "Cedar" stylešœœ.˜GK– "Cedar" stylešœQœ)˜€K– "Cedar" stylešœœ˜ —K– "Cedar" stylešœ%Ÿ˜?K– "Cedar" style˜K– "Cedar" stylešœ˜—K– "Cedar" stylešœŸœŸœ˜—K– "Cedar" style˜– "Cedar" styleš žœœœ2œœ˜[– "Cedar" stylešœ˜K– "Cedar" stylešœœ ˜-K– "Cedar" stylešœœ ˜-K– "Cedar" stylešœœ˜—K– "Cedar" stylešœŸ˜—K– "Cedar" style˜– "Cedar" stylešžœœœ<œ˜`– "Cedar" stylešœ˜K– "Cedar" stylešœ0˜0K– "Cedar" stylešœ0˜0K– "Cedar" stylešœœ˜—K– "Cedar" stylešœŸ˜—K– "Cedar" style˜– "Cedar" stylešžœœœ#œ˜RK– "Cedar" stylešœœœ˜– "Cedar" stylešœ˜– "Cedar" stylešœœœœ˜&– "Cedar" stylešœ!œ˜)– "Cedar" stylešœœ˜K– "Cedar" stylešœœ œ ˜@——K– "Cedar" stylešœ˜—– "Cedar" stylešœœœœ˜&– "Cedar" stylešœ!œ˜)– "Cedar" stylešœœ˜K– "Cedar" stylešœœ œ ˜@——K– "Cedar" stylešœ˜ —K– "Cedar" stylešœœ˜—K– "Cedar" styleš œœœœœ˜6K– "Cedar" stylešœŸ˜—K– "Cedar" style˜– "Cedar" stylešžœœœœ˜=K– "Cedar" stylešœŸœ˜)—K– "Cedar" style˜– "Cedar" styleš žœœœœœ˜?– "Cedar" stylešœœœ˜Kšœœœœ˜-Kšœ˜—KšœœŸœ˜—K– "Cedar" style˜K– "Cedar" stylešœ˜——…—/d