-- Copyright 1996-2000 Robelle Consulting Ltd.
-- Version 1.03 November 10, 2000

<<  Sortlines:  Sort a group of lines.  This is a destructive script in that the
	lines in the specified file will be changed, unless they are already
	sorted.  This script is carefully designed so that the changes to the
	original file are done in a single operation.  Users should be able to
	recover their original file contents in a single undo operation.
	
	In order to minimize data movement, we do the following:
	
	1.  We create a list of line numbers.
	
	2.  The line numbers are logically pointers to the lines in the file.
	
	3.  We sort the list of line numbers and not the text itself.
	
	4.  A scratch file is created on the same machine as the file we
	    are sorting.  The goal is to make the final copy/delete/paste
		operation a little bit faster.
>>

name QSLUtilSort group "Ro&belle" command "&Sortlines";

Option Private;
property QSLScriptVersion = "SortLines 1.03 - Copyright 2000 Robelle Solutions Technology Inc";
property globlist = {};

<<  We want to compare the text of line numbers line1 and line2.  We
    return:
	
	    -1 if the text at line1 is less than the text at line2
		 0 if the text at line1 and line2 are the same
		+1 if the text at line1 is greater than the text at line2
>>

sub comparelines(file, line1, line2, startcolumn, endcolumn)

	buf1 = file.gettext(startline: line1, startcolumn: startcolumn,
								endline: line1, endcolumn: endcolumn);
	buf2 = file.gettext(startline: line2, startcolumn: startcolumn,
								endline: line2, endcolumn: endcolumn);

	buf1 = buf1[1];
	buf2 = buf2[1];

	if buf1 < buf2 then
		return -1;
	else
		if buf1 > buf2 then
			return 1;
		else
		--	If text is equal, check line numbers to preserve chronology
			if line1 < line2 then
				return -1;
			else
				if line1 > line2 then
					return 1;
				else
					return 0;
				endif
			endif
		endif
	endif
		
endsub

<<  The following subroutine is part of the heapsort algorithm.  It
	refers to the global globlist for sorting.
>>

sub sift(file, left, right, ascending, startcolumn, endcolumn)

	i = integer(left);
	j = integer(2 * left);
	x = globlist[i];
	finished = false;

	repeat while j <= right and not finished

		if j < right then
			if ascending then
                if comparelines(file, globlist[j], globlist[j + 1], startcolumn, endcolumn) < 0 then
					j = j + 1;
				endif
			else
				if comparelines(file, globlist[j], globlist[j + 1], startcolumn, endcolumn) > 0 then
					j = j + 1;
				endif
			endif
		endif

		if ascending then
            if comparelines(file, x, globlist[j], startcolumn, endcolumn) >= 0 then
				finished = true;
			endif
		else
			if comparelines(file, x, globlist[j], startcolumn, endcolumn) <= 0 then
				finished = true;
			endif			
		endif
		
		if not finished
			globlist[i] = globlist[j];
			i = j;
			j = 2 * i;
		endif

	endrepeat

	globlist[i] = x;
	
endsub

<<  This subroutine returns the list of line numbers passed in as a
    list of sorted lines.  That is the line numbers in the returned
	list point to lines that are in logically sorted order.
	
	The sort algorithm is heapsort taken from page 75 of Niklaus Wirth's
	Algorithms + Data Structures = Programs.
>>
	
sub sortlist(file, list, ascending, startcolumn, endcolumn)

	if typeof(ascending) = qedit.typeundefined then
		ascending = true;
	endif
	
	globlist = list;  -- We use a global variable to reduce copying, since
	                  -- parameters are always copies and not references
	n        = length(globlist);
	left     = integer(integer(n / 2) + 1);
	right    = integer(n);
	
	repeat while left > 1
	
		left = left - 1;
		
		sift(file, left, right, ascending, startcolumn, endcolumn);
		
	endrepeat
	
	repeat while right > 0
	
		x               = globlist[1];
		globlist[1]     = globlist[right];
		globlist[right] = x;
		
		right = right - 1;
		sift(file, left, right, ascending, startcolumn, endcolumn);
		
	endrepeat
	
	return globlist
	
endsub

<<  All lines from "startline" to "endline" of "file".
>>

sub sortlines(file, startline, endline, ascending)

	if typeof(ascending) = qedit.typeundefined then
		ascending = true;
	endif
	
	if startline = endline then
		return;     --  Nothing to do
	endif
	
	if startline > endline then  --  Be nice if things are reversed
		templine = endline;
		endline  = startline;
		startline= templine;
	endif
	
	if endline - startline > file.cachemaxlines / 2 then
		result = dialog("Sortlines called with more than " +
				        string(file.cachemaxlines / 2) + " lines to sort");
		return;
	endif
	
	--  Parameter checking is over.  We now start the main implementation

	--  Save the selection in the file so that we can restore it later
	
	saveselection = file.selection;
	
	--	Sort on columns if Rectangular selection
   if length(saveselection) = 3 then   -- Rectangular selection
		startcolumn = saveselection.start.column;
		endcolumn = saveselection.end.column;
	else
		startcolumn = 1;
		endcolumn = file.recordlength - 1;  -- Bug: should be RecordLength. Remove when fixed.
	endif
			
--  Create a selection that includes all of the lines from start to end
	
	file.select(startline:	startline, endline:	endline);	
	
	--  Start the sorting setup
		
	linelist = {};  --  Create a list of line numbers
	
	repeat for inx from startline to endline
	
		linelist = linelist + inx;
		
	endrepeat

	linelist = sortlist(file, linelist, ascending, startcolumn, endcolumn);

	tempfile = newfile(connection: file.connectionname);
	
	repeat for line in linelist
		buf = file.gettext(line: line);
		buf = buf[1];

		atlist = {};
		atlist.line = tempfile.linecount + 1;
		atlist.column = 1;

		tempfile.insert(at: atlist, text: buf);
	endrepeat

	tempfile.insert({""});    --  Need a final carriage return
		
	tempfile.select(startline: 1, endline: tempfile.linecount);

	tempfile.copy();

	file.select(startline: startline, endline: endline);
	
	file.paste();
	
	file.select(range: saveselection);   --  Restore original selection, if any
	
	tempfile.close(discardchanges: true);
		
endsub

<<  UI for sortlines.  Check that there is a foreground document.  Make sure
    that there is a selection.  Report errors and if everything is okay sort
	the selection.
>>

sub sortactivedocument(ascending)

    writelog(QSLScriptVersion);
	sortfile = qedit.activefile;

	if not exists(sortfile) then
		result = dialog("There is no document to sort");
	else
	
		sortselection = sortfile.selection;

		if length(sortselection) = 1 then   --  Oops, only a caret is active
			result = dialog("You must have an active selection to specify which lines to sort");
		else
		
			sortstart = sortselection.start;
			sortend   = sortselection.end;
			if sortselection.end.column = 0 then
				sortend.line   = sortend.line - 1;
			endif
			
			sortlines(sortfile, sortstart.line, sortend.line, ascending);
			
			--  Position caret at the start of the selection
			
			sortfile.select(startline: sortstart.line, startcolumn: sortstart.column);
		endif
	endif

endsub

<<
	Quick and easy routine to select columns to sort on.
	User selects columns on one or more lines and the subroutine
	automatically extends the selection to all the lines in the file.
	For multiple-line selection, it must be a rectangular selection.
>>
sub sortoncolumns();

	currentFile = qedit.activefile;

	if length(currentFile.selection) = 1 then	-- Caret only
		dialogResult = dialog("You must select some text! (2 or more columns)");
		stop;
	else
		if length(currentFile.selection) = 2 and	-- Ragged selection is invalid
			currentFile.selection.start.line <> currentFile.selection.end.line then
			dialogResult = dialog("Selected text must be on a single line or rectangular!");
			stop;
		endif
	endif

	firstColumn = currentFile.selection.start.column;
	lastColumn = currentFile.selection.end.column;
	-- dialogResult = dialog("Sorting on columns " + string(firstColumn) + " to " + string(lastColumn));

	currentFile.select	(startline: 1
						,startcolumn: firstColumn
						,endline: currentFile.linecount
						,endcolumn: lastColumn
						,rectangular: true);
endsub

on command "&Ascending"

	sortactivedocument(true);

endon

on command "&Descending"

	sortactivedocument(false);
	
endon

on command "&Select columns"

	sortoncolumns();
	
endon