EditToolSortImpl.mesa
Paxton on January 4, 1983 9:00 am
Russ Atkinson, September 26, 1983 5:59 pm
DIRECTORY
Basics,
EditToolPrivate,
EditToolBuilder,
Buttons,
Convert,
EditNotify,
EditSpan,
IO,
UndoEvent,
Labels,
List,
ListSort,
Menus,
MessageWindow,
NodeAddrs,
ParticularList,
Rope,
RopeEdit,
RopeReader,
RunReader,
TextEdit,
TextFind,
TextLooks,
TextLooksSupport,
TextNode,
TEditDisplay,
TEditDocument,
TEditInput,
TEditInputOps,
TEditLocks,
TEditOps,
TEditSelection,
TreeFind,
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: BOOLFALSE;
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.STREAMIO.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: BOOLFALSE;
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] };
----------------------------
}.
..