<> <> <> <> 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] ~ { <> < RETURN [less];>> < RETURN [greater];>> < IF ixItem1.range. THEN
TruePart>> <<
TestList =>
Statement;>> <
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 { <> 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.