<> <> <> <<>> DIRECTORY Rope, Convert, DrotBool, DrotCover; DrotCoverImpl: CEDAR MONITOR IMPORTS Rope, Convert, DrotBool EXPORTS DrotCover ~ BEGIN OPEN DrotBool, DrotCover; <> RecurseCSimilar: PUBLIC PROC [cv1, cv2: Node] RETURNS [BOOL] ~ { <> IF cv1^.type # cv2^.type THEN RETURN[FALSE]; SELECT cv1^.type FROM prim => RETURN[TRUE]; buf => RETURN[RecurseCSimilar[cv1^.kidlist^.child,cv2^.kidlist^.child]]; not => RETURN[RecurseCSimilar[cv1^.kidlist^.child,cv2^.kidlist^.child]]; ENDCASE => IF RecurseCSimilar[cv1^.kidlist^.child,cv2^.kidlist^.child] AND RecurseCSimilar[cv1^.kidlist^.next^.child,cv2^.kidlist^.next^.child] THEN RETURN[TRUE] ELSE IF RecurseCSimilar[cv1^.kidlist^.child,cv2^.kidlist^.next^.child] AND RecurseCSimilar[cv1^.kidlist^.next^.child, cv2^.kidlist^.child] THEN RETURN[TRUE] ELSE RETURN[FALSE]; <> }; CopyCTree: PUBLIC PROC [tree: Dag] RETURNS [ct: Dag] ~ { <> ct _ NEW[Degree _ [val: tree^.val, netval: tree^.netval, next: NIL, prev: NIL, cell: tree^.cell]]; ClearScratch[tree]; --Must be called prior to CopyCNode [] _ CopyCNode[tree^.csucs, ct]; <> ct^.csucs^.outname _ tree^.csucs^.outname; ct^.csucs^.output _ TRUE; }; CopyCNode: PROC [cv: Node, ct: Dag] RETURNS [cvertex: Node] ~ { <> IF cv^.scratch = 1 THEN RETURN[cv^.map]; --Already processed SELECT cv^.type FROM prim => { [] _ MakeNewNodeA[ct, NIL, prim, cv^.inname]}; buf => { [] _ MakeNewNodeA[ct, NIL, buf, cv^.inname]}; not => { cvertex _ CopyCNode[cv^.kidlist^.child, ct]; [] _ MakeNewNodeA[ct, NIL, not, cv^.inname]; MakeLink[ct^.csucs, cvertex]}; ENDCASE => { cv1: Node _ CopyCNode[cv^.kidlist^.child, ct]; cv2: Node _ CopyCNode[cv^.kidlist^.next^.child, ct]; [] _ MakeNewNodeA[ct, NIL, nand, cv^.inname]; MakeLink[ct^.csucs, cv1]; MakeLink[ct^.csucs, cv2]}; cvertex _ ct^.csucs; --Because MakeNewNodeA was called with NIL cv^.map _ cvertex; cv^.scratch _ 1; --Registers that this node is already processed. cvertex^.mate _ cv^.mate; }; MakeNewCTree: PUBLIC PROC [treeSet: Treeset, cTree: Dag] ~ { <> temp: Dag _ NEW[Degree]; IF treeSet^.top = NIL THEN { temp^.prev _ temp; treeSet^.top _ temp} ELSE IF cTree = NIL THEN { temp^.prev _ treeSet^.top^.prev; temp^.next _ treeSet^.top; temp^.next^.prev _ temp; treeSet^.top _ temp} ELSE { temp^.prev _ cTree; temp^.next _ cTree^.next; IF cTree^.next = NIL THEN treeSet^.top^.prev _ temp ELSE cTree^.next^.prev _ temp; cTree^.next _ temp}; treeSet^.size _ treeSet^.size + 1; temp^.number _ treeSet^.size }; MakeNewCTreeSet: PUBLIC PROC RETURNS [Treeset] ~ { This creates an empty set of trees used for matching covers. RETURN[NEW[Treesetrec _ [top : NIL]]] }; PlaceTreeAtEnd: PROC [ctcoll: Treeset, tree: Dag] ~ { <> IF tree^.next # NIL THEN IF ctcoll^.top = tree THEN { tree^.prev^.next _ tree; ctcoll^.top _ tree^.next; tree^.next _ NIL } ELSE { ctcoll^.top^.prev^.next _ tree; tree^.next^.prev _ tree^.prev; tree^.prev^.next _ tree^.next; tree^.prev _ ctcoll^.top^.prev; ctcoll^.top^.prev _ tree; tree^.next _ NIL }; }; MakeNewTreeA: PROC [ctcoll: Treeset, tree: Dag] RETURNS[temp: Dag] ~ { <> temp _ NEW[Degree _ [number: ctcoll^.size + 1]]; IF ctcoll^.top = NIL THEN { temp^.prev _ temp; ctcoll^.top _ temp} ELSE IF tree = NIL THEN { temp^.prev _ ctcoll^.top^.prev; temp^.next _ ctcoll^.top; temp^.next^.prev _ temp; ctcoll^.top _ temp} ELSE { temp^.prev _ tree; temp^.next _ tree^.next; IF tree^.next = NIL THEN ctcoll^.top^.prev _ temp ELSE tree^.next^.prev _ temp; tree^.next _ temp}; ctcoll^.size _ ctcoll^.size + 1 }; RemoveTree: PUBLIC PROC [ctcoll: Treeset, tree: Dag] ~ { <> IF tree^.next = NIL --If tree is at the end of ctcoll THEN ctcoll^.top^.prev _ tree^.prev ELSE tree^.next^.prev _ tree^.prev; IF tree = ctcoll^.top --If tree is at the beginning of ctcoll THEN ctcoll^.top _ tree^.next ELSE tree^.prev^.next _ tree^.next; IF tree^.number < ctcoll^.size THEN { --we only want the trees numbered from 1 to ctcoll^.size (-1) iter: Dag _ ctcoll^.top; WHILE iter^.number # ctcoll^.size DO iter _ iter^.next ENDLOOP; iter^.number _ tree^.number}; ctcoll^.size _ ctcoll^.size - 1 }; Replicate: PUBLIC PROC [v: Node, nt: Dag, special: Node, count: INT] RETURNS [top: Node] ~ { <> <> IF v^.scratch = 1 THEN RETURN[v^.map]; --Already processed IF v^.type = prim THEN {top _ MakeNewNodeB[nt, NIL, prim, v^.inname]; --Make the copy of the node v^.map _ top; --Record where the copy of the new node is v^.scratch _ 1; --Note that it's just been processed RETURN}; IF v^.type = not OR v^.type = buf THEN { top _ MakeNewNodeA[nt, NIL, v^.type, v^.inname]; v^.map _ top; v^.scratch _ 1; MakeLink[top, Replicate[v^.kidlist^.child, nt, special, count]]; RETURN}; IF v^.type = nand AND v # special THEN { top _ MakeNewNodeA[nt, NIL, nand, v^.inname]; v^.map _ top; v^.scratch _ 1; FOR iter: Kidptr _ v^.kidlist, iter^.next UNTIL iter = NIL DO MakeLink[top, Replicate[iter^.child, nt, special, count]] ENDLOOP; RETURN}; IF v = special THEN { --If this node has been selected as special kiditer : Kidptr _ v^.kidlist; ct: INT _ 0; topl, topr, topm: Node; countr: ROPE _ Convert.RopeFromInt[count,2,FALSE]; --This generates a pattern according to which we split up the children of this node countr _ Rope.Substr[countr, 1, Rope.Length[countr] - 1]; --We needed the extra 1 to obtain the leading 0s. top _ MakeNewNodeA[nt, NIL, nand, v^.inname]; v^.map _ top; v^.scratch _ 1; --Marking as having been processed IF Rope.Find[countr, "0", Rope.Find[countr, "0", 0] + 1] = -1 <> THEN topl _ top ELSE { topl _ MakeNewNodeB[nt, NIL, nand, NIL]; topm _ MakeNewNodeB[nt, NIL, not, NIL]; MakeLink[top, topm]; MakeLink[topm, topl]}; IF Rope.Find[countr, "1", Rope.Find[countr, "1", 0] + 1] = -1 <> THEN topr _ top ELSE { topr _ MakeNewNodeB[nt, NIL, nand, NIL]; topm _ MakeNewNodeB[nt, NIL, not, NIL]; --We need an intermediate not here since we're not using ands. MakeLink[top, topm]; MakeLink[topm, topr]}; WHILE kiditer # NIL DO res: Node _ Replicate[kiditer^.child, nt, NIL, 0]; IF Rope.Fetch[countr, ct] = '0 --Here is where the children get hooked up to the appropriate side THEN MakeLink[topl,res] ELSE MakeLink[topr,res]; ct _ ct + 1; kiditer _ kiditer^.next; ENDLOOP; RETURN} }; MakeNewTree: PROC [] RETURNS [tree: Dag] ~ { <> tree _ NEW[Degree] }; <> TwoifyAllTrees: PUBLIC PROC [ctcoll: Treeset] ~ { <> count: INT _ 0; repiter : Node; representativesInAcc: Dag _ MakeNewTree[]; --This is used to detect identical cover trees. It contains a representative of each processed tree already made. It is done in a kludgey sort of fashion. For each tree to be represented, a node is created in representativesInAcc whose brother field point to the root of the tree being represented. acc: Treeset _ MakeNewCTreeSet[]; --acc stands for accumulated WHILE ctcoll^.top # NIL DO --for each tree in ctcoll kludge: BOOL _ TRUE; temp : Treeset _ MakeNewCTreeSet[]; --we will make a new Treeset consisting of that tree only (and then remove that tree from ctcoll) [] _ MakeNewTreeA[temp, NIL]; temp^.top^.size _ ctcoll^.top^.size; temp^.top^.csucs _ ctcoll^.top^.csucs; temp^.top^.val _ ctcoll^.top^.val; temp^.top^.cell _ ctcoll^.top^.cell; RemoveTree[ctcoll, ctcoll^.top]; TwoifyAllWays[temp]; --Then we generate all representations of this where the fanin of each nand is limited to 2. repiter _ representativesInAcc^.csucs; WHILE repiter # NIL DO --Now, for each of the representatives in representativesInAcc IF RecurseCSimilar[repiter^.brother, temp^.top^.csucs] -- we compare it to the first of the processed decompositions in temp (Assumes that temp^.top^.csucs is actually the root of a tree) -- THEN { --Here they are found to be similar, so we set a flag not to splice this set of trees in with the rest kludge _ FALSE; EXIT} ELSE repiter _ repiter^.next; ENDLOOP; IF kludge THEN { --If it was a new tree (to the best of our ability to determine so) RemoveDuplicates[temp]; --This eliminates duplicate trees within the newly processed tree MakeNewNodeA[representativesInAcc, NIL]^.brother _ temp^.top^.csucs; --Pick a representative Splice[temp,acc]}; --Add it right in to the growing set. ENDLOOP; ctcoll^.top _ acc^.top; --Here we give everything back to ctcoll, after having taken it all away ctcoll^.size _ acc^.size; FOR iter: Dag _ ctcoll^.top, iter^.next UNTIL iter = NIL DO --for each tree FOR nodeIter: Node _ iter^.csucs, nodeIter^.next UNTIL nodeIter = NIL DO IF nodeIter^.parnum > 1 THEN { --If we have a non true tree then we had better expand it so that we can use it to match covers. iter^.unmap _ MakeUnmappingOfCTree[iter]; --This is where an unmapped version is stored EXIT} ENDLOOP; ENDLOOP; FOR iter: Dag _ ctcoll^.top, iter^.next UNTIL iter = NIL DO IF iter^.unmap = NIL THEN --for each tree not unmapped FOR niter: Node _ iter^.csucs, niter^.next UNTIL niter = NIL DO IF niter^.type = nand THEN niter^.sim _ RecurseCSimilar[niter^.kidlist^.child, niter^.kidlist^.next^.child]; --Check whether it has similar subtrees. ENDLOOP; ENDLOOP; }; MakeUnmappingOfCTree: PROC [oldtree: Dag] RETURNS [newtree: Dag] ~ { <> newtree _ MakeNewBoolTree[]; FOR iter: Node _ oldtree^.csucs, iter^.next UNTIL iter = NIL DO IF iter^.parnum = 0 THEN [] _ RCopyNode[iter, newtree]; ENDLOOP; newtree^.val _ oldtree^.val; }; MakeNewBoolTree: PROC [] RETURNS [tree: Dag] ~ { <> tree _ NEW[Degree] }; RCopyNode: PROC [vertex: Node, newtree: Dag] RETURNS [unmapped: Node] ~ { This unmaps the selected node and its subtree in the fashion of MakeUnmappingOfCTree. Returns the unmapped node unmapped _ MakeNewNodeB[newtree, NIL, vertex^.type, vertex^.inname, vertex^.varname, vertex^.outname, vertex^.output]; unmapped^.map _ vertex; FOR iter: Kidptr _ vertex^.kidlist, iter^.next UNTIL iter = NIL DO w: Node _ RCopyNode[iter^.child, newtree]; MakeLink[unmapped, w]; ENDLOOP; }; TwoifyAllWays: PROC [ctcoll: Treeset] ~ { <> tree: Dag _ ctcoll^.top; OrphansToFront[tree]; WHILE NOT tree^.done DO --The done field is naturally set when you are done processing a particular tree special: Node _ SelectVertex[tree^.csucs]; --This is the vertex we are going to expand on this pass IF special = NIL THEN { --then we're all done tree^.done _ TRUE; PlaceTreeAtEnd[ctcoll, tree]} ELSE { offsethalf: INT _ IntPower[2, special^.kidnum - 1]; offset: INT _ 2*offsethalf; <> count: INT _ 1; WHILE count < offsethalf DO --while we have not yet split it up in all possible ways nt: Dag _ MakeNewTreeA[ctcoll, tree]; ClearScratch[tree]; --Replicate demands that the scratch fields be cleared PlaceAtBeg[nt, Replicate[tree^.csucs, nt, special, offset + count]]; <> nt^.val _ tree^.val; nt^.cell _ tree^.cell; nt^.csucs^.outname _ tree^.csucs^.outname; --nt^.csucs assumed to be the root nt^.csucs^.output _ TRUE; count _ count + 1; ENDLOOP; RemoveTree[ctcoll, tree]}; --If we've had to process a tree, we now get rid of it tree _ ctcoll^.top; ENDLOOP; }; SelectVertex: PROC [vertex: Node] RETURNS [res: Node _ NIL] ~ { <> IF vertex^.type # prim THEN IF vertex^.type = not OR vertex^.type = buf THEN res _ SelectVertex[vertex^.kidlist^.child] ELSE { FOR kiditer: Kidptr _ vertex^.kidlist, kiditer^.next UNTIL kiditer = NIL DO res _ SelectVertex[kiditer^.child]; IF res # NIL THEN RETURN; ENDLOOP; IF vertex^.kidnum > 2 THEN res _ vertex}; RETURN }; IntPower: PROC [base, exp: INT] RETURNS [INT] ~ { <> SELECT exp FROM 0 => RETURN[1]; 1 => RETURN[base]; ENDCASE => RETURN[IntPower[base, exp MOD 2] * IntPower[base * base, exp/2]]; }; Splice: PROC [ezt, ebbe: Treeset] ~ { <> IF ebbe^.top = NIL THEN ebbe^.top _ ezt^.top ELSE IF ezt^.top # NIL THEN { temp : Dag _ ebbe^.top^.prev; FOR iter: Dag _ ezt^.top, iter^.next UNTIL iter = NIL DO iter^.number _ iter^.number + ebbe^.size; ENDLOOP; temp^.next _ ezt^.top; ebbe^.top^.prev _ ezt^.top^.prev; ezt^.top^.prev _ temp}; ebbe^.size _ ebbe^.size + ezt^.size }; RemoveDuplicates: PROC [ctcoll: Treeset] ~ { <> iter1: Dag _ ctcoll^.top; WHILE iter1 # NIL DO iter2: Dag _ iter1^.next; WHILE iter2 # NIL DO IF RecurseCSimilar[iter1^.csucs,iter2^.csucs] --This yields whether two subtrees are similar THEN { temp : Dag _ iter2^.next; RemoveTree[ctcoll, iter2]; iter2 _ temp} ELSE iter2 _ iter2^.next; ENDLOOP; iter1 _ iter1^.next; ENDLOOP; }; <> ProduceTotalCovering: PUBLIC PROC [tree: Dag, ctcoll: Treeset] ~ { <> iter: Node; CoverAndYield[tree, ctcoll]; --This produces the inital covering. <> <> OrderNodesByOrphans[tree]; --Put nodes in a useful order for the following lines. ClearScratch[tree]; iter _ tree^.csucs; WHILE iter # NIL DO --Now, for each node, starting with orphans IF iter^.output AND iter^.type # prim --if it's an output but not an input THEN { LabelCoverEndpoints[iter^.cover]; --a non recursive call. iter _ iter^.next} ELSE IF (iter^.scratch > 0) AND RedoMatchingOfAncestors[iter^.parlist, iter, ctcoll] <> THEN { ClearScratch[tree]; --start over iter _ tree^.csucs} ELSE { IF (iter^.type # prim) THEN LabelCoverEndpoints[iter^.cover]; <> iter _ iter^.next}; ENDLOOP; }; RedoMatchingOfAncestors: PROC [pariter: Kidptr, iter: Node, ctcoll: Treeset] RETURNS [changed: BOOL _ FALSE] ~ { <> WHILE pariter # NIL DO <> IF pariter^.child^.scratch > 0 OR pariter^.child^.output THEN changed _ changed OR RedoCover[pariter^.child, iter, ctcoll] ELSE changed _ changed OR RedoMatchingOfAncestors[pariter^.child^.parlist, iter, ctcoll]; pariter _ pariter^.next; ENDLOOP; }; RedoCover: PROC [vertex, selectedNode: Node, ctcoll: Treeset] RETURNS [changed: BOOL] ~ { <> changed _ ModifyCoverToRedoCover[vertex^.cover^.csucs, selectedNode]; IF changed THEN { <> KillHangingNodes[vertex^.cover, TRUE]; --Who knows what nodes we just got rid of. We won't want any extras floating around for the next step. CoverAndYield[vertex^.cover, ctcoll]; --AHA! Why not make some use of all the code we just wrote. We may as well go with the best (ahem...cover). OrderNodesByOrphans[vertex^.cover]; --This should be exterranneous since node order is not modified anywhere. I suggest removing it. CoverSubtreeWithCoversCover[vertex^.cover^.csucs^.cover^.csucs]; --The really neat thing about this is that it is guaranteed to produce a tree which ProduceTotalCover will be able to purcolate farther down than last time. vertex^.cover _ vertex^.cover^.csucs^.cover} <> }; ModifyCoverToRedoCover: PROC [cnode, selectedTreeNode: Node] RETURNS [changed: BOOL] ~ { <> IF cnode^.mate = selectedTreeNode THEN IF cnode^.type = prim THEN RETURN[FALSE] --It's OK here ELSE { FOR kiditer: Kidptr _ cnode^.kidlist, kiditer^.next UNTIL kiditer = NIL DO [] _ KillCLink[kiditer]; --We chop off the tree here. ENDLOOP; cnode^.type _ prim; --And it's important to now be declared as input. RETURN[TRUE]} ELSE SELECT cnode^.type FROM not => RETURN[ModifyCoverToRedoCover[cnode^.kidlist^.child, selectedTreeNode]]; nand => RETURN [ModifyCoverToRedoCover[cnode^.kidlist^.child,selectedTreeNode] OR ModifyCoverToRedoCover[cnode^.kidlist^.next^.child, selectedTreeNode]]; prim => RETURN[FALSE]; ENDCASE => NULL }; CoverSubtreeWithCoversCover: PROC [cnode: Node] ~ { <> SELECT cnode^.type FROM not => CoverSubtreeWithCoversCover[cnode^.kidlist^.child]; nand => { CoverSubtreeWithCoversCover[cnode^.kidlist^.child]; CoverSubtreeWithCoversCover[cnode^.kidlist^.next^.child]}; prim => IF cnode^.mate^.type # prim THEN { cnode^.mate^.mate^.cover _ cnode^.mate^.cover; <> CoverSubtreeWithCoversCover[cnode^.mate^.cover^.csucs]}; ENDCASE; cnode^.mate _ cnode^.mate^.mate; }; LabelCoverEndpoints: PROC [cTree: Dag] ~ { <> FOR iter: Node _ cTree^.csucs^.next, iter^.next UNTIL iter = NIL DO IF iter^.type = prim THEN iter^.mate^.scratch _ iter^.mate^.scratch + 1; ENDLOOP; }; CoverAndYield: PUBLIC PROC [tree: Dag, ctcoll: Treeset] ~ { <> iter: Node; OrderNodesByPrims[tree]; iter _ tree^.csucs^.prev; WHILE iter# tree^.csucs DO IF iter^.type # prim THEN Coverup[iter, ctcoll]; --This does the covering iter _ iter^.prev; ENDLOOP; IF iter^.type # prim THEN Coverup[iter, ctcoll] --Have to cover the top node, too }; Coverup: PROC [iter: Node, ctcoll : Treeset] ~ { <> iterct: Dag _ ctcoll^.top; newp : BOOL _ TRUE; --a particular tree may yield more than one cover. newp TRUE indicates that this is the first time we have tried to cover with a particular ctree. WHILE iterct # NIL DO IF PassesCoverTest[iter, iterct, newp] --This routine searches for a cover and reports it if found. THEN { iterct^.netval _ ThisCoverVal[iterct]; IF iter^.cover = NIL --If there is no current cover yet THEN iter^.cover _ CopyCTree[iterct] --then accept this one ELSE IF iterct^.netval < iter^.cover^.netval --otherwise check to see if the newly generated cover is better than the old one THEN iter^.cover _ CopyCTree[iterct]; --if so, accept it. newp _ FALSE} ELSE { --If no cover found, go to the next ctree newp _ TRUE; iterct _ iterct^.next}; ENDLOOP; }; PassesCoverTest: PROC [toBeCovered: Node, withThisTree: Dag, firstTime: BOOL] RETURNS [coverFound: BOOL] ~ { <> IF withThisTree^.unmap = NIL --if withThisTree is a true tree THEN RETURN[Match[toBeCovered, withThisTree^.csucs, firstTime]] ELSE { --withThisTree had to be Unmapped IF firstTime THEN IF Match[toBeCovered, withThisTree^.unmap^.csucs, firstTime] THEN IF VerifyCover[withThisTree, withThisTree^.unmap] <> THEN RETURN[TRUE] ELSE NULL ELSE RETURN[FALSE]; firstTime _ FALSE; --An unused statement WHILE Match[toBeCovered, withThisTree^.unmap^.csucs, firstTime] DO IF VerifyCover[withThisTree, withThisTree^.unmap] THEN RETURN[TRUE]; ENDLOOP} }; VerifyCover: PROC [maptree, covertree: Dag] RETURNS [ok: BOOL _ TRUE] ~ { <> ClearScratch[maptree]; FOR iter: Node _ covertree^.csucs, iter^.next UNTIL iter = NIL DO IF iter^.map^.scratch = 0 THEN { iter^.map^.mate _ iter^.mate; iter^.map^.scratch _ 1} ELSE IF iter^.map^.mate # iter^.mate THEN RETURN[FALSE]; --Oops. Inconsistency ENDLOOP; }; Match: PROC [vertex: Node, cvertex: Node, newp: BOOL, notFirstPass: BOOL _ FALSE] RETURNS [BOOL] ~ { This is the workhorse of the whole covering routine. Don't try to understand this; just pray that it works. It is an ennumeration/verification scheme for covers all rolled into one. I have no idea whether all portions of this have been exercised. newp TRUE indicates that we want the first possible match of this subtree, while FALSE indicates that we want the next possible match. notFirstPass is necessary to avoid having outputs misinterpreted since they are treated as primitives (inputs) unless the original call to Match is with an output IF vertex = NIL OR cvertex = NIL THEN RETURN[FALSE]; <> cvertex^.mate _ vertex; SELECT cvertex^.type FROM prim => RETURN[newp]; not => IF vertex^.type # not OR (notFirstPass AND vertex^.output) THEN RETURN[FALSE] ELSE RETURN[Match[vertex^.kidlist^.child, cvertex^.kidlist^.child, newp, TRUE]]; buf => IF vertex^.type # buf OR (notFirstPass AND vertex^.output)--Should not be encountered THEN RETURN[FALSE] ELSE RETURN[Match[vertex^.kidlist^.child, cvertex^.kidlist^.child, newp, TRUE]]; ENDCASE => IF vertex^.type # nand OR (notFirstPass AND vertex^.output) THEN RETURN[FALSE] <> ELSE { left: Node _ vertex^.kidlist^.child; right: Node _ vertex^.kidlist^.next^.child; cleft: Node _ cvertex^.kidlist^.child; cright: Node _ cvertex^.kidlist^.next^.child; IF newp THEN IF cvertex^.sim THEN RETURN[Match[left, cleft, TRUE, TRUE] AND Match[right, cright, TRUE, TRUE]] ELSE IF Match[left, cleft, TRUE, TRUE] AND Match[right, cright, TRUE, TRUE] THEN RETURN[TRUE] ELSE RETURN[Match[right, cleft, TRUE, TRUE] AND Match[left, cright, TRUE, TRUE]] ELSE IF cvertex^.sim THEN IF Match[right, cright, FALSE, TRUE] THEN RETURN[TRUE] ELSE RETURN[Match[left, cleft, FALSE, TRUE] AND Match[right, cright, TRUE, TRUE]] ELSE IF cleft^.mate = left <> THEN IF Match[right, cright, FALSE, TRUE] THEN RETURN[TRUE] ELSE IF Match[left, cleft, FALSE, TRUE] AND Match[right, cright, TRUE, TRUE] THEN RETURN[TRUE] ELSE RETURN[Match[right, cleft, TRUE, TRUE] AND Match[left, cright, TRUE, TRUE]] ELSE IF Match[left, cright, FALSE, TRUE] THEN RETURN[TRUE] ELSE RETURN[Match[right, cleft, FALSE, TRUE] AND Match[left, cright, TRUE, TRUE]]}; }; ThisCoverVal: PROC [ctree: Dag] RETURNS [coversize: INT] ~ { <> coversize _ ctree^.val + RecurseCoverVal[ctree^.csucs] }; RecurseCoverVal: PROC [cv: Node] RETURNS [acc: INT _ 0] ~ { <> FOR iter: Node _ cv^.next, iter^.next UNTIL iter = NIL DO IF iter^.type = prim AND iter^.mate^.type # prim THEN acc _ acc+ iter^.mate^.cover^.netval; ENDLOOP; }; END.