---

rdArray.h

// rdArray.h
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Copyright 2003 Realistic Dynamics, Inc.
// All rights reserved.
//
// Please do not read, copy, distribute, or use without permission.
// Contact: Frank C. Anderson, fca@RealisticDynamics.com
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
#ifndef __rdArray_h__
#define __rdArray_h__


#include "rdTools.h"
#include "rdException.h"

static const int rdArray_CAPMIN = 1;

//=============================================================================
//=============================================================================
template<class T> class rdArray
{

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// DATA
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
protected:
   int _size;
   int _capacity;
   int _capacityIncrement;
   T _defaultValue;
   T *_array;

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// METHODS
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//=============================================================================
// CONTRUCTION
//=============================================================================
public:
//_____________________________________________________________________________
virtual ~rdArray()
{
   if(_array!=NULL) { delete[] _array;  _array = NULL; }
}
//_____________________________________________________________________________
rdArray(const T &aDefaultValue,int aSize=0,int aCapacity=rdArray_CAPMIN)
{
   setNull();

   // DEFAULT VALUE
   _defaultValue = aDefaultValue;

   // CAPACITY
   int newCapacity;
   int min = aSize + 1;
   if(min < aCapacity) min = aCapacity;
   computeNewCapacity(min,newCapacity);
   ensureCapacity(newCapacity);

   // SIZE
   _size = aSize;
   if(_size<0) _size=0;
}
//_____________________________________________________________________________
rdArray(const rdArray<T> &aArray)
{
   setNull();
   *this = aArray;
}

private:
//_____________________________________________________________________________
void setNull()
{
   _size = 0;
   _capacityIncrement = -1;
   _capacity = 0;
   _array = NULL;
}


//=============================================================================
// OPERATORS
//=============================================================================
public:
//-----------------------------------------------------------------------------
// BRACKETS ([])
//-----------------------------------------------------------------------------
//_____________________________________________________________________________
T& operator[](int aIndex) const
{
   return(_array[aIndex]);
}

//-----------------------------------------------------------------------------
// ASSIGNMENT (=)
//-----------------------------------------------------------------------------
//_____________________________________________________________________________
rdArray<T>& operator=(const rdArray<T> &aArray)
{
   _size = aArray._size;
   _capacity = aArray._capacity;
   _capacityIncrement = aArray._capacityIncrement;
   _defaultValue = aArray._defaultValue;

   // ARRAY
   if(_array!=NULL) delete[] _array;
   _array = new T[_capacity];
   for(int i=0;i<_capacity;i++) _array[i] = aArray._array[i];

   return(*this);
}


//=============================================================================
// CAPACITY
//=============================================================================
//_____________________________________________________________________________
bool computeNewCapacity(int aMinCapacity,int &rNewCapacity)
{
   rNewCapacity = _capacity;
   if(rNewCapacity < rdArray_CAPMIN) rNewCapacity = rdArray_CAPMIN;

   // CHECK FOR ZERO INCREMENT
   if(_capacityIncrement == 0) {
      printf("rdArray.computeNewCapacity: WARN- capacity is set");
      printf(" not to increase (i.e., _capacityIncrement==0).\n");
      return(false);
   }

   // INCREMENT UNTIL LARGER THAN THE MINIMUM SIZE
   while(rNewCapacity < aMinCapacity) {
      if(_capacityIncrement < 0) {
         rNewCapacity = 2 * rNewCapacity;
      } else {
         rNewCapacity = rNewCapacity + _capacityIncrement;
      }
   }

   return(true);
}
//_____________________________________________________________________________
bool ensureCapacity(int aCapacity)
{
   // CHECK REQUESTED CAPACITY
   if(aCapacity < rdArray_CAPMIN) aCapacity = rdArray_CAPMIN;
   if(_capacity>=aCapacity) return(true);

   // ALLOCATE THE NEW ARRAY
   int i;
   T *newArray = new T[aCapacity];
   if(newArray==NULL) {
      printf("rdArray.ensureCapacity: ERR- failed to increase capacity.\n");
      return(false);
   }

   // COPY CURRENT ARRAY
   if(_array!=NULL) {
      for(i=0;i<_size;i++) newArray[i] = _array[i];
      for(i=_size;i<aCapacity;i++) newArray[i] = _defaultValue;
      delete []_array;  _array=NULL;
   } else {
      for(i=0;i<aCapacity;i++) newArray[i] = _defaultValue;
   }
   
   // REASSIGN
   _capacity = aCapacity;
   _array = newArray;

   return(true);
}
//_____________________________________________________________________________
void trim()
{
   // COMPUTE NEW CAPACITY
   int newCapacity = _size + 1;
   if(newCapacity>=_capacity) return;
   if(newCapacity<rdArray_CAPMIN) newCapacity = rdArray_CAPMIN;

   // ALLOCATE TEMPORARY ARRAY
   int i;
   T *array = new T[newCapacity];
   if(array==NULL) {
      printf("rdArray.trim: ERR- unable to allocate temporary array.\n");
      return;
   }

   // COPY CURRENT ARRAY
   for(i=0;i<_size;i++) array[i] = _array[i];

   // DELETE OLD ARRAY
   delete[] _array;

   // ALLOCATE NEW ARRAY
   _array = new T[newCapacity];
   if(_array==NULL) {
      printf("rdArray.trim: ERR- unable to allocate array.\n");
      return;
   }

   // RESET PREVIOUS VALUES
   for(i=0;i<_size;i++) _array[i] = array[i];
   _array[_size] = _defaultValue;

   // SET CORRECT CAPACITY
   _capacity = newCapacity;
}
//_____________________________________________________________________________
int getCapacity() const
{
   return(_capacity);
}

//-----------------------------------------------------------------------------
// CAPACITY INCREMENT
//-----------------------------------------------------------------------------
//_____________________________________________________________________________
void setCapacityIncrement(int aIncrement)
{
   _capacityIncrement = aIncrement;
}
//_____________________________________________________________________________
int getCapacityIncrement() const
{
   return(_capacityIncrement);
}

//=============================================================================
// STORAGE OPERATIONS
//=============================================================================
//-----------------------------------------------------------------------------
// SIZE
//-----------------------------------------------------------------------------
//_____________________________________________________________________________
bool setSize(int aSize)
{
   if(aSize==_size) return(true);
   if(aSize<0) aSize = 0;
   bool success = true;
   if(aSize<_size) {
      int i;
      for(i=(_size-1);i>=aSize;i--) _array[i] = _defaultValue;
      _size = aSize;
   } else if(aSize<=_capacity) {
      _size = aSize;
   } else {
      int newCapacity;
      success = computeNewCapacity(aSize+1,newCapacity);
      if(!success) return(false);
      success = ensureCapacity(newCapacity);
      if(success) _size = aSize;
   }

   return(success);
}
//_____________________________________________________________________________
int getSize() const
{
   return(_size);
}

//-----------------------------------------------------------------------------
// APPEND
//-----------------------------------------------------------------------------
//_____________________________________________________________________________
int append(const T &aValue)
{
   // ENSURE CAPACITY
   if((_size+1)>=_capacity) {
      int newCapacity;
      bool success;
      success = computeNewCapacity(_size+1,newCapacity);
      if(!success) return(_size);
      success = ensureCapacity(newCapacity);
      if(!success) return(_size);
   }

   // SET
   _array[_size] = aValue;
   _size++;

   return(_size);
}
//_____________________________________________________________________________
int append(const rdArray<T> &aArray)
{
   // LOOP THROUGH THE ELEMENTS
   int i,n=aArray.getSize();
   for(i=0;i<n;i++) {
      append(aArray[i]);
   }

   return(_size);
}

//-----------------------------------------------------------------------------
// INSERT
//-----------------------------------------------------------------------------
//_____________________________________________________________________________
int insert(int aIndex,const T &aValue)
{
   // NEGATIVE INDEX
   if(aIndex<0) {
      printf("rdArray.insert: ERR- aIndex was less than 0.\n");
      return(_size);
   }

   // INDEX PAST END OF ARRAY
   if(aIndex>=_size) {
      setSize(aIndex+1);
      _array[aIndex] = aValue;
      return(_size);
   }

   // ENSURE CAPACITY
   if((_size+1)>=_capacity) {
      int newCapacity;
      bool success;
      success = computeNewCapacity(_size+1,newCapacity);
      if(!success) return(_size);
      success = ensureCapacity(newCapacity);
      if(!success) return(_size);
   }

   // SHIFT ARRAY
   int i;
   for(i=_size;i>aIndex;i--) {
      _array[i] = _array[i-1];
   }

   // SET
   _array[aIndex] = aValue;
   _size++;

   return(_size);
}

//-----------------------------------------------------------------------------
// REMOVE
//-----------------------------------------------------------------------------
//_____________________________________________________________________________
int remove(int aIndex)
{
   if(aIndex<0) {
      printf("rdArray.remove: ERR- aIndex was less than 0.\n");
      return(_size);
   }
   if(aIndex>=_size) {
      printf("rdArray.remove: ERR- aIndex was greater than or equal the ");
      printf("size of the array.\n");
      return(_size);
   }

   // SHIFT ARRAY
   int i;
   _size--;
   for(i=aIndex;i<_size;i++) {
      _array[i] = _array[i+1];
   }
   _array[_size] = _defaultValue;


   return(_size);
}

//-----------------------------------------------------------------------------
// SET AND GET
//-----------------------------------------------------------------------------
//_____________________________________________________________________________
void set(int aIndex,const T &aValue)
{
   if(aIndex<0) return;

   // ENSURE CAPACITY
   bool success = false;
   if((aIndex+2)>=_capacity) {
      int newCapacity;
      success = computeNewCapacity(aIndex+2,newCapacity);
      if(!success) return;
      success = ensureCapacity(newCapacity);
      if(!success) return;
   }

   // SET
   _array[aIndex] = aValue;

   // FIRST EMPTY
   if(aIndex>=_size)  _size = aIndex+1;
}
//_____________________________________________________________________________
T& get(int aIndex) const
{
   if((aIndex<0)||(aIndex>=_size)) {
      throw(rdException("Array index out of bounds."));
   }
   return(_array[aIndex]);
}
//_____________________________________________________________________________
T& getLast() const
{
   if(_size<=0) {
      throw(rdException("Array is empty."));
   }
   return(_array[_size-1]);
}
   //void insert(int aIndex,const T &aValue);
   //void remove(int aIndex);
   //void remove(const T &aValue);


//=============================================================================
// SEARCH
//=============================================================================
//_____________________________________________________________________________
int searchBinary(const T &aValue,bool aFindFirst=false,
                 int aLo=-1,int aHi=-1) const
{
   if(_size<=0) return(-1);
   int lo = aLo;  if(lo<0) lo = 0;
   int hi = aHi;  if((hi<0)||(hi>=_size)) hi = _size - 1;
   int mid;

   // CHECK lo AND hi
   if(lo>hi) return(-1);

   // SEARCH
   while(lo <= hi) {
      mid = (lo + hi) / 2;
      if(aValue < _array[mid]) {
         hi = mid - 1;
      } else if(_array[mid] < aValue) {
         lo = mid + 1;
      } else {
         break;
      }
   }

   // MAKE SURE LESS THAN
   if(aValue < _array[mid]) mid--;
   if(mid<=0) {
      return(mid);
   }

   // FIND FIRST
   if(aFindFirst) {
      if(_array[mid-1]<_array[mid]) {
         return(mid);
      }
      lo = aLo;  if(lo<0) lo = 0;
      hi = mid;
      int mid2 = mid;
      T value2 = _array[mid];
      while(lo <= hi) {
         mid2 = (lo + hi) / 2;
         if(_array[mid2] == value2) {
            hi = mid2 - 1;
         } else if(_array[mid2] < value2) {
            lo = mid2 + 1;
         }
      }
      if(_array[mid2]<value2) mid2++;
      if(mid2<mid) mid = mid2;
   }

   return(mid);
}

//=============================================================================
}; // END of class rdArray
//=============================================================================
//=============================================================================


#endif //__rdArray_h__

---