//
// stack.hpp
//
// Definition and implementation of a generic, array-based stack class.
//
// Because we're using templates, we need to define the methods in
// this file so that the compiler won't complain.
//
// Computer Science S-111, Harvard University
//

#ifndef STACK_HPP
#define STACK_HPP

#include <assert.h>
#include "../util/s111unx.hpp"


template <class elt>
class stack {
private:
    int num_items;
    int max_items;
    elt *data;
    
public:
    stack();
    stack(int max);
    ~stack();

    void set_max(int max);
    void reinit();

    // Pushes item from source to stack, returning false if stack was full.
    bool push(elt source);

    // Pops top item into target, returning false if stack was empty. 
    bool pop(elt& target);

    elt& peek();
    void traverse(void (*action)(int, elt));

    bool empty() { return (num_items == 0); }
    bool full()  { return (num_items == max_items); }
};


//
// Default constructor
//
template <class elt>
stack<elt>::stack()
{
    num_items = 0;
    max_items = 0;
    data = NULL;
}

//
// Constructor that takes the maximum number of items
//
template <class elt>
stack<elt>::stack(int max)
{
    data = NULL;
    set_max(max);
}

//
// Destructor
//
template <class elt>
stack<elt>::~stack()
{
    if (data != NULL)
	delete [] data;
}

//
// set_max - (re)initialize the stack to the specified maximum size
//
template <class elt>
void
stack<elt>::set_max(int max)
{
    assert(max > 0);

    if (data != NULL)
	delete [] data;

    num_items = 0;
    max_items = max;
    data = new elt[max_items];
}

//
// reinit - returns to an empty stack
//
template <class elt>
void
stack<elt>::reinit()
{
    num_items = 0;
}

//
// push - pushes item from source to top of stack, returning false
// if stack is full.
//
template <class elt>
bool
stack<elt>::push(elt source)
{
    if (full())
	return false;

    //
    // The top item of the stack is in data[num_items - 1].
    // Thus, the new item should go in data[n], where n is
    // the number of items on the stack *before* the new one
    // is added.  Thus, we increment num_items *after* adding the item.
    //
    data[num_items] = source;
    num_items++;
    
    return true;
}

//
// pop - pops top item into target, returning false if stack is empty
//
template <class elt>
bool
stack<elt>::pop(elt& target)
{
    if (empty())
	return false;

    //
    // The top item of the stack is in data[num_items - 1].
    // Thus, we decrement num_items *before* using it as an index
    // for the item we are removing.
    //
    num_items--;
    target = data[num_items];

    return true;
}

//
// peek - returns a reference to the top item without removing it
//
template <class elt>
elt&
stack<elt>::peek()
{
    assert (!empty());
    return data[num_items-1];
}

//
// traverse - traverses stack from bottom to top, applying
// specified function to each element in the stack.
//
template <class elt>
void
stack<elt>::traverse(void (*action)(int, elt))
{
    for (int pos = 0; pos < num_items; pos++) 
	(*action)(pos, data[pos]);
}

#endif
