/*  snstack.h  by K.Tsuru  */
/**************************************************************
Stack class using Block class
[Notice]
 1.do not lnitialize
 2.If "T" is a class it must have operator=() and operator==().
 3.If there is no data to pop, terminate the program.
**************************************************************/
#ifndef SNSTACK_H
#define SNSTACK_H

#ifndef SNBLOCK_H
#include "snblock.h"
#endif

    const uint stackMinSize = 4u;

    template <class T> class SNStack {
        SNBlock <T>     v;
        uint    stackElements;
    //When elements become small, reduce the size(1) or not(0).
        int     resize;
    //Does not provide copy constructor nor operator=(), probably not necessary.
        SNStack(const SNStack<T>& a);               // has no body, then cannot use.
        SNStack<T>& operator=(const SNStack<T>& a); // same above.
    public:
    // constructor
        SNStack(int rsz = 1) : stackElements(0), resize(rsz){
            v.size(stackMinSize, -1);
        }
        ~SNStack(){}
        uint    Size() const  { return v.size();    }
        T operator()(uint n) const {
    #ifndef NDEBUG
    assert( n < stackElements);
    #endif
            return v(n);
        }
        void    ResizeSwitch(int rsz){  resize = rsz;   }
    //Return the number of stacked elements.
        uint    Elements() const { return v.size() ? stackElements : 0; }
        void    Push(const T& x);
        T       Pop();
    //Search an element "x", if it was found return its number(first element is one).
    //If not found return 0.
        uint    Search(const T& x);
    //Search an elements"x", if it is not found push it on stack.
    //T must have operator==()
        bool    Entry(const T& x); // ver. 2,17
    //delete an element x
        bool    Extract(const T& x);  // ver. 2,17
        int     Error() { return v.Error(); }
    };

    template <class T> void SNStack<T>::Push(const T& x){
        v.reserve(stackElements);
        v[stackElements++] = x;
    #ifndef NDEBUG
    assert(v.Error() == v.NORMAL);
    #endif
    }

    template <class T> T SNStack<T>::Pop(){
        if(!stackElements) exit(EXIT_FAILURE);  //no data to pop
        if( resize && (stackElements >= stackMinSize) && (stackElements <= v.size()/2) ){
        // reduce the size, example : size = 8, stackElements = 4 ===> size = 4
            v.size(stackElements, 1);
        }
        return v(--stackElements);
    }

    template <class T> uint SNStack<T>::Search(const T& x){
        uint j = 0;
        bool found = false;  // ver. 2,17
        while(j < stackElements) if( v(j++) == x ){ found = true;   break;  }
        return found ? j : 0;   // j >= 1
    }

    template <class T> bool SNStack<T>::Entry(const T& x){ // ver. 2,17
        int found = Search(x);
        if(!found) Push(x);
        return !found;
    }
    template <class T> bool SNStack<T>::Extract(const T& x){ // ver. 2,17
        int found = Search(x);
        if(!found) return false;

        for(int i = found; i < stackElements; i++) v[i-1] = v[i];
        stackElements--;
        if( resize && (stackElements >= stackMinSize) && (stackElements <= v.size()/2) ){
            v.size(stackElements, 1);
        }
        return true;
    }

#endif  // STACK_H