DIRECTORY
Rope, DrotBool;

DrotBoolTree: CEDAR MONITOR
IMPORTS Rope
EXPORTS DrotBool
~ BEGIN OPEN DrotBool;

PlaceAtEnd: PUBLIC PROC [tree: Dag, vertex: Node] ~ {
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] ~ {
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] ~ {
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;
IF vertex^.type = prim AND nonPrimEncountered THEN PlaceAtEnd[tree, vertex]}
};

OrphansToFront: PUBLIC PROC [tree: Dag] ~ {
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] ~ {
IF after = NIL
THEN PlaceAtEnd[tree, before]
ELSE IF before # after AND (before^.next # after) THEN 
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] ~ {
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] ~ {
IF tree^.csucs # NIL THEN {
PrimitivesToEnd[tree];
ClearScratch[tree];
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;
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];
[] _ PlaceBefore[tree, pariter^.child, front];
front _ pariter^.child};
pariter _ pariter^.next;
ENDLOOP;
rear _ rear^.prev;
ENDLOOP}}
};

OrderNodesByOrphans: PUBLIC PROC [tree: Dag] ~ {
IF tree^.csucs # NIL THEN {
OrphansToFront[tree];
ClearScratch[tree];
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;
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}}
};
RemoveNode: PUBLIC PROC [tree: Dag, vertex: Node] ~ {
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;
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;
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] ~ {
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] ~ {
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] ~ {
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] ~ {
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] ~ {
[] _ KillCLink[plink^.parlink];
RETURN [plink^.next]
};

MakeLink: PUBLIC PROC [par,gyerek: Node] ~ {
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
THEN
temp^.prev _ temp
ELSE {
temp^.prev _ temp^.next^.prev;
temp^.next^.prev _ temp};
temp _ gyerek^.parlist;
IF temp^.next = NIL 
THEN
temp^.prev _ temp
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] ~ {
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] ~ {
temp: Kidptr _ ConnectionBetween[szulo,gyerek];
WHILE temp # NIL DO
[] _ KillCLink[temp];
temp _ ConnectionBetween[szulo,gyerek];
ENDLOOP;
};
EstablishLevels: PUBLIC PROC [tree: Dag] ~ {
ResetLevels[tree];
FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO
IF iter^.parnum = 0 THEN REstablishLevels[iter,1];
ENDLOOP;
};

ResetLevels: PROC [tree: Dag] ~ {
FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO
iter^.level _ 0;
ENDLOOP;
};

REstablishLevels: PROC [iter: Node, levelnum: INT] ~ {
IF iter # NIL AND levelnum > iter^.level THEN {
IF iter^.kidnum = 1
THEN REstablishLevels[iter^.kidlist^.child, levelnum + 1]
ELSE FOR kiditer: Kidptr _ iter^.kidlist, kiditer^.next UNTIL kiditer = NIL DO
REstablishLevels[kiditer^.child, levelnum + CLogarythm[2,iter^.kidnum]];
ENDLOOP;
iter^.level _ levelnum}
};

CLogarythm: PUBLIC PROC [base, num: INT] RETURNS [INT] ~ {
IF num = 1
THEN RETURN[0]
ELSE RETURN[1 + CLogarythm[base, (num + base -1)/base]]
};

ClearScratch: PUBLIC PROC [tree: Dag] ~ {
FOR iter: Node _ tree^.csucs, iter^.next UNTIL iter = NIL DO
iter^.scratch _ 0;
ENDLOOP;
};
NegNodeType: PUBLIC PROC [intype: Vtype] RETURNS [Vtype] ~ {
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] ~ {
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] ~ {
IF listb = NIL THEN RETURN[lista]
ELSE RETURN[MergeListOfRopes[CONS[listb.first, lista], listb.rest]]
};

NotAbove: PUBLIC PROC [pariter: Kidptr] RETURNS [Node] ~ {
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] ~ {
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] ~ {
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] ~ {
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] ~ {
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] ~ {
vertex _ FindInputByName[tree, name];
IF vertex # NIL
THEN RETURN[vertex]
ELSE RETURN[FindExpressionByName[tree, name]]
};
ForwardSimilar: PUBLIC PROC [nodea, nodeb: Node] RETURNS [a: BOOL _ FALSE] ~ {
IF nodea^.kidnum = nodeb^.kidnum
THEN RETURN[KidlistEqual[nodea^.kidlist, nodeb^.kidlist]]
};

KidlistEqual: PROC [kidlista, kidlistb: Kidptr] RETURNS [a: BOOL] ~ {
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] ~ {
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] ~ {
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] ~ {
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] ~ {
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] ~ {
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] ~ {
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};
};

END.

βDrotBoolImpl.mesa
Copyright Σ 1987 by Xerox Corporation.  All rights reserved.
Csaba Gabor August 19, 1987 10:32:35 pm PDT

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.

Takes a vertex in tree and causes that vertex to be the last in linear order in the tree --
This takes vertex in tree and causes it to be the first in linear order in the tree --
This takes all nodes which represent inputs (prims) and places them at the end (in linear order) of the tree.
Now we have to take care of the last node
This takes all nodes which have no parents and places them at the beginning (in linear order) of the tree --
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. --
Think about it.  That first line makes sense after all --
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). --
Arranges tree so that considering linear order, each node's parents are greater than it. --
We use the scratch field for counting the number of children already accessed
We put a placeholder, front, at the head of all the processed nodes
I believe that the above line should go, but I haven't double checked yet.  Should probably be redone to be like OrderNodesByOrphans
Arranges a tree so that if linear order is considered, each node's forward pointers point only to vertices less than it. --
We use the scratch field for counting the number of parents already accessed
We put a placeholder, rear, at the end of all the processed nodes
Creating And Deleting Tree Parts
Completely removes a node from the tree, including any links it has --
The next two statements remove the node from the circular list of the tree.
We want the tree to be numbered from 1 to tree^.size
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. --
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. --
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.
This expects as input some link to a child which it will delete.
This expects as input some link to a parent which link it will delete.
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 --
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.
Given two nodes, this finds the parent (szulo) - child (gyerek) link between them, if it exists, and removes it
Setting Values On All Nodes
This finds the real level of all nodes in a tree.  Gates with large amounts of inputs will cause their children to have correspondingly higher levels.  Ex.  A 4-input and is really at least a 2-input and of two 2-input ands.  Unfortunately, I have not fixed it up yet to ignore nots, but that should not be too difficult.  On the bright side, this level information is not really being used currently, though eventually it should be.
The the levelnumber of each node in the tree to 0
This recursively establishes the level of all nodes in the subtree headed by iter.  levelnum is the level at which this particular node (iter) is starting out.
Computes the ceiling function of log base base of num.  This is a cute function; that's why it is public.  Everyone should be encouraged to use cute functions. --
This sets the scratch field of every node in tree to 0.  Used prior to tree searches for initialization --
Non Modifying Functions
Returns the negative of any Vtype (the type of any node)
Generates a name for the negation of a variable.  This could be removed since it only affects internal names.
Appends one list of ROPES to another.  listb should be shorter, if possible.
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.
Returns the negation of vertex, if it exists, else NIL.  Currently, there is no check for the negations of XORs.
If szulo has gyerek as a child then the link between them is returned, otherwise NIL
Finds a node (if it exists) with the given name (searches the varname and outname fields)
Finds an input (prim) with the given name, if it exists
Finds a node with the given name giving preference to inname, varname, outname in that order.
Tree Modifying Functions
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. --
Assumes kidlista, kidlistb have the same number of elements.  See ForwardSimilar --
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. --
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!
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.
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.
Any nodes which do not contribute to the output are annihilated (with the possible exception of inputs if primsToo is FALSE)
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)
Κ3–

"cedar" style˜š
œ™Icode™<Kš
œ+™+—K™š
Οk	˜	Kš
œ˜—K˜KšΠlnœœ
˜Kšœ˜Kšœ	˜Kšœœ
œ
˜K˜
head™Kš
ΟcΑ™ΑK™šΟn
œœ
œ˜5KšœYŸ™[šœœ
œŸ˜8šœŸ ˜9šœ˜K˜K˜Kšœ˜K˜
—šœ˜K˜!K˜"K˜"K˜!K˜Kšœ˜Kš
œ˜———K˜—K˜š 
œœ
œ˜5KšœTŸ™Všœœ˜šœœŸ˜7šœ˜Kšœ˜K˜
—šœ˜K˜"K˜"K˜!K˜Kš
œ˜——K˜K˜—K˜—K˜š œœ
œ˜,Kš
œm™mšœœ
œœ
œŸ˜DKšœœœ
˜"K˜"šœ˜šœœ˜-šœ˜KšœŸ˜8K˜K˜—šœ˜Kš
œ+˜+Kš
œ˜——Kšœ
˜—Kš
œ)™)Kšœœœ˜L—K˜—K˜š œœ
œ˜+KšœjŸ™lš
œœ
œœ
œ˜*Kšœœœ
˜$K˜šœœ
˜šœœ˜,šœ˜KšœŸ˜6K˜K˜Kš
œ
˜
—šœ˜Kš
œ*˜*K˜——Kšœ˜	——K˜—K˜š œœ
œ"œ
˜KKšœ
œaœLŸ™Εšœ	˜Kšœ˜šœ
œœœ
˜7Kšœ7Ÿ™9šœŸ˜8šœ˜KšœŸ+˜BšœœŸ˜1šœ˜K˜Kšœ˜K˜
—šœ˜K˜"K˜"K˜K˜K˜Kš
œ˜——K˜
—šœ˜šœŸ(˜AKšœ˜Kšœ#˜'—šœœŸ&˜=Kšœ!˜%Kšœ#˜'—K˜K˜K˜K˜Kš
œ˜————Kšœ˜K˜—K˜š 
œœ
œ!œ
˜IKšœ‘
œ@œœŸ™‘šœ
˜Kšœ˜šœ
œœ˜6šœœŸ%˜<šœ˜K˜šœŸ˜7šœ˜K˜Kšœœ
˜—šœ˜K˜ K˜ K˜Kšœœ
˜K˜———šœ˜šœœŸ$˜:Kšœ ˜$Kšœ!˜%—šœŸ%˜=Kšœ˜Kšœ!˜%—K˜K˜K˜K˜————šœ˜Kšœ
œ
œ
˜Kšœ
œ˜—K˜—K˜š œœ
œ˜.KšœYŸ™[šœœ
œ˜K˜K˜Kš
œM™Mšœœ"œ˜IK˜K˜šœ˜K˜Kšœ
˜—Kš
œC™CK˜šœœŸ˜,K˜ šœœ
œŸ˜)K˜6šœ2œ˜:K˜.Kš
œ„
™„
K˜.K˜—K˜Kšœ
˜—K˜Kšœ˜	———K˜—K˜š œœ
œ˜0KšœyŸ™{šœœ
œ˜K˜K˜Kš
œL™Lšœœ!œ˜GK˜K˜šœ˜K˜Kšœ
˜—Kš
œA™Ašœœ
˜K˜!šœœ
˜K˜6šœ1˜3Kšœ0˜4—K˜Kšœ
˜—K˜Kšœ˜	———K˜——š
œ ™ š 
œœ
œ˜5KšœDŸ™FK˜ K˜ šœ	œ
œŸ)˜?K˜Kšœ
˜—šœ	œ
œŸ(˜>K˜Kšœ
˜—Kšœœ
œœ
˜=Kš
œK™Kšœ˜Kšœ!˜%Kšœ#˜'—šœ˜Kšœ˜Kšœ#˜'—Kš
œ4™4šœœ˜%K˜šœ˜"K˜Kšœ
˜—K˜—K˜K˜—K˜š œœ
œ7œœœœœ
œ
œœ
œœœ˜»
KšœPœPœŸ™ͺ
Kšœœu˜šœœ
œŸ˜4K˜K˜—š	œ
œ
œ
œŸ,˜IK˜K˜K˜K˜—šœ˜K˜K˜šœ˜Kšœ˜Kšœ˜—K˜—K˜K˜—K˜š œœ
œ7œœœœœ
œ
œœ
œœœ˜»
KšœQœPœŸ™«
Kšœœu˜šœœ
œŸ˜3K˜K˜—š	œ
œ
œ
œŸ=˜ZK˜K˜K˜—šœ˜K˜K˜šœ˜Kšœ˜Kšœ˜—K˜—K˜K˜—K˜š œœ
œ˜6Kš
œ
™
šœœ
œ˜K˜ZK˜K˜"—K˜—K˜š 	œœ
œœ
˜:Kš
œ@™@KšœŸ˜-Kšœ Ÿ/˜OKšœŸ˜'K˜K˜šœ˜Kšœ ˜$Kšœ˜#—šœ˜Kšœ!˜%Kšœ!˜%—šœ˜Kšœ˜Kšœ˜#—šœ˜Kšœ˜Kšœ!˜%—Kšœ˜K˜—K˜š 	œœ
œœ
˜;Kš
œF™FK˜Kšœ˜K˜—K˜š œœ
œ˜,Kšœ¨
Ÿ™ͺ
K˜
Kšœœ/˜AKšœœF˜[K˜(K˜šœ˜š
˜Kš
œ˜—šœ˜K˜Kš
œ˜——K˜šœœ
˜š
˜K˜—šœ˜K˜Kš
œ˜——K˜K˜#K˜—K˜š 	œœ
œ˜0Kš
œ΄™΄Kšœœ˜.Kšœœ*˜=K˜šœ˜Kšœ˜šœ˜K˜#K˜$——K˜šœ˜Kšœ˜šœ˜K˜$K˜%——K˜K˜"K˜#K˜—K˜š 
œœ
œ˜1Kš
œo™oK˜/šœœ
˜K˜K˜'Kšœ
˜—Kš
œ˜——š
œ™š œœ
œ˜,Kš
œ±™±K˜šœ&œœ
˜<Kšœœ˜2Kšœ
˜—K˜K˜š œœ˜!Kš
œ1™1šœ&œœ
˜<K˜Kšœ
˜—K˜—K˜š œœœ˜6Kš
œŸ
™Ÿ
šœœ
œœ˜/šœ˜Kšœ5˜9š	œ
œ0œœ
˜NK˜HKšœ
˜——K˜—K˜——K˜š 
œœ
œ
œœœ˜:Kšœ 
Ÿ™’
šœ˜
Kšœ
œ˜Kšœ
œ,˜7—K˜—K˜š œœ
œ˜)KšœhŸ™jšœ&œœ
˜<K˜Kšœ
˜—K˜——š
œ™š œœ
œœ˜<Kš
œ8™8šœ˜Kšœœ˜Kšœœ˜Kšœœ˜Kšœœ˜Kšœœ˜Kšœœ˜Kšœœ	Ÿ˜/—K˜—K˜š 
œœ
œœœœ˜:Kš
œm™mšœ˜Kšœ
œ
œ
˜šœ
œ˜Kšœ
œ+˜6Kšœ
œ˜$——K˜—K˜š œœ
œœ
œ
œœœ
œ
œ˜UKš
œL™Lšœ	œ
œ
œ˜!Kšœ
œœ"˜C—K˜—K˜š œœ
œœ˜:Kš
œΞ
™Ξ
šœ˜Kšœ
œ
œ
˜šœ
œ˜"Kšœ
œ˜Kšœ
œ˜$——K˜—K˜š
 
œœ
œœœ˜JKšœ3œ:™pšœ
œ
˜šœœ
œ
œ˜5šœ
œœ
œ˜>Kšœ
œ˜'———K˜—K˜š
 œœ
œœœ˜UKšœQ™Tšœ+œœ
˜AKšœœ
œ˜*Kšœ
˜—K˜—K˜š œœ
œœœœ˜ZKš
œY™Yšœ&œœ
˜<Kšœ œ
œ˜4š
œœ
œ
œ œœ
˜QKšœ!œ
œ˜5Kšœ
˜—Kšœ
˜—K˜—K˜š œœ
œœœœ˜UKš
œ7™7šœ&œœ
˜<Kšœœœ
œ˜IKšœ
˜—K˜—K˜š
 œœ
œœœ˜NKš
œ]™]K˜%šœ
˜Kšœ
œ˜Kšœ
œ"˜-—K˜——š
œ™š œœ
œœœœ˜NKšœϋ
Ÿ™ύ
šœ˜ Kšœ
œ.˜9—K˜K˜Kš œœœœ˜EšœQŸ™SK˜šœ'˜,šœ	˜Kšœ
œ
œ
˜šœ
œ˜#Kšœ
œ
œ
˜Kšœ˜——Kšœ
˜—K˜——K˜š œœ
œ˜5Kšœ“
Ÿ™•
šœ
œ
˜šœ˜šœ˜K˜K˜Kšœ˜K˜
—šœ˜K˜K˜K˜K˜K˜Kšœ˜Kš
œ˜———K˜—K˜š œœ
œœ˜GKšœ¬
œ
œ
œ
™Ί
šœ˜Kšœ
œ˜šœ
œ˜šœ
œœ˜.Kšœ
œ˜#šœ˜K˜$K˜Kšœ˜
——šœ˜Kšœœ
œ
œ˜Jš
œœœ
œœ˜KK˜)Kšœ
˜—K˜2Kšœ˜———K˜—K˜š
 œœ
œœœ	˜MKš
œ ™ šœ+œœ
˜AK˜Kšœ
˜—šœ*œœ
˜@K˜Kšœ
˜—šœ+œœ
˜AK˜#K˜0Kšœ
˜—K˜—K˜š œœ
œ˜;Kš
œΉ
™Ή
K˜K˜#šœ˜šœ˜K˜%K˜Kšœœ
œ
œ˜B—šœ
œ˜šœ˜K˜K˜—šœ
œ˜$šœ˜K˜(K˜—šœ
œœœ˜:šœ˜K˜HK˜K˜—Kšœ#˜'————K˜—K˜š œœ
œœ˜=Kš
œ|™|K˜šœ&œœ
˜<Kšœœ˜+Kšœ
˜—šœ&œœ
˜<Kšœœœœ˜UKšœ
˜—K˜K˜š œœ˜(Kš
œΏ
™Ώ
šœœ˜K˜šœ˜Kšœœ
˜
K˜4š	œœ2œœ
˜VK˜ Kšœ˜	———K˜———K˜Kšœ
˜K˜—…—?DqY