#ifndef ORIGIN_VECTOR_SHRINK_HPP
#define ORIGIN_VECTOR_SHRINK_HPP

#include <origin/memory.hpp>

namespace origin { namespace vector_ {

/**
 * The never strategy will never cause the vector shrink. This is generally the
 * default and preferred behavior since vectors can be "shrink-wrapped" after
 * a series of operations in order to save memory.
 */
struct shrink_never {
    template <typename Vector>
    void operator()(Vector&) const { }
};

/**
 * The exponential shrinking policy automatically reduces the capacity of a
 * vector after erasures. The new capacity is reallocated as Factor * size()
 * whenever size() &gt; capacity() / Fraction. For example, if a 100 element
 * vector is reduced to 5 elements, the vector is resized so that its capcity
 * is 10.
 */
template <std::size_t Fraction = 4u, std::size_t Factor = 2u>
struct shrink_exponential {
    /** @requires MemoryRange<Range> */
    template <typename Range>
    void operator()(Range& v) const
    {
        typedef typename Range::allocator_type Alloc;
        typedef typename Range::pointer Ptr;
        typedef typename Range::size_type Size;
        if(v.size() < v.capacity() / Fraction) {
            Alloc& alloc = v.get_allocator();
            Size size = v.size();
            Size ext = (size + 1) * Factor;

            // Try to allocate the new memory and move the previous elements
            // of the vector into that location. If an exception occurs,
            // destruct any moved elements and deallocate the memory.
            // TODO What happens if an exception occurs in the middle of the
            // move sequence? We've moved part of the original vector into
            // a new location, so destructing those elements will effectively
            // cause them to be lost. Ideally, we'd like a no-throw guarantee
            // on move operations.
            Ptr p = alloc.allocate(ext);
            try {
                uninitialized_move(v.start(), v.finish(), p, alloc);
            }
            catch(...) {
                destruct(p, p + size, alloc);
                alloc.deallocate(p, ext);
                throw;
            }

            // Don't forget to deallocate the previous memory.
            alloc.deallocate(v.start(), v.capacity());

            // Reset the structure of the to the new dimensions.
            v.start(p);
            v.finish(p + size);
            v.extent(p + ext);
        }
    }
};

/** @name Vector Shrink Strategy
 * The shrink policy determines how the vector shrinks after erasures of
 * single or ranges of elements.
 */
struct shrink_policy { };

/** @requires ShrinkStrategy<Strategy> */
template <typename Strategy = shrink_never>
struct shrink {
    typedef shrink_policy policy_kind;
    typedef Strategy type;

    // Aliases for common shrinking policies
    typedef shrink<grow_never> never;
    typedef shrink<shrink_exponential<4, 2>> halving;
};

template <typename Policies, typename Default>
class extract_shrink {
    typedef policy_element<shrink_policy, Policies> element;
public:
    typedef typename mpl::if_<
        std::is_same<typename element::type, mpl::none>,
        Default,
        typename element::type
    >::type type;
};

} } // namespace origin::vector_

#endif