<> <> <> <> DIRECTORY Basics USING [Comparison], EditSpan USING [CompareNodeOrder, Move, Place], IndexProps USING [Compare, IndexEntry, Phrases], IndexTree, IO USING [PutFR, rope], PutGet USING [FromRope], RedBlackTree USING [Create, Compare, Delete, DuplicateKey, GetKey, Insert, Lookup3, LookupNextLarger, Table], Rope USING [Compare, Concat, Length, Equal, ROPE], TextNode USING [Body, FirstChild, NodeItself, Ref, Span], TiogaButtons USING [AppendToButton, CreateButtonFromNode, TiogaButton, TiogaButtonProc, TextNodeRef, TiogaOpsRef], TiogaOps USING [CompareNodeOrder, GetRope, Next, Parent, Ref], TiogaOpsDefs USING []; -- convince the compiler I know what a Ref really is! IndexTreeImpl: CEDAR PROGRAM IMPORTS EditSpan, IO, IndexProps, PutGet, RedBlackTree, Rope, TextNode, TiogaButtons, TiogaOps EXPORTS TiogaOpsDefs, 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; TextNodeRef: PROC [ref: REF] RETURNS [TextNode.Ref] ~ TiogaButtons.TextNodeRef; TiogaOpsRef: PROC [ref: REF] RETURNS [TiogaOps.Ref] ~ TiogaButtons.TiogaOpsRef; DuplicateKey: PUBLIC SIGNAL = CODE; -- if ix entry already present in the indexTable <<>> <<>> <<>> <> <<>> <<>> <<>> CreateIndex: PUBLIC PROC [rootOfIndex: TextNode.Ref] RETURNS [index: Index] ~ { index.table _ RedBlackTree.Create[getKey: IxItemGetKey, compare: IxItemCompare]; index.root _ rootOfIndex; }; <<>> 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 [Basics.Comparison] ~ { SELECT EditSpan.CompareNodeOrder[span1.end.node, span2.start.node] FROM disjoint => ERROR; before => RETURN [less]; after => RETURN [greater]; same => { RETURN [SELECT TRUE FROM span1.end.where < span2.start.where => less, span1.start.where > span2.end.where => greater, ENDCASE => equal]; }; ENDCASE => ERROR; }; <<>> 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] RETURNS [ixItem: IxItem] = { smallerIxItem, equalIxItem, largerIxItem: IxItem; smallerParent, largerParent: TiogaOps.Ref _ NIL; correctParent: BOOLEAN; ixItem _ NEW[IxItemRec _ [ix, range]]; [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, TextNodeRef[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, TextNodeRef[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, TextNodeRef[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: TiogaOps.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, TextNodeRef[node], child]; RETURN; } ELSE TRUSTED { <> node: TiogaOps.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, TextNodeRef[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, TextNodeRef[node], child]; RETURN; }; }; InsertPhrases: PROCEDURE [ixItem: IxItem, phrases: IndexProps.Phrases, root, old: TextNode.Ref, where: EditSpan.Place] = { <> branch: TextNode.Ref _ NIL; UNTIL phrases = NIL OR phrases.rest = NIL DO contents: ROPE _ phrases.first; formatting: ROPE _ phrases.rest.first; phraseRoot: TextNode.Ref _ PutGet.FromRope[Rope.Concat[contents, formatting]]; phraseNode: TextNode.Ref _ TextNode.FirstChild[phraseRoot]; branch _ EditSpan.Move[destRoot: root, dest: [old, TextNode.NodeItself], sourceRoot: phraseRoot, source: [[phraseNode, TextNode.NodeItself], [phraseNode, TextNode.NodeItself]], where: IF branch = NIL THEN where ELSE child ].start.node; <> ixItem.button _ TiogaButtons.CreateButtonFromNode[node~TiogaOpsRef[branch], proc~HitIndexPhraseProc]; phrases _ phrases.rest.rest; -- munch on both contents and formatting parts ENDLOOP; IF phrases # NIL THEN ERROR; -- wonder how we got here with an invalid invariant ixItem.button _ TiogaButtons.AppendToButton[button~ixItem.button, rope~" "]; ixItem.button _ TiogaButtons.AppendToButton[button~ixItem.button, rope~RopeForIndexReference[ixItem].reference, proc~HitIndexPhraseProc, clientData~ixItem]; }; HitIndexPhraseProc: TiogaButtons.TiogaButtonProc ~ { <> <> }; UpdateBranch: PROCEDURE [indexRoot: TextNode.Ref, ixItem: IxItem, parentItem: IxItem, where: EditSpan.Place] = { <> unmatchedPhrases: IndexProps.Phrases _ IndexProps.Compare[parentItem.ix, ixItem.ix].unmatched; node: TiogaOps.Ref _ parentItem.button.startLoc.node; phrases: IndexProps.Phrases _ IF where = child THEN unmatchedPhrases ELSE unmatchedPhrases.rest; WHILE phrases # NIL DO node _ TiogaOps.Parent[node]; phrases _ phrases.rest; ENDLOOP; unmatchedPhrases _ IndexProps.Compare[ixItem.ix, parentItem.ix].unmatched; InsertPhrases[ixItem, unmatchedPhrases, indexRoot, TextNodeRef[node], where]; }; UpdateReferences: PROCEDURE [indexTable: Table, fromThisItem: IxItem, node: TiogaOps.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; <> }; 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: TiogaOps.Ref] = { <> node: TiogaOps.Ref _ try.button.startLoc.node; parent _ node; <> DO q: TiogaOps.Ref _ TiogaOps.Parent[parent]; <> IF q = NIL OR TiogaOps.Next[q] = 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.