dynamic_array.h

Go to the documentation of this file.

///   \file
///   \brief  The disti::DynamicArray class. A templated array of objects capable of dynamically growing.
///
///   \par Copyright Information
///
///   Copyright (c) 2020 by 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 POSSIBILITY
/// 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.
 
#ifndef INCLUDED_DISTI_DYNAMIC_ARRAY_H
#define INCLUDED_DISTI_DYNAMIC_ARRAY_H
 
#include "disti_assert.h"
#include "gls_cpp_lang_support.h"
#include "gls_include.h"
 
#include <climits>
#include <cstddef>
#include <cstdlib>
#include <new>
 
#if defined( DISTI_HAS_CPP11 )
#    include <initializer_list>
#endif
 
#if defined( DISTI_HAS_TYPE_TRAITS )
#    include <type_traits>
#endif
#if defined( DISTI_HAS_RVAL_REFS )
#    include <utility>
#endif
 
namespace disti
{
// Forward declarations
// clang-format off
template<class T, bool Obsolete>          class DynamicArray;
template<class T, bool Obsolete, class U> unsigned FindIndexOf( const DynamicArray<T, Obsolete>& array, const U& object );
template<class T, bool Obsolete>          void     DeleteEachAndClear( DynamicArray<T, Obsolete>& array );
// clang-format on
 
/// Constant returned by FindIndexOf() if the item is not found.
const unsigned g_itemNotFound = UINT_MAX;
 
/// A templated array of objects. The array dynamically resizes as needed.
/// \tparam T The type of the objects contained.
/// \tparam Obsolete Obsolete parameter retained for backwards compatibility. Please ignore.
template<class T, bool Obsolete = true>
class DynamicArray DISTI_FINAL
{
public:
    typedef T ElementType; ///< Typedef for the type of object contained in this array.
 
    /// DynamicArray constructor
    /// \param initialCapacity The initial number of elements to be allocated for the array
    explicit DynamicArray( unsigned initialCapacity = 0 )
        : _capacity( 0 )
        , _count( 0 )
        , _objects( NULL )
    {
        if( initialCapacity != 0 )
        {
            Capacity( initialCapacity );
        }
    }
 
#if defined( DISTI_HAS_CPP11 )
    /// Construct from a list of items, e.g.:
    /// \code
    ///    const auto a = DynamicArray<int>{ 1, 2, 3, 4 };
    /// \endcode
    /// \param list The list of items to construct from.
    DynamicArray( std::initializer_list<T> list )
        : _capacity( 0 )
        , _count( 0 )
        , _objects( NULL )
    {
        const auto capacity = static_cast<unsigned>( list.size() );
        if( capacity != 0 )
        {
            Capacity( capacity );
            for( auto&& item : list )
            {
                PushBack( std::move( item ) );
            }
        }
    }
#endif
 
    /// Initialize this array by deep-copying \a other
    /// \param other The array to copy from.
    DynamicArray( const DynamicArray<T, true>& other )
        : _capacity( 0 )
        , _count( 0 )
        , _objects( NULL )
    {
        DeepCopyFrom( other );
    }
 
    /// Initialize this array by deep-copying \a other
    /// \param other The array to copy from.
    DynamicArray( const DynamicArray<T, false>& other )
        : _capacity( 0 )
        , _count( 0 )
        , _objects( NULL )
    {
        DeepCopyFrom( other );
    }
 
    /// Assign this array by deep-copying \a other
    /// \param other The array to copy from.
    /// \return The resulting array (this).
    DynamicArray& operator=( const DynamicArray<T, true>& other )
    {
        if( this != &other )
        {
            DeepCopyFrom( other );
        }
        return *this;
    }
 
    /// Assign this array by deep-copying \a other
    /// \param other The array to copy from.
    /// \return The resulting array (this).
    DynamicArray& operator=( const DynamicArray<T, false>& other )
    {
        if( this != &other )
        {
            DeepCopyFrom( other );
        }
        return *this;
    }
 
#if defined( DISTI_HAS_RVAL_REFS )
    /// Construct this array by taking ownership of \a other's contents.
    /// \param other The array to move from.
    DynamicArray( DynamicArray<T, true>&& other )
        : _capacity( other._capacity )
        , _count( other._count )
        , _objects( other._objects )
    {
        // Relieve of ownership
        other._capacity = 0;
        other._count    = 0;
        other._objects  = NULL;
    }
 
    /// Construct this array by taking ownership of \a other's contents.
    /// \param other The array to move from.
    DynamicArray( DynamicArray<T, false>&& other )
        : _capacity( other._capacity )
        , _count( other._count )
        , _objects( other._objects )
    {
        // Relieve of ownership
        other._capacity = 0;
        other._count    = 0;
        other._objects  = NULL;
    }
 
    /// Assign this array by clearing any current contents and then taking ownership of \a other's contents.
    /// \param other The array to move from.
    /// \return The resulting array (this).
    DynamicArray& operator=( DynamicArray<T, true>&& other )
    {
        StealFrom( std::move( other ) );
        return *this;
    }
 
    /// Assign this array by clearing any current contents and then taking ownership of \a other's contents.
    /// \param other The array to move from.
    /// \return The resulting array (this).
    DynamicArray& operator=( DynamicArray<T, false>&& other )
    {
        StealFrom( std::move( other ) );
        return *this;
    }
#endif
 
    /// DynamicArray destructor. Clears the array but does not delete the objects being pointed to by the array.
    ~DynamicArray()
    {
        StripCapacity();
    }
 
    /// Returns the number of elements used of this dynamic array
    /// \return The number of elements used of the array (number of elements)
    /// \note Similar to std::vector::size()
    unsigned Count() const { return _count; }
 
    /// Set the "Count" value for this array, destroying items or creating default-constructed items as needed.
    /// \note Similar to std::vector::resize()
    /// \param newCount The new count to allocate.
    void Count( const unsigned newCount )
    {
        if( newCount > _capacity )
        {
            Capacity( newCount );
        }
 
        if( newCount > _count )
        {
            // If we're increasing our count, then we need to initialize the new values manually since
            // setting the capacity doesn't deal with initializing objects.
            for( unsigned i = _count; i < newCount; ++i )
            {
                new( _objects + i ) T(); // Use placement-new to construct at this memory location
            }
        }
        else
        {
            // If we're lowering our count, we need to destroy some objects because we want them to
            // clean up after themselves (e.g., if they have some resource they need to close). We
            // can't call delete because this container manually manages the memory the object sits in.
            Destroy( newCount, _count );
        }
 
        _count = newCount;
    }
 
    /// Clears the list so Count() is zero, destroying all items. Does not strip capacity. Shorthand for Count( 0 ).
    /// \note Similar to std::vector::clear().
    /// \sa StripCapacity()
    void Clear()
    {
        Count( 0 );
    }
 
    /// \return The capacity of this dynamic array.
    /// \note Similar to std::vector::capacity()
    unsigned Capacity() const { return _capacity; }
 
    /// Reserves space for \a newCapacity elements in the array, reallocating as needed.
    /// \param newCapacity  The new number of elements reserved in the array.
    /// \note Similar to std::vector::reserve(), but does lower capacity when asked.
    void Capacity( const unsigned newCapacity )
    {
        // Case 1: Don't reallocate if the capacity doesn't change
        if( newCapacity == _capacity )
        {
            return;
        }
        // Case 2: Erasing all capacity
        else if( 0 == newCapacity )
        {
            Destroy( 0, _count );
            std::free( _objects );
            _objects  = NULL;
            _capacity = 0;
            _count    = 0;
            return;
        }
 
        // Case 3: Change the capacity
 
        // Allocate the new memory using malloc since we will control construction
        // and destruction separately from memory allocation.
        // Note: Don't set any member vars until after the malloc so that we have
        //       perfect roll-back if malloc fails.
        T* const newObjects = reinterpret_cast<T*>( std::malloc( sizeof( T ) * newCapacity ) );
        if( !newObjects )
        {
            throw std::bad_alloc();
        }
 
        // If we're shrinking the capacity, destroy the obsolete objects
        if( newCapacity < _count )
        {
            Destroy( newCapacity, _count );
            _count = newCapacity;
        }
 
        // Move the old objects over to the new array, if needed
        if( _objects )
        {
            // Move only the active objects, not the potentially uninitialized ones
            for( unsigned i = 0; i < _count; i++ )
            {
                Assign( newObjects[ i ], DISTI_RVAL_MOVE( _objects[ i ] ) );
            }
 
            // Release the old memory
            std::free( _objects );
        }
 
        // Own the new objects
        _objects  = newObjects;
        _capacity = newCapacity;
    }
 
    /// Remove all capacity, destroying any extant items (but deleting any pointees, if the item is a pointer; for that, see DeleteEachAndClear()).
    /// \sa Clear(), DeleteEachAndClear()
    void StripCapacity() { Capacity( 0 ); }
 
    /// 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 object  The object to insert
    /// \param loc  The index location to insert into
    /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
    /// \note Similar to std::vector::insert( object, begin(*this) + loc );
    unsigned Insert( const T& object, unsigned loc )
    {
        return InsertImpl( object, loc );
    }
 
    /// Adds the specified object into the list, at the end of the list
    /// \param object A pointer to the object to add
    /// \return Where the object was inserted
    /// \note Similar to std::vector::push_back()
    unsigned PushBack( const T& object )
    {
        InsertImpl( object, _count );
        return _count - 1;
    }
 
    /// Removes the last item in the array. If the array is empty, it has no effect.
    void PopBack()
    {
        if( _count > 0 )
        {
            Count( _count - 1 );
        }
    }
 
    /// \return The last element in the array.
    /// \throws DistiException if array is empty.
    T& Back()
    {
        GLS_VERIFY( !IsEmpty() );
        return _objects[ _count - 1 ];
    }
 
    /// \return The last element in the array.
    /// \throws DistiException if array is empty.
    const T& Back() const
    {
        GLS_VERIFY( !IsEmpty() );
        return _objects[ _count - 1 ];
    }
 
    /// Adds the specified \a object at the head of the list.
    /// \note Similar to std::vector::insert( object, begin(*this) );
    /// \note Prefer PushBack() instead to avoid inefficiencies.
    /// \param object The object to add.
    void PushFront( const T& object )
    {
        InsertImpl( object, 0 );
    }
 
    // Extra rvalue overloads for efficiency, where available.
#if defined( DISTI_HAS_RVAL_REFS )
    /// 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 object  The object to insert
    /// \param loc  The index location to insert into
    /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
    unsigned Insert( T&& object, unsigned loc )
    {
        return InsertImpl( std::move( object ), loc );
    }
 
    /// Adds the specified \a object into the list, at the end of the list
    /// \param object The object to add.
    /// \return Where the object was inserted
    unsigned PushBack( T&& object )
    {
        return InsertImpl( std::move( object ), _count );
    }
 
    /// Adds the specified \a object at the head of the list.
    /// \note Similar to std::vector::insert( object, begin(*this) );
    /// \note Prefer PushBack() instead to avoid inefficiencies.
    /// \param object The object to add.
    void PushFront( T&& object )
    {
        InsertImpl( std::move( object ), 0 );
    }
#endif
 
    /// Deletes the specified object from the list. Does not delete it, if a pointer.
    /// \param object A pointer to the object to delete
    /// \return true if object was found and deleted else false
    bool Erase( const T& object )
    {
        const unsigned loc = FindIndexOf( *this, object );
        if( loc != g_itemNotFound )
        {
            return EraseAt( loc );
        }
        return false;
    }
 
    /// Removes the object at the specified index. (Does not delete it, if pointer.)
    /// \param index Index of the object to delete
    /// \return true if object was found and deleted else false
    bool EraseAt( const unsigned index )
    {
        if( index >= _count )
        {
            return false;
        }
 
        // Destroy the object in question
        Destroy( _objects[ index ] );
 
        // Shift all items down on top of the deleted item
        for( unsigned j = index; j < _count - 1u; j++ )
        {
            Assign( _objects[ j ], DISTI_RVAL_MOVE( _objects[ j + 1u ] ) );
        }
 
        _count--;
 
        return true;
    }
 
    /// Overload of array operator to get element at desired index
    /// \note Resizes if \a index exceeds Capacity() or Count().
    /// \param index The index of the item to return.
    /// \return The item found, which will be a new item if index is greater than the count.
    T& operator[]( const unsigned index )
    {
        // This gets an element, resizing the array if needed
        if( index >= _capacity )
        {
            Count( index + 1 );
        }
        else if( index >= _count )
        {
            for( unsigned i = _count; i <= index; ++i )
            {
                Assign( _objects[ i ], T() );
            }
 
            _count = index + 1;
        }
 
        return _objects[ index ];
    }
 
    /// Overload of array operator to get element at desired index
    /// \note Does not resize if \a index exceeds Capacity() or Count().
    /// \param index The index of the item to return.
    /// \return The item found.
    const T& operator[]( const unsigned index ) const
    {
        GLS_ASSERT( index < _capacity && index < _count );
        return _objects[ index ];
    }
 
    /// \return The internal array pointer.
    /// \note If you call any non-const methods on this object it may invalidate the pointer.
    T* InternalArray()
    {
        return _objects;
    }
 
    /// \return The internal array pointer.
    /// \note If you call any non-const methods on this object it may invalidate the pointer.
    const T* InternalArray() const
    {
        return _objects;
    }
 
    /// \return true if the list is empty
    bool IsEmpty() const
    {
        return ( _count == 0 );
    }
 
    ///////////////////////////////////////////////////////////////////////////////////////////////
    // The following functions have been deprecated but are retained for now for backwards
    // compatibility. All new code should use their noted replacements.
    ///////////////////////////////////////////////////////////////////////////////////////////////
 
    /// \return The capacity of this array.
    /// \deprecated Renamed to Capacity() for clarity.
    /// \note similar to std::vector::capacity()
    DISTI_DEPRECATED( "Renamed to Capacity() for clarity." )
    unsigned Size() const { return Capacity(); }
 
    /// Reserves space for \a newCapacity elements in the array, reallocating as needed.
    /// \param newCapacity  The new number of elements reserved in the array
    /// \note similar to std::vector::reserve()
    /// \deprecated Renamed to Capacity() for clarity.
    DISTI_DEPRECATED( "Renamed to Capacity() for clarity." )
    void Size( unsigned newCapacity )
    {
        Capacity( newCapacity );
    }
 
    /// 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 object  The object to insert
    /// \param loc  The index location to insert into
    /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
    /// \note Similar to std::vector::insert()
    /// \deprecated Use Insert( object, loc ) instead.
    DISTI_DEPRECATED( "Use Insert( object, loc ) instead." )
    unsigned InsertObject( const T& object, unsigned loc )
    {
        return Insert( object, loc );
    }
 
    /// Adds the specified \a object into the list, at the end of the list
    /// \param object The object to insert.
    /// \return Where the object was inserted.
    /// \note similar to std::vector::push_back()
    /// \deprecated Use PushBack( object ) instead.
    DISTI_DEPRECATED( "Use PushBack( object ) instead." )
    unsigned InsertObject( const T& object )
    {
        return PushBack( object );
    }
 
    /// Insert the object into the list at the specified location
    /// \param object  The object to insert
    /// \param loc  The index location to insert into
    /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
    /// \note similar to std::vector::insert()
    /// \deprecated Use Insert( object, loc + 1 ) instead.
    DISTI_DEPRECATED( "Use Insert( object, loc + 1 ) instead." )
    unsigned InsertObjectAfter( const T& object, unsigned loc )
    {
        return Insert( object, loc + 1 );
    }
 
    /// Adds the specified \a object into the list, at the head of the list
    /// Treats the list like a stack, hence the name Push
    /// \note Similar to std::vector::insert( object, begin(*this) );
    /// \param object The object to add.
    /// \deprecated Renamed to PushFront(), but prefer PushBack() instead to avoid inefficiencies.
    DISTI_DEPRECATED( "Renamed to PushFront(), but prefer PushBack() instead to avoid inefficiencies." )
    void PushObject( const T& object )
    {
        PushFront( object );
    }
 
    // Extra rvalue overloads for efficiency, where available.
#if defined( DISTI_HAS_RVAL_REFS )
    /// 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 object  The object to insert
    /// \param loc  The index location to insert into
    /// \note Similar to std::vector::insert()
    /// \deprecated Use Insert( object, loc ) instead.
    DISTI_DEPRECATED( "Use Insert( object, loc ) instead." )
    void InsertObject( T&& object, unsigned loc )
    {
        Insert( std::move( object ), loc );
    }
 
    /// Adds the specified \a object into the list, at the end of the list
    /// \param object The object to insert.
    /// \return Where the object was inserted.
    /// \note Similar to std::vector::push_back()
    /// \deprecated Use PushBack( object ) instead.
    DISTI_DEPRECATED( "Use PushBack( object ) instead." )
    unsigned InsertObject( T&& object )
    {
        return PushBack( std::move( object ) );
    }
 
    /// Insert the object into the list at the specified location
    /// \param object  The object to insert
    /// \param loc  The index location to insert into
    /// \note Similar to std::vector::insert()
    /// \deprecated Use Insert( object, loc + 1 ) instead.
    DISTI_DEPRECATED( "Use Insert( object, loc + 1 ) instead." )
    void InsertObjectAfter( T&& object, unsigned loc )
    {
        Insert( std::move( object ), loc + 1 );
    }
 
    /// Adds the specified \a object at the head of the list.
    /// \note This must move or copy all existing items, so it may be expensive.
    /// \note Similar to std::vector::insert( object, begin(*this) );
    /// \param object The object to add.
    /// \deprecated Renamed to PushFront(), but prefer PushBack() instead to avoid inefficiencies.
    DISTI_DEPRECATED( "Renamed to PushFront(), but prefer PushBack() instead to avoid inefficiencies." )
    void PushObject( T&& object )
    {
        PushFront( std::move( object ) );
    }
#endif
 
    /// Removes the object, shrinking the array count. (Does not delete it, if pointer.)
    /// \param object A pointer to the object to delete
    /// \return  true if object was found and deleted else false
    /// \note Similar to std::vector::erase()
    /// \deprecated Renamed EraseAt() for clarity.
    DISTI_DEPRECATED( "Renamed Erase() for clarity." )
    bool DeleteObject( const T& object )
    {
        return Erase( object );
    }
 
    /// Removes the object at the specified index. (Does not delete it, if pointer.)
    /// \param index Index of the object to delete
    /// \return  true if object was found and removed else false
    /// \note Similar to std::vector::erase()
    /// \deprecated Renamed EraseAt() for clarity.
    DISTI_DEPRECATED( "Renamed EraseAt() for clarity." )
    bool DeleteObjectAtIndex( const unsigned index )
    {
        return EraseAt( index );
    }
 
    /// Calls delete on each element and then clears the list.
    /// \deprecated Use the non-member function DeleteEachAndClear( dynamicArray ) instead.
    DISTI_DEPRECATED( "Use the non-member function DeleteEachAndClear( dynamicArray ) instead." )
    void EmptyList()
    {
        DeleteEachAndClear( *this );
    }
 
    /// Clears the list so Count() is zero. Does not strip capacity. Shorthand for Count( 0 ).
    /// \deprecated Renamed to Clear() for consistency.
    DISTI_DEPRECATED( "Renamed to Clear() for consistency." )
    void ClearList()
    {
        Clear();
    }
 
    /// Get the index position of the specified \a object in the list
    /// \param object The object whose index is to be found.
    /// \return The index of the object in the list, -1 if it isn't in the list
    /// \deprecated Use helper function FindIndexOf() instead, but note that it returns unsigned.
    DISTI_DEPRECATED( "Use helper function FindIndexOf() instead, but note that it returns unsigned." )
    int Position( const T& object ) const
    {
        const unsigned index = FindIndexOf( *this, object );
        return index == g_itemNotFound ? -1 : static_cast<int>( index );
    }
 
private:
    unsigned _capacity; // Number of elements in the array
    unsigned _count;    // Number of elements used
    T*       _objects;  // The array of objects
 
    // Give access to the dynamic array with the *other* value for the old TypeIsSimple parameter.
    friend class DynamicArray<T, !Obsolete>;
 
    // Expands the object array, leaving a hole at loc.
    void GrowAround( const unsigned loc )
    {
        const unsigned newCapacity = _capacity == 0 ? 2 : _capacity * 2;
        T* const       newObjects  = reinterpret_cast<T*>( std::malloc( sizeof( T ) * newCapacity ) );
        if( !newObjects )
        {
            throw std::bad_alloc();
        }
 
        // Note: We set this after the malloc so that we have perfect roll-back if malloc fails.
        _capacity = newCapacity;
 
        GLS_ASSERT( loc < _capacity );
 
        // Move any old objects over to the new array, touching only the active objects,
        // not the potentially uninitialized ones, leaving a hole at loc.
        for( unsigned i = 0; i < loc; i++ )
        {
            Assign( newObjects[ i ], DISTI_RVAL_MOVE( _objects[ i ] ) );
        }
 
        for( unsigned i = loc; i < _count; i++ )
        {
            Assign( newObjects[ i + 1 ], DISTI_RVAL_MOVE( _objects[ i ] ) );
        }
 
        // Release the old memory
        std::free( _objects );
 
        // Take ownership of the new array
        _objects = newObjects;
    }
 
    // Insert an object by using universal references.
    // This implementation allows us to avoid overloading on universal references, per Effective Modern C++ #26.
    template<class U>
    unsigned InsertImpl( DISTI_UREF( U ) object, unsigned loc )
    {
        // If the Location Index exceeds the array bounds, put the new object at the end of the array.
        // Note: This is a bit surprising behavior from the user's perspective and may hide bugs.
        //       It is kept for historical reasons.
        if( loc >= _count + 1 )
        {
            loc = _count;
        }
 
        // Do we need to expand the array to accomodate the new value?
        if( _count + 1 > _capacity )
        {
            GrowAround( loc );
        }
        else
        {
            // Shift the array elements *after* the insertion location up to make room
            for( unsigned i = _count; i > loc; i-- )
            {
                Assign( _objects[ i ], DISTI_RVAL_MOVE( _objects[ i - 1 ] ) );
            }
        }
 
        // Assign the object at the specified location
        Assign( _objects[ loc ], DISTI_UREF_FORWARD( U, object ) );
        ++_count;
        return loc;
    }
 
    template<bool OtherObsolete>
    void DeepCopyFrom( const DynamicArray<T, OtherObsolete>& other )
    {
        Capacity( other.Count() ); // Don't copy capacity, just active count
        for( unsigned i = 0; i < other.Count(); i++ )
        {
            Assign( _objects[ i ], other._objects[ i ] );
        }
        _count = other.Count();
    }
 
#if defined( DISTI_HAS_RVAL_REFS )
    template<bool OtherObsolete>
    void StealFrom( DynamicArray<T, OtherObsolete>&& other )
    {
        if( this != &other )
        {
            // We're replacing our list, so get rid of any current contents
            StripCapacity();
 
            // Take ownership
            _capacity = other._capacity;
            _count    = other._count;
            _objects  = other._objects;
 
            // Relieve of ownership
            other._capacity = 0;
            other._count    = 0;
            other._objects  = NULL;
        }
    }
#endif
 
    // Assign as if dest = src, but without assuming that dest is valid.
    template<class U>
    static void Assign( T& dest, DISTI_UREF( U ) src )
    {
        // Use placement-new to construct in situ by invoking the copy/move constructor,
        // and not the assignment operator, which makes the (bad) assumption that both
        // the left-hand and right-hand side of the equals are valid.
        new( &dest ) T( DISTI_UREF_FORWARD( U, src ) );
    }
 
    // Destroy an object by selecting which Destroy() implementation is appropriate for this type
    static void Destroy( T& object )
    {
        DestroyImpl( object, DISTI_IS_TRIVIALLY_DESTRUCTIBLE( T ) );
    }
 
    // For non-trivially destructible types, call their destructor explicitly.
    static void DestroyImpl( T& object, /*trivially destructible*/ DISTI_TT_FALSE_TYPE )
    {
        object.~T();
    }
 
    // Do nothing for trivially destructible types
    static void DestroyImpl( T& /*object*/, /*trivially destructible*/ DISTI_TT_TRUE_TYPE ) {}
 
    // Destroy objects with indices in the range [i, end).
    // Does not modify _count or _capacity.
    void Destroy( unsigned i, const unsigned end )
    {
        GLS_ASSERT( i <= end );
        while( i < end )
        {
            Destroy( _objects[ i++ ] );
        }
    }
};
 
/// Overload begin() so that range-for loops and other constructs work with DynamicArray.
/// \param array The array whose first element is to be returned.
/// \return The first element of the array, otherwise NULL.
template<class T, bool Obsolete>
T* begin( DynamicArray<T, Obsolete>& array )
{
    return array.Count() == 0 ? NULL : array.InternalArray();
}
 
/// Overload begin() so that range-for loops and other constructs work with DynamicArray.
/// \param array The array whose first element is to be returned.
/// \return The first element of the array, otherwise NULL.
template<class T, bool Obsolete>
const T* begin( const DynamicArray<T, Obsolete>& array )
{
    return array.Count() == 0 ? NULL : array.InternalArray();
}
 
/// Overload end() so that range-for loops and other constructs work with DynamicArray.
/// \param array The array whose last element is to be returned.
/// \return The last element of the array, otherwise NULL.
template<class T, bool Obsolete>
T* end( DynamicArray<T, Obsolete>& array )
{
    return array.Count() == 0 ? NULL : array.InternalArray() + array.Count();
}
 
/// Overload end() so that range-for loops and other constructs work with DynamicArray.
/// \param array The array whose last element is to be returned.
/// \return The last element of the array, otherwise NULL.
template<class T, bool Obsolete>
const T* end( const DynamicArray<T, Obsolete>& array )
{
    return array.Count() == 0 ? NULL : array.InternalArray() + array.Count();
}
 
/// Get the index position of the specified \a object in the given \a array
/// \param array The list to search.
/// \param object The object to search for.
/// \return The index of the object in the list, or g_itemNotFound if it isn't in the list
template<class T, bool Obsolete, class U>
unsigned FindIndexOf( const DynamicArray<T, Obsolete>& array, const U& object )
{
    for( unsigned i = 0, count = array.Count(); i < count; ++i )
    {
        if( object == array[ i ] )
        {
            return i;
        }
    }
    return g_itemNotFound;
}
 
/// Calls delete on each element and then clears the list.
/// \param array The list to operate on.
/// \note Works only where T is a pointer.
template<class T, bool Obsolete>
void DeleteEachAndClear( DynamicArray<T, Obsolete>& array )
{
    for( unsigned i = 0; i < array.Count(); ++i )
    {
        delete array[ i ];
        array[ i ] = NULL;
    }
    array.Clear();
}
 
/// Calls delete[] on each element and then clears the list.
/// \param array The list to operate on.
/// \note Works only where T is a pointer to an array.
template<class T, bool Obsolete>
void DeleteArraysAndClear( DynamicArray<T, Obsolete>& array )
{
    for( unsigned i = 0; i < array.Count(); ++i )
    {
        delete[] array[ i ];
        array[ i ] = NULL;
    }
    array.Clear();
}
} // namespace disti
 
#endif