source: src/stackclass.hpp@ 02da9e

#ifndef STACKCLASS_HPP_
#define STACKCLASS_HPP_

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 = (T *) Malloc(sizeof(T)*EntryCount, "StackClass::StackClass: **StackList");
};

/** Destructor of class StackClass.
 */
template <typename T> StackClass<T>::~StackClass()
{
        Free((void **)&StackList, "StackClass::StackClass: **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_*/