simple_hash_map.h

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

#ifndef LEAN_CONTAINERS_SIMPLE_HASH_MAP
#define LEAN_CONTAINERS_SIMPLE_HASH_MAP

#include "../lean.h"
#include "../limits.h"
#include "../smart/terminate_guard.h"
#include "../tags/noncopyable.h"
#include "../functional/hashing.h"
#include "../meta/type_traits.h"
#include <memory>
#include <utility>
#include <cmath>
#include <functional>
#include <string>
#include <iterator>

namespace lean 
{
namespace containers
{

namespace simple_hash_map_policies
{
    template <bool RawMove = false, bool NoDestruct = false, bool RawKeyMove = RawMove, bool NoKeyDestruct = NoDestruct>
    struct policy
    {
        static const bool raw_move = RawMove;
        static const bool no_destruct = NoDestruct;
        static const bool raw_key_move = RawKeyMove;
        static const bool no_key_destruct = NoKeyDestruct;
    };

    typedef policy<> nonpod;
    typedef policy<false, false, true> semipodkey;
    typedef policy<true> semipod;
    typedef policy<false, false, true, true> podkey;
    typedef policy<true, false, true, true> podkey_semipod;
    typedef policy<true, true> pod;
}

template <class Key>
struct default_keys
{
    static const Key invalid_key;
    static const Key end_key;
    LEAN_INLINE static bool is_valid(const Key &key)
    {
        return (key != invalid_key);
    }
};

// Numeric (generic) defaults
template <class Key>
const Key default_keys<Key>::invalid_key =
    (numeric_limits<Key>::has_infinity)
        ? numeric_limits<Key>::infinity
        : (numeric_limits<Key>::is_unsigned)
            ? numeric_limits<Key>::max
            : numeric_limits<Key>::min;
template <class Key>
const Key default_keys<Key>::end_key = Key();

// Pointer defaults
template <class Value>
struct default_keys<Value*>
{
    static Value* const invalid_key;
    static Value* const end_key;

    LEAN_INLINE static bool is_valid(Value *ptr)
    {
        return (ptr != nullptr);
    }
};

template <class Value>
Value* const default_keys<Value*>::invalid_key = nullptr;
template <class Value>
Value* const default_keys<Value*>::end_key = reinterpret_cast<Value*>( static_cast<uintptr_t>(-1) );

// String defaults
template <class Char, class Traits, class Allocator>
struct default_keys< std::basic_string<Char, Traits, Allocator> >
{
    typedef std::basic_string<Char, Traits, Allocator> key_type;

    static const key_type invalid_key;
    static const key_type end_key;

    LEAN_INLINE static bool is_valid(const key_type &key)
    {
        return !key.empty();
    }
};

template <class Char, class Traits, class Allocator>
const std::basic_string<Char, Traits, Allocator>
    default_keys< std::basic_string<Char, Traits, Allocator> >::invalid_key = std::basic_string<Char, Traits, Allocator>();
template <class Char, class Traits, class Allocator>
const std::basic_string<Char, Traits, Allocator>
    default_keys< std::basic_string<Char, Traits, Allocator> >::end_key = std::basic_string<Char, Traits, Allocator>(1, Char());

namespace impl
{

LEAN_MAYBE_EXPORT size_t next_prime_capacity(size_t capacity, size_t max);

template < class Key, class Element,
    class Policy,
    class KeyValues,
    class Allocator >
class simple_hash_map_base
{
protected:
    typedef std::pair<const Key, Element> value_type_;

    typedef typename Allocator::template rebind<value_type_>::other allocator_type_;
    allocator_type_ m_allocator;

    value_type_ *m_elements;
    value_type_ *m_elementsEnd;

    typedef typename allocator_type_::size_type size_type_;
    size_type_ m_count;
    size_type_ m_capacity;

    float m_maxLoadFactor;

    static const size_type_ s_maxElementCount = static_cast<size_type_>(-1) / sizeof(value_type_);
    // Make sure size_type is unsigned
    LEAN_STATIC_ASSERT(is_unsigned<size_type_>::value);
    // Reserve end element to allow for proper iteration termination
    static const size_type_ s_maxBucketCount = s_maxElementCount - 1U;
    // Keep one slot open at all times to simplify wrapped find loop termination
    static const size_type_ s_maxSize = s_maxBucketCount - 1U;
    static const size_type_ s_minSize = (32U < s_maxSize) ? 32U : s_maxSize;

    LEAN_INLINE size_type_ buckets_from_capacity(size_type_ capacity)
    {
        LEAN_ASSERT(capacity <= s_maxSize);

        float bucketHint = ceil(capacity / m_maxLoadFactor);
        
        size_type_ bucketCount = (bucketHint >= s_maxBucketCount)
            ? s_maxBucketCount
            : static_cast<size_type_>(bucketHint);

        // Keep one slot open at all times to simplify wrapped find loop termination conditions
        return max(bucketCount, capacity + 1U);
    }
    LEAN_INLINE size_type_ capacity_from_buckets(size_type_ buckets, size_type_ minCapacity)
    {
        LEAN_ASSERT(buckets <= s_maxBucketCount);
        LEAN_ASSERT(minCapacity <= s_maxSize);

        // Keep one slot open at all times to simplify wrapped find loop termination conditions
        LEAN_ASSERT(minCapacity < buckets);

        return max(
                // Keep one slot open at all times to simplify wrapped find loop termination conditions
                // -> Unsigned overflow handles buckets == 0
                min(static_cast<size_type_>(buckets * m_maxLoadFactor), buckets - 1U),
                // Guarantee minimum capacity
                minCapacity);
    }

    LEAN_INLINE bool contains_element(const value_type_ *element) const
    {
        return (m_elements <= element) && (element < m_elementsEnd);
    }
    LEAN_INLINE bool contains_element(const value_type_ &element) const
    {
        return contains_element(lean::addressof(element));
    }

    static LEAN_INLINE void mark_end(value_type_ *dest)
    {
        new( const_cast<void*>(static_cast<const void*>(lean::addressof(dest->first))) ) Key(KeyValues::end_key);
    }
    static LEAN_INLINE void invalidate(value_type_ *dest)
    {
        new( const_cast<void*>(static_cast<const void*>(lean::addressof(dest->first))) ) Key(KeyValues::invalid_key);
    }
    static void invalidate(value_type_ *dest, value_type_ *destEnd)
    {
        value_type_ *destr = dest;

        try
        {
            for (; dest != destEnd; ++dest)
                invalidate(dest);
        }
        catch (...)
        {
            destruct_keys(destr, dest);
            throw;
        }
    }
    static LEAN_INLINE void revalidate(value_type_ *dest)
    {
        destruct_key(dest);
    }

    static LEAN_INLINE void destruct_key(value_type_ *destr)
    {
        if (!Policy::no_key_destruct)
            destr->first.~Key();
    }
    static void destruct_keys(value_type_ *destr, value_type_ *destrEnd)
    {
        if (!Policy::no_key_destruct)
            for (; destr != destrEnd; ++destr)
                destruct_key(destr);
    }

    class invalidate_guard : public noncopyable
    {
    private:
        value_type_ *m_dest;
        bool m_armed;

    public:
        LEAN_INLINE explicit invalidate_guard(value_type_ *dest, bool armed = true)
            : m_dest(dest),
            m_armed(armed) { }
        LEAN_INLINE ~invalidate_guard()
        {
            if (m_armed)
                invalidate(m_dest);
        }
        LEAN_INLINE void disarm() { m_armed = false; }
    };

    class invalidate_n_guard : public noncopyable
    {
    private:
        value_type_ *m_dest;
        value_type_ *m_destEnd;
        bool m_armed;

    public:
        LEAN_INLINE explicit invalidate_n_guard(value_type_ *dest, value_type_ *destEnd, bool armed = true)
            : m_dest(dest),
            m_destEnd(destEnd),
            m_armed(armed) { }
        LEAN_INLINE ~invalidate_n_guard()
        {
            if (m_armed)
                invalidate(m_dest, m_destEnd);
        }
        LEAN_INLINE void disarm() { m_armed = false; }
    };

    LEAN_INLINE void default_construct(value_type_ *dest, const Key &key)
    {
        invalidate_guard guard(dest);

        revalidate(dest);
        m_allocator.construct(dest, value_type_(key, Element()));

        guard.disarm();
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    LEAN_INLINE void default_construct(value_type_ *dest, Key &&key)
    {
        invalidate_guard guard(dest);

        revalidate(dest);
        m_allocator.construct(dest, value_type_(std::move(key), Element()));

        guard.disarm();
    }
#endif

    LEAN_INLINE void copy_construct(value_type_ *dest, const value_type_ &source)
    {
        invalidate_guard guard(dest);

        revalidate(dest);
        m_allocator.construct(dest, source);

        guard.disarm();
    }
    LEAN_INLINE void move_construct(value_type_ *dest, value_type_ &source)
    {
#ifndef LEAN0X_NO_RVALUE_REFERENCES
        invalidate_guard guard(dest);
        
        revalidate(dest);
        m_allocator.construct(dest, std::move(source));
        
        guard.disarm();
#else
        copy_construct(dest, source);
#endif
    }
    LEAN_INLINE void move(value_type_ *dest, value_type_ &source)
    {
#ifndef LEAN0X_NO_RVALUE_REFERENCES
        const_cast<Key&>(dest->first) = std::move(const_cast<Key&>(source.first));
        dest->second = std::move(source.second);
#else
        const_cast<Key&>(dest->first) = const_cast<Key&>(source.first);
        dest->second = source.second;
#endif
    }
    
    LEAN_INLINE void destruct_element(value_type_ *destr)
    {
        if (!Policy::no_destruct)
            m_allocator.destroy(destr);
    }

    void destruct(value_type_ *destr, value_type_ *destrEnd)
    {
        if (!Policy::no_destruct || !Policy::no_key_destruct)
            for (; destr != destrEnd; ++destr)
                if (key_valid(destr->first))
                    destruct_element(destr);
                else
                    destruct_key(destr);
    }

    void destruct_and_invalidate(value_type_ *destr, value_type_ *destrEnd)
    {
        // Elements invalidated (overwritten) by guard on exception
        invalidate_n_guard invalidateGuard(destr, destrEnd);

        for (; destr != destrEnd; ++destr)
            if (key_valid(destr->first))
            {
                // Don't handle exceptions explicitly, resources leaking anyways
                destruct_element(destr);
                invalidate(destr);
            }

        // Everything has been invalidated correctly
        invalidateGuard.disarm();
    }

    LEAN_NOINLINE static void length_exceeded()
    {
        throw std::length_error("simple_hash_map<K, E> too long");
    }
    LEAN_INLINE static void check_length(size_type_ count)
    {
        if (count > s_maxSize)
            length_exceeded();
    }

    LEAN_INLINE explicit simple_hash_map_base(float maxLoadFactor)
        : m_elements(nullptr),
        m_elementsEnd(nullptr),
        m_count(0),
        m_capacity(0),
        m_maxLoadFactor(maxLoadFactor) { }
    LEAN_INLINE simple_hash_map_base(float maxLoadFactor, const allocator_type_ &allocator)
        : m_allocator(allocator),
        m_elements(nullptr),
        m_elementsEnd(nullptr),
        m_count(0),
        m_capacity(0),
        m_maxLoadFactor(maxLoadFactor) { }
    LEAN_INLINE simple_hash_map_base(const simple_hash_map_base &right)
        : m_allocator(right.m_allocator),
        m_elements(nullptr),
        m_elementsEnd(nullptr),
        m_count(0),
        m_capacity(0),
        m_maxLoadFactor(right.m_maxLoadFactor) { }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    LEAN_INLINE simple_hash_map_base(simple_hash_map_base &&right)
        : m_allocator(std::move(right.m_allocator)),
        m_elements(std::move(right.m_elements)),
        m_elementsEnd(std::move(right.m_elementsEnd)),
        m_count(std::move(right.m_count)),
        m_capacity(std::move(right.m_capacity)),
        m_maxLoadFactor(std::move(right.m_maxLoadFactor)) { }
#endif

    LEAN_INLINE simple_hash_map_base& operator =(const simple_hash_map_base&) { return *this; }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    LEAN_INLINE simple_hash_map_base& operator =(simple_hash_map_base&&) { return *this; }
#endif

    LEAN_INLINE static bool key_valid(const Key &key) { return KeyValues::is_valid(key); }

    LEAN_INLINE void swap(simple_hash_map_base &right) throw()
    {
        using std::swap;

        swap(m_allocator, right.m_allocator);
        swap(m_elements, right.m_elements);
        swap(m_elementsEnd, right.m_elementsEnd);
        swap(m_count, right.m_count);
        swap(m_capacity, right.m_capacity);
        swap(m_maxLoadFactor, right.m_maxLoadFactor);
    }
};

}

template < class Key, class Element,
    class Policy = simple_hash_map_policies::nonpod,
    class Hash = hash<Key>,
    class KeyValues = default_keys<Key>,
    class Pred = std::equal_to<Key>,
    class Allocator = std::allocator<Element> >
class simple_hash_map : private impl::simple_hash_map_base<Key, Element, Policy, KeyValues, Allocator>
{
private:
    typedef impl::simple_hash_map_base<Key, Element, Policy, KeyValues, Allocator> base_type;

    typedef Hash hasher_;
    hasher_ m_hasher;
    typedef Pred key_equal_;
    key_equal_ m_keyEqual;

    void reallocate(size_type_ newBucketCount, size_type_ minCapacity = 0U)
    {
        // Make prime (required for universal modulo hashing)
        newBucketCount = impl::next_prime_capacity(newBucketCount, s_maxBucketCount);
        
        // Guarantee minimum capacity
        // ASSERT: One slot always remains open, automatically terminating find loops
        if (newBucketCount <= minCapacity)
            length_exceeded();
        
        // Use end element to allow for proper iteration termination
        const size_type_ newElementCount = newBucketCount + 1U;
        
        value_type_ *newElements = m_allocator.allocate(newElementCount);
        value_type_ *newElementsEnd = newElements + newBucketCount;
        
        try
        {
            // ASSERT: End element key always valid to allow for proper iteration termination
            mark_end(newElementsEnd);

            try
            {
                invalidate(newElements, newElementsEnd);
            }
            catch(...)
            {
                destruct_key(newElementsEnd);
                throw;
            }
            
            if (!empty())
                try
                {
                    // ASSERT: One slot always remains open, automatically terminating find loops
                    LEAN_ASSERT(size() < newBucketCount);

                    for (value_type_ *element = m_elements; element != m_elementsEnd; ++element)
                        if (base_type::key_valid(element->first))
                            move_construct(
                                locate_element(element->first, newElements, newElementsEnd, newBucketCount).second,
                                *element );
                }
                catch(...)
                {
                    destruct(newElements, newElementsEnd);
                    destruct_key(newElementsEnd);
                    throw;
                }
        }
        catch(...)
        {
            m_allocator.deallocate(newElements, newElementCount);
            throw;
        }
        
        value_type_ *oldElements = m_elements;
        value_type_ *oldElementsEnd = m_elementsEnd;
        const size_type_ oldBucketCount = bucket_count();
        
        m_elements = newElements;
        m_elementsEnd = newElementsEnd;
        m_capacity = capacity_from_buckets(newBucketCount, minCapacity);
        
        if (oldElements)
            free(oldElements, oldElementsEnd, oldBucketCount + 1U);
    }
    
    LEAN_INLINE void free()
    {
        if (m_elements)
            free(m_elements, m_elementsEnd, bucket_count() + 1U);
    }
    LEAN_INLINE void free(value_type_ *elements, value_type_ *elementsEnd, size_type_ elementCount)
    {
        // ASSERT: End element key always valid to allow for proper iteration termination

        // Do nothing on exception, resources leaking anyways!
        destruct(elements, elementsEnd);
        destruct_key(elementsEnd);
        m_allocator.deallocate(elements, elementCount);
    }

    LEAN_INLINE value_type_* first_element(const Key &key) const
    {
        return first_element(key, m_elements, bucket_count());
    }
    LEAN_INLINE value_type_* first_element(const Key &key, value_type_ *elements, size_type_ bucketCount) const
    {
        return elements + m_hasher(key) % bucketCount;
    }
    LEAN_INLINE std::pair<bool, value_type_*> locate_element(const Key &key) const
    {
        return locate_element(key, m_elements, m_elementsEnd, bucket_count());
    }
    LEAN_INLINE std::pair<bool, value_type_*> locate_element(const Key &key, value_type_ *elements, value_type_ *elementsEnd, size_type_ bucketCount) const
    {
        LEAN_ASSERT(base_type::key_valid(key));

        value_type_ *element = first_element(key, elements, bucketCount);

        while (base_type::key_valid(element->first))
        {
            if (m_keyEqual(element->first, key))
                return std::make_pair(false, element);
            
            // Wrap around
            if (++element == elementsEnd)
                element = elements;

            // ASSERT: One slot always remains open, automatically terminating this loop
        }

        return std::make_pair(true, element);
    }
    LEAN_INLINE value_type_* find_element(const Key &key) const
    {
        value_type_ *element = first_element(key);
        
        while (base_type::key_valid(element->first))
        {
            if (m_keyEqual(element->first, key))
                return element;
            
            // Wrap around
            if (++element == m_elementsEnd)
                element = m_elements;

            // ASSERT: One slot always remains open, automatically terminating this loop
        }

        return m_elementsEnd;
    }
    LEAN_INLINE void remove_element(value_type_ *element)
    {
        // If anything goes wrong, we won't be able to fix it
        terminate_guard terminateGuard;

        value_type_ *hole = element;
        
        // Wrap around
        if (++element == m_elementsEnd)
            element = m_elements;

        // Find next empty position
        while (base_type::key_valid(element->first))
        {
            value_type_ *auxElement = first_element(element->first);
            
            bool tooLate = (auxElement <= hole);
            bool tooEarly = (element < auxElement);
            bool wrong = (hole <= element) ? (tooLate || tooEarly) : (tooLate && tooEarly);
            
            // Move wrongly positioned elements into hole
            if (wrong)
            {
                move(hole, *element);
                hole = element;
            }
            
            // Wrap around
            if (++element == m_elementsEnd)
                element = m_elements;

            // ASSERT: One slot always remains open, automatically terminating this loop
        }

        destruct_element(hole);
        invalidate(hole);
        --m_count;

        terminateGuard.disarm();
    }
    LEAN_INLINE void copy_elements_to_empty(const value_type_ *elements, const value_type_ *elementsEnd)
    {
        LEAN_ASSERT(empty());

        for (const value_type *element = elements; element != elementsEnd; ++element)
            if (base_type::key_valid(element->first))
            {
                copy_construct(
                    locate_element(element->first).second,
                    *element );
                ++m_count;
            }
    }

    LEAN_INLINE void growTo(size_type_ newCount, bool checkLength = true)
    {
        // Mind overflow
        if (checkLength)
            check_length(newCount);

        reallocate(buckets_from_capacity(next_capacity_hint(newCount)), newCount);
    }
    LEAN_INLINE void grow(size_type_ count)
    {
        size_type_ oldSize = size();

        // Mind overflow
        if (count > s_maxSize || s_maxSize - count < oldSize)
            length_exceeded();

        growTo(oldSize + count, false);
    }
    LEAN_NOINLINE void growToHL(size_type_ newCount)
    {
        growTo(newCount);
    }
    LEAN_NOINLINE void growHL(size_type_ count)
    {
        grow(count);
    }

public:
    typedef Policy construction_policy;

    typedef allocator_type_ allocator_type;
    typedef size_type_ size_type;
    typedef typename allocator_type::difference_type difference_type;

    typedef typename allocator_type::pointer pointer;
    typedef typename allocator_type::const_pointer const_pointer;
    typedef typename allocator_type::reference reference;
    typedef typename allocator_type::const_reference const_reference;
    typedef typename allocator_type::value_type value_type;
    typedef Key key_type;
    typedef Element mapped_type;

    template <class Element>
    class basic_iterator
    {
    friend class simple_hash_map;

    private:
        Element *m_element;

        enum search_first_valid_t
        {
            search_first_valid
        };

        LEAN_INLINE basic_iterator(Element *element)
            : m_element(element) { }
        LEAN_INLINE basic_iterator(Element *element, search_first_valid_t)
            : m_element(
                (element && !base_type::key_valid(element->first))
                    ? (++basic_iterator(element)).m_element
                    : element
                ) { }

    public:
        typedef std::forward_iterator_tag iterator_category;
        typedef typename simple_hash_map::difference_type difference_type;
        typedef Element value_type;
        typedef value_type& reference;
        typedef value_type* pointer;

        LEAN_INLINE reference operator *() const
        {
            return *m_element;
        }
        LEAN_INLINE pointer operator ->() const
        {
            return m_element;
        }

        LEAN_INLINE basic_iterator& operator ++()
        {
            do
            {
                ++m_element;
            }
            // ASSERT: End element key is always valid
            while (!base_type::key_valid(m_element->first));

            return *this;
        }
        LEAN_INLINE basic_iterator operator ++(int)
        {
            return ++basic_iterator(*this);
        }

        LEAN_INLINE bool operator ==(const basic_iterator &right) const
        {
            return (m_element == right.m_element);
        }
        LEAN_INLINE bool operator !=(const basic_iterator &right) const
        {
            return (m_element != right.m_element);
        }
    };

    typedef basic_iterator<value_type> iterator;
    typedef basic_iterator<const value_type> const_iterator;
    typedef iterator local_iterator;
    typedef const_iterator const_local_iterator;

    typedef hasher_ hasher;
    typedef key_equal_ key_equal;

    simple_hash_map()
        : base_type(0.75f)
    {
        LEAN_ASSERT(key_valid(KeyValues::end_key));
    }
    explicit simple_hash_map(size_type capacity, float maxLoadFactor = 0.75f)
        : base_type(maxLoadFactor)
    {
        LEAN_ASSERT(key_valid(KeyValues::end_key));
        growTo(capacity);
    }
    simple_hash_map(size_type capacity, float maxLoadFactor, const hasher& hash)
        : base_type(maxLoadFactor),
        m_hasher(hash)
    {
        LEAN_ASSERT(key_valid(KeyValues::end_key));
        growTo(capacity);
    }
    simple_hash_map(size_type capacity, float maxLoadFactor, const hasher& hash, const key_equal& keyComp)
        : base_type(maxLoadFactor),
        m_hasher(hash),
        m_keyEqual(keyComp)
    {
        LEAN_ASSERT(key_valid(KeyValues::end_key));
        growTo(capacity);
    }
    simple_hash_map(size_type capacity, float maxLoadFactor, const hasher& hash, const key_equal& keyComp, const allocator_type &allocator)
        : base_type(maxLoadFactor, allocator),
        m_hasher(hash),
        m_keyEqual(keyComp)
    {
        LEAN_ASSERT(key_valid(KeyValues::end_key));
        growTo(capacity);
    }
    simple_hash_map(const simple_hash_map &right)
        : base_type(right),
        m_hasher(right.m_hasher),
        m_keyEqual(right.m_keyEqual)
    {
        if (!right.empty())
        {
            growTo(right.size());
            copy_elements_to_empty(right.m_elements, right.m_elementsEnd);
        }
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    simple_hash_map(simple_hash_map &&right)
        : base_type(std::move(right)),
        m_hasher(std::move(right.m_hasher)),
        m_keyEqual(std::move(right.m_keyEqual))
    {
        right.m_elements = nullptr;
        right.m_elementsEnd = nullptr;
        right.m_count = 0;
        right.m_capacity = 0;
    }
#endif

    ~simple_hash_map()
    {
        free();
    }

    simple_hash_map& operator =(const simple_hash_map &right)
    {
        if (&right != this)
        {
            // Clear before reallocation to prevent full-range moves
            clear();

            if (!right.empty())
            {
                if (right.size() > capacity())
                    growToHL(right.size());
                
                copy_elements_to_empty(right.m_elements, right.m_elementsEnd);
            }
        }
        return *this;
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    simple_hash_map& operator =(simple_hash_map &&right)
    {
        if (&right != this)
        {
            free();

            m_elements = std::move(right.m_elements);
            m_elementsEnd = std::move(right.m_elementsEnd);

            right.m_elements = nullptr;
            right.m_elementsEnd = nullptr;

            m_allocator = std::move(right.m_allocator);
        }
        return *this;
    }
#endif

    LEAN_INLINE reference insert(const key_type &key)
    {
        LEAN_ASSERT(base_type::key_valid(key));

        if (m_count == capacity())
            growHL(1);

        std::pair<bool, value_type*> element = locate_element(key);
        
        if (element.first)
        {
            default_construct(element.second, key);
            ++m_count;
        }
        return *element.second;
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES


    LEAN_INLINE reference insert(key_type &&key)
    {
        LEAN_ASSERT(base_type::key_valid(key));

        if (m_count == capacity())
            growHL(1);

        std::pair<bool, value_type*> element = locate_element(key);
        
        if (element.first)
        {
            default_construct(element.second, std::move(key));
            ++m_count;
        }
        return *element.second;
    }
#endif

    LEAN_INLINE std::pair<iterator, bool> insert(const value_type &value)
    {
        LEAN_ASSERT(base_type::key_valid(value.first));

        if (m_count == capacity())
        {
            if (contains_element(value))
                return std::make_pair(iterator(const_cast<value_type*>(lean::addressof(value))), false);

            growHL(1);
        }

        std::pair<bool, value_type*> element = locate_element(value.first);

        if (element.first)
        {
            copy_construct(element.second, value);
            ++m_count;
        }
        return std::make_pair(iterator(element.second), element.first);
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    LEAN_INLINE std::pair<iterator, bool> insert(value_type &&value) // wrong way round
    {
        LEAN_ASSERT(base_type::key_valid(value.first));

        if (m_count == capacity())
        {
            if (contains_element(value))
                return std::make_pair(iterator(lean::addressof(value)), false);

            growHL(1);
        }

        std::pair<bool, value_type*> element = locate_element(value.first);

        if (element.first)
        {
            move_construct(element.second, value);
            ++m_count;
        }
        return std::make_pair(iterator(element.second), element.first);
    }
#endif

    LEAN_INLINE size_type erase(const key_type &key)
    {
        // Explicitly handle unallocated state
        value_type* element = (!empty())
            ? find_element(key)
            : m_elementsEnd;

        if (element != m_elementsEnd)
        {
            remove_element(element);
            return 1;
        }
        else
            return 0;
    }
    LEAN_INLINE iterator erase(iterator where)
    {
        LEAN_ASSERT(contains_element(where.m_element));
        
        remove_element(where.m_element);
        return iterator(where.m_element, iterator::search_first_valid);
    }

    LEAN_INLINE void clear()
    {
        m_count = 0;
        destruct_and_invalidate(m_elements, m_elementsEnd);
    }

    LEAN_INLINE void reserve(size_type newCapacity)
    {
        // Mind overflow
        check_length(newCapacity);

        if (newCapacity > capacity())
            reallocate(buckets_from_capacity(newCapacity), newCapacity);
    }
    LEAN_INLINE void rehash(size_type newCapacity)
    {
        newCapacity = max(size(), newCapacity);

        // Mind overflow
        check_length(newCapacity);

        if (newCapacity != capacity())
            reallocate(buckets_from_capacity(newCapacity), newCapacity);
    }

    LEAN_INLINE iterator find(const key_type &key) { return (!empty()) ? iterator(find_element(key)) : end(); }
    LEAN_INLINE const_iterator find(const key_type &key) const { return (!empty()) ? const_iterator(find_element(key)) : end(); }

    LEAN_INLINE mapped_type& operator [](const key_type &key) { return insert(key).second; }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    LEAN_INLINE mapped_type& operator [](key_type &&key) { return insert(std::move(key)).second; }
#endif

    LEAN_INLINE iterator begin(void) { return iterator(m_elements, iterator::search_first_valid); }
    LEAN_INLINE const_iterator begin(void) const { return const_iterator(m_elements, const_iterator::search_first_valid); }
    LEAN_INLINE iterator end(void) { return iterator(m_elementsEnd); }
    LEAN_INLINE const_iterator end(void) const { return const_iterator(m_elementsEnd); }

    LEAN_INLINE allocator_type get_allocator() const { return m_allocator; };

    LEAN_INLINE bool key_valid(const key_type &key) const { return base_type::key_valid(key); }

    LEAN_INLINE bool empty(void) const { return (m_count == 0); };
    LEAN_INLINE size_type size(void) const { return m_count; };
    LEAN_INLINE size_type capacity(void) const { return m_capacity; };
    LEAN_INLINE size_type bucket_count() const { return m_elementsEnd - m_elements; }

    LEAN_INLINE float max_load_factor() const { return m_maxLoadFactor; }
    void max_load_factor(float factor)
    {
        m_maxLoadFactor = factor;

        // Make sure capacity never goes below the number of elements currently stored
        // -> Capacity equal count will result in reallocation on next element insertion
        m_capacity = capacity_from_buckets(bucket_count(), size());
    }

    LEAN_INLINE float load_factor() const { return static_cast<float>(m_count) / static_cast<float>(m_capacity); };

    size_type next_capacity_hint(size_type count) const
    {
        size_type oldCapacity = capacity();
        LEAN_ASSERT(oldCapacity <= s_maxSize);

        // Try to double capacity (mind overflow)
        size_type newCapacity = (s_maxSize - oldCapacity < oldCapacity)
            ? 0
            : oldCapacity + oldCapacity;
        
        if (newCapacity < count)
            newCapacity = count;

        if (newCapacity < s_minSize)
            newCapacity = s_minSize;
        
        return newCapacity;
    }

    LEAN_INLINE void swap(simple_hash_map &right) throw()
    {
        using std::swap;

        swap(m_keyEqual, right.m_keyEqual);
        swap(m_hasher, right.m_hasher);
        base_type::swap(right);
    }
    LEAN_INLINE size_type max_size() const
    {
        return s_maxSize;
    }
};

template <class Element, class Policy, class Allocator>
LEAN_INLINE void swap(simple_hash_map<Element, Policy, Allocator> &left, simple_hash_map<Element, Policy, Allocator> &right)
{
    left.swap(right);
}

} // namespace

namespace simple_hash_map_policies = containers::simple_hash_map_policies;
using containers::simple_hash_map;

} // namespace

#ifdef LEAN_INCLUDE_LINKED
#include "source/simple_hash_map.cpp"
#endif

#endif