%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Id $
% File:		lib/ADT/DOC/Stack.tex
% Authors:	Nicolas M. Thiéry <nthiery@users.sourceforge.net>
% Purpose:	Documentation for the domain adt::Stack
% Created:	Tue Jan  6 09:04:13 2004
% License:	LGPL
% Project:	MuPAD-Combinat, http://mupad-combinat.sf.net
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{Mhelppage}{Stack}{Nicolas M. Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{nthiery}{28/09/2004}{reasonably complete, but not proofread}

\begin{MInfo}
  \eng{abstract datatype ``Stack''}
  \de{}
\end{MInfo}

\begin{MIntro}
  \eng{\Mthis{} implements the abstract data type ``Stack''.}
  \de{}
\end{MIntro}

\begin{MCalls}
  \call{stack}
\end{MCalls} % end of MCalls

\begin{MParameters}
  \param{queue}
    \eng{an \Mhref[stdlib,_exprseq]{expression sequence} of objects to initialize the stack}
%    \de {eine \Mhref[stdlib,_exprseq]{Sequenz von Ausdrücken} von Objekten zur Initialisierung
%         der ??? (\emph{Stack})}
\end{MParameters} % end of MParameters

\begin{MReturnValue}
  \eng{an object of the domain \Mthis}
  \de {ein Objekt des Domains \Mthis}
\end{MReturnValue} % end of MReturnValue

\MKeywords{abstract data type,stack}

\begin{MDetails}
  \eng{\Mthis\ implements the abstract data type ``Stack. To create a
    stack, an expression sequence of any \mupad\ objects can be given
    to initialize the queue, otherwise an empty stack is built.}

%  \de {\Mthis\ stellt den abstrakten Datentyp "`Schlange"' (\emph{Queue}) zur Verf"ugung.}
  
  \eng{\Mwarn{The methods of all \Mhref[adt]{abstract datatypes} must
      be called especially and will result in changing the object
      itself as sideeffect.}}
  
  \de {\Mwarn{Die Methoden aller \Mhref[adt]{abstrakter Datentypen}
      werden in besonderer Weise aufgerufen und ändern das Objekt
      selbst als Seiteneffekt.}}
  
  \eng{With \Mex{S := adt::Stack()} an empty stack is built and
    assigned to the variable \Mex{S}.}
  
  \eng{\Mwarn{\emph{All following methods changes the value of \Mex{S}
        itself.}  A new assignment to the variable (in this example
      \Mex{S}) is not necessary, in contrast to all other \mupad{}
      functions and data types.}}

  \begin{MMethodDetails}{S::empty}
    \infoEng{is the stack empty}
%    \infoDe {ist die Schlange leer}
    \call{}
    \eng{This method returns \Mup{TRUE}, if no element is in the
      stack, otherwise \Mup{FALSE}.}
%      \de {.}
  \end{MMethodDetails}

  \begin{MMethodDetails}{S::nops}
    \infoEng{size of the stack}
%    \infoDe {Länge der Schlange}
    \call{}
      \eng{This method returns the number of elements in the stack.}
%      \de {.}
  \end{MMethodDetails}

  \begin{MMethodDetails}{S::depth}
    \infoEng{depth of the stack}
%    \infoDe {Länge der Schlange}
    \call{}
      \eng{This method returns the number of elements in the stack
        (same as \Mup{nops}).}
%      \de {.}
  \end{MMethodDetails}

  \begin{MMethodDetails}{S::top}
    \infoEng{top element of the stack}
%    \infoDe {erstes Element der Schlange}
    \call{}
    \eng{This method returns the top element of the stack (the last
      added) \emph{without} removing it from the stack.}
%      \de {.}
  \end{MMethodDetails}

  \begin{MMethodDetails}{S::push}
    \infoEng{push an element on the stack}
%    \infoDe {Füllen der Schlange}
    \call{x}
    \eng{This method puts the element \Mpar{x} on top of the stack.}
%      \de {.}
  \end{MMethodDetails}

  \begin{MMethodDetails}{S::pop}
    \infoEng{pop an element from the stack}
%    \infoDe {Herausnehmen eines Elementes aus der Schlange}
    \call{}
    
    \eng{This method removes the top element of the queue (the last
      added) and returns it.}
%      \de {.}
  \end{MMethodDetails}

  \begin{MMethodDetails}{S::reverse}
    \infoEng{revert the stack}
%    \infoDe {Umdrehen der ???}
    \call{}
      \eng{This method reverses the order of all elements in the stack.}
%      \de {.}
  \end{MMethodDetails}

  \begin{MMethodDetails}{S::copy}
    \infoEng{copy of the stack}
%    \infoDe {Umdrehen der ???}
    \call{}
    \eng{This method returns an independent copy of the stack,
      breaking the reference effect.}
%      \de {.}
  \end{MMethodDetails}
\end{MDetails}


\begin{MExample}{ex-basic}
  \eng{We create an empty stack, and fill it with some values:}
  \begin{Mexin}
S := adt::Stack():
S::push(a): S::push(b): S::push(c):
  \end{Mexin}
  \eng{The stack now contains 3 elements:}
  \begin{Mexin}
S::nops();
S
  \end{Mexin}
  \begin{Mexout}
                               3

                      adt::Stack(a, b, c)
  \end{Mexout}

  \eng{The top of the stack is the last valued pushed:}
  \begin{Mexin}
S::top()
  \end{Mexin}
  \begin{Mexout}
                               c
  \end{Mexout}
  \eng{Now, we fetch successively the values contains in \Mex{S}; they
    come back in reversed order:}
  \begin{Mexin}
S::pop();
S::pop();
S::pop()
  \end{Mexin}
  \begin{Mexout}
                               c

                               b

                               a
  \end{Mexout}
  
  \eng{Now, the stack is empty. Trying to pop again an element from it
    results in a \Mup{FAIL} value being returned:}
  \begin{Mexin}
S::pop()
  \end{Mexin}
  \begin{Mexout}
                             FAIL
  \end{Mexout}

  \eng{Note that the output of very large stacks is truncated:}
  \begin{Mexin}
adt::Stack(i $ i = 1..20)
  \end{Mexin}
  \begin{Mexout}
    adt::Stack(..., 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
  \end{Mexout} %$
  \eng{You may customize the truncation threshold by setting
    \Mex{adt::Stack::printMaxSize} to the maximal number of elements
    to be output.}
\end{MExample}

\begin{MExample}{ex-infinite}
  \eng{Experimental feature: one may mimic a stack with infinite depth
    by providing functions to be called to pop or top an empty stack:}
  \begin{Mexin}
stack := adt::Stack::newExtended([a, b, c], f, g)
  \end{Mexin}
  \begin{Mexout}
                      adt::Stack(a, b, c)
  \end{Mexout}
  \eng{At first, the behavior is as usual:}
  \begin{Mexin}
stack::pop(), stack::depth();
stack::pop(), stack::depth();
stack::pop(), stack::depth();
  \end{Mexin}
  \begin{Mexout}
                             c, 2

                             b, 1

                             a, 0
  \end{Mexout}
  \eng{Now, the stack is empty; poping new elements results in \Mex{f}
    being called with the current depth of the stack:}
  \begin{Mexin}
stack::pop(), stack::depth();
stack::pop(), stack::depth();
stack::pop(), stack::depth()
  \end{Mexin}
  \begin{Mexout}
                           f(0), -1

                           f(-1), -2

                           f(-2), -3
  \end{Mexout}
  \eng{Similarly, calling \Mex{top} results in \Mex{g} being called:}
  \begin{Mexin}
stack::top()
  \end{Mexin}
  \begin{Mexout}
                             g(-3)
  \end{Mexout}
  \eng{We push an element on the stack, and then pop again a few
    of them:}
  \begin{Mexin}
stack::push(d):
stack::pop(), stack::depth();
stack::pop(), stack::depth();
stack::pop(), stack::depth()
  \end{Mexin}
  \begin{Mexout}
                             d, -3

                           f(-3), -4

                           f(-4), -5
  \end{Mexout}
\end{MExample}

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

\end{Mhelppage}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
