DIRECTORY
Basics USING [Comparison],
EditSpan USING [InsertTextNode, Place],
IndexProps USING [Compare, IndexEntry, Phrases],
IndexTree,
IO USING [PutFR, rope],
RedBlackTree USING [Create, Compare, Delete, DuplicateKey, GetKey, Insert, Lookup3, LookupNextLarger, Table],
Rope USING [Cat, Compare, Concat, Length, Equal, ROPE],
TextNode USING [Body, Parent, Ref, Span],
TiogaButtons USING [CreateButtonFromNode, TiogaButton, TiogaButtonProc],
TiogaFileOps USING [InsertNode, SetContents],
TiogaOps USING [CompareNodeOrder, GetRope, Parent, Ref],
TiogaOpsDefs USING [];  -- convince the compiler I know what a Ref really is!

IndexTreeImpl: CEDAR PROGRAM
IMPORTS EditSpan, IO, IndexProps, RedBlackTree, Rope, TextNode, TiogaButtons, TiogaFileOps, TiogaOps
EXPORTS TiogaOpsDefs, TiogaFileOps, IndexTree
= BEGIN

ROPE: TYPE = Rope.ROPE;
Comparison: TYPE = Basics.Comparison;
NodeBody: PUBLIC TYPE = TextNode.Body;
Index: TYPE ~ IndexTree.Index;
IxItem: TYPE ~ IndexTree.IxItem;
IxItemRec: TYPE ~ IndexTree.IxItemRec;
Table: TYPE ~ RedBlackTree.Table;

DuplicateKey: PUBLIC SIGNAL = CODE; -- if ix entry already present in the indexTable
CreateIndex: PUBLIC PROC [root: TiogaOps.Ref] RETURNS [index: Index] ~ {
index.table _ RedBlackTree.Create[getKey: IxItemGetKey, compare: IxItemCompare];
index.root _ root;
};
IxItemGetKey: RedBlackTree.GetKey ~ {
RETURN [data];
};
IxItemCompare: RedBlackTree.Compare ~ {
ixItem1: IxItem ~ NARROW[k];
ixItem2: IxItem ~ NARROW[data];
result: Basics.Comparison _ IndexProps.Compare[ixItem1.ix, ixItem2.ix].result;
IF result # equal THEN RETURN [result];
{
see1: IndexProps.Phrases _ ixItem1.ix.seePhrases;
see2: IndexProps.Phrases _ ixItem1.ix.seePhrases;
a: ROPE;
b: ROPE;
UNTIL see1 = NIL DO
a _ see1.first;
b _ IF see2 # NIL THEN see2.first ELSE NIL;
result _ Rope.Compare[a, b, FALSE];
IF result # equal THEN RETURN [result];
see1 _ see1.rest;
IF see2 # NIL THEN see2 _ see2.rest;
ENDLOOP;
IF see2 # NIL THEN RETURN [less];
};
RETURN [CompareSpanOrder[ixItem1.range, ixItem2.range]];
};
CompareSpanOrder: PROC [span1, span2: TextNode.Span]
RETURNS [result: Basics.Comparison] ~ {
};
Lookup: PROC [table: Table, ixItem: IxItem]
RETURNS [small, equal, large: IxItem _ NIL] ~ {
smallerItem, equalItem, largerItem: REF;
[smallerItem, equalItem, largerItem] _ RedBlackTree.Lookup3[table, ixItem];
IF smallerItem # NIL THEN small _ NARROW[smallerItem, IxItem];
IF equalItem # NIL THEN equal _ NARROW[equalItem, IxItem];
IF largerItem # NIL THEN large _ NARROW[largerItem, IxItem];
};
InsertNewIndexEntry: PUBLIC PROCEDURE [ix: IndexProps.IndexEntry, range: TextNode.Span,
index: Index] = {
ixItem: IxItem _ NEW[IxItemRec _ [ix, range]];
smallerIxItem, equalIxItem, largerIxItem: IxItem;
smallerParent, largerParent: TextNode.Ref _ NIL;
correctParent: BOOLEAN;
[smallerIxItem, equalIxItem, largerIxItem] _ Lookup[index.table, ixItem];
IF equalIxItem # NIL THEN {
-- perhaps we are extending the 
SIGNAL DuplicateKey;
};
RedBlackTree.Insert[index.table, ixItem, ixItem !
RedBlackTree.DuplicateKey => SIGNAL DuplicateKey];
IF smallerIxItem = NIL AND largerIxItem = NIL THEN {
InsertPhrases[ixItem, ixItem.ix.phrases, index.root, index.root, child];
RETURN;
};
IF largerIxItem # NIL THEN {
[correctParent, largerParent] _ BelongsToBranch[ixItem, largerIxItem];
IF NOT correctParent AND smallerIxItem = NIL THEN {
InsertPhrases[ixItem, ixItem.ix.phrases, index.root, largerParent, before];
RETURN;
};
};
IF smallerIxItem # NIL THEN {
[correctParent, smallerParent] _ BelongsToBranch[ixItem, smallerIxItem];
IF NOT correctParent AND largerIxItem = NIL THEN {
InsertPhrases[ixItem, ixItem.ix.phrases, index.root, smallerParent, sibling];
RETURN;
};
};
IF smallerParent # NIL AND AllPhrasesMatch[ixItem, smallerIxItem] THEN {
smallerIxItem _ BackUpToFirstItemSameAs[index.table, ixItem, smallerIxItem];
UpdateReferences[index.table, smallerIxItem, smallerIxItem.button.startLoc.node];
RETURN;
};
IF largerParent # NIL AND AllPhrasesMatch[ixItem, largerIxItem] THEN {
smallerIxItem _ BackUpToFirstItemSameAs[index.table, ixItem, largerIxItem];
UpdateReferences[index.table, smallerIxItem, largerIxItem.button.startLoc.node];
RETURN;
};
IF largerParent = NIL THEN TRUSTED {
unmatchedPhrases: IndexProps.Phrases _
IndexProps.Compare[ixItem.ix, smallerIxItem.ix].unmatched;
InsertPhrases[ixItem, unmatchedPhrases, index.root, smallerIxItem.button.startLoc.node, IF unmatchedPhrases = NIL THEN child ELSE sibling];
RETURN;
}
ELSE IF smallerParent = NIL THEN TRUSTED {
unmatchedPhrases: IndexProps.Phrases _
IndexProps.Compare[largerIxItem.ix, ixItem.ix].unmatched;
node: TextNode.Ref _ largerIxItem.button.startLoc.node;
WHILE unmatchedPhrases # NIL DO
node _ TiogaOps.Parent[node];
unmatchedPhrases _ unmatchedPhrases.rest;
ENDLOOP;
IF IndexProps.Compare[ixItem.ix, largerIxItem.ix].unmatched = NIL THEN {
UpdateReferences[index.table, ixItem, node];
RETURN;
};
unmatchedPhrases _ IndexProps.Compare[ixItem.ix, largerIxItem.ix].unmatched;
InsertPhrases[ixItem, unmatchedPhrases, index.root, node, child];
RETURN;
}
ELSE TRUSTED {
node: TextNode.Ref _ largerIxItem.button.startLoc.node;
where: EditSpan.Place;
unmatchedPhrases: IndexProps.Phrases _
IndexProps.Compare[largerIxItem.ix, ixItem.ix].unmatched;
WHILE unmatchedPhrases # NIL DO
node _ TiogaOps.Parent[node];
IF TiogaOps.CompareNodeOrder[node, smallerIxItem.button.startLoc.node] = before THEN {
unmatchedPhrases: IndexProps.Phrases _
IndexProps.Compare[smallerIxItem.ix, ixItem.ix].unmatched;
node _ smallerIxItem.button.startLoc.node;
IF unmatchedPhrases = NIL THEN {
where _ child;
}
ELSE {
WHILE unmatchedPhrases.rest # NIL DO
node _ TiogaOps.Parent[node];
unmatchedPhrases _ unmatchedPhrases.rest;
ENDLOOP;
where _ sibling;
};
unmatchedPhrases _ IndexProps.Compare[ixItem.ix, smallerIxItem.ix].unmatched;
InsertPhrases[ixItem, unmatchedPhrases, index.root, node, where];
RETURN;
};
IF IndexProps.Compare[ixItem.ix, largerIxItem.ix].unmatched = NIL THEN {
UpdateReferences[index.table, ixItem, node];
RETURN;
};
unmatchedPhrases _ unmatchedPhrases.rest;
ENDLOOP;
unmatchedPhrases _ IndexProps.Compare[ixItem.ix, largerIxItem.ix].unmatched;
InsertPhrases[ixItem, unmatchedPhrases, index.root, node, child];
RETURN;
};
};

InsertPhrases: PROCEDURE [ixItem: IxItem, phrases: IndexProps.Phrases, root, old: TextNode.Ref, where: EditSpan.Place] = {
branch: TextNode.Ref _ EditSpan.InsertTextNode[root: root, old: old, where: where];
UNTIL phrases.rest = NIL DO
TiogaFileOps.SetContents[branch, phrases.first];
[] _ TiogaButtons.CreateButtonFromNode[node~branch, proc~HitIndexPhraseProc];
branch _ TiogaFileOps.InsertNode[x: branch, child: TRUE];
phrases _ phrases.rest;
ENDLOOP;
TiogaFileOps.SetContents[branch,
Rope.Cat[phrases.first, ", ", RopeForIndexReference[ixItem].reference]];
[] _ TiogaButtons.CreateButtonFromNode[node~branch, end~Rope.Length[phrases.first], proc~HitIndexPhraseProc];

};

HitIndexPhraseProc: TiogaButtons.TiogaButtonProc ~ {
};

UpdateBranch: PROCEDURE [indexRoot: TiogaOps.Ref, ixItem: IxItem,
parentItem: IxItem, where: EditSpan.Place] = {
unmatchedPhrases: IndexProps.Phrases _ IndexProps.Compare[parentItem.ix, ixItem.ix].unmatched;
node: TextNode.Ref _ parentItem.button.startLoc.node;
phrases: IndexProps.Phrases _ IF where = child THEN unmatchedPhrases ELSE unmatchedPhrases.rest;
WHILE phrases # NIL DO
node _ TextNode.Parent[node];
phrases _ phrases.rest;
ENDLOOP;
unmatchedPhrases _ IndexProps.Compare[ixItem.ix, parentItem.ix].unmatched;
InsertPhrases[ixItem, unmatchedPhrases, indexRoot, node, where];
};

UpdateReferences: PROCEDURE [indexTable: Table,
fromThisItem: IxItem, node: TextNode.Ref] = {
referenceRope: ROPE;
sawPage, sawSee: BOOLEAN _ FALSE;
nodeRope: ROPE _ Rope.Concat[LastPhrase[fromThisItem], ", "];
currentItem: IxItem _ fromThisItem;
DO
currentItem.button.startLoc _ [node, nodeRope.Length];
[referenceRope, sawPage, sawSee] _ RopeForIndexReference[currentItem, sawPage, sawSee];
nodeRope _ Rope.Concat[nodeRope, referenceRope];
currentItem.button.endLoc _ [node, nodeRope.Length];
currentItem _ NARROW[RedBlackTree.LookupNextLarger[indexTable, currentItem], IxItem];
IF currentItem = NIL THEN EXIT;
IF NOT AllPhrasesMatch[fromThisItem, currentItem] THEN EXIT;
ENDLOOP;
TiogaFileOps.SetContents[node, nodeRope];
};

RopeForIndexReference: PUBLIC PROCEDURE [ixItem: IxItem,
seenPage, seenSee: BOOLEAN _ FALSE]
RETURNS [reference: ROPE _ NIL, sawPage, sawSee: BOOLEAN _ FALSE] = {
IF seenPage OR seenSee THEN reference _ ", ";
IF ixItem.ix.seePhrases # NIL THEN {
seePhrases: IndexProps.Phrases _ ixItem.ix.seePhrases;
IF sawPage THEN
reference _ Rope.Concat[reference, ", "];
IF NOT seenSee THEN
reference _ Rope.Concat[reference, IO.PutFR["%l%g%l ", IO.rope["i"], IO.rope[IF seenPage OR sawPage THEN "see also" ELSE "see"], IO.rope["I"]]];
sawSee _ seenSee;
UNTIL seePhrases = NIL DO
IF sawSee THEN reference _ Rope.Concat[reference, ", "];
reference _ Rope.Concat[reference, seePhrases.first];
seePhrases _ seePhrases.rest;
sawSee _ TRUE;
ENDLOOP;
};
};

BackUpToFirstItemSameAs: PROCEDURE [indexTable: Table, ixItem: IxItem, thisItem: IxItem]
RETURNS [firstItem: IxItem] = {
smallerIxItem, equalIxItem, largerIxItem: IxItem;
firstItem _ thisItem;
DO
[smallerIxItem, equalIxItem, largerIxItem] _ Lookup[indexTable, firstItem];
IF smallerIxItem = NIL THEN EXIT;
IF NOT AllPhrasesMatch[ixItem, smallerIxItem] THEN EXIT;
firstItem _ smallerIxItem;
ENDLOOP;
RETURN [firstItem]
};

BelongsToBranch: PROCEDURE [ixItem: IxItem, try: IxItem]
RETURNS [correctParent: BOOLEAN, parent: TextNode.Ref] = {
node: TextNode.Ref _ try.button.startLoc.node;
parent _ node;
DO
q: TextNode.Ref _ TiogaOps.Parent[parent];
IF q = NIL OR q.next = NIL THEN EXIT;
parent _ q;
ENDLOOP;
correctParent _ Rope.Equal[ixItem.ix.phrases.first, TiogaOps.GetRope[parent]] OR Rope.Equal[ixItem.ix.phrases.first, try.ix.phrases.first];
};

DeleteIndexEntry: PUBLIC PROCEDURE [ixItem: IxItem, index: Index] = {
[] _ RedBlackTree.Delete[index.table, ixItem];
};

LastPhrase: PROCEDURE [ixItem: IxItem] RETURNS [lastPhrase: ROPE _ NIL] = {
phrases: IndexProps.Phrases _ ixItem.ix.phrases;
UNTIL phrases = NIL DO
lastPhrase _ phrases.first;
phrases _ phrases.rest;
ENDLOOP;
};

AllPhrasesMatch: PROCEDURE [ix1, ix2: IxItem] RETURNS [BOOLEAN] = {
RETURN [IndexProps.Compare[ix1.ix, ix2.ix].result = equal];
};


END.
	vIndexTreeImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
Created by Rick Beach, July 12, 1983 3:27 pm
Rick Beach, April 6, 1985 8:34:58 pm PST



more attention necessary to the phrases invariant here





PROC [k: Key, data: UserData] RETURNS [Comparison];
compare see phrases
still equal, compare order of index reference span

SELECT EditSpan.CompareNodeOrder[ixItem1.range.end.node, ixItem2.range.start.node] FROM
before => RETURN [less];
after => RETURN [greater];
same => IF ixItem1.range. THEN 
TruePart

TestList => 
Statement;
ENDCASE => 
Statement;


this entry is the first entry in the tree.
this entry must be the first item in the tree.
insert a new branch for this entry.
leave behind largerParent as a correct parent of this entry.
this entry goes somewhere after the smaller entry in the tree.
insert a new branch for this entry.
leave behind smallerParent as a correct parent of this entry.
this entry belongs among the references of the smaller entry.
this entry belongs among the references of the larger entry.
this is either the first child or sibling of the smaller parent.
this entry is either a first child or among the references of the larger parent.
both parents exist so try climbing the path from the larger parent until it crosses over the smaller entry.
this entry is a child of the smaller entry.
this entry is a sibling of some parent of the smaller entry.
this should be under a lock! via TiogaOps
oops! this should be TiogaContents from ViewerTools, but TiogaFileOps doesn't provide that interface!
Fix up the branch that should contain the index entry.
its possible for the see item reference to be dangling; should be avoided in IndexToolViewer but also checked here
this is where the various looks for each kindOfEntry are applied... $Definition "bi", $Example "z", $See "i", and so on, perhaps within a $Index property on the root of the document
Search back in the index table for the first item that should preceed the ix index entry.
This may involve searching past several items whose phrases all match the ix entry.
Find the parent node for the ix index entry from the try index entry. 
Find the first-level parent node of node.
Quit if q is the root of the tree that contains node
Its the correct parent if the first phrase matches the try index entry.
we should update the viewer also, hmmm...
worry about the Phrases invariant here for sure
Κ…˜
codeš
œ™Kšœ
Οm
œ1™<K™,K™(—K˜š
Οk	˜	Kšœžœ˜Kšœ	žœ˜'Kšœžœ ˜0K˜
Kšžœ
žœ˜Kšœ
žœ[˜mKšœžœ'žœ˜7Kšœ	žœ˜)Kšœ
žœ6˜HKšœ
žœ˜-Kšœ	žœ*˜8Kšœ
žœΟc5˜M—K˜KšΠbl
œžœ
ž˜KšžœžœP˜dKšžœ&˜-Kšœž˜˜Kšžœžœžœ
˜Kšœžœ˜%Kšœ
žœ
žœ˜&Kšœžœ˜Kšœžœ˜ Kšœžœ˜&Kšœžœ˜!K˜Kšœžœ
žœžœŸ0˜TK™K™K™Kš
Οb6™6K™K™K™šΟnœžœ
žœžœ˜HJš
œP˜PJš
œ˜J˜J™—š’œ˜%Jšžœ˜J˜J™—š’
œ˜'Jšžœžœ™3Jšœžœ˜Jšœžœ˜Jš
œN˜NJšžœžœ
žœ
˜'Jš
œ™š
œ
˜
Kš
œ1˜1Kš
œ1˜1Kšœžœ
˜Kšœžœ
˜šžœžœ
ž˜K˜Kš
œžœžœ
žœžœ
ž˜+Kšœžœ˜#Kšžœžœ
žœ
˜'Kš
œ˜Kšžœžœ
žœ˜$Kšžœ
˜—Kšžœžœ
žœ
žœ˜!Jš
œ˜—Jš
œ2™2Jšžœ2˜8J˜J™—š’œžœžœ ˜\šžœMž™WJšœ
žœ™Jšœ	žœ™Jšœžœžœ™)J™Jšžœ™—J˜J™—š’œžœ žœ žœ˜[Kšœ$žœ
˜(Jš
œK˜KJšžœžœ
žœž	œ˜>Jšžœ
žœ
žœž	œ˜:Jšžœžœ
žœž	œ˜<J˜J™—š’œžœD˜iKšœžœ˜.Kš
œ1˜1Kšœ,žœ
˜0Kšœžœ
˜Kš
œI˜Išžœžœ
žœ˜J˜ Jšžœ˜Jš
œ˜—š
œ1˜1Kšœžœ˜2—š
žœžœ
žœžœ
žœ˜4K™*Kš
œH˜HKšžœ
˜Kš
œ˜—šžœžœ
žœ˜K™.Kš
œF˜Fš
žœ
žœžœžœ
žœ˜3K™#Kš
œK˜KKšžœ
˜Kš
œ˜—K™<Kš
œ˜—šžœžœ
žœ˜K™>Kš
œH˜Hš
žœ
žœžœžœ
žœ˜2K™#Kš
œM˜MKšžœ
˜Kš
œ˜—Kš
œ=™=Kš
œ˜—šžœžœ
žœ'žœ˜HK™=Kš
œL˜LKš
œQ˜QKšžœ
˜Kš
œ˜—šžœžœ
žœ&žœ˜FK™<Kš
œK˜KKš
œP˜PKšžœ
˜Kš
œ˜—šžœžœ
žœ
žœ˜$K™@Kš
œa˜aKš	œXžœžœ
žœžœ
˜‹
Kšžœ
˜Kš
œ
˜
—š
žœ
žœžœ
žœ
žœ˜*K™PKš
œ`˜`Kš
œ7˜7šžœžœ
ž˜K˜K˜)Kš
ž˜—šžœ<žœ
žœ˜HKš
œ,˜,Kšžœ
˜Kš
œ˜—Kš
œL˜LKš
œA˜AKšžœ
˜K˜
—šžœ
žœ˜K™kKš
œ7˜7Kš
œ˜Kš
œ`˜`šžœžœ
ž˜K˜šžœNžœ˜VKš
œa˜aKš
œ*˜*šžœžœ
žœ˜ K™+K˜Kš
œ
˜
—šžœ˜K™<šžœžœ
ž˜$K˜Kš
œ)˜)Kš
ž˜—K˜Kš
œ˜—Kš
œM˜MKš
œA˜AKšžœ
˜Kš
œ˜—šžœ<žœ
žœ˜HKš
œ,˜,Kšžœ
˜Kš
œ˜—Kš
œ)˜)Kš
ž˜—Kš
œL˜LKš
œA˜AKšžœ
˜Kš
œ˜—K˜K˜—š’
œž	œb˜zKš
œ)™)Kš
œS˜Sšžœž˜Kš
œe™eKš
œ0˜0K˜MKšœ3žœ˜9K˜Kš
ž˜—š
œ ˜ Kš
œH˜H—K˜mK˜K˜K˜—š’œ"˜4J˜J˜—š’œž	œY˜pK™6Kš
œ^˜^Kš
œ5˜5Kšœžœžœžœ˜`šžœžœ
ž˜Kš
œ˜Kš
œ˜Kš
ž˜—Kš
œJ˜JKš
œ@˜@Kš
œ˜K˜—š’œž	œB˜]Kš
œr™rKšœžœ
˜Kšœžœžœ
˜!Kšœ
žœ/˜=Kš
œ#˜#š
ž˜Kš
œ6˜6Kš
œW˜WKš
œ0˜0Kš
œ4˜4KšœžœA˜UKšžœžœ
žœ
žœ
˜Kšžœ
žœ,žœ
žœ
˜<Kšžœ
˜—K•StartOfExpansionμ
[viewer: 
ViewerClasses.Viewer, start: 
TiogaOpsDefs.Ref, end: 
TiogaOpsDefs.Ref, level: 
TiogaOpsDefs.SelectionGrain _ node, caretBefore: 
BOOL _ TRUE, pendingDelete: 
BOOL _ FALSE, which: 
TiogaOpsDefs.WhichSelection _ primary]š
œ)˜)K˜K˜—š’œžœ%žœžœžœ
žœžœžœžœ˜’
Kšžœžœ˜-šžœžœ
žœ˜$Kš
œ6˜6šžœ	ž˜Kš
œ)˜)—Kš
œ΅
™΅
šžœ
žœ	ž˜Kšœ#žœžœžœžœ
žœ	žœžœ	žœ
˜
—K˜šžœžœ
ž˜Kšžœžœ*˜8Kš
œ5˜5K˜Kšœ	žœ
˜Kšžœ
˜—Kš
œ˜—K˜K˜—š’œž	œ7žœ˜xK™YK™SKš
œ1˜1Kš
œ˜š
ž˜Kš
œK˜KKšžœžœ
žœ
žœ
˜!Kšžœ
žœ(žœ
žœ
˜8Kš
œ˜Kšžœ
˜—Kšžœ˜K˜K˜—š’œž	œžœžœ˜sK™FKš
œ.˜.Kš
œ˜K™)š
ž˜Kš
œ*˜*K™4Kšžœžœ
žœ
žœ
žœ
žœ
˜%Kš
œ˜Kš
ž˜—K™GKšœNžœ;˜‹
K˜K˜—š’œžœ#˜EKš
œ.˜.Kš
œ)™)K˜K˜—š’
œž	œžœž
œ˜KKš
œ/™/Kš
œ0˜0šžœžœ
ž˜K˜K˜Kš
ž˜—K˜K˜—š’œž	œžœžœ˜CKšžœ5˜;K˜K˜——K˜Kšžœ
˜—…—(J>E