source: src/stackclass.hpp@ 09048c

#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();
  bool IsFull();
  int ItemCount();
  void Output(ofstream *out) const;
  void TestImplementation(ofstream *out, T test);

  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)
{
  CurrentLastEntry = 0;
  CurrentFirstEntry = 0;
  NextFreeField = 0;
  EntryCount = dimension;
  StackList = Malloc<T>(EntryCount, "StackClass::StackClass: **StackList");
};

/** Destructor of class StackClass.
 */
template <typename T> StackClass<T>::~StackClass()
{
  Free(&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 {
    cerr << "ERROR: 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)
      cerr << "ERROR: 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
    cerr << "ERROR: 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)
      cerr << "ERROR: 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 {
    cerr << "ERROR: 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;
  cout << 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
        cout << 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
          cout << Verbose(5) << "Shifting item 0 to place " << EntryCount-1 << "." << endl;
          StackList[EntryCount-1] = StackList[0];
        } else {
          cout << 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
    cerr << "ERROR: 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;
};

/** Test the functionality of the stack.
 * \param *out ofstream for debugging
 * \param *test one item to put on stack
 * \return true - all tests worked correctly
 */
template <typename T> void StackClass<T>::TestImplementation(ofstream *out, T test)
{
  T Walker = test;
  *out << Verbose(1) << "Testing the snake stack..." << endl;
  for (int i=0;i<EntryCount;i++) {
    *out << Verbose(2) << "Filling " << i << "th element of stack." << endl;
    Push(Walker);
    Walker=Walker->next;
  }
  *out << endl;
  Output(out);
  if (IsFull())
    *out << "Stack is full as supposed to be!" << endl;
  else
    *out << "ERROR: Stack is not as full as supposed to be!" << endl;
  //if (StackList[(EntryCount+1)/2] != NULL) {
    *out << "Removing element in the middle ..." << endl;
    RemoveItem(StackList[(EntryCount+1)/2]);
    Output(out);
  //}
  //if (StackList[CurrentFirstEntry] != NULL) {
    *out << "Removing first element  ..." << endl;
    RemoveItem(StackList[CurrentFirstEntry]);
    Output(out);
  //}
  //if (StackList[CurrentLastEntry] != NULL) {
    *out << "Removing last element ..." << endl;
    RemoveItem(StackList[CurrentLastEntry]);
    Output(out);
  //}
  *out << "Clearing stack ... " << endl;
  ClearStack();
  Output(out);
  if (IsEmpty())
    *out << "Stack is empty as supposed to be!" << endl;
  else
    *out << "ERROR: Stack is not as empty as supposed to be!" << endl;
  *out << "done." << endl;
};

/** Puts contents of stack into ofstream \a *out.
 * \param *out ofstream for output
 */
template <typename T> void StackClass<T>::Output(ofstream *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()
{
  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()
{
  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()
{
  //cout << "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_*/