//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
// Created: MJF 05/22/89 -- Initial design.
// Updated: JCB 06/05/89 -- Implementation.
// Updated: LGO 08/09/89 -- Inherit from Generic
// Updated: MBN 08/20/89 -- Changed usage of template to reflect new syntax
// Updated: MBN 08/23/89 -- Added conditional exception handling and base class
// Updated: LGO 10/05/89 -- Efficiency improvements to popn
// Updated: MBN 10/19/89 -- Added optional argument to set_compare method
// Updated: MBN 11/01/89 -- Added constructor with user-provided storage param
// Updated: LGO 12/07/89 -- re-write push and pushn, added grow method
// Updated: LGO 12/07/89 -- Make compare_s default to NULL
// Updated: MBN 02/22/90 -- Changed size arguments from long to unsigned long
// Updated: MJF 05/31/90 -- Use memcpy in resize
// Updated: MJF 05/31/90 -- Use "delete [size] data"
// Updated: MJF 06/30/90 -- Added base class name to constructor initializer
//
// The Stack<Type>  class is publicly  derived  from  the base Stack  class and
// implements a one  dimensional  vector of  a  user-specified  type.   This is
// accomplished by using the parameterized type  capability of C++.   The stack
// will grow dynamically as necessary with the  amount  of growth determined by
// the  value of an  allocation  size slot.   Fixed   length stacks   are  also
// supported by setting the value of the allocation size slot to zero.
//
// Each Stack<Type> object contains a private  data section that  has a slot to
// hold the current size of the stack and a pointer to an allocated block large
// enough to hold "size elements" of type "Type."   A slot to  thold the number
// of elements currently on  the stack is also available.   The protected  data
// section has   a pointer  to a  compare function  that  is used   in equality
// operations. The default equality function used is the == operator.
//
// There  are four   constructors   for the   Stack<Type> class.   The    first
// constructor takes  no arguments and creates   an  empty  Stack object of the
// specified type.  The second constructor takes a required argument specifying
// the initial  size  of the stack.  The  third takes a pointer   to a block of
// user-defined storage    and  the number of  elements  the   stack  can hold.
// Finally,  the   third constructor  takes a  single argument  consisting of a
// reference to a Stack<Type> and duplicates its size and element values.
//
// Methods are provided to push and  pop items to  and from the  stack, examine
// the   item on the   top of the stack  without  removing  it, determine if an
// element is already  on the stack, report the  number of items in the  stack,
// check the empty status, and clear all items from the stack.  The assignment,
// output, and  equality operators are  overloaded. Finally, two methods to set
// the allocation growth size and compare function are provided.
//

#ifndef STACKH					// If no definition for Stack
#define STACKH					// Define stack symbol

#ifndef BASE_STACKH				// If no definition for class
#include <cool/Base_Stack.h>			// Include definition file
#endif

#ifndef NEWH
#if defined(DOS) || defined(M_XENIX)
#include <new.hxx>				// include the new header file
#else
#include <new.h>				// include the new header file
#endif
#define NEWH
#endif

template <class Type> Stack {
  typedef Boolean (*Type##_Stack_Compare) (const Type&, const Type&);
}

template <class Type>
class Stack<Type> : public Stack {
private:
  Type* data;					// Pointer to allocated storage

protected:
  static Type##_Stack_Compare compare_s;	// Pointer operator== function
  Boolean grow (long min_size);			// Grow on push

public:
  Stack<Type> ();				// Simple constructor
  Stack<Type> (unsigned long);			// Stack of initial size
  Stack<Type> (void*, unsigned long);		// Stack with static storage
  Stack<Type> (const Stack<Type>&);		// Duplicate another stack
  ~Stack<Type> ();				// Stack destructor

  Boolean push (const Type&);			// Push item on top of stack
  Boolean pushn (const Type&, long);		// Push n items w/initial value

  inline Type& pop ();				// Pop top item off stack
  Type& popn (long);				// Remove n items, return nth
  inline Type& top ();				// Return top item on stack

  inline Type& operator[] (unsigned long);	// Zero-relative (top) index 
  long position (const Type&) CONST;		// Returns stack index of value
  Boolean find (const Type&);			// Returns TRUE if found

  Stack<Type>& operator= (const Stack<Type>& s); // Assignment s = s2;
  Boolean operator== (const Stack<Type>& s) CONST; // is equal
  inline Boolean operator!= (const Stack<Type>& s) CONST ; // is not equal

  void resize (long);				// Resize for at least count
  inline long set_length (long);		// Set number of elements
  inline void set_growth_ratio (float);		// Set growth percentage
  inline void set_compare(Type##_Stack_Compare = NULL); // Set compare function
  inline void set_alloc_size (int);		 // Set alloc size

  friend ostream& operator<< (ostream&, const Stack<Type>&);
  inline friend ostream& operator<< (ostream&, const Stack<Type>*);
};

// Type& top() -- Return the top item on this stack
// Input:         None
// Output:        Reference to top item on stack

template<class Type>
inline Type& Stack<Type>::top () {
#if ERROR_CHECKING
  if (this->number_elements > this->size)	// If index out of range
    this->top_error (#Type);			// Raise exception
#endif
  return this->data[this->number_elements-1];	// The top is really at the end
}


// Type& pop () -- Pop top item off this stack and return it
// Input:          None
// Output:         Top item of stack

template<class Type>
inline Type& Stack<Type>::pop () {
#if ERROR_CHECKING
  if (this->number_elements > this->size)	// If index out of range
    this->pop_error (#Type);			// Raise expception
#endif
  return (this->data[--this->number_elements]);	// Remove/return top element
}


// Type& operator[](long) -- Return the nth element (zero-relative from top)
// Input:                    Integer n
// Output:                   Reference to the nth element of stack

template<class Type>
inline Type& Stack<Type>::operator[] (unsigned long n) {
#if ERROR_CHECKING
  if (unsigned(n) >= this->number_elements)	// If index out of range
    this->bracket_error (#Type, n);		// Raise exception
#endif
  return this->data[number_elements-n-1];	// Nth element from "top"
}


// Boolean operator!= (Stack<Type>&) -- Compare this stack with another stack;
//                                      return TRUE if they are not equal
// Input:  Reference to a stack
// Output: TRUE or FALSE

template<class Type>
inline Boolean Stack<Type>::operator!= (const Stack<Type>& s) CONST {
  return (!this->operator== (s));
}


// long set_length(long) -- Change number of elements in this stack
// Input:                   Integer number of elements
// Output:                  None

template<class Type>
inline long Stack<Type>::set_length (long n) {
  this->Stack::set_length (n, #Type);		// Pass size/type to base class
  return this->number_elements;			// Return value
}


// void set_growth_ratio(float) -- Set growth percentage of this stack
// Input:                          Float ratio
// Output:                         None

template<class Type>
inline void Stack<Type>::set_growth_ratio (float ratio) {
  this->Stack::set_growth_ratio (ratio, #Type);	// Pass ratio/type to base
} 


// void set_compare(Type##_Stack_Compare) -- Set this stack's compare function
// Input:                                    Pointer to a compare function
// Output:                                   None

template<class Type>
inline void Stack<Type>::set_compare (Type##_Stack_Compare c) {
  this->compare_s = c;			// Set to user function or NULL
}


// void set_alloc_size(int) -- Set the default allocation size
// Input:                      Integer size
// Output:                     None

template<class Type>
inline void Stack<Type>::set_alloc_size (int size) {
  this->Stack::set_alloc_size (size, #Type);
}


// Stack<Type> () -- Empty constructor for the Stack class
// Input:            None
// Output:           None

template<class Type>
Stack<Type>::Stack<Type> () {
  this->data = NULL;				// Initialize data
}


// Stack<Type> (long) -- Constructor that specifies number of elements
// Input:                Integer number of elements
// Output:               None

template<class Type>
Stack<Type>::Stack<Type> (unsigned long n)
#ifdef __cplusplus
 : Stack(n)
#else
 : (n)
#endif 
{
  this->data = (Type*) new Type[n];		// Allocate memory
}


// Stack<Type> (void*, long) -- Constructor that specifies static-sized storage
//                              and number of elements
// Input:                       Integer number of elements
// Output:                      None

template<class Type>
Stack<Type>::Stack<Type> (void* s, unsigned long n)
#ifdef __cplusplus
 : Stack(n)
#else
 : (n) 
#endif 
{
  this->data = (Type*) s;			// Pointer to storage block
  this->alloc_size_s = INVALID;			// Indicate static-size object
}


// Stack<Type> (Stack<Type>&) -- Constructor for reference to another stack
// Input:                        Stack reference
// Output:                       None

template<class Type>
Stack<Type>::Stack<Type> (const Stack<Type>& s)
#ifdef __cplusplus
 : Stack(s)
#else
 : (s)
#endif
{
  this->data = (Type*) new Type[s.size];	// New memory allocation
  for (long i = 0; i < s.number_elements; i++)	// For each element
    this->data[i] = s.data[i];			// Copy data into this
}


// ~Stack<Type> -- Destructor for Stack class that frees up storage
// Input:          None
// Output:         None

template<class Type>
Stack<Type>::~Stack<Type> () {
  if (this->size != 0 &&			
      this->alloc_size_s != INVALID)		// If not user-provided storage
    delete [this->size] this->data;		// Free up the memory
}


// Boolean push(Type&) -- Push item on top of this stack
// Input:                 Reference to a Type value to push onto stack
// Output:                TRUE or FALSE

template<class Type>
Boolean Stack<Type>::push (const Type& value) {
  if (this->number_elements == this->size) {	// If not enough memory
    if (!this->grow(this->size+1)) return FALSE; // Report failure
  }
  this->data[number_elements++] = value;	// Top item becomes value
  return TRUE;					// Report success
}


// Boolean pushn(Type&, long) -- Push n items with a fill value onto this stack
// Input:  Reference to Type value, integer number of items to be pushed
// Output: TRUE or FALSE

template<class Type>
Boolean Stack<Type>::pushn (const Type& value, long n) {
  if (n < 0)					// Range-checking error
    return FALSE;				// Return FALSE
  if (n == 0) {					// For push(foo, 0)
    this->data[number_elements-1] = value;	// Replace top item
    return TRUE;				// Return success
  }
  if (n == 1)					// If just push one item
    return (push(value));			// Push one item == push
  if (this->number_elements+n > this->size) {	// If not enough memory
    if (!this->grow(this->size+1)) return FALSE; // Report failure
  }
  this->number_elements += n;			// Add n to number of elements
  for (long i = number_elements - n; i < number_elements; i++) // For "n" elts
    this->data[i] = value;		        // Fill with value
  return TRUE;					// Report success  
}


// Type& popn(long) -- Pop n items off this stack, from the top; return the
//                     nth item
// Input:              Integer number of items
// Output:             nth element of stack

template<class Type>
Type& Stack<Type>::popn (long n) {
#if ERROR_CHECKING
  if (n < 0)					// If index out of range
    this->popn_error (#Type, n);		// Raise exception
#endif
  if (n == 0)					// If top element
    return (this->data[number_elements-1]);	// Return top item
  if (n > this->number_elements)  {		// If arg n > # elements
    this->number_elements = 0;			// Reset # of elements
    return this->data[0];			// Return last element
  }
  return (this->data[this->number_elements -= n]); // Return nth from "top"
}


// Stack<Type>& operator= (Stack<Type>&) -- Assigns this stack to another stack
// Input:  Reference to a stack
// Output: Reference to modified this

template<class Type>
Stack<Type>& Stack<Type>::operator= (const Stack<Type>& s) {
  if (this->size < s.size) {                    // If not enough memory
#if ERROR_CHECKING
    if (this->alloc_size_s == INVALID)		// If static size queue
      this->assign_error (#Type);		// Raise exception
#endif
    if (this->size != 0)
      delete [this->size] this->data;		// Free it up
    this->data = (Type*) new Type[s.size];      // Allocate bigger memory
    this->size = s.size;                        // New stack size
  }
  this->Stack::operator= (s);			// Call base class assignment
  for (long i = 0; i < s.number_elements; i++)   // For each element
    this->data[i] = s.data[i];                  // Copy value
  return *this;					// Return reference
}


// Boolean operator== (Stack<Type>&) -- Compare this stack with another
//                                      stack; return TRUE if they are equal
// Input:  Reference to a stack
// Output: TRUE or FALSE

template<class Type>
Boolean Stack<Type>::operator== (const Stack<Type>& s) CONST {
  if (this->number_elements != s.number_elements) // If not same number
    return FALSE;				  // Then not equal
  if (this->compare_s == NULL) {
    for (long i = 0; i < this->number_elements; i++) // For each element
      if (!(this->data[i] == s.data[i]))	     // If not equal
	return FALSE;				     // Return failure
  } else {
    for (long i = 0; i < this->number_elements; i++) // For each element
      if (!(*this->compare_s)(this->data[i],s.data[i])) // If not equal
	return FALSE;					// Return failure
  }
  return TRUE;					  // Return sucess
}


// Boolean find (Type&) -- Return TRUE if value is found in this stack
// Input:                  Reference to a Type value
// Output:                 TRUE or FALSE

template<class Type>
Boolean Stack<Type>::find (const Type& value) {
  return this->position(value) >= 0;
}


// long position (Type&) -- Return the index (from top) of value if found;
//                          otherwise return -1
// Input:                   Reference to a Type value
// Output:                  Integer index or -1

template<class Type>
long Stack<Type>::position (const Type& value) CONST {
  if (this->compare_s == NULL) {
    for (long i = this->number_elements - 1; i >= 0;  i--) // Search from "top"
      if (this->data[i] == value)			   // If found
	return (this->number_elements-i-1);		   // Index from "top"
  } else {
    for (long i = this->number_elements - 1; i >= 0;  i--) // Search from "top"
      if ((*(this->compare_s))(this->data[i], value))	   // If found
	return (this->number_elements-i-1);		   // Index from "top"
  }
  return -1;                                              // Failure
}

// grow -- grow stack on push overflow
// Input:    None
// Output:   None

template<class Type>
Boolean Stack<Type>::grow (long min_size) {
  if (this->alloc_size_s == INVALID) {	// If not allowed to grow
#if ERROR_CHECKING
    this->push_error (#Type);			// Raise exception
#endif
    return FALSE;				// Report failure
  }
  if (this->growth_ratio != 0.0 &&
      (this->size * (1.0+growth_ratio)) >= min_size)
    min_size = (long)(this->size * (1.0 + growth_ratio)); // New size
  else
    min_size += alloc_size_s;
  resize(min_size);
  return TRUE;
}

// resize -- Adjust the memory size of a Stack to accomodate some size
// Input:    Number of elements to hold
// Output:   None

template<class Type>
void Stack<Type>::resize (long new_size) {
  if (new_size <= this->size) {			// Don't bother shrinking stack
#if ERROR_CHECKING
    if (new_size < 0)				// If index out of range
      this->resize_error (#Type, new_size);	// Raise exception
#endif
    return;
  }
#ifndef DOS
  Type* temp = (Type*) new char[sizeof(Type) * new_size];   // Allocate storage
  memcpy ((char*)temp, (char*)this->data,
	 (int)(this->size * new_size));		// copy old data
  (void) new(&temp[this->size]) Type[new_size - this->size]; // Construct new
  if (this->data != NULL)
    delete (char*) this->data;			// Free old, no destructors
#else
  Type* temp = (Type*) new Type[new_size];	// Allocate storage
  for (long i = 0; i < this->number_elements; i++)// For each element in Vector
    temp[i] = this->data[i];			// Copy into new storage
  
  if (this->size != 0)
    delete [this->size] this->data;		// Free up old memory
#endif
  this->data = temp;				// Assign new memory block
  this->size = new_size;			// Save new size value
}

// operator<< -- Overload the output operator for Stack
// Input:        ostream reference, stack reference
// Output:       Stack data is output to ostream

template<class Type> Stack {
ostream& operator<< (ostream& os, const Stack<Type>& s) {
  if (s.length() == 0)				// If no elements
    os << " Empty ";				// Report empty status
  else {
    os << "[ ";					// From top of stack
    for (long i = s.length() - 1; i >= 0; i--)	// For each element
      os << s.data[i] << " ";			// Print data items
    os << "]";					// Bottom of stack
  }
  return os;					// Return stream reference
}
}


// operator<< -- Overload the output operator for Stack
// Input:        ostream reference, stack pointer
// Output:       Stack data is output to ostream

template<class Type> Stack {
inline ostream& operator<< (ostream& os, const Stack<Type>* s) {
  return operator<<(os, *s);
}
}

#endif				// End #ifdef of STACKH

