% \iffalse
%% File: l3prg.dtx Copyright (C) 2005-2006 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 ``expl3 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/cgi-bin/cvsweb.cgi/
%%
%% 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.
%%
%% -----------------------------------------------------------------------
%
%<package>\RequirePackage{l3names}
%<*dtx>
%\fi
\def\GetIdInfo$Id: #1.dtx #2 #3-#4-#5 #6 #7$#8{%
  \def\fileversion{#2}%
  \def\filedate{#3/#4/#5}%
  \ProvidesFile{#1.dtx}[#3/#4/#5 v#2 #8]%
}
%\iffalse
%</dtx>
%\fi
\GetIdInfo$Id: l3prg.dtx 574 2006-08-21 23:30:10Z morten $
       {L3 Experimental control structures}
%
% \iffalse
%<*driver>
\documentclass{l3doc}

\begin{document}
\DocInput{l3prg.dtx}
\end{document}
%</driver>
% \fi
%
% \title{The \textsf{l3prg} package\thanks{This file
%         has version number \fileversion, last
%         revised \filedate.}\\
% Program control structures}
% \author{\Team}
% \date{\filedate}
% \maketitle
%
%
% \section{Control structures}
%
% \subsection{Choosing modes}
%
% \begin{function}{\mode_vertical_p:|
%                  \mode_vertical:TF |
%                  \mode_vertical:T |
%                  \mode_vertical:F
%                 }
% \begin{syntax}
%   "\mode_vertical:TF" "{"<true code>"}" "{"<false code>"}"
% \end{syntax}
% Determines if \TeX{} is in vertical mode or not and executes either
% <true code> or <false code> accordingly.
% \end{function}
%
% \begin{function}{\mode_horizontal_p:|
%                  \mode_horizontal:TF |
%                  \mode_horizontal:T |
%                  \mode_horizontal:F
%                 }
% \begin{syntax}
%   "\mode_horizontal:TF" "{"<true code>"}" "{"<false code>"}"
% \end{syntax}
% Determines if \TeX{} is in horizontal mode or not and executes either
% <true code> or <false code> accordingly.
% \end{function}
%
%
% \begin{function}{
%     \mode_inner_p:|
%     \mode_inner:TF|
%     \mode_inner:T|
%     \mode_inner:F
%                 }
% \begin{syntax}
%   "\mode_inner:TF" "{"<true code>"}" "{"<false code>"}"
% \end{syntax}
% Determines if \TeX{} is in inner mode or not and executes either
% <true code> or <false code> accordingly.
% \end{function}
%
% \begin{function}{
%               \mode_math:TF|
%               \mode_math:T|
%               \mode_math:F|
%                 }
% \begin{syntax}
%   "\mode_math:TF" "{"<true code>"}" "{"<false code>"}"
% \end{syntax}
% Determines if \TeX{} is in math mode or not and executes either
% <true code> or <false code> accordingly.
% \begin{texnote}
% This version will choose the right branch even at the beginning of
% an alignment cell.
% \end{texnote}
% \end{function}
%
%
% \subsubsection{Alignment safe grouping and scanning}
%
% \begin{function}{\scan_align_safe_stop:}
% \begin{syntax}
%   "\scan_align_safe_stop:"
% \end{syntax}
% This function gets \TeX{} on the right track inside an alignment
% cell but without destroying any kerning.
% \end{function}
%
%
% \begin{function}{\group_align_safe_begin:|
%                  \group_align_safe_end:}
% \begin{syntax}
%   "\group_align_safe_begin:" <...> "\group_align_safe_end:"
% \end{syntax}
% Encloses <...> inside a group but is safe inside an alignment cell.
% See the implementation of |\peek_token_generic:NNTF| for an
% application.
% \end{function}
%
%
% \subsection{Producing $n$ copies}
% 
% There are often several different requirements for producing
% multiple copies of something. Sometimes one might want to produce a
% number of identical copies of a sequence of tokens whereas at other
% times the goal is to simulate a for loop as known from most real
% programming languages.
%
% \begin{function}{\prg_replicate:nn }
% \begin{syntax}
%   "\prg_replicate:nn" "{" <number> "}" "{" <arg> "}"
% \end{syntax}
% Creates <number> copies of <arg>. Expandable.
% \end{function}
%
%
% \begin{function}{\prg_stepwise_function:nnnN}
% \begin{syntax}
%   "\prg_stepwise_function:nnnN" "{"<start>"}" "{"<step>"}"
%   "{"<end>"}" <function>
% \end{syntax}
% This function performs <action> once for each step starting at
% <start> and ending once <end> is passed. <function> is placed
% directly in front of a brace group holding the current number so it
% should usually be a function taking one argument. The
% |\prg_stepwise_function:nnnN| function is expandable.
% \end{function}
%
% \begin{function}{\prg_stepwise_inline:nnnn}
% \begin{syntax}
%   "\prg_stepwise_inline:nnnn" "{"<start>"}" "{"<step>"}" "{"<end>"}"
%   "{"<action>"}"
% \end{syntax}
% Same as |\prg_stepwise_function:nnnN| except here <action> is
% performed each time with |##1| as a placeholder for the number
% currently being tested. This function is not expandable and it is
% nestable.
% \end{function}
%
% \begin{function}{\prg_stepwise_variable:nnnNn}
% \begin{syntax}
%   "\prg_stepwise_variable:nnnn" "{"<start>"}" "{"<step>"}" "{"<end>"}"
%   <temp-var> "{"<action>"}"
% \end{syntax}
% Same as |\prg_stepwise_inline:nnnn| except here the current value is
% stored in <temp-var> and the programmer can use it in <action>. This
% function is not expandable.
% \end{function}
%
%
%
%  \subsection{Conditionals and logical operations}
%
%
%  \LaTeX3 has two primary forms of conditional flow processing. The
%  one type deals with the truth value of a test directly as in
%  "\cs_free:NTF" where you test if a control sequence was undefined
%  and then execute either the \m{true} or \m{false} part depending on
%  the result and after exiting the underlying "\if...\fi:" structure.
%  The second type has to do with predicate functions like
%  "\cs_free_p:N" which return either "\c_true" or "\c_false" to be
%  used in testing with "\if:w".
%
%
%  This section describes a boolean data type which is closely
%  connected to both parts as sometimes you want to execute some code
%  depending on the value of a switch (e.g.,~draft/final) and other
%  times you perhaps want to use it as a predicate function in an
%  "\if:w" test. Here \TeX's original concept with "\iffalse" and
%  "\iftrue" is a little difficult to handle so the easiest is simply
%  to let a boolean either be "\c_true" or "\c_false". This also means
%  we get the logical operations And, Or, and Not which can then be
%  used on both the boolean type and predicate functions. All
%  functions by the name |\prg_if_predicate_| are expandable and
%  expect the input to also be fully expandable. More generic
%  constructs do not contain |predicate| in their names.
%
%
%  \subsubsection{The boolean data type}
%
%  \begin{function}{%
%                   \bool_new:N |
%                   \bool_new:c |
%  }
%  \begin{syntax}
%     "\bool_new:N" <bool> 
%  \end{syntax}
%  Define a new boolean variable. The initial value is <false>. A
%  boolean is actually just either "\c_true" or "\c_false".
%  \end{function}
%
%  \begin{function}{%
%                   \bool_set_true:N |
%                   \bool_set_true:c |
%                   \bool_set_false:N |
%                   \bool_set_false:c |
%                   \bool_gset_true:N |
%                   \bool_gset_true:c |
%                   \bool_gset_false:N |
%                   \bool_gset_false:c |
%  }
%  \begin{syntax}
%     "\bool_gset_false:N" <bool>
%  \end{syntax}
%  Set <bool> either true or false. We can also do this globally.
%  \end{function}
%
%
%  \begin{function}{%
%                   \bool_set_eq:NN |
%                   \bool_set_eq:Nc |
%                   \bool_set_eq:cN |
%                   \bool_set_eq:cc |
%                   \bool_gset_eq:NN |
%                   \bool_gset_eq:Nc |
%                   \bool_gset_eq:cN |
%                   \bool_gset_eq:cc |
%
%  }
%  \begin{syntax}
%     "\bool_set_eq:NN" <bool1> <bool2>
%  \end{syntax}
%  Set <bool1> equal to the value of <bool2>.
%  \end{function}
%
%  \begin{function}{%
%                   \bool_if:NTF |
%                   \bool_if:NT |
%                   \bool_if:NF |
%                   \bool_if_p:N |
%
%  }
%  \begin{syntax}
%     "\bool_if:NTF" <bool> "{"\m{true}"}" "{"\m{false}"}"   \\
%     "\bool_if_p:N" <bool>
%  \end{syntax}
%  Test the truth value of the boolean and execute the \m{true} or
%  \m{false} code. "\bool_if_p:N" is a predicate function for use in
%  "\if:w" tests.
%  \end{function}
%
%  \begin{function}{%
%                   \bool_whiledo:NT |
%                   \bool_whiledo:NF |
%                   \bool_dowhile:NT |
%                   \bool_dowhile:NF |
%
%  }
%  \begin{syntax}
%     "\bool_whiledo:NT" <bool> "{"\m{true}"}"  \\
%     "\bool_whiledo:NF" <bool> "{"\m{false}"}"  \\
%  \end{syntax}
%  The "T" versions execute the \m{true} code as long as the boolean is
%  true and the "F" versions execute the \m{false} code as long as the
%  boolean is false. The "whiledo" functions execute the body after
%  testing the boolean and the "dowhile" functions executes the body
%  first and then tests the boolean.
%  \end{function}
%
%
%  \begin{function}{%
%                   \l_tmpa_bool |
%                   \g_tmpa_bool |
%
%  }
%  \begin{syntax}
%  \end{syntax}
%  Reserved booleans.
%  \end{function}
%
%  \subsubsection{Logical operations}
%
%  Somewhat related to the subject of conditional flow processing is
%  logical operators as these deal with \m{true} and \m{false}
%  statements which is precisely what the predicate functions return.
%
%
%  \begin{function}{%
%                   \prg_if_predicate:nTF |
%                   \prg_if_predicate:nT |
%                   \prg_if_predicate:nF |
%  }
%  \begin{syntax}
%    "\prg_if_predicate:nTF" "{"<predicate>"}" "{"<true>"}" "{"<false>"}" \\
%  \end{syntax}
%  The first argument can either be a predicate function like
%  "\cs_free_p:N \foo" or one of the logic tests below.
%  \end{function}
%
%
%
%
%  \begin{function}{%
%                   \prg_if_predicate_ors_p:n |
%                   \prg_if_predicate_or_p:nn |
%                   \prg_if_predicate_ands_p:n |
%                   \prg_if_predicate_and_p:nn |
%                   \prg_if_predicate_not_p:n |
%  }
%  \begin{syntax}
%     "\prg_if_predicate_ors_p:n" "{"<predicate> <predicate> ..."}"  \\
%     "\prg_if_predicate_or_p:nn" "{"<predicate>"}" "{"<predicate>"}" \\
%     "\prg_if_predicate_ands_p:n" "{"<predicate> <predicate> ..."}"  \\
%     "\prg_if_predicate_and_p:nn" "{"<predicate>"}" "{"<predicate>"}" \\
%     "\prg_if_predicate_not_p:n" "{"<predicate>"}"
%  \end{syntax}
%  "\prg_if_predicate_or_p:nn" compares the outcome of two predicate
%  functions (or other logic tests) and if either turns out to be
%  \m{true} returns \m{true} itself. "\prg_if_predicate_and_p:nn"
%  works in a similar way but requires both outcomes to be \m{true} in
%  order for it to return \m{true} itself. "\prg_if_predicate_not_p:n"
%  reverses the truth value of a predicate test or a logic
%  operation. Thus
%  \begin{quote}
%  "\prg_if_predicate_not_p:n {\prg_if_predicate_not_p:n {\c_true}}"
%  \end{quote}
%  ultimately returns \m{true}.  The argument of the functions
%  "\prg_if_predicate_ors_p:n" and "\prg_if_predicate_ands_p:n" take a
%  list of predicate functions (and their arguments) and return either
%  \m{true} or \m{false}.
%  \end{function}
% 
%  \subsubsection{Generic loops}
%
%
%  \begin{function}{
%                   \prg_whiledo:nT |
%                   \prg_whiledo:nF |
%                   \prg_dowhile:nT |
%                   \prg_dowhile:nF |
%
%  }
%  \begin{syntax}
%     "\prg_whiledo:nT" "{"<test>"}" "{"\m{true}"}"  \\
%     "\prg_whiledo:nF" "{"<test>"}" "{"\m{false}"}"  
%  \end{syntax}
%  The "T" versions execute the \m{true} code as long as <test> is
%  true and the "F" versions execute the \m{false} code as long as
%  <test> is false. The "whiledo" functions execute the body after
%  testing the boolean and the "dowhile" functions executes the body
%  first and then tests the boolean. For the "T" versions, <test>
%  should end with a function executing only the \meta{true} code for
%  some test such as |\tlp_if_eq:NNT|. Similarly the "F" types should
%  end with |\tlp_if_eq:NNF|.
%  \end{function}
%
% \subsection{Sorting}
%
%
%  \begin{function}{
%                   \prg_quicksort:n |
%  }
%  \begin{syntax}
%    "\prg_quicksort:n" "{" "{"<element~1>"}" "{"<element~2>"}"
%      \dots\space "{"<element~n>"}" "}"
%  \end{syntax}
%  Performs a Quicksort on the token list. The comparisons are
%  performed by the function |\prg_quicksort_compare:nnTF| which is up
%  to the programmer to define. When the sorting process is over, all
%  elements are given as argument to the function
%  |\prg_quicksort_function:n| which the programmer also controls.
%  \end{function}
%
%  \begin{function}{
%                   \prg_quicksort_function:n |
%                   \prg_quicksort_compare:nnTF
%  }
%  \begin{syntax}
%    "\prg_quicksort_function:n" "{"<element>"}" \\
%    "\prg_quicksort_compare:nnTF" "{"<element 1>"}" "{"<element 2>"}"\\
%  \end{syntax}
%  The two functions the programmer must define before calling
%  |\prg_quicksort:n|. As an example we could define
% \begin{quote}
% |\def:NNn\prg_quicksort_function:n 1{{#1}}|\\
% |\def:NNn\prg_quicksort_compare:nnTF 2{\num_compare:nNnTF{#1}>{#2}}|
% \end{quote}
% Then the function call
% \begin{quote}
% |\prg_quicksort:n {876234520}|
% \end{quote}
% would return |{0}{2}{2}{3}{4}{5}{6}{7}{8}|. An alternative example
% where one sorts a list of words, |\prg_quicksort_compare:nnTF| could
% be defined as
% \begin{quote}
% |\def:NNn\prg_quicksort_compare:nnTF 2{|\\
% |  \num_compare:nNnTF{\tlist_compare:nn{#1}{#2}}>\c_zero }|
% \end{quote}
% 
%  \end{function}
%
%
% \StopEventually{}
%
% \subsection{The Implementation}
%
%
%    We start by ensuring that the required packages are loaded.
%    \begin{macrocode}
%<*package>
\RequirePackage{l3quark}
\RequirePackage{l3toks}
\RequirePackage{l3int}
%</package>
%<*initex|package>
%    \end{macrocode}
%
%
%  \subsubsection{Choosing modes}
%
%  \begin{macro}{\mode_vertical_p:}
%  \begin{macro}{\mode_vertical:TF}
%  \begin{macro}{\mode_vertical:T}
%  \begin{macro}{\mode_vertical:F}
%  For testing vertical mode.
%    \begin{macrocode}
\def_new:Npn \mode_vertical_p: {
  \if_mode_vertical: \c_true \else: \c_false\fi:}
\def_test_function_new:npn{mode_vertical:}{\if_mode_vertical:}
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%
%  \begin{macro}{\mode_horizontal_p:}
%  \begin{macro}{\mode_horizontal:TF}
%  \begin{macro}{\mode_horizontal:T}
%  \begin{macro}{\mode_horizontal:F}
%  For testing horizontal mode.
%    \begin{macrocode}
\def_new:Npn \mode_horizontal_p: {
  \if_mode_horizontal: \c_true \else: \c_false\fi:}
\def_test_function_new:npn{mode_horizontal:}{\if_mode_horizontal:}
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%
%  \begin{macro}{\mode_inner_p:}
%  \begin{macro}{\mode_inner:TF}
%  \begin{macro}{\mode_inner:T}
%  \begin{macro}{\mode_inner:F}
%  For testing inner mode.
%    \begin{macrocode}
\def_new:Npn \mode_inner_p: {
  \if_mode_inner: \c_true \else: \c_false\fi:}
\def_test_function_new:npn{mode_inner:}{\if_mode_inner:}
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%
%  \begin{macro}{\mode_math:TF}
%  \begin{macro}{\mode_math:T}
%  \begin{macro}{\mode_math:F}
%  For testing math mode. Uses the kern-save |\scan_align_safe_stop:|.
%    \begin{macrocode}
\def_test_function_new:npn{mode_math:} {
  \scan_align_safe_stop:  \if_mode_math: }
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%
% \paragraph{Alignment safe grouping and scanning}
%
%
%  \begin{macro}{\group_align_safe_begin:}
%  \begin{macro}{\group_align_safe_end:}
%  \TeX's alignment structures present many problems. As Knuth says
%  himself in \emph{\TeX: The Program}: ``It's sort of a miracle
%  whenever |\halign| or |\valign| work, [\ldots]'' One problem relates
%  to commands that internally issues a |\cr| but also peek ahead for
%  the next character for use in, say, an optional argument. If the
%  next token happens to be a |&| with category code~4 we will get some
%  sort of weird error message because the underlying
%  |\tex_futurelet:D| will store the token at the end of the alignment
%  template. This could be a |&|$\sb4$ giving a message like
%  |! Misplaced \cr.| or even worse: it could be the |\endtemplate|
%  token causing even more trouble! To solve this we have to open a
%  special group so that \TeX{} still thinks it's on safe ground but at
%  the same time we don't want to introduce any brace group that may
%  find its way to the output. The following functions help with this
%  by using code documented only in Appendix~D of
%  \emph{The \TeX book}\dots
%    \begin{macrocode}
\def_new:Npn \group_align_safe_begin: {\if_false:{\fi:\if_num:w0=`}\fi:}
\def_new:Npn \group_align_safe_end:   {\if_num:w0=`{\fi:\if_false:}\fi:}
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%
%
%  \begin{macro}{\scan_align_safe_stop:}
%  When \TeX{} is in the beginning of an align cell (right after the
%  |\cr|) it is in a somewhat strange mode as it is looking ahead to
%  find an |\tex_omit:D| or |\tex_noalign:D| and hasn't looked at the
%  preamble yet. Thus an |\tex_ifmmode:D| test will always fail unless
%  we insert |\scan_stop:| to stop \TeX's scanning ahead. On the other
%  hand we don't want to insert a |\scan_stop:| every time as that will
%  destroy kerning between letters\footnote{Unless we enforce an extra
%  pass with an appropriate value of \texttt{\string\pretolerance}.}
%  Unfortunately there is no way to detect if we're in the beginning of
%  an alignment cell as they have different characteristics depending
%  on column number etc. However we \emph{can} detect if we're in an
%  alignment cell by checking the current group type and we can also
%  check if the previous node was a character or ligature. What is done
%  here is that |\scan_stop:| is only inserted iff a)~we're in the
%  outer part of an alignment cell and b)~the last node \emph{wasn't} a
%  char node or a ligature node.
%    \begin{macrocode}
\def_new:Npn \scan_align_safe_stop: {
  \num_compare:nNnT \etex_currentgrouptype:D = \c_six
  {
    \num_compare:nNnF \etex_lastnodetype:D = \c_zero
    {
      \num_compare:nNnF \etex_lastnodetype:D = \c_seven
        \scan_stop:
    }
  }
}
%    \end{macrocode}
%  \end{macro}
%
% \subsubsection{Making $n$ copies}
% 
% \begin{macro}{\prg_replicate:nn}
% \begin{macro}{\prg_replicate_aux:N}
% \begin{macro}{\prg_replicate_first_aux:N}
% This function uses a cascading csname technique by David Kastrup
% (who else :-)
% 
% The idea is to make the input "25" result in first adding five, and
% then 20 copies of the code to be replicated. The technique uses
% cascading csnames which means that we start building several csnames
% so we end up with a list of functions to be called in reverse
% order. This is important here (and other places) because it means
% that we can for instance make the function that inserts five copies
% of something to also hand down ten to the next function in
% line. This is exactly what happens here: in the example with "25"
% then the next function is the one that inserts two copies but it
% sees the ten copies handed down by the previous function. In order
% to avoid the last function to insert say, 100 copies of the original
% argument just to gobble them again we define separate functions to
% be inserted first. Finally we must ensure that the cascade comes to
% a peaceful end so we make it so that the original csname \TeX{} is
% creating is simply "\use_noop:" expanding to nothing.
%
% This function has one flaw though: Since it constantly passes down
% ten copies of its previous argument it will severely affect the main
% memory once you start demanding hundreds of thousands of copies. Now
% I don't think this is a real limitation for any ordinary use. An
% alternative approach is to create a string of "m"'s with
% "\int_to_roman:w" which can be done with just four macros but that
% method has its own problems since it can exhaust the string
% pool. Also, it is considerably slower than what we use here so the
% few extra csnames are well spent I would say.
%    \begin{macrocode}
\def_new:Npn \prg_replicate:nn #1{
  \cs:w use_noop: 
  \exp_after:NN\prg_replicate_first_aux:N
  \int_use:N \int_eval:n{#1} \cs_end: 
  \cs_end: 
}
\def_new:Npn \prg_replicate_aux:N#1{
  \cs:w prg_replicate_#1:n\prg_replicate_aux:N
}
\def_new:Npn \prg_replicate_first_aux:N#1{
  \cs:w prg_replicate_first_#1:n\prg_replicate_aux:N
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% Then comes all the functions that do the hard work of inserting all
% the copies.
%    \begin{macrocode}
\def_new:Npn      \prg_replicate_ :n #1{}% no, this is not a typo!
\def_long_new:cpn {prg_replicate_0:n}#1{\cs_end:{#1#1#1#1#1#1#1#1#1#1}}
\def_long_new:cpn {prg_replicate_1:n}#1{\cs_end:{#1#1#1#1#1#1#1#1#1#1}#1}
\def_long_new:cpn {prg_replicate_2:n}#1{\cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1}
\def_long_new:cpn {prg_replicate_3:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1}
\def_long_new:cpn {prg_replicate_4:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1#1}
\def_long_new:cpn {prg_replicate_5:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1#1#1}
\def_long_new:cpn {prg_replicate_6:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1#1#1#1}
\def_long_new:cpn {prg_replicate_7:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1#1#1#1#1}
\def_long_new:cpn {prg_replicate_8:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1#1#1#1#1#1}
\def_long_new:cpn {prg_replicate_9:n}#1{
  \cs_end:{#1#1#1#1#1#1#1#1#1#1}#1#1#1#1#1#1#1#1#1}
%    \end{macrocode}
%    Users shouldn't ask for something to be replicated once or even
%    not at all but\dots
%    \begin{macrocode}
\def_long_new:cpn {prg_replicate_first_0:n}#1{\cs_end: }
\def_long_new:cpn {prg_replicate_first_1:n}#1{\cs_end: #1}
\def_long_new:cpn {prg_replicate_first_2:n}#1{\cs_end: #1#1}
\def_long_new:cpn {prg_replicate_first_3:n}#1{\cs_end: #1#1#1}
\def_long_new:cpn {prg_replicate_first_4:n}#1{\cs_end: #1#1#1#1}
\def_long_new:cpn {prg_replicate_first_5:n}#1{\cs_end: #1#1#1#1#1}
\def_long_new:cpn {prg_replicate_first_6:n}#1{\cs_end: #1#1#1#1#1#1}
\def_long_new:cpn {prg_replicate_first_7:n}#1{\cs_end: #1#1#1#1#1#1#1}
\def_long_new:cpn {prg_replicate_first_8:n}#1{\cs_end: #1#1#1#1#1#1#1#1}
\def_long_new:cpn {prg_replicate_first_9:n}#1{\cs_end: #1#1#1#1#1#1#1#1#1}
%    \end{macrocode} 
%
%
%
%
% \begin{macro}{\prg_stepwise_function:nnnN}
% \begin{macro}{\prg_stepwise_function_incr:nnnN}
% \begin{macro}{\prg_stepwise_function_decr:nnnN}
%   A stepwise function. Firstly we check the direction of the steps
%   |#2| since that will depend on which test we should use. If the
%   step is positive we use a greater than test, otherwise a less than
%   test.  If the test comes out true exit, otherwise perform |#4|,
%   add the step to |#1| and try again with this new value of |#1|.
%    \begin{macrocode}
\def_long_new:NNn \prg_stepwise_function:nnnN 2{
  \num_compare:nNnTF{#2}<\c_zero
  {\exp_args:No\prg_stepwise_function_decr:nnnN }
  {\exp_args:No\prg_stepwise_function_incr:nnnN }
  {\int_use:N\int_eval:n{#1}}{#2}
}
\def_long_new:NNn \prg_stepwise_function_incr:nnnN 4{
  \num_compare:nNnF {#1}>{#3}
  {
    #4{#1}
    \exp_args:No \prg_stepwise_function_incr:nnnN 
    {\int_use:N\int_eval:n{#1 + #2}} 
    {#2}{#3}{#4}
  }
}
\def_long_new:NNn \prg_stepwise_function_decr:nnnN 4{
  \num_compare:nNnF {#1}<{#3}
  {
    #4{#1}
    \exp_args:No \prg_stepwise_function_decr:nnnN 
    {\int_use:N\int_eval:n{#1 + #2}} 
    {#2}{#3}{#4}
  }
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\l_prg_inline_level_int}
% \begin{macro}{\prg_stepwise_inline:nnnn}
% \begin{macro}{\prg_stepwise_inline_decr:nnnn}
% \begin{macro}{\prg_stepwise_inline_incr:nnnn}
%   This function uses the same approach as for instance
%   |\clist_map_inline:Nn| to allow arbitrary nesting. First construct
%   the special function and then call an auxiliary one which just
%   carries the newly constructed csname.
%    \begin{macrocode}
\int_new:N\l_prg_inline_level_int
\def_long_new:NNn\prg_stepwise_inline:nnnn 4{
  \int_incr:N \l_prg_inline_level_int
  \def:cpn{prg_stepwise_inline_\int_use:N\l_prg_inline_level_int :n}##1{#4}
  \num_compare:nNnTF {#2}<\c_zero
  {\exp_args:Nco \prg_stepwise_inline_decr:Nnnn }
  {\exp_args:Nco \prg_stepwise_inline_incr:Nnnn }
  {prg_stepwise_inline_\int_use:N\l_prg_inline_level_int :n} 
  {\int_use:N\int_eval:n{#1}} {#2} {#3}
  \int_decr:N \l_prg_inline_level_int
}
\def_long_new:NNn \prg_stepwise_inline_incr:Nnnn 4{
  \num_compare:nNnF {#2}>{#4}
  {
    #1{#2}
    \exp_args:NNo \prg_stepwise_inline_incr:Nnnn #1
    {\int_use:N\int_eval:n{#2 + #3}} {#3}{#4}
  }
}
\def_long_new:NNn \prg_stepwise_inline_decr:Nnnn 4{
  \num_compare:nNnF {#2}<{#4}
  {
    #1{#2}
    \exp_args:NNo \prg_stepwise_inline_decr:Nnnn #1
    {\int_use:N\int_eval:n{#2 + #3}} {#3}{#4}
  }
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\prg_stepwise_variable:nnnNn}
% \begin{macro}{\prg_stepwise_variable_decr:nnnNn}
% \begin{macro}{\prg_stepwise_variable_incr:nnnNn}
%   Almost the same as above. Just store the value in |#4| and execute
%   |#5|.
%    \begin{macrocode}
\def_long_new:NNn \prg_stepwise_variable:nnnNn 2 {
  \num_compare:nNnTF {#2}<\c_zero
  {\exp_args:No\prg_stepwise_variable_decr:nnnNn}
  {\exp_args:No\prg_stepwise_variable_incr:nnnNn}
  {\int_use:N\int_eval:n{#1}}{#2}
}
\def_long_new:NNn \prg_stepwise_variable_incr:nnnNn 5 {
  \num_compare:nNnF {#1}>{#3}
  {
    \def:Npn #4{#1} #5
    \exp_args:No \prg_stepwise_variable_incr:nnnNn
    {\int_use:N\int_eval:n{#1 + #2}}{#2}{#3}#4{#5}
  }
}
\def_long_new:NNn \prg_stepwise_variable_decr:nnnNn 5 {
  \num_compare:nNnF {#1}<{#3}
  {
    \def:Npn #4{#1} #5
    \exp_args:No \prg_stepwise_variable_decr:nnnNn
    {\int_use:N\int_eval:n{#1 + #2}}{#2}{#3}#4{#5}
  }
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
%
% \subsubsection{Booleans}
%  For normal booleans we set them to either "\c_true" or "\c_false"
%  and then use "\if:w" to choose the right branch. The functions
%  return either the TF, T, or F case \emph{after} ending the |\if:w|.
%  We only define the |N| versions here as the |c| versions can easily
%  be constructed with the expansion module.
%
%  \begin{macro}{\bool_new:N}
%  \begin{macro}{\bool_new:c}
%  \begin{macro}{\bool_set_true:N}
%  \begin{macro}{\bool_set_true:c}
%  \begin{macro}{\bool_set_false:N}
%  \begin{macro}{\bool_set_false:c}
%  \begin{macro}{\bool_gset_true:N}
%  \begin{macro}{\bool_gset_true:c}
%  \begin{macro}{\bool_gset_false:N}
%  \begin{macro}{\bool_gset_false:c}
%  Defining and setting a boolean is easy.
%    \begin{macrocode}
\def_new:Npn \bool_new:N #1   { \let_new:NN #1 \c_false }
\def_new:Npn \bool_new:c #1   { \let_new:cN #1 \c_false }
\def_new:Npn \bool_set_true:N   #1 { \let:NN  #1 \c_true }
\def_new:Npn \bool_set_true:c   #1 { \let:cN  #1 \c_true }
\def_new:Npn \bool_set_false:N  #1 { \let:NN  #1 \c_false }
\def_new:Npn \bool_set_false:c  #1 { \let:cN  #1 \c_false }
\def_new:Npn \bool_gset_true:N   #1 { \glet:NN  #1 \c_true }
\def_new:Npn \bool_gset_true:c   #1 { \glet:cN  #1 \c_true }
\def_new:Npn \bool_gset_false:N  #1 { \glet:NN  #1 \c_false }
\def_new:Npn \bool_gset_false:c  #1 { \glet:cN  #1 \c_false }
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%
%  \begin{macro}{\bool_set_eq:NN}
%  \begin{macro}{\bool_set_eq:Nc}
%  \begin{macro}{\bool_set_eq:cN}
%  \begin{macro}{\bool_set_eq:cc}
%  \begin{macro}{\bool_gset_eq:NN}
%  \begin{macro}{\bool_gset_eq:Nc}
%  \begin{macro}{\bool_gset_eq:cN}
%  \begin{macro}{\bool_gset_eq:cc}
%  Setting a boolean to another is also pretty easy.
%    \begin{macrocode}
\let_new:NN \bool_set_eq:NN \let:NN
\let_new:NN \bool_set_eq:Nc \let:Nc
\let_new:NN \bool_set_eq:cN \let:cN
\let_new:NN \bool_set_eq:cc \let:cc
\let_new:NN \bool_gset_eq:NN \glet:NN
\let_new:NN \bool_gset_eq:Nc \glet:Nc
\let_new:NN \bool_gset_eq:cN \glet:cN
\let_new:NN \bool_gset_eq:cc \glet:cc
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%
%  \begin{macro}{\l_tmpa_bool}
%  \begin{macro}{\g_tmpa_bool}
%  A few booleans just if you need them.
%    \begin{macrocode}
\bool_new:N \l_tmpa_bool
\bool_new:N \g_tmpa_bool
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%
%  \begin{macro}{\bool_if:NTF}
%  \begin{macro}{\bool_if:NT}
%  \begin{macro}{\bool_if:NF}
%  \begin{macro}{\bool_if:cTF}
%  \begin{macro}{\bool_if:cT}
%  \begin{macro}{\bool_if:cF}
%  Straight forward here.
%    \begin{macrocode}
\def_test_function_new:npn{bool_if:N}#1{\if:w #1}
\def_new:Npn \bool_if:cTF{\exp_args:Nc\bool_if:NTF}
\def_new:Npn \bool_if:cT{\exp_args:Nc\bool_if:NT}
\def_new:Npn \bool_if:cF{\exp_args:Nc\bool_if:NF}
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%
%  \begin{macro}{\bool_if_p:N}
%  \begin{macro}{\bool_if_p:c}
%  We also make a predicate function for the "bool" data type but since
%  we use "\c_true" and "\c_false" it's rather simple\dots{}
%  Not that there's anything wrong in simplicity -- on the contrary!
%    \begin{macrocode}
\def_new:Npn \bool_if_p:N #1 { #1 }
\let_new:NN \bool_if_p:c \cs_use:c
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%
%
%  \begin{macro}{\bool_whiledo:NT}
%  \begin{macro}{\bool_whiledo:cT}
%  \begin{macro}{\bool_whiledo:NF}
%  \begin{macro}{\bool_whiledo:cF}
%  A "while" loop where the boolean is tested before executing the
%  statement. The "NT" version executes the "T" part as long as the
%  boolean is true while the "NF" version executes the "F" part as
%  long as the boolean is false.
%    \begin{macrocode}
\def_long_new:Npn \bool_whiledo:NT #1 #2 {
  \bool_if:NT #1 {#2 \bool_whiledo:NT #1 {#2}}
}
\def_new:Npn \bool_whiledo:cT{\exp_args:Nc\bool_whiledo:NT}
\def_long_new:Npn \bool_whiledo:NF #1 #2 {
  \bool_if:NF #1 {#2 \bool_whiledo:NF #1 {#2}}
}
\def_new:Npn \bool_whiledo:cF{\exp_args:Nc\bool_whiledo:NF}
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%
%  \begin{macro}{\bool_dowhile:NT}
%  \begin{macro}{\bool_dowhile:cT}
%  \begin{macro}{\bool_dowhile:NF}
%  \begin{macro}{\bool_dowhile:cF}
%  A "do-while" loop where the body is performed at least once and the
%  boolean is tested after executing the body. Otherwise identical to
%  the above functions.
%    \begin{macrocode}
\def_long_new:Npn \bool_dowhile:NT #1 #2 {
  #2 \bool_if:NT #1 {\bool_dowhile:NT #1 {#2}}
}
\def_new:Npn \bool_dowhile:cT{\exp_args:Nc\bool_dowhile:NT}
\def_long_new:Npn \bool_dowhile:NF #1 #2 {
  #2 \bool_if:NF #1 {\bool_dowhile:NF #1 {#2}}
}
\def_new:Npn \bool_dowhiledo:cF{\exp_args:Nc\bool_dowhile:cF}
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%
%  \begin{macro}{\bool_double_if:NNnnnn}
%  \begin{macro}{\bool_double_if:cNnnnn}
%  \begin{macro}{\bool_double_if:Ncnnnn}
%  \begin{macro}{\bool_double_if:ccnnnn}
%    Execute |#3| iff TT, |#4| iff TF, |#5| iff FT and |#6| iff
%    FF. The name isn't that great but I'll have to think about
%    that. Ideally it should be something with |TF| since only one of
%    the cases is executed but we haven't got any naming scheme for
%    this kind of thing so for now I'll just stick to simple |nnnn|.
%    \begin{macrocode}
\def_new:Npn \bool_double_if:NNnnnn#1#2{
  \if_case:w \num_eval:w #1\scan_stop:
    \if_case:w \num_eval:w #2\scan_stop:
      \exp_after:NN\exp_after:NN\exp_after:NN \use_arg_i:nnnn
    \else:
      \exp_after:NN\exp_after:NN\exp_after:NN \use_arg_ii:nnnn
    \fi:
  \else:
    \if_case:w \num_eval:w #2\scan_stop:
      \exp_after:NN\exp_after:NN\exp_after:NN \use_arg_iii:nnnn
    \else:
      \exp_after:NN\exp_after:NN\exp_after:NN \use_arg_iv:nnnn
    \fi:
  \fi:
}
\def_new:Npn \bool_double_if:cNnnnn{\exp_args:Nc\bool_double_if:NNnnnn}
\def_new:Npn \bool_double_if:Ncnnnn{\exp_args:NNc\bool_double_if:NNnnnn}
\def_new:Npn \bool_double_if:ccnnnn{\exp_args:Ncc\bool_double_if:NNnnnn}
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%  \end{macro}
% \subsubsection{Generic testing}
%
% \begin{macro}{\prg_whiledo:nT}
% \begin{macro}{\prg_whiledo:nF}
% \begin{macro}{\prg_dowhile:nT}
% \begin{macro}{\prg_dowhile:nF}
%   We provide these four generic while loops. |#1| is a test function
%   and for the |T| functions it should be a test function ending with
%   just the true case. Similar for the |F| types.
%    \begin{macrocode}
\def_long_new:Npn \prg_whiledo:nT #1#2{
  #1 {#2 \prg_whiledo:nT {#1}{#2}}
}
\def_long_new:Npn \prg_whiledo:nF #1#2{
  #1 {#2 \prg_whiledo:nF {#1}{#2}}
}
\def_long_new:Npn \prg_dowhile:nT #1#2{
  #2 #1 {\prg_dowhile:nT {#1}{#2}}
}
\def_long_new:Npn \prg_dowhile:nF #1#2{
  #2 #1 {\prg_dowhile:nF {#1}{#2}}
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
%  \begin{macro}{\prg_if_predicate:nTF}
%  \begin{macro}{\prg_if_predicate:nT}
%  \begin{macro}{\prg_if_predicate:nF}
%  As the boolean type is actually a predicate function, the next ones
%  are just aliases.
%    \begin{macrocode}
\let_new:NN \prg_if_predicate:nTF \bool_if:NTF
\let_new:NN \prg_if_predicate:nT  \bool_if:NT
\let_new:NN \prg_if_predicate:nF  \bool_if:NF
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%
%
%  \begin{macro}{\prg_if_predicate_or_p:nn}
%  \begin{macro}{\prg_if_predicate_and_p:nn}
%  \begin{macro}{\prg_if_predicate_not_p:n}
%  The logic operations require a little more work. The idea is to have
%  the end result of the logic "and" and "or" functions return "00" and
%  "01" resp.\ to be used in an "\if:w" test. The arguments of the
%  functions are always something expanding to "\c_true" or "\c_false"
%  which is usually resulting from a predicate function or from another
%  logical operation. All the functions start with a "0" and depending
%  on the results of the tests return either "0" or "1" to the input
%  stream to form a new true or false statement.
%
%  The comments in the following is mostly to convince myseld of the
%  validity of the code.
%    \begin{macrocode}
\def_new:Npn \prg_if_predicate_or_p:nn #1#2{
%    \end{macrocode}
% Form a number of the input which is one of "0000", "0001", "0100", or
% "0101". If the truth value of both tests are false we get the "0101"
% else we get a number less than that. So we check if the number formed
% is less than $101$.
%    \begin{macrocode}
  \if_num:w #1#2<\c_hundred_one
%    \end{macrocode}
% If it is we put a "\c_true" back into the input stream.
%    \begin{macrocode}
    \c_true
  \else:
%    \end{macrocode}
% Otherwise we insert "\c_false".
%    \begin{macrocode}
    \c_false
  \fi:
}
%    \end{macrocode}
% The "and" function is a little different. Again we can have input of
% the types "0000", "0001", "0100", or "0101". As we require both
% values to be \m{true} in order to continue we simply check if the
% number formed by the input is "0" or not and then put the
% corresponding "0" or "1" back in the input stream as above. We could
% use "\if_num:w" for this test as well but that'll require us to read
% the additional "=\c_zero" which runs a little slower than using
% "\if_case:w" directly, so we use the latter.
%    \begin{macrocode}
\def_new:Npn \prg_if_predicate_and_p:nn #1#2{
  \if_case:w #1#2 ~
    \c_true
  \else:
    \c_false
  \fi:
}
%    \end{macrocode}
% The "not" function checks a single truth value and reverses it. Here
% we either get a "00" or "01". If the input equals "0" we put a "1"
% in the input stream, else we put a "0". Again we use "\if_case:w"
% because it's slightly faster.
%    \begin{macrocode}
\def_new:Npn \prg_if_predicate_not_p:n #1{
  \if_case:w #1 ~
    \c_false
  \or:
    \c_true
  \fi:
}
%    \end{macrocode}
%  \end{macro}
%  \end{macro}
%  \end{macro}
%
%
%  \begin{macro}{\prg_if_predicate_ors_p:n}
%  \begin{macro}{\prg_if_predicate_ands_p:n}
%  \begin{macro}{\prg_if_predicate_andor_aux:NNN}
%  \begin{macro}{\prg_if_predicate_andor_break:NNN }
%    For longer lists of predicates we can't rely on such structures
%    as above. The "\prg_if_predicate_ands_p:n" would have been easy to
%    program as simply
%  \begin{verbatim}
% \def_new:Npn \prg_if_predicate_and_p:n #1 {
%  0\tex_ifcase:D #1 ~ \exp_after:NN 0 \else: \exp_after:NN 1 \fi:
% }
%  \end{verbatim}
%  but this would fail with a "! Number too big." in case we were
%  testing six predicate functions where the first was false. This
%  would mean we would have to first convert the string from binary
%  into numerical and then check. While challenging and interesting
%  in itself (See \textsf{binhex}) it still imposes a restriction of
%  15 predicate functions\footnote{We would probably never hit that
%  limit but why create a restriction when we can avoid it?} and we
%  haven't dealt with the "or" case either.
%
%  The solution below expands a predicate function until |\c_false| or
%  |\c_true| are seen and expanded to |01| or |00| respectively. If
%  we're testing the logical AND operation, all predicate functions
%  must return \meta{true}; if they don't we can exit and return
%  \meta{false}. In an OR operation, we just need one predicate
%  function to return \meta{true}, the rest don't matter. Since every
%  expansion in the internal loop results in a result of either |00|
%  or |01|, we can test against this number to decide what to do.
%
%  First up is the top level functions.
%    \begin{macrocode}
\def_long_new:Npn \prg_if_predicate_ands_p:n #1{
  \exp_after:NN \prg_if_predicate_andor_aux:NNN \exp_after:NN \c_true
  \int_to_roman:w -`0 #1 \scan_stop: \scan_stop:
}
\def_long_new:Npn \prg_if_predicate_ors_p:n #1{
  \exp_after:NN \prg_if_predicate_andor_aux:NNN \exp_after:NN \c_false
  \int_to_roman:w -`0 #1 \scan_stop: \scan_stop:
}
%    \end{macrocode}
% When we reach the inner loop we have already expanded all tokens in
% the first predicate function as far as possible. This means that
% either are arguments |#2| and |#3| \emph{both} |\scan_stop:| or else
% |#2| is |0| and |#3| is |0| if the predicate returned \meta{true} or
% |1| if it returned \meta{false}. If we reached the end we return
% \meta{true} for the AND function and \meta{false} for the OR
% function. If |#3| is |0| and we are doing the OR test, we want to
% exit and return \meta{true}. If |#3| is |0| and we are in the AND
% test we must continue to check the remaining predicate functions. If
% |#3| is |1| and we are in the OR test we continue in case a later
% predicate function returns \meta{true}. Finally, if |#3| is |1| and
% we are in the AND test we can exit and return \meta{false} before
% deciding what to do.
%    \begin{macrocode}
\def_new:Npn \prg_if_predicate_andor_aux:NNN #1#2#3{
  \token_if_eq_meaning:NNTF \scan_stop: #2
  { #1 }
  { 
    \int_compare:nNnTF #3 = #1
    { \exp_after:NN \prg_if_predicate_andor_aux:NNN } 
    { \exp_after:NN \prg_if_predicate_andor_break:NNN }
    \exp_after:NN #1 \int_to_roman:w -`0
  }
}
%    \end{macrocode}
% The break loop is called when we know what the final outcome
% is. However we keep expanding because a)~we don't know which tokens
% we might have left dangling ahead and b)~it also provides error
% checking on the remaining predicate functions. |#1| is \meta{false}
% for the OR function and \meta{true} for the AND function so we
% reverse them here.
%    \begin{macrocode}
\def_new:Npn \prg_if_predicate_andor_break:NNN #1#2#3{
  \token_if_eq_meaning:NNTF \scan_stop: #2
  { \if:w #1\c_false\else:\c_true\fi: }
  {
    \exp_after:NN \prg_if_predicate_andor_break:NNN \exp_after:NN #1
    \int_to_roman:w -`0 
  }
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro} 
%
% \subsubsection{Sorting}
%
%
% \begin{macro}{\prg_define_quicksort:nnn}
%   |#1| is the name, |#2| and |#3| are the tokens enclosing the
%   argument. For the somewhat strange \meta{clist} type which doesn't
%   enclose the items but uses a separator we define it by hand
%   afterwards. When doing the first pass, the algorithm wraps all
%   elements in braces and then uses a generic quicksort which works
%   on token lists.
%
%   As an example
%   \begin{quote}
%   |\prg_define_quicksort:nnn{seq}{\seq_elt:w}{\seq_elt_end:w}|  
%   \end{quote}
%   defines the user function |\seq_quicksort:n| and furthermore
%   expects to use the two functions |\seq_quicksort_compare:nnTF|
%   which compares the items and |\seq_quicksort_function:n| which is
%   placed before each sorted item. It is up to the programmer to
%   define these functions when needed. For the |seq| type a sequence
%   is a token list pointer, so one additionally has to define
%   \begin{quote}
%     |\def:Npn \seq_quicksort:N{\exp_args:No\seq_quicksort:n}|
%   \end{quote}
%
%
%   For details on the implementation see ``Sorting in \TeX's Mouth''
%   by Bernd Raichle. Firstly we define the function for parsing the
%   ininital list and then the braced list afterwards.
%    \begin{macrocode}
\def_new:NNn \prg_define_quicksort:nnn 3 {
  \def_long:cNx{#1_quicksort:n}1{
    \exp_not:c{#1_quicksort_start_partition:w} ##1
    \exp_not:n{#2\q_nil#3\q_stop}
  }
  \def_long:cNx{#1_quicksort_braced:n}1{
    \exp_not:c{#1_quicksort_start_partition_braced:n} ##1
    \exp_not:N\q_nil\exp_not:N\q_stop
  }
  \def_long:cpx {#1_quicksort_start_partition:w} #2 ##1 #3{
    \exp_not:N \quark_if_nil:nT {##1}\exp_not:N \use_none_delimit_by_q_stop:w
    \exp_not:c{#1_quicksort_do_partition_i:nnnw} {##1}{}{} 
  }
  \def_long:cNx {#1_quicksort_start_partition_braced:n} 1 {
    \exp_not:N \quark_if_nil:nT {##1}\exp_not:N \use_none_delimit_by_q_stop:w
    \exp_not:c{#1_quicksort_do_partition_i_braced:nnnn} {##1}{}{} 
  }
%    \end{macrocode}
% Now for doing the partitions.
%    \begin{macrocode}
  \def_long:cpx {#1_quicksort_do_partition_i:nnnw} ##1##2##3 #2 ##4 #3 {
    \exp_not:N \quark_if_nil:nTF {##4} \exp_not:c {#1_do_quicksort_braced:nnnnw}
    {
      \exp_not:c{#1_quicksort_compare:nnTF}{##1}{##4}
      \exp_not:c{#1_quicksort_partition_greater_ii:nnnn}
      \exp_not:c{#1_quicksort_partition_less_ii:nnnn}
    }
    {##1}{##2}{##3}{##4}
  }
  \def_long:cNx {#1_quicksort_do_partition_i_braced:nnnn} 4 {
    \exp_not:N \quark_if_nil:nTF {##4} \exp_not:c {#1_do_quicksort_braced:nnnnw}
    {
      \exp_not:c{#1_quicksort_compare:nnTF}{##1}{##4}
      \exp_not:c{#1_quicksort_partition_greater_ii_braced:nnnn}
      \exp_not:c{#1_quicksort_partition_less_ii_braced:nnnn}
    }
    {##1}{##2}{##3}{##4}
  }
  \def_long:cpx {#1_quicksort_do_partition_ii:nnnw} ##1##2##3 #2 ##4 #3 {
    \exp_not:N \quark_if_nil:nTF {##4} \exp_not:c {#1_do_quicksort_braced:nnnnw}
    {
      \exp_not:c{#1_quicksort_compare:nnTF}{##4}{##1}
      \exp_not:c{#1_quicksort_partition_less_i:nnnn}
      \exp_not:c{#1_quicksort_partition_greater_i:nnnn}
    }
    {##1}{##2}{##3}{##4}
  }
  \def_long:cNx {#1_quicksort_do_partition_ii_braced:nnnn} 4 {
    \exp_not:N \quark_if_nil:nTF {##4} \exp_not:c {#1_do_quicksort_braced:nnnnw}
    {
      \exp_not:c{#1_quicksort_compare:nnTF}{##4}{##1}
      \exp_not:c{#1_quicksort_partition_less_i_braced:nnnn}
      \exp_not:c{#1_quicksort_partition_greater_i_braced:nnnn}
    }
    {##1}{##2}{##3}{##4}
  }
%    \end{macrocode}
% This part of the code handles the two branches in each
% sorting. Again we will also have to do it braced.
%    \begin{macrocode}
  \def_long:cNx {#1_quicksort_partition_less_i:nnnn} 4{
    \exp_not:c{#1_quicksort_do_partition_i:nnnw}{##1}{##2}{{##4}##3}}
  \def_long:cNx {#1_quicksort_partition_less_ii:nnnn} 4{
    \exp_not:c{#1_quicksort_do_partition_ii:nnnw}{##1}{##2}{##3{##4}}}
  \def_long:cNx {#1_quicksort_partition_greater_i:nnnn} 4{
    \exp_not:c{#1_quicksort_do_partition_i:nnnw}{##1}{{##4}##2}{##3}}
  \def_long:cNx {#1_quicksort_partition_greater_ii:nnnn} 4{
    \exp_not:c{#1_quicksort_do_partition_ii:nnnw}{##1}{##2{##4}}{##3}}
  \def_long:cNx {#1_quicksort_partition_less_i_braced:nnnn} 4{
    \exp_not:c{#1_quicksort_do_partition_i_braced:nnnn}{##1}{##2}{{##4}##3}}
  \def_long:cNx {#1_quicksort_partition_less_ii_braced:nnnn} 4{
    \exp_not:c{#1_quicksort_do_partition_ii_braced:nnnn}{##1}{##2}{##3{##4}}}
  \def_long:cNx {#1_quicksort_partition_greater_i_braced:nnnn} 4{
    \exp_not:c{#1_quicksort_do_partition_i_braced:nnnn}{##1}{{##4}##2}{##3}}
  \def_long:cNx {#1_quicksort_partition_greater_ii_braced:nnnn} 4{
    \exp_not:c{#1_quicksort_do_partition_ii_braced:nnnn}{##1}{##2{##4}}{##3}}
%    \end{macrocode}
% Finally, the big kahuna! This is where the sub-lists are sorted.
%    \begin{macrocode}
  \def_long:cpx {#1_do_quicksort_braced:nnnnw} ##1##2##3##4\q_stop {
    \exp_not:c{#1_quicksort_braced:n}{##2}
    \exp_not:c{#1_quicksort_function:n}{##1}
    \exp_not:c{#1_quicksort_braced:n}{##3}
  }
}
%    \end{macrocode}
% \end{macro}
%
%
% \begin{macro}{\prg_quicksort:n}
%   A simple version. Sorts a list of tokens, uses the function
%   |\prg_quicksort_compare:nnTF| to compare items, and places the
%   function |\prg_quicksort_function:n| in front of each of them.
%    \begin{macrocode}
\prg_define_quicksort:nnn {prg}{}{}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\prg_quicksort_function:n}
% \begin{macro}{\prg_quicksort_compare:nnTF}
%    \begin{macrocode}
\let:NN \prg_quicksort_function:n \ERROR
\let:NN \prg_quicksort_compare:nnTF \ERROR
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
%
%  That's it (for now).
%    \begin{macrocode}
%</initex|package>
%<*showmemory>
\showMemUsage
%</showmemory>
%    \end{macrocode}
%
% \endinput
%
% $Log$
% Revision 1.19  2006/08/08 10:26:09  morten
% Fixed bugs in stepwise functions
%
% Revision 1.18  2006/07/30 14:41:28  morten
% Added stepwise functions (loops going from i to k with step of j) plus quicksort.
%
% Revision 1.17  2006/07/06 14:57:13  morten
% Moved code in the `miscellaneus' section to l3basics.
%
% Revision 1.16  2006/06/03 18:55:12  morten
% Added special double boolean switches.
%
% Revision 1.15  2006/03/20 18:26:38  braams
% Updated the copyright notice (2006) and demoted all implementation
% sections to subsections and so on to clean up the toc for source3.tex
%
% Revision 1.14  2006/01/19 22:31:56  morten
% Added \bool_set_eq:NN functions plus made function collection
% complete.
%
% Revision 1.13  2006/01/04 00:58:17  morten
% Added generic loops. Changed some names plus syntax for some of the
% logical operations. Added code for defining functions with specified
% number of arguments.
%
% Revision 1.12  2005/12/27 10:01:55  morten
% Changed RCS information retrieval. Moved tlist code to l3tlp. Added
% code for inserting n copies of something. Changed \bool_while to
% \bool_whiledo.
%
% Revision 1.11  2005/04/25 15:01:59  morten
% Fixed some names. Improved \peek_char_generic:NNTF to not use token registers.
%
% Revision 1.10  2005/04/23 14:36:12  morten
% Changed \c_left|right_brace_token to \c_group_begin_token and
% \c_group_end_token. Fixed definitions of \tlist_if_head_XXX functions.
% Added example for PR/3080.
%
% Revision 1.9  2005/04/09 21:08:43  morten
% Documentation blunders fixed
%
% Revision 1.8  2005/04/06 21:27:15  morten
% More tlist functions, Moved \engine_aleph:TF to l3basics, new peek-ahead functions, definitions of implicit characters.
%
% Revision 1.7  2005/03/26 21:11:14  morten
% Fix typo in \scan_align_safe_stop:
%
% Revision 1.6  2005/03/22 23:23:30  morten
% Moved \tlist_ functions from l3basics. Added align-safe versions of important functions. Reorganized documentation slightly.
%
% Revision 1.5  2005/03/16 22:36:10  braams
% Added the tweaks necessary to be able to load with initex
%
% Revision 1.4  2005/03/11 21:28:20  braams
% Fixed the use of RCS information; added \StopEventually
%