dynamic_array.h

Go to the documentation of this file.

#ifndef _DYNAMIC_ARRAY_H
#define _DYNAMIC_ARRAY_H

/*! \file dynamic_array.h
  \brief  The disti::DynamicArray class. A templated array of objects capable of dynamically growing.

  \par Copyright Information

  Copyright (c) 2012 The DiSTI Corporation.<br>
  11301 Corporate Blvd; Suite 100<br>
  Orlando, Florida 32817<br>
  USA<br>
  <br>
  All rights reserved.<br>

  This Software contains proprietary trade secrets of DiSTI and may not be
reproduced, in whole or part, in any form, or by any means of electronic,
mechanical, or otherwise, without the written permission of DiSTI.  Said
permission may be derived through the purchase of applicable DiSTI product
licenses which detail the distribution rights of this content and any
Derivative Works based on this or other copyrighted DiSTI Software.

  NO WARRANTY. THE SOFTWARE IS PROVIDED "AS-IS," WITHOUT WARRANTY OF ANY KIND,
AND ANY USE OF THIS SOFTWARE PRODUCT IS AT YOUR OWN RISK. TO THE MAXIMUM EXTENT
PERMITTED BY APPLICABLE LAW, DISTI AND ITS SUPPLIERS DISCLAIM ALL WARRANTIES
AND CONDITIONS, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
IMPLIED WARRANTIES AND CONDITIONS OF MERCHANTABILITY AND/OR FITNESS FOR A
PARTICULAR PURPOSE, TITLE, AND NON-INFRINGEMENT, WITH REGARD TO THE SOFTWARE.

  LIMITATION OF LIABILITY. TO THE MAXIMUM EXTENT PERMITTED BY APPLICABLE LAW,
IN NO EVENT SHALL DISTI OR ITS SUPPLIERS BE LIABLE FOR ANY SPECIAL, INCIDENTAL,
INDIRECT, OR CONSEQUENTIAL DAMAGES WHATSOEVER (INCLUDING, WITHOUT LIMITATION,
DAMAGES FOR LOSS OF BUSINESS PROFITS, BUSINESS INTERRUPTION, LOSS OF BUSINESS
INFORMATION, OR ANY OTHER PECUNIARY LOSS) ARISING OUT OF THE USE OF OR
INABILITY TO USE THE SOFTWARE, EVEN IF DISTI HAS BEEN ADVISED OF THE POSSIBLITY
OF SUCH DAMAGES.  DISTI'S ENTIRE LIABILITY AND YOUR EXCLUSIVE REMEDY SHALL NOT
EXCEED FIVE DOLLARS (US$5.00).

  The aforementioned terms and restrictions are governed by the laws of the
State of Florida and the United States of America.

*/

#include "string.h"
#include "assert.h"

namespace disti
{

#if defined (_MSC_VER)
#pragma warning( push, 3 )
#endif

/** \brief A templated array of objects. The array dynamically resizes as needed.
  \param TypeIsSimple set to true for types which can be initialized to
         all zero using memset.  
         If T is a class with a default constructor, a working '=' operator, 
         set TypeIsSimple to false.
*/
template <class T,bool TypeIsSimple = true>
class DynamicArray
{
    protected:

    unsigned int _size;        /** Number of elements in the array */
    unsigned int _count;       /** Number of elements used */
    T  *_objects;              /** Dynamic array is an array of objects */


    /** Grow the array.  If nothing has been allocated yet, set the size to 2 elements.  Otherwise double the array size. */
    void GrowArray(void)
    {
        if (!_objects || _size == 0)
            Size(2);
        else
            Size(_size * 2);
    }
    
    public:

    typedef T ElementType;

    /** DynamicArray constructor
      * \param  The initial number of elements to be allocated for the array
      */
    DynamicArray(int initialSize=0)
    {
        _size = initialSize;
        _count = 0;
        _objects = NULL;

        if (initialSize)
            Size(initialSize);          
    }

    DynamicArray(const DynamicArray& other)
    {
        _size = 0;
        _count = 0;
        _objects = NULL;

        *this = other;
    }

    /** DynamicArray destructor.  Clears the array but does not delete the objects being pointed to by the array
      */
    ~DynamicArray(void) 
    { 
        if (_objects)
        {
            delete []_objects; 
        }
    };


    /** Set the "Count" value for this array
      */
    void Count(const unsigned int count) 
    {
        _count = count;

        if(_count > _size)
        {
            Size(_count);
        }
    }

    /** Returns the number of elements used of this dynamic array
      * \return The number of elements used of the array (number of elements)
      */
    inline unsigned int Count() const { return _count; }

    /** Returns the current size of this dynamic array
      * \return The current size of the array (number of elements)
      */
    inline unsigned int Size() const { return _size; }

    /** Sets the array size to the new size given.  Reallocates the array as needed
      * \param newSize  The new number of elements in the array
      */
    void Size(unsigned int newSize)
    {
        T *newobjs;

        if (newSize > 0)
        {
            // Test for case when array has not yet been allocated
            if (!_objects)
            {
                _objects = new T[newSize];
                assert(_objects);

                if (TypeIsSimple)
                    memset(_objects,0,newSize*sizeof(T));

                _size = newSize;
            }

            // Don't reallocate if the size doesn't change
            if (newSize == _size)
                return;

            newobjs = new T[newSize];
            assert(newobjs);

            if (newSize > _size)
            {
                if (TypeIsSimple)
                {
                    // Because it is just a pointer or other simple type,
                    // we can just memcpy the data
                    memcpy(newobjs,_objects,_size*sizeof(T));
                }
                else
                {
                    for(unsigned int i=0; i < _size; i++)
                    {
                        newobjs[i] = _objects[i];
                    }
                }

                if (TypeIsSimple)
                    memset(newobjs+_size,0,(newSize-_size)*sizeof(T));
            }
            else
            {

                if (TypeIsSimple)
                {
                    // Because it is just a pointer or other simple type,
                    // we can just memcpy the data
                    memcpy(newobjs,_objects,newSize*sizeof(T));
                }
                else
                {
                    for(unsigned int i=0; i < newSize; i++)
                    {
                        newobjs[i] = _objects[i];
                    }
                }
            }

            if (_objects)
                delete [] _objects;

            _objects = newobjs;
        }
        else // newSize is zero
        {
            if (_objects)
                delete [] _objects;

            _objects = NULL;
        }

        _size = newSize;

        // Just in case the user shrank the array, reduce count to match size if needed
        if (_count > _size)
            _count = _size;
    }

    /** Attempts to insert the object into the list at the specified location.  If the
      * specified location is beyond the array bounds, the object is inserted at the next
      * position in the array.
      * \param obj  The object to insert
      * \param loc  The index location to insert into
      */
    void InsertObject(const T& obj,unsigned int loc)
    {
        _count++;   // we are adding an object, increase the count
        
        // Check to see if the count exceeds the size, if so Grow
        if (_count > _size)
        {
            GrowArray();
        }

        // If the Location Index exceeds the array bounds,
        // put the new object at the end of the array
        if (loc >= _count)
        {
            loc = _count-1; 
        }

        // Move the array elements up to make room to insert the new element
        for (unsigned int i=_count-1; i > loc; i--)
        {
            _objects[i] = _objects[i-1];
        }

        _objects[loc] = obj;  // Insert the new object.
    }

    /** Adds the specified object into the list, at the end of the list
      * \param  A pointer to the object to add
      * \return Where the object was inserted
      */
    unsigned int InsertObject(const T& obj)
    {
        unsigned int rval;

        rval = _count;

        InsertObject(obj,_count);

        return rval;
    }

    /** Adds the specified object into the list, at the head of the list
      * Treats the list like a stack, hence the name Push
      * \param  A pointer to the object to add
      */
    void PushObject(const T& obj)
    {
        InsertObject(obj,0);
    }

    /** Insert the object into the list at the specified location
      * \param obj  The object to insert
      * \param loc  The index location to insert into
      */
    void InsertObjectAfter(const T& obj,unsigned int loc)
    {
        InsertObject(obj,loc+1);
    }
 
    /** Deletes the specified object from the list. Does not free it
      * \param   A pointer to the object to delete
      * \return  true if object was found and deleted else false
      */
    bool DeleteObject(const T& obj)
    {
        int loc = Position(obj);

        if (loc >= 0)
            return DeleteObjectAtIndex(loc);

        return false;
    }

    /** Deletes the object at the specified index. Does not free it
      * \param   Index of the object to delete
      * \return  true if object was found and deleted else false
      */
    bool DeleteObjectAtIndex(unsigned int index)
    {
        if (index >= _count)
        {
            return false;
        }
        else
        {
            for (unsigned int j=index; j < (_count - 1u); j++)
            {
                _objects[j] = _objects[j+1u];
            }

            _count--;
        }
        return true;
    }

    /** Get the index position of the specified object in the list
      * \param obj   The object to find
      * \return The index of the object in the list, -1 if it isn't in the list
      */
    int Position(const T& obj)
    {
        for (unsigned int i=0;i < _count; i++)
            if (obj==_objects[i])
                return i;
        return -1;
    }

    /** Empties the list, calling delete on all of its elements 
      * This method is intended for pointer data types only.
      */
    void EmptyList(void)
    {
        for (unsigned int i=0; i < Count(); i++)
            delete _objects[i];

        ClearList();
    }

    /** Clears the list so Count() is zero.  Does not attempt to delete the objects data */
    void ClearList(void)
    {
        // Clear object array
        if (_objects)
        {
            if(TypeIsSimple)
            {
                memset(_objects,0,sizeof(T) * _size);
            }
            else
            {
                // For non simple objects, just delete them all, and 
                // as they are accessed, new ones will be created.
                delete [] _objects;
                _objects = NULL;
                _size = 0;
            }
        }

        _count = 0;
    }

    /** Overload of array operator to get element at desired index */
    T &operator[] (unsigned int index)
    {
        assert(int(index) >= 0); //test for passing in -1, which would resize the array to size 0
        
        // This gets an element, resizing the array if needed

        if (index >= _size)
        {
            Size(index+1);
            _count = index+1;
        } 
        else if (index >= _count)
        {
            _count = index+1;
        }

        return _objects[index];
    }

    /** Overload of array operator to get element at desired index - const safe version */
    const T &operator[] (unsigned int index) const
    {
        assert(int(index) >= 0); //test for passing in -1, which would resize the array to size 0
        
        // This gets an element, resizing the array if needed

        if (index >= _size)
        {
            Size(index+1);
            _count = index+1;
        } 
        else if (index >= _count)
        {
            _count = index+1;
        }

        return _objects[index];
    }


    /** Return the internal array pointer
      * If you call any other methods on this object it invalidates the pointer.*/
    inline T* InternalArray(void)
    {
        return _objects;
    }

    /** Overload the assignment operator to create a duplicate of the righthand operand */
    DynamicArray<T,TypeIsSimple>& operator= (const DynamicArray<T,TypeIsSimple>& right)
    {
        Size(right.Size());
        for(unsigned int i = 0; i <Size(); i++)
        {
            _objects[i] = right._objects[i];
        }
        _count = right.Count();
        return *this;
    }

    /** \return true if the list is empty */
    bool IsEmpty(void) const
    { 
        return (_count==0); 
    }
};

#if defined (_MSC_VER)
#pragma warning( pop )
#endif

} // namespace disti

#endif