Stack.hpp

Go to the documentation of this file.

/*****************************************************************************
 * Copyright (C) 2011 by Benjamin Hadorn (b_hadorn@bluewin.ch)
 *****************************************************************************
 * Project    : Zeus Base Library
 * Module     : Stack
 * Package    : Zeus.ZeusBase.System
 * Author     : Benjamin Hadorn
 * Date       : 27.12.2011
 * System     : Zeus-Framework
 *****************************************************************************
 * Licence:                                                                  *
 *   This library is free software; you can redistribute it and/or modify    *
 *   it under the terms of the GNU Lesser General Public License as          *
 *   published by the Free Software Foundation; either version               *
 *   2.1 of the License, or (at your option) any later version.              *
 *                                                                           *
 *   This library is distributed in the hope that it will be useful,         *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of          *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the            *
 *   GNU Lesser General Public License for more details.                     *
 *                                                                           *
 *   You should have received a copy of the GNU Lesser General Public        *
 *   License along with this library; if not, write to the Free Software     *
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110, USA    *
 *****************************************************************************/

/*****************************************************************************
 * Changes:
 *  27.12.2011 bha: created zeus 2.0
 *****************************************************************************/

#ifndef StackHPP
#define StackHPP

#ifdef _MSC_VER
  #pragma warning(push, 1)
#endif

#include <stddef.h>

#ifdef _MSC_VER
  #pragma warning(pop)
#endif


#include <string.h>
#include <zeusbase/System/Interfaces/IStack.hpp>
#include <zeusbase/System/Iterators.hpp>

BEGIN_NAMESPACE_Zeus

/******************************************************************************/
/******************************************************************************/
template <class T> class TStack : public IStack<T>
{
  public:
    TStack();
    TStack(const T& rEmptyObject);
    virtual ~TStack();

    //Methods of IStack
    virtual void MQUALIFIER copyToStack(IStack<T>& rStack) const;
    virtual void MQUALIFIER copyToList(IList<T>& rList) const;
    virtual void MQUALIFIER flush();
    virtual Int MQUALIFIER getCount() const;
    virtual bool MQUALIFIER hasItem(const T& rItem) const;
    virtual bool MQUALIFIER hasAllItems(const IList<T>& rlstItems) const;
    virtual bool MQUALIFIER isEmpty() const;
    virtual void MQUALIFIER push(const T& rData);
    virtual void MQUALIFIER pushAll(const IList<T>& rlstItems);
    virtual T MQUALIFIER pop();
    virtual T& MQUALIFIER peek();

    //operators
    TStack<T>& operator=(const TStack<T>& rStack);
    TStack<T>& operator=(const IStack<T>& rStack);

  protected:
    T getItem(Int iIndex) const;

  private:
    /*********************************************************************/
    /*********************************************************************/
    struct TBaseElement
    {
      inline TBaseElement(T data, TBaseElement* next)
      {
        Data = data;
        Next = next;
      }

      T Data;
      TBaseElement* Next;
    };

    /*********************************************************************/
    /* COMPILER PROBLEM:
       Change this if a compiler fails with : m_tEmpty(T()) (see constructors)

    #ifdef A_COMPILER_TYPE
    static const T& getDefaultEmpty()
    {
        static const T Empty; // is initialized by compiler
        return Empty;
    }
    #endif

    */

    TBaseElement* m_pElHead;
    Int m_iSize;
    T m_EmptyObject;
};


/******************************************************************************/
/******************************************************************************/
template <class T> inline TStack<T>::TStack()
 /* COMPILER PROBLEM*/
 /*#ifdef A_COMPILER_TYPE
    : m_EmptyObject(getDefaultEmpty())
   #else
    : m_EmptyObject(T())
   #endif
*/
  : m_EmptyObject(T())
{
  m_pElHead = NULL;
  m_iSize = 0;

  // DO NOT USE MEMSET. This causes memory leaks on complex objects
  //memset(&m_EmptyObject,0, sizeof(T));
}

/******************************************************************************/
/******************************************************************************/
template <class T> inline TStack<T>::TStack(const T& rEmptyItem)
 : m_EmptyObject(rEmptyItem)
{
  m_pElHead = NULL;
  m_iSize = 0;
}

/******************************************************************************/
/******************************************************************************/
template <class T> inline TStack<T>::~TStack()
{
  flush();
  m_pElHead = NULL;
}


/******************************************************************************/
/******************************************************************************/
template <class T> T TStack<T>::getItem(Int iIndex) const
{
  T tRetval = m_EmptyObject;
  if (m_pElHead != NULL && iIndex >= 0 && iIndex < m_iSize)
  {
    TBaseElement* pActElement = m_pElHead;
    Int iCount = 0;
    while(iCount <= iIndex && pActElement != NULL)
    {
      pActElement = pActElement->Next;
      ++iCount;
    }

    if (pActElement != NULL)
    {
      tRetval = pActElement->Data;
    }
  }
  return tRetval;
}

/******************************************************************************/
/******************************************************************************/
template <class T> void MQUALIFIER TStack<T>::flush()
{
  while(m_pElHead != NULL)
  {
    TBaseElement* next = m_pElHead->Next;
    delete m_pElHead;
    m_pElHead = next;
  }
  m_iSize = 0;
}

/******************************************************************************/
/******************************************************************************/
template <class T> bool MQUALIFIER TStack<T>::hasItem(const T& rItem) const
{
  bool bRetval = false;
  TBaseElement* pActElement = m_pElHead;
  while(pActElement != NULL && !bRetval)
  {
    bRetval = (pActElement->Data == rItem);
    pActElement = pActElement->Next;
  }
  return bRetval;
}

/******************************************************************************/
/******************************************************************************/
template <class T> inline bool MQUALIFIER TStack<T>::hasAllItems(const IList<T>& rlstItems) const
{
  bool bRetval = true;
  TConstIterator<T> It = rlstItems.getConstIterator();
  while(bRetval && It.hasNextItem())
  {
    bRetval &= this->hasItem(It.getNextItemConst());
  }
  return bRetval;
}

/******************************************************************************/
/******************************************************************************/
template <class T> inline void MQUALIFIER TStack<T>::push(const T& data)
{
  m_pElHead = new TBaseElement(data, m_pElHead);
  m_iSize++;
}

/******************************************************************************/
/******************************************************************************/
template <class T> inline void MQUALIFIER TStack<T>::pushAll(const IList<T>& rlstItems)
{
  TConstIterator<T> It = rlstItems.getConstIterator();
  while(It.hasNextItem())
  {
    this->push(It.getNextItemConst());
  }
}


/******************************************************************************/
/******************************************************************************/
template <class T> T MQUALIFIER TStack<T>::pop()
{
  if (m_pElHead != NULL)
  {
    T retval = m_pElHead->Data;
    TBaseElement* del = m_pElHead;
    m_pElHead = m_pElHead->Next;
    delete del;
    m_iSize--;
    return retval;
  }
  else
  {
    return m_EmptyObject;
  }
}


/******************************************************************************/
/******************************************************************************/
template <class T> inline T& MQUALIFIER TStack<T>::peek()
{
  if (m_pElHead != NULL)
  {
    return m_pElHead->Data;
  }
  else
  {
    return m_EmptyObject;
  }
}

/******************************************************************************/
/******************************************************************************/
template <class T> inline Int MQUALIFIER TStack<T>::getCount() const
{
  return m_iSize;
}


/******************************************************************************/
/******************************************************************************/
template <class T> inline bool MQUALIFIER TStack<T>::isEmpty() const
{
  return (m_iSize == 0);
}


/******************************************************************************/
/******************************************************************************/
template <class T> void MQUALIFIER TStack<T>::copyToStack(IStack<T>& rStack) const
{
  TStack<T> stackTemp;

  TBaseElement* pActElement = m_pElHead;
  while(pActElement != NULL)
  {
    stackTemp.push(pActElement->Data);
    pActElement = pActElement->Next;
  }

  while(!stackTemp.isEmpty())
  {
    rStack.push(stackTemp.pop());
  }
}

/******************************************************************************/
/******************************************************************************/
template <class T> void MQUALIFIER TStack<T>::copyToList(IList<T>& rList) const
{
  TBaseElement* pActElement = m_pElHead;
  while(pActElement != NULL)
  {
    rList.add(pActElement->Data);
    pActElement = pActElement->Next;
  }
}

/******************************************************************************/
/******************************************************************************/
template <class T> inline TStack<T>& TStack<T>::operator=(const TStack<T>& rStack)
{
  rStack.copyToStack(*this);
  return *this;
}

/******************************************************************************/
/******************************************************************************/
template <class T> inline TStack<T>& TStack<T>::operator=(const IStack<T>& rStack)
{
  rStack.copyToStack(*this);
  return *this;
}

END_NAMESPACE_Zeus

#endif