diff options
Diffstat (limited to 'Master/texmf-dist/source')
-rw-r--r-- | Master/texmf-dist/source/latex/arraysort/arraysort.dtx | 1061 | ||||
-rw-r--r-- | Master/texmf-dist/source/latex/arraysort/arraysort.ins | 53 |
2 files changed, 1114 insertions, 0 deletions
diff --git a/Master/texmf-dist/source/latex/arraysort/arraysort.dtx b/Master/texmf-dist/source/latex/arraysort/arraysort.dtx new file mode 100644 index 00000000000..a08b81ce620 --- /dev/null +++ b/Master/texmf-dist/source/latex/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/Master/texmf-dist/source/latex/arraysort/arraysort.ins b/Master/texmf-dist/source/latex/arraysort/arraysort.ins new file mode 100644 index 00000000000..6ed0d7bbcbf --- /dev/null +++ b/Master/texmf-dist/source/latex/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 |