accumulation_map.h

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

#ifndef LEAN_CONTAINERS_ACCUMULATION_MAP
#define LEAN_CONTAINERS_ACCUMULATION_MAP

#include "../lean.h"
#include <utility>

namespace lean
{
namespace containers
{
    

template <class Container>
class accumulation_map
{
public:
    typedef Container container_type;
    typedef typename container_type::allocator_type allocator_type;
    typedef typename container_type::size_type size_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 container_type::reverse_iterator reverse_iterator;
    typedef typename container_type::const_reverse_iterator const_reverse_iterator;

    typedef typename container_type::key_compare key_compare;
    typedef typename container_type::key_type key_type;
    typedef typename container_type::mapped_type mapped_type;
    typedef typename container_type::value_compare value_compare;

private:
    // Container
    container_type m_container;

    // Invalid marker
    mapped_type m_invalidValue;

    LEAN_INLINE void invalidate(mapped_type &value) const
    {
        // Const method modifier makes m_invalidValue const
        value = m_invalidValue;
    }

public:
    accumulation_map() { }
    explicit accumulation_map(const key_compare& predicate)
        : m_container(predicate) { }
    accumulation_map(const key_compare& predicate, const allocator_type& allocator)
        : m_container(predicate, allocator) { }
    accumulation_map(const accumulation_map& right)
        : m_container(right.m_container) { }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    accumulation_map(accumulation_map&& right)
        : m_container(std::move(right.m_container)) { }
#endif

    template<class Iterator>
    accumulation_map(Iterator itFirst, Iterator itEnd)
        : m_container(itFirst, itEnd) { }
    template<class Iterator>
    accumulation_map(Iterator itFirst, Iterator itEnd, const key_compare& predicate)
        : m_container(itFirst, itEnd, predicate) { }
    template<class Iterator>
    accumulation_map(Iterator itFirst, Iterator itEnd, const key_compare& predicate, const allocator_type& allocator)
        : m_container(itFirst, itEnd, predicate, allocator) { }

    accumulation_map& operator =(const accumulation_map &right)
    {
        if (this != &right)
        {
            m_invalidValue = right.m_invalidValue;

            key_compare keyComp = m_container.key_comp();

            iterator itDest = m_container.begin();
            const_iterator itSource = right.begin();

            while (itSource != right.end() && itDest != m_container.end())
            {
                // Replace old value with new one on exact match
                if (itSource->first == itDest->first)
                    (itDest++)->second = (itSource++)->second;
                // Wait for next source element, if still less than dest
                else if (keyComp(itSource->first, itDest->first))
                    m_container.insert(itDest, *(itSource++));
                // Source element already greater than dest, invalidate dest
                else
                    invalidate((itDest++)->second);
            }

            // Invalidate remaining old elements
            while (itDest != m_container.end())
                invalidate((itDest++)->second);

            // Append remaining source elements
            while (itSource != right.end())
                m_container.insert(m_container.end(), *(itSource++));
        }
        return *this;
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    inline accumulation_map& operator =(accumulation_map &&right)
    {
        m_container = std::move(right.m_container);
        return *this;
    }
#endif

    LEAN_INLINE void inv_elem(const mapped_type &invalid) { m_invalidValue = invalid; }
    LEAN_INLINE mapped_type inv_elem(void) { return m_invalidValue; }

    LEAN_INLINE size_type size(void) const { return m_container.size(); };
    LEAN_INLINE bool empty(void) const { return m_container.empty(); };

    LEAN_INLINE std::pair<iterator, bool> insert(const value_type &element) { return m_container.insert(element); }
    LEAN_INLINE iterator insert(iterator itWhere, const value_type &element) { return m_container.insert(itWhere, element); }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    LEAN_INLINE std::pair<iterator, bool> insert(value_type &&element) { return m_container.insert(std::move(element)); }
    LEAN_INLINE iterator insert(iterator itWhere, value_type &&element) { return m_container.insert(itWhere, std::move(element)); }
#endif

    template<class Iterator>
    LEAN_INLINE void insert(Iterator itFirst, Iterator itEnd) { m_container.insert(itFirst, itEnd); }

    LEAN_INLINE size_type erase(const key_type &key)
    {
        iterator itElem = m_container.find(key);

        if (itElem != m_container.end())
        {
            invalidate(itElem->second);
            return 1;
        }
        else
            return 0;
    }
    LEAN_INLINE iterator erase(iterator itWhere)
    {
        invalidate(itWhere->second);
        return itWhere;
    }
    LEAN_INLINE void erase(iterator itFirst, iterator itEnd)
    {
        while (itFirst != itEnd)
            invalidate((itFirst++)->second);
    }

    LEAN_INLINE size_type erase_fully(const key_type &key) { return m_container.erase(key); }
    LEAN_INLINE iterator erase_fully(iterator itWhere) { return m_container.erase(itWhere); }
    LEAN_INLINE void erase_fully(iterator itFirst, iterator itEnd) { m_container.erase(itFirst, itEnd); }

    LEAN_INLINE void clear(void)
    {
        // Invalidate all elements
        for (iterator itElem = begin(); itElem != end(); ++itElem)
            invalidate(itElem->second);
    }
    LEAN_INLINE void reset(void) { m_container.clear(); }

    LEAN_INLINE key_compare key_comp(void) const { return m_container.key_comp(); }
    LEAN_INLINE value_compare value_comp(void) const { return m_container.value_comp(); }

    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 iterator lower_bound(const key_type &key) { return m_container.lower_bound(key); }
    LEAN_INLINE const_iterator lower_bound(const key_type &key) const { return m_container.lower_bound(key); }
    LEAN_INLINE iterator upper_bound(const key_type &key) { return m_container.upper_bound(key); }
    LEAN_INLINE const_iterator upper_bound(const key_type &key) const { return m_container.upper_bound(key); }
    LEAN_INLINE std::pair<iterator, iterator> equal_range(const key_type &key) { return m_container.equal_range(key); }
    LEAN_INLINE std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const { return m_container.equal_range(key); }

    LEAN_INLINE iterator find(const key_type &key) { return m_container.find(key); }
    LEAN_INLINE const_iterator find(const key_type &key) const { return m_container.find(key); }
    LEAN_INLINE size_type count(const key_type &key) const { return m_container.count(key); }

    LEAN_INLINE mapped_type& operator [](const key_type &key) { return m_container[key]; }

    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.end(); }
    LEAN_INLINE const_iterator end(void) const { return m_container.end(); }

    LEAN_INLINE reverse_iterator rbegin(void) { return m_container.rbegin(); }
    LEAN_INLINE const_reverse_iterator rbegin(void) const { return m_container.rbegin(); }
    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 maps.
    LEAN_INLINE void swap(accumulation_map& right)
    {
        using std::swap;

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

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

} // namespace

using containers::accumulation_map;

} // namespace

#endif