stack.h

Go to the documentation of this file.

// ============================================================================
// Project:     Deductive Database
// Filename:    stack.h
// Purpose:     Simple Stack Implementation (Class Template)
// Last Change: 04.08.2017
// Language:    C++
// EMail:       brass@informatik.uni-halle.de
// WWW:         http://www.informatik.uni-halle.de/~brass/
// Address:     Feldschloesschen 15, D-06120 Halle (Saale), GERMANY
// Copyright:   (c) 2010-2017 by Stefan Brass
// License:     See file "LICENSE" for copying conditions.
// Note:        There is no warranty at all - this code may contain bugs.
// ============================================================================


//=============================================================================
// Include File Frame:
//=============================================================================

#ifndef STACK_INCLUDED
#define STACK_INCLUDED

//=============================================================================
// Used Types and Macros:
//=============================================================================

#ifndef VER_INCLUDED
#include "../base/ver.h"
#endif

#ifndef STR_INCLUDED
#include "../base/str.h"
#endif

#ifndef CHECK_INCLUDED
#include "../base/check.h"
#endif


//=============================================================================
// Private Constants:
//=============================================================================

//-----------------------------------------------------------------------------
// STACK_MAGIC: Magic number (identifies objects of this class).
//-----------------------------------------------------------------------------

static const long STACK_MAGIC = 0x53544B0AL;    // 'STK\n'

//-----------------------------------------------------------------------------
// STACK_SIZE: Size of the array (maximal number of stack elements).
//-----------------------------------------------------------------------------

// Usually sufficient:
// static const int STACK_SIZE = 10000;

// For wine ontology benchmark:
//static const int STACK_SIZE = 100000;

//=============================================================================
// Class Template for Stacks (Simple Implementation with Fixed Size Array):
//=============================================================================

template<class T, int STACK_SIZE = 10000> class stack_c {
        public:

//-----------------------------------------------------------------------------
// Constructor, Destructor:
//-----------------------------------------------------------------------------

        // Constructor:
        explicit stack_c(str_t name)
        {
                // Check parameter:
                CHECK(name != STR_NULL, "stack_c::constructor: name is null");

                // Initialize attributes:
                Name     = name;
                NumElems = 0;
                StackPtr = Stack;

                // Set Magic number:
                CHECK_CODE(Magic = STACK_MAGIC);
        }

        // Destructor:
        ~stack_c()
        {
                // Check this object:
                CHECK_VALID("stack_c::destructor");

                // Make this object invalid:
                CHECK_CODE(Magic = 0);
        }

//-----------------------------------------------------------------------------
// Copy-constructor and assignment operator are not supported for this class:
//-----------------------------------------------------------------------------

        private:

        stack_c(const stack_c& obj);            // Not implemented
        stack_c& operator=(const stack_c& obj); // Not implemented

//=============================================================================
// (Object) Methods:
//=============================================================================

        public:

//-----------------------------------------------------------------------------
// push: Put a new element on top of the stack.
//-----------------------------------------------------------------------------

        inline bool push(T elem) {

                // Ensure that object is valid:
                CHECK_VALID("stack_c::push");

                // Generate error if the stack is already full:
                if(NumElems >= STACK_SIZE) {
                        err_c::stack_overflow(Name, STACK_SIZE);
                        return false;
                }

                // Put element on top of stack and increase number of elems:
                NumElems++;
                *StackPtr++ = elem;
                return true;
        }

//-----------------------------------------------------------------------------
// pop: Get top element from the stack.
//-----------------------------------------------------------------------------

        inline T pop() {
                // Ensure that object is valid:
                CHECK_VALID("stack_c::pop");

                // This can only be called if the stack is non-empty:
                CHECK(NumElems > 0, "stack_c::pop: Stack is empty");

                // Return topmost stack element and remove it:
                NumElems--;
                return *--StackPtr;
        }

//-----------------------------------------------------------------------------
// is_empty: Check whether the stack is empty.
//-----------------------------------------------------------------------------

        inline bool is_empty() const {

                // Ensure that object is valid:
                CHECK_VALID("stack_c::is_empty");

                // The stack is empty if it has zero elements:
                return NumElems == 0;
        }

//-----------------------------------------------------------------------------
// num_elems: Return current stack size (number of elements on the stack).
//-----------------------------------------------------------------------------

        inline int num_elems() const {

                // Ensure that object is valid:
                CHECK_VALID("stack_c::num_elems");

                // Return number of elements on the stack:
                return NumElems;
        }

//=============================================================================
// Debugging Support:
//=============================================================================

//-----------------------------------------------------------------------------
// check: Check the integrity of this object, return error message or NULL.
//-----------------------------------------------------------------------------

#if     VER_DEBUG
        // Integrity check:
        public:
        str_t   check() const {

                // Check magic number:
                if(Magic != STACK_MAGIC)
                        return "wrong magic number";

                // Check number of elements:
                if(NumElems < 0)
                        return "NumElems is negative";
                if(NumElems > STACK_SIZE)
                        return "NumElems is greater than the stack size";

                // Check stack pointer:
                if(StackPtr == static_cast<T*>(0))
                        return "StackPtr is null";
                if(StackPtr != Stack + NumElems)
                        return "StackPtr has wrong value";

                // Ok:
                return STR_NULL;
        }

        // Magic number (identifies objects of this class for debugging).
        private:
        long    Magic;          // Must be "STACK_MAGIC".
#endif

//-----------------------------------------------------------------------------
// dump: Show data structure.
//-----------------------------------------------------------------------------

#if     VER_DUMP

        public:

void dump(str_t headline = STR_NULL) const
{
        // Headline:
        if(headline == STR_NULL)
                headline = "Stack";
        err_c::dump_begin(headline);

        // Basic information:
        err_c::dump_str("Name:       '");
        err_c::dump_str(Name);
        err_c::dump_str("'");
        err_c::dump_nl();
        err_c::dump_str("NumElems:    ");
        err_c::dump_int(NumElems);
        err_c::dump_nl();
        err_c::dump_str("Base Addr. : ");
        err_c::dump_ptr(Stack);
        err_c::dump_nl();
        err_c::dump_str("StackPtr:    ");
        err_c::dump_ptr(StackPtr);
        err_c::dump_str("  [corresponds to index ");
        err_c::dump_int(static_cast<int>(StackPtr - Stack));
        err_c::dump_str("]");
        err_c::dump_nl();
        err_c::dump_str("Object Size: ");
        err_c::dump_int(static_cast<int>(sizeof(stack_c<T>)));
        err_c::dump_nl();
        err_c::dump_nl();

        // Dump stack elements as int-values:
        if(NumElems > 0) {
                err_c::dump_str("Stack Contents (printed as int-values):");
                for(int i = 0; i < NumElems; i++) {
                        err_c::dump_str("   ");
                        err_c::dump_str(str_fill(i, 3));
                        err_c::dump_int(i);
                        err_c::dump_str(": ");
                        err_c::dump_int(reinterpret_cast<int>(Stack[i]));
                        err_c::dump_nl();
                }
                err_c::dump_nl();
        }

        // Done:
        err_c::dump_end();
}

#endif


//=============================================================================
// Private Object Members:
//=============================================================================

        private:

        // NumElems: Number of elements in the stack.
        int NumElems;

        // Stack: Array for storing the elements of the stack.
        T Stack[STACK_SIZE];

        // StackPtr: Pointer to the next (free) place in the array.
        T *StackPtr;

        // Name: Name of stack (for use in "stack overflow" error message).
        str_t Name;

//=============================================================================
// End of Class Template:
//=============================================================================

};


//=============================================================================
// End of Include File:
//=============================================================================

#endif