summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/arraysort
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/latex/contrib/arraysort
Initial commit
Diffstat (limited to 'macros/latex/contrib/arraysort')
-rw-r--r--macros/latex/contrib/arraysort/Makefile20
-rw-r--r--macros/latex/contrib/arraysort/README20
-rw-r--r--macros/latex/contrib/arraysort/arraysort.dtx1061
-rw-r--r--macros/latex/contrib/arraysort/arraysort.ins53
-rw-r--r--macros/latex/contrib/arraysort/arraysort.pdfbin0 -> 302651 bytes
5 files changed, 1154 insertions, 0 deletions
diff --git a/macros/latex/contrib/arraysort/Makefile b/macros/latex/contrib/arraysort/Makefile
new file mode 100644
index 0000000000..234ecfac7e
--- /dev/null
+++ b/macros/latex/contrib/arraysort/Makefile
@@ -0,0 +1,20 @@
+all: clean arraysort.pdf
+
+clean:
+ rm -f *.log *.bbl *.blg *.dvi *.glo *.idx *.ilg *.ind *.sty *.aux *.gls *.zip *.tmp *~;
+
+dist: clean
+ cd .. && zip -r arraysort/arraysort.zip arraysort/
+
+arraysort.sty : arraysort.ins arraysort.dtx
+ latex arraysort.ins
+
+arraysort.pdf : arraysort.sty arraysort.glo arraysort.ind
+ time pdflatex arraysort.dtx
+
+# Glossary contains the changelist(?)
+arraysort.glo : arraysort.dtx
+ pdflatex arraysort.dtx && makeindex -s gglo.ist -o arraysort.gls arraysort.glo
+
+arraysort.ind : arraysort.idx
+ makeindex -s gind.ist -o arraysort.ind arraysort.idx
diff --git a/macros/latex/contrib/arraysort/README b/macros/latex/contrib/arraysort/README
new file mode 100644
index 0000000000..a18ad2b728
--- /dev/null
+++ b/macros/latex/contrib/arraysort/README
@@ -0,0 +1,20 @@
+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.
+
+
+This archive provides the arraysort package, providing a mechanism to
+sort arrays (or sections of them) declared using the arrayjob package.
+
+
+
+This package uses the standard TeX ins+dtx install mechanism, althogh
+a UNIX Makefile is also provided for convenience to generate all files.
diff --git a/macros/latex/contrib/arraysort/arraysort.dtx b/macros/latex/contrib/arraysort/arraysort.dtx
new file mode 100644
index 0000000000..a08b81ce62
--- /dev/null
+++ b/macros/latex/contrib/arraysort/arraysort.dtx
@@ -0,0 +1,1061 @@
+% \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
diff --git a/macros/latex/contrib/arraysort/arraysort.ins b/macros/latex/contrib/arraysort/arraysort.ins
new file mode 100644
index 0000000000..6ed0d7bbcb
--- /dev/null
+++ b/macros/latex/contrib/arraysort/arraysort.ins
@@ -0,0 +1,53 @@
+%%
+%% 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.
+%
+\input docstrip.tex
+\keepsilent
+\usedir{tex/latex/arraysort}
+\preamble
+
+This is a generated file.
+
+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.
+
+\endpreamble
+
+\generate{\file{arraysort.sty}{\from{arraysort.dtx}{package}}}
+
+\obeyspaces
+
+\Msg{****************************************************}
+\Msg{* *}
+\Msg{* To finish the installation you have to move the *}
+\Msg{* following file into a directory searched by TeX: *}
+\Msg{* *}
+\Msg{* arraysort.sty *}
+\Msg{* *}
+\Msg{* To produce the documentation run the file *}
+\Msg{* arraysort.dtx through LaTeX. *}
+\Msg{* *}
+\Msg{* Happy TeXing! *}
+\Msg{* *}
+\Msg{****************************************************}
+
+\endbatchfile
diff --git a/macros/latex/contrib/arraysort/arraysort.pdf b/macros/latex/contrib/arraysort/arraysort.pdf
new file mode 100644
index 0000000000..c814817f8f
--- /dev/null
+++ b/macros/latex/contrib/arraysort/arraysort.pdf
Binary files differ