Saf/Collection/DynArray.h

Go to the documentation of this file.

/*
    This file is part of Simple Application Framework (Saf) library.
    Copyright (C) 2010 - 2012 Ondrej Danek <ondrej.danek@gmail.com>

    This library is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published 
    by the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Saf is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Simple Application Framework library. If not, 
    see <http://www.gnu.org/licenses/>.
*/

#ifndef SAF_COLLECTION_DYNARRAY_H
#define SAF_COLLECTION_DYNARRAY_H

#include "../Type.h"
#include "../Mem/Alloc.h"
#include "../IndexOutOfRangeException.h"
#include "../OverflowException.h"
#include "../ArgumentException.h"
#include "../Algo/Swap.h"
#include "../Algo/Selection/MinMax.h"
#include "../Type/Limits.h"

namespace Saf
{
    namespace Collection
    {
        template <class T>
        class DynArray
        {
        protected:
            typedef DynArray<T> MyType;

        public:
            typedef T* Iterator;
            typedef const T* ConstIterator;

        protected:
            static Size MinCapacity()
            {
                return 16;
            }

        private:
            Size m_elems;
            Size m_cap;
            T *m_data;

        public:
            DynArray()
                : m_elems(0), m_cap(0), m_data(nullptr)
            {}

            explicit DynArray(Size initSize, const T& initVal = T())
                : m_elems(0), m_cap(0), m_data(nullptr)
            {
                Resize(initSize, initVal);
            }

            DynArray(const MyType& a)
                : m_elems(0), m_cap(0), m_data(nullptr)
            {
                *this = a;
            }

            MyType& operator=(const MyType& a)
            {
                if (&a != this)
                {
                    Resize(a.Elements());
                    Algo::Range::Copy(a.Begin(), a.End(), Begin());
                }

                return *this;
            }

            ~DynArray()
            {
                Free();
            }

            MyType& Free()
            {
                if (m_cap > 0)
                {
                    while (m_elems > 0)
                    {
                        m_data[--m_elems].~T();
                    }

                    Mem::OperatorDelete(m_data, m_cap);                    
                    m_cap = 0;
                }

                return *this;
            }

            MyType& Swap(MyType& da)
            {
                if (this != &da)
                {
                    Algo::Swap(m_elems, da.m_elems);
                    Algo::Swap(m_cap, da.m_cap);
                    Algo::Swap(m_data, da.m_data);
                }

                return *this;
            }

            Size Elements() const
            {
                return m_elems;
            }

            Size Capacity() const
            {
                return m_cap;
            }

            bool IsEmpty() const
            {
                return m_elems == 0;
            }

            T& operator[](Size i)
            {
                return m_data[i];
            }

            const T& operator[](Size i) const
            {
                return m_data[i];
            }

            MyType& PushBack(const T& val)
            {
                Resize(m_elems + 1, val);
                return *this;
            }

            MyType& PushFront(const T& val)
            {
                Resize(m_elems + 1);

                // @todo Is this safe?
                for (Size i = m_elems - 1; i > 0; --i)
                {
                    m_data[i] = m_data[i - 1];
                }

                m_data[0] = val;

                return *this;
            }

            MyType& PopBack()
            {
                if (m_elems > 0)
                {
                    --m_elems;
                    m_data[m_elems].~T();
                }

                return *this;
            }

            MyType& PopFront()
            {
                if (m_elems > 0)
                {
                    Erase(Begin());
                }

                return *this;
            }

            Iterator Erase(Iterator it)
            {
                return Erase(it, it + 1);
            }

            Iterator Erase(Iterator itBegin, Iterator itEnd)
            {
                if (itBegin > itEnd)
                {
                    throw ArgumentException(SAF_SOURCE_LOCATION, "Invalid range specification.");
                }

                if (itBegin < Begin() || itEnd > End())
                {
                    throw IndexOutOfRangeException(SAF_SOURCE_LOCATION);
                }

                // Number of removed elements
                Size num = itEnd - itBegin;

                if (num)
                {
                    // @todo Is this safe?
                    if (itEnd < End())
                    {
                        Algo::Range::Copy(itEnd, End(), itBegin);
                    }
                    
                    while (num-- > 0)
                    {
                        End()->~T();
                        --m_elems;
                    }
                }

                return itBegin;
            }

            MyType& Resize(Size newSize, const T& initVal = T())
            {
                if (newSize > m_cap)
                {
                    Grow(OptimalCapacityIncrease(newSize));
                }

                if (newSize > m_elems)
                {
                    // Add elements
                    while (m_elems < newSize)
                    {
                        new (&m_data[m_elems]) T(initVal);
                        m_elems++;
                    }
                }
                else if (newSize < m_elems)
                {
                    // Remove elements
                    while (m_elems > newSize)
                    {
                        m_data[--m_elems].~T();
                    }
                }

                return *this;
            }

            MyType& Reserve(Size cap)
            {
                if (cap > m_cap)
                {
                    Grow(cap);
                }

                return *this;
            }

            MyType& Shrink()
            {
                if (!m_elems)
                {
                    Free();
                }
                else if (m_elems != m_cap)
                {
                    Grow(Algo::Selection::Max(MinCapacity(), m_elems));
                }
            }

            Iterator Begin()
            {
                return m_data;
            }

            ConstIterator Begin() const
            {
                return m_data;
            }

            Iterator End()
            {
                return m_data + m_elems;
            }

            ConstIterator End() const
            {
                return m_data + m_elems;
            }

            Iterator Front()
            {
                return m_data;
            }

            ConstIterator Front() const
            {
                return m_data;
            }

            Iterator Back()
            {
                return m_data + (m_elems - 1);
            }

            ConstIterator Back() const
            {
                return m_data + (m_elems - 1);
            }

        protected:
            void Grow(Size cap)
            {
                if (!cap)
                {
                    throw ArgumentException(SAF_SOURCE_LOCATION, "Capacity must be nonzero.");
                }

                if (cap < m_elems)
                {
                    throw ArgumentException(SAF_SOURCE_LOCATION, "Capacity must be at least equal to the number of elements.");
                }

                // Alloc new array
                T *newData;
                Mem::OperatorNew(newData, cap, SAF_SOURCE_LOCATION);

                // Copy data
                Size newSize = 0;

                try
                {
                    while (newSize < m_elems)
                    {
                        new (&newData[newSize]) T(m_data[newSize]);
                        ++newSize;
                    }
                }
                catch (...)
                {
                    // Exception, deallocate temporary array
                    while (newSize > 0)
                    {
                        newData[newSize].~T();
                        --newSize;
                    }

                    Mem::OperatorDelete(newData, cap);
                    throw; // Re-throw
                }

                // Deallocate old and swap pointers
                Free();

                m_data = newData;
                m_cap = cap;
                m_elems = newSize;
            }

            Size OptimalCapacityIncrease(Size reqSize)
            {
                Size maxElems = (Type::Limits<Size>::Max() / sizeof(T)) - 1;

                if (reqSize > maxElems)
                {
                    throw OverflowException(SAF_SOURCE_LOCATION, "Requested number of elements "
                        "exceeds the maximum possible.");
                }

                // Ideally grow by half of the old capacity
                Size newCap = (maxElems - m_cap < m_cap / 2) ? maxElems : (m_cap + m_cap / 2);

                return Algo::Selection::Max(MinCapacity(), reqSize, newCap);
            }
        };
    }

    namespace Algo
    {
        // Swap specialization for dynamic arrays.
        template <class T>
        struct SwapFunc< Collection::DynArray<T> >
        {
            void operator()(Collection::DynArray<T>& x, Collection::DynArray<T>& y)
            {
                x.Swap(y);
            }
        };
    }
}

#endif