dynamic_array.h

/*****************************************************/
/* lean Containers              (c) Tobias Zirr 2011 */
/*****************************************************/

#ifndef LEAN_CONTAINERS_DYNAMIC_ARRAY
#define LEAN_CONTAINERS_DYNAMIC_ARRAY

#include "../lean.h"
#include "../memory/default_heap.h"

namespace lean 
{
namespace containers
{

template < class Element, class Heap = default_heap >
class dynamic_array
{
public:
    typedef Heap heap_type;
    typedef typename heap_type::size_type size_type;

    typedef Element value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;

    typedef pointer iterator;
    typedef const_pointer const_iterator;

private:
    value_type *m_elements;
    value_type *m_elementsEnd;

    // Make sure size_type is unsigned
    LEAN_STATIC_ASSERT(is_unsigned<size_type>::value);

    static LEAN_INLINE void default_construct(Element *dest)
    {
        new (static_cast<void*>(dest)) value_type();
    }
    static void default_construct(Element *dest, Element *destEnd)
    {
        Element *destr = dest;

        try
        {
            for (; dest != destEnd; ++dest)
                default_construct(dest);
        }
        catch(...)
        {
            destruct(destr, dest);
            throw;
        }
    }

    static LEAN_INLINE void copy_construct(Element *dest, const Element &source)
    {
        new (static_cast<void*>(dest)) value_type(source);
    }
    template <class Iterator>
    static void copy_construct(Iterator source, Iterator sourceEnd, Element *dest)
    {
        Element *destr = dest;

        try
        {
            for (; source != sourceEnd; ++dest, ++source)
                copy_construct(dest, *source);
        }
        catch(...)
        {
            destruct(destr, dest);
            throw;
        }
    }

    static LEAN_INLINE void move_construct(Element *dest, Element &source)
    {
#ifndef LEAN0X_NO_RVALUE_REFERENCES
        new (static_cast<void*>(dest)) value_type( std::move(source) );
#else
        copy_construct(dest, source);
#endif
    }

    static LEAN_INLINE void move(Element *dest, Element &source)
    {
#ifndef LEAN0X_NO_RVALUE_REFERENCES
        *dest = std::move(source);
#else
        *dest = source;
#endif
    }
    static void move(Element *source, Element *sourceEnd, Element *dest)
    {
        for (; source != sourceEnd; ++dest, ++source)
            move(dest, *source);
    }

    static void destruct(value_type *destr)
    {
        destr->~value_type();
    }
    static void destruct(value_type *destr, value_type *destrEnd)
    {
        for (; destr != destrEnd; ++destr)
            destruct(destr);
    }

    static LEAN_INLINE value_type* allocate(size_type capacity)
    {
        return (capacity > 0)
            ? static_cast<value_type*>( heap_type::allocate(capacity * sizeof(value_type)) )
            : nullptr;
    }
    
    LEAN_INLINE void free()
    {
        if (m_elements)
        {
            // Do nothing on exception, resources leaking anyways!
            clear();

            value_type *oldElements = m_elements;
            m_elements = nullptr;
            m_elementsEnd = nullptr;

            heap_type::free(oldElements);
        }
    }

public:
    enum consume_t
    {
        consume     
    };

    dynamic_array()
        : m_elements(nullptr),
        m_elementsEnd(nullptr) { }
    explicit dynamic_array(size_type capacity)
        : m_elements( allocate(capacity) ),
        m_elementsEnd( m_elements ) { }
    dynamic_array(const dynamic_array &right)
        : m_elements( allocate(right.size()) ),
        m_elementsEnd( m_elements + right.size() )
    {
        copy_construct(right.m_elements, right.m_elementsEnd, m_elements);
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    dynamic_array(dynamic_array &&right)
        : m_elements(std::move(right.m_elements)),
        m_elementsEnd(std::move(right.m_elementsEnd))
    {
        right.m_elements = nullptr;
        right.m_elementsEnd = nullptr;
    }
#endif

    dynamic_array(dynamic_array &right, consume_t)
        : m_elements(right.m_elements),
        m_elementsEnd(right.m_elementsEnd)
    {
        right.m_elements = nullptr;
        right.m_elementsEnd = nullptr;
    }
    ~dynamic_array()
    {
        free();
    }

    dynamic_array& operator =(const dynamic_array &right)
    {
        if (&right != this)
        {
            reset(right.size());

            copy_construct(right.m_elements, right.m_elementsEnd, m_elements);
            m_elementsEnd += right.size();
        }
        return *this;
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    dynamic_array& operator =(dynamic_array &&right)
    {
        if (&right != this)
        {
            free();

            m_elements = std::move(right.m_elements);
            m_elementsEnd = std::move(right.m_elementsEnd);

            right.m_elements = nullptr;
            right.m_elementsEnd = nullptr;
        }
        return *this;
    }
#endif

    LEAN_INLINE void* allocate_back()
    {
        return m_elementsEnd;
    }
    LEAN_INLINE reference shift_back(value_type *newElement)
    {
        LEAN_ASSERT(newElement == m_elementsEnd);

        return *(m_elementsEnd++);
    }

    LEAN_INLINE reference push_back()
    {
        default_construct(m_elementsEnd);
        return *(m_elementsEnd++);
    }
    LEAN_INLINE pointer push_back(size_type count)
    {
        Element *firstElement = m_elementsEnd;
        default_construct(firstElement, firstElement + count);
        m_elementsEnd += count;
        return firstElement;
    }
    LEAN_INLINE void push_back(const value_type &value)
    {
        copy_construct(m_elementsEnd, value);
        ++m_elementsEnd;
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    LEAN_INLINE void push_back(value_type &&value)
    {
        move_construct(m_elementsEnd, value);
        ++m_elementsEnd;
    }
#endif

    LEAN_INLINE void pop_back()
    {
        LEAN_ASSERT(!empty());

        destruct(m_elementsEnd--);
    }

    LEAN_INLINE void clear()
    {
        Element *oldElementsEnd = m_elementsEnd;
        m_elementsEnd = m_elements;
        destruct(m_elements, oldElementsEnd);
    }

    LEAN_INLINE void reset(size_type newCapacity)
    {
        free();

        if (newCapacity > 0)
        {
            m_elements = allocate(newCapacity);
            m_elementsEnd = m_elements;
        }
    }
    
    LEAN_INLINE reference front(void) { LEAN_ASSERT(!empty()); return *m_elements; };
    LEAN_INLINE const_reference front(void) const { LEAN_ASSERT(!empty()); return *m_elements; };
    LEAN_INLINE reference back(void) { LEAN_ASSERT(!empty()); return m_elementsEnd[-1]; };
    LEAN_INLINE const_reference back(void) const { LEAN_ASSERT(!empty()); return m_elementsEnd[-1]; };

    LEAN_INLINE reference operator [](size_type pos) { return m_elements[pos]; };
    LEAN_INLINE const_reference operator [](size_type pos) const { return m_elements[pos]; };

    LEAN_INLINE iterator begin(void) { return m_elements; };
    LEAN_INLINE const_iterator begin(void) const { return m_elements; };
    LEAN_INLINE iterator end(void) { return m_elementsEnd; };
    LEAN_INLINE const_iterator end(void) const { return m_elementsEnd; };

    LEAN_INLINE bool empty(void) const { return (m_elements == m_elementsEnd); };
    LEAN_INLINE size_type size(void) const { return m_elementsEnd - m_elements; };

    LEAN_INLINE void swap(dynamic_array &right) throw()
    {
        using std::swap;

        swap(m_elements, right.m_elements);
        swap(m_elementsEnd, right.m_elementsEnd);
    }
};

template <class Element, class Heap>
LEAN_INLINE void swap(dynamic_array<Element, Heap> &left, dynamic_array<Element, Heap> &right)
{
    left.swap(right);
}

} // namespace

using containers::dynamic_array;

} // namespace

#endif