accumulation_vector.h

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

#ifndef LEAN_CONTAINERS_ACCUMULATION_VECTOR
#define LEAN_CONTAINERS_ACCUMULATION_VECTOR

#include "../lean.h"
#include <algorithm>
#include "default_reallocation_policy.h"

namespace lean
{
namespace containers
{

namespace Impl
{

template <class Container>
class has_reverse_iterator
{
private:
    typedef char yes[1];
    typedef char no[2];

    template <class T>
    static yes& sfinae_check(T*, typename T::reverse_iterator* = nullptr);
    static no& sfinae_check(...);

public:
    static const bool value = (
        sizeof( has_reverse_iterator::sfinae_check( static_cast<Container*>(nullptr) ) )
        ==
        sizeof(yes) );
};

template <bool HasReverseIterators, class Container>
struct reverse_iterators_impl
{
    typedef void reverse_iterator;
    typedef void const_reverse_iterator;
};
template <class Container>
struct reverse_iterators_impl<true, Container>
{
    typedef typename Container::reverse_iterator reverse_iterator;
    typedef typename Container::const_reverse_iterator const_reverse_iterator;
};

template <class Container>
struct reverse_iterators
    : public reverse_iterators_impl<has_reverse_iterator<Container>::value, Container> { };

} // namespace
    

template < class Container, class ReallocationPolicy = default_reallocation_policy<Container> >
class accumulation_vector
{
public:
    typedef Container container_type;
    typedef ReallocationPolicy reallocation_policy; 

    typedef typename container_type::value_type value_type;
    typedef typename container_type::size_type size_type;
    typedef typename container_type::allocator_type allocator_type;
    typedef typename container_type::difference_type difference_type;

    typedef typename container_type::pointer pointer;
    typedef typename container_type::const_pointer const_pointer;
    typedef typename container_type::reference reference;
    typedef typename container_type::const_reference const_reference;
    typedef typename container_type::value_type value_type;

    typedef typename container_type::iterator iterator;
    typedef typename container_type::const_iterator const_iterator;

    typedef typename Impl::reverse_iterators<Container>::reverse_iterator reverse_iterator;
    typedef typename Impl::reverse_iterators<Container>::const_reverse_iterator const_reverse_iterator;

private:
    container_type m_container;
    size_type m_size;
    
    LEAN_INLINE void reserve_internal(size_type newCount)
    {
        ReallocationPolicy::reserve(m_container, newCount);
    }
    LEAN_INLINE void growTo(size_type newCount)
    {
        ReallocationPolicy::pre_resize(m_container, newCount);
    }
    LEAN_INLINE void grow(size_type count)
    {
        growTo(m_size + count);
    }

    LEAN_INLINE void assert_outside(const value_type& value)
    {
        LEAN_ASSERT(lean::addressof(value) < lean::addressof(*m_container.begin()) || lean::addressof(*m_container.end()) <= lean::addressof(value));
    }

    LEAN_NOINLINE static void out_of_range()
    {
        throw std::out_of_range("accumulation_vector<T> out of range");
    }
    LEAN_INLINE void check_pos(size_type pos) const
    {
        if (pos >= m_size)
            out_of_range();
    }

public:
    accumulation_vector()
        : m_size(0) { }
    explicit accumulation_vector(const allocator_type &allocator)
        : m_container(allocator),
        m_size(0) { }
    explicit accumulation_vector(size_type count)
        : m_container(count),
        m_size(count) { }
    accumulation_vector(size_type count, const value_type& value)
        : m_container(count, value),
        m_size(count) { }
    accumulation_vector(size_type count, const value_type& value, const allocator_type& allocator)
        : m_container(count, value, allocator),
        m_size(count) { }
    accumulation_vector(const accumulation_vector& right)
        : m_container(right.m_container),
        m_size(right.m_size) { }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    accumulation_vector(accumulation_vector&& right)
        : m_container(std::move(right.m_container)),
        m_size(std::move(right.m_size)) { }
#endif

    template<class Iterator>
    accumulation_vector(Iterator itFirst, Iterator itEnd)
        : m_container(itFirst, itEnd),
        m_size(m_container.size()) { }
    template<class Iterator>
    accumulation_vector(Iterator itFirst, Iterator itEnd, const allocator_type& allocator)
        : m_container(itFirst, itEnd, allocator),
        m_size(m_container.size()) { }

    accumulation_vector& operator =(const accumulation_vector& right)
    {
        if (this != &right)
        {
            if (right.empty())
                // Clearing is extremely fast for this class
                clear();
            else
                // Suppress destruction, assign manually
                assign(right.begin(), right.end());
        }

        return *this;
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    inline accumulation_vector& operator =(accumulation_vector&& right)
    {
        if (this != &right)
        {
            if (right.empty())
                // Keep own allocated storage
                clear();
            else
            {
                // Invoke default move operators
                m_container = std::move(right.m_container);
                m_size = std::move(right.m_size);
            }
        }

        return *this;
    }
#endif

    LEAN_INLINE size_type size(void) const { return m_size; };
    LEAN_INLINE bool empty(void) const { return (m_size == 0); };

    LEAN_INLINE value_type& push_back(void)
    {
        if (m_size == m_container.size())
        {
            grow(1);
            m_container.push_back(value_type());
        }

        return m_container[m_size++];
    }
    LEAN_INLINE void push_back(const value_type& value)
    {
        assert_outside(value);

        if (m_size == m_container.size())
        {
            grow(1);
            m_container.push_back(value);
        }
        else
            m_container[m_size] = value;

        ++m_size;
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    LEAN_INLINE void push_back(value_type&& value)
    {
        assert_outside(value);

        if (m_size == m_container.size())
        {
            grow(1);
            m_container.push_back(std::move(value));
        }
        else
            m_container[m_size] = std::move(value);

        ++m_size;
    }
#endif

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

        --m_size;
    }

    iterator insert(iterator itWhere)
    {
        if (m_size == m_container.size())
        {
            size_type index = itWhere - m_container.begin();
            grow(1);
            itWhere = m_container.insert(m_container.begin() + index, value_type());
        }
        else
            std::copy_backward(itWhere, end(), ++end());

        ++m_size;
        return itWhere;
    }
    iterator insert(iterator itWhere, const value_type& value)
    {
        assert_outside(value);

        if (m_size == m_container.size())
        {
            size_type index = itWhere - m_container.begin();
            grow(1);
            itWhere = m_container.insert(m_container.begin() + index, value);
            ++m_size;
        }
        else
        {
            std::copy_backward(itWhere, end(), ++end());
            ++m_size;
            *itWhere = value;
        }
        
        return itWhere;
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    iterator insert(iterator itWhere, value_type&& value)
    {
        assert_outside(value);

        if (m_size == m_container.size())
        {
            size_type index = itWhere - m_container.begin();
            grow(1);
            itWhere = m_container.insert(m_container.begin() + index, std::move(value));
            ++m_size;
        }
        else
        {
            std::copy_backward(itWhere, end(), ++end());
            ++m_size;
            *itWhere = std::move(value);
        }
        
        return itWhere;
    }
#endif

    iterator insert(iterator itWhere, size_type count)
    {
        size_type newSize = m_size + count;
        
        if(newSize > m_container.size())
        {
            size_type index = itWhere - m_container.begin();
            growTo(newSize);
            m_container.resize(newSize);
            itWhere = m_container.begin() + index;
        }
        
        std::copy_backward(itWhere, end(), end() + count);
        m_size = newSize;

        return itWhere;
    }
    LEAN_INLINE void insert(iterator itWhere, size_type count, const value_type& value)
    {
        assert_outside(value);

        std::fill_n(
            insert(itWhere, count),
            count, value);
    }
    template<class Iterator>
    void insert(iterator itWhere, Iterator itFirst, Iterator itEnd)
    {
        LEAN_ASSERT(itFirst <= itEnd);

        size_type count = itEnd - itFirst;
        size_type index = lean::addressof(*itFirst) - lean::addressof(*m_container.begin());

        // Index is unsigned, make use of wrap-around
        if (index < m_size)
        {
            size_type endIndex = lean::addressof(*itEnd) - lean::addressof(*m_container.begin());
            
            LEAN_ASSERT(itEnd <= itWhere || itWhere <= itFirst);

            if (itWhere <= itFirst)
            {
                index += count;
                endIndex += count;
            }
            itWhere = insert(itWhere, count);

            itFirst = m_container.begin() + index;
            itEnd = m_container.begin() + endIndex;
        }
        else
            itWhere = insert(itWhere, count);
        
        std::copy(itFirst, itEnd, itWhere);
    }

    LEAN_INLINE iterator erase(iterator itWhere)
    {
        LEAN_ASSERT(!empty());
        
        std::copy(++iterator(itWhere), end(), itWhere);
        --m_size;

        return itWhere;
    }
    LEAN_INLINE void erase(iterator itFirst, iterator itEnd)
    {
        std::copy(itEnd, end(), itFirst);
        m_size -= itEnd - itFirst;
    }

    void assign(size_type count, const value_type& value)
    {
        assert_outside(value);

        if(count > m_container.size())
        {
            growTo(count);
            m_container.resize(count);
        }

        std::fill_n(m_container.begin(), count, value);
        m_size = count;
    }
    template<class Iterator>
    void assign(Iterator itFirst, Iterator itEnd)
    {
        LEAN_ASSERT(itFirst <= itEnd);

        size_t count = itEnd - itFirst;
        
        if(count > m_container.size())
        {
            size_type index = lean::addressof(*itFirst) - lean::addressof(*m_container.begin());
            size_type endIndex = lean::addressof(*itEnd) - lean::addressof(*m_container.begin());

            growTo(count);
            m_container.resize(count);

            // Index is unsigned, make use of wrap-around
            if (index < m_size)
            {
                itFirst = m_container.begin() + index;
                itEnd = m_container.begin() + endIndex;
            }
        }

        std::copy(itFirst, itEnd, m_container.begin());
        m_size = count;
    }

    LEAN_INLINE void clear(void) { m_size = 0; }

    LEAN_INLINE allocator_type get_allocator() const { return m_container.get_allocator(); }
    LEAN_INLINE size_type max_size(void) const { return m_container.max_size(); }

    LEAN_INLINE size_type capacity(void) const { return m_container.capacity(); }
    LEAN_INLINE void reserve(size_type count)
    {
        reserve_internal(count);
    }
    void resize(size_type count)
    {
        if(count > m_container.size())
        {
            growTo(count);
            m_container.resize(count);
        }

        m_size = count;
    }
    void resize(size_type count, const value_type& value)
    {
        if(count > m_container.size())
        {
            growTo(count);
            m_container.resize(count);
        }

        if(count > m_size)
            std::fill_n(end(), count - m_size, value);

        m_size = count;
    }

    LEAN_INLINE reference at(size_type pos) { check_pos(pos); return m_container.at(pos); }
    LEAN_INLINE const_reference at(size_type pos) const { check_pos(pos); return m_container.at(pos); }
    LEAN_INLINE reference front(void) { LEAN_ASSERT(!empty()); return m_container.front(); }
    LEAN_INLINE const_reference front(void) const { LEAN_ASSERT(!empty()); return m_container.front(); }
    LEAN_INLINE reference back(void) { LEAN_ASSERT(!empty()); return m_container[m_size - 1]; }
    LEAN_INLINE const_reference back(void) const { LEAN_ASSERT(!empty()); return m_container[m_size - 1]; }

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

    LEAN_INLINE iterator begin(void) { return m_container.begin(); }
    LEAN_INLINE const_iterator begin(void) const { return m_container.begin(); }
    LEAN_INLINE iterator end(void) { return m_container.begin() + m_size; }
    LEAN_INLINE const_iterator end(void) const { return m_container.begin() + m_size; }

    LEAN_INLINE reverse_iterator rbegin(void) { return m_container.rend() - m_size; }
    LEAN_INLINE const_reverse_iterator rbegin(void) const { return m_container.rend() - m_size; }
    LEAN_INLINE reverse_iterator rend(void) { return m_container.rend(); }
    LEAN_INLINE const_reverse_iterator rend(void) const { return m_container.rend(); }

    // Swaps the elements of two accumulation vectors.
    LEAN_INLINE void swap(accumulation_vector& right)
    {
        using std::swap;

        swap(m_container, right.m_container);
        swap(m_size, right.m_size);
    }
};

template<class Container, class Policy>
LEAN_INLINE bool operator ==(const accumulation_vector<Container, Policy>& left, 
    const accumulation_vector<Container, Policy>& right)
{
    return (left.size() == right.size()) && std::equal(left.begin(), left.end(), right.begin());
}

template<class Container, class Policy>
LEAN_INLINE bool operator !=(const accumulation_vector<Container, Policy>& left, 
    const accumulation_vector<Container, Policy>& right)
{
    return !(left == right);
}

template<class Container, class Policy>
LEAN_INLINE bool operator <(const accumulation_vector<Container, Policy>& left, 
    const accumulation_vector<Container, Policy>& right)
{
    return std::lexicographical_compare(left.begin(), left.end(), right.begin(), right.end());
}

template<class Container, class Policy>
LEAN_INLINE bool operator >(const accumulation_vector<Container, Policy>& left, 
    const accumulation_vector<Container, Policy>& right)
{
    return (right < left);
}

template<class Container, class Policy>
LEAN_INLINE bool operator <=(const accumulation_vector<Container, Policy>& left, 
    const accumulation_vector<Container, Policy>& right)
{
    return !(right < left);
}

template<class Container, class Policy>
LEAN_INLINE bool operator >=(const accumulation_vector<Container, Policy>& left, 
    const accumulation_vector<Container, Policy>& right)
{
    return !(left < right);
}

// Swaps the elements of two accumulation vectors.
template<class Container, class Policy>
LEAN_INLINE void swap(accumulation_vector<Container, Policy>& left, 
    accumulation_vector<Container, Policy>& right)
{
    left.swap(right);
}

} // namespace

using containers::accumulation_vector;

} // namespace

#endif