% \iffalse meta-comment
%
% Copyright (C) 2013 by Robert J Lee
%
% This file may be distributed and/or modified under the
% conditions of the LaTeX Project Public License, either
% version 1.2 of this license or (at your option) any later
% version. The latest version of this license is in:
%
% http://www.latex-project.org/lppl.txt
%
% and version 1.2 or later is part of all distributions of
% LaTeX version 1999/12/01 or later.
%
% \fi
%
% \iffalse
%<package>\NeedsTeXFormat{LaTeX2e}[1999/12/01]
%<package>\ProvidesPackage{arraysort}
%<package> [2013/09/04 v1.0 sorting arrayjobx arrays]
%
%<*driver>
\documentclass{ltxdoc}
\usepackage[comparestr,comparenum,randompart]{arraysort}
\EnableCrossrefs
\usepackage{indentfirst}
\usepackage{showexpl}
\usepackage{multido}
\newbool{excludelongtest}
\setbool{excludelongtest}{true} % change to false for slow test
\CodelineIndex
\RecordChanges
\begin{document}
\DocInput{arraysort.dtx}
\end{document}
%</driver>
% \fi
%
% \CharacterTable
% {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z
% Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z
% Digits \0\1\2\3\4\5\6\7\8\9
% Exclamation \! Double quote \" Hash (number) \#
% Dollar \$ Percent \% Ampersand \&
% Acute accent \' Left paren \( Right paren \)
% Asterisk \* Plus \+ Comma \,
% Minus \- Point \. Solidus \/
% Colon \: Semicolon \; Less than \<
% Equals \= Greater than \> Question mark \?
% Commercial at \@ Left bracket \[ Backslash \\
% Right bracket \] Circumflex \^ Underscore \_
% Grave accent \` Left brace \{ Vertical bar \|
% Right brace \} Tilde \~}
%
% \CheckSum{236}
%
% \changes{v1.0}{2013/09/04}{Initial version}
%
% \GetFileInfo{arraysort.sty}
%
% \DoNotIndex{\let, \edef, \xdef, \relax, \newcommand}
% \DoNotIndex{\csname, \endcsname, \ifcsname}
% \DoNotIndex{\OR, \if, \else, \fi, \equal, \ifthenelse, \iftoggle}
% \DoNotIndex{\arabic, \addtocounter, \value, \setcounter, \stepcounter}
% \DoNotIndex{\g@addto@macro, \string}
%
%
%\def\IsPositive#1{% http://www.tex.ac.uk/cgi-bin/texfaq2html?label=isitanum
% TT\fi
% \ifcat_\ifnum0<0#1 _\else A\fi
%}
%
% \newenvironment{exg}[1]{\pagebreak[3]\begin{center}
% \line(1,0){250}
% \end{center}\nopagebreak~\par\nopagebreak\textit{Example:~~\texttt{#1}}\par\vspace{-1em}}{\begin{center}
% \line(1,0){250}
% \end{center}\delarray{A}\noindent}
%
% \title{The Arraysort Package\thanks{This document corresponds to \textsf{Arraysort}~\fileversion, dated \filedate.}}
% \author{Robert J Lee \\ latex@rjlee.homelinux.org}
%
% \maketitle
%
% \begin{abstract}
%
% The |arraysort| package allows the user to sort an array (defined
% with the |arrayjobx| package), or a portion of such an array,
% without using external files or commands or requiring a second run
% of \LaTeX.
%
% Basic comparators are provided for sorting by ASCII-code or for
% sorting numeric values. Options to tweak performance of the sort are
% also provided, should they be needed.
%
% \end{abstract}
%
% \section*{Introduction}
%
% This package implements an in-place Quick Sort algorithm for
% \LaTeX. Quick-Sort is a recursive and highly configurable algorithm
% for sorting of arrays.
%
%
% \section{Usage}
%
% The |arraysort| package requires the |arrayjobx| package, which
% provides several methods to define an array of values. This docment
% assumes that you are familiar with |arrayjobx|. A number of examples
% are provided to sort a small array named $A$; the package can sort
% much larger arrays than those shown including arrays whose contents
% are stored unexpanded (although they will be expanded when comparing
% them using the provided comparators).
%
% \subsection*{Sorting by Text}
%
% \DescribeMacro{\sortArray}
%
% To sort the first |10| elemnets of $A$, you can simply write:
% |\sortArray{|10|}{|$A$|}|
%
% |\sortArray| takes two mandatory parameters: the first is the
% number of elements to sort, the second is the name of the array.
%
% \iffalse
%<*example>
% \fi
\begin{exg}{$\backslash$sortArray with words}\begin{LTXexample}
\newarray{A}
\readarray{A}{The&Quick&Brown&%
Fox&Jumps&Over&the&Lazy&Dog}
\sortArray{9}{A}
\A(1) \A(2) \A(3) \A(4) \A(5)
\A(6) \A(7) \A(8) \A(9)
\end{LTXexample}\end{exg}
% \iffalse
%</example>
% \fi
% Note that the default is to sort by character code order, so the
% lower-case ``the'' is sorted after the words starting with
% upper-case letters. This is a limitation of the default sorting
% method, but other ways of sorting are possible.
%
% \subsection*{Sorting Numbers}
%
% The default sorting method can have surprising results when sorting
% arrays of numbers:
% \iffalse
%<*example>
% \fi
\begin{exg}{$\backslash$sortArray with numbers}\begin{LTXexample}
\newarray{A}
\readarray{A}{78&4&85&1&28&6}
\sortArray{6}{A}
\A(1) \A(2) \A(3) \A(4) \A(5) \A(6)
\end{LTXexample}\end{exg}
% \iffalse
%</example>
% \fi
% Here, the numbers are still sorted in dictionary order,
% which was probably not the intent, as the number~28 would usually be
% sorted after the number~6, even though the first digit of~28 is
% smaller than the first digit of~6.
%
% To solve this problem, an alternative comparator can be used:
% \iffalse
%<*example>
% \fi
\begin{exg}{$\backslash$sortArray with |arraysortcomparenum|}\begin{LTXexample}
\newarray{A}
\readarray{A}{78&4&85&1&28&6}
\sortArray[arraysortcomparenum]{6}{A}
\A(1) \A(2) \A(3) \A(4) \A(5) \A(6)
\end{LTXexample}\end{exg}
% \iffalse
%</example>
% \fi
% The |arraysortcomparenum| comparator is passed as the first optional
% argument; this option sorts by numerical order in the intuitive
% way --- but it will error if a value in the array is not a number.
%
% This option requires additional package options; see section below.
%
% \subsection*{Sorting part of an array}
%
% A second optional argument is accepted for the start of the range to
% be sorted. So you can easily sort only a segment of an array:
% \iffalse
%<*example>
% \fi
\begin{exg}{$\backslash$sortArray with range}\begin{LTXexample}
\newarray{A}
\readarray{A}{P&Y&F&G&%
A&O&E&U&I&D&H&T&N&S&%
Q&J&K&X&B&M&W&V&Z}
\sortArray[arraysortcomparestr][8]{21}{A}
\A(1)\A(2)\A(3)\A(4)\A(5)\A(6)\A(7)%
\textit{\A(8)\A(9)\A(10)\A(11)\A(12)%
\A(13)\A(14)\A(15)\A(16)}\A(17)\A(18)%
\A(19)\A(20)\A(21)\A(22)\A(23)
\end{LTXexample}\end{exg}
% \iffalse
%</example>
% \fi
% The start of the range must be the second optional parameter, so you
% need to specify the comparator as well. The default comparator is
% |arraysortcomparestr| as shown here.
%
% The example shows sorting the italicised region of 8--21 letters,
% originally arranged in the relatively jumbled order of the Dvorak
% keyboard.
%
% \subsection*{Sorting by Custom Order}
%
% While it is useful to sort an array into numbers or alphabetically,
% it is possible to sort an array into any order. To do this, you need
% to write a \textit{comparator}; this is a macro that is passed 2
% values from the array and evaluates which should appear first.
%
% A custom comparotor macro can be passed by appending its name as the
% optional argument is passed at the end of the |\sortarray| macro
% call.
%
% Your comparator macro must set the value of two toggles:
%
% \DescribeMacro{arraysortresult}
% Set |arraysortresult| to true if the first parameter is less than
% the second (\textit{ie} if the parameters are presented in sorted
% order).
%
% \DescribeMacro{arraysortresequal}
% |arraysortresequal| should be set by a comparator if both values are
% equal. It is not necessary to set |arraysortresult| if
% |arraysortresequal| is set to true.
%
% Both toggles can be set using the macros |\toggletrue{|\textit{togglename}|}|
% and |\togglefalse{|\textit{togglename}|}| defined in the |etoolbox|
% package, where \textit{togglename} is the name of the toggle to be
% set or cleared.
%
% The name of the comparator is passed to the sort algorithm as the
% first optional parameter; the leading $\backslash$ should be
% omitted.
%
% \iffalse
%<*example>
% \fi
\begin{exg}{$\backslash$sortArray with custom comparator}\begin{LTXexample}
\newcommand{\cmpnumbersfirst}[2]{%
\edef\cmpA{#1}%
\edef\cmpB{#2}%
\if\IsPositive{\cmpA}%
\if\IsPositive{\cmpB}%
\arraysortcomparenum{\cmpA}{\cmpB}%
\else%
\togglefalse{arraysortresequal}%
\toggletrue{arraysortresult}%
\fi%
\else%
\if\IsPositive{\cmpB}%
\togglefalse{arraysortresequal}%
\togglefalse{arraysortresult}%
\else%
\arraysortcomparestr{\cmpA}{\cmpB}%
\fi%
\fi%
}
\newarray{A}
\readarray{A}{apple&2&rabbits&12&-4}
\sortArray[cmpnumbersfirst]{5}{A}
\A(1) \A(2) \A(3) \A(4) \A(5)
\end{LTXexample}\end{exg}
% \iffalse
%</example>
% \fi
% This example uses the following definition of |\IsPositive| from
% the |cite| package\footnote{See
% \texttt{http://www.tex.ac.uk/cgi-bin/texfaq2html?label=isitanum}}
%
% \begin{verbatim}
% \def\IsPositive#1{%
% TT\fi
% \ifcat_\ifnum0<0#1 _\else A\fi
% }
% \end{verbatim}
%
% This custom sort places positive integers first, in numerical order,
% then everything else in default order.
%
% The |\cmpnumbersfirst| macro tests each parameter to see if is a
% positive number. If both parameters are positive integers, then it delegates
% to the |arraysortcomparenum| macro so that integers are sorted in
% sequence. If both parameters are not positive integers then the
% default sort is used. Otherwise, |arraysortresult| is set to true if
% |#1| is a positive integer and |#2| is not, or false if it is the
% other way around; this guarantees that positive numbers are sorted first.
%
% \textsc{tip:} Most comparators will fully expand their arguments
% only once per comparison, to ensure that the sorting order remains
% appropriate. That is the reason for the |\edef| in the above
% example, which expands and copies the parameter into a temporary
% macro. This is useless when passing individual string arguments, as
% in this example, but prevents unstable behaviour when arguments
% could change when reevaluated, such as when a macro contains the
% current time or a pseudorandom value.
%
% \subsection*{Changing the Partitioning Scheme}
%
% The partitioning scheme does not affect the final sorting order
% (unless you write your own that does not use the comparator argument)
% but may affect how long it takes \LaTeX\ to sort your array. In
% general it is recommended to use the default scheme, unless you are
% sorting a very large array and find the
% performance is unacceptable.
%
% To change the partitioning scheme, an optional argument can be added
% to the end of the |\sortArray| macro, thus:
% \iffalse
%<*example>
% \fi
\begin{exg}{$\backslash$sortArray with custom
partition}\begin{LTXexample}
\newarray{A}
\readarray{A}{e&d&c&b&a}
\sortArray{5}{A}%
[sortArrayPartitionRand]
\A(1) \A(2) \A(3) \A(4) \A(5)
\end{LTXexample}\end{exg}
% \iffalse
%</example>
% \fi
% Here, the writer of the package knows that $A$ is not randomised
% before it is sorted, so uses the |sortArrayPartitionRand| to
% partition the array at random. This avoids the worst-case
% performance of the sorting algorithm.
%
% The performance of each partitioning method is discussed in detail
% where it is defined; you should also read the section on the
% in-place quick-sort algorithm to understand the purpose of each
% algorithm.
%
% The partition name is just the name of a macro, so you can easily
% write your own. It must take four parameters:
% \begin{enumerate}
% \item The name of a comparator macro, described above
% \item The start index (inclusive) of the array segment to be partitioned
% \item The end index (inclusive) of the array segment to be
% partitioned
% \item The name of the array to be partitioned
% \end{enumerate}
%
% The macro should generate no output as it may be called multiple
% times with different array segments to partition. It should set
% |arraysort@partpos| to the current value of the partition element.
%
% Values that are equal to the partition value may be sorted into
% either segment. A sorting algorithm that retains the relative order
% of equal values is known as a \textit{stable sorting algorithm}; if
% this is required, then the partitioning algorithm must
% retain the relative position of each element in each sub-array,
% not just those which are equal to the pivot. \textbf{The supplied
% partitioning algorithms make no claim to be a stable sort},
% and stable sort semantics of the partitioning algorithm should
% \textbf{not be relied on for future versions}.
%
% In general, it is sufficient to identify the partition element
% within the array and swap it with the first element, then use
% |\sortArrayPartitionFirst|
%
% \textsc{Note}: It is important to ensure that all elements are
% expanded only once during the partition, as it is theoretically
% possible for a macro to expand to different values each time it is
% expanded.
%
% \subsection*{All Package Options}
%
% Package options are passed on the |\usepackage| line near the top of
% your document. A comma-separated list may be supplied, like this:
%
% \verb!\usepackage[comparestr,comparenum,randompart]{arraysort}!
%
% \DescribeMacro{comparestr}
% The |comparestr| option requires the |pdftexcmds| package to be
% installed and to run |pdflatex|. It is currently the default sort
% option, so you must either supply the |comparestr| option or specify
% a comparator explicitly.
%
% \DescribeMacro{comparenum}
% The |comparenum| option defines the |arraysortcomparenum|
% comparator, which allows you to sort arrays comparing numbers by
% numeric value instead of by name.
%
% \DescribeMacro{randompart}
% The |randompart| macro requires the |lcg| package to be
% installed. It defines the |sortArrayPartitionRand| option to
% partition arrays using a pseudorandom sequence.
% This option repeatedly calls |\reinitrand|, which resets the value
% of the pseudorandom sequence as well as the maximum and minimum
% values generated, so you should take care if using the |lcg| package
% outwith this package. At minimum, you should call |\reinitrand|
% yourself after every sort, and possibly within macros if |\rand| is
% used. Be aware that this will output whitespace unless care is taken
% to consume it before it is output. |lcg| will output warnings about
% reusing an existing counter; these can be safely ignored as
% |sortArrayPartitionRand| intentionally reuses the counter to prevent
% exhaustion of counters with large sorts.
%
% \pagebreak
% \section{Method: The In-Place Quick-Sort Algorithm}
%
% Quick-sort is a practical example of a recursive algorithm.
%
% \subsubsection*{Definition of terms:}
%
% \begin{description}
% \item[Partition] A single element from the array.
% \item[Segment] A contiguous group of elements from the array.
% \end{description}
%
% The general approach is to divide the array into two smaller arrays,
% then sort each smaller array in turn.
%
% The inital array segment is the entire array.
%
% The basic steps are:
%
% \begin{enumerate}
% \item Determine $A_P$, the index of the partition element within the
% current array segment. In practice, this must be done in constant
% time~[$O(1)$] or the sort becomes slow.
% \item Partition the array into two array segments, separated by a
% partition, in linear time~[$O(N)$].
% \item Quick-sort the first array segment
% \item Quick-sort the second array segment
% \end{enumerate}
%
% The first step is choosing the partition element, $A_P$. This may be
% any element from the array segment, although the fastest results are
% achieved by selecting the median value. Many algorithms exist to
% perform this ``best guess''.
%
% The next step is partitioning. Other than the partition element,
% every element in the array is iterated over in turn. Any value less
% than the partition value~$P$ is moved to the left of the partition
% (lower index than $A_P$), and any value greater than the partition
% is moved to its right (higher index than $A_P$).
%
% So, if there are $N$ elements in an array~$A$, the original array is
% given by:
% \begin{eqnarray*}
% & A_0 \dots A_n &
% \end{eqnarray*}
%
% After the partitioning stage, the partitioned array is given by:
% \begin{eqnarray*}
% & A_0 \dots A_{(P-1)} , A_P , A_{(P+1)} \dots A_N &
% \end{eqnarray*}
% where $A_P$ is the partition and $P$ is the index of the
% partition.
%
% $A_0 \dots A_{(P-1)}$ defines the first array segment to be
% sorted and $A_{(P+1)} \dots A_N$ defines the second.
%
% Each array segment is considered to be sorted if it contains one
% element or less; otherwise, each are presented to the entire
% quick-sort algorithm to be sorted.
%
% Each iteration through the algorithm divides the array into smaller
% segments, each of which is always sorted relative to the other
% segments. Once the segment size is as small as one element, the
% entire array is sorted.
%
% \section{Possible Future Improvements}
%
% \begin{itemize}
% \item It should be possible to sort macro contents by their
% unexpanded values
% \item It may also be possible to sort macro contents in a
% case-insensitive manner (depending on language). Note that sorting
% mixed-language, mixed-alphabet content in a standard-complient
% manner is not always possible.
% \item Further speed improvemnts are possible; in particular, it is
% often faster to defer to a lower-overhead $O(n^2)$ sorting algorithm
% when the number of array segment elements is smaller than some threshold
% value (quick-sort is inefficient at sorting small arrays, but
% often produces many of them to be sorted).
% \item More sorting and partitining options. I am undecided about
% passing options \textit{versus}\ simply defining multiple macros;
% certainly the chance of a name collision is very small with the
% naming convention used so far.
% \item Support partition values not in the array:
% \end{itemize}
%
% \noindent Some implementations of quicksort allow for a partition value $P$
% that does not correspond to a value in the array, divding the array
% into:
% \begin{eqnarray*}s
% & A_0 \dots\/A_i , A_{(i+1)} \dots\ A_N &
% \end{eqnarray*}
% \noindent where $i$ is arbitrary. This is usually less efficient, as there is
% an additional value to be sorted with each iteration and hence a
% greater number of iterations in the best case.
%
% In some cases, it is not possible to know the best partition value
% within an array segment, or a single partition may not be applicable
% (such as an array containing only two distinct values); however,
% there may be some knowledge of the array's distribution. In the best
% case, a pre-calculated median of the array's contents might already be
% available prior to sorting, which would be the ideal partition value
% for the first iteration but would be unlikely to be a value in the
% array, let alone a value of known position.
%
% This would likely require significant changes to the algorithm.
%
% \ifexcludelongtest\else
% \section{Large-Scale Sorting}
%
%
% \makeatletter
% \iffalse
%<*example>
% \fi
\begin{exg}{$\backslash$sortArray on a large
scale}\begin{LTXexample}
\newarray{A}
\expandarrayelementtrue
\reinitrand[counter=rand,quiet=y]
\newcommand{\asize}{10000}
\multido{\i=1+1}{\asize}{
\rand
\A(\i)={\arabic{rand}}
}
\textbf{Before sort:}
\multido{\i=1+1}{50}{
\A(\i)
}\dots
\sortArray[arraysortcomparenum]{%
\asize}{A}
\line(1,0){100}
\textbf{After sort:}
\multido{\i=1+1}{50}{
\A(\i)
}\dots
\end{LTXexample}
This example uses the |multido| and |lcg| packages\end{exg}
% \iffalse
%</example>
% \fi
% \fi
%
% \section{Implementation}
%\StopEventually{\PrintChanges \pagebreak[4] \PrintIndex}
%
% \begin{macro}{\arraysort@extrapkgs}
% The \LaTeX\ package-option support does not allow conditional
% includes of packages. So, instead, we build up the required
% |\RequiresPackage| statements inside the |\arraysort@extrapkgs|
% macro.
% \begin{macrocode}
\newcommand*{\arraysort@extrapkgs}{}
% \end{macrocode}
% \end{macro}
%
% \begin{macro}{comparestr}
% \begin{macrocode}
\DeclareOption{comparestr}{
\g@addto@macro{\arraysort@extrapkgs}{
\RequirePackage{pdftexcmds}% for comparison. TODO: use compare.sty optionally
}
% \end{macrocode}
% \begin{macro}{\arraysortcomparestr}
% Called with two arguments, guaranteed to be re-evaluatable.
% must set arraysortresequal if arguments are considered equal, otherwise
% must set arraysortresult true if |#2| is to be sorted after |#1|, otherwise
% must set both flags false.
%
% Basic ASCII-like comparison
% \begin{macrocode}
\newcommand*{\arraysortcomparestr}[2]{%
\protected@edef\arraysort@left{#1}%
\protected@edef\arraysort@right{#2}%
\arraysort@comparestr%
}
% \end{macrocode}
%
% The following macro performs the comparison. The parameters must (it
% seems) be passed by macro as passing by parameter |#1| and |#2| did
% not cause the expected results, hence the extra macro.
% \begin{macrocode}
\newcommand*{\arraysort@comparestr}{%
\protected@edef\arraysort@compresult{\pdf@strcmp{\arraysort@left}{\arraysort@right}}%
\ifthenelse{\equal{\arraysort@compresult}{0}}{%
\toggletrue{arraysortresequal}%
}{%
\togglefalse{arraysortresequal}%
\ifthenelse{\equal{\arraysort@compresult}{-1}}{%
\toggletrue{arraysortresult}% #2 > #1
}{%
\togglefalse{arraysortresult}% #2 < #1
}%
}%
}
}
% \end{macrocode}
% \end{macro}
% \end{macro}
% \begin{macro}{comparenum}
% \begin{macrocode}
% Numeric comparison, as |\arraysortcomparestr| but used with arrays compairng numbers
\DeclareOption{comparenum}{
% \end{macrocode}
% \begin{macro}{\arraysortcomparenum}
% \begin{macrocode}
\newcommand*{\arraysortcomparenum}[2]{%
\ifthenelse{\equal{#1}{#2}}{%
\toggletrue{arraysortresequal}%
}{%
\togglefalse{arraysortresequal}%
\ifthenelse{#2 > #1}{%
\toggletrue{arraysortresult}%
}{%
\togglefalse{arraysortresult}%
}%
}%
}
}
% \end{macrocode}
% \end{macro}
% \end{macro}
%
% All partitioning algorithms should complete in O(1) time; that is,
% they should not iterate over the array, or do anything that takes
% longer the more elements there are.
%
% \begin{macro}{\sortArrayPartitionMed}
%
% Partition the segment consisting of indexes |#2|--|#3| (inclusive)
% of array named |#4|, using comparator |#1|
%
% Use the median of the first, last and middle values. While this has
% extra overhead compared to sortArrayPartitionFirst, it is guaranteed
% to avoid the worst-case performance of that method. If the array is
% randomly shuffled prior to sorting, this usually offers the best
% performance. This is the default method.
%
% Performance depends on the comparison macro.
%
% May not work well if there are many duplicate values.
% \begin{macrocode}
\newcommand*{\sortArrayPartitionMed}[4]{%
\setcounter{arraysort@temp1}{(#2 + #3) / 2}%
\edef\arraysort@midpos{\arabic{arraysort@temp1}}%
\testarray{#4}(#2)\protected@edef\arraysort@left{\temp@macro}%
\testarray{#4}(\arraysort@midpos)\protected@edef\arraysort@mid{\temp@macro}%
\testarray{#4}(#3)\protected@edef\arraysort@right{\temp@macro}%
\csname#1\endcsname{\arraysort@left}{\arraysort@mid}%
\iftoggle{arraysortresequal}{%
% \end{macrocode}
% left $=$ mid
% if any two are the same, there can be no median, so may as well
% leave alone
% \begin{macrocode}
}{%
% \end{macrocode}
% left $\ne$ mid
% \begin{macrocode}
\iftoggle{arraysortresult}{%
% \end{macrocode}
% left $<$ mid
% \begin{macrocode}
\csname#1\endcsname{\arraysort@left}{\arraysort@right}%
\iftoggle{arraysortresequal}{%
% \end{macrocode}
% $(\mbox{left} = \mbox{right}) < \mbox{mid}$
% \begin{macrocode}
}{%
\iftoggle{arraysortresult}{%
% \end{macrocode}
% left $<$ mid, left $<$ right
% \begin{macrocode}
\csname#1\endcsname{\arraysort@mid}{\arraysort@right}%
\iftoggle{arraysortresequal}{%
% \end{macrocode}
% $\mbox{left} < (\mbox{mid} = \mbox{right})$
% \begin{macrocode}
}{%
\iftoggle{arraysortresult}{%
% \end{macrocode}
% $\mbox{left} < \mbox{mid} < \mbox{right}$
% \begin{macrocode}
\arraysort@swap{#4}{#2}{\arraysort@midpos}%
}{%
% \end{macrocode}
% $\mbox{left} < \mbox{right} < \mbox{mid}$
% \begin{macrocode}
\arraysort@swap{#4}{#2}{#3}%
}%
}%
}{%
% \end{macrocode}
% left $<$ mid, left $>$ right
%
% left is already in the middle; leave alone
% \begin{macrocode}
}%
}%
}{%
% \end{macrocode}
% left $>$ mid
% \begin{macrocode}
\csname#1\endcsname{\arraysort@mid}{\arraysort@right}%
\iftoggle{arraysortresequal}{%
% \end{macrocode}
% $\mbox{left} > (\mbox{mid} = \mbox{right})$
% \begin{macrocode}
}{%
\iftoggle{arraysortresult}{%
% \end{macrocode}
% $\mbox{left} > \mbox{right} > \mbox{mid}$
% \begin{macrocode}
\arraysort@swap{#4}{#2}{#3}%
% \end{macrocode}
% swap right \& left, so left is median
% \begin{macrocode}
}{%
% \end{macrocode}
% $\mbox{left} > \mbox{mid} > \mbox{right}$
%
% swap right \& mid, so left is median
% \begin{macrocode}
\arraysort@swap{#4}{#2}{\arraysort@midpos}%
}%
}%
}%
}%
\sortArrayPartitionFirst{#1}{#2}{#3}{#4}%
}
% \end{macrocode}
%
% \begin{macro}{\sortArrayPartitionRand}
%
% Partition the sub-array
% consisting of indexes |#2|--|#3| (inclusive) of array named |#4|,
% using comparator |#1|
%
% Use the lcg package to generate a (pseudo)-random partition
% value. This should perform reasonably well most of the time, and you
% can simply re-run LaTeX if the performance is unacceptable.
%
% Caution: this macro will re-initialise the LCG package.
% \begin{macro}{randompart}
% \begin{macrocode}
\DeclareOption{randompart}{
\g@addto@macro{\arraysort@extrapkgs}{
% \end{macrocode}
% Store for later execution the fact that we will need tho |lcg| package
% for random numbers
% \begin{macrocode}
\RequirePackage[quiet]{lcg}
}
\newcommand*{\sortArrayPartitionRand}[4]{%
% \end{macrocode}
% It is necessary to change the start and end values of the sequence; the only way
% to do this is by reinitialising |lcg|. There are 2 possible
% problems; firstly, reinitrand outputs whitespace; and secondly it
% prints out a warning about a re-used counter. It's actually best to re-use
% the counter, but there's no way to silence the warning.
% \begin{macrocode}
\reinitrand[counter=arraysort@temp1,first=#2,last=#3,quiet=y]%
\rand%
\arraysort@swap{#4}{#2}{\arabic{arraysort@temp1}}%
\sortArrayPartitionFirst{#1}{#2}{#3}{#4}%
}
}
% \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\sortArrayPartitionMid}
%
% Partition the sub-array
% consisting of indexes |#2|--|#3| (inclusive) of array named |#4|,
% using comparator |#1|
%
% This implementation uses the middle value in the array segment. This is
% generally the best option if you don't know anything about the
% array's contents; in particular, it offers reasonable speed when
% attempting to re-sort previously-sorted ararys.
% \begin{macrocode}
\newcommand*{\sortArrayPartitionMid}[4]{%
\setcounter{arraysort@temp1}{(#2 + #3) / 2}%
\arraysort@swap{#4}{#2}{\arabic{arraysort@temp1}}%
\sortArrayPartitionFirst{#1}{#2}{#3}{#4}%
}
% \end{macrocode}
% \end{macro}
%
% \begin{macro}{\sortArrayPartitionFirst}
% Partition the array segment
% consisting of indexes |#2|--|#3| (inclusive) of array named |#4|,
% using comparator |#1|
%
% This implementation uses the first value in the array segment. This is
% fastest in theory, but only if the array is pre-shuffled. This has
% the worst performance when attempting to sort an already-sorted
% array.
% \begin{macrocode}
\newcommand*{\sortArrayPartitionFirst}[4]{%
\setcounter{arraysort@partpos}{#2}%
\setcounter{arraysort@temp1}{#2 + 1}%
\setcounter{arraysort@endpos}{#3 + 1}%
\arraysort@repeats{arraysort@temp1}{\value{arraysort@temp1}}{\value{arraysort@endpos}}{1}{%
\testarray{#4}(\arabic{arraysort@temp1})%
% \end{macrocode}
% if the value $A_{\mbox{temp1}}$ is less than partition $A_P$,
% decrement the partition counter by 1 and swap.
%
% |\let| copies without expanding:
% \begin{macrocode}
\let\arraysort@cur\temp@macro%
\testarray{#4}(\arabic{arraysort@partpos})%
% \end{macrocode}
% Expand the macros only once just in case they would be different
% on subsequent expansion:
% \begin{macrocode}
\protected@edef\arraysort@left{\arraysort@cur}%
\protected@edef\arraysort@right{\temp@macro}%
\csname#1\endcsname{\arraysort@left}{\arraysort@right}% #2 = cur, #3 = partition
\setcounter{arraysort@temp2}{\value{arraysort@partpos} + 1}%
\iftoggle{arraysortresequal}{% #2 = #3
% \end{macrocode}
% Must be moved before pivot
% Swap $A_P$ with $A_{P+1}$ then swap (the new) $A_P$ with
% current ($A_{\mbox{temp2}}=A_{P+1}$)
% \begin{macrocode}
\arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp2}}%
\arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp1}}%
% \end{macrocode}
% Increment partition; otherwise the next non-equal pivot will break
% \begin{macrocode}
\stepcounter{arraysort@partpos}%
}{%
\iftoggle{arraysortresult}{% #3 > #2
\ifthenelse{\equal{\arabic{arraysort@temp2}}{\arabic{arraysort@temp1}}}{%
% \end{macrocode}
% Just swap part with current value; they are adjacent
% \begin{macrocode}
\arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp1}}%
}{%
% \end{macrocode}
% Swap $A_P$ with $A_{P+1}$ then swap (the new) $A_P$ with
% current ($\mbox{temp}_2=A_{p+1}$)
% \begin{macrocode}
\arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp2}}%
\arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp1}}%
}%
% \end{macrocode}
% Increment partition; one more in left array segment
% \begin{macrocode}
\stepcounter{arraysort@partpos}%
}{%
% \end{macrocode}
% $A_{|arraysort@cur|} > A_P$ and already after it; leave it alone
% \begin{macrocode}
}%
}%
}%
}
% \end{macrocode}
% \end{macro}
%
% \begin{macro}{\ProcessOptions}
% This processes the package include options, defining whichever of
% the above macros the user has asked for, and adding a list of any
% optional packages into |\arraysort@extrapkgs|.
%
% \begin{macrocode}
\ProcessOptions\relax
% \end{macrocode}
%\end{macro}
%
% Package includes for required packages:
%
% For loading the arrays that we will sort
% \begin{macrocode}
\RequirePackage{arrayjobx}
% \end{macrocode}
% For easier syntax on counter operations
% \begin{macrocode}
\RequirePackage{calc}
% \end{macrocode}
% For comparisons
% \begin{macrocode}
\RequirePackage{ifthen}
% \end{macrocode}
% Toggles etc.
% \begin{macrocode}
\RequirePackage{etoolbox}
% \end{macrocode}
% To declare macros with multiple optional arguments (\textit{ie}
% |\sortArray|)
% \begin{macrocode}
\RequirePackage{xargs}
% \end{macrocode}
% For partitioning
% \begin{macrocode}
\RequirePackage{macroswap}
% \end{macrocode}
% now process any conditional includes
% \begin{macrocode}
\arraysort@extrapkgs
% \end{macrocode}
%
% Now we are done including packages, so discard the macro:
% \begin{macrocode}
\let\arraysort@extrapkgs\relax
% \end{macrocode}
%
%
% \DescribeMacro{\sortArray}
% Sort the elements at index |#2|--|#3| of array named |#4|, using
% comparator |#1|.
%
% |#5| is the partitioning algorithm to use.
%
% \textit{eg} |\sortArray[1]{3}{ABC}|
%
% Defined using the |xargs| package
% \begin{macrocode}
\newcommandx*\sortArray[5][1=arraysortcomparestr,2=1,5=sortArrayPartitionMed]{%
\ifcsname#1\endcsname%
\ifthenelse{#2>0}{%
\ifthenelse{#3>#2}{%
\ifcsname total@#4\endcsname%
\arraysort@sort{#1}{#2}{#3}{#4}{#5}%
\else%
\PackageError{arraysort}{Cannot sort unknown array #4}{}%
\fi%
}{%
\PackageError{arraysort}{Cannot sort; to index #3 greater than from index #2}{}%
}%
}{%
\PackageError{arraysort}{Cannot sort; Invalid from index #2}{}%
}%
\else%
\PackageError{arraysort}{Cannot sort by undefined comparator #1}{}%
\fi%
}
% \end{macrocode}
% \end{macro}
%
% \begin{macro}{\arraysort@sort}
% As |\sortArray|, except that it doesn't validate its parameters,
% hence the |@| in the name (signifying an internal macro).
%
% Use with caution as error messages may be misleading.
%
% Sort the elements at index |#2|--|#3| of array named |#4|, using
% comparator |#1|
%
% |#5| is the partitioning algorithm to use.
% \begin{macrocode}
\newcommand*{\arraysort@sort}[5]{%
\csname#5\endcsname{#1}{#2}{#3}{#4}%
% \end{macrocode}
% Keep the position on the local stack!
% \begin{macrocode}
\edef\arraysort@partition{\value{arraysort@partpos}}%
\setcounter{arraysort@temp1}{\arraysort@partition - 1}%
\ifthenelse{#2 = \value{arraysort@temp1} \OR #2 > \value{arraysort@temp1}}{%
}{%
\edef\arraysort@to{\arabic{arraysort@temp1}}%
\arraysort@sort{#1}{#2}{\arraysort@to}{#4}{#5}%
}%
\setcounter{arraysort@temp1}{\arraysort@partition + 1}%
\ifthenelse{\value{arraysort@temp1} = #3 \OR #3 < \value{arraysort@temp1}}{%
}{%
\edef\arraysort@from{\arabic{arraysort@temp1}}%
\arraysort@sort{#1}{\arraysort@from}{#3}{#4}{#5}%
}%
}
% \end{macrocode}
% \end{macro}
%
%
% Counters used for sorting
%
% current position of the partition
% \begin{macrocode}
\newcounter{arraysort@partpos}
% \end{macrocode}
% current position in loop
% \begin{macrocode}
\newcounter{arraysort@temp1}
% \end{macrocode}
% partition position $+1$
% \begin{macrocode}
\newcounter{arraysort@temp2}
% \end{macrocode}
% used for partitioning
% \begin{macrocode}
\newcounter{arraysort@endpos}
% \end{macrocode}
%
% Toggles used by the comparator macro
%
% set by comparison if $|#1| < |#2|$
% \begin{macrocode}
\newtoggle{arraysortresult}
% \end{macrocode}
% set by comparison if $|#1| = |#2|$
% \begin{macrocode}
\newtoggle{arraysortresequal}
% \end{macrocode}
%
% \begin{macro}{\arrayort@repeats}
%
% Don't use |\whiledo| here because it uses up TeX's capacity,
% so rolling own basic repeat loop...
%
% For counter |#1| from |#2| to |#3| step |#4|, do |#5|
% \begin{macrocode}
\newcommand*{\arraysort@repeats}[5]{%
\setcounter{#1}{#2}%
\ifthenelse{\equal{\value{#1}}{#3}}{%
}{%
#5%
\addtocounter{#1}{#4}%
\arraysort@repeats{#1}{\arabic{#1}}{#3}{#4}{#5}%
}%
}
% \end{macrocode}
% \end{macro}
%
% \begin{macro}{\arraysort@swap}
% Globally swap array values |#1(#2)| with |#1(#3)|
%
% \textit{ie} \\ |#1| is the macro name \\
% |#2| and |#3| are the numeic indexes of the array elements to be
% swapped.
% \begin{macrocode}
\newcommand\arraysort@swap[3]{%
% \end{macrocode}
% |arrayjobx| does not provide a way to assign an array element to the
% contents of another element (or macro) without expanding it. This macro simply
% swaps the definitions of the two macros used internally by |arrayjobx|:
% \begin{macrocode}
\gmacroswap{#1#2\string~}{#1#3\string~}%
}
% \end{macrocode}
% \end{macro}
%
% That is all
% \Finale
\endinput