//
// 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 03/27/89 -- Initial design
// Updated: MBN 04/18/89 -- Modification to support dynamic vectors, provide
//                          mechanism to define default allocation size, and
//                          separation of arithmetic vector to another class.
// Updated: MBN 05/08/89 -- Parameterized the class Vector<Type>
// Updated: MBN 05/26/89 -- Removed the non-destructive forms of the methods
//                          and implemented the notion of current position.
// Updated: MBN 06/07/89 -- Added growth ratio slot and resize method
// Updated: MBN 06/20/89 -- Changed returns types from Vector<Type>& to void
// Updated: LGO 07/13/89 -- Inherit from Generic
// Updated: MBN 08/15/89 -- Added const qualifer to arguments where necessary
// Updated: MBN 08/20/89 -- Changed usage of template to reflect new syntax
// Updated: MBN 08/31/89 -- Added conditional exception handling and base class
// Updated: LGO 10/02/89 -- Make destructor inline
// Updated: MBN 10/10/89 -- Changed "current_position" to "curpos" 
// 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 11/09/89 -- Initialize alloc_size and growth_ratio
// Updated: MBN 11/13/89 -- Optimize sort for one element case
// Updated: LGO 12/05/89 -- Performance enhancements to most methods
// Updated: LGO 12/05/89 -- Make sort/merge predicate ANSI compatable
// Updated: LGO 12/12/89 -- Make copy, fill and search take exclusive end args.
// Updated: LGO 01/02/89 -- Add get and put methods
// 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   Vector<Type>  class  is   publicly derived from  the  Vector class and
// implements single dimensional vectors   of a user specified type.    This is
// accomplished by using    the   parameterized type capability   of C++.   The
// Vector<Type>  class   is  dynamic  in the  sense  that an   object can  grow
// dynamically if necessary.   The growth size is determined  by the value of a
// static  allocation  size variable  for  the  class.  However,  fixed  length
// vectors are also supported by setting this variable to INVALID.
// 
// Each vector object contains a protected data section that has a slot to hold
// the current  size  of the  vector and a pointer  to an allocated block large
// enough to hold "size" elements of type "Type". A  slot to hold the number of
// elements is also provided. A single protected  slot contains  a pointer to a
// compare  function to be  used in equality operations.  The  default function
// used is the built-in == operator.  Finally, a current  position slot is used
// to maintain the index of the last element affected by an operation.
//
// Five different constructors are  provided.  The  first constructor  takes no
// arguments and creates an empty Vector object of a specified type. The second
// constructor takes  a single  argument  specifying the  initial   size of the
// Vector.  The third   constructor takes two  required   arguments,  the first
// specifiying  the inital  size  of  the Vector  and  the  second providing an
// initialization value to  assign to  each element.  The fourth constructor is
// similar to  the third, except that it  takes a  variable number of arguments
// after the size to allow for the initialization of any  number of elements of
// the Vector to different  arbitrary values.  Finally, the  fifth  constructor
// takes a single argument consisting of a reference to a Vector and duplicates
// its size and element values.
// 
// The Vector class implements the notion of a current position. This is useful
// for iterating through the  elements  of a  vector.  The current  position is
// maintained in an  integer and  is   set  or reset  by all methods  affecting
// elements   in the Vector  class. Methods  to   reset,  move to the  next and
// previous, find, and get the value at the current position are provided.
//
// Methods are provided  to  destructively   perform reverse, remove,  replace,
// prepend, append, merge, sort, and insert operations on a Vector object.   In
// addition, several miscelaneous methods  support  resize, copy, fill, length,
// search,  push, push_new, pop,  and   position functions.  The assignment and
// element accessor functions allow for individual elements of the vector to be
// set and read.  Finally, both equality and non-equality tests are implemented
// via  a user-defined  comparison function  as  well as  overloaded input  and
// output operators.
//

#ifndef VECTORH					// If no definition for Vector
#define VECTORH					// define the vector symbol

#ifndef BASE_VECTORH				// If no definition for base
#include <cool/Base_Vector.h>			// Include the class header
#endif

#ifndef STDARGH
#if defined(M_XENIX)
#include <stdarg.hxx>
#elif defined(DOS)
extern "C" {
#include <stdarg.h>				// for variable arglist
}
#else
#include <stdarg.h>				// for variable arglist
#endif
#define STDARGH
#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> Vector {
  // Used for sorting: returns -1 for less, 0 for equal, and 1 for greater
  typedef int (*Type##_Vector_Predicate) (const Type&, const Type&);
  // Used for find, operator== and search, returns TRUE when equal
  typedef Boolean (*Type##_Vector_Compare) (const Type&, const Type&);
}

template <class Type>
class Vector<Type> : public Vector {
protected:
  Type* data;					// Pointer to allocated storage
  static Type##_Vector_Compare compare_s;	// Pointer operator== function
  void grow (long min_size);			// Make the Vector bigger

public:
  Vector<Type> ();				// Vector v; 
  Vector<Type> (unsigned long);			// Vector v(10);
  Vector<Type> (void*, unsigned long);		// Vector with static storage
  Vector<Type> (unsigned long, const Type&);	// Vector v(10,x);
  Vector<Type> (unsigned long, int, ...);	// Vector v(10,3,x,y,z);
  Vector<Type> (const Vector<Type>&);		// Vector v = y;
  ~Vector<Type> ();				// Destructor

  Boolean find (const Type&, unsigned long start = 0); // Set current position
  inline Type& value ();			// Value at current position
  
  Vector<Type>& operator= (const Vector<Type>&); // v = vec1;
  Vector<Type>& operator= (const Type&);	 // v = 0; (set elements)
  inline Type& operator[](unsigned long) CONST;	 // return element
  inline Type& get(int n);			 // Return element, set curpos
  inline Boolean put(const Type& x, int n);	 // Sets nth data-node to x

  Boolean operator== (const Vector<Type>&) CONST; // Compare 2 vectors 
  inline Boolean operator!= (const Vector<Type>&) CONST; // Compare 2 vectors

  friend ostream& operator<< (ostream&, CONST Vector<Type>&); // output
  friend ostream& operator<< (ostream&, CONST Vector<Type>*);

  inline long position () CONST;		// Return current position 
  inline long set_length (long);		// Set length of vector
  inline void set_growth_ratio (float);		// Set growth ration
  inline void set_alloc_size (int);		// Set allocation size
  inline void set_compare (Type##_Vector_Compare = NULL); // Compare function

  void resize (long);				// Resize vector
  void fill (const Type&, unsigned long start=0, long end = -1);// set elements
  long position (const Type&);			// Index of 1st occurrence
  
  void copy (const Vector<Type>&, unsigned long start = 0, long end = -1);
  Boolean search (const Vector<Type>& sequence, long start=0, long end=-1);

  Boolean push (const Type&);			// Add element to end of vector
  Boolean push_new (const Type&);		// Append element if not there
  Type& pop ();					// Remove/return last element

  void reverse ();				// Reverse order of elements
  Type remove ();				// Remove item at current pos.
  Boolean remove (const Type&);			// Remove first occurrence
  Boolean remove_duplicates ();			// Removes duplicate elements
  Boolean replace (const Type&, const Type&);	// Replace first occurrence
  Boolean replace_all (const Type&, const Type&); // Replace all occurrences
  Boolean prepend (const Vector<Type>&);	// Prepend vector 
  Boolean append (const Vector<Type>&);		// Append vector
  
  Boolean insert_before (const Type&);		// Insert before current pos
  Boolean insert_after (const Type&);		// Insert after current pos
  Boolean insert_before (const Type&, long index); // Insert before index
  Boolean insert_after (const Type&, long index);  // Insert after index

  void merge (const Vector<Type>&, Type##_Vector_Predicate); // Merge
  void sort (Type##_Vector_Predicate);			       // Sort 
};


// Boolean find () -- Find first/next occurrence of element in a Vector.
// Input:             Type reference to search value, starting index
// Output:            TRUE/FALSE

template<class Type> 
Boolean Vector<Type>::find (const Type& value, unsigned long start) {
  register long i;
  if (this->compare_s == NULL) {
    for (i = start; i < this->number_elements; i++)
      if (this->data[i] == value) {
	this->curpos = i;
	return TRUE;
      }
  } else {
    for (i = start; i < this->number_elements; i++)
      if ((*(this->compare_s))(this->data[i], value) == TRUE) {
	this->curpos = i;
	return TRUE;
      }
  }
  return FALSE;
}


// Type& value () -- Return value at current position.
// Input:            None
// Output:           Type reference to value at current position

template<class Type> 
inline Type& Vector<Type>::value () {
#if ERROR_CHECKING
  if (this->curpos == INVALID)			// If INVALID current position
    this->value_error (#Type);			// Raise exception
#endif
  return (this->data[this->curpos]);
}


// Type& operator[] () -- Access an individual element from a vector.
//                        Range checking is performed.
// Input:                 Integer index of element to access
// Output:                Type reference of element

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


// get() -- Returns the element of THIS.
// Input:   A positive integer index.
// Output:  A Type reference of data in the nth element of THIS.

template <class Type> 
inline Type& Vector<Type>::get(int n) {
#if ERROR_CHECKING  
  if (n >= this->number_elements) // If index out of range
    this->bracket_error (#Type, n);		// Raise exception
#endif
  this->curpos = n;				// Update current position
  return this->data[n];
}

// put() -- Replaces the data slot of the Vector element and if
//          successful, returns the  new data item.
// Input:   A Type reference and a positive integer index.
// Output:  TRUE if nth element exists, FALSE otherwise.

template <class Type> 
inline Boolean Vector<Type>::put(const Type& x, int n) {
  if (n >= this->number_elements)		// False if index out of range
    return FALSE;
  else {
    this->curpos = n;				// Update current position
    this->data[n] = x;				// Store data
    return TRUE;
  }
}

// void grow () -- Adjust the memory size of a Vector to accomodate some size
// Input:            Interger number of elements to hold
// Output:           None

template<class Type> 
void Vector<Type>::grow (long min_size) {
  long new_size = (long)(this->size * (1.0 + growth_ratio)); // New size?
  if (new_size < min_size) new_size = min_size + alloc_size;
  resize(new_size);
}

// void resize () -- Adjust the memory size of a Vector to accomodate some size
// Input:            Interger number of elements to hold
// Output:           None

template<class Type> 
void Vector<Type>::resize (long new_size) {
  if (new_size <= this->size) {			// Don't bother shrinking
#if ERROR_CHECKING  
    if (new_size < 0)				// If index out of range
      this->resize_error (#Type,new_size);	// Raise exception
#endif
    return;
  }
#if ERROR_CHECKING  
  if (alloc_size == INVALID)			// If static size vector
    this->static_error (#Type);			// Raise exception
#endif
#if 0 /* ifndef DOS - Kludge until the following works - LGO 4/1/91 at request of Fred Burk for Mary Fontana */
  Type* temp = (Type*) new char[sizeof(Type) * new_size];   // Allocate storage
  memcpy ((char*)temp, (char*)this->data,
	  (int)(this->size * new_size));	// Copy new 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
}

  
// Boolean operator!= -- Test for inequality of the data of two vectors
// Input:                Reference to Vector object
// Output:               TRUE/FALSE

template<class Type> 
inline Boolean Vector<Type>::operator!= (const Vector<Type>& v) CONST {
  return (!operator== (v));
}


// long position () -- Return current position.
// Input:              None
// Output:             Integer representing current position

template<class Type> 
inline long Vector<Type>::position () CONST {
  return this->Vector::position ();
}


// long set_length () -- Set the number of elements in a Vector object.
//                       If there is not enough storage allocated, set to
//                       maximum size for storage.
// Input:                Length value
// Output:               Integer representing number of elements

template<class Type> 
inline long Vector<Type>::set_length (long n) {
  this->Vector::set_length (n, #Type);		// Call base class with type
  return this->length();			// Return length
}


// void set_compare () -- Specify the comparison function to be used in 
//                        logical comparisons of vector objects
// Input:                 Pointer to a compare function
// Output:                None

template<class Type> 
inline void Vector<Type>::set_compare (Type##_Vector_Compare c) {
  this->compare_s = c;
}


// void set_alloc_size () -- Set the default allocation size growth rate.
// Input:                    Growth size in number of elements
// Output:                   None

template<class Type> 
inline void Vector<Type>::set_alloc_size (int n) {
  this->Vector::set_alloc_size (n, #Type);	// Call base class with size
}


// void set_growth_ratio () -- Set the growth percentage for the Vector object
// Input:                      Float ratio
// Output:                     None

template<class Type> 
inline void Vector<Type>::set_growth_ratio (float ratio) {
  this->Vector::set_growth_ratio (ratio, #Type); // Call base class with size
}


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

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


// Vector<Type> (long) -- Constructor that specifies number of elements.
// Input:                 Number of elements 
// Output:                None

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


// Vector<Type> (void*, long) -- Constructor that specifies user-defined static
//                               size storage and number of elements
// Input:                        Pointer to storage, number of elements 
// Output:                       None

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


// Vector<Type> (long, Type&) -- Constructor that specifies number of elements
//                               and also an initialization value to set all
//                               elements.
// Input:   Number of elements and Type reference to initialization value
// Output:  None

template<class Type> 
Vector<Type>::Vector<Type> (unsigned long n, const Type& value)
#ifdef __cplusplus
 : Vector(n)
#else
 : (n)
#endif
{
  this->data = (Type*) new Type[n];		// Allocate memory
  for (long i = 0; i < n; i++)			// For each element in Vector
    this->data[i] = value;			// Set initial value
  this->number_elements = n;			// Set element count
}


// Vector<Type> (long,int, ...) -- Constructor that specifies number of elements
//                                 and also a variable number of references to
//                                 initialization values for successive elements
//                                 in the vector.
// Input:   Number of elements, number of initial values, and initial values
// Output:  None

template<class Type> 
Vector<Type>::Vector<Type> (unsigned long n, int v, ...)
#ifdef __cplusplus
 : Vector(n)
#else
 : (n)
#endif
{
  this->data = (Type*) new Type[n];		// Allocate memory
  this->number_elements = v;			// Update element count
  va_list argp;					// Declare argument list
  va_start (argp, v);				// Initialize macro
  for (int i = 0; i < v; i++)			// For remaining values given
    this->data[i] = EXPAND_ARGS(va_arg, argp, Type); // Extract and assign
  va_end (argp);
}


// Vector<Type> (<Vector<Type>&) -- Constructor for reference to another
//                                  Vector object.
// Input:   Vector reference
// Output:  None

template<class Type> 
Vector<Type>::Vector<Type> (const Vector<Type>& v)
#ifdef __cplusplus
 : Vector(v)
#else
 : (v)
#endif
{
  this->data = (Type*) new Type[v.size];	// Allocate enough storage
  for (long i = 0; i < v.number_elements; i++)	// For each element in Vector
     this->data[i] = v.data[i];			// Copy value
}


// ~Vector<Type> () -- Destructor for Vector class that frees up storage.
// Input:              None
// Output:             None

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


// Boolean is_data_equal () -- Default data comparison function if user has
//                             not provided another method
// Input:                      Two Type references
// Output:                     TRUE/FALSE

template<class Type> Vector {
  Boolean Type##_Vector_is_data_equal (const Type& t1, const Type& t2) {
    return ((t1 == t2) ? TRUE : FALSE);
  }
}


// Vector<Type&> operator= () -- Overload the assignment operator
// Input:                        Reference to Vector object
// Output:                       Reference to copied Vector object

template<class Type> 
Vector<Type>& Vector<Type>::operator= (const Vector<Type>& v) {
  if (this->size < v.size) {			// If not enough memory
#if ERROR_CHECKING
    if (alloc_size == INVALID)			// If static size vector
      this->assign_error (#Type);		// Raise exception
#endif
    if (this->size != 0)
      delete [this->size] this->data;		// Free it up
    this->data = (Type*) new Type[v.size];	// and allocate bigger memory
    this->size = v.size;			// Set new vector size
  }
  this->Vector::operator= (v);			// Base class assignment
  for (long i = 0; i < v.number_elements; i++)	// For each element
    this->data[i] = v.data[i];			// Copy value
  return *this;					// Return Vector reference
}


// Vector<Type>& operator= () -- Overload the assignment operator to assign a
//                               single value to all the elements of a vector
// Input:                        Type reference to fill value
// Output:                       Reference to updated Vector object

template<class Type> 
Vector<Type>& Vector<Type>::operator= (const Type& value) {
  for (long i = 0; i < this->number_elements; i++) // For each element in Vector
    this->data[i] = value;			   // Set initial value
  this->curpos = INVALID;			   // Point to first element
  return *this;					   // Return Vector reference
}

// ostream& operator<< () -- Overload the output operator for Vector pointer
// Input:                    Ostream reference and Vector pointer
// Output:                   Ostream reference

template<class Type> Vector {
ostream& operator<< (ostream& os, CONST Vector<Type>* v) {
  return operator<< (os, *v);
}
}

  
// ostream& operator<< () -- Overload the output operator for Vector reference
// Input:                    Ostream reference and Vector reference
// Output:                   Ostream reference

template<class Type> Vector {
ostream& operator<< (ostream& os, CONST Vector<Type>& v) {
  if (v.length() == 0)				// If no elements in vector
    os << " Empty ";				// Indicate empty status
  else {
    os << "[ ";
    for (long i = 0; i < v.length(); i++)	// For each element
      os << v.data[i] << " ";			// Output value to stream
    os << "]";
  }
  return os;					// Return ostream reference
}
}


// Boolean operator== () -- Compare the elements of this Vector with a second
// Input:                   Reference to vector object
// Output:                  TRUE/FALSE

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


// void fill () -- Fill elements `start' through `end' inclusive with valuen
// Input:          Type reference, start inclusive, and end index exclusive
// Output:         None


template<class Type> 
void Vector<Type>::fill (const Type& value, unsigned long start, long end) {
  if (end == -1)				// If no value given
    end = this->number_elements;		// Fill until end
#if ERROR_CHECKING  
  if (start >= this->number_elements)		// If start out of range
    this->fill_start_error (#Type, start);	// Raise exception
  if (end < start || end > this->number_elements) // If end out of range
    this->fill_end_error (#Type, end);		// Raise exception
#endif
  for (long i = start; i < end; i++)		// For each element in range
    this->data[i] = value;			// Assign new value
  this->curpos = INVALID;			// Invalidate current position
}


// long position () -- Find first occurrence of element in a Vector.
// Input:              Element value searching for
// Output:             Integer representing index or -1 if not found

template<class Type> 
long Vector<Type>::position (const Type& value) {
  if (this->find(value)) return this->curpos;
  else return -1;
}


// void copy () -- Copy a specified range of elements from one vector to this
// Input:          Vector reference, start inclusive, and end index exclusive
// Output:         None

template<class Type> 
void Vector<Type>::copy (const Vector<Type>& v, unsigned long start, long end){
  if (end == -1)				// If no value given
    end = v.number_elements;			// Copy until end
#if ERROR_CHECKING  
  if (start >= v.number_elements)		// If start out of range
    this->copy_start_error (#Type, start);	// Raise exception
  if (end < start || end > v.number_elements)	// If end out of range
    this->copy_end_error (#Type, end);		// Raise exception
#endif
  if (this->size < end) {			// If not enough memory
#if ERROR_CHECKING
    if (alloc_size == INVALID)			// If static size vector
      this->copy_error (#Type);			// Raise exception
#endif
    this->grow(end);
  }
  for (long i = start; i < end; i++)		// For each element in range
    this->data[i] = v.data[i];			// Assign new value
  if (i > this->number_elements)		// If we added new elements
    this->number_elements = i;			// Update element count
  this->curpos = i;				// Update current position
}


// search -- Find a subsequence of elements in a Vector
// Input:    Vector reference to subsequence searching for,
//           start inclusive, and end index exclusive
// Output:   TRUE/FALSE; current position updated if found

template<class Type> 
Boolean Vector<Type>::search (const Vector<Type>& v, long start, long end) {
  register long i, j;
  if (end == -1)				// If no end index given
    end = this->number_elements;		// Set to number of elements
  end -= v.number_elements;
  if (this->compare_s == NULL) {
    for (i = start; i < end; i++) {		// Find start of subsequence
      for (j = 0; j < v.number_elements; j++)
	if (!(this->data[i+j] == v.data[j]))	// If not equal
	  goto again1;				// try again
      this->curpos = i;				// Point to start of sequence
      return TRUE;				// Return starting index
    again1:;
    }
  } else {
    for (i = start; i < end; i++) {		// Find start of subsequence
      for (j = 0; j < v.number_elements; j++)
	if (!(*this->compare_s)(this->data[i+j],v.data[j])) // If not equal
	  goto again2;				// try again
      this->curpos = i;				// Point to start of sequence
      return TRUE;				// Return starting index
    again2:;
    }
  }
  return FALSE;
}


// push -- Add element to end of the Vector
// Input:  Type reference
// Output: TRUE if successful, FALSE if could not grow vector

template<class Type> 
Boolean Vector<Type>::push (const Type& value) {
  if (this->number_elements == this->size) {	// If not enough memory
    if (this->alloc_size == INVALID)		// If not allowed to grow
      return FALSE;				// Return failure flag
    this->grow(this->size+1);			// Else grow the Vector
  }
  this->curpos = this->number_elements;		// Set current position
  this->data[this->number_elements++] = value;	// Assign new value
  return TRUE;					// Return success status
}


// push_new -- Add an element if it is not already there
// Input:      Reference to Type
// Output:     TRUE/FALSE

template<class Type> 
Boolean Vector<Type>::push_new (const Type& value) {
  if (this->number_elements == this->size && this->alloc_size == INVALID)
    return FALSE;				// Return failure flag
  if (this->find(value)) return FALSE;		// If already in Vector
  if (this->number_elements >= this->size)	// If not enough memory
    this->grow(this->size+1);			// Else grow the Vector
  this->curpos = this->number_elements;		// Set current position
  this->data[this->number_elements++] = value;	// Assign new value
  return TRUE;					// Return success status
}


// pop --   Return last element in the Vector
// Input:   None
// Output:  Type reference to last element in Vector

template<class Type> 
Type& Vector<Type>::pop () {
  if (this->number_elements > 0) {		// If there are elements
    this->curpos = INVALID;			// Invalidate current position
    return (this->data[--this->number_elements]); // Return the last one
  }
}


// reverse -- Destructively reverse the order of elements in a Vector
// Input:     None
// Output:    None

template<class Type> 
void Vector<Type>::reverse () {
  Type temp;
  for (long i = 0, j = this->number_elements-1;	// Counting from front and rear
       i < this->number_elements / 2; i++, j--) { // until we reach the middle
    temp = this->data[i];			// Save front data item
    this->data[i] = this->data[j];		// Switch with rear data item
    this->data[j] = temp;			// Copy new rear data item
  }
  this->curpos = INVALID;			// Invalidate current position
}


// remove -- Destructively remove item at current position
// Input:   None
// Output:  Type reference to item removed

template<class Type> 
Type Vector<Type>::remove () {
  long i = this->curpos;
  if (i == INVALID) this->remove_error(#Type);
  Type value = this->data[i];
  int* words = (int*) &this->data[i];		// Avoid using operator=
  long n = (this->number_elements - i) * (sizeof(Type) / sizeof(int));
  while(n-- > 0)				// Copy over current
    *words = *(words + (sizeof(Type) / sizeof(int))), words++;
  this->number_elements--;			// Update element count
  if (this->curpos == this->number_elements)	// If past end of vector
    this->curpos = INVALID;			// Invalidate current position
  return value;					// Return Vector reference
}


// remove -- Destructively remove the first occurrence of an element
// Input:   Type reference
// Output:  TRUE if element found and removed, FALSE otherwise

template<class Type> 
Boolean Vector<Type>::remove (const Type& value) {
  if (this->find(value)) {			// When found
    long i = this->curpos;
    int* words = (int*) &this->data[i];		// Avoid using operator=
    long n = (this->number_elements - i) * (sizeof(Type) / sizeof(int));
    while(n-- > 0)				// Copy over current
      *words = *(words + (sizeof(Type) / sizeof(int))), words++;
    this->number_elements--;			// Update element count
    return TRUE;
  } else return FALSE;
}


// remove_duplicates -- Destructively remove duplicate elements from Vector
// Input:               None
// Output:              TRUE if any removed, FALSE otherwise

template<class Type> 
Boolean Vector<Type>::remove_duplicates () {
  this->curpos = INVALID;			// Invalidate current position
  Boolean success = FALSE;			// Return value
  if (this->size == 0) return success;
  Type* old = this->data;			// Old data
  this->data = new Type[this->size];		// New data
  long n = this->number_elements;		// length of old data
  this->number_elements = 0;
  for (long i = 0; i < n; i++) {		// For each element
    if (!this->find(old[i])) {			// if not copied yet
      this->data[this->number_elements++] = old[i]; // copy value
      success = TRUE;				// Set flag
    }
  }
  delete [this->size] old;			// destroy old data
  return success;
}


// replace -- Destructively replace the first occurrence of an element
// Input:     Two Type references
// Output:    TRUE if element found and replaced, FALSE otherwise

template<class Type> 
Boolean Vector<Type>::replace (const Type& t1, const Type& t2) {
  if (this->find(t1)) {
    this->data[this->curpos++] = t2;		// Point to item after replace
    if (this->curpos > this->number_elements) this->curpos = INVALID;
    return TRUE;
  } else return FALSE;
}


// replace_all -- Destructively replace all occurrences of an element
// Input:         Two Type references
// Output:        TRUE if any element replaced, FALSE otherwise

template<class Type> 
Boolean Vector<Type>::replace_all (const Type& t1, const Type& t2) {
  Boolean success = FALSE;		     	       // Return value
  this->curpos = 0;
  for (;;) {
    if (!this->find(t1, this->curpos)) return success;
    this->data[this->curpos++] = t2;		// Point to item after replace
    if (this->curpos > this->number_elements) this->curpos = INVALID;
  }
}


// prepend -- Destructively insert the elements of some Vector at the beginning
// Input:     Vector reference
// Output:    TRUE if successful, FALSE if could not grow Vector

template<class Type> 
Boolean Vector<Type>::prepend (const Vector<Type>& v) {
  Type* temp;					// Declare temporary
  long old_size = this->size;			// Keep old size
  long new_size = this->number_elements + v.number_elements; // Minimum size
  if (this->size < new_size) {			// Enough memory?
    if (this->alloc_size == INVALID)		// If not allowed to grow
      return FALSE;				// Return failure flag
    this->size = (long)(this->size * (1.0 + growth_ratio)); // New size
    if (this->size < new_size)			// If not enough
      this->size = new_size + this->alloc_size;	// use alloc_size
  }
  temp = new Type[this->size];			// Allocate required storage
  for (long i = 0; i < v.number_elements; i++)	// For all elements
    temp[i] = v.data[i];			// Copy to beginning of Vector
  this->curpos = i;				// Set current position
  for (i = 0; i < this->number_elements; i++)	// For each element
    temp[i+v.number_elements] = this->data[i];  // Copy into new storage
  if (old_size != 0)
    delete [old_size] this->data;		// Free up old memory
  this->data = temp;				// Assign new memory block
  this->number_elements += v.number_elements;	// Update element count
  return TRUE;					// Return success flag
}


// append -- Destructively append the elements of some Vector at the beginning
// Input:    Vector reference
// Output:   TRUE if successful, FALSE if could not grow Vector

template<class Type> 
Boolean Vector<Type>::append (const Vector<Type>& v) {
  long new_size = this->number_elements + v.number_elements; // Minimum size
  if (this->size < new_size) {			// Enough memory?
    if (this->alloc_size == INVALID)		// If not allowed to grow
      return FALSE;				// Return failure flag
    this->grow(new_size);
  }
  this->curpos = this->number_elements - 1;	// Set current position
  for (long i = 0; i < v.number_elements; i++)	// For each element
    this->data[i+this->number_elements] = v.data[i]; // Copy to end of Vector
  this->number_elements += v.number_elements;	// Update element count
  return TRUE;					// Return Vector reference
}


// insert_before -- Destructively insert an element before current position
// Input:           Type reference
// Output:          TRUE if successful, FALSE if could not grow Vector

template<class Type> 
Boolean Vector<Type>::insert_before (const Type&  value) {
  if (this->curpos == INVALID)			// If no current position
    return FALSE;				// Return failure flag
  return this->insert_before(value, this->curpos);
}


// insert_after -- Destructively insert an element after current position
// Input:          Type reference
// Output:         TRUE if successful, FALSE if could not grow Vector

template<class Type> 
Boolean Vector<Type>::insert_after (const Type&  value) {
  if (this->curpos == INVALID)			// If no current position
    return FALSE;				// Return failure flag
  return this->insert_after(value, this->curpos);
}


// insert_before -- Destructively insert an element before specified index
// Input:           Type reference and an index position
// Output:          TRUE if successful, FALSE if could not grow Vector

template<class Type> 
Boolean Vector<Type>::insert_before (const Type&  value, long index) {
  long n = this->number_elements+1;
  if (n >= this->size) {			// If not enough memory
    if (this->alloc_size == INVALID)		// If not allowed to grow
      return FALSE;				// Return failure flag
    this->grow(n);
  }
  this->curpos = index;
  int* words = (int*) &this->data[n];		// Avoid using operator=
  n = (n - index) * (sizeof(Type) / sizeof(int));
  while(--n >= 0)				// Copy over current
    words--, *words = *(words - (sizeof(Type) / sizeof(int)));
  this->data[index] = value;			// Assign new value
  this->number_elements++;
  return TRUE;					// Return Vector reference
}


// insert_after -- Destructively insert an element after specified index
// Input:          Type reference and an index position
// Output:         TRUE if successful, FALSE if could not grow Vector

template<class Type> 
Boolean Vector<Type>::insert_after (const Type&  value, long index) {
  long n = this->number_elements+1;
  if (n >= this->size) {			// If not enough memory
    if (this->alloc_size == INVALID)		// If not allowed to grow
      return FALSE;				// Return failure flag
    this->grow(n);
  }
  this->curpos = ++index;
  int* words = (int*) &this->data[n];		// Avoid using operator=
  n = (n - index) * (sizeof(Type) / sizeof(int));
  while(--n >= 0)				// Copy over current
    words--, *words = *(words - (sizeof(Type) / sizeof(int)));
  this->data[index] = value;			// Assign new value
  this->number_elements++;
  return TRUE;					// Return Vector reference
}


// merge -- Destructively merge two Vectors of the same size using a user
//          supplied predicate function. The predicate function returns
//          TRUE if and only if the first element preceeds the second.
// Input:   Vector reference and pointer to Predicate function
// Output:  None

template<class Type> 
void Vector<Type>::merge(const Vector<Type>& v,Type##_Vector_Predicate pred) {
  long old_size = this->size;			// Keep old size
  long total = this->number_elements+v.number_elements; // Min space required
  if (this->size < total) {
    this->size = (long)(this->size*(1.0+growth_ratio)); // New size by ratio
    if (this->size < total)			      // check growth
      this->size = total + this->alloc_size;	      // New size by growth
  }
  Type* temp = new Type[this->size];		// Allocated storage
  for (long i=0,j=0,k=0; i < total; i++) {	// For all elements
    if (j >= this->number_elements) {		// If past end of vector
      for (; k < v.number_elements; k++, i++)	// Copy rest of other vector
	temp[i] = v.data[k];			// Copy element value
      break;					// Break out of loop when done
    }
    else if (k >= v.number_elements) {		// If past end of other vector
      for (; j < this->number_elements;j++,i++) // Copy rest of other vector
	temp[i] = this->data[j];		// Copy element value
      break;					// Break out of loop when done
    }
    else {
      if ((*pred)(this->data[j], v.data[k]) < 0) // If it goes here
	temp[i] = this->data[j++];		// Copy first element
      else
	temp[i] = v.data[k++];			// Copy second element
    }
  }
  if (old_size != 0)
    delete [old_size] this->data;		// Free up old memory
  this->data = temp;				// Assign new memory block
  this->number_elements = total;		// Update element count
  this->curpos = INVALID;			// Invalidate current position
}


// sort -- Destructively sort the elements of a vector using the supplied
//         predicate function. The predicate function returns TRUE if and only
//         if the first element preceeds the second. This routine uses the 
//         Heap Sort algorithm as given in "Numerical Recipes in C" p247.
// Input:   Pointer to predicate function
// Output:  None
 
#ifdef __cplusplus
#if defined(DOS)
extern "C" {
#include <stdlib.h>		// include the standard c library
}
#else
#include <stdlib.h>		// include the standard c library
#endif

template<class Type> 
void Vector<Type>::sort (Type##_Vector_Predicate p) {
  if (this->number_elements > 1)		// If more than one element
    qsort((void*) this->data,
	  (unsigned int) this->number_elements, sizeof(Type),
	  (int(*)(const void*, const void*)) p);
}

#else						// Not all machines have qsort

template<class Type> 
void Vector<Type>::sort (Type##_Vector_Predicate p) {
  if (this->number_elements > 1) {		// If more than one element
    long n = this->number_elements;
    long l, j, ir, i;
    Type temp;
    Type* v_prime = this->data - 1;		// Adjust for 1-based index
    l = (n >> 1) + 1;
    ir = n;
    while (TRUE) {
      if (l > 1)
	temp = v_prime[--l];
      else {
	temp = v_prime[ir];
	v_prime[ir] = v_prime[1];
	if (--ir == 1) {
	  v_prime[1] = temp;
	  break;
	}
      }
      i = l;
      j = i << 1;
      while (j <= ir) {
	if (j < ir && (*p)(v_prime[j], v_prime[j+1]) < 0)
	  ++j;
	if ((*p)(temp, v_prime[j]) < 0) {
	  v_prime[i] = v_prime[j];
	  j += (i = j);
	}
	else
	  j = ir + 1;
      }
      v_prime[i] = temp;
    }
    this->curpos = INVALID;			// Invalidate current position
  }
}
#endif
    
// If all the generic support hasn't been loaded yet, do it now.
// Unless this is being loaded from inside Association.h
// When this is true, Association.h will load Generic.h

#if ! defined GENERIC_H && ! defined ASSOCIATIONH
#include <cool/Generic.h>
#endif

#endif						// End ifdef of VECTORH
