move_reallocation_policy.h

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

#ifndef LEAN_CONTAINERS_MOVE_REALLOCATION_POLICY
#define LEAN_CONTAINERS_MOVE_REALLOCATION_POLICY

#include "../lean.h"

namespace lean
{
namespace containers
{


template <class Container, int GrowthDenominator = 2>
class move_reallocation_policy
{
private:
    typedef typename Container::iterator iterator;

public:
    typedef typename Container::size_type size_type;


    static void reserve(Container &container, size_type newCapacity)
    {
        if (newCapacity > container.capacity())
        {
            Container newContainer;

            newContainer.reserve(newCapacity);
            newContainer.resize(container.size());

            for (iterator itOld = container.begin(), itNew = newContainer.begin();
                 itNew != newContainer.end(); ++itOld, ++itNew)
                itNew->move(*itOld);

            using std::swap;
            swap(container, newContainer);
        }

        LEAN_ASSERT(newCapacity <= container.capacity());
    }

    static void pre_resize(Container &container, size_type newCount)
    {
        size_t capacity = container.capacity();

        if (newCount > capacity)
        {
            size_type capacityDelta = capacity / GrowthDenominator;
            size_type maxSize = container.max_size();

            // Mind overflow
            capacity = (maxSize - capacityDelta < capacity)
                ? maxSize
                : capacity + capacityDelta;

            if (capacity < newCount)
                capacity = newCount;

            reserve(container, capacity);
        }

        LEAN_ASSERT(newCount <= container.capacity());
    }
};

} // namespace

using containers::move_reallocation_policy;

} // namespace

#endif