IndexTreeImpl.mesa
Copyright © 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
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
more attention necessary to the phrases invariant here
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 ~ {
PROC [k: Key, data: UserData] RETURNS [Comparison];
ixItem1: IxItem ~ NARROW[k];
ixItem2: IxItem ~ NARROW[data];
result: Basics.Comparison ← IndexProps.Compare[ixItem1.ix, ixItem2.ix].result;
IF result # equal THEN RETURN [result];
compare see phrases
{
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];
};
still equal, compare order of index reference span
RETURN [CompareSpanOrder[ixItem1.range, ixItem2.range]];
};
CompareSpanOrder: PROC [span1, span2: TextNode.Span]
RETURNS [result: Basics.Comparison] ~ {
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;
};
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 {
this entry is the first entry in the tree.
InsertPhrases[ixItem, ixItem.ix.phrases, index.root, index.root, child];
RETURN;
};
IF largerIxItem # NIL THEN {
this entry must be the first item in the tree.
[correctParent, largerParent] ← BelongsToBranch[ixItem, largerIxItem];
IF NOT correctParent AND smallerIxItem = NIL THEN {
insert a new branch for this entry.
InsertPhrases[ixItem, ixItem.ix.phrases, index.root, largerParent, before];
RETURN;
};
leave behind largerParent as a correct parent of this entry.
};
IF smallerIxItem # NIL THEN {
this entry goes somewhere after the smaller entry in the tree.
[correctParent, smallerParent] ← BelongsToBranch[ixItem, smallerIxItem];
IF NOT correctParent AND largerIxItem = NIL THEN {
insert a new branch for this entry.
InsertPhrases[ixItem, ixItem.ix.phrases, index.root, smallerParent, sibling];
RETURN;
};
leave behind smallerParent as a correct parent of this entry.
};
IF smallerParent # NIL AND AllPhrasesMatch[ixItem, smallerIxItem] THEN {
this entry belongs among the references of the smaller entry.
smallerIxItem ← BackUpToFirstItemSameAs[index.table, ixItem, smallerIxItem];
UpdateReferences[index.table, smallerIxItem, smallerIxItem.button.startLoc.node];
RETURN;
};
IF largerParent # NIL AND AllPhrasesMatch[ixItem, largerIxItem] THEN {
this entry belongs among the references of the larger entry.
smallerIxItem ← BackUpToFirstItemSameAs[index.table, ixItem, largerIxItem];
UpdateReferences[index.table, smallerIxItem, largerIxItem.button.startLoc.node];
RETURN;
};
IF largerParent = NIL THEN TRUSTED {
this is either the first child or sibling of the smaller parent.
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 {
this entry is either a first child or among the references of the larger parent.
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 {
both parents exist so try climbing the path from the larger parent until it crosses over the smaller entry.
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 {
this entry is a child of the smaller entry.
where ← child;
}
ELSE {
this entry is a sibling of some parent of the smaller entry.
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] = {
this should be under a lock! via TiogaOps
branch: TextNode.Ref ← EditSpan.InsertTextNode[root: root, old: old, where: where];
UNTIL phrases.rest = NIL DO
oops! this should be TiogaContents from ViewerTools, but TiogaFileOps doesn't provide that interface!
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] = {
Fix up the branch that should contain the index entry.
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] = {
its possible for the see item reference to be dangling; should be avoided in IndexToolViewer but also checked here
referenceRope: ROPE;
sawPage, sawSee: BOOLEANFALSE;
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: BOOLEANFALSE]
RETURNS [reference: ROPENIL, sawPage, sawSee: BOOLEANFALSE] = {
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, ", "];
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
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] = {
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.
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] = {
Find the parent node for the ix index entry from the try index entry.
node: TextNode.Ref ← try.button.startLoc.node;
parent ← node;
Find the first-level parent node of node.
DO
q: TextNode.Ref ← TiogaOps.Parent[parent];
Quit if q is the root of the tree that contains node
IF q = NIL OR q.next = NIL THEN EXIT;
parent ← q;
ENDLOOP;
Its the correct parent if the first phrase matches the try index entry.
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];
we should update the viewer also, hmmm...
};
LastPhrase: PROCEDURE [ixItem: IxItem] RETURNS [lastPhrase: ROPE ← NIL] = {
worry about the Phrases invariant here for sure
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.