% \iffalse
%
%% File l3sort.dtx (C) Copyright 2012 The LaTeX3 Project
%%
%% It may be distributed and/or modified under the conditions of the
%% LaTeX Project Public License (LPPL), either version 1.3c of this
%% license or (at your option) any later version.  The latest version
%% of this license is in the file
%%
%%    http://www.latex-project.org/lppl.txt
%%
%% This file is part of the "l3experimental bundle" (The Work in LPPL)
%% and all files in that bundle must be distributed together.
%%
%% The released version of this bundle is available from CTAN.
%%
%% -----------------------------------------------------------------------
%%
%% The development version of the bundle can be found at
%%
%%    http://www.latex-project.org/svnroot/experimental/trunk/
%%
%% for those people who are interested.
%%
%%%%%%%%%%%
%% NOTE: %%
%%%%%%%%%%%
%%
%%   Snapshots taken from the repository represent work in progress and may
%%   not work or may contain conflicting material!  We therefore ask
%%   people _not_ to put them into distributions, archives, etc. without
%%   prior consultation with the LaTeX Project Team.
%%
%% -----------------------------------------------------------------------
%%
%
%<*driver|package>
\RequirePackage{expl3}
\GetIdInfo$Id: l3sort.dtx 3467 2012-02-26 15:39:35Z bruno $
  {L3 Experimental sorting functions}
%</driver|package>
%<*driver>
\documentclass[full]{l3doc}
\usepackage{amsmath}
\begin{document}
  \DocInput{\jobname.dtx}
\end{document}
%</driver>
% \fi
%
% \title{^^A
%   The \pkg{l3sort} package\\ Sorting lists^^A
%   \thanks{This file describes v\ExplFileVersion,
%      last revised \ExplFileDate.}^^A
% }
%
% \author{^^A
%  The \LaTeX3 Project\thanks
%    {^^A
%      E-mail:
%        \href{mailto:latex-team@latex-project.org}
%          {latex-team@latex-project.org}^^A
%    }^^A
% }
%
% \date{Released \ExplFileDate}
%
% \maketitle
%
% \begin{documentation}
%
% \section{\pkg{l3sort} documentation}
%
% \LaTeX3 comes with a function to sort list variables (sequences,
% token lists, or comma-lists) according to some user-defined
% comparison. For instance,
% \begin{verbatim}
%   \clist_set:Nn \l_foo_clist { 3 , 01 , -2 , 5 , +1 }
%   \clist_sort:Nn \l_foo_clist
%     {
%       \int_compare:nNnTF { #1 } > { #2 }
%         { \sort_reversed: }
%         { \sort_ordered: }
%     }
% \end{verbatim}
% will result in \cs{l_foo_clist} holding the values
% |{ -2 , 01 , +1 , 3 , 5 }| sorted in non-decreasing order.
%
% The code defining the comparison should perform
% \cs{sort_reversed:} if the two items given as |#1|
% and |#2| are not in the correct order, and otherwise it
% should call \cs{sort_ordered:} to indicate that
% the order of this pair of items should not be changed.
%
% For instance, a \meta{comparison code} consisting only
% of \cs{sort_ordered:} with no test will yield a trivial
% sort: the final order is identical to the original order.
% Conversely, using a \meta{comparison code} consisting only
% of \cs{sort_reversed:} will reverse the list (in a fairly
% inefficient way).
%
% \begin{texnote}
%   Internally, the code from \pkg{l3sort} stores items in \tn{toks}.
%   Thus, the \meta{comparison code} should not alter the
%   contents of any \tn{toks}, nor assume that they hold a
%   given value.
% \end{texnote}
%
% \begin{function}{\seq_sort:Nn, \seq_gsort:Nn}
%   \begin{syntax}
%     \cs{seq_sort:Nn} \meta{sequence} \Arg{comparison code}
%   \end{syntax}
%   Sorts the items in the \meta{sequence} according to the
%   \meta{comparison code}, and assigns the result to
%   \meta{sequence}.
% \end{function}
%
% \begin{function}{\tl_sort:Nn, \tl_gsort:Nn}
%   \begin{syntax}
%     \cs{tl_sort:Nn} \meta{tl var} \Arg{comparison code}
%   \end{syntax}
%   Sorts the items in the \meta{tl var} according to the
%   \meta{comparison code}, and assigns the result to
%   \meta{tl var}.
% \end{function}
%
% \begin{function}{\clist_sort:Nn, \clist_gsort:Nn}
%   \begin{syntax}
%     \cs{clist_sort:Nn} \meta{clist var} \Arg{comparison code}
%   \end{syntax}
%   Sorts the items in the \meta{clist var} according to the
%   \meta{comparison code}, and assigns the result to
%   \meta{clist var}.
% \end{function}
%
% \end{documentation}
%
% \begin{implementation}
%
% \section{\pkg{l3sort} implementation}
%
%    \begin{macrocode}
%<*initex|package>
%    \end{macrocode}
%
%    \begin{macrocode}
%<*package>
\ProvidesExplPackage
  {\ExplFileName}{\ExplFileDate}{\ExplFileVersion}{\ExplFileDescription}
\package_check_loaded_expl:
%</package>
%    \end{macrocode}
%
% \subsection{Variables}
%
% \begin{variable}{\c_sort_max_length_int}
%   The maximum length of a sequence which will not overflow
%   the available registers depends on which engine is in use.
%   For $2^{N}$ registers, it is $3\cdot 2^{N-2}$: for that number
%   of items, at the last step the block size will be $2^{N-1}$,
%   and the two blocks to merge will be of sizes $2^{N-1}$ and
%   $2^{N-2}$ respectively. When merging, one of the blocks must
%   be copied to temporary registers; here, the smallest block,
%   of size $2^{N-2}$, will fill up exactly the $2^{N-2}$ free
%   registers, totalling $2^{N-1}+2^{N-2}+2^{N-2}=2^{N}$ registers.
%    \begin{macrocode}
\int_const:Nn \c_sort_max_length_int
  { \luatex_if_engine:TF { 49152 } { 24576 } }
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_sort_length_int}
%   Length of the sequence which is being sorted.
%    \begin{macrocode}
\int_new:N \l_sort_length_int
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_sort_block_int}
%   Merge sort is done in several passes. In each pass, blocks of size
%   \cs{l_sort_block_int} are merged in pairs. The block size starts
%   at $1$, and, for a length in the range $[2^k+1,2^{k+1}]$, reaches
%   $2^{k}$ in the last pass.
%    \begin{macrocode}
\int_new:N \l_sort_block_int
%    \end{macrocode}
% \end{variable}
%
% \begin{variable}{\l_sort_begin_int}
% \begin{variable}{\l_sort_end_int}
%   When merging two blocks, \cs{l_sort_begin_int} marks the lowest
%   index in the two blocks, and \cs{l_sort_end_int} marks the
%   highest index, plus $1$.
%    \begin{macrocode}
\int_new:N \l_sort_begin_int
\int_new:N \l_sort_end_int
%    \end{macrocode}
% \end{variable}
% \end{variable}
%
% \begin{variable}{\l_sort_A_int}
% \begin{variable}{\l_sort_B_int}
% \begin{variable}{\l_sort_C_int}
%   When merging two blocks (whose end-points are \texttt{beg}
%   and \texttt{end}), $A$ starts from the high end of the low
%   block, and decreases until reaching \texttt{beg}. The index
%   $B$ starts from the top of the range and marks the register
%   in which a sorted item should be put. Finally, $C$ points
%   to the copy of the high block in the interval of registers
%   starting at \cs{l_sort_length_int}, upwards. $C$ starts
%   from the upper limit of that range.
%    \begin{macrocode}
\int_new:N \l_sort_A_int
\int_new:N \l_sort_B_int
\int_new:N \l_sort_C_int
%    \end{macrocode}
% \end{variable}
% \end{variable}
% \end{variable}
%
% \subsection{User commands}
%
% \begin{macro}[int]{\sort_aux:NNnNn}
%   Sorting happens in three steps. First store items
%   in \tn{toks} registers ranging from $0$ to the length
%   of the list, while checking that the list is not too
%   long. If we reach the maximum length, all further
%   items are entirely ignored after raising an error.
%   Secondly, sort the array of \tn{toks} registers,
%   using the user-defined sorting function, |#5|.
%   Finally, unpack the \tn{toks} registers (now sorted)
%   into a variable of the right type, by \texttt{x}-expanding
%   the code in |#3|, specific to each type of list.
%    \begin{macrocode}
\cs_new_protected:Npn \sort_aux:NNnNn #1#2#3#4#5
  {
    \group_begin:
      \l_sort_length_int \c_zero
      #2 #4
        {
          \if_num:w \l_sort_length_int = \c_sort_max_length_int
            \sort_too_long_error:Nw #4
          \fi:
          \tex_toks:D \l_sort_length_int {##1}
          \tex_advance:D \l_sort_length_int \c_one
        }
      \cs_set:Npn \sort_compare:nn ##1 ##2 { #5 }
      \l_sort_block_int \c_one
      \sort_level:
      \use:x
        {
          \group_end:
          #1 \exp_not:N #4 {#3}
        }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\seq_sort:Nn, \seq_gsort:Nn}
%   The first argument to \cs{sort_aux:NNnNn} is the final
%   assignment function used, either \cs{tl_set:Nn} or
%   \cs{tl_gset:Nn} to control local versus global results.
%   The second argument is what mapping function is used
%   when storing items to \tn{toks} registers. The third
%   is used to build back the correct kind of list from the
%   contents of the \tn{toks} registers. Fourth and fifth
%   arguments are the variable to sort, and the sorting method
%   as inline code.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \seq_sort:Nn
  {
    \sort_aux:NNnNn \tl_set:Nn
      \seq_map_inline:Nn
      { \sort_toks:NNw \exp_not:N \seq_item:n 0 ; }
  }
\cs_new_protected_nopar:Npn \seq_gsort:Nn
  {
    \sort_aux:NNnNn \tl_gset:Nn
      \seq_map_inline:Nn
      { \sort_toks:NNw \exp_not:N \seq_item:n 0 ; }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\tl_sort:Nn, \tl_gsort:Nn}
%   Again, use \cs{tl_set:Nn} or \cs{tl_gset:Nn} to control
%   the scope of the assignment. Mapping through the token
%   list is done with \cs{tl_map_inline:Nn}, and producing
%   the token list is very similar to sequences, removing
%   \cs{seq_item:Nn}.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \tl_sort:Nn
  {
    \sort_aux:NNnNn \tl_set:Nn
      \tl_map_inline:Nn
      { \sort_toks:NNw \prg_do_nothing: \prg_do_nothing: 0 ; }
  }
\cs_new_protected_nopar:Npn \tl_gsort:Nn
  {
    \sort_aux:NNnNn \tl_gset:Nn
      \tl_map_inline:Nn
      { \sort_toks:NNw \prg_do_nothing: \prg_do_nothing: 0 ; }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\clist_sort:Nn, \clist_gsort:Nn}
% \begin{macro}[aux]{\clist_sort_aux:NNn}
%   The case of empty comma-lists is a little bit special as usual,
%   and filtered out: there is nothing to sort in that case.
%   Otherwise, the input is done with \cs{clist_map_inline:Nn},
%   and the output requires some more elaborate processing than
%   for sequences and token lists. The first comma must be removed.
%   An item must be wrapped in an extra set of braces if it contains
%   either the space or the comma characters. This is taken care of
%   by \cs{clist_wrap_item:n}, but \cs{sort_toks:NNw} would simply
%   feed \cs{tex_the:D} \cs{tex_toks:D} \meta{number} as an
%   argument to that function; hence we need to expand this argument
%   once to unpack the register.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \clist_sort:Nn
  { \clist_sort_aux:NNn \tl_set:Nn }
\cs_new_protected_nopar:Npn \clist_gsort:Nn
  { \clist_sort_aux:NNn \tl_gset:Nn }
\cs_new_protected:Npn \clist_sort_aux:NNn #1#2#3
  {
    \clist_if_empty:NF #2
      {
        \sort_aux:NNnNn #1
          \clist_map_inline:Nn
          {
            \exp_last_unbraced:Nf \use_none:n
              { \sort_toks:NNw \exp_args:No \clist_wrap_item:n 0 ; }
          }
          #2 {#3}
      }
  }
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\sort_toks:NNw}
%   Unpack the various \tn{toks} registers, from $0$ to the length
%   of the list. The functions |#1| and |#2| allow us to treat the
%   three data structures in a unified way:
%   \begin{itemize}
%   \item for sequences, they are \cs{exp_not:N} \cs{seq_item:n},
%     expanding to the \cs{seq_item:n} separator, as expected;
%   \item for token lists, they expand to nothing;
%   \item for comma lists, they expand to \cs{exp_args:No}
%     \cs{clist_wrap_item:n}, taking care of unpacking the register
%     before letting the undocumented internal \pkg{clist} function
%     \cs{clist_wrap_item:n} do the work of putting a comma and possibly
%     braces.
%   \end{itemize}
%    \begin{macrocode}
\cs_new:Npn \sort_toks:NNw #1#2#3 ;
  {
    \if_num:w #3 < \l_sort_length_int
      #1 #2 { \tex_the:D \tex_toks:D #3 }
      \exp_after:wN \sort_toks:NNw \exp_after:wN #1 \exp_after:wN #2
      \int_use:N \int_eval:w #3 + \c_one \exp_after:wN ;
    \fi:
  }
%    \end{macrocode}
% \end{macro}
%
% \subsection{Sorting itself}
%
% \begin{macro}[int]{\sort_level:}
%   This function is called once blocks of size \cs{l_sort_block_int}
%   (initially $1$) are each sorted. If the whole list fits in one
%   block, then we are done (this also takes care of the case of an
%   empty list or a list with one item). Otherwise, go through pairs
%   of blocks starting from $0$, then double the block size, and repeat.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \sort_level:
  {
    \if_num:w \l_sort_block_int < \l_sort_length_int
      \l_sort_end_int \c_zero
      \sort_merge_blocks:
      \tex_multiply:D \l_sort_block_int \c_two
      \exp_after:wN \sort_level:
    \fi:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\sort_merge_blocks:}
%   This function is called to merge a pair of blocks, starting at
%   the last value of \cs{l_sort_end_int} (end-point of the previous
%   pair of blocks). If shifting by one block to the right we reach
%   the end of the list, then this pass has ended: this end of the
%   list is sorted already. Store the result of that shift in $A$,
%   which will index the first block starting from the top end.
%   Then locate the end-point (maximum) of the upper block: shift
%   \texttt{end} upwards by one more block, checking that we don't
%   go beyond the length of the list. Copy this upper block of \tn{toks}
%   registers in registers above \texttt{length}, indexed by $C$:
%   this is covered by \cs{sort_copy_block:}. Once this is done we
%   are ready to do the actual merger using \cs{sort_merge_blocks_aux:},
%   after shifting $A$, $B$ and $C$ so that they point to the largest
%   index in their respective ranges rather than pointing just beyond
%   those ranges. Of course, once that pair of blocks is merged,
%   move on to the next pair.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \sort_merge_blocks:
  {
    \l_sort_begin_int \l_sort_end_int
    \tex_advance:D \l_sort_end_int \l_sort_block_int
    \if_num:w \int_eval:w \l_sort_end_int < \l_sort_length_int
      \l_sort_A_int \l_sort_end_int
      \tex_advance:D \l_sort_end_int \l_sort_block_int
      \if_num:w \l_sort_end_int > \l_sort_length_int
        \l_sort_end_int \l_sort_length_int
      \fi:
      \l_sort_B_int \l_sort_A_int
      \l_sort_C_int \l_sort_length_int
      \sort_copy_block:
      \tex_advance:D \l_sort_A_int \c_minus_one
      \tex_advance:D \l_sort_B_int \c_minus_one
      \tex_advance:D \l_sort_C_int \c_minus_one
      \sort_merge_blocks_aux:
      \exp_after:wN \sort_merge_blocks:
    \fi:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[int]{\sort_copy_block:}
%   We wish to store a copy of the \enquote{upper} block of
%   \tn{toks} registers, ranging between the initial value of
%   \cs{l_sort_B_int} (included) and \cs{l_sort_end_int}
%   (excluded) into a new range starting at the initial value
%   of \cs{l_sort_C_int}, namely \cs{l_sort_length_int}.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \sort_copy_block:
  {
    \tex_toks:D \l_sort_C_int \tex_toks:D \l_sort_B_int
    \tex_advance:D \l_sort_C_int \c_one
    \tex_advance:D \l_sort_B_int \c_one
    \if_num:w \l_sort_B_int = \l_sort_end_int
      \use_i:nn
    \fi:
    \sort_copy_block:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\sort_merge_blocks_aux:}
%   At this stage, the first block starts at \cs{l_sort_begin_int},
%   and ends at \cs{l_sort_A_int}, and the second block starts at
%   \cs{l_sort_length_int} and ends at \cs{l_sort_C_int}. The result
%   of the merger is stored at positions indexed by \cs{l_sort_B_int},
%   which starts at $\cs{l_sort_end_int}-1$ and decreases down to
%   \cs{l_sort_begin_int}, covering the full range of the two blocks.
%   In other words, we are building the merger starting with the
%   largest values.
%   The comparison function is defined to return either
%   \texttt{reversed} or \texttt{ordered}. Of course, this
%   means the arguments need to be given in the order they
%   appear originally in the list.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \sort_merge_blocks_aux:
  {
    \exp_after:wN \sort_compare:nn \exp_after:wN
      { \tex_the:D \tex_toks:D \exp_after:wN \l_sort_A_int \exp_after:wN }
      \exp_after:wN { \tex_the:D \tex_toks:D \l_sort_C_int }
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\sort_ordered:}
%   If the comparison function returns \texttt{ordered},
%   then the second argument fed to \cs{sort_compare:nn}
%   should remain to the right of the other one. Since
%   we build the merger starting from the right, we copy
%   that \tn{toks} register into the allotted range, then
%   shift the pointers $B$ and $C$, and go on to do one
%   more step in the merger, unless the second block has
%   been exhausted: then the remainder of the first block
%   is already in the correct register and we are done
%   with merging those two blocks.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \sort_ordered:
  {
    \tex_toks:D \l_sort_B_int \tex_toks:D \l_sort_C_int
    \tex_advance:D \l_sort_B_int \c_minus_one
    \tex_advance:D \l_sort_C_int \c_minus_one
    \if_num:w \l_sort_C_int < \l_sort_length_int
      \use_i:nn
    \fi:
    \sort_merge_blocks_aux:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\sort_reversed:}
%   If the comparison function returns \texttt{reversed},
%   then the next item to add to the merger is the first
%   argument, contents of the \tn{toks} register $A$.
%   Then shift the pointers $A$ and $B$ to the left, and
%   go for one more step fo the merger, unless the left
%   block was exhausted ($A$ goes below the threshold).
%   In that case, all remaining \tn{toks} registers in
%   the second block, indexed by $C$, should be copied
%   to the merger (see \cs{sort_merge_blocks_end:}).
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \sort_reversed:
  {
    \tex_toks:D \l_sort_B_int \tex_toks:D \l_sort_A_int
    \tex_advance:D \l_sort_B_int \c_minus_one
    \tex_advance:D \l_sort_A_int \c_minus_one
    \if_num:w \l_sort_A_int < \l_sort_begin_int
      \sort_merge_blocks_end: \use_i:nn
    \fi:
    \sort_merge_blocks_aux:
  }
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}[aux]{\sort_merge_blocks_end:}
%   This function's task is to copy the \tn{toks} registers
%   in the block indexed by $C$ to the merger indexed by $B$.
%   The end can equally be detected by checking when $B$ reaches
%   the threshold \texttt{begin}, or when $C$ reaches
%   \texttt{length}.
%    \begin{macrocode}
\cs_new_protected_nopar:Npn \sort_merge_blocks_end:
  {
    \tex_toks:D \l_sort_B_int \tex_toks:D \l_sort_C_int
    \tex_advance:D \l_sort_B_int \c_minus_one
    \tex_advance:D \l_sort_C_int \c_minus_one
    \if_num:w \l_sort_B_int < \l_sort_begin_int
      \use_i:nn
    \fi:
    \sort_merge_blocks_end:
  }
%    \end{macrocode}
% \end{macro}
%
% \subsection{Messages}
%
% \begin{macro}{\sort_too_long_error:Nw}
%   When there are too many items in a sequence, this is an error,
%   and we clean up properly the mapping over items in the list.
%   This relies on the fact that the breaking code for all mappings
%   is unified.
%    \begin{macrocode}
\cs_new_protected:Npn \sort_too_long_error:Nw #1 \fi:
  {
    \fi:
    \msg_kernel_error:nnx { sort } { too-large } { \token_to_str:N #1 }
    \prg_map_break:
  }
\msg_kernel_new:nnnn { sort } { too-large }
  { The~list~#1~is~too~long~to~be~sorted~by~TeX. }
  {
    TeX~has~\int_use:N \c_max_register_int \ registers~available:~
    this~only~allows~to~sorts~with~up~to~\int_use:N \c_sort_max_length_int
    \ items.~All~extra~items~will~be~ignored.
  }
%    \end{macrocode}
% \end{macro}
%
%    \begin{macrocode}
%</initex|package>
%    \end{macrocode}
%
% \end{implementation}
%
% \PrintIndex