source: src/stackclass.hpp@ 31b09e

#ifndef STACKCLASS_HPP_
#define STACKCLASS_HPP_

using namespace std;

/*********************************************** includes ***********************************/

// include config.h
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include "verbose.hpp"
#include "memoryallocator.hpp"

/****************************************** forward declarations *****************************/

template <typename T> class StackClass;

/******************************** Functions for class StackClass ********************************/

/* Stack of Stuff.
 * Is used during DepthFirstSearchAnalysis() to detect nonseparable components.
 */
template <typename T> class StackClass {
  public:
  StackClass<T>(int dimension);
  ~StackClass<T>();

  bool Push(T object);
  T PopFirst();
  T PopLast();
  bool RemoveItem(T ptr);
  void ClearStack();
  bool IsEmpty() const;
  bool IsFull() const;
  int ItemCount() const;
  void Output(ofstream * const out) const;

  private:
    T *StackList;   //!< the list containing the atom pointers
    int EntryCount;     //!< number of entries in the stack
    int CurrentLastEntry;   //!< Current last entry (newest item on stack)
    int CurrentFirstEntry;   //!< Current first entry (oldest item on stack)
    int NextFreeField;       //!< Current index of next free field
};

/** Constructor of class StackClass.
 */
template <typename T> StackClass<T>::StackClass(int dimension) : StackList(NULL), EntryCount(dimension), CurrentLastEntry(0), CurrentFirstEntry(0), NextFreeField(0)
{
  StackList = new T[EntryCount];
  for (int i=0;i<EntryCount;i++)
    StackList[i] = NULL;
};

/** Destructor of class StackClass.
 */
template <typename T> StackClass<T>::~StackClass()
{
  delete[](StackList);
};

/** Pushes an object onto the stack.
 * \param *object atom to be pushed on stack
 * \return true - sucess, false - failure, meaning stack field was occupied
 */
template <typename T> bool StackClass<T>::Push(T object)
{
  if (!IsFull()) {    // check whether free field is really not occupied
    StackList[NextFreeField] = object;
    CurrentLastEntry = NextFreeField;
    NextFreeField = (NextFreeField + 1) % EntryCount; // step on to next free field
    return true;
  } else {
    DoeLog(1) && (eLog()<< Verbose(1) << "Stack is full, " << "Stack: CurrentLastEntry " << CurrentLastEntry<< "\tCurrentFirstEntry " << CurrentFirstEntry << "\tNextFreeField " << NextFreeField << "\tEntryCount " << EntryCount << "!" << endl);
    return false;
  }
};

/** Pops first/oldest atom from stack.
 * First in, last out.
 * \return atom pointer from stack, NULL - if failure (no atom pointer in field)
 */
template <typename T> T StackClass<T>::PopFirst()
{
  T Walker = NULL;
  if (!IsEmpty()) {
    Walker = StackList[CurrentFirstEntry];
    if (Walker == NULL)
      DoeLog(1) && (eLog()<< Verbose(1) << "Stack's field is empty!" << endl);
    StackList[CurrentFirstEntry] = NULL;
    if (CurrentFirstEntry != CurrentLastEntry) { // hasn't last item been popped as well?
      CurrentFirstEntry = (CurrentFirstEntry + 1) % EntryCount; // step back from current free field to last used (somehow modulo does not work in -1)
    } else {
      CurrentFirstEntry = (CurrentFirstEntry + 1) % EntryCount; // step back from current free field to last used (somehow modulo does not work in -1)
      CurrentLastEntry = CurrentFirstEntry;
    }
  } else
    DoeLog(1) && (eLog()<< Verbose(1) << "Stack is empty!" << endl);
  return Walker;
};

/** Pops last element from stack.
 * First in, first out.
 * \return element pointer from stack, NULL - if failure (no atom pointer in field)
 */
template <typename T> T StackClass<T>::PopLast()
{
  T Walker = NULL;
  if (!IsEmpty()) {
    Walker = StackList[CurrentLastEntry];
    StackList[CurrentLastEntry] = NULL;
    if (Walker == NULL)
      DoeLog(1) && (eLog()<< Verbose(1) << "Stack's field is empty!" << endl);
    NextFreeField = CurrentLastEntry;
    if (CurrentLastEntry != CurrentFirstEntry)  // has there been more than one item on stack
      CurrentLastEntry = (CurrentLastEntry + (EntryCount-1)) % EntryCount; // step back from current free field to last (modulo does not work in -1, thus go EntryCount-1 instead)
  } else {
    DoeLog(1) && (eLog()<< Verbose(1) << "Stack is empty!" << endl);
  }
  return Walker;
};

/** Removes a certain item from the stack.
 * Item is seeked between \a CurrentFirstEntry and \a CurrentLastEntry, if found, place in stack is NULL'd and
 * all subsequent items shifted by one position downward (with wrapping taken into account).
 * \param *ptr adress of item
 * \return true - item was removed, false - item was not found
 */
template <typename T> bool StackClass<T>::RemoveItem(T ptr)
{
  bool found = false;
  DoLog(5) && (Log() << Verbose(5) << "First " << CurrentFirstEntry<< "\tLast " << CurrentLastEntry<< "\tNext " << NextFreeField<< "\tCount " << EntryCount<< "." << endl);
  int i=CurrentFirstEntry;
  if (!IsEmpty())
    do {
      if (StackList[i] == ptr) {  // if item found, remove
        DoLog(5) && (Log() << Verbose(5) << "Item " << *ptr << " was number " << i << " on stack, removing it." << endl);
        found = true;
        StackList[i] = NULL;
      }
      if ((found) && (StackList[i] != NULL)) {  // means we have to shift (and not the removed item)
        if (i == 0) { // we are down to first item in stack, have to put onto last item
          DoLog(5) && (Log() << Verbose(5) << "Shifting item 0 to place " << EntryCount-1 << "." << endl);
          StackList[EntryCount-1] = StackList[0];
        } else {
          DoLog(5) && (Log() << Verbose(5) << "Shifting item " << i << " to place " << i-1 << "." << endl);
          StackList[i-1] = StackList[i];
        }
      }
      i=((i + 1) % EntryCount); // step on
    } while (i!=NextFreeField);
  else
    DoeLog(1) && (eLog()<< Verbose(1) << "Stack is already empty!" << endl);
  if (found) {
    NextFreeField = CurrentLastEntry;
    if (CurrentLastEntry != CurrentFirstEntry)  // has there been more than one item on stack
      CurrentLastEntry = (CurrentLastEntry + (EntryCount-1)) % EntryCount;
  }
  return found;
};


/** Puts contents of stack into ofstream \a *out.
 * \param *out ofstream for output
 */
template <typename T> void StackClass<T>::Output(ofstream * const out) const
{
  *out << "Contents of Stack: ";
  for(int i=0;i<EntryCount;i++) {
    *out << "\t";
    if (i == CurrentFirstEntry)
      *out << " 1";
    if  (i == CurrentLastEntry)
      *out << " "<< EntryCount;
    if (i ==  NextFreeField)
      *out << " F";
    *out << ": " << StackList[i];
  }
  *out << endl;
};

/** Checks whether stack is empty.
 * Simply checks whether StackClass::NextFreeField is equal to StackClass::CurrentFirstEntry and
 * StackClass::CurrentFirstEntry is equal to StackClass::CurrentLastEntry.
 * \return true - empty, false - not
 */
template <typename T> bool StackClass<T>::IsEmpty() const
{
  return((NextFreeField == CurrentFirstEntry) && (CurrentLastEntry == CurrentFirstEntry));
};

/** Checks whether stack is full.
 * Simply checks whether StackClass::NextFreeField is equal to StackClass::CurrentFirstEntry and
 * StackClass::CurrentFirstEntry is _not_ equal to StackClass::CurrentLastEntry.
 * \return true - full, false - not
 */
template <typename T> bool StackClass<T>::IsFull() const
{
  return((NextFreeField == CurrentFirstEntry) && (CurrentLastEntry != CurrentFirstEntry));
};

/** Returns number of items on stack.
 * Simply returns difference between StackClass::Stacklist entry StackClass::CurrentEntry-1.
 * \return number of items on stack
 * \warning will never return correct item count if stack is full, i.e. count would be StackClass::EntryCount.
 */
template <typename T> int StackClass<T>::ItemCount() const
{
  //Log() << Verbose(0) << "Stack: CurrentLastEntry " << CurrentLastEntry<< "\tCurrentFirstEntry " << CurrentFirstEntry << "\tEntryCount " << EntryCount << "." << endl;
  return((NextFreeField + (EntryCount - CurrentFirstEntry)) % EntryCount);
};

/** Clears the stack from all atoms.
 * \return true - sucess, false - failure
 */
template <typename T> void StackClass<T>::ClearStack()
{
  for(int i=EntryCount; i--;)
    StackList[i] = NULL;
  CurrentFirstEntry = 0;
  CurrentLastEntry = 0;
  NextFreeField = 0;
};



#endif /*STACKCLASS_HPP_*/