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.

 ¸DrotCoverImpl.mesa
Copyright Ó 1987 by Xerox Corporation.  All rights reserved.
Csaba Gabor August 20, 1987 2:46:23 pm PDT

Operations on CTrees
This computes whether the two subtrees are similar.  Currently, it only works for non Dags (true trees).  Has to be able to eventually solve NAND(NAND(a,b),NAND(a,c)) and NAND(NAND(a,b),NAND(a,b)).  Dependent code is in Match (see sim field) and TwoifyAllTrees
In the last case there are two ways to combine the children of two nands.
This produces a copy of the (cover) tree handed to it.  This is used when a potential cover is found, to record exactly what it is, since the original will be reused.
This assumes that tree is a true true, and that tree^.csucs is its root
Does the same thing as Replicate with special = NIL, and it copies the mate field.  Demands that ClearScratch be called on the tree containing cv prior to invocation.  It recursively copies the subtree headed by cv (until is runs into a subtree already processed (which is determined by the scratch field))
This creates a new Ctree placing it after cTree in linear order unless cTree = NIL in which case the created Ctree becomes the head of the Treeset --
Takes a tree in ctcoll and causes that tree to be the last in linear order in the ctcoll --
This creates a new node placing it after tree in linear order unless tree = NIL in which case the created node becomes the head of the ctcoll.  ctcoll must not be NIL. --
Completely removes a tree from the ctcoll --
Expects as input a tree with only nands,nots,prims (though that could easily be expanded).  Will return a copy (nt for newtree) of the subtree headed by the input node with the vertex special (in the same tree as v) being treated differently if special # nil.  The difference is that if special is a nand then it is split into two parts according to the binary representation of count.  Demands that ClearScratch be called on the tree containing v prior to call of Replicate.
The map field is used as sort of a scratch pad to keep track of where the replication goes since Replicate is only called on the initial cover trees and never an expanded one.  Scratch is used to keep track of which nodes have already been replicated (0 means not yet, 1 means already).
If there is only one 0 (and there is at least one) then there is no need to create a new left side node.
If there is only one 1 (and there is at least one) then there is no need to create a new right subnode.
This creates a new Dag with no children
Generating All Cover Trees
Given a set of trees with only nands, nots and prims, finds all decompositions where only two-input-nands, nots, and prims are used --
Given an oldtree (which may not be a true tree) this will yield a true tree with equal vertices being mapped onto the same original vertex (via the map field).  This new tree is placed onto the unmap field of the old one (used to be internal but is now external and up to the caller)
This creates a new Dag with no children
Given a Treeset with only nots, nands, and prims, this will find all equivalent trees where no gate has more than two inputs.  Currently, the way this is done is to call it with only one tree in the treeset at a time (this was originally going to make eliminating duplicates easier.  I think it's still a slight win)  --
This is the means by which the splitting up of the children of special is controlled.  After all, they must be split up in all possible ways.  Fortunately, with gates of three or four inputs this is not much.
This produces a copy of tree, modified according to count at special
This yields a vertex (if it does not exist then NIL is returned) which is as far down as possible (in some sense), is not of prim, not, or buf type and has fanin at least 3
Computes base ** exp.  It is naturally more efficient than the version for reals. --
This takes ezt (meaning from) and merges it into ebbe (meaning into).  Every tree in ezt will follow every tree in ebbe in linear order (Ie. ezt is put at the end of ebbe)
Given a collection of trees (not Dags) this will remove any obviously identical ones.  Assumes that the trees are composed of only nands, nots, and prims. --
Covering a Dag
This produces a covering for tree with elements from ctcoll.  The basic idea is that an easy initial covering is found and then that is redone because of nodes with more that one parents.
It is possible to get an obscure error (arising from Match -ing the Nand(a,a) as such.  Prior code should try hard to eliminate these types of cases
From this point down I consider the code to be extremely sensitive.  If you muck with it, be prepared for obscure errors popping up.  A lot of it works because of the order things are done in (that is one reason why OrderNodesByOrphans is called)  As it is, I do not consider the results generated here to be as good as they might be, but (because?) in some sense I have taken the easy way out, which means that despite all good sense to the contrary, this code should work in all cases.
If its used as an internal signal and Matchings needed to be redone
else keep going
If a rematching has to be effected, this will do it and return TRUE, otherwise it will return FALSE
This goes recursively up through the field of parents until it hits an internal node or output on all the recursive branches.  Since each of these reaches at least past iter, with one of them terminating on iter, they may as well all terminate on iter (why stretch past it).  Now, this is a perfectly reasonable thing if we are guaranteed to have this shortened version of each of these covers lying around.  However, there is no such guarantee so that this modified cover may have to be split, and this is the reason for a lot of grief above and below this code.  The reason that we don't have to worry about something from above one of these selected nodes snaking down to or past iter is that it would have been caught and eliminated before.  This is the reason for OrderNodesByOrphans above.
If a particular cover has to be redone, this is what redoes it.
vertex^.cover has been modified (in ModifyCoverToRedoCover) to look the way that we would like our cover to look.  Now, we just have to find the real cover which actually matches our modified version.
This is a slick piece of code.  To recalculate a subcover, we modify that subcover as we wish and then cover that.  Hooray for side effects.  Cs P G.
If selectedTreeNode does not as the input to the cover containng cnode, then we chop off cnode at selectedTreeNode and declare that we want the result as a new cover.
This should reall by called CoverSubtreeWithCover'sCover
CAREFUL!.. This may actually be destroying a better cover, but it seems to me extremely difficult, at best, to determine if this is the situation.  Fortunately, at least it is internally consistent to change the cover.
Adds one to the scratch field of all the internal signals/ inputs acting as inputs to theis cover.  Watch the use!
This tries to cover a Dag with the best fit.  It assumes that each node is only in a tree and not a full Dag.  Done using dynamic programming.  At the end, these will need to be merged --
This checks to see which vertex covers iter best.  It assumes that the vertices below have been covered (in ThisCoverVal) --
This determines whether withThisTree can offer another cover of toBeCovered and if so, finds it.
This checks whether the appropriate nodes from the unmapped version (with which we tried to cover) actually mapped to the same node, and if so accepts it.
Here covertree gets mapped onto maptree.  Covertree is an unmapped version of maptree.  This basically takes the mate field from covertree and puts it onto maptree (while verifying consistency)
This should never be encountered --
For what it's worth, what follows is basically a counting scheme where we count (I think) with the right tree first and when that 'fills up' with the left tree.  The way that we keep track from call to call of where we are is by where the nodes had their mates previously.
There is an obscure error that may happen here if both the children of a nand are identical.  This should never happen, of course.
This computes the size of the cover of ctree^.csucs^.mate.  If ctree^.csucs^.type = prim then there is a serious problem --
This computes the size of the covers at each of the inputs to this particular cover.
�Ê“˜š
œ™Icode™<Kš
œ*™*—K™š
Ïk	˜	Kš
œ#˜#—K˜KšÐln
œ�œ
�˜Kš�œ˜Kš�œ
˜Kšœ�œ
�œ˜!K˜
headš
œ™š
Ïnœ�œ
�œ�œ�œ˜@Kš
œ�
�œ
�œ�œ�œ
�œ�œF™„Kš�œ�œ
�œ
�œ˜,š�œ�˜Kšœ�œ
�œ˜Kšœ�œ;˜HKšœ�œ;˜Hš�œ�œ:�œE˜�
Kš�œ
�œ
�œ
˜š�œ
�œ@�œ@˜Š
Kš�œ
�œ
�œ
˜Kš�œ
�œ
�œ˜——Kš
œI™I—K˜—K˜šŸ	œ�œ
�œ
�œ˜8Kš
œ¦
™¦
Kšœ�œ7�œ�œ˜bKšœÏc#˜8K˜ Kš
œG™GK˜*Kšœ�œ
˜K˜K˜šŸ	œ�œ�œ˜?Kšœ0�œÿ
™²Kš�œ�œ
�œ ˜=š�œ
�˜˜	Kšœ�œ˜.—˜Kšœ�œ˜-—˜K˜,Kšœ�œ˜,K˜—š�œ˜Kš
œ.˜.Kš
œ4˜4Kšœ�œ˜-Kš
œ˜Kš
œ˜——Kšœ *˜@K˜Kšœ 0˜BK˜K˜——K˜šŸœ�œ
�œ#˜<KšœO�œA ™•
Kšœ�œ	˜š�œ�œ
�œ˜K˜K˜—š�œ
�œ	�œ
�œ˜K˜ K˜K˜K˜—š�œ˜K˜K˜š�œ�˜Kš�œ˜Kš�œ˜—K˜—K˜"K˜K˜—K˜šŸœ�œ
�œ
�œ˜2K˜<Kš�œ
�œ�œ˜%K˜—K˜šŸœ�œ!˜5KšœY ™[š�œ�œ
�˜š�œ˜š�œ˜K˜K˜Kšœ
�˜K˜
—š�œ˜K˜K˜K˜K˜K˜Kšœ
�˜Kš
œ˜———K˜—K˜šŸœ�œ�œ˜FKšœL�œT�œ ™ª
Kšœ�œ&˜0š�œ�œ
�œ˜K˜K˜—š�œ
�œ�œ
�œ˜K˜K˜K˜K˜—š�œ˜K˜K˜š�œ�˜Kš�œ˜Kš�œ˜—K˜—K˜K˜—K˜šŸ
œ�œ
�œ!˜8Kšœ* ™,š�œ�œ !˜6Kš�œ˜#Kš�œ˜#—š�œ '˜>Kš�œ˜Kš�œ˜#—š�œ�œ =˜dK˜š�œ�˜$K˜Kš�œ
˜—K˜—K˜K˜—K˜š
Ÿ	œ�œ
�œ*�œ�œ˜\Kš
œÛ™ÛK™žKš�œ�œ
�œ ˜;š�œ�˜Kšœ�œ ˜KKšœ *˜9Kšœ $˜5Kš�œ˜—š�œ�œ�œ˜(Kšœ�œ˜0K˜
K˜K˜@Kš�œ˜—š�œ�œ
�œ˜(Kšœ�œ˜-K˜
K˜š�œ'�œ�œ
�˜=K˜9Kš�œ
˜—Kš�œ˜—š�œ
�œ +˜BKš
œ˜Kšœ�œ˜K˜Kšœ�œ�œ S˜‡
Kšœ; 1˜lKšœ�œ˜-K˜
Kšœ "˜3š�œ;˜=Kš
œh™hKš�œ˜š�œ˜Kšœ�œ�œ˜(Kšœ�œ�œ˜'K˜K˜——š�œ;˜=Kš
œg™gKš�œ˜š�œ˜Kšœ�œ�œ˜(Kšœ�œ�œ >˜gK˜K˜——š�œ�œ
�˜Kšœ*�œ˜2š�œ B˜bKš�œ˜Kš�œ˜—K˜K˜Kš�œ
˜—Kš�œ
˜—K˜—K˜šŸœ�œ�œ˜,Kš
œ'™'Kšœ�œ˜K˜——š
œ™šŸœ�œ
�œ˜1Kšœ„
 ™†
Kšœ�œ˜K˜Kšœ, ­˜ÙKšœ# ˜?š�œ�œ
�œ ˜5Kšœ�œ�œ
˜Kšœ% a˜†
Kšœ�œ˜K˜$K˜&K˜"K˜$K˜ Kšœ \˜rK˜&š�œ�œ
�œ >˜Vš�œ6 ‡
˜¿
š�œ f˜nKšœ	�œ
˜Kš�œ
˜—Kš�œ˜—Kš�œ
˜—š�œ�œ C˜UKšœ A˜ZKšœ#�œ  ˜]Kšœ %˜9—Kš�œ
˜—Kšœ H˜aK˜š	�œ%�œ�œ
�œ ˜Lš�œ.�œ�œ
�˜Hš�œ�œ `˜€
Kšœ+ -˜XKš�œ
˜—Kš�œ
˜—Kš�œ
˜—š�œ%�œ�œ
�˜;š�œ�œ
�œ ˜7š�œ(�œ	�œ
�˜?Kš�œ�œT (˜–
Kš�œ
˜——Kš�œ
˜—K˜K˜šŸœ�œ�œ˜DKš
œ›™›K˜š�œ)�œ�œ
�˜?Kš�œ�œ˜7Kš�œ
˜—K˜K˜K˜šŸœ�œ�œ˜0Kš
œ'™'Kšœ�œ˜Kš
œ˜—K˜šŸ	œ�œ�œ˜IK˜pKšœ!�œR˜vK˜š�œ,�œ�œ
�˜BK˜*K˜Kš�œ
˜—K˜——K˜šŸ
œ�œ˜)Kšœ¾ ™ÀK˜K˜š�œ
�œ�œ P˜iKšœ, 8˜dš�œ�œ
˜š�œ ˜Kšœ
�œ
˜K˜—š�œ˜Kšœ�œ$˜3Kšœ�œ˜Kš
œÐ
™Ð
Kšœ�œ˜š�œ�œ 8˜UK˜%Kšœ 6˜KK˜DKš
œD™DK˜K˜Kšœ, "˜NKšœ�œ
˜K˜Kš�œ
˜—Kšœ 6˜R——K˜Kš�œ
˜—K˜K˜šŸœ�œ�œ�œ˜?Kšœ0�œy™¬
š�œ˜š�œ
�œ�œ˜0Kš�œ+˜/š�œ˜š�œ2�œ�œ
�˜KK˜#Kš�œ�œ
�œ
�œ
˜Kš�œ
˜—Kš�œ�œ˜)———Kš
�˜K˜—K˜š
Ÿœ�œ
�œ�œ�œ˜1KšœR ™Tš�œ�˜Kšœ�œ˜Kšœ�œ˜Kš�œ�œ�œ$˜L—K˜——K˜šŸœ�œ˜%Kš
œ«
™«
š�œ
�˜Kš�œ˜š�œ
�œ�œ
�œ˜K˜š�œ"�œ�œ
�˜8K˜)Kš�œ
˜—K˜K˜!K˜——K˜#K˜—K˜šŸœ�œ˜,Kšœ›
 ™�
K˜š�œ	�œ
�˜K˜š�œ	�œ
�˜š�œ- .˜]š�œ˜K˜K˜K˜
—Kš�œ˜—Kš�œ
˜—K˜Kš�œ
˜—K˜———š
œ™šŸœ�œ
�œ!˜BKš
œ»
™»
K˜Kšœ $˜Bš
œ”
™”
Kš
œç™ç—Kšœ 6˜RK˜K˜š�œ�œ
�œ +˜@š�œ�œ $˜Kš�œ˜Kšœ# ˜:Kš
œ˜—š�œ
˜š�œ�œ5˜OKš
œC™Cš�œ˜Kšœ ˜!K˜—š�œ˜Kš�œ�œ"˜=Kš
œ™K˜————Kš�œ
˜—K˜K˜š
Ÿœ�œ0�œ�œ�œ˜pKš
œc™cš�œ�œ
�˜Kš
œ›™›š�œ�œ˜8Kš�œ�œ(˜AKš�œ�œ@˜Y—K˜Kš�œ
˜—K˜K˜šŸ	œ�œ/�œ�œ˜YKš
œ?™?Kš
œE˜Eš�œ	�œ˜Kš
œÈ
™È
Kšœ �œ g˜�
Kšœ' l˜“
Kšœ% a˜†
KšœB œ
˜Þ
K˜,Kš
ϥ
™•
—K˜K˜šŸœ�œ!�œ�œ˜XKš
œ¦
™¦
š�œ˜!š�œ
�œ˜Kš�œ
�œ
�œ ˜"š�œ˜š�œ1�œ�œ
�˜JKšœ ˜6Kš�œ
˜—Kšœ 1˜FKš�œ
�œ˜
——š�œ
�œ
�˜Kšœ�œB˜OKšœ�œA�œH˜™
Kšœ�œ
�œ˜Kš�œ�˜——K˜—K˜šŸœ�œ˜3Kš
œ8™8š�œ
�˜K˜:˜	K˜3K˜:—šœ�œ�œ˜*Kš
œ.˜.Kš�œÓ
™Ú
Kš
œ8˜8—Kš�œ
˜K˜ —K˜———K˜šŸœ�œ˜*Kš
œr™rš�œ-�œ�œ
�˜CKš�œ�œ/˜HKš�œ
˜—K˜—K˜šŸ
œ�œ
�œ!˜;Kšœ¹
 ™»
K˜K˜K˜š�œ�˜Kš�œ�œ ˜JK˜Kš�œ
˜—Kš�œ�œ !˜RK˜K˜šŸœ�œ#˜0Kšœz ™|K˜Kšœ�œ�œ “
˜¨
š�œ
�œ
�˜š�œ& <˜dš�œ˜K˜&š�œ�œ "˜8Kš�œ" ˜<š�œ
�œ' P˜~Kš�œ# ˜:——Kšœ�œ
˜
—š�œ )˜1Kšœ�œ
˜Kš
œ˜——Kš�œ
˜—K˜K˜š
Ÿœ�œ3�œ�œ�œ˜lKš
œ`™`š�œ�œ  ˜>Kš�œ
�œ4˜?š�œ !˜)š�œ
˜š�œ
�œ:˜Aš�œ
�œ/˜6Kš
œš
™š
Kš�œ
�œ
�œ
˜Kš�œ
�˜	—Kš�œ
�œ
�œ˜——Kšœ�œ ˜)š�œ;�˜BKš�œ0�œ
�œ
�œ˜DKš�œ
˜———K˜K˜š
Ÿœ�œ�œ�œ�œ˜IKš
œÁ
™Á
K˜š�œ+�œ�œ
�˜Aš�œ˜š�œ˜K˜K˜—Kš�œ
�œ�œ
�œ
�œ ˜P—Kš�œ
˜—K˜—K˜šŸœ�œ%�œ�œ�œ�œ�œ˜dKšœ€�œH�œÔ
˜¥š�œ
�œ
�œ�œ
�œ
�œ
�œ˜4Kšœ! ™#—K˜š�œ�˜Kšœ�œ˜šœ�œ�œ�œ˜AKš�œ
�œ
�œ
˜Kš�œ
�œ>�œ˜P—šœ�œ�œ�œ ˜\Kš�œ
�œ
�œ
˜Kš�œ
�œ>�œ˜P—š�œ�œ�œ�œ˜FKš�œ
�œ
�œ
˜Kš
œ�™�š�œ˜Kš
œ$˜$Kš
œ+˜+Kš
œ&˜&Kš
œ-˜-š�œ˜š�œ
�œ
˜Kš�œ
�œ�œ�œ�œ�œ�œ˜Pš�œ
�œ�œ�œ�œ�œ�œ
˜KKš�œ
�œ
�œ
˜Kš�œ
�œ�œ�œ�œ�œ�œ˜P——š�œ
�œ
˜š�œ
�œ�œ�œ
˜)Kš�œ
�œ
�œ
˜Kš�œ
�œ�œ�œ�œ�œ�œ˜Q—š�œ
�œ˜Kš
œ‚
™‚
š�œ
�œ�œ�œ
˜)Kš�œ
�œ
�œ
˜š�œ
�œ�œ�œ�œ�œ�œ
˜LKš�œ
�œ
�œ
˜Kš�œ
�œ�œ�œ�œ�œ�œ˜P——š�œ
�œ�œ�œ
˜(Kš�œ
�œ
�œ
˜Kš�œ
�œ�œ�œ�œ�œ�œ˜S———————K˜——K˜šŸœ�œ�œ
�œ˜<Kš
œ{™{Kš
œ6˜6K˜K˜šŸœ�œ�œ�œ	˜;Kš
œT™Tš�œ#�œ�œ
�˜9š�œ�œ˜0Kš�œ&˜*—Kš�œ
˜—Kš
œ˜——————K˜Kš�œ
˜K˜—…—Nô†?