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