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. ξIndexTreeImpl.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Created by Rick Beach, July 12, 1983 3:27 pm Rick Beach, April 29, 1985 4:17:11 pm PDT 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 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 assuming that a phrase is a single node! get indexToolHandle from ... normalize viewer to item 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 TiogaFileOps.SetContents[node, nodeRope]; really want the button in here so we can update it for them 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 Κ Q˜codešœ™Kšœ Οmœ1™Kšœ žœΟc5˜M—K˜KšΠbl œžœž˜Kšžœ žœJ˜^Kšžœ˜Kšœž˜˜Kšžœžœžœ˜Kšœ žœ˜%Kšœ žœžœ˜&Kšœžœ˜Kšœžœ˜ Kšœ žœ˜&Kšœžœ˜!K˜Kšœ žœžœžœ+˜OKšœ žœžœžœ+˜OK˜KšœžœžœžœŸ0˜TK™K™K™KšΟb6™6K™K™K™šΟn œžœžœžœ˜OJšœ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™—š’œžœžœ˜Tšžœ=ž˜GJšœ žœ˜Jšœ žœ˜Jšœ žœ ˜šœž˜ šžœžœžœž˜Jšœ,˜,Jšœ/˜/Jšžœ ˜—Jšœ˜—Jšžœžœ˜—J˜J™—š’œžœ žœ žœ˜[Kšœ$žœ˜(JšœK˜KJšžœžœžœž œ˜>Jšžœ žœžœž œ˜:Jšžœžœžœž œ˜KšœH˜Hš žœžœžœžœžœ˜2K™#KšœZ˜ZKšžœ˜Kšœ˜—Kšœ=™=Kšœ˜—šžœžœžœ'žœ˜HK™=KšœL˜LKšœQ˜QKšžœ˜Kšœ˜—šžœžœžœ&žœ˜FK™