Listing 3 The base class SPListBase

// This is a partial listing of
// the base class for SPList,
// it handles the underlying dynamic
// array mechanism
template<class T>
class SPListBase
{
private:
  enum{ALLOCINC=20}; // default array size
  T *a;         // the actual data
  int cnt;      // the number of elements in the array
  int first;    // the start of the array
  int allocated;// amount allocated for the array
  int allocinc; // amount to re-allocate to array
  
  void grow(int amnt= 0, int newcnt= -1); // make array grow

protected:
  void compact(const int i); // remove an element from the array

public:
  SPListBase(int n= ALLOCINC) // default constructor
  {
    a= new T[n];
    cnt= 0;
    first= n>>1; // start off in the middle
    allocated= n;
    allocinc= n;
  }
  
  // copy constructor
  SPListBase(const SPListBase<T>& n);
  // assignment operator
  SPListBase<T>& SPListBase<T>: :operator=(const SPListBase<T>& n);
  
  virtual ~SPListBase() { // destuctor
    delete [] a;
  }
  
  // index operator
  INLINE T& operator[](const int i);
  
  const T& operator[](const int i) const{
    // generate an assert error if indices don't make sense
    assert((i >= 0) && (i < cnt));
    return a[first+i];
  }
  
  int count(void) const{ return cnt; }
  
  // add an element to the end of the array
  void add(const T& n){
    if(cnt+first >= allocated) grow();
    a[first+cnt]= n;
    cnt++;
  }
  
  // add an element into middle of array
  void add(const int i, const T& n);
  
  // reset array
  void erase(void){ cnt= 0; first= (allocated>>1);{
};

// Allow the array to grow if index is out of range
template <class T>
INLINE T& SPListBase<T>::operator[] (const int i)
{
  assert((i >= 0) && (first > 0) && ((first+cnt) <= allocated));
  int indx= first+i;
  
  if(indx >= allocated){ // need to grow it
    // index as yet unused element
    grow((indx-allocated)+allocinc, i+1);
    indx= first+i; // first will have changed in grow()
  }
  assert(indx >= 0 && indx < allocated);
  
  if(i >= cnt) cnt= i+1; // it grew
  return a[indx];
}
// End of File