Debian Codegraph @

texmf-dist/source/latex/arraysort/arraysort.dtx

raw
1 % \iffalse meta-comment
2 %
3 % Copyright (C) 2013 by Robert J Lee
4 %
5 % This file may be distributed and/or modified under the
6 % conditions of the LaTeX Project Public License, either
7 % version 1.2 of this license or (at your option) any later
8 % version. The latest version of this license is in:
9 %
10 % http://www.latex-project.org/lppl.txt
11 %
12 % and version 1.2 or later is part of all distributions of
13 % LaTeX version 1999/12/01 or later.
14 %
15 % \fi
16 %
17 % \iffalse
18 %<package>\NeedsTeXFormat{LaTeX2e}[1999/12/01]
19 %<package>\ProvidesPackage{arraysort}
20 %<package> [2013/09/04 v1.0 sorting arrayjobx arrays]
21 %
22 %<*driver>
23 \documentclass{ltxdoc}
24 \usepackage[comparestr,comparenum,randompart]{arraysort}
25 \EnableCrossrefs
26 \usepackage{indentfirst}
27 \usepackage{showexpl}
28 \usepackage{multido}
29 \newbool{excludelongtest}
30 \setbool{excludelongtest}{true} % change to false for slow test
31 \CodelineIndex
32 \RecordChanges
33 \begin{document}
34 \DocInput{arraysort.dtx}
35 \end{document}
36 %</driver>
37 % \fi
38 %
39 % \CharacterTable
40 % {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
41 % 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
42 % Digits \0\1\2\3\4\5\6\7\8\9
43 % Exclamation \! Double quote \" Hash (number) \#
44 % Dollar \$ Percent \% Ampersand \&
45 % Acute accent \' Left paren \( Right paren \)
46 % Asterisk \* Plus \+ Comma \,
47 % Minus \- Point \. Solidus \/
48 % Colon \: Semicolon \; Less than \<
49 % Equals \= Greater than \> Question mark \?
50 % Commercial at \@ Left bracket \[ Backslash \\
51 % Right bracket \] Circumflex \^ Underscore \_
52 % Grave accent \` Left brace \{ Vertical bar \|
53 % Right brace \} Tilde \~}
54 %
55 % \CheckSum{236}
56 %
57 % \changes{v1.0}{2013/09/04}{Initial version}
58 %
59 % \GetFileInfo{arraysort.sty}
60 %
61 % \DoNotIndex{\let, \edef, \xdef, \relax, \newcommand}
62 % \DoNotIndex{\csname, \endcsname, \ifcsname}
63 % \DoNotIndex{\OR, \if, \else, \fi, \equal, \ifthenelse, \iftoggle}
64 % \DoNotIndex{\arabic, \addtocounter, \value, \setcounter, \stepcounter}
65 % \DoNotIndex{\g@addto@macro, \string}
66 %
67 %
68 %\def\IsPositive#1{% http://www.tex.ac.uk/cgi-bin/texfaq2html?label=isitanum
69 % TT\fi
70 % \ifcat_\ifnum0<0#1 _\else A\fi
71 %}
72 %
73 % \newenvironment{exg}[1]{\pagebreak[3]\begin{center}
74 % \line(1,0){250}
75 % \end{center}\nopagebreak~\par\nopagebreak\textit{Example:~~\texttt{#1}}\par\vspace{-1em}}{\begin{center}
76 % \line(1,0){250}
77 % \end{center}\delarray{A}\noindent}
78 %
79 % \title{The Arraysort Package\thanks{This document corresponds to \textsf{Arraysort}~\fileversion, dated \filedate.}}
80 % \author{Robert J Lee \\ [email protected]}
81 %
82 % \maketitle
83 %
84 % \begin{abstract}
85 %
86 % The |arraysort| package allows the user to sort an array (defined
87 % with the |arrayjobx| package), or a portion of such an array,
88 % without using external files or commands or requiring a second run
89 % of \LaTeX.
90 %
91 % Basic comparators are provided for sorting by ASCII-code or for
92 % sorting numeric values. Options to tweak performance of the sort are
93 % also provided, should they be needed.
94 %
95 % \end{abstract}
96 %
97 % \section*{Introduction}
98 %
99 % This package implements an in-place Quick Sort algorithm for
100 % \LaTeX. Quick-Sort is a recursive and highly configurable algorithm
101 % for sorting of arrays.
102 %
103 %
104 % \section{Usage}
105 %
106 % The |arraysort| package requires the |arrayjobx| package, which
107 % provides several methods to define an array of values. This docment
108 % assumes that you are familiar with |arrayjobx|. A number of examples
109 % are provided to sort a small array named $A$; the package can sort
110 % much larger arrays than those shown including arrays whose contents
111 % are stored unexpanded (although they will be expanded when comparing
112 % them using the provided comparators).
113 %
114 % \subsection*{Sorting by Text}
115 %
116 % \DescribeMacro{\sortArray}
117 %
118 % To sort the first |10| elemnets of $A$, you can simply write:
119 % |\sortArray{|10|}{|$A$|}|
120 %
121 % |\sortArray| takes two mandatory parameters: the first is the
122 % number of elements to sort, the second is the name of the array.
123 %
124 % \iffalse
125 %<*example>
126 % \fi
127 \begin{exg}{$\backslash$sortArray with words}\begin{LTXexample}
128 \newarray{A}
129 \readarray{A}{The&Quick&Brown&%
130 Fox&Jumps&Over&the&Lazy&Dog}
131 \sortArray{9}{A}
132 \A(1) \A(2) \A(3) \A(4) \A(5)
133 \A(6) \A(7) \A(8) \A(9)
134 \end{LTXexample}\end{exg}
135 % \iffalse
136 %</example>
137 % \fi
138 % Note that the default is to sort by character code order, so the
139 % lower-case ``the'' is sorted after the words starting with
140 % upper-case letters. This is a limitation of the default sorting
141 % method, but other ways of sorting are possible.
142 %
143 % \subsection*{Sorting Numbers}
144 %
145 % The default sorting method can have surprising results when sorting
146 % arrays of numbers:
147 % \iffalse
148 %<*example>
149 % \fi
150 \begin{exg}{$\backslash$sortArray with numbers}\begin{LTXexample}
151 \newarray{A}
152 \readarray{A}{78&4&85&1&28&6}
153 \sortArray{6}{A}
154 \A(1) \A(2) \A(3) \A(4) \A(5) \A(6)
155 \end{LTXexample}\end{exg}
156 % \iffalse
157 %</example>
158 % \fi
159 % Here, the numbers are still sorted in dictionary order,
160 % which was probably not the intent, as the number~28 would usually be
161 % sorted after the number~6, even though the first digit of~28 is
162 % smaller than the first digit of~6.
163 %
164 % To solve this problem, an alternative comparator can be used:
165 % \iffalse
166 %<*example>
167 % \fi
168 \begin{exg}{$\backslash$sortArray with |arraysortcomparenum|}\begin{LTXexample}
169 \newarray{A}
170 \readarray{A}{78&4&85&1&28&6}
171 \sortArray[arraysortcomparenum]{6}{A}
172 \A(1) \A(2) \A(3) \A(4) \A(5) \A(6)
173 \end{LTXexample}\end{exg}
174 % \iffalse
175 %</example>
176 % \fi
177 % The |arraysortcomparenum| comparator is passed as the first optional
178 % argument; this option sorts by numerical order in the intuitive
179 % way --- but it will error if a value in the array is not a number.
180 %
181 % This option requires additional package options; see section below.
182 %
183 % \subsection*{Sorting part of an array}
184 %
185 % A second optional argument is accepted for the start of the range to
186 % be sorted. So you can easily sort only a segment of an array:
187 % \iffalse
188 %<*example>
189 % \fi
190 \begin{exg}{$\backslash$sortArray with range}\begin{LTXexample}
191 \newarray{A}
192 \readarray{A}{P&Y&F&G&%
193 A&O&E&U&I&D&H&T&N&S&%
194 Q&J&K&X&B&M&W&V&Z}
195 \sortArray[arraysortcomparestr][8]{21}{A}
196 \A(1)\A(2)\A(3)\A(4)\A(5)\A(6)\A(7)%
197 \textit{\A(8)\A(9)\A(10)\A(11)\A(12)%
198 \A(13)\A(14)\A(15)\A(16)}\A(17)\A(18)%
199 \A(19)\A(20)\A(21)\A(22)\A(23)
200 \end{LTXexample}\end{exg}
201 % \iffalse
202 %</example>
203 % \fi
204 % The start of the range must be the second optional parameter, so you
205 % need to specify the comparator as well. The default comparator is
206 % |arraysortcomparestr| as shown here.
207 %
208 % The example shows sorting the italicised region of 8--21 letters,
209 % originally arranged in the relatively jumbled order of the Dvorak
210 % keyboard.
211 %
212 % \subsection*{Sorting by Custom Order}
213 %
214 % While it is useful to sort an array into numbers or alphabetically,
215 % it is possible to sort an array into any order. To do this, you need
216 % to write a \textit{comparator}; this is a macro that is passed 2
217 % values from the array and evaluates which should appear first.
218 %
219 % A custom comparotor macro can be passed by appending its name as the
220 % optional argument is passed at the end of the |\sortarray| macro
221 % call.
222 %
223 % Your comparator macro must set the value of two toggles:
224 %
225 % \DescribeMacro{arraysortresult}
226 % Set |arraysortresult| to true if the first parameter is less than
227 % the second (\textit{ie} if the parameters are presented in sorted
228 % order).
229 %
230 % \DescribeMacro{arraysortresequal}
231 % |arraysortresequal| should be set by a comparator if both values are
232 % equal. It is not necessary to set |arraysortresult| if
233 % |arraysortresequal| is set to true.
234 %
235 % Both toggles can be set using the macros |\toggletrue{|\textit{togglename}|}|
236 % and |\togglefalse{|\textit{togglename}|}| defined in the |etoolbox|
237 % package, where \textit{togglename} is the name of the toggle to be
238 % set or cleared.
239 %
240 % The name of the comparator is passed to the sort algorithm as the
241 % first optional parameter; the leading $\backslash$ should be
242 % omitted.
243 %
244 % \iffalse
245 %<*example>
246 % \fi
247 \begin{exg}{$\backslash$sortArray with custom comparator}\begin{LTXexample}
248 \newcommand{\cmpnumbersfirst}[2]{%
249 \edef\cmpA{#1}%
250 \edef\cmpB{#2}%
251 \if\IsPositive{\cmpA}%
252 \if\IsPositive{\cmpB}%
253 \arraysortcomparenum{\cmpA}{\cmpB}%
254 \else%
255 \togglefalse{arraysortresequal}%
256 \toggletrue{arraysortresult}%
257 \fi%
258 \else%
259 \if\IsPositive{\cmpB}%
260 \togglefalse{arraysortresequal}%
261 \togglefalse{arraysortresult}%
262 \else%
263 \arraysortcomparestr{\cmpA}{\cmpB}%
264 \fi%
265 \fi%
266 }
267 \newarray{A}
268 \readarray{A}{apple&2&rabbits&12&-4}
269 \sortArray[cmpnumbersfirst]{5}{A}
270 \A(1) \A(2) \A(3) \A(4) \A(5)
271 \end{LTXexample}\end{exg}
272 % \iffalse
273 %</example>
274 % \fi
275 % This example uses the following definition of |\IsPositive| from
276 % the |cite| package\footnote{See
277 % \texttt{http://www.tex.ac.uk/cgi-bin/texfaq2html?label=isitanum}}
278 %
279 % \begin{verbatim}
280 % \def\IsPositive#1{%
281 % TT\fi
282 % \ifcat_\ifnum0<0#1 _\else A\fi
283 % }
284 % \end{verbatim}
285 %
286 % This custom sort places positive integers first, in numerical order,
287 % then everything else in default order.
288 %
289 % The |\cmpnumbersfirst| macro tests each parameter to see if is a
290 % positive number. If both parameters are positive integers, then it delegates
291 % to the |arraysortcomparenum| macro so that integers are sorted in
292 % sequence. If both parameters are not positive integers then the
293 % default sort is used. Otherwise, |arraysortresult| is set to true if
294 % |#1| is a positive integer and |#2| is not, or false if it is the
295 % other way around; this guarantees that positive numbers are sorted first.
296 %
297 % \textsc{tip:} Most comparators will fully expand their arguments
298 % only once per comparison, to ensure that the sorting order remains
299 % appropriate. That is the reason for the |\edef| in the above
300 % example, which expands and copies the parameter into a temporary
301 % macro. This is useless when passing individual string arguments, as
302 % in this example, but prevents unstable behaviour when arguments
303 % could change when reevaluated, such as when a macro contains the
304 % current time or a pseudorandom value.
305 %
306 % \subsection*{Changing the Partitioning Scheme}
307 %
308 % The partitioning scheme does not affect the final sorting order
309 % (unless you write your own that does not use the comparator argument)
310 % but may affect how long it takes \LaTeX\ to sort your array. In
311 % general it is recommended to use the default scheme, unless you are
312 % sorting a very large array and find the
313 % performance is unacceptable.
314 %
315 % To change the partitioning scheme, an optional argument can be added
316 % to the end of the |\sortArray| macro, thus:
317 % \iffalse
318 %<*example>
319 % \fi
320 \begin{exg}{$\backslash$sortArray with custom
321 partition}\begin{LTXexample}
322 \newarray{A}
323 \readarray{A}{e&d&c&b&a}
324 \sortArray{5}{A}%
325 [sortArrayPartitionRand]
326 \A(1) \A(2) \A(3) \A(4) \A(5)
327 \end{LTXexample}\end{exg}
328 % \iffalse
329 %</example>
330 % \fi
331 % Here, the writer of the package knows that $A$ is not randomised
332 % before it is sorted, so uses the |sortArrayPartitionRand| to
333 % partition the array at random. This avoids the worst-case
334 % performance of the sorting algorithm.
335 %
336 % The performance of each partitioning method is discussed in detail
337 % where it is defined; you should also read the section on the
338 % in-place quick-sort algorithm to understand the purpose of each
339 % algorithm.
340 %
341 % The partition name is just the name of a macro, so you can easily
342 % write your own. It must take four parameters:
343 % \begin{enumerate}
344 % \item The name of a comparator macro, described above
345 % \item The start index (inclusive) of the array segment to be partitioned
346 % \item The end index (inclusive) of the array segment to be
347 % partitioned
348 % \item The name of the array to be partitioned
349 % \end{enumerate}
350 %
351 % The macro should generate no output as it may be called multiple
352 % times with different array segments to partition. It should set
353 % |arraysort@partpos| to the current value of the partition element.
354 %
355 % Values that are equal to the partition value may be sorted into
356 % either segment. A sorting algorithm that retains the relative order
357 % of equal values is known as a \textit{stable sorting algorithm}; if
358 % this is required, then the partitioning algorithm must
359 % retain the relative position of each element in each sub-array,
360 % not just those which are equal to the pivot. \textbf{The supplied
361 % partitioning algorithms make no claim to be a stable sort},
362 % and stable sort semantics of the partitioning algorithm should
363 % \textbf{not be relied on for future versions}.
364 %
365 % In general, it is sufficient to identify the partition element
366 % within the array and swap it with the first element, then use
367 % |\sortArrayPartitionFirst|
368 %
369 % \textsc{Note}: It is important to ensure that all elements are
370 % expanded only once during the partition, as it is theoretically
371 % possible for a macro to expand to different values each time it is
372 % expanded.
373 %
374 % \subsection*{All Package Options}
375 %
376 % Package options are passed on the |\usepackage| line near the top of
377 % your document. A comma-separated list may be supplied, like this:
378 %
379 % \verb!\usepackage[comparestr,comparenum,randompart]{arraysort}!
380 %
381 % \DescribeMacro{comparestr}
382 % The |comparestr| option requires the |pdftexcmds| package to be
383 % installed and to run |pdflatex|. It is currently the default sort
384 % option, so you must either supply the |comparestr| option or specify
385 % a comparator explicitly.
386 %
387 % \DescribeMacro{comparenum}
388 % The |comparenum| option defines the |arraysortcomparenum|
389 % comparator, which allows you to sort arrays comparing numbers by
390 % numeric value instead of by name.
391 %
392 % \DescribeMacro{randompart}
393 % The |randompart| macro requires the |lcg| package to be
394 % installed. It defines the |sortArrayPartitionRand| option to
395 % partition arrays using a pseudorandom sequence.
396 % This option repeatedly calls |\reinitrand|, which resets the value
397 % of the pseudorandom sequence as well as the maximum and minimum
398 % values generated, so you should take care if using the |lcg| package
399 % outwith this package. At minimum, you should call |\reinitrand|
400 % yourself after every sort, and possibly within macros if |\rand| is
401 % used. Be aware that this will output whitespace unless care is taken
402 % to consume it before it is output. |lcg| will output warnings about
403 % reusing an existing counter; these can be safely ignored as
404 % |sortArrayPartitionRand| intentionally reuses the counter to prevent
405 % exhaustion of counters with large sorts.
406 %
407 % \pagebreak
408 % \section{Method: The In-Place Quick-Sort Algorithm}
409 %
410 % Quick-sort is a practical example of a recursive algorithm.
411 %
412 % \subsubsection*{Definition of terms:}
413 %
414 % \begin{description}
415 % \item[Partition] A single element from the array.
416 % \item[Segment] A contiguous group of elements from the array.
417 % \end{description}
418 %
419 % The general approach is to divide the array into two smaller arrays,
420 % then sort each smaller array in turn.
421 %
422 % The inital array segment is the entire array.
423 %
424 % The basic steps are:
425 %
426 % \begin{enumerate}
427 % \item Determine $A_P$, the index of the partition element within the
428 % current array segment. In practice, this must be done in constant
429 % time~[$O(1)$] or the sort becomes slow.
430 % \item Partition the array into two array segments, separated by a
431 % partition, in linear time~[$O(N)$].
432 % \item Quick-sort the first array segment
433 % \item Quick-sort the second array segment
434 % \end{enumerate}
435 %
436 % The first step is choosing the partition element, $A_P$. This may be
437 % any element from the array segment, although the fastest results are
438 % achieved by selecting the median value. Many algorithms exist to
439 % perform this ``best guess''.
440 %
441 % The next step is partitioning. Other than the partition element,
442 % every element in the array is iterated over in turn. Any value less
443 % than the partition value~$P$ is moved to the left of the partition
444 % (lower index than $A_P$), and any value greater than the partition
445 % is moved to its right (higher index than $A_P$).
446 %
447 % So, if there are $N$ elements in an array~$A$, the original array is
448 % given by:
449 % \begin{eqnarray*}
450 % & A_0 \dots A_n &
451 % \end{eqnarray*}
452 %
453 % After the partitioning stage, the partitioned array is given by:
454 % \begin{eqnarray*}
455 % & A_0 \dots A_{(P-1)} , A_P , A_{(P+1)} \dots A_N &
456 % \end{eqnarray*}
457 % where $A_P$ is the partition and $P$ is the index of the
458 % partition.
459 %
460 % $A_0 \dots A_{(P-1)}$ defines the first array segment to be
461 % sorted and $A_{(P+1)} \dots A_N$ defines the second.
462 %
463 % Each array segment is considered to be sorted if it contains one
464 % element or less; otherwise, each are presented to the entire
465 % quick-sort algorithm to be sorted.
466 %
467 % Each iteration through the algorithm divides the array into smaller
468 % segments, each of which is always sorted relative to the other
469 % segments. Once the segment size is as small as one element, the
470 % entire array is sorted.
471 %
472 % \section{Possible Future Improvements}
473 %
474 % \begin{itemize}
475 % \item It should be possible to sort macro contents by their
476 % unexpanded values
477 % \item It may also be possible to sort macro contents in a
478 % case-insensitive manner (depending on language). Note that sorting
479 % mixed-language, mixed-alphabet content in a standard-complient
480 % manner is not always possible.
481 % \item Further speed improvemnts are possible; in particular, it is
482 % often faster to defer to a lower-overhead $O(n^2)$ sorting algorithm
483 % when the number of array segment elements is smaller than some threshold
484 % value (quick-sort is inefficient at sorting small arrays, but
485 % often produces many of them to be sorted).
486 % \item More sorting and partitining options. I am undecided about
487 % passing options \textit{versus}\ simply defining multiple macros;
488 % certainly the chance of a name collision is very small with the
489 % naming convention used so far.
490 % \item Support partition values not in the array:
491 % \end{itemize}
492 %
493 % \noindent Some implementations of quicksort allow for a partition value $P$
494 % that does not correspond to a value in the array, divding the array
495 % into:
496 % \begin{eqnarray*}s
497 % & A_0 \dots\/A_i , A_{(i+1)} \dots\ A_N &
498 % \end{eqnarray*}
499 % \noindent where $i$ is arbitrary. This is usually less efficient, as there is
500 % an additional value to be sorted with each iteration and hence a
501 % greater number of iterations in the best case.
502 %
503 % In some cases, it is not possible to know the best partition value
504 % within an array segment, or a single partition may not be applicable
505 % (such as an array containing only two distinct values); however,
506 % there may be some knowledge of the array's distribution. In the best
507 % case, a pre-calculated median of the array's contents might already be
508 % available prior to sorting, which would be the ideal partition value
509 % for the first iteration but would be unlikely to be a value in the
510 % array, let alone a value of known position.
511 %
512 % This would likely require significant changes to the algorithm.
513 %
514 % \ifexcludelongtest\else
515 % \section{Large-Scale Sorting}
516 %
517 %
518 % \makeatletter
519 % \iffalse
520 %<*example>
521 % \fi
522 \begin{exg}{$\backslash$sortArray on a large
523 scale}\begin{LTXexample}
524 \newarray{A}
525 \expandarrayelementtrue
526 \reinitrand[counter=rand,quiet=y]
527 \newcommand{\asize}{10000}
528 \multido{\i=1+1}{\asize}{
529 \rand
530 \A(\i)={\arabic{rand}}
531 }
532
533 \textbf{Before sort:}
534
535 \multido{\i=1+1}{50}{
536 \A(\i)
537 }\dots
538
539 \sortArray[arraysortcomparenum]{%
540 \asize}{A}
541
542 \line(1,0){100}
543
544 \textbf{After sort:}
545
546 \multido{\i=1+1}{50}{
547 \A(\i)
548 }\dots
549
550 \end{LTXexample}
551 This example uses the |multido| and |lcg| packages\end{exg}
552 % \iffalse
553 %</example>
554 % \fi
555 % \fi
556 %
557 % \section{Implementation}
558 %\StopEventually{\PrintChanges \pagebreak[4] \PrintIndex}
559 %
560 % \begin{macro}{\arraysort@extrapkgs}
561 % The \LaTeX\ package-option support does not allow conditional
562 % includes of packages. So, instead, we build up the required
563 % |\RequiresPackage| statements inside the |\arraysort@extrapkgs|
564 % macro.
565 % \begin{macrocode}
566 \newcommand*{\arraysort@extrapkgs}{}
567 % \end{macrocode}
568 % \end{macro}
569 %
570 % \begin{macro}{comparestr}
571 % \begin{macrocode}
572 \DeclareOption{comparestr}{
573 \g@addto@macro{\arraysort@extrapkgs}{
574 \RequirePackage{pdftexcmds}% for comparison. TODO: use compare.sty optionally
575 }
576 % \end{macrocode}
577 % \begin{macro}{\arraysortcomparestr}
578 % Called with two arguments, guaranteed to be re-evaluatable.
579 % must set arraysortresequal if arguments are considered equal, otherwise
580 % must set arraysortresult true if |#2| is to be sorted after |#1|, otherwise
581 % must set both flags false.
582 %
583 % Basic ASCII-like comparison
584 % \begin{macrocode}
585 \newcommand*{\arraysortcomparestr}[2]{%
586 \protected@edef\arraysort@left{#1}%
587 \protected@edef\arraysort@right{#2}%
588 \arraysort@comparestr%
589 }
590 % \end{macrocode}
591 %
592 % The following macro performs the comparison. The parameters must (it
593 % seems) be passed by macro as passing by parameter |#1| and |#2| did
594 % not cause the expected results, hence the extra macro.
595 % \begin{macrocode}
596 \newcommand*{\arraysort@comparestr}{%
597 \protected@edef\arraysort@compresult{\pdf@strcmp{\arraysort@left}{\arraysort@right}}%
598 \ifthenelse{\equal{\arraysort@compresult}{0}}{%
599 \toggletrue{arraysortresequal}%
600 }{%
601 \togglefalse{arraysortresequal}%
602 \ifthenelse{\equal{\arraysort@compresult}{-1}}{%
603 \toggletrue{arraysortresult}% #2 > #1
604 }{%
605 \togglefalse{arraysortresult}% #2 < #1
606 }%
607 }%
608 }
609 }
610 % \end{macrocode}
611 % \end{macro}
612 % \end{macro}
613 % \begin{macro}{comparenum}
614 % \begin{macrocode}
615 % Numeric comparison, as |\arraysortcomparestr| but used with arrays compairng numbers
616 \DeclareOption{comparenum}{
617 % \end{macrocode}
618 % \begin{macro}{\arraysortcomparenum}
619 % \begin{macrocode}
620 \newcommand*{\arraysortcomparenum}[2]{%
621 \ifthenelse{\equal{#1}{#2}}{%
622 \toggletrue{arraysortresequal}%
623 }{%
624 \togglefalse{arraysortresequal}%
625 \ifthenelse{#2 > #1}{%
626 \toggletrue{arraysortresult}%
627 }{%
628 \togglefalse{arraysortresult}%
629 }%
630 }%
631 }
632 }
633 % \end{macrocode}
634 % \end{macro}
635 % \end{macro}
636 %
637 % All partitioning algorithms should complete in O(1) time; that is,
638 % they should not iterate over the array, or do anything that takes
639 % longer the more elements there are.
640 %
641 % \begin{macro}{\sortArrayPartitionMed}
642 %
643 % Partition the segment consisting of indexes |#2|--|#3| (inclusive)
644 % of array named |#4|, using comparator |#1|
645 %
646 % Use the median of the first, last and middle values. While this has
647 % extra overhead compared to sortArrayPartitionFirst, it is guaranteed
648 % to avoid the worst-case performance of that method. If the array is
649 % randomly shuffled prior to sorting, this usually offers the best
650 % performance. This is the default method.
651 %
652 % Performance depends on the comparison macro.
653 %
654 % May not work well if there are many duplicate values.
655 % \begin{macrocode}
656 \newcommand*{\sortArrayPartitionMed}[4]{%
657 \setcounter{arraysort@temp1}{(#2 + #3) / 2}%
658 \edef\arraysort@midpos{\arabic{arraysort@temp1}}%
659 \testarray{#4}(#2)\protected@edef\arraysort@left{\temp@macro}%
660 \testarray{#4}(\arraysort@midpos)\protected@edef\arraysort@mid{\temp@macro}%
661 \testarray{#4}(#3)\protected@edef\arraysort@right{\temp@macro}%
662 \csname#1\endcsname{\arraysort@left}{\arraysort@mid}%
663 \iftoggle{arraysortresequal}{%
664 % \end{macrocode}
665 % left $=$ mid
666 % if any two are the same, there can be no median, so may as well
667 % leave alone
668 % \begin{macrocode}
669 }{%
670 % \end{macrocode}
671 % left $\ne$ mid
672 % \begin{macrocode}
673 \iftoggle{arraysortresult}{%
674 % \end{macrocode}
675 % left $<$ mid
676 % \begin{macrocode}
677 \csname#1\endcsname{\arraysort@left}{\arraysort@right}%
678 \iftoggle{arraysortresequal}{%
679 % \end{macrocode}
680 % $(\mbox{left} = \mbox{right}) < \mbox{mid}$
681 % \begin{macrocode}
682 }{%
683 \iftoggle{arraysortresult}{%
684 % \end{macrocode}
685 % left $<$ mid, left $<$ right
686 % \begin{macrocode}
687 \csname#1\endcsname{\arraysort@mid}{\arraysort@right}%
688 \iftoggle{arraysortresequal}{%
689 % \end{macrocode}
690 % $\mbox{left} < (\mbox{mid} = \mbox{right})$
691 % \begin{macrocode}
692 }{%
693 \iftoggle{arraysortresult}{%
694 % \end{macrocode}
695 % $\mbox{left} < \mbox{mid} < \mbox{right}$
696 % \begin{macrocode}
697 \arraysort@swap{#4}{#2}{\arraysort@midpos}%
698 }{%
699 % \end{macrocode}
700 % $\mbox{left} < \mbox{right} < \mbox{mid}$
701 % \begin{macrocode}
702 \arraysort@swap{#4}{#2}{#3}%
703 }%
704 }%
705 }{%
706 % \end{macrocode}
707 % left $<$ mid, left $>$ right
708 %
709 % left is already in the middle; leave alone
710 % \begin{macrocode}
711 }%
712 }%
713 }{%
714 % \end{macrocode}
715 % left $>$ mid
716 % \begin{macrocode}
717 \csname#1\endcsname{\arraysort@mid}{\arraysort@right}%
718 \iftoggle{arraysortresequal}{%
719 % \end{macrocode}
720 % $\mbox{left} > (\mbox{mid} = \mbox{right})$
721 % \begin{macrocode}
722 }{%
723 \iftoggle{arraysortresult}{%
724 % \end{macrocode}
725 % $\mbox{left} > \mbox{right} > \mbox{mid}$
726 % \begin{macrocode}
727 \arraysort@swap{#4}{#2}{#3}%
728 % \end{macrocode}
729 % swap right \& left, so left is median
730 % \begin{macrocode}
731 }{%
732 % \end{macrocode}
733 % $\mbox{left} > \mbox{mid} > \mbox{right}$
734 %
735 % swap right \& mid, so left is median
736 % \begin{macrocode}
737 \arraysort@swap{#4}{#2}{\arraysort@midpos}%
738 }%
739 }%
740 }%
741 }%
742 \sortArrayPartitionFirst{#1}{#2}{#3}{#4}%
743 }
744 % \end{macrocode}
745 %
746 % \begin{macro}{\sortArrayPartitionRand}
747 %
748 % Partition the sub-array
749 % consisting of indexes |#2|--|#3| (inclusive) of array named |#4|,
750 % using comparator |#1|
751 %
752 % Use the lcg package to generate a (pseudo)-random partition
753 % value. This should perform reasonably well most of the time, and you
754 % can simply re-run LaTeX if the performance is unacceptable.
755 %
756 % Caution: this macro will re-initialise the LCG package.
757 % \begin{macro}{randompart}
758 % \begin{macrocode}
759 \DeclareOption{randompart}{
760 \g@addto@macro{\arraysort@extrapkgs}{
761 % \end{macrocode}
762 % Store for later execution the fact that we will need tho |lcg| package
763 % for random numbers
764 % \begin{macrocode}
765 \RequirePackage[quiet]{lcg}
766 }
767 \newcommand*{\sortArrayPartitionRand}[4]{%
768 % \end{macrocode}
769 % It is necessary to change the start and end values of the sequence; the only way
770 % to do this is by reinitialising |lcg|. There are 2 possible
771 % problems; firstly, reinitrand outputs whitespace; and secondly it
772 % prints out a warning about a re-used counter. It's actually best to re-use
773 % the counter, but there's no way to silence the warning.
774 % \begin{macrocode}
775 \reinitrand[counter=arraysort@temp1,first=#2,last=#3,quiet=y]%
776 \rand%
777 \arraysort@swap{#4}{#2}{\arabic{arraysort@temp1}}%
778 \sortArrayPartitionFirst{#1}{#2}{#3}{#4}%
779 }
780 }
781 % \end{macrocode}
782 % \end{macro}
783 % \end{macro}
784 %
785 % \begin{macro}{\sortArrayPartitionMid}
786 %
787 % Partition the sub-array
788 % consisting of indexes |#2|--|#3| (inclusive) of array named |#4|,
789 % using comparator |#1|
790 %
791 % This implementation uses the middle value in the array segment. This is
792 % generally the best option if you don't know anything about the
793 % array's contents; in particular, it offers reasonable speed when
794 % attempting to re-sort previously-sorted ararys.
795 % \begin{macrocode}
796 \newcommand*{\sortArrayPartitionMid}[4]{%
797 \setcounter{arraysort@temp1}{(#2 + #3) / 2}%
798 \arraysort@swap{#4}{#2}{\arabic{arraysort@temp1}}%
799 \sortArrayPartitionFirst{#1}{#2}{#3}{#4}%
800 }
801 % \end{macrocode}
802 % \end{macro}
803 %
804 % \begin{macro}{\sortArrayPartitionFirst}
805 % Partition the array segment
806 % consisting of indexes |#2|--|#3| (inclusive) of array named |#4|,
807 % using comparator |#1|
808 %
809 % This implementation uses the first value in the array segment. This is
810 % fastest in theory, but only if the array is pre-shuffled. This has
811 % the worst performance when attempting to sort an already-sorted
812 % array.
813 % \begin{macrocode}
814 \newcommand*{\sortArrayPartitionFirst}[4]{%
815 \setcounter{arraysort@partpos}{#2}%
816 \setcounter{arraysort@temp1}{#2 + 1}%
817 \setcounter{arraysort@endpos}{#3 + 1}%
818 \arraysort@repeats{arraysort@temp1}{\value{arraysort@temp1}}{\value{arraysort@endpos}}{1}{%
819 \testarray{#4}(\arabic{arraysort@temp1})%
820 % \end{macrocode}
821 % if the value $A_{\mbox{temp1}}$ is less than partition $A_P$,
822 % decrement the partition counter by 1 and swap.
823 %
824 % |\let| copies without expanding:
825 % \begin{macrocode}
826 \let\arraysort@cur\temp@macro%
827 \testarray{#4}(\arabic{arraysort@partpos})%
828 % \end{macrocode}
829 % Expand the macros only once just in case they would be different
830 % on subsequent expansion:
831 % \begin{macrocode}
832 \protected@edef\arraysort@left{\arraysort@cur}%
833 \protected@edef\arraysort@right{\temp@macro}%
834 \csname#1\endcsname{\arraysort@left}{\arraysort@right}% #2 = cur, #3 = partition
835 \setcounter{arraysort@temp2}{\value{arraysort@partpos} + 1}%
836 \iftoggle{arraysortresequal}{% #2 = #3
837 % \end{macrocode}
838 % Must be moved before pivot
839 % Swap $A_P$ with $A_{P+1}$ then swap (the new) $A_P$ with
840 % current ($A_{\mbox{temp2}}=A_{P+1}$)
841 % \begin{macrocode}
842 \arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp2}}%
843 \arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp1}}%
844 % \end{macrocode}
845 % Increment partition; otherwise the next non-equal pivot will break
846 % \begin{macrocode}
847 \stepcounter{arraysort@partpos}%
848 }{%
849 \iftoggle{arraysortresult}{% #3 > #2
850 \ifthenelse{\equal{\arabic{arraysort@temp2}}{\arabic{arraysort@temp1}}}{%
851 % \end{macrocode}
852 % Just swap part with current value; they are adjacent
853 % \begin{macrocode}
854 \arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp1}}%
855 }{%
856 % \end{macrocode}
857 % Swap $A_P$ with $A_{P+1}$ then swap (the new) $A_P$ with
858 % current ($\mbox{temp}_2=A_{p+1}$)
859 % \begin{macrocode}
860 \arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp2}}%
861 \arraysort@swap{#4}{\arabic{arraysort@partpos}}{\arabic{arraysort@temp1}}%
862 }%
863 % \end{macrocode}
864 % Increment partition; one more in left array segment
865 % \begin{macrocode}
866 \stepcounter{arraysort@partpos}%
867 }{%
868 % \end{macrocode}
869 % $A_{|arraysort@cur|} > A_P$ and already after it; leave it alone
870 % \begin{macrocode}
871 }%
872 }%
873 }%
874 }
875 % \end{macrocode}
876 % \end{macro}
877 %
878 % \begin{macro}{\ProcessOptions}
879 % This processes the package include options, defining whichever of
880 % the above macros the user has asked for, and adding a list of any
881 % optional packages into |\arraysort@extrapkgs|.
882 %
883 % \begin{macrocode}
884 \ProcessOptions\relax
885 % \end{macrocode}
886 %\end{macro}
887 %
888 % Package includes for required packages:
889 %
890 % For loading the arrays that we will sort
891 % \begin{macrocode}
892 \RequirePackage{arrayjobx}
893 % \end{macrocode}
894 % For easier syntax on counter operations
895 % \begin{macrocode}
896 \RequirePackage{calc}
897 % \end{macrocode}
898 % For comparisons
899 % \begin{macrocode}
900 \RequirePackage{ifthen}
901 % \end{macrocode}
902 % Toggles etc.
903 % \begin{macrocode}
904 \RequirePackage{etoolbox}
905 % \end{macrocode}
906 % To declare macros with multiple optional arguments (\textit{ie}
907 % |\sortArray|)
908 % \begin{macrocode}
909 \RequirePackage{xargs}
910 % \end{macrocode}
911 % For partitioning
912 % \begin{macrocode}
913 \RequirePackage{macroswap}
914 % \end{macrocode}
915 % now process any conditional includes
916 % \begin{macrocode}
917 \arraysort@extrapkgs
918 % \end{macrocode}
919 %
920 % Now we are done including packages, so discard the macro:
921 % \begin{macrocode}
922 \let\arraysort@extrapkgs\relax
923 % \end{macrocode}
924 %
925 %
926 % \DescribeMacro{\sortArray}
927 % Sort the elements at index |#2|--|#3| of array named |#4|, using
928 % comparator |#1|.
929 %
930 % |#5| is the partitioning algorithm to use.
931 %
932 % \textit{eg} |\sortArray[1]{3}{ABC}|
933 %
934 % Defined using the |xargs| package
935 % \begin{macrocode}
936 \newcommandx*\sortArray[5][1=arraysortcomparestr,2=1,5=sortArrayPartitionMed]{%
937 \ifcsname#1\endcsname%
938 \ifthenelse{#2>0}{%
939 \ifthenelse{#3>#2}{%
940 \ifcsname total@#4\endcsname%
941 \arraysort@sort{#1}{#2}{#3}{#4}{#5}%
942 \else%
943 \PackageError{arraysort}{Cannot sort unknown array #4}{}%
944 \fi%
945 }{%
946 \PackageError{arraysort}{Cannot sort; to index #3 greater than from index #2}{}%
947 }%
948 }{%
949 \PackageError{arraysort}{Cannot sort; Invalid from index #2}{}%
950 }%
951 \else%
952 \PackageError{arraysort}{Cannot sort by undefined comparator #1}{}%
953 \fi%
954 }
955 % \end{macrocode}
956 % \end{macro}
957 %
958 % \begin{macro}{\arraysort@sort}
959 % As |\sortArray|, except that it doesn't validate its parameters,
960 % hence the |@| in the name (signifying an internal macro).
961 %
962 % Use with caution as error messages may be misleading.
963 %
964 % Sort the elements at index |#2|--|#3| of array named |#4|, using
965 % comparator |#1|
966 %
967 % |#5| is the partitioning algorithm to use.
968 % \begin{macrocode}
969 \newcommand*{\arraysort@sort}[5]{%
970 \csname#5\endcsname{#1}{#2}{#3}{#4}%
971 % \end{macrocode}
972 % Keep the position on the local stack!
973 % \begin{macrocode}
974 \edef\arraysort@partition{\value{arraysort@partpos}}%
975 \setcounter{arraysort@temp1}{\arraysort@partition - 1}%
976 \ifthenelse{#2 = \value{arraysort@temp1} \OR #2 > \value{arraysort@temp1}}{%
977 }{%
978 \edef\arraysort@to{\arabic{arraysort@temp1}}%
979 \arraysort@sort{#1}{#2}{\arraysort@to}{#4}{#5}%
980 }%
981 \setcounter{arraysort@temp1}{\arraysort@partition + 1}%
982 \ifthenelse{\value{arraysort@temp1} = #3 \OR #3 < \value{arraysort@temp1}}{%
983 }{%
984 \edef\arraysort@from{\arabic{arraysort@temp1}}%
985 \arraysort@sort{#1}{\arraysort@from}{#3}{#4}{#5}%
986 }%
987 }
988 % \end{macrocode}
989 % \end{macro}
990 %
991 %
992 % Counters used for sorting
993 %
994 % current position of the partition
995 % \begin{macrocode}
996 \newcounter{arraysort@partpos}
997 % \end{macrocode}
998 % current position in loop
999 % \begin{macrocode}
1000 \newcounter{arraysort@temp1}
1001 % \end{macrocode}
1002 % partition position $+1$
1003 % \begin{macrocode}
1004 \newcounter{arraysort@temp2}
1005 % \end{macrocode}
1006 % used for partitioning
1007 % \begin{macrocode}
1008 \newcounter{arraysort@endpos}
1009 % \end{macrocode}
1010 %
1011 % Toggles used by the comparator macro
1012 %
1013 % set by comparison if $|#1| < |#2|$
1014 % \begin{macrocode}
1015 \newtoggle{arraysortresult}
1016 % \end{macrocode}
1017 % set by comparison if $|#1| = |#2|$
1018 % \begin{macrocode}
1019 \newtoggle{arraysortresequal}
1020 % \end{macrocode}
1021 %
1022 % \begin{macro}{\arrayort@repeats}
1023 %
1024 % Don't use |\whiledo| here because it uses up TeX's capacity,
1025 % so rolling own basic repeat loop...
1026 %
1027 % For counter |#1| from |#2| to |#3| step |#4|, do |#5|
1028 % \begin{macrocode}
1029 \newcommand*{\arraysort@repeats}[5]{%
1030 \setcounter{#1}{#2}%
1031 \ifthenelse{\equal{\value{#1}}{#3}}{%
1032 }{%
1033 #5%
1034 \addtocounter{#1}{#4}%
1035 \arraysort@repeats{#1}{\arabic{#1}}{#3}{#4}{#5}%
1036 }%
1037 }
1038 % \end{macrocode}
1039 % \end{macro}
1040 %
1041 % \begin{macro}{\arraysort@swap}
1042 % Globally swap array values |#1(#2)| with |#1(#3)|
1043 %
1044 % \textit{ie} \\ |#1| is the macro name \\
1045 % |#2| and |#3| are the numeic indexes of the array elements to be
1046 % swapped.
1047 % \begin{macrocode}
1048 \newcommand\arraysort@swap[3]{%
1049 % \end{macrocode}
1050 % |arrayjobx| does not provide a way to assign an array element to the
1051 % contents of another element (or macro) without expanding it. This macro simply
1052 % swaps the definitions of the two macros used internally by |arrayjobx|:
1053 % \begin{macrocode}
1054 \gmacroswap{#1#2\string~}{#1#3\string~}%
1055 }
1056 % \end{macrocode}
1057 % \end{macro}
1058 %
1059 % That is all
1060 % \Finale
1061 \endinput