#ifndef Stack_hpp
#define Stack_hpp

#include <stdio.h>
#include <algorithm>
using namespace std;

template <class T>
class Stack
{
    
    public:
        Stack(int = 10);
        Stack(const Stack&); //copy constructor
        ~Stack();
        
        bool IsEmpty() const;
        T& Top() const;
        void push(const T&);
        void pop();
        void showStack();
        Stack splitStack(int);
        Stack combine(Stack&);
    
    
       private:
        T* stack;
        int top;
        int capacity;
    
};


template<class T>
void ChangeSize1D(T* x, int oldSize, int newSize)
{
    if (newSize<0) {
        throw "Size must be > 0";
    }
    T* temp = new T[newSize];
    int n = min(oldSize, newSize);
    copy(x, x+n, temp);
    delete [] x;
    x = temp;
    
    
}



template<class T>
Stack<T>::Stack(int stackCapacity):capacity(stackCapacity)
{
    if (capacity< 1) {
        throw "it must be" > 0;
        
    }
    stack = new T[capacity];
    top = -1;
}


//copy constructor
template<class T>
Stack<T>::Stack(const Stack& b)
{
    top = b.top;
    capacity = b.capacity;
    delete [] stack;
    stack  = new T[capacity];
    copy(b.stack, b.stack+top+1, stack);
    
}


template<class T>
Stack<T>::~Stack()
{
    cout << stack <<" DEs Called!" << endl;
    delete [] stack;
}


template <class T>
inline bool Stack<T>::IsEmpty() const {return top == -1;}



template <class T>
T& Stack<T>::Top() const
{
    if (IsEmpty()) throw "Stack is Empty.";
    return stack[top];
}


template<class T>
void Stack<T>::push(const T &item)
{
    if (top == capacity-1) {
        ChangeSize1D(stack, capacity, 2*capacity);
        capacity*=2;
    }
    stack[++top] = item;
}

template<class T>
void Stack<T>::pop()
{
    if (IsEmpty()) {
        throw "Stack is empty.";
    }
    stack[top--].~T();
}

template <class T>

void Stack<T>::showStack()
{
    if (IsEmpty()) throw "Stack is empty.";
    for (int i = capacity-1; i >= top+1; i--) {
        cout << "| |"<<endl;
    }
    for (int i = top; i>=0; i--) {
        cout <<"|"<< stack[i] << "|" << endl;
    }
    cout << "|-|"<<endl;
}

template <class T>
Stack<T> Stack<T>::splitStack(int n) // 保留第0～n個在原本的stack，多的分出去給承接的stack
{
    if (IsEmpty()) throw "Stack is empty.";
    
    Stack first;
    
    T element;
    for (int i = n+1; i <=top; i++) {
        element = stack[i];
        first.push(element);
    }
    for (int i = top; i>n; i--) pop();
    cout << first.stack << endl;
    return Stack<T>(first);
}


template<class T>
Stack<T> Stack<T>::combine(Stack<T> &b)
{
    Stack result;
    
    for (int i = 0; i <=top; i++) {
        result.push(stack[i]);
    }
    for (int i = 0; i<=b.top; i++) {
        result.push(b.stack[i]);
    }
    return result;
}



#endif /* Stack_hpp */