/* seq.h
 *
 * A structure to hold a sequence of elements.
 *
 *   PUBLIC VARIABLES
 *
 *     none!
 *
 *   CONSTRUCTORS
 *
 *     seq()               Create an empty sequence
 *
 *   PUBLIC FUNCTIONS
 *
 *     add( x )            Add x to the end of the sequence
 *     remove()            Remove the last element of the sequence
 *     remove( i )         Remove the i^{th} element of the sequence (expensive)
 *     operator [i]        Returns the i^{th} element (starting from 0)
 *     exists( x )         Return true if x exists in sequence, false otherwise
 *     clear()             Deletes the whole sequence
 */


#ifndef SEQ_H
#define SEQ_H

#include <iostream.h>


template<class T> class seq {

  int storageSize;
  int numElements;
  T  *data;

public:

  seq() {			// constructor
    storageSize = 1;
    numElements = 0;
    data = new T[ storageSize ];
  }

  ~seq() {			// destructor
    delete [] data;
  }

  seq( const seq<T> & source ) { // copy constructor

    storageSize = source.storageSize;
    numElements = source.numElements;
    data = new T[ storageSize ];
    for (int i=0; i<numElements; i++)
      data[i] = source.data[i];
  }

  void remove() {
    if (numElements == 0) {
      cerr << "remove: Tried to remove element from empty sequence\n";
      abort();
    }

    numElements = numElements - 1;
  }

  void remove( int i );

  int size() const {
    return numElements;
  }

  T & operator [] ( int i ) const {
    if (i >= numElements || i < 0) {
      cerr << "element: Tried to access an element beyond the range of the sequence\n";
      abort();
    }
    return data[ i ];
  }

  void clear() {
    delete [] data;
    storageSize = 1;
    numElements = 0;
    data = new T[ storageSize ];
  }

  void add( const T &x );
  bool exists( const T &x );
};


// Add an element to the end of the sequence

template<class T>
void 
seq<T>::add( const T &x )

{
  // No storage left?  If so, double the storage

  if (numElements == storageSize) {
    T *newData;

    newData = new T[ storageSize * 2 ];
    for (int i=0; i<storageSize; i++)
      newData[i] = data[i];
    storageSize = storageSize * 2;
    delete [] data;
    data = newData;
  }

  // Store the element in the next available position

  data[ numElements ] = x;
  numElements++;
}


// Find and return an element

template<class T>
bool 
seq<T>::exists( const T &x )

{
  for (int i=0; i<numElements; i++)
    if (data[i] == x)
      return true;

  return false;
}


template<class T>
void 
seq<T>::remove( int i )

{
  if (i < 0 || i >= numElements) {
    cerr << "remove: Tried to remove element " << i
	 << " from a sequence of " << numElements << " elements \n";
    abort();
  }

  for (int j=i; j<numElements-1; j++)
    data[j] = data[j+1];

  numElements--;
}



#endif
