DrotCoverImpl.mesa
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
Csaba Gabor August 20, 1987 2:46:23 pm PDT
Bertrand Serlet August 21, 1987 4:18:49 pm PDT
DIRECTORY
Rope, Convert, DrotBool, DrotCover;
DrotCoverImpl: CEDAR MONITOR
IMPORTS Rope, Convert, DrotBool
EXPORTS DrotCover
~ BEGIN OPEN DrotBool, DrotCover;
Operations on CTrees
RecurseCSimilar: PUBLIC PROC [cv1, cv2: Node] RETURNS [BOOL] ~ {
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
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];
In the last case there are two ways to combine the children of two nands.
};
CopyCTree: PUBLIC PROC [tree: Dag] RETURNS [ct: Dag] ~ {
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.
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];
This assumes that tree is a true true, and that tree.csucs is its root
ct.csucs.outname ← tree.csucs.outname;
ct.csucs.output ← TRUE;
};
CopyCNode: PROC [cv: Node, ct: Dag] RETURNS [cvertex: Node] ~ {
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))
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] ~ {
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 --
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] ~ {
Takes a tree in ctcoll and causes that tree to be the last in linear order in the ctcoll --
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] ~ {
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. --
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] ~ {
Completely removes a tree from the ctcoll --
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] ~ {
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 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
If there is only one 0 (and there is at least one) then there is no need to create a new left side node.
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
If there is only one 1 (and there is at least one) then there is no need to create a new right subnode.
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] ~ {
This creates a new Dag with no children
tree ← NEW[Degree]
};
Generating All Cover Trees
TwoifyAllTrees: PUBLIC PROC [ctcoll: Treeset] ~ {
Given a set of trees with only nands, nots and prims, finds all decompositions where only two-input-nands, nots, and prims are used --
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] ~ {
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)
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] ~ {
This creates a new Dag with no children
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] ~ {
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) --
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;
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.
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]];
This produces a copy of tree, modified according to count at special
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] ~ {
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
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] ~ {
Computes base ** exp. It is naturally more efficient than the version for reals. --
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] ~ {
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)
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] ~ {
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. --
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;
};
Covering a Dag
ProduceTotalCovering: PUBLIC PROC [tree: Dag, ctcoll: Treeset] ~ {
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.
iter: Node;
CoverAndYield[tree, ctcoll]; --This produces the inital covering.
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.
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]
If its used as an internal signal and Matchings needed to be redone
THEN {
ClearScratch[tree]; --start over
iter ← tree.csucs}
ELSE {
IF (iter.type # prim) THEN LabelCoverEndpoints[iter.cover];
else keep going
iter ← iter.next};
ENDLOOP;
};
RedoMatchingOfAncestors: PROC [pariter: Kidptr, iter: Node, ctcoll: Treeset] RETURNS [changed: BOOL ← FALSE] ~ {
If a rematching has to be effected, this will do it and return TRUE, otherwise it will return FALSE
WHILE pariter # NIL DO
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 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] ~ {
If a particular cover has to be redone, this is what redoes it.
changed ← ModifyCoverToRedoCover[vertex.cover.csucs, selectedNode];
IF changed THEN {
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.
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}
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.
};
ModifyCoverToRedoCover: PROC [cnode, selectedTreeNode: Node] RETURNS [changed: BOOL] ~ {
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.
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] ~ {
This should reall by called CoverSubtreeWithCover'sCover
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;
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.
CoverSubtreeWithCoversCover[cnode.mate.cover.csucs]};
ENDCASE;
cnode.mate ← cnode.mate.mate;
};
LabelCoverEndpoints: PROC [cTree: Dag] ~ {
Adds one to the scratch field of all the internal signals/ inputs acting as inputs to theis cover. Watch the use!
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] ~ {
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 --
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] ~ {
This checks to see which vertex covers iter best. It assumes that the vertices below have been covered (in ThisCoverVal) --
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] ~ {
This determines whether withThisTree can offer another cover of toBeCovered and if so, finds it.
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]
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.
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] ~ {
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)
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];
This should never be encountered --
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]
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.
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
There is an obscure error that may happen here if both the children of a nand are identical. This should never happen, of course.
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] ~ {
This computes the size of the cover of ctree.csucs.mate. If ctree.csucs.type = prim then there is a serious problem --
coversize ← ctree.val + RecurseCoverVal[ctree.csucs]
};
RecurseCoverVal: PROC [cv: Node] RETURNS [acc: INT ← 0] ~ {
This computes the size of the covers at each of the inputs to this particular cover.
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.