DIRECTORY
Basics USING [CompareInt, Comparison],
CD USING [Instance, InstanceList, InterestRect, Number, Object, Rect],
CDBasics,
CDInstances USING [InstRectO],
CDProperties USING [GetProp, GetInstanceProp, PutInstanceProp, PutObjectProp],
FS USING [StreamOpen],
ImagerTransformation USING [Transformation],
IO USING [atom, Close, int, PutF, PutFR, PutRope, real, refAny, rope, STREAM, time],
Properties USING [GetProp, PropList, PutProp],
Real USING [Fix],
RedBlackTree USING [Compare, Create, DestroyTable, DuplicateKey, GetKey, Insert, LookupLargest, LookupNextSmaller, Table],
RefTab USING [Fetch, Key, Pairs, Ref, Store, Val],
Rope USING [Cat, Compare, Fetch, Length, ROPE],
SX USING [AreaPerimRec, Circuit, CircuitNode, FindRootNode, MergeRecList, NodeLinkage, NormalizeCircuit],
SXAccess USING [design],
SXAccessInternal USING [GetLogicalCell],
SXOutput USING [outputGeometricInfo, shortestNamesOnly],
SXOutputPrivate USING [actualCellInstanceName, actualSignalName, Circuit, CircuitNode, isPort, LogicalCell, MergeRec, MergeRecList, Naming, NodeLinkage, ROPE, ROPEList],
UserCredentials USING [Get];
SXOutputImplB: CEDAR PROGRAM
IMPORTS Basics, CD, CDBasics, CDInstances, CDProperties, FS, IO, Properties, Real, RedBlackTree, RefTab, Rope, SX, SXAccess, SXAccessInternal, SXOutput, SXOutputPrivate, UserCredentials
EXPORTS SXOutputPrivate = BEGIN
OPEN SXOutputPrivate;
tiptoe: BOOL _ FALSE;
ValidMerge: PUBLIC PROC [merge: MergeRec] RETURNS [valid: BOOL] = {
valid _ merge.applChain.rest = NIL;
};
GetANaming: PUBLIC PROC [thing: REF ANY, insistValid: BOOL _ TRUE] RETURNS [naming: Naming] = {
WITH thing SELECT FROM
node: REF CircuitNode => {
naming _ NARROW[node.properties.GetProp[ actualSignalName]];
};
appl: CD.Instance => {
naming _ NARROW[CDProperties.GetInstanceProp[from: appl, prop: actualCellInstanceName]];
};
ENDCASE => ERROR;
IF insistValid THEN WHILE naming # NIL AND NOT Valid[naming] DO naming _ naming.next ENDLOOP;
};
Valid: PUBLIC PROC [naming: Naming] RETURNS [valid: BOOL] = {
valid _ naming.named # NIL;
};
GetAName: PUBLIC PROC [thing: REF ANY] RETURNS [name: ROPE] = {
naming: Naming _ GetANaming[thing];
name _ IF naming # NIL THEN NamingName[naming] ELSE NIL;
};
NamingName: PUBLIC PROC [naming: Naming] RETURNS [name: ROPE] = {
name _ naming.name};
HasAskedName: PUBLIC PROC [thing: REF ANY] RETURNS [asked: BOOL] = {
FOR naming: Naming _ GetANaming[thing], naming.next WHILE naming # NIL DO
IF Valid[naming] AND NamingAsked[naming] THEN RETURN [TRUE];
ENDLOOP;
asked _ FALSE;
};
NamingAsked: PUBLIC PROC [naming: Naming] RETURNS [asked: BOOL] = {
asked _ naming.explicit;
};
EnumerateNames: PUBLIC PROC [thing: REF ANY, PerName: PROC [name: ROPE, valid: BOOL], onlyValid: BOOL _ TRUE] = {
FOR naming: Naming _ GetANaming[thing, FALSE], naming.next WHILE naming # NIL DO
valid: BOOL _ Valid[naming];
IF valid OR NOT onlyValid THEN PerName[NamingName[naming], valid];
ENDLOOP;
};
ReverseNamings: PUBLIC PROC [oldFirst: Naming] RETURNS [newFirst: Naming] = {
prev: Naming _ oldFirst;
cur: Naming _ prev.next;
prev.next _ NIL;
WHILE cur # NIL DO
next: Naming _ cur.next;
cur.next _ prev;
prev _ cur;
cur _ next;
ENDLOOP;
newFirst _ prev;
};
SKey: TYPE = REF Rope.ROPE;	-- RedBlackTree.Key
SRec: TYPE = RECORD [key: SKey, naming: Naming];
SData: TYPE = REF SRec;	-- RedBlackTree.UserData
WorstClass: CARDINAL = 8;
classes: ARRAY [0 .. WorstClass] OF RedBlackTree.Table;
NamKey: RedBlackTree.GetKey =
BEGIN
RETURN [NARROW [data, SData].key]
END;	-- NamKey
NamComp: RedBlackTree.Compare = 
BEGIN
c: Basics.Comparison;
sk: SKey = NARROW [k];	-- name
d: SData = NARROW [data];	-- naming
c _ Rope.Compare [sk^, d.key^];
IF c = equal THEN BEGIN
n1i: INT _ LOOPHOLE [sk^];
n2i: INT _ LOOPHOLE [d.key^];
c _ Basics.CompareInt [n1i, n2i];
END; 
RETURN [c]
END;	-- NamComp
Start: PROCEDURE =
BEGIN
FOR c: CARDINAL IN [0 .. WorstClass] DO
classes[c] _ RedBlackTree.Create [getKey: NamKey, compare: NamComp]
ENDLOOP
END;	-- Start
SInsert: PROCEDURE [s: RedBlackTree.Table, nam: Naming] RETURNS [duplicate: BOOL] =
BEGIN
ENABLE RedBlackTree.DuplicateKey => GOTO dupl;
sk: SKey _ NEW [Rope.ROPE _ nam.name];
data: SData _ NEW [SRec _ [key: sk, naming: nam]];
RedBlackTree.Insert [s, data, sk];
RETURN [FALSE];
EXITS
dupl => RETURN [TRUE]
END;	-- SInsert
SortNamings: PUBLIC PROC [oldFirst: Naming] RETURNS [newFirst: Naming] = {
IF oldFirst.next = NIL THEN RETURN [oldFirst];
FOR oldFirst _ oldFirst, newFirst WHILE oldFirst # NIL DO
class: CARDINAL _ 0;
seeingGen: BOOL _ FALSE;
lastWasGen, lastWasDash, lastWasAlpha, nextLastWasAlpha: BOOL _ FALSE;
newFirst _ oldFirst.next;
oldFirst.next _ NIL;
FOR i: INT IN [0 .. oldFirst.name.Length[]) DO
c: CHAR _ oldFirst.name.Fetch[i];
SELECT c FROM
'., '- => IF seeingGen THEN class _ class + 1;
ENDCASE;
SELECT c FROM
'. => {class _ class + 1; seeingGen _ FALSE};
IN ['0 .. '9] => {
IF lastWasDash THEN {class _ class + 1; IF seeingGen THEN ERROR};
IF lastWasGen AND NOT nextLastWasAlpha THEN seeingGen _ TRUE;
};
ENDCASE => seeingGen _ FALSE;
nextLastWasAlpha _ lastWasAlpha;
SELECT c FROM
'., '-  => lastWasAlpha _ FALSE;
ENDCASE => lastWasAlpha _ TRUE;
SELECT c FROM
'n, 'C, 'Q => {lastWasGen _ TRUE; lastWasDash _ FALSE};
'- => {lastWasGen _ FALSE; lastWasDash _ TRUE};
ENDCASE => lastWasGen _ lastWasDash _ FALSE;
ENDLOOP;
IF seeingGen THEN class _ class + 1;
[] _ SInsert [s: classes[MIN[WorstClass, class]], nam: oldFirst]
ENDLOOP;
IF newFirst # NIL THEN ERROR;
IF SXOutput.shortestNamesOnly THEN {
FOR c: CARDINAL IN [0 .. WorstClass] DO
sNaming: SData _ NARROW [RedBlackTree.LookupLargest[classes[c]]];
foundValid: BOOL _ FALSE;
WHILE (sNaming # NIL) AND (sNaming.naming # NIL) DO
foundValid _ foundValid OR Valid[sNaming.naming];
sNaming.naming.next _ newFirst;
newFirst _ sNaming.naming;
sNaming _ NARROW [RedBlackTree.LookupNextSmaller[classes[c], sNaming.key]];
ENDLOOP;
RedBlackTree.DestroyTable [self: classes[c]];
IF foundValid THEN {
FOR d: CARDINAL IN (c .. WorstClass] DO
RedBlackTree.DestroyTable [self: classes[d]]
ENDLOOP;
EXIT;
}
ENDLOOP;
}
ELSE {
FOR c: CARDINAL DECREASING IN [0 .. WorstClass] DO
sNaming: SData _ NARROW [RedBlackTree.LookupLargest[classes[c]]];
WHILE (sNaming # NIL) AND (sNaming.naming # NIL) DO
sNaming.naming.next _ newFirst;
newFirst _ sNaming.naming;
sNaming _ NARROW [RedBlackTree.LookupNextSmaller[classes[c], sNaming.key]];
ENDLOOP;
RedBlackTree.DestroyTable [self: classes[c]]
ENDLOOP;
};
IF newFirst = NIL THEN ERROR;
};
PrintNaming: PUBLIC PROC [to: IO.STREAM, naming: Naming, insert: ROPE _ NIL] = {
nth: CARDINAL _ 0;
FOR naming _ naming, naming.next WHILE naming # NIL DO
IF Valid[naming] THEN {
SELECT nth FROM
=0 => NULL;
=1 => to.PutRope[" (A ("];
>1 => to.PutRope[" ("];
ENDCASE => ERROR;
to.PutF["\"%q\"", IO.rope[NamingName[naming]]];
IF nth = 0 AND insert # NIL THEN to.PutRope[insert];
to.PutRope[IF NamingAsked[naming] THEN " (G D)" ELSE " (G P)"];
SELECT nth FROM
=0 => NULL;
>0 => to.PutRope[")"];
ENDCASE => ERROR;
nth _ nth + 1;
};
ENDLOOP;
IF nth > 1 THEN to.PutRope[")"];
};
CheckNodeInCircuit: PROC [node: REF CircuitNode, circuit: REF Circuit] = {
IF NOT tiptoe THEN RETURN;
FOR nl: LIST OF REF CircuitNode _ circuit.nodes, nl.rest WHILE nl # NIL DO
IF nl.first = node THEN EXIT;
REPEAT FINISHED => ERROR;
ENDLOOP;
};
CheckMergeDirectory: PROC [circuit: REF Circuit] ~ {
CheckMerges: PROC [key: RefTab.Key, val: RefTab.Val] RETURNS [quit: BOOLEAN] -- RefTab.EachPairAction -- ~ {
bottomNode: REF CircuitNode ~ NARROW[key];
FOR ml: MergeRecList _ NARROW[val], ml.rest WHILE ml # NIL DO
bottomCircuit: REF Circuit _ SXAccessInternal.GetLogicalCell[ml.first.applChain.first.ob].circuit;
CheckNodeInCircuit[bottomNode, bottomCircuit];
CheckNodeInCircuit[ml.first.becomes, circuit];
ENDLOOP;
quit _ FALSE;
};
IF tiptoe AND circuit.mergeDirectory#NIL THEN
[] _ circuit.mergeDirectory.Pairs[action: CheckMerges];
};
AddIntermediateNodes: PUBLIC PROC [cellList: LIST OF REF LogicalCell] ~ {
FOR cl: LIST OF REF LogicalCell _ cellList, cl.rest WHILE cl # NIL DO
CheckMergeDirectory[cl.first.circuit];
ENDLOOP;
FOR cl: LIST OF REF LogicalCell _ cellList, cl.rest WHILE cl # NIL DO
circuit: REF Circuit _ cl.first.circuit;
PiecifyMerges: PROC [key: RefTab.Key, val: RefTab.Val] RETURNS [quit: BOOLEAN] -- RefTab.EachPairAction -- ~ {
bottomNode: REF CircuitNode ~ NARROW[key];
FOR ml: MergeRecList _ NARROW[val], ml.rest WHILE ml # NIL DO
IF ml.first.applChain = NIL THEN ERROR;
IF ml.first.applChain.rest = NIL THEN
bottomNode.properties _ bottomNode.properties.PutProp[prop~ isPort, val~ isPort]
ELSE {
lowNode: REF CircuitNode _ bottomNode;
nextHigherNode: REF CircuitNode;
lastQual: LIST OF CD.Instance;
highQual: LIST OF CD.Instance;
FOR appls: LIST OF CD.Instance _ ml.first.applChain, appls.rest WHILE appls.rest # NIL DO
qual: LIST OF CD.Instance ~ LIST[appls.first];
lastStep: LIST OF CD.Instance;
parentCircuit: REF Circuit _ SXAccessInternal.GetLogicalCell[appls.rest.first.ob].circuit;
[node~ nextHigherNode, rootQualifier~ lastStep] _ SX.FindRootNode[ circuit~parentCircuit, subcircuitNode~lowNode, qualifier~qual, insertIfNotInCircuit~TRUE];
IF lastStep # NIL THEN ERROR;
IF nextHigherNode = NIL THEN ERROR;
CheckNodeInCircuit[nextHigherNode, parentCircuit];
CheckMergeDirectory[parentCircuit];
lowNode.properties _ lowNode.properties.PutProp[prop~ isPort, val~ isPort];
lowNode _ nextHigherNode;
lastQual _ appls.rest;
ENDLOOP;
[ node~ nextHigherNode, rootQualifier~ highQual] _ SX.FindRootNode[ circuit~ circuit, subcircuitNode~ lowNode, qualifier~ lastQual, insertIfNotInCircuit~ FALSE];
IF highQual = NIL AND nextHigherNode # ml.first.becomes THEN ERROR;
IF highQual # NIL AND (highQual.rest # NIL OR highQual.first # lastQual.first) THEN ERROR;
lowNode.properties _ lowNode.properties.PutProp[prop~ isPort, val~ isPort];
IF highQual # NIL THEN {
newML: MergeRecList ~ LIST[[lastQual, ml.first.becomes]];
newML.rest _ NARROW[circuit.mergeDirectory.Fetch[ lowNode].val];
[] _ circuit.mergeDirectory.Store[ lowNode, newML];
}
};
ENDLOOP;
quit _ FALSE;
};
IF circuit.mergeDirectory # NIL THEN {
CheckMergeDirectory[circuit];
[] _ circuit.mergeDirectory.Pairs[ action~ PiecifyMerges];
CheckMergeDirectory[circuit];
};
ENDLOOP;
FOR cl: LIST OF REF LogicalCell _ cellList, cl.rest WHILE cl # NIL DO
circuit: REF Circuit = cl.first.circuit;
FOR appls: CD.InstanceList _ circuit.subcircuits, appls.rest WHILE appls # NIL DO
subcircuit: REF Circuit = SXAccessInternal.GetLogicalCell[appls.first.ob].circuit;
FOR nl: LIST OF REF CircuitNode _ subcircuit.nodes, nl.rest WHILE nl # NIL DO
IF nl.first.properties.GetProp[ isPort] # NIL THEN {
parentNode: REF CircuitNode;
qual: LIST OF CD.Instance;
[node: parentNode, rootQualifier: qual] _ SX.FindRootNode[circuit: circuit, subcircuitNode: nl.first, qualifier: LIST[appls.first], insertIfNotInCircuit: TRUE];
IF qual#NIL OR parentNode=NIL THEN ERROR;
};
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
CleanUp: PUBLIC PROC [cellList: LIST OF REF LogicalCell] ~ {
FOR cl: LIST OF REF LogicalCell _ cellList, cl.rest WHILE cl # NIL DO
circuit: REF Circuit _ cl.first.circuit; 
FOR nl: LIST OF REF CircuitNode _ circuit.nodes, nl.rest WHILE nl # NIL DO
nl.first.properties _ nl.first.properties.PutProp[ actualSignalName, NIL].PutProp[ isPort, NIL];
ENDLOOP;
FOR appls: CD.InstanceList _ circuit.subcircuits, appls.rest WHILE appls # NIL DO
CDProperties.PutInstanceProp[appls.first, actualCellInstanceName, NIL];
ENDLOOP;
FOR links: LIST OF REF NodeLinkage _ circuit.linkages, links.rest WHILE links # NIL DO
CDProperties.PutInstanceProp[ links.first.source, actualCellInstanceName, NIL];
ENDLOOP;
IF undoIntermediates THEN {
SX.NormalizeCircuit[circuit]
};
ENDLOOP;
};
undoIntermediates: BOOL _ TRUE;
IntTransform: TYPE = RECORD [dxdx, dxdy, dx, dydx, dydy, dy: INT];
PrintRoseInstantiationTransformation: PUBLIC PROC [to: IO.STREAM, appl: CD.Instance] = {
IF SXOutput.outputGeometricInfo THEN {
t: ImagerTransformation.Transformation _ CDBasics.ImagerTransform[appl.trans];
it: IntTransform _ [dxdx: Real.Fix[t.a], dxdy: Real.Fix[t.b], dx: Real.Fix[t.c], dydx: Real.Fix[t.d], dydy: Real.Fix[t.e], dy: Real.Fix[t.f]];
IF t.a # it.dxdx OR t.b # it.dxdy OR t.c # it.dx OR t.d # it.dydx OR t.e # it.dydy OR t.f # it.dy THEN ERROR;
to.PutF[" (t6 %g %g %g", IO.int[it.dxdx], IO.int[it.dxdy], IO.int[it.dx]];
to.PutF[" %g %g %g)", IO.int[it.dydx], IO.int[it.dydy], IO.int[it.dy]];
}
};	-- end PrintRoseInstantiationTransformation
PrintRoseInstanceBounds: PUBLIC PROC [to: IO.STREAM, appl: CD.Instance] = {
r: CD.Rect;
IF NOT SXOutput.outputGeometricInfo THEN RETURN;
r _ CDInstances.InstRectO[appl];
to.PutF[" (bb %g %g %g %g)",
IO.real [REAL[r.x1]/SXAccess.design.technology.lambda],
IO.real [REAL[r.y1]/SXAccess.design.technology.lambda],
IO.real [REAL[r.x2]/SXAccess.design.technology.lambda],
IO.real [REAL[r.y2]/SXAccess.design.technology.lambda]];
};
nameCount: INT _ 0;
NameTransType: PUBLIC PROC [desWDir: ROPE, obj: CD.Object, dfStream: IO.STREAM, type, mode: ATOM, length, width: CD.Number] RETURNS [name: ROPE] = {
cellFileName: ROPE;
cellStream: IO.STREAM;
name _ NARROW[CDProperties.GetProp[from~obj, prop~dfStream]];
IF name # NIL THEN RETURN;
name _ IO.PutFR["%g%g%g", IO.atom[type], IO.atom[mode], IO.int[nameCount _ nameCount + 1]];
CDProperties.PutObjectProp[onto~obj, prop~dfStream, val~name];
cellFileName _ name.Cat[".sch"];
cellStream _ FS.StreamOpen[desWDir.Cat[cellFileName], create];
dfStream.PutF["-- (CellType \"%g\")\n  %g\n", IO.rope[name], IO.rope[cellFileName]];
cellStream.PutF[
"-- %g\n\n(CreatingUser %g)\n(CreationTime \"%g\")\n",
IO.rope[cellFileName],
IO.refAny[UserCredentials.Get[].name],
IO.time[]];
cellStream.PutF[
"(CellTypeName %g)\n(EC \"Structure\" \"%g%g\")\n",
IO.refAny[name],
IO.atom[type],
IO.atom[mode]];
IF SXOutput.outputGeometricInfo THEN {
b: CD.Rect _ CD.InterestRect[obj];
cellStream.PutF["(scale %g \"lambda\")\n", IO.int[1]];
cellStream.PutF[
"(bb %g %g %g %g)\n",
IO.real [REAL[b.x1]/SXAccess.design.technology.lambda],
IO.real [REAL[b.y1]/SXAccess.design.technology.lambda],
IO.real [REAL[b.x2]/SXAccess.design.technology.lambda],
IO.real [REAL[b.y2]/SXAccess.design.technology.lambda]];
};
cellStream.PutRope["(Ports
(\"gate\" (G D) (IN))
(\"ch1\" (G D) (BIDIR) (EC \"Structure\" \"channel\"))
(\"ch2\" (G D) (BIDIR) (EC \"Structure\" \"channel\"))
)\n"];
cellStream.PutF["(MOSFETFlavor %g %g)\n", IO.atom[type], IO.atom[mode]];
cellStream.PutF["(MOSFETShape %g %g)\n", IO.real[REAL[length]/SXAccess.design.technology.lambda], IO.real[REAL[width]/SXAccess.design.technology.lambda]];
cellStream.PutF["(PrivateFollows)\n(InsidesUnspecified)\n"];
cellStream.Close[];
};
UnNameTransType: PUBLIC PROC [dfStream: IO.STREAM, linkage: REF SX.NodeLinkage] --SXOutput.LinkageHousekeeper-- = {
CDProperties.PutObjectProp[onto~linkage.source.ob, prop~dfStream, val~NIL];
};
Start[];
END.
"SXOutputImplB.mesa
Copyright c 1984, 1985 by Xerox Corporation.  All rights reserved.
Written by Shand, July 16, 1984 2:58:45 pm PDT
Last Edited by: Shand, March 10, 1985 11:11:35 pm PST
Last edited by: gbb June 6, 1986 4:33:51 pm PDT
Last Edited by: Spreitzer, January 16, 1985 12:04:51 pm PST
Last Edited by: Jacobi, April 5, 1985 3:54:25 pm PST
Last edited by: Christian Jacobi, November 7, 1986 1:22:50 pm PST

Stuff for RedBlackTree (used in SortNamings)
Initializes the symbol tables
Raises DuplicateKey if appl with same location already added.

For detecting name segments matching {n|C|Q}{0..9}+
IF NOT Valid[oldFirst] THEN LOOP;
We save 'em now, because we might propogate them upward.
Break long merge chains up into steps one application long:
-- Note circuit must have a mergeDirectory as we are currently enumerating it!
Introduce stopper nodes:
Remove names and portness.
Maybe restore old node lists and merge directories.
All new merges introduced by FindRootNode will be UnMerged and will therefore be removed by NormalizeCircuit.
Note that output is in CD units and not in lambdas
The designers prefer 1.0
Edited on March 10, 1985 11:11:36 pm PST, by Shand
Now uses SX.NormalizeCircuit to cleanup introduced merges, rather its own ad hoc scheme.  All nodes introduced by SX.FindRootNode are marked as UnMerged until they become connected to other nodes in this circuit through SX.MergeNode.  Nodes which do not become connected are deleted when SX.NormalizeCircuit is called.  In the case of nodes introduced by this module, they are never connected to other nodes, so the cleanup will be performed.
changes to: AddIntermediateNodes, CleanUp, CleanUp, DIRECTORY, PiecifyMerges (local of AddIntermediateNodes), PiecifyMerges (local of AddIntermediateNodes), PiecifyMerges (local of AddIntermediateNodes), PiecifyMerges (local of AddIntermediateNodes), CheckMergeDirectory, PiecifyMerges (local of AddIntermediateNodes), DIRECTORY, PiecifyMerges (local of AddIntermediateNodes), NameTransType, NameTransType
Edited on May 6, 1985 5:29:17 pm PDT, by Beretta
Converted to ChipNDale version CD20.
Edited on June 19, 1985 8:22:34 pm PDT, by Beretta
The designers definitely prefer lambda units.
changes to: PrintRoseInstantiationTransformation, PrintRoseInstanceBounds, NameTransType: sizes are in lambda units.
Edited on July 6, 1985 6:38:33 pm PDT, by Beretta
The wrong coordinate system was used for the position of instances
changes to: PrintRoseInstantiationTransformation: now uses ARectI.
Edited on July 8, 1985 10:41:14 am PDT, by Beretta
changes to: DIRECTORY, PrintRoseInstantiationTransformation
Last edited by: gbb July 17, 1985 3:56:55 pm PDT
Replaced ordered symbol table stuff by red-black trees for Cedar 6.0
Last edited by: gbb July 22, 1985 5:20:08 pm PDT
Added a test for empty symbol table.
Κι˜™Icodešœ
Οm
œ7™BK™.K™5K™/J™;J™4K™A—
unitš
Οk	˜	Kšœžœ˜&Kšžœ
žœ>˜FKš
œ	˜	Kšœžœ
˜Kšœ
žœ<˜NKšžœ
žœ˜Kšœžœ˜,Kšžœ
žœ>žœ˜TKšœžœ˜.Kšœžœ˜Kšœ
žœh˜zKšœžœ&˜2Kšœžœžœ˜/Kšžœ
žœa˜iKšœ	žœ
˜Kšœžœ˜(Kšœ	žœ*˜8Kšœžœ„
žœ˜©
Kšœžœ˜—šΡaox
œžœ
ž˜Lš
žœ	žœ'žœžœ0žœH˜Ή
Lšžœž˜Lšžœ˜—Lšœžœžœ
˜š
Οn
œžœ
žœžœ	žœ˜CKšœžœ
˜#K˜—š 
œžœ
žœ	žœ
žœžœžœžœ˜_šžœžœ
ž˜šœžœ˜Kšœ	žœ-˜<K˜—šœžœ˜Kšœ	žœI˜XK˜—Kšžœžœ
˜—Kšžœ
žœ
žœ
žœ
žœ
žœžœžœ
˜]K˜—š
 œžœ
žœžœ	žœ˜=Kšœžœ
˜K˜—š œžœ
žœ	žœ
žœžœžœ˜?Kš
œ#˜#Kšœžœ
žœ
žœžœ
žœ
˜8K˜—š
 
œžœ
žœžœžœ˜AKš
œ˜—š œžœ
žœ	žœ
žœžœ	žœ˜Dšžœ1žœ
žœ
ž˜IKš
žœžœžœ
žœžœ˜<Kšžœ
˜—Kšœžœ
˜K˜—š
 œžœ
žœžœ	žœ˜CKš
œ˜K˜—š œžœ
žœ	žœ
žœ œžœžœ	žœžœžœ˜qš	žœ$žœžœ
žœ
ž˜PKšœžœ˜Kšžœžœ
žœžœ$˜BKšžœ
˜—K˜—š œžœ
žœžœ˜MK˜K˜Kšœžœ
˜šžœžœ
ž˜K˜K˜K˜K˜Kšžœ
˜—K˜Kš
œ˜L™
Kš
œ,™,LšœžœžœžœΟc˜/Kšœžœžœ˜0Kšœžœžœ‘˜0Kšœžœ˜Kšœ	žœžœ˜7š œ˜Kš
ž˜Kšžœžœ˜!Kšžœ‘	˜—š œ˜ Kš
ž˜K˜Kšœžœ‘˜Kšœžœ	‘	˜#Kš
œ˜šžœžœ
ž˜Kšœžœžœ˜Kšœžœžœ
˜Kš
œ!˜!Kšžœ˜—Kšžœ˜
Kšžœ‘
˜—š œž	œ˜J™Kš
ž˜šžœžœ
žœž˜'K•StartOfExpansion@[getKey: 
RedBlackTree.GetKey, compare: 
RedBlackTree.Compare]š
œC˜CKš
ž˜—Kšžœ
˜
—š œž	œ&žœ
žœ˜SKš
ž˜Kšžœžœ˜.Kšœžœžœ
˜&Kšœžœ!˜2Kš
œ"˜"Kš
‘=™=Kšžœžœ˜š
ž˜Kšœžœžœ
˜—Kšžœ‘
˜—Kš
œ
™
—š œžœ
žœžœ˜JKšžœžœ
žœ
žœ˜.šžœžœžœ
ž˜9Kšœžœ˜šœžœžœ
˜K™3—Kšœ9žœžœ
˜FK˜Kšœžœ
˜šžœ
žœžœ
žœ
™!K™8—šžœžœ
žœž˜.Kšœžœ˜!šžœž˜
Kšœ
žœžœ˜.Kšžœ
˜—šžœž˜
Kšœ&žœ˜-šžœ˜Kš
žœ
žœžœžœ
žœ˜AKš
žœžœ
žœžœ
žœ
˜=K˜—Kšžœžœ
˜—Kš
œ ˜ šžœž˜
Kšœžœ
˜ Kšžœžœ
˜—šžœž˜
Kšœžœžœ˜7Kšœžœžœ˜/Kšžœžœ
˜,—Kšžœ
˜—Kšžœžœ˜$Kšœžœ$˜@Kšžœ
˜—Kšžœžœ
žœ
žœ
˜šžœžœ˜$šžœžœ
žœž˜'šœžœ*˜AKšœžœžœ
˜š	žœžœžœžœž˜3Kšœžœ˜1Kš
œ˜Kš
œ˜Kšœ
žœ;˜KKšžœ
˜—K–[self: 
RedBlackTree.Table]š
œ-˜-šžœžœ˜šžœžœ
žœž˜'Kš
œ,˜,Kšžœ
˜—Kšžœ
˜Kš
œ
˜
——Kšžœ
˜—Kš
œ
˜
—šžœ˜š	žœžœ
ž
œ
žœž˜2šœžœ*˜Aš	žœžœžœžœž˜3Kš
œ˜Kš
œ˜Kšœ
žœ;˜KKšžœ
˜——Kš
œ,˜,Kšžœ
˜—Kš
œ˜—Kšžœžœ
žœ
žœ
˜Kš
œ˜—š œžœ
žœžœ
žœžœžœ˜PKšœžœ˜šžœžœ
žœ
ž˜6šžœžœ˜šžœž˜Kšœžœ
˜K˜K˜Kšžœžœ
˜—Kšœžœ˜/Kšžœ	žœ
žœ
žœ˜4Kšœžœžœ
žœ˜?šžœž˜Kšœžœ
˜K˜Kšžœžœ
˜—K˜K˜—Kšžœ
˜—Kšžœ	žœ˜ K˜—š œžœžœžœ
˜JKšžœ
žœžœ
žœ
˜š
žœžœ
žœ
žœ&žœžœ
ž˜JKšžœžœ
žœ
˜Kšžœ
žœžœ
˜Kšžœ
˜—K˜—š œžœžœ
˜4š
 œžœ$žœžœ‘œ˜lKšœžœžœ˜*š	žœžœžœžœ
ž˜=KšœžœP˜bKš
œ.˜.K˜.Kšžœ
˜—Kšœžœ
˜
K˜—šžœžœžœ
ž˜-Kš
œ7˜7—K˜—š œžœ
žœžœ
žœ
žœ˜Iš
žœžœ
žœ
žœ!žœžœ
ž˜EKš
œ&˜&Kšžœ
˜—K™;š
žœžœ
žœ
žœ!žœžœ
ž˜EKšœ	žœ˜(š
 
œžœ$žœžœ‘œ˜nKšœžœžœ˜*š	žœžœžœžœ
ž˜=Kšžœžœ
žœ
žœ
˜'šžœžœ
ž˜%Kš
œP˜P—šžœ˜Kšœ	žœ˜&Kšœžœ
˜ Kšœ
žœ
žœ
žœ
˜Kšœ
žœ
žœ
žœ
˜š
žœžœ
žœ
žœ+žœžœ
ž˜YKš	œžœ
žœ
žœžœ˜.Kšœ
žœ
žœ
žœ
˜KšœžœH˜ZLšœ—
žœ˜
Kšžœžœ
žœ
žœ
˜Kšžœžœ
žœ
žœ
˜#Kš
œ2˜2Kš
œ#˜#Kš
œK˜KKš
œ˜Kš
œ˜Kšžœ
˜—Lšœš
žœ˜‘
Kš
žœžœ
žœ#žœ
žœ
˜CKšžœžœ
žœžœ
žœ"žœ
žœ
˜ZKš
œK˜Kšžœžœ
žœ˜Kšœžœ˜9Kš
œN™NKšœ
žœ-˜@Kš
œ3˜3K˜
—K˜—Kšžœ
˜—Kšœžœ
˜
K˜—šžœžœ
žœ˜&K˜Kš
œ:˜:K˜K˜—Kšžœ
˜—K™š
žœžœ
žœ
žœ!žœžœ
ž˜EKšœ	žœ˜(š	žœžœ0žœ	žœ
ž˜QKšœžœC˜Rš
žœžœ
žœ
žœ)žœžœ
ž˜Mšžœ(žœ
žœ˜4Kšœžœ
˜Kšœžœ
žœ
žœ
˜Kšœqžœ%žœ˜ 
Kšžœžœ
žœžœ
žœ
žœ
˜)K˜—Kšžœ
˜—Kšžœ
˜—Kšžœ
˜—K˜—š œžœ
žœžœ
žœ
žœ˜<K™K™3š
žœžœ
žœ
žœ!žœžœ
ž˜EKšœ	žœ˜)š
žœžœ
žœ
žœ&žœžœ
ž˜JKšœEžœžœ˜`Kšžœ
˜—š	žœžœ0žœ	žœ
ž˜QKšœBžœ˜GKšžœ
˜—š
žœžœ
žœ
žœ,žœ	žœ
ž˜VKšœJžœ˜OKšžœ
˜—šžœžœ˜Kšœ2Οeœ3™mKšžœ˜K˜—Kšžœ
˜—K˜—Lšœžœžœ
˜Kšœžœžœ"žœ˜Bš $œžœ
žœžœ
žœžœ˜Xšžœžœ˜&Kš
œN˜NK˜Ž
Kšžœžœžœ
žœžœžœ
žœ
žœ
˜mKšœžœžœžœ
˜JKšœžœžœžœ
˜GK™2K˜
—Kšœ‘+˜.—š œžœ
žœžœ
žœžœ˜KKšœžœ˜Kšžœ
žœžœ
žœ
˜0Kš
œ ˜ Kšœžœžœ+žœžœ+žœžœ+žœžœ+˜ύ
K˜—Lšœžœ˜š 
œžœ
žœžœžœžœ
žœžœžœ	žœžœ˜”
Kšœžœ
˜Kšœžœ
žœ
˜Kšœžœ0˜=Kšžœžœ
žœ
žœ
˜Kš	œžœžœ
žœ
žœ!˜[Kš
œ>˜>Kš
œ ˜ Kšœ
žœ/˜>Kšœ.žœ
žœ˜T˜K˜6Kšžœ˜Kšžœ$˜&Kšžœ	˜—˜K˜3Kšžœ˜Kšžœ˜Kšžœ
˜—šžœžœ˜&Kšœžœ˜"Kšœ+žœ	˜6K™˜Kšœžœžœ+žœžœ+žœžœ+žœžœ+˜φ
—K˜—K˜₯
Kšœ*žœ
žœ
˜HKš	œ)žœžœ-žœžœ,˜š
K˜<K˜K˜—š œžœ
žœžœ
žœžœ‘œ˜sKšœFžœ˜KK˜—K˜Kšžœ
˜™2Kš
œΊ™ΊKšœΟr@œ £œ £œ £œ £$œ £œ £™•—™0K™$—™2K™-Kšœ£&’£œ™t—™1K™BKšœ£$œ’™B—™2Kšœ£/™;—™0K™D—™0K™$——…—9ΞXΩ