Main Page | Namespace List | Class Hierarchy | Compound List | File List | Compound Members | File Members

GrowableArray< T > Class Template Reference

GrowableArray template is used to create array objects that will grow as elements are added to the end of the array. More...

#include <GrowableArray.h>

Collaboration diagram for GrowableArray< T >:

Collaboration graph
[legend]
List of all members.

Public Member Functions

 GrowableArray ()
 GrowableArray (size_t initialSize)
 ~GrowableArray ()
const size_t length (void) const
T & operator[] (const size_t i) throw (std::out_of_range)
T operator[] (const size_t i) const throw (std::out_of_range)
const T * getData () const
void append (T item) throw (std::runtime_error)
 append an item to the end of the array

void expand (size_t amount) throw (std::runtime_error)
 Expand the number of array data slots by "amount" elements.

void remove (void)
 Remove one item from the end of the array.

void set_size (size_t new_size)
 Set the number of data elements in the array to a new value (note that this will usually be smaller than the array size, unless a power of two is chosen for "new_size").


Private Types

enum  bogus { StartArraySize = 64 }

Private Member Functions

bool twice ()
 Double the amount of memory allocated for the array.

void init (size_t initialSize)

Private Attributes

size_t num_elem
size_t array_size
T * pArray

Detailed Description

template<class T>
class GrowableArray< T >

GrowableArray template is used to create array objects that will grow as elements are added to the end of the array.

This is similar to the STL <vector> class.

This array class is designed for dense arrays where the all elements of the array are used.

Usage:

A doubling algorithm is used when the data size is expanded because it minimizes the amount of copying that must be done. The array will quickly grow to a the size needed to accomodate the data set and no more copying will be necessary. For large arrays there is the drawback that more memory may be allocated than is needed, since the amount of memory used grows exponentially.

Definition at line 76 of file GrowableArray.h.

Member Enumeration Documentation

template<class T>
enum GrowableArray::bogus [private]
 

Enumeration values:
StartArraySize 

Definition at line 78 of file GrowableArray.h. 

00078 { StartArraySize = 64 } bogus;

Constructor & Destructor Documentation

template<class T>
GrowableArray< T >::GrowableArray (   )  [inline]
 

Definition at line 126 of file GrowableArray.h.

References GrowableArray< T >::init(). 

00127   {
00128     init( 0 );
00129   } // GrowableArray constructor

template<class T>
GrowableArray< T >::GrowableArray (  size_t  initialSize  )  [inline]
 

Definition at line 132 of file GrowableArray.h.

References GrowableArray< T >::init(). 

00133   {
00134     init( initialSize );
00135   }

template<class T>
GrowableArray< T >::~GrowableArray (   )  [inline]
 

Definition at line 137 of file GrowableArray.h.

References GrowableArray< T >::pArray. 

00138   {
00139     if (pArray != 0) {
00140       delete [] pArray;
00141     }
00142   } // GrowableArray destructor

Member Function Documentation

template<class T>
void GrowableArray< T >::append (  T  item  )  throw (std::runtime_error) [inline]
 

append an item to the end of the array

Definition at line 169 of file GrowableArray.h.

References GrowableArray< T >::array_size, GrowableArray< T >::num_elem, GrowableArray< T >::pArray, and GrowableArray< T >::twice(). 

00171   {
00172 
00173     if (num_elem == array_size) {
00174       bool allocOK = twice();
00175       if (!allocOK) {
00176         const char *errMsg = "GrowableArray::append - memory allocation error";
00177         throw std::runtime_error( errMsg );
00178       }
00179     }
00180 
00181     pArray[ num_elem ] = item;
00182     num_elem++;
00183   } // append

template<class T>
void GrowableArray< T >::expand (  size_t  amount  )  throw (std::runtime_error) [inline]
 

Expand the number of array data slots by "amount" elements.

Note that "array_size" is the total amount of storage available for data slots. "num_elem" is the number of data slots. The bounds over which the array can be indexed is governed by num_elem. Note that after expand() is called the new data elements can be read, but their value is undefined until they are initialized.

This function calls twice(), which copies the old elements into the new array. This function is not called by the constructor which takes a size argument, because there is not existing array at construction time.

Definition at line 200 of file GrowableArray.h.

References GrowableArray< T >::array_size, GrowableArray< T >::num_elem, and GrowableArray< T >::twice().

Referenced by GrowableArray< T >::set_size(). 

00202   {
00203     bool allocOK = true;
00204 
00205     while (allocOK && num_elem + amount >= array_size) {
00206       allocOK = twice();
00207       if (!allocOK) {
00208         const char *errMsg = "GrowableArray::expand - memory allocation error";
00209         throw std::runtime_error( errMsg );
00210       }
00211     }
00212     num_elem += amount;
00213   } // expand

template<class T>
const T* GrowableArray< T >::getData (   )  const [inline]
 

Definition at line 166 of file GrowableArray.h.

References GrowableArray< T >::pArray. 

00166 { return pArray; }

template<class T>
void GrowableArray< T >::init (  size_t  initialSize  )  [inline, private]
 

Definition at line 115 of file GrowableArray.h.

References GrowableArray< T >::array_size, GrowableArray< T >::num_elem, GrowableArray< T >::pArray, and GrowableArray< T >::StartArraySize.

Referenced by GrowableArray< T >::GrowableArray(). 

00116   {
00117     array_size = StartArraySize;
00118     while (initialSize > array_size) {
00119       array_size = array_size * 2;
00120     }
00121     pArray = new T[ array_size ];
00122     num_elem = initialSize;
00123   } // init

template<class T>
const size_t GrowableArray< T >::length (  void   )  const [inline]
 

Definition at line 144 of file GrowableArray.h.

References GrowableArray< T >::num_elem.

Referenced by RCArray< T >::SharedData::copy(). 

00144 { return num_elem; }

template<class T>
T GrowableArray< T >::operator[] (  const size_t  i  )  const throw (std::out_of_range) [inline]
 

Definition at line 156 of file GrowableArray.h.

References GrowableArray< T >::num_elem, and GrowableArray< T >::pArray. 

00158   {
00159     if (i >= num_elem) {
00160       const char *errMsg = "2. GrowableArray::[] - index out of bounds";
00161       throw std::out_of_range(errMsg);
00162     }
00163     return pArray[ i ];
00164   }

template<class T>
T& GrowableArray< T >::operator[] (  const size_t  i  )  throw (std::out_of_range) [inline]
 

Definition at line 146 of file GrowableArray.h.

References GrowableArray< T >::num_elem, and GrowableArray< T >::pArray. 

00148   {
00149     if (i >= num_elem) {
00150       const char *errMsg = "1. GrowableArray::[] - index out of bounds";
00151       throw std::out_of_range(errMsg);
00152     }
00153     return pArray[ i ];
00154   }

template<class T>
void GrowableArray< T >::remove (  void   )  [inline]
 

Remove one item from the end of the array.

Definition at line 217 of file GrowableArray.h.

References GrowableArray< T >::num_elem. 

00218   {
00219     if (num_elem > 0)
00220       num_elem--;
00221   } // remove

template<class T>
void GrowableArray< T >::set_size (  size_t  new_size  )  [inline]
 

Set the number of data elements in the array to a new value (note that this will usually be smaller than the array size, unless a power of two is chosen for "new_size").

Definition at line 229 of file GrowableArray.h.

References GrowableArray< T >::array_size, GrowableArray< T >::expand(), and GrowableArray< T >::num_elem. 

00230   {
00231     if (new_size <= array_size) {
00232       num_elem = new_size;
00233     }
00234     else { // new_size > array_size
00235       size_t num_new_elem = new_size - num_elem;
00236       expand( num_new_elem );
00237     }
00238   } // set_size

template<class T>
bool GrowableArray< T >::twice (   )  [inline, private]
 

Double the amount of memory allocated for the array.

Return true if memory allocation succeeded, false otherwise.

Definition at line 89 of file GrowableArray.h.

References GrowableArray< T >::array_size, and GrowableArray< T >::pArray.

Referenced by GrowableArray< T >::append(), and GrowableArray< T >::expand(). 

00090   {
00091     bool rslt;
00092 
00093     T *old_array = pArray;
00094     size_t new_size = array_size * 2;
00095     
00096     pArray = new T [ new_size ];
00097     if (pArray != 0) {
00098       rslt = true;
00099       for (int i = 0; i < array_size; i++) {
00100         pArray[i] = old_array[i];
00101       }
00102     
00103       delete [] old_array;
00104     
00105       array_size = new_size;
00106     }
00107     else {
00108       rslt = false;
00109     }
00110 
00111     return rslt;
00112   } // twice

Member Data Documentation

template<class T>
size_t GrowableArray< T >::array_size [private]
 

Definition at line 80 of file GrowableArray.h.

Referenced by GrowableArray< T >::append(), GrowableArray< T >::expand(), GrowableArray< T >::init(), GrowableArray< T >::set_size(), and GrowableArray< T >::twice().

template<class T>
size_t GrowableArray< T >::num_elem [private]
 

Definition at line 79 of file GrowableArray.h.

Referenced by GrowableArray< T >::append(), GrowableArray< T >::expand(), GrowableArray< T >::init(), GrowableArray< T >::length(), GrowableArray< T >::operator[](), GrowableArray< T >::remove(), and GrowableArray< T >::set_size().

template<class T>
T* GrowableArray< T >::pArray [private]
 

Definition at line 81 of file GrowableArray.h.

Referenced by GrowableArray< T >::append(), GrowableArray< T >::getData(), GrowableArray< T >::init(), GrowableArray< T >::operator[](), GrowableArray< T >::twice(), and GrowableArray< T >::~GrowableArray().

The documentation for this class was generated from the following file:
Generated on Mon Sep 22 20:23:01 2003 by doxygen 1.3.3