/*---------------------------------------------------------------------------*
 *                                   IT++                                    *
 *---------------------------------------------------------------------------*
 * Copyright (c) 1995-2002 by Tony Ottosson, Thomas Eriksson, Pål Frenger,   *
 * Tobias Ringström, and Jonas Samuelsson.                                   *
 *                                                                           *
 * Permission to use, copy, modify, and distribute this software and its     *
 * documentation under the terms of the GNU General Public License is hereby *
 * granted. No representations are made about the suitability of this        *
 * software for any purpose. It is provided "as is" without expressed or     *
 * implied warranty. See the GNU General Public License for more details.    *
 *---------------------------------------------------------------------------*/

/*! 
  \file 
  \brief Stack class (container)
  \author Thomas Eriksson
  
  This file is not separated into a .h and a .cpp file. The reason is to 
  avoid problems with template initializations of this class.
  An \c Stack<type> can contain any type and it is not possible 
  to initialize and pre-compile all types that might be put into an \c Stack.
  
  1.4

  2003/05/22 08:55:17
*/

#ifndef __stack_h
#define __stack_h

#include "itconfig.h"
#include "base/itassert.h"
#include <iostream>

namespace itpp {

  /*! 
    \brief General stack class
  
    This class is a general stack class for arbitrary types.
  
    For rarely used types you will need to instantiate the class by
    \code
    template class Stack<type>;
    \endcode
  
    The following example shows how to define a Stack of vectors:
    \code
    vec a = randn(10);
    vec b = randn(20);
    Stack<vec> my_stack(10);
    my_stack.push(a);
    my_stack.push(b);
  
    cout << my_stack.pop() << " " << my_stack.pop() << endl ;
    \endcode
  */
  template<class T>
    class Stack {
    public:
    //! Default constructor
    Stack();
    //! Create a Stack of size \c n
    Stack(int n);
    //! Create a copy of \c s
    Stack(const Stack<T> &s);
    //! Default destructor
    virtual ~Stack();

    //! Pop the topmost element of the stack
    T pop();
    //! Peek at the topmost element of the stack, without removing it
    T peek() const;
    //! Push an element at top of stack
    void push(T v);
    //! Empty the stack
    void clear();

    //! Assignment operator
    void operator=(const Stack<T> &s);

    //! Returns the maximum number of data elements the stack can store
    int size() const { return ndata; }
    //! Returns the number of data elements currently in the stack
    int no_elements() const { return valptr; }
    //! Resizing a Stack<T>.
    void set_size(int n, bool copy=false);

    private:
    int valptr;
    int ndata;
    T *data;

    private:
    void alloc(int n);
    void free();
  };

  // --------------------------- Implementation starts here ----------------------------------

  template<class T>
    Stack<T>::Stack()
    {
      data = 0;
      ndata = 0;
      valptr = 0;
    }

  template<class T>
    Stack<T>::Stack(int n)
    {
      alloc(n);
      valptr=0;
    }

  template<class T>
    Stack<T>::Stack(const Stack<T> &s)
    {
      data=NULL;
      ndata=0;
      valptr=s.valptr;
      alloc(s.ndata);
      for (int i=0; i<s.ndata; i++)
	data[i] = s.data[i];
    }

  template<class T>
    Stack<T>::~Stack()
    {
      free();
    }

  template <class T>
    T Stack<T>::pop()
    {
      it_error_if(valptr==0,"Stack<T>::pop: Empty stack");
      valptr--;
      return data[valptr];
    }

  template <class T>
    T Stack<T>::peek() const
    {
      it_error_if(valptr==0,"Stack<T>::peek: Empty stack");
      return data[valptr-1];
    }

  template <class T>
    void Stack<T>::push(T v)
    {
      it_error_if(valptr>=ndata,"Stack<T>::push: Full stack");
      data[valptr]=v;
      valptr++;
    }

  template <class T>
    void Stack<T>::clear()
    {
      valptr=0;
    }

  template<class T>
    void Stack<T>::alloc(int n)
    {
      if (n == 0) {
	data = NULL;
	ndata = 0;
      }
      else {
	data = new T[n];
	it_assert1(data!=0, "Out of memory in Stack::alloc");
      }
      ndata = n;
    }

  template<class T>
    void Stack<T>::free()
    {

      delete [] data;

      data = 0;
      ndata = 0;
    }

  template<class T>
    void Stack<T>::operator=(const Stack<T> &s)
    {
      set_size(s.ndata);
      for (int i=0; i<ndata; i++)
	data[i] = s.data[i];
      valptr=0;
    }

  template<class T>
    void Stack<T>::set_size(int sz, bool copy)
    {
      int i, min;
      T *tmp;

      if (ndata == sz)
	return;

      if (copy) {
	tmp = data;
	min = ndata < sz ? ndata : sz;
	alloc(sz);
	for (i=0; i<min; i++)
	  data[i] = tmp[i];
	delete [] tmp;
      } else {
	free();
	alloc(sz);
      }
      ndata = sz;
    }

} //namespace itpp

#endif // __Stack_h