[Indigo]<Cedar5.3>EditTool>EditToolSortImpl.mesa!1

EditToolSortImpl.mesa

Paxton on January 4, 1983 9:00 am

Russ Atkinson, September 26, 1983 5:59 pm

Doug Wyatt, February 4, 1984 4:02:14 pm PST

Michael Plass, October 23, 1984 2:29:11 pm PDT

DIRECTORY

Basics USING [Comparison],

Buttons USING [ButtonProc],

EditSpan USING [Delete, Move],

EditToolBuilder USING [BuildButton, BuildPair, BuildTriple, ToMiddle, ToNext],

EditToolPrivate USING [ChangeState, CheckPSel, CycleTriple, DoButton, Info, mainToolInfo, Register, sortBranches, sortLines, sortText, tSel],

IO USING [Put, RopeFromROS, ROS, STREAM],

Labels USING [Set],

ListSort USING [Sort],

MessageWindow USING [Append, Blink],

ParticularList USING [Item],

Rope USING [ROPE, Size],

RopeEdit USING [BlankChar, Concat, Copy, PunctuationChar, SemiFlatten],

RopeReader USING [Backwards, CompareSubstrs, Create, Get, GetIndex, Ref, SetCharForEndOfRope, SetPosition],

RuntimeError USING [UNCAUGHT],

TEditDocument USING [Selection],

TEditInput USING [CommandProc, CurrentEvent],

TEditInputOps USING [CheckReadonly],

TEditLocks USING [Lock],

TEditOps USING [GetSelData],

TEditSelection USING [LockSel, MakeSelection, SelectionRoot, UnlockDocAndPSel, UnlockSel],

TextEdit USING [DeleteText, FetchChar, FetchLooks, Flatten, InsertChar, ReplaceByChar, ReplaceByText, Size],

TextLooks USING [Concat, Copy, Flatten, Looks, Runs],

TextLooksSupport USING [],

TextNode USING [LastWithin, MakeNodeLoc, MakeNodeSpan, NarrowToTextNode, Next, NodeItself, Offset, Parent, Previous, pZone, Ref, RefTextNode, Span],

UndoEvent USING [Ref];

EditToolSortImpl: CEDAR MONITOR

IMPORTS EditSpan, EditToolBuilder, EditToolPrivate, IO, Labels, ListSort, MessageWindow, Rope, RopeEdit, RopeReader, RuntimeError, 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

r1 ← RopeReader.Create[];

r2 ← RopeReader.Create[];

DoSortComI[info, reversing, eliminateDuplicates ! RuntimeError.UNCAUGHT => {TEditSelection.UnlockSel[primary]; REJECT}];

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: INT ← 0;

duplicates: INT ← 0;

CountBlanks: PROC [rope: Rope.ROPE, from: Offset] RETURNS [count: Offset] = {

IF Rope.Size[rope]=0 THEN RETURN [0];

RopeReader.SetCharForEndOfRope[r1, '\000];

RopeReader.SetPosition[r1, rope, from];

count ← 0;

WHILE RopeEdit.BlankChar[RopeReader.Get[r1]] DO count ← count+1; ENDLOOP };

event: UndoEvent.Ref ← TEditInput.CurrentEvent[];

TEditSelection.LockSel[primary, "DoSortComI"];

sel ← TEditOps.GetSelData[];

IF ~CheckPSel[sel] OR ~TEditInputOps.CheckReadonly[sel] THEN {

MessageWindow.Append["Make selection.", TRUE];

MessageWindow.Blink;

TEditSelection.UnlockSel[primary];

}

ELSE {

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 {

MessageWindow.Append["Selection must end inside a sibling of start node.",TRUE];

MessageWindow.Blink[];

GOTO Quit };

IF IsSibling[start,n] THEN { last ← n; EXIT };

ENDLOOP;

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];

previous: TextNode.Ref ← TextNode.Previous[start, parent];

IF eliminateDuplicates THEN [duplicates, ----] ← EliminateDuplicates[list, Del];

DKW: Note that EliminateDuplicates might delete start!

start ← list.first.text; -- new start

IF TextNode.Previous[start] # previous THEN { -- move start to correct location

IF previous=NIL THEN -- move first to child of parent

[] ← EditSpan.Move[

destRoot: root, sourceRoot: root, dest: TextNode.MakeNodeLoc[parent],

source: TextNode.MakeNodeSpan[start, TextNode.LastWithin[start]],

where: child, event: event]

ELSE -- move first to after node before start

[] ← EditSpan.Move[

destRoot: root, sourceRoot: root,

dest: TextNode.MakeNodeLoc[previous],

source: TextNode.MakeNodeSpan[start, TextNode.LastWithin[start]],

where: sibling, event: event];

};

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

RopeReader.SetCharForEndOfRope[r1, ' ];

UNTIL RopeEdit.BlankChar[char ← RopeReader.Get[r1]] DO

finalChar ← char; next ← next+1; ENDLOOP;

IF next=end THEN RETURN; next ← next+1;

RopeReader.SetCharForEndOfRope[r1, '\000];

WHILE RopeEdit.BlankChar[RopeReader.Get[r1]] DO

next ← next+1; ENDLOOP }

ELSE { -- scan to CRs

RopeReader.SetCharForEndOfRope[r1, '\n];

UNTIL (char ← RopeReader.Get[r1]) = '\n DO

finalChar ← char; next ← next+1; ENDLOOP;

IF next=end THEN RETURN; next ← next+1;

RopeReader.SetCharForEndOfRope[r1, '\000];

WHILE 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 {

MessageWindow.Append["Selection must be in a single node.",TRUE];

MessageWindow.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;

loc ← start;

end ← MIN[end+1, Rope.Size[node.rope]]; -- 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 {

h: IO.STREAM ← IO.ROS[];

IO.Put[h, [integer[count]],

IF ~reversing THEN [rope[" items sorted. "]]

ELSE [rope[" items reversed. "]]];

IF eliminateDuplicates THEN IO.Put[h, [integer[duplicates]],

IF duplicates=1 THEN [rope[" duplicate eliminated. "]]

ELSE [rope[" duplicates eliminated. "]]];

MessageWindow.Append[IO.RopeFromROS[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: Basics.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] };

----------------------------

Michael Plass, October 23, 1984 2:29:35 pm PDT — Fixed bounds fault that came up when sorting lines that came up to the end of the document. Also added kludge to unlock the selection in case of an uncaught error, to make debugging easier.