//----------------------------------------------------------------------------
// William Baxter III's Ray Tracer
//
//     Project for Comp 238, Raster Graphics
//     University of North Carolina at Chapel Hill
//     
// $Id:$
// Code in this file copyright Numerical Design Ltd.
//----------------------------------------------------------------------------

#ifndef WB3TARRAY_H
#define WB3TARRAY_H

// While the template arrays work best for pointer types T, other types
// certainly will work when they satisfy the conditions below.  The template
// class assumes that type T has the following:
//   1.  A "zero" element (i.e., T var; var = 0; is supported)
//       which is considered to be a null array element.
//   2.  The default constructor for T must exist and create the
//       "zero" element.  The constructor must also handle all necessary
//       actions for constructing elements.  That is, the template array
//       class cannot make any post-construction member calls that are
//       specific to class T.
//   3.  Copy constructor T::T (const T&) must work properly.  The class T is
//       responsible for implementing this if need be.
//   4.  The destructor must handle all necessary actions for destroying
//       elements.  That is, the template array class cannot make any
//       pre-destruction member calls that are specific to class T.
//   5.  bool operator== (const T&);
//   6.  bool operator!= (const T&);
//   7.  T& operator= (const T&);
//
// An example to illustrate what the members of wb3TArray mean.  Shown is
// an array of elements (0 = null element, x = an element)
//     index:    0 1 2 3 4 5 6 7 8 9
//     element:  x 0 x x 0 0 x 0 0 0
//
//     m_uiMaxSize = 10 (number of slots in array)
//     m_uiSize    =  7 (next available slot, useful for traversing minimum
//                       block of elements while searching for non-null items)
//     m_uiESize   =  4 (number of used slots)
//
// Note that when m_uiSize = m_uiMaxSize, an attempt to add a new element
// requires growing the array.  SetAtGrow does this.  SetAt does not.

#include <assert.h>

template <class T> class wb3TArray 
{
public:
    // construction and destruction
    wb3TArray (unsigned int uiMaxSize = 1, unsigned int uiGrowBy = 1);
    virtual ~wb3TArray ();

    // slots available and used
    unsigned int GetSize () const;
    unsigned int GetEffectiveSize () const;
    unsigned int GetGrowBy () const;
    void SetSize (unsigned int uiSize);
    void SetGrowBy (unsigned int uiGrowBy);

    // set and get elements
    T* GetBase () { return m_pBase; }
    T GetAt (unsigned int uiIndex) const;
    void SetAt (unsigned int uiIndex, T element);
    int SetAtGrow (unsigned int uiIndex, T element);

    // add and remove elements
    void Add (T element);
    void AddFirstEmpty (T element);
    T RemoveAt (unsigned int uiIndex);
    T RemoveEnd ();
    void RemoveAll ();

    // Compact all elements to contiguous space starting at the beginning of
    // the array.  Reallocation is performed to eliminate unused slots.
    void Compact ();

    // After deletions before m_uiSize slot, m_uiSize no longer points to
    // the first available slot.  This routine resets it to the first
    // available slot.
    void UpdateSize ();

protected:
    T* m_pBase;                // pointer to the array storage
    unsigned int m_uiMaxSize;  // number of slots in array
    unsigned int m_uiSize;     // first available empty slot in array
    unsigned int m_uiESize;    // number of filled slots
    unsigned int m_uiGrowBy;   // number of slots to grow array when full
};

//---------------------------------------------------------------------------
template <class T> inline
wb3TArray<T>::wb3TArray (unsigned int uiMaxSize, unsigned int uiGrowBy)
{
    assert( uiMaxSize > 0 );

    m_uiMaxSize = uiMaxSize;
    m_uiGrowBy = uiGrowBy;
    m_uiSize = 0;
    m_uiESize = 0;

    m_pBase = new T[m_uiMaxSize];
    assert( m_pBase );
}
//---------------------------------------------------------------------------
template <class T> inline
wb3TArray<T>::~wb3TArray ()
{
    delete[] m_pBase;
}
//---------------------------------------------------------------------------
template <class T> inline
unsigned int wb3TArray<T>::GetSize () const
{
    return m_uiSize;
}
//---------------------------------------------------------------------------
template <class T> inline
unsigned int wb3TArray<T>::GetEffectiveSize () const
{
    return m_uiESize;
}
//---------------------------------------------------------------------------
template <class T> inline
unsigned int wb3TArray<T>::GetGrowBy () const
{
    return m_uiGrowBy;
}
//---------------------------------------------------------------------------
template <class T> inline
void wb3TArray<T>::SetSize (unsigned int uiMaxSize)
{
    assert( uiMaxSize > 0 );

    if ( uiMaxSize == m_uiMaxSize )
        return;

    // If the number of slots gets smaller, the elements in the unwanted
    // slots must be zeroed in case class T has side effects that must occur.
    // For example, if T is a smart pointer class, then decrementing the ref
    // count must occur.
    unsigned int i;
    if ( uiMaxSize < m_uiSize )
    {
        for (i = uiMaxSize; i < m_uiSize; i++)
        {
            if ( m_pBase[i] != 0 )
            {
                m_pBase[i] = T(0);
                m_uiESize--;
            }
        }

        m_uiSize = uiMaxSize;
    }

    // allocate a new array
    m_uiMaxSize = uiMaxSize;
    T* pSaveBase = m_pBase;
    m_pBase = new T[m_uiMaxSize];
    assert( m_pBase );

    // copy old array to new array
    for (i = 0; i < m_uiSize; i++)
        m_pBase[i] = pSaveBase[i];

    // delete old array
    delete[] pSaveBase;
}
//---------------------------------------------------------------------------
template <class T> inline
void wb3TArray<T>::SetGrowBy (unsigned int uiGrowBy)
{
    m_uiGrowBy = uiGrowBy;
}
//---------------------------------------------------------------------------
template <class T> inline
T wb3TArray<T>::GetAt (unsigned int uiIndex) const
{
    return m_pBase[uiIndex];
}
//---------------------------------------------------------------------------
template <class T> inline
void wb3TArray<T>::SetAt (unsigned int uiIndex, T element)
{
    assert ( uiIndex < m_uiMaxSize );
    if ( uiIndex >= m_uiMaxSize )
        return;

    if ( uiIndex >= m_uiSize )
    {
        m_uiSize = uiIndex+1;
        if ( element != 0 )
            m_uiESize++;
    }
    else 
    {
        if ( element != 0 )
        {
            if ( m_pBase[uiIndex] == 0 )
                m_uiESize++;
        }
        else
        {
            if ( m_pBase[uiIndex] != 0 )
                m_uiESize--;
        }
    }

    m_pBase[uiIndex] = element;
}
//---------------------------------------------------------------------------
template <class T> inline
int wb3TArray<T>::SetAtGrow (unsigned int uiIndex, T element)
{
    if ( uiIndex >= m_uiMaxSize )
        SetSize(uiIndex+m_uiGrowBy);

    SetAt(uiIndex,element);
    return uiIndex;
}
//---------------------------------------------------------------------------
template <class T> inline
void wb3TArray<T>::Add (T element)
{
    SetAtGrow(m_uiSize,element);
}
//---------------------------------------------------------------------------
template <class T> inline
void wb3TArray<T>::AddFirstEmpty (T element)
{
    if ( element == 0 )
        return;

    for (unsigned int i = 0; i < m_uiSize; i++)
    {
        if ( m_pBase[i] == 0 )
        {
            // empty slot - add here
            m_pBase[i] = element;
            m_uiESize++;
            return;
        }
    }

    // no empty slots - add at end
    SetAtGrow(m_uiSize,element);
}
//---------------------------------------------------------------------------
template <class T> inline
T wb3TArray<T>::RemoveAt (unsigned int uiIndex)
{
    if ( uiIndex >= m_uiSize )
        return T(0);
    
    T element = m_pBase[uiIndex];
    m_pBase[uiIndex] = 0;

    if ( element != 0 )
        m_uiESize--;

    if ( uiIndex == m_uiSize-1 )
        m_uiSize--;

    return element;
}
//---------------------------------------------------------------------------
template <class T> inline
T wb3TArray<T>::RemoveEnd ()
{
    if ( m_uiSize == 0 )
        return T(0);

    m_uiSize--;
    T element = m_pBase[m_uiSize];
    m_pBase[m_uiSize] = 0;

    if ( element != 0 )
        m_uiESize--;

    return element;
}
//---------------------------------------------------------------------------
template <class T> inline
void wb3TArray<T>::RemoveAll ()
{
    // The elements in the to-be-removed slots must be zeroed in case class
    // T has side effects that must occur.  For example, if T is a smart
    // pointer class, then decrementing the ref count must occur.
    for (unsigned int i = 0; i < m_uiSize; i++)
        m_pBase[i] = 0;

    m_uiSize = 0;
    m_uiESize = 0;
}
//---------------------------------------------------------------------------
template <class T> inline
void wb3TArray<T>::Compact ()
{
    if ( m_uiESize == m_uiSize )
        return;

    // move elements to contiguous memory at beginning of array
    if ( m_uiESize )
    {
        for (unsigned int i = 0, j = 0; i < m_uiSize; i++)
        {
            if (m_pBase[i]) 
            {
                if (m_pBase[j] != m_pBase[i])
                    m_pBase[j] = m_pBase[i];
                j++;
            }
        }
    }

    // downsize storage
    T* pSaveBase = m_pBase;
    m_uiSize = m_uiESize;
    m_uiMaxSize = m_uiSize;
    m_pBase = new T[m_uiMaxSize];
    assert( m_pBase );

    // copy old array to new array
    for (unsigned int i = 0; i < m_uiSize; i++)
        m_pBase[i] = pSaveBase[i];

    // delete old array
    delete[] pSaveBase;
}
//---------------------------------------------------------------------------
template <class T> inline
void wb3TArray<T>::UpdateSize ()
{
    while ( m_uiSize > 0 )
    {
        if ( m_pBase[m_uiSize-1] != 0 )
            break;

        m_uiSize--;
    }
}
//---------------------------------------------------------------------------

#endif