vector.h

#ifndef __SEAL_VECTOR_H__
#define __SEAL_VECTOR_H__

#include "list.h"
#include "randaccess.h"
#include "dataptr.h"
#include "exception.h"

#define DEFAULT_VECTOR_CAPACITY 11

namespace seal
{

template <typename T>
class Vector : public List<T>, public RandomAccess<T>
{
public:

class Iterator : public AbstractIterator<T>
{

friend class Vector<T>;

public:

    Iterator(void) : AbstractIterator<T>(), _firstIndex(0), _lastIndex(0), _iterIndex(-1), _size(0) {}

    virtual T next(void) throw (OutOfBoundsException);

    virtual bool hasNext(void);

    virtual void reset(void);

private:

    Iterator(int firstIndex, int lastIndex, unsigned int size, T *dataPtr)
          : AbstractIterator<T>(), _firstIndex(firstIndex), _lastIndex(lastIndex), _size(size), _dataPtr(dataPtr)
    { _iterIndex = _firstIndex-1; }
    
    int _firstIndex, _lastIndex, _iterIndex;
    unsigned int _size;
    
    T *_dataPtr;
}; // class Iterator

    Vector(void);

    Vector(unsigned int length);

    Vector(const Vector<T> &v);

    virtual ~Vector();

    virtual unsigned int size(void) const { return *_sizePtr; }

    virtual bool isEmpty(void) const { return (*_sizePtr == 0); }

    virtual AbstractIterator<T>* iteratorPtr(void) const 
    { 
        typename Vector<T>::Iterator *iterPtr = new typename Vector<T>::Iterator(*_firstPtr, *_lastPtr, *_sizePtr, _dataPtr->data);
        return iterPtr;
    }

    typename Vector<T>::Iterator iterator(void) const 
    { 
        return typename Vector<T>::Iterator(*_firstPtr, *_lastPtr, *_sizePtr, _dataPtr->data); 
    }

    virtual void purge(void);

    inline virtual const T& operator[](int index) const throw (OutOfRangeException<int>);

    inline virtual T& operator[](int index) throw (OutOfRangeException<int>);

    void operator=(const Vector<T> &v);

    virtual void pushBack(const T element);

    virtual void popBack(void);
    
    virtual void pushFront(const T element);

    virtual void popFront(void);
    
    virtual void insert(const T element, unsigned int index);

    virtual void remove(unsigned int index);

    virtual const T& first(void) const throw (EmptyCollectionException);

    virtual const T& last(void) const throw (EmptyCollectionException);

    virtual T& first(void) throw (EmptyCollectionException);

    virtual T& last(void) throw(EmptyCollectionException);

private:

    unsigned int *_firstPtr, *_lastPtr, *_capacityPtr;
    unsigned int *_refCountPtr;
    unsigned int *_sizePtr;
    DataPtr<T> *_dataPtr;
}; // class Vector



template <typename T>
Vector<T>::Vector(void)
          : List<T>(), RandomAccess<T>()
{
    _capacityPtr = new unsigned int; *_capacityPtr = DEFAULT_VECTOR_CAPACITY;
    _sizePtr = new unsigned int; *_sizePtr = 0;
    _refCountPtr = new unsigned int; *_refCountPtr = 1;

    _firstPtr = new unsigned int; *_firstPtr = DEFAULT_VECTOR_CAPACITY/2;    
    _lastPtr = new unsigned int; *_lastPtr = DEFAULT_VECTOR_CAPACITY/2;    

    _dataPtr = new DataPtr<T>();
    _dataPtr->data = new T [DEFAULT_VECTOR_CAPACITY];
} // Vector default constructor.

template <typename T>
Vector<T>::Vector(unsigned int length)
          : List<T>(), RandomAccess<T>()
{
    _capacityPtr = new unsigned int; *_capacityPtr = 2*length;
    _sizePtr = new unsigned int; *_sizePtr = length;
    _refCountPtr = new unsigned int; *_refCountPtr = 1;
    
    _firstPtr = new unsigned int; *_firstPtr = length/2;
    _lastPtr = new unsigned int; *_lastPtr = *_firstPtr + length - 1;

    _dataPtr = new DataPtr<T>();
    _dataPtr->data = new T [*_capacityPtr];
} // Vector constructor.

template <typename T>
Vector<T>::Vector(const Vector<T> &v)
          : List<T>(), RandomAccess<T>(),
            _firstPtr(v._firstPtr),
            _lastPtr(v._lastPtr),
            _capacityPtr(v._capacityPtr),
            _refCountPtr(v._refCountPtr),
            _sizePtr(v._sizePtr),
            _dataPtr(v._dataPtr)
{
    (*_refCountPtr)++;
} // Vector copy constructor.

template <typename T>
Vector<T>::~Vector()
{
    if (*_refCountPtr <= 1)
    {
        delete _firstPtr; 
        delete _lastPtr;
        delete _capacityPtr; 
        delete _sizePtr;
        delete _refCountPtr;

        delete [] _dataPtr->data;
        delete _dataPtr;
    }
    else
        (*_refCountPtr)--;
} // Vector destructor.

template <typename T>
void Vector<T>::purge(void)
{
    *_sizePtr = 0;
    *_firstPtr = *_capacityPtr / 2;
    *_lastPtr = *_firstPtr;
} // Vector::purge

template <typename T>
const T& Vector<T>::operator[](int index) const throw (OutOfRangeException<int>)
{
    if (*_sizePtr == 0)
        throw OutOfRangeException<int>(-1, -1, 0);
    else if (index < 0 || index >= *_sizePtr)
        throw OutOfRangeException<int>(0, *_sizePtr-1, index);
    else
        return _dataPtr->data[*_firstPtr + index];
} // Vector::operator[] const

template <typename T>
T& Vector<T>::operator[](int index) throw (OutOfRangeException<int>)
{
    if (*_sizePtr == 0)
        throw OutOfRangeException<int>(-1, -1, 0);
    else if (index < 0 || index >= *_sizePtr)
        throw OutOfRangeException<int>(0, *_sizePtr-1, index);
    else
        return _dataPtr->data[*_firstPtr + index];
} // Vector::operator[] 

template <typename T>
void Vector<T>::pushBack(const T element)
{
    // Update the lastPtr value. The firstPtr value 
    // should not be changed.
    if (*_sizePtr > 0)
        (*_lastPtr)++;

    // Update size. The size HAS to increase with a pushBack 
    // operation.
    (*_sizePtr)++;

    // If there is enough capacity, then just add the new
    // element.
    if (*_lastPtr < *_capacityPtr)
    {
        _dataPtr->data[*_lastPtr] = element;
    }
    else
    {
        // If the capacity is not sufficient, then double 
        // the capacity and add the new element. The steps 
        // are as follows:

        // 1) Double the capacity
        (*_capacityPtr) *= 2;

        // 2) Create new data area with the new capacity.
        T *newData = new T [*_capacityPtr]; 
       
        // 3) Copy the data from the old area into the new 
        //    area.
        for (int i = *_firstPtr; i < *_lastPtr; i++)
        {
            newData[i] = _dataPtr->data[i];
        }
        
        // 4) Add the new element into the last location.
        newData[*_lastPtr] = element;

        // 5) Delete the old data area and make the 
        //    dataPtr point to the new data area.
        delete [] _dataPtr->data;
        _dataPtr->data = newData;
    }

} // Vector::pushBack

template <typename T>
void Vector<T>::popBack(void)
{
    // There is nothing to pop if the size is 0!
    if (*_sizePtr == 0)
        return;

    // A pop operation HAS to reduce the size if 
    // the size is non-zero!
    (*_sizePtr)--;

    // Last pointer should be decremented if the 
    // new size is greater than 0.
    if (*_sizePtr > 0)
        (*_lastPtr)--;

    // Reduce the capacity if the size is too small!
    if (*_sizePtr < (*_capacityPtr)/4 && *_capacityPtr >= 3*DEFAULT_VECTOR_CAPACITY/2)
    {
        (*_capacityPtr) /= 2;
        T *newData = new T [*_capacityPtr];
        
        int newFirst = (*_capacityPtr)/2 - (*_sizePtr)/2;
        for (int i = *_firstPtr, j = newFirst; i <= *_lastPtr; i++, j++)
            newData[j] = _dataPtr->data[i];

        *_firstPtr = newFirst;
        *_lastPtr = newFirst + *_sizePtr - 1;

        delete [] _dataPtr->data;
        _dataPtr->data = newData;
    }
}

template <typename T>
void Vector<T>::pushFront(const T element)
{
    // The size HAS to be incremented anyway!
    (*_sizePtr)++; 

    if (*_firstPtr > 0)
    {
        if (*_sizePtr > 1)
            (*_firstPtr)--;

        _dataPtr->data[*_firstPtr] = element;
    }
    else
    {
        if (*_sizePtr == 1) // Note that it is the updated size here!
        {
            _dataPtr->data[*_firstPtr] = element;
        }
        else
        {
            
            // In this case, the capacity of the vector 
            // should be doubled.
            (*_capacityPtr) *= 2;
            T *newData = new T [*_capacityPtr];

            // Copy the old data into the new data area.
            int newFirst = (*_capacityPtr)/2 - (*_sizePtr)/2;
            for (int i = *_firstPtr, j = newFirst+1; i <= *_lastPtr; i++, j++)
            {
                newData[j] = _dataPtr->data[i];
            }

            newData[newFirst] = element;
            *_firstPtr = newFirst;
            *_lastPtr = newFirst + *_sizePtr - 1;
            
            // Delete the old data area
            delete [] _dataPtr->data;

            // Use the new data area
            _dataPtr->data = newData;            
        }
    }

} // Vector::pushBack

template <typename T>
void Vector<T>::popFront(void)
{
    // Nothing to pop if size is 0.
    if (*_sizePtr == 0)
        return;

    // A pop HAS to reduce the size if the size 
    // is non-zero.
    (*_sizePtr)--;

    // The first pointer has to be incremented if
    // the new size is greater than 0!
    if (*_sizePtr > 0)
        (*_firstPtr)++;

    // Reduce the capacity is the size is too small.
    if (*_sizePtr < (*_capacityPtr)/4 && *_capacityPtr > 3*DEFAULT_VECTOR_CAPACITY/2)
    {
        // Reduce the capacity to half.
        (*_capacityPtr) /= 2;
        T *newData = new T [*_capacityPtr];

        // Copy the data from the old data area 
        // into the new data area.
        int newFirst = (*_capacityPtr)/2 - (*_sizePtr)/2;
        for (int i = *_firstPtr, j= newFirst; i <= *_lastPtr; i++, j++)
        {
            newData[j] = _dataPtr->data[i];
        }

        // Update the boundary value pointers.
        *_firstPtr = newFirst;
        *_lastPtr = newFirst + *_sizePtr - 1;

        // Use the new data area.
        delete [] _dataPtr->data;
        _dataPtr->data = newData;
    }

}

template <typename T>
void Vector<T>::insert(const T element, unsigned int index)
{
    if (index == 0)
        pushFront(element);
    else if (index >= *_sizePtr)
        pushBack(element);
    else
    {
        unsigned int size = *_sizePtr;
        pushBack(this->operator[](size - 1));
        for (int i = size-1; i > index; i--)
        {
            this->operator[](i) = this->operator[](i-1);
        }

        this->operator[](index) = element;
    }
} // Vector::insert

template <typename T>
void Vector<T>::remove(unsigned int index)
{
    if (index == 0)
        popFront();
    else if (index == (*_sizePtr - 1))
        popBack();
    else if (index >= *_sizePtr)
        return;
    else
    {
        for (int i = index; i < *_sizePtr-1; i++)
        {
            this->operator[](i) = this->operator[](i+1);
        }

        popBack();
    }
} // Vector::remove

template <typename T>
void Vector<T>::operator=(const Vector<T> &v)
{
    if (_refCountPtr == v._refCountPtr)
        return;

    if (*_refCountPtr > 1)
    {
        (*_refCountPtr)--;

        _firstPtr = v._firstPtr;
        _lastPtr = v._lastPtr;
        _capacityPtr = v._capacityPtr;
        _sizePtr = v._sizePtr;
        _refCountPtr = v._refCountPtr;
        _dataPtr = v._dataPtr;

        (*_refCountPtr)++;
    }
    else
    {
        delete _firstPtr; 
        delete _lastPtr;
        delete _capacityPtr; 
        delete _sizePtr;
        delete _refCountPtr;

        delete [] _dataPtr->data;
        delete _dataPtr;

        _firstPtr = v._firstPtr;
        _lastPtr = v._lastPtr;
        _capacityPtr = v._capacityPtr;
        _sizePtr = v._sizePtr;
        _refCountPtr = v._refCountPtr;
        _dataPtr = v._dataPtr;

        (*_refCountPtr)++;
    }
} // Vector::operator=

template <typename T>
const T& Vector<T>::first(void) const throw (EmptyCollectionException)
{
    if (*_sizePtr == 0)
        throw EmptyCollectionException();

    return _dataPtr->data[*_firstPtr];
}

template <typename T>
T& Vector<T>::first(void) throw (EmptyCollectionException)
{
    if (*_sizePtr == 0)
        throw EmptyCollectionException();

    return _dataPtr->data[*_firstPtr];
}

template <typename T>
const T& Vector<T>::last(void) const throw (EmptyCollectionException)
{
    if (*_sizePtr == 0)
        throw EmptyCollectionException();

    return _dataPtr->data[*_lastPtr];
}

template <typename T>
T& Vector<T>::last(void) throw (EmptyCollectionException)
{
    if (*_sizePtr == 0)
        throw EmptyCollectionException();

    return _dataPtr->data[*_lastPtr];
}


template <typename T>
bool Vector<T>::Iterator::hasNext()
{
    if (_size > 0 && _iterIndex < _lastIndex && _iterIndex >= _firstIndex - 1)
        return true;
    else
        return false;
} // VectorIterator::hasNext()

template <typename T>
T Vector<T>::Iterator::next() throw (OutOfBoundsException)
{
    if (_size > 0 && _iterIndex < _lastIndex && _iterIndex >= _firstIndex - 1)
    {
        _iterIndex++;
        return _dataPtr[_iterIndex];
    }
    else
        throw OutOfBoundsException();
} // VectorIterator::next()

template <typename T>
void Vector<T>::Iterator::reset()
{
    _iterIndex = _firstIndex - 1;
} 

} // End of namespace seal.

#endif // __SEAL_VECTOR_H__

---