// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- //
// C++ Header File Name: stack.hpp 
// Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
// Produced By: Doug Gaer   
// File Creation Date: 01/21/1997 
// Date Last Modified: 07/30/1998
// Copyright (c) 1997 Douglas M. Gaer
// ----------------------------------------------------------- // 
// ---------- Include File Description and Details  ---------- // 
// ----------------------------------------------------------- // 
/*
The VBD C++ classes are copyright (c) 1997, by Douglas M. Gaer.
All those who put this code or its derivatives in a commercial
product MUST mention this copyright in their documentation for
users of the products in which this code or its derivative
classes are used. Otherwise, you have the freedom to redistribute
verbatim copies of this source code, adapt it to your specific
needs, or improve the code and release your improvements to the
public provided that the modified files carry prominent notices
stating that you changed the files and the date of any change.

THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
CORRECTION.

A generic singly linked list based stack. This is a last-in,
first-out (LIFO) resizable data structure. Heap space is
allocated and de-allocated with every push and pop operation.
*/
// ----------------------------------------------------------- //   
#ifndef __STACK_HPP
#define __STACK_HPP

#include "sllist.hpp"

template<class TYPE>
class Stack : public SLListBase
{
public:
  Stack() { }
  ~Stack();
  Stack(const Stack<TYPE> &X) { Copy(X); }
  void operator=(const Stack<TYPE> &X) { Copy(X); }

public:
  int Push(const TYPE &X);
  int Pop(TYPE &X);
  int Pop();
  void Rewind(unsigned Index=0);
  TYPE *Top() { return IsEmpty() ? 0 : &(((SNode<TYPE> *)GetFront())->Data); }
  const TYPE *Top() const { return ((Stack<TYPE> *)this)->Top(); }
  TYPE *Look(unsigned Index);
  const TYPE *Look(unsigned Index) const {
    return ((Stack<TYPE> *)this)->Look(Index); }

  // This function is for test purposes only
  friend int List(const Stack<TYPE> &X);

protected:
  virtual SNode<TYPE> *AllocNode(const TYPE &X);
  virtual SNodeBase *DupNode(const SNodeBase *Node);
  virtual void FreeNode(SNodeBase *Node);
};

template<class TYPE>
Stack<TYPE>::~Stack()
{
  Rewind();
}

template<class TYPE>
SNode<TYPE> *Stack<TYPE>::AllocNode(const TYPE &X)
{
  return new SNode<TYPE>(X);
}

template<class TYPE>
SNodeBase *Stack<TYPE>::DupNode(const SNodeBase *Node)
{
  return new SNode<TYPE>(((SNode<TYPE> *)Node)->Data);
}

template<class TYPE>
void Stack<TYPE>::FreeNode(SNodeBase *Node)
{
  delete (SNode<TYPE> *)Node;
}

template<class TYPE>
int Stack<TYPE>::Push(const TYPE &X)
{
  SNode<TYPE> *ptr = AllocNode(X);
  if (ptr == 0) return 0; // Allocation failed
  AttachToFront(ptr);
  return 1;
}

template<class TYPE>
int Stack<TYPE>::Pop(TYPE &X)
{
  SNode<TYPE> *ptr = (SNode<TYPE> *)RmvFront();
  if (ptr == 0) return 0; // Stack is empty
  X = ptr->Data;
  FreeNode(ptr);
  return 1;
}

template<class TYPE>
int Stack<TYPE>::Pop()
{
  if (IsEmpty()) return 0; // Stack is empty
  FreeNode(RmvFront());
  return 1;
}

template<class TYPE>
TYPE *Stack<TYPE>::Look(unsigned Index)
{
  SNode<TYPE> *ptr = (SNode<TYPE> *)GetFront();
  while(!IsHeader(ptr)) {
    if (Index-- == 0) return &ptr->Data; // Return data in the top elememnt
    ptr = ptr->GetNext();
  }
  return 0; // Out of range
}

template<class TYPE>
void Stack<TYPE>::Rewind(unsigned Index)
{
  if (Index == 0) Index = (unsigned)(-1); // Biggest number that can be used
  SNode<TYPE> *ptr = (SNode<TYPE> *)Next;
  while(!IsHeader(ptr) && Index--) {
    SNode<TYPE> *NextPtr = ptr->GetNext();
    FreeNode(ptr);
    ptr = NextPtr;
    Next = NextPtr;
  }
}

// This function is for test purposes only
template<class TYPE>
int List(const Stack<TYPE> &X)
{
  if (X.IsEmpty()) {
    cout << "Stack is empty" << endl;
  }
  else {
    const SNode<TYPE> *ptr = (const SNode<TYPE> *)X.GetFront();
    while(!X.IsHeader(ptr)) {
      cout << ptr->Data << endl;
      ptr = ptr->GetNext();
    }
    cout << endl;
  }
  return 1;
}

#endif // __STACK_HPP
// ----------------------------------------------------------- // 
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //
