[Indigo]<PostCedar5.2>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

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, SetPosition],

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

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

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 {

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

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