%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Id: IntegerListsLexClass.tex,v 1.1.1.3 2004/10/04 17:25:13 nthiery Exp $
% File:		lib/DOMAINS/CATEGORY/DOC/IntegerListsLexClass.tex
% Authors:	Nicolas M. Thiéry <nthiery@users.sourceforge.net>
% Purpose:	Documentation for the category Cat::IntegerListsLexClass
% Created:	Wed Sep  3 14:56:03 2003
% License:	LGPL
% Project:	MuPAD-Combinat, http://mupad-combinat.sf.net
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{Mhelppage}{IntegerListsLexClass}{Nicolas M. Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
%\Mproofread{...}{...}{...}

\begin{MInfo}
  \eng{the category of combinatorial classes based on
    \Mup{combinat::integerListsLexTools}}
\end{MInfo}

\begin{MIntro}
  \eng{\Mthis{} represents the category of combinatorial classes based on
    \Mup{combinat::integerListsLexTools}. It is used for lexicographic
    enumeration of list of integer verifying some constraints.}
  \eng{\Mwarn{This is an internal category. It is used by the special purpose
      domains \Mup{combinat::partitions}, \Mup{combinat::compositions}, and
      \Mup{combinat::integerVectors} which provide user-friendly interfaces.
    
      This documentation is only provided here for the curious reader as well
      as for developers. The interface is subject to incompatible changes
      anytime in the future. Use at your own risk.}}
\end{MIntro}

\MKeywords{combinatorics}

\begin{MCatConst}
  \MCall{}
\end{MCatConst}

\begin{MCategories}
  \Mup{Cat::CombinatorialClass}, \Mup{Cat::OrderedSet}
\end{MCategories}

\begin{MDetails}
  \eng{The purpose if this category is to provide an easy interface for
  \Mup{combinat::integerListsLexTools}. Refer to this documentation page for
  the description of the functionalities.}
  
  \eng{A \Mthis{} is a is a set of list of non-negative integers sharing the
    same set of constraints.}

  \eng{Here, we call \emph{integer list} a list \Mex{l} of nonnegative
    integers, its \emph{parts}. By abuse, infinite parts will be
    allowed in some cases. The \emph{length} of \Mex{l} is the number
    of its parts; the \emph{sum} of \Mex{l} is the sum of its parts.}
  
  \eng{Let \Mex{minSlope} be an integer or $\Mex{-infinity}$ and
    \Mex{maxSlope} be an integer or $\Mex{+infinity}$. Then an integer
    list is \emph{regular} w.r.t. \Mex{minSlope} and \Mex{maxSlope} if
    \Mex{minSlope <= l[i+1]-l[i] <= maxSlope}, for all \Mex{i}.
    Regular functions are defined similarly.}
  
  \eng{Let \Mex{f} be a function, and \Mex{l} an integer list. Then,
    \Mex{f} is an \emph{upper bound} (resp. \emph{lower bound}) for
    \Mex{l} if \Mex{l[i]<=f(i)} (resp. \Mex{f(i)<=l[i]}) for all
    \Mex{i}.}
  
  \eng{A set of constraints is specified by a sequence of $6$ objects
    \Mex{minLength, maxLength, floor, ceiling, minSlope, maxSlope} of
    the following types:
    \begin{itemize}
    \item \Mex{minLength}: nonnegative integer;
    \item \Mex{maxLength}: nonnegative integer or \Mex{+infinity};
    \item \Mex{floor} and \Mex{ceiling}: regular functions from
      \Mex{[1..maxLength]} to \Mex{0..+infinity};
    \item \Mex{minSlope}: integer or \Mex{-infinity};
    \item \Mex{maxSlope}: integer or \Mex{+infinity}.
    \end{itemize}
    
    The purpose of the domains belonging to \Mthis{} is to generate all the
    \emph{valid} integer lists of a given sum which satisfy all the specified
    constraints.}
  
  \eng{To build a domain \Mex{cl} that belongs to \Mthis{} the user must provide
    a procedure called \Mex{parseOptions} which take any argument describing
    the constraints and return the sequence of constraints as defined
    above. Then the category automatically implement the standard functions
    \Mex{isA}, \Mex{count}, \Mex{list}, \Mex{generator}, \Mex{first},
    \Mex{Next}, \Mex{last}, \Mex{previous}, \Mex{_less}. For the description
    of these functions see \Mup{Cat::CombinatorialClass}}
\end{MDetails}

\begin{MDomBasEntries}
  \MDomEntry{interfaceIntegerListsLexClass}
  \eng{The standard common interface of a domain that belongs to
    \Mthis. This is not really needed anymore.}
  \de{}
\end{MDomBasEntries}

\MTechMethods %----------------------------------------------------------------
\begin{MDetails}
  \eng{To help the writing of integers list classes, the following method is
    provided. It is not supposed to be called directly, but is
    rather here to provide default implementations.}
\end{MDetails}

\begin{MMethodDetails}{parseOptionsIntegerListsLexClass}
  \infoEng{Parse the standard options of an integers lists Class.}
  \infoDe{}
  \call{\Mtype{default constraints} t, \Mtype{extra constr.} c}
  
  \eng{Each constraint is given as an equation
    \Mex{\Mtype{contraints}=\Mtype{value}} where constraints is one of the
    following \Mex{MinLength},\Mex{MaxLength}, \Mex{Length}, \Mex{MinPart},
    \Mex{MaxPart}, \Mex{Inner}, \Mex{Outer}, \Mex{MinSlope}, \Mex{MaxSlope}.
    The set of default constraint is given as a table of such equations. Extra
    constraints are given as a sequence of such equation.}
\end{MMethodDetails}

%----------------------------------------------------------------

\begin{MExample}{intClass}
  \eng{Here is a way to define the domain of vector of zero and one of a given
    length with a given number of one. One only needs to provide the
    \Mex{parseOptions} functions}
  \begin{Mexin}
domain zeroOneVectors
    inherits Dom::BaseDomain;
    category Cat::IntegerListsLexClass;

    parseOptions :=
        proc(k)
        begin
            dom::parseOptionsIntegerListsLexClass
                   (table(Length   = k,
                          MinPart  = 0,
                          MaxPart  = 1,
                          Inner    = NIL,
                          Outer    = NIL,
                          MinSlope = -infinity,
                          MaxSlope = infinity
                         ),
                    args(2..args(0)));
        end_proc;
end_domain:
  \end{Mexin}

  \eng{Here is now the way to get the lists of such vectors of sum $2$ and
  length $4$.}
  \begin{Mexin}
zeroOneVectors::list(2, 4)
  \end{Mexin}
  \begin{Mexout}
[[1, 1, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1], [0, 1, 1, 0],

   [0, 1, 0, 1], [0, 0, 1, 1]]
  \end{Mexout}

  \eng{One can now add constraints to force some element to be equal to zero
  or one. Here is now the way to get the lists of such vectors of sum $4$ and
  length $6$, having zeros in position 1 and 3 and ending with a one.}
  \begin{Mexin}
zeroOneVectors::list(4, 8, Outer = [0, 1, 0, 1, 1, 1, 1, 1],
                           Inner = [0, 0, 0, 0, 0, 0, 0, 1])
  \end{Mexin}
  \begin{Mexout}
[[0, 1, 0, 1, 1, 0, 0, 1], [0, 1, 0, 1, 0, 1, 0, 1],

   [0, 1, 0, 1, 0, 0, 1, 1], [0, 1, 0, 0, 1, 1, 0, 1],

   [0, 1, 0, 0, 1, 0, 1, 1], [0, 1, 0, 0, 0, 1, 1, 1],

   [0, 0, 0, 1, 1, 1, 0, 1], [0, 0, 0, 1, 1, 0, 1, 1],

   [0, 0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 0, 1, 1, 1, 1]]
  \end{Mexout}
\end{MExample}

\begin{MChanges}
  \version{3.0}
  \eng[New category]{\Mthis{} is a new category} %
\end{MChanges}

\end{Mhelppage}
