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;
-- Update positive Edges --
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};
-- Updatge negative Edges --
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.