Linear Ordering Of Trees
--Dags have two types of ordering here. The first is the conventional one where each node may have children and parents. However, to make the data structure more manageable the nodes are kept on a circularly linked list and in this sense have a 'linear order.' To visit each node for example one may percolate around the nodes in a depth first search (after finding the sources, of course) or one may just go from one to the next in linear order.
PlaceAtEnd:
PUBLIC
PROC [tree: Dag, vertex: Node] ~ {
Takes a vertex in tree and causes that vertex to be the last in linear order in the tree --
IF vertex^.next #
NIL
THEN
--No action in an empty tree
IF tree^.csucs = vertex
--If vertex is the first element
THEN {
vertex^.prev^.next ← vertex;
tree^.csucs ← vertex^.next;
vertex^.next ← NIL
}
ELSE {
tree^.csucs^.prev^.next ← vertex;
vertex^.next^.prev ← vertex^.prev;
vertex^.prev^.next ← vertex^.next;
vertex^.prev ← tree^.csucs^.prev;
tree^.csucs^.prev ← vertex;
vertex^.next ← NIL
};
};
PlaceAtBeg:
PUBLIC
PROC [tree: Dag, vertex: Node] ~ {
This takes vertex in tree and causes it to be the first in linear order in the tree --
IF vertex # tree^.csucs
THEN {
IF vertex^.next =
NIL
--If vertex is the last element
THEN {
vertex^.prev^.next ← NIL
}
ELSE {
vertex^.prev^.next ← vertex^.next;
vertex^.next^.prev ← vertex^.prev;
vertex^.prev ← tree^.csucs^.prev;
tree^.csucs^.prev ← vertex
};
vertex^.next ← tree^.csucs;
tree^.csucs ← vertex}
};
PrimitivesToEnd:
PUBLIC
PROC [tree: Dag] ~ {
This takes all nodes which represent inputs (prims) and places them at the end (in linear order) of the tree.
IF tree #
NIL
AND tree^.csucs #
NIL
THEN {
--If the tree is not NIL
nonPrimEncountered : BOOL ← FALSE;
vertex : Node ← tree^.csucs^.prev;
WHILE vertex # tree^.csucs
DO
IF vertex^.type = prim
AND nonPrimEncountered
THEN {
temp: Node ← vertex^.prev; --So we don't lose our place
PlaceAtEnd[tree, vertex];
vertex ← temp}
ELSE {
nonPrimEncountered ← (vertex^.type # prim);
vertex ← vertex^.prev}
ENDLOOP;
Now we have to take care of the last node
IF vertex^.type = prim AND nonPrimEncountered THEN PlaceAtEnd[tree, vertex]}
};
OrphansToFront:
PUBLIC
PROC [tree: Dag] ~ {
This takes all nodes which have no parents and places them at the beginning (in linear order) of the tree --
IF tree #
NIL
AND tree^.csucs #
NIL
THEN {
nonOrphanEncountered : BOOL ← FALSE;
iter: Node ← tree^.csucs;
WHILE iter #
NIL
DO
IF iter^.parnum = 0
AND nonOrphanEncountered
THEN {
temp: Node ← iter^.next; --So we don't lose our place
PlaceAtBeg[tree, iter];
iter ← temp
}
ELSE {
nonOrphanEncountered ← (iter^.parnum > 0);
iter ← iter^.next}
ENDLOOP};
};
PlaceBefore:
PUBLIC
PROC [tree: Dag, before, after: Node]
RETURNS[Node] ~ {
after stays fixed here. This procedure takes before and after in tree and causes before to be placed before after in linear order. If after = NIL then PlaceAtEnd[tree, before] is invoked. It really is consistent. This will fail if before = NIL. Returns before^.next. Thus, unless before = after it will return after. --
IF after =
NIL
THEN PlaceAtEnd[tree, before]
ELSE
IF before # after
AND (before^.next # after)
THEN
Think about it. That first line makes sense after all --
IF after = tree^.csucs
--if after is first in the tree
THEN {
tree^.csucs ← before; --then before becomes the new first element
IF before^.next =
NIL
--if before was at the end
THEN {
before^.next ← after;
before^.prev^.next ← NIL
}
ELSE {
before^.prev^.next ← before^.next;
before^.next^.prev ← before^.prev;
before^.prev ← after^.prev;
before^.next ← after;
after^.prev ← before
};
}
ELSE {
IF before = tree^.csucs
--if before was at the front of the tree
THEN tree^.csucs ← before^.next
ELSE before^.prev^.next ← before^.next;
IF before^.next =
NIL
--if before was at the end of the tree
THEN tree^.csucs^.prev ← before^.prev
ELSE before^.next^.prev ← before^.prev;
before^.next ← after;
before^.prev ← after^.prev;
after^.prev^.next ← before;
after^.prev ← before
};
RETURN[before^.next]
};
PlaceAfter:
PUBLIC
PROC[tree: Dag, before, after: Node]
RETURNS[Node] ~ {
before stays fixed here. This procedure takes before and after in tree and causes after to be placed after before in linear order. If before = NIL then PlaceAtBeg[tree, after] is invoked. Will fail if after = NIL. Returns after^.prev (or NIL if after = tree^.csucs). --
IF before =
NIL
THEN PlaceAtBeg[tree, after]
ELSE
IF before # after
AND (before^.next # after)
THEN
IF before^.next =
NIL
--If before is at the end of the tree
THEN {
before^.next ← after;
IF after = tree^.csucs
--If after is first in the tree
THEN {
tree^.csucs ← after^.next;
after^.next ← NIL}
ELSE {
after^.prev^.next ← after^.next;
after^.next^.prev ← after^.prev;
tree^.csucs^.prev ← after;
after^.next ← NIL;
after^.prev ← before}}
ELSE {
IF after^.next =
NIL
--If after is at the end of the tree
THEN tree^.csucs^.prev ← after^.prev
ELSE after^.next^.prev ← after^.prev;
IF after = tree^.csucs
--If after is at the head of the tree
THEN tree^.csucs ← after^.next
ELSE after^.prev^.next ← after^.next;
after^.prev ← before;
after^.next ← before^.next;
before^.next^.prev ← after;
before^.next ← after};
IF after = tree^.csucs
THEN RETURN[NIL]
ELSE RETURN[after^.prev];
};
OrderNodesByPrims:
PUBLIC
PROC [tree: Dag] ~ {
Arranges tree so that considering linear order, each node's parents are greater than it. --
IF tree^.csucs #
NIL
THEN {
PrimitivesToEnd[tree];
ClearScratch[tree];
We use the scratch field for counting the number of children already accessed
IF (tree^.csucs^.type # prim)
AND (tree^.csucs^.prev^.type = prim)
THEN {
rear: Node ← tree^.csucs^.prev;
front: Node ← rear;
WHILE front^.type = prim
DO
front ← front^.prev;
ENDLOOP;
We put a placeholder, front, at the head of all the processed nodes
front ← front^.next;
WHILE front # tree^.csucs
DO
--Main routine
pariter: Kidptr ← rear^.parlist;
WHILE pariter #
NIL
DO
--For each parent
pariter^.child^.scratch ← pariter^.child^.scratch + 1;
IF pariter^.child^.scratch = pariter^.child^.kidnum
THEN {
KidptrToEnd[pariter^.parlink, pariter^.child];
I believe that the above line should go, but I haven't double checked yet. Should probably be redone to be like OrderNodesByOrphans
[] ← PlaceBefore[tree, pariter^.child, front];
front ← pariter^.child};
pariter ← pariter^.next;
ENDLOOP;
rear ← rear^.prev;
ENDLOOP}}
};
OrderNodesByOrphans:
PUBLIC
PROC [tree: Dag] ~ {
Arranges a tree so that if linear order is considered, each node's forward pointers point only to vertices less than it. --
IF tree^.csucs #
NIL
THEN {
OrphansToFront[tree];
ClearScratch[tree];
We use the scratch field for counting the number of parents already accessed
IF (tree^.csucs^.parnum = 0)
AND (tree^.csucs^.prev^.parnum # 0)
THEN {
front: Node ← tree^.csucs;
rear: Node ← front;
WHILE rear^.parnum = 0
DO
rear ← rear^.next;
ENDLOOP;
We put a placeholder, rear, at the end of all the processed nodes
WHILE rear #
NIL
DO
kiditer: Kidptr ← front^.kidlist;
WHILE kiditer #
NIL
DO
kiditer^.child^.scratch ← kiditer^.child^.scratch + 1;
IF kiditer^.child^.scratch = kiditer^.child^.parnum
THEN rear ← PlaceBefore[tree, kiditer^.child, rear];
kiditer ← kiditer^.next;
ENDLOOP;
front ← front^.next;
ENDLOOP}}
};
Creating And Deleting Tree Parts
RemoveNode:
PUBLIC
PROC [tree: Dag, vertex: Node] ~ {
Completely removes a node from the tree, including any links it has --
kiter: Kidptr ← vertex^.kidlist;
piter: Kidptr ← vertex^.parlist;
WHILE kiter #
NIL
DO
--Gets rid of the links with the Children
kiter ← KillCLink[kiter];
ENDLOOP;
WHILE piter #
NIL
DO
--Gets rid of the links with the Parents
piter ← KillPLink[piter];
ENDLOOP;
IF vertex^.brother # NIL THEN vertex^.brother^.brother ← NIL;
The next two statements remove the node from the circular list of the tree.
IF vertex^.next =
NIL
THEN tree^.csucs^.prev ← vertex^.prev
ELSE vertex^.next^.prev ← vertex^.prev;
IF vertex = tree^.csucs
THEN tree^.csucs ← vertex^.next
ELSE vertex^.prev^.next ← vertex^.next;
We want the tree to be numbered from 1 to tree^.size
IF vertex^.number < tree^.size
THEN {
iter: Node ← tree^.csucs;
WHILE iter^.number # tree^.size
DO
iter ← iter^.next
ENDLOOP;
iter^.number ← vertex^.number};
tree^.size ← tree^.size - 1
};
MakeNewNodeA:
PUBLIC
PROC [tree: Dag, vertex: Node, type: Vtype ← prim, inname:
ROPE ←
NIL, varname:
ROPE ←
NIL, outname:
LIST
OF
ROPE ←
NIL, output:
BOOL ←
FALSE]
RETURNS[temp: Node] ~ {
This creates a new node placing it after vertex in linear order unless vertex = NIL in which case the created node becomes the head of the tree. tree must not be NIL. --
temp ← NEW[Noderec ← [type: type, inname: inname, varname: varname, outname: outname, output: output, number: tree^.size + 1]];
IF tree^.csucs =
NIL
THEN {
--If the tree was empty
temp^.prev ← temp;
tree^.csucs ← temp}
ELSE
IF vertex =
NIL
THEN {
--If the new node is to be first in the tree
temp^.prev ← tree^.csucs^.prev;
temp^.next ← tree^.csucs;
temp^.next^.prev ← temp;
tree^.csucs ← temp}
ELSE {
temp^.prev ← vertex;
temp^.next ← vertex^.next;
IF vertex^.next =
NIL
THEN tree^.csucs^.prev ← temp
ELSE vertex^.next^.prev ← temp;
vertex^.next ← temp};
tree^.size ← tree^.size + 1
};
MakeNewNodeB:
PUBLIC
PROC [tree: Dag, vertex: Node, type: Vtype ← prim, inname:
ROPE ←
NIL, varname:
ROPE ←
NIL, outname:
LIST
OF
ROPE ←
NIL, output:
BOOL ←
FALSE]
RETURNS[temp: Node] ~ {
This creates a new node placing it before vertex in linear order unless vertex = NIL in which case the created node becomes the tail of the tree. tree must not be NIL. --
temp ← NEW[Noderec ← [type: type, inname: inname, varname: varname, outname: outname, output: output, number: tree^.size + 1]];
IF tree^.csucs =
NIL
THEN {
--If the tree is empty
temp^.prev ← temp;
tree^.csucs ← temp}
ELSE
IF vertex =
NIL
THEN {
--If the new node is to be last in the tree (in linear order)
temp^.prev ← tree^.csucs^.prev;
tree^.csucs^.prev ← temp;
temp^.prev^.next ← temp}
ELSE {
temp^.next ← vertex;
temp^.prev ← vertex^.prev;
IF vertex = tree^.csucs
THEN tree^.csucs ← temp
ELSE vertex^.prev^.next ← temp;
vertex^.prev ← temp};
tree^.size ← tree^.size + 1
};
MakeBrother:
PUBLIC
PROC [tree: Dag, vertex: Node] ~ {
Finds the negation of a node and creates it if it does not exist, in either case linking the two through the brother field. Currently not used.
IF vertex^.brother =
NIL
THEN {
[] ← MakeNewNodeA[tree, vertex, NegNodeType[vertex^.type], NegateVarName[vertex^.inname]];
vertex^.brother ← vertex^.next;
vertex^.brother^.brother ← vertex}
};
KillCLink:
PUBLIC
PROC [link: Kidptr]
RETURNS [Kidptr] ~ {
This expects as input some link to a child which it will delete.
kid: Node ← link^.child; --This is the child
plink: Kidptr ← link^.parlink; --This is the link from the child to the parent
par: Node ← plink^.child; --The parent
par^.kidnum ← par^.kidnum - 1;
kid^.parnum ← kid^.parnum - 1;
IF link^.next =
NIL
THEN par^.kidlist^.prev ← link^.prev
ELSE link^.next^.prev ← link^.prev;
IF plink^.next =
NIL
THEN kid^.parlist^.prev ← plink^.prev
ELSE plink^.next^.prev ← plink^.prev;
IF link = par^.kidlist
THEN par^.kidlist ← link^.next
ELSE link^.prev^.next ← link^.next;
IF plink = kid^.parlist
THEN kid^.parlist ← plink^.next
ELSE plink^.prev^.next ← plink^.next;
RETURN[link^.next]
};
KillPLink:
PUBLIC
PROC [plink: Kidptr]
RETURNS [Kidptr] ~ {
This expects as input some link to a parent which link it will delete.
[] ← KillCLink[plink^.parlink];
RETURN [plink^.next]
};
MakeLink:
PUBLIC
PROC [par,gyerek: Node] ~ {
Makes a link from par (parent) to gyerek (child) (and the reciprocal link from gyerek to parent) in the tree containing them. Both links will be first in linear order --
temp: Kidptr;
par^.kidlist ← NEW[Kidrec ← [child: gyerek, next: par^.kidlist]];
gyerek^.parlist ← NEW[Kidrec ← [child: par, next: gyerek^.parlist, parlink: par^.kidlist]];
par^.kidlist^.parlink ← gyerek^.parlist;
temp ← par^.kidlist;
IF temp^.next =
NIL
ELSE {
temp^.prev ← temp^.next^.prev;
temp^.next^.prev ← temp};
temp ← gyerek^.parlist;
IF temp^.next =
NIL
ELSE {
temp^.prev ← temp^.next^.prev;
temp^.next^.prev ← temp};
par^.kidnum ← par^.kidnum + 1;
gyerek^.parnum ← gyerek^.parnum + 1
};
MakeLinkE:
PUBLIC
PROC [szulo, gyerek: Node] ~ {
This places the newly created link between szulo and gyerek at the end of their respective lists. Unfortunately, this is used in a few places where we are iterating through a list of links, creating some as we go along and then having to process the newly created links. See, for example, ProcessGndAndVdd.
tempk: Kidptr ← NEW[Kidrec ← [child: gyerek]];
tempp: Kidptr ← NEW[Kidrec ← [child: szulo, parlink: tempk]];
tempk^.parlink ← tempp;
IF szulo^.kidlist =
NIL
THEN szulo^.kidlist ← tempk
ELSE {
szulo^.kidlist^.prev^.next ← tempk;
tempk^.prev ← szulo^.kidlist^.prev};
szulo^.kidlist^.prev ← tempk;
IF gyerek^.parlist =
NIL
THEN gyerek^.parlist ← tempp
ELSE {
gyerek^.parlist^.prev^.next ← tempp;
tempp^.prev ← gyerek^.parlist^.prev};
gyerek^.parlist^.prev ← tempp;
szulo^.kidnum ← szulo^.kidnum + 1;
gyerek^.parnum ← gyerek^.parnum + 1
};
RemoveLink:
PUBLIC
PROC [szulo, gyerek: Node] ~ {
Given two nodes, this finds the parent (szulo) - child (gyerek) link between them, if it exists, and removes it
temp: Kidptr ← ConnectionBetween[szulo,gyerek];
WHILE temp #
NIL
DO
[] ← KillCLink[temp];
temp ← ConnectionBetween[szulo,gyerek];
ENDLOOP;
};
Non Modifying Functions
NegNodeType:
PUBLIC
PROC [intype: Vtype]
RETURNS [Vtype] ~ {
Returns the negative of any Vtype (the type of any node)
SELECT intype
FROM
nand => RETURN[and];
and => RETURN[nand];
or => RETURN[nor];
nor => RETURN[or];
not => RETURN[buf];
buf => RETURN[not];
ENDCASE => RETURN[prim]; --Prims are not gates
};
NegateVarName:
PUBLIC
PROC [name:
ROPE]
RETURNS [
ROPE] ~ {
Generates a name for the negation of a variable. This could be removed since it only affects internal names.
IF Rope.IsEmpty[name]
THEN RETURN[NIL]
ELSE
IF Rope.Fetch[name,0] = '~
THEN RETURN[Rope.Substr[name,1,Rope.Length[name] - 1]]
ELSE RETURN[Rope.Concat["~", name]];
};
MergeListOfRopes:
PUBLIC
PROC [lista, listb:
LIST
OF
ROPE]
RETURNS [
LIST
OF
ROPE] ~ {
Appends one list of ROPES to another. listb should be shorter, if possible.
IF listb =
NIL
THEN
RETURN[lista]
ELSE RETURN[MergeListOfRopes[CONS[listb.first, lista], listb.rest]]
};
NotAbove:
PUBLIC
PROC [pariter: Kidptr]
RETURNS [Node] ~ {
Given the parlist of a vertex this determines whether at least one of its parents is of type not. For practical purposes (fanout) it should eventually find that not parent with the least number of parents.
IF pariter =
NIL
THEN RETURN[NIL]
ELSE
IF pariter^.child^.type = not
THEN RETURN[pariter^.child]
ELSE RETURN[NotAbove[pariter^.next]]
};
NegativeOf:
PUBLIC
PROC [vertex: Node]
RETURNS [negVertex: Node ←
NIL] ~ {
Returns the negation of vertex, if it exists, else NIL. Currently, there is no check for the negations of XORs.
IF vertex #
NIL
THEN
IF vertex^.brother #
NIL
THEN
RETURN[vertex^.brother]
ELSE
IF vertex^.type = not
THEN
RETURN[vertex^.kidlist^.child]
ELSE RETURN[NotAbove[vertex^.parlist]];
};
ConnectionBetween:
PUBLIC
PROC [szulo, gyerek: Node]
RETURNS [link: Kidptr ←
NIL] ~ {
If szulo has gyerek as a child then the link between them is returned, otherwise NIL
FOR iter: Kidptr ← szulo^.kidlist, iter^.next
UNTIL iter =
NIL
DO
IF iter^.child = gyerek THEN RETURN[iter];
ENDLOOP;
};
FindExpressionByName:
PUBLIC
PROC [tree: Dag, name:
ROPE]
RETURNS [vertex: Node ←
NIL] ~ {
Finds a node (if it exists) with the given name (searches the varname and outname fields)
FOR iter: Node ← tree^.csucs, iter^.next
UNTIL iter =
NIL
DO
IF Rope.Equal[iter^.varname,name] THEN RETURN[iter];
FOR nameiter:
LIST
OF
ROPE ← iter^.outname, nameiter.rest
UNTIL nameiter =
NIL
DO
IF Rope.Equal[nameiter.first,name] THEN RETURN[iter];
ENDLOOP;
ENDLOOP;
};
FindInputByName:
PUBLIC
PROC [tree: Dag, name:
ROPE]
RETURNS [vertex: Node ←
NIL] ~ {
Finds an input (prim) with the given name, if it exists
FOR iter: Node ← tree^.csucs, iter^.next
UNTIL iter =
NIL
DO
IF iter^.type = prim AND Rope.Equal[iter^.inname,name] THEN RETURN[iter];
ENDLOOP;
};
FindNodeByName:
PUBLIC
PROC [tree: Dag, name:
ROPE]
RETURNS [vertex: Node] ~ {
Finds a node with the given name giving preference to inname, varname, outname in that order.
vertex ← FindInputByName[tree, name];
IF vertex #
NIL
THEN RETURN[vertex]
ELSE RETURN[FindExpressionByName[tree, name]]
};
Tree Modifying Functions
ForwardSimilar:
PUBLIC
PROC [nodea, nodeb: Node]
RETURNS [a:
BOOL ←
FALSE] ~ {
Compares whether the children of two nodes (inputs) are the same. Assumes order on the links. See RemoveDuplicateNodes. I think this code is archaic. It should be scrapped and IntersectionSize should be used in RemoveDuplicateNodes and elsewhere. --
IF nodea^.kidnum = nodeb^.kidnum
THEN RETURN[KidlistEqual[nodea^.kidlist, nodeb^.kidlist]]
};
KidlistEqual: PROC [kidlista, kidlistb: Kidptr] RETURNS [a: BOOL] ~ {
Assumes kidlista, kidlistb have the same number of elements. See ForwardSimilar --
iterb: Kidptr ← kidlistb;
FOR itera: Kidptr ← kidlista, itera^.next
DO
IF itera =
NIL
THEN RETURN[TRUE]
ELSE
IF itera^.child # iterb^.child
THEN RETURN[FALSE]
ELSE iterb ← iterb^.next
ENDLOOP;
};
KidptrToEnd:
PUBLIC
PROC [kid: Kidptr, par: Node] ~ {
This places the specified link to the end of par's kidlist. kid must be in the kidlist of par. I'm unsure whether this is needed or even useful. --
IF kid^.next #
NIL
THEN
IF par^.kidlist = kid
THEN {
kid^.prev^.next ← kid;
par^.kidlist ← kid^.next;
kid^.next ← NIL
}
ELSE {
par^.kidlist^.prev^.next ← kid;
kid^.next^.prev ← kid^.prev;
kid^.prev^.next ← kid^.next;
kid^.prev ← par^.kidlist^.prev;
par^.kidlist^.prev ← kid;
kid^.next ← NIL
};
};
Negate:
PUBLIC
PROC [tree: Dag, vertex: Node]
RETURNS [csucs: Node] ~ {
Given vertex in tree, this finds that node's complement, creating it if necessary. If the node has no parents then it will change the type of vertex appropriately. Thus, USE WITH CARE!
IF vertex^.brother #
NIL
THEN RETURN[vertex^.brother]
ELSE
IF vertex^.type = not
THEN
IF (vertex^.parnum > 0)
OR vertex^.output
THEN RETURN[vertex^.kidlist^.child]
ELSE {
temp: Node ← vertex^.kidlist^.child;
RemoveNode[tree, vertex];
RETURN[temp]}
ELSE {
IF NotAbove[vertex^.parlist] # NIL THEN RETURN[NotAbove[vertex^.parlist]];
IF vertex^.type # prim
AND vertex^.parnum = 0
AND
NOT vertex^.output
THEN {
vertex^.type ← NegNodeType[vertex^.type];
RETURN[vertex]};
MakeLink[MakeNewNodeB[tree, vertex, not], vertex];
RETURN[vertex^.prev]}
};
IntersectionSize:
PUBLIC
PROC [nagy, kicsi: Node]
RETURNS [size:
INT ← 0] ~ {
This determines the size of the intersection of the children of nagy and kicsi. Those nodes (their scratch fields) in the intersection are marked with 2, the children of only one with a 1, and the scratch fields of the rest may be anything. This has made many other procedures obsolete.
FOR iter: Kidptr ← kicsi^.kidlist, iter^.next
UNTIL iter =
NIL
DO
iter^.child^.scratch ← 0;
ENDLOOP;
FOR iter: Kidptr ← nagy^.kidlist, iter^.next
UNTIL iter =
NIL
DO
iter^.child^.scratch ← 1;
ENDLOOP;
FOR iter: Kidptr ← kicsi^.kidlist, iter^.next
UNTIL iter =
NIL
DO
size ← size + iter^.child^.scratch;
iter^.child^.scratch ← iter^.child^.scratch + 1;
ENDLOOP;
};
NegateConnection:
PUBLIC
PROC [tree: Dag, link: Kidptr] ~ {
This takes a link from some parent to a child and changes that link (and its reciprocal link) to point from the parent to the negation of the child, creating that negation if necessary.
ide: Node ← link^.child;
innen: Node ← link^.parlink^.child;
IF ide^.type = not
THEN {
MakeLink[innen, ide^.kidlist^.child];
[] ← KillCLink[link];
IF ide^.parnum = 0 AND NOT ide^.output THEN RemoveNode[tree, ide]}
ELSE
IF ide^.brother #
NIL
THEN {
MakeLink[innen, ide^.brother];
[] ← KillCLink [link]}
ELSE
IF NotAbove[ide^.parlist] #
NIL
THEN {
MakeLink[innen, NotAbove[ide^.parlist]];
[] ← KillCLink [link]}
ELSE
IF ide^.parnum > 1
OR ide^.type = prim
OR ide^.output
THEN {
MakeLink[MakeNewNodeB[tree, ide, not, NegateVarName[ide^.inname]], ide];
MakeLink[innen, ide^.prev];
[] ← KillCLink[link]}
ELSE ide^.type ← NegNodeType[ide^.type]
};
KillHangingNodes:
PUBLIC
PROC [tree: Dag, primsToo:
BOOL] ~ {
Any nodes which do not contribute to the output are annihilated (with the possible exception of inputs if primsToo is FALSE)
ClearScratch[tree];
FOR iter: Node ← tree^.csucs, iter^.next
UNTIL iter =
NIL
DO
IF iter^.output THEN MarkThisSubtree[iter];
ENDLOOP;
FOR iter: Node ← tree^.csucs, iter^.next
UNTIL iter =
NIL
DO
IF (primsToo OR iter^.type # prim) AND iter^.scratch # 1 THEN RemoveNode[tree, iter];
ENDLOOP;
};
MarkThisSubtree:
PROC [vertex: Node] ~ {
This puts a 1 on each scratch field of the subtree headed by vertex (since this is only used by KillHangingNodes, the recursive process terminates if a 1 is encountered on some scratch field)
IF vertex^.scratch # 1
THEN {
vertex^.scratch ← 1;
SELECT vertex^.type
FROM
prim => NULL;
not, buf => MarkThisSubtree[vertex^.kidlist^.child];
ENDCASE =>
FOR kiditer: Kidptr ← vertex^.kidlist, kiditer^.next
UNTIL kiditer =
NIL
DO
MarkThisSubtree[kiditer^.child];
ENDLOOP};
};