<<-- EditToolSortImpl.mesa>> <<-- Edited by Paxton on January 4, 1983 9:00 am>> DIRECTORY EditToolPrivate, EditToolBuilder, Buttons, Convert, EditNotify, EditSpan, Environment, Inline, IO, UndoEvent, Labels, List, ListSort, Menus, MessageWindow, NodeAddrs, ParticularList, Rope, RopeEdit, RopeReader, RunReader, Runtime, TextEdit, TextFind, TextLooks, TextLooksSupport, TextNode, TEditDisplay, TEditDocument, TEditInput, TEditInputOps, TEditLocks, TEditOps, TEditSelection, TreeFind, UserTerminal, ViewerClasses, ViewerMenus, ViewerOps; EditToolSortImpl: CEDAR MONITOR IMPORTS EditToolPrivate, EditToolBuilder, IO, Labels, ListSort, MessageWindow, Rope, RopeEdit, RopeReader, EditSpan, TEditInput, TEditInputOps, TEditLocks, TEditOps, TEditSelection, TextEdit, TextLooks, TextNode EXPORTS EditToolPrivate, ParticularList = { OPEN EditToolPrivate, EditToolBuilder, ParticularList; ROPE: TYPE = Rope.ROPE; Runs: TYPE = TextLooks.Runs; Offset: TYPE = TextNode.Offset; BuildSortButtons: PUBLIC PROC [info: Info] = { OPEN info; [] _ BuildButton[layout, "Sort", DoSort, info, TRUE]; [] _ BuildButton[layout, "Reverse", DoReverse, info, TRUE]; [] _ BuildButton[layout, "Sort-and-remove-duplicates", DoSortElim, info, TRUE]; ToNext[layout]; sortIncreasing _ TRUE; [sortOrderLabel,] _ BuildPair[layout,SortOrderButton,sortIncreasing,sortIncRope,sortDecRope,info]; ToMiddle[layout]; sortKind _ sortText; [sortKindLabel,] _ BuildTriple[layout, SortKindButton, sortKind, sortTextRope, sortLinesRope, sortBranchesRope, info]; }; ---------------------------- ---------------------------- sortIncRope: ROPE = "Sort increasing"; sortDecRope: ROPE = "Sort decreasing"; sortIncAtom: LIST OF REF = Register[$SortIncreasing,SortIncOp]; sortDecAtom: LIST OF REF = Register[$SortDecreasing,SortDecOp]; SortOrderButton: Buttons.ButtonProc = { ChangeState[mainToolInfo.sortIncreasing, sortIncAtom,sortDecAtom] }; SortIncOp: TEditInput.CommandProc = { SortInc[mainToolInfo] }; SortInc: PROC [info: Info] = { OPEN info; sortIncreasing _ TRUE; Labels.Set[sortOrderLabel,sortIncRope] }; SortDecOp: TEditInput.CommandProc = { SortDec[mainToolInfo] }; SortDec: PROC [info: Info] = { OPEN info; sortIncreasing _ FALSE; Labels.Set[sortOrderLabel,sortDecRope] }; ---------------------------- ---------------------------- sortTextRope: ROPE = "Text (blanks delimit)"; sortLinesRope: ROPE = "Lines (CRs delimit)"; sortBranchesRope: ROPE = "Branches"; sortTextAtom: LIST OF REF = Register[$SortText,SortTextOp]; sortLinesAtom: LIST OF REF = Register[$SortLines,SortLinesOp]; sortBranchesAtom: LIST OF REF = Register[$SortBranches,SortBranchesOp]; SortKindButton: Buttons.ButtonProc = { CycleTriple[mainToolInfo.sortKind, sortTextAtom, sortLinesAtom, sortBranchesAtom] }; SortTextOp: TEditInput.CommandProc = { SortText[mainToolInfo] }; SortText: PROC [info: Info] = { OPEN info; sortKind _ sortText; Labels.Set[sortKindLabel,sortTextRope] }; SortLinesOp: TEditInput.CommandProc = { SortLines[mainToolInfo] }; SortLines: PROC [info: Info] = { OPEN info; sortKind _ sortLines; Labels.Set[sortKindLabel,sortLinesRope] }; SortBranchesOp: TEditInput.CommandProc = { SortBranches[mainToolInfo] }; SortBranches: PROC [info: Info] = { OPEN info; sortKind _ sortBranches; Labels.Set[sortKindLabel,sortBranchesRope] }; ---------------------------- ---------------------------- doSortAtom: LIST OF REF = Register[$DoSort,DoSortOp]; DoSort: Buttons.ButtonProc = { DoButton[doSortAtom] }; DoSortOp: TEditInput.CommandProc = { DoSortCom[mainToolInfo,FALSE,FALSE] }; doSortAndElimAtom: LIST OF REF = Register[$DoSortAndRemoveDuplicates,DoSortAndElimOp]; DoSortElim: Buttons.ButtonProc = { DoButton[doSortAndElimAtom] }; DoSortAndElimOp: TEditInput.CommandProc = { DoSortCom[mainToolInfo,FALSE,TRUE] }; doReverseAtom: LIST OF REF = Register[$DoReverse,DoReverseOp]; DoReverse: Buttons.ButtonProc = { DoButton[doReverseAtom] }; DoReverseOp: TEditInput.CommandProc = { DoSortCom[mainToolInfo,TRUE,FALSE] }; DoSortCom: ENTRY PROC [info: Info, reversing, eliminateDuplicates: BOOLEAN] = { ENABLE UNWIND => NULL; <<-- monitor this so can save ropereaders in globals for use in Compare>> DoSortComI[info, reversing, eliminateDuplicates]; r1 _ r2 _ NIL }; DoSortComI: PROC [info: Info, reversing, eliminateDuplicates: BOOLEAN] = { OPEN info; sel: TEditDocument.Selection; span: TextNode.Span; list: LIST OF Item; root: TextNode.Ref; kind: [0..2] _ sortKind; count, duplicates: INT _ 0; { CountBlanks: PROC [rope: Rope.ROPE, from: Offset] RETURNS [count: Offset] = { IF Rope.Size[rope]=0 THEN RETURN [0]; RopeReader.SetPosition[r1, rope, from]; count _ 0; WHILE RopeEdit.BlankChar[RopeReader.Get[r1]] DO count _ count+1; ENDLOOP }; GetRopeReaders: PROC = { r1 _ RopeReader.Create[]; r2 _ RopeReader.Create[] }; event: UndoEvent.Ref _ TEditInput.CurrentEvent[]; TEditSelection.LockSel[primary, "DoSortComI"]; sel _ TEditOps.GetSelData[]; IF ~CheckPSel[sel] OR ~TEditInputOps.CheckReadonly[sel] THEN { OPEN MessageWindow; Append["Make selection.", TRUE]; Blink; TEditSelection.UnlockSel[primary]; RETURN }; root _ TEditSelection.SelectionRoot[sel]; tSel^ _ sel^; increasing _ sortIncreasing; interrupt^ _ FALSE; [ ] _ TEditLocks.Lock[root, "DoSortComI"]; span _ [tSel.start.pos, tSel.end.pos]; IF kind=sortBranches THEN { start, end, last, loc: TextNode.Ref; Next: PROC [n: TextNode.Ref] RETURNS [TextNode.Ref] = INLINE { RETURN [TextNode.Next[n]] }; IsSibling: PROC [first, last: TextNode.Ref] RETURNS [BOOLEAN] = { FOR n: TextNode.Ref _ first, Next[n] DO SELECT n FROM NIL => RETURN [FALSE]; last => EXIT; ENDCASE; ENDLOOP; RETURN [TRUE] }; start _ span.start.node; FOR n: TextNode.Ref _ span.end.node, TextNode.Parent[n] DO IF n = NIL THEN { OPEN MessageWindow; Append["Selection must end inside a sibling of start node.",TRUE]; Blink[]; GOTO Quit }; IF IsSibling[start,n] THEN { last _ n; EXIT }; ENDLOOP; GetRopeReaders[]; loc _ start; end _ Next[last]; UNTIL loc=end DO -- make list of things to sort node: TextNode.RefTextNode _ TextNode.NarrowToTextNode[loc]; blanks: Offset _ CountBlanks[node.rope,0]; list _ TextNode.pZone.CONS[Item[node,0,TextEdit.Size[node],blanks],list]; loc _ Next[loc]; count _ count+1; ENDLOOP; IF ~reversing AND ~interrupt^ THEN list _ ListSort.Sort[list]; IF ~interrupt^ THEN { -- reorder the branches Del: PROC [text: TextNode.RefTextNode] = { [] _ EditSpan.Delete[ root: root, del: TextNode.MakeNodeSpan[text,TextNode.LastWithin[text]], event: event, saveForPaste: FALSE] }; parent: TextNode.Ref _ TextNode.Parent[start]; IF eliminateDuplicates THEN [duplicates, ----] _ EliminateDuplicates[list, Del]; IF list.first.text # start THEN { -- move list.first.text to correct location IF TextNode.FirstChild[parent] = start THEN -- move first to child of parent [] _ EditSpan.Move[ destRoot: root, sourceRoot: root, dest: TextNode.MakeNodeLoc[parent], source: TextNode.MakeNodeSpan[list.first.text,TextNode.LastWithin[list.first.text]], where: child, event: event] ELSE -- move first to after node before start [] _ EditSpan.Move[ destRoot: root, sourceRoot: root, dest: TextNode.MakeNodeLoc[TextNode.Previous[start, parent]], source: TextNode.MakeNodeSpan[list.first.text,TextNode.LastWithin[list.first.text]], where: sibling, event: event]; start _ list.first.text }; FOR lst: LIST OF Item _ list, lst.rest DO <<-- move next of list to after first of list>> next, dest: TextNode.Ref; nesting: INTEGER; IF lst.rest=NIL THEN { last _ lst.first.text; EXIT }; next _ lst.rest.first.text; IF lst.first.text.next = next THEN LOOP; -- already in correct order dest _ TextNode.LastWithin[lst.first.text]; nesting _ 0; FOR n: TextNode.Ref _ dest, TextNode.Parent[n] UNTIL n=lst.first.text DO nesting _ nesting-1; ENDLOOP; [] _ EditSpan.Move[ destRoot: root, sourceRoot: root, dest: TextNode.MakeNodeLoc[dest], source: TextNode.MakeNodeSpan[next,TextNode.LastWithin[next]], nesting: nesting, where: sibling, event: event]; ENDLOOP; }; SELECT tSel.granularity FROM node, branch => NULL; ENDCASE => tSel.granularity _ node; tSel.start.pos _ [start, 0]; last _ TextNode.LastWithin[last]; tSel.end.pos _ [last, MAX[TextEdit.Size[TextNode.NarrowToTextNode[last]],1]-1]; } ELSE { -- sorting text/lines within a single node node: TextNode.RefTextNode; rope, newRope: Rope.ROPE; runs, newRuns: Runs; start, loc, end, newSize, elim: Offset; lastChar, delimChar, finalChar: CHAR _ 0C; looks: TextLooks.Looks; addedChar, addedDelimiter, replacedFinalDelimiter: BOOL _ FALSE; Next: PROC [at: Offset] RETURNS [next: Offset, finalChar: CHAR] = { -- scan to break char: CHAR; RopeReader.SetPosition[r1,rope,at]; next _ at; finalChar _ 0C; IF kind=sortText THEN { -- scan to blanks UNTIL next=end OR RopeEdit.BlankChar[char _ RopeReader.Get[r1]] DO finalChar _ char; next _ next+1; ENDLOOP; IF next=end THEN RETURN; next _ next+1; UNTIL next=end OR ~RopeEdit.BlankChar[RopeReader.Get[r1]] DO next _ next+1; ENDLOOP } ELSE { -- scan to CRs UNTIL next=end OR (char _ RopeReader.Get[r1]) = '\n DO finalChar _ char; next _ next+1; ENDLOOP; IF next=end THEN RETURN; next _ next+1; UNTIL next=end OR RopeReader.Get[r1] # '\n DO next _ next+1; ENDLOOP }}; ConcatList: PROC [start, num: INT] RETURNS [cRope: ROPE, cRuns: Runs, cSize, depth: Offset] = { iList: LIST OF Item _ list; IF interrupt^ THEN RETURN; IF num > 8 THEN { -- split into balanced parts half: INT _ num/2; fRope, bRope: ROPE; fRuns, bRuns: Runs; fSize, bSize, fDepth, bDepth: Offset; [fRope, fRuns, fSize, fDepth] _ ConcatList[start, half]; [bRope, bRuns, bSize, bDepth] _ ConcatList[start+half, num-half]; IF interrupt^ THEN RETURN; cRope _ RopeEdit.Concat[fRope, bRope, fSize, bSize]; cRuns _ TextLooks.Concat[fRuns, bRuns, fSize, bSize]; cSize _ fSize + bSize; IF (depth _ MAX[fDepth,bDepth]+1) > 4 THEN { -- need to flatten as we go depth _ 0; cRope _ RopeEdit.SemiFlatten[cRope]; cRuns _ TextLooks.Flatten[cRuns] }; RETURN }; FOR i: INT _ 0, i+1 UNTIL i=start DO -- skip to correct part of list iList _ iList.rest; ENDLOOP; cSize _ depth _ 0; FOR i: INT _ 0, i+1 UNTIL i=num DO -- concat the items cRope _ RopeEdit.Copy[dest: cRope, destLoc: cSize, source: rope, start: iList.first.start, len: iList.first.len, destSize: cSize]; cRuns _ TextLooks.Copy[dest: cRuns, destLoc: cSize, source: runs, start: iList.first.start, len: iList.first.len, destSize: cSize]; cSize _ cSize+iList.first.len; iList _ iList.rest; ENDLOOP; }; IF span.start.node # span.end.node THEN { OPEN MessageWindow; Append["Selection must be in a single node.",TRUE]; Blink[]; GOTO Quit }; node _ TextNode.NarrowToTextNode[span.start.node]; IF node=NIL THEN GOTO Quit; rope _ node.rope; runs _ node.runs; IF (start _ span.start.where) = TextNode.NodeItself THEN start _ 0; IF (end _ span.end.where) = TextNode.NodeItself THEN end _ Rope.Size[rope]-1; IF end <= start THEN GOTO Quit; GetRopeReaders[]; loc _ start; end _ end+1; -- location after the things to be sorted lastChar _ TextEdit.FetchChar[node,end-1]; IF kind=sortText THEN { IF ~RopeEdit.BlankChar[lastChar] THEN { -- add blank [] _ TextEdit.InsertChar[root: root, dest: node, destLoc: end, char: ' , event: event]; addedChar _ TRUE }} ELSE IF lastChar # '\n THEN { -- add CR [] _ TextEdit.InsertChar[root: root, dest: node, destLoc: end, char: '\n , event: event]; addedChar _ TRUE }; IF addedChar THEN { end _ end+1; rope _ node.rope; runs _ node.runs }; UNTIL loc=end DO -- make list of things to sort next, blanks: Offset; [next, finalChar] _ Next[loc]; IF loc=start AND RopeEdit.PunctuationChar[finalChar] THEN delimChar _ finalChar ELSE IF finalChar # delimChar THEN IF next#end THEN delimChar _ 0C -- don't have uniform delimiters ELSE IF delimChar # 0C THEN { IF RopeEdit.PunctuationChar[finalChar] THEN { -- replace final delimiter finalCharLoc: Offset; RopeReader.SetPosition[r1,node.rope,end]; UNTIL RopeReader.Backwards[r1]=finalChar DO ENDLOOP; finalCharLoc _ RopeReader.GetIndex[r1]; [] _ TextEdit.ReplaceByChar[ root: root, dest: node, start: finalCharLoc, len: 1, inherit: FALSE, looks: looks _ TextEdit.FetchLooks[node, finalCharLoc], char: delimChar, event: event]; replacedFinalDelimiter _ TRUE } ELSE { -- add delimiter to final item [] _ TextEdit.InsertChar[ root: root, dest: node, destLoc: end-1, char: delimChar, event: event]; addedDelimiter _ TRUE; next _ end _ end+1 }; rope _ node.rope; runs _ node.runs }; blanks _ IF kind=sortText THEN 0 ELSE CountBlanks[node.rope, loc]; list _ TextNode.pZone.CONS[Item[node, loc, next-loc, blanks], list]; loc _ next; count _ count+1; ENDLOOP; elim _ 0; IF ~reversing THEN { list _ ListSort.Sort[list]; IF eliminateDuplicates THEN [duplicates, elim] _ EliminateDuplicates[list] }; [newRope, newRuns, newSize, ----] _ ConcatList[0, count-duplicates]; -- concat in new order IF ~interrupt^ THEN { IF newSize # end-start-elim THEN ERROR; [] _ TextEdit.ReplaceByText[root: root, dest: node, destStart: start, destLen: end-start, sourceRope: newRope, sourceRuns: newRuns, event: event] }; IF addedChar THEN { -- delete trailing blank or CR TextEdit.DeleteText[root: root, text: node, start: start+newSize-1, len: 1, event: event]; newSize _ newSize-1 }; IF addedDelimiter OR replacedFinalDelimiter THEN { -- fix up trailing delimiter RopeReader.SetPosition[r1,node.rope,start+newSize]; UNTIL RopeReader.Backwards[r1]=delimChar DO ENDLOOP; IF addedDelimiter THEN { TextEdit.DeleteText[ root: root, text: node, start: RopeReader.GetIndex[r1], len: 1, event: event]; newSize _ newSize-1 } ELSE IF replacedFinalDelimiter THEN [] _ TextEdit.ReplaceByChar[ root: root, dest: node, start: RopeReader.GetIndex[r1], len: 1, inherit: FALSE, looks: looks, char: finalChar, event: event] ELSE ERROR }; tSel.end.pos.where _ tSel.start.pos.where + MAX[newSize-1, 0]; [] _ TextEdit.Flatten[node]; -- just to be safe }; -- end of text/line case tSel.pendingDelete _ FALSE; TEditSelection.MakeSelection[new: tSel]; TEditSelection.UnlockDocAndPSel[root]; IF ~interrupt^ THEN { OPEN IO; h: Handle _ CreateOutputStreamToRope[]; Put[h, int[count], IF ~reversing THEN rope[" items sorted. "] ELSE rope[" items reversed. "]]; IF eliminateDuplicates THEN Put[h, int[duplicates], IF duplicates=1 THEN rope[" duplicate eliminated. "] ELSE rope[" duplicates eliminated. "]]; MessageWindow.Append[GetOutputStreamRope[h],TRUE] } ELSE MessageWindow.Append["interrupted",TRUE]; EXITS Quit => TEditSelection.UnlockDocAndPSel[root] }}; r1, r2: RopeReader.Ref; increasing: BOOL; debug: BOOL _ FALSE; EliminateDuplicates: PROC [lst: LIST OF Item, proc: PROC [TextNode.RefTextNode] _ NIL] RETURNS [number, elim: Offset] = { number _ elim _ 0; UNTIL lst.rest = NIL DO IF Compare[lst, lst.rest]=equal THEN { -- eliminate lst.rest elim _ elim + lst.rest.first.len; number _ number + 1; IF proc # NIL THEN proc[lst.rest.first.text]; lst.rest _ lst.rest.rest; LOOP }; lst _ lst.rest; ENDLOOP }; Compare: PUBLIC SAFE PROC [a, b: LIST OF Item] RETURNS [result: Environment.Comparison] = { <<-- exported to ParticularList; called by ListSort.Sort>> aBlanks: Offset = a.first.blanks; bBlanks: Offset = b.first.blanks; result _ RopeReader.CompareSubstrs[ r1: a.first.text.rope, r2: b.first.text.rope, rdr1: r1, rdr2: r2, case: FALSE, start1: a.first.start+aBlanks, start2: b.first.start+bBlanks, len1: a.first.len-aBlanks, len2: b.first.len-bBlanks]; RETURN [SELECT result FROM less => IF increasing THEN less ELSE greater, equal => equal, greater => IF increasing THEN greater ELSE less, ENDCASE => ERROR] }; ---------------------------- }. ..