HashMap.h

// WARNING: Changes to this file must be contributed back to Sawyer or else they will
//          be clobbered by the next update from Sawyer.  The Sawyer repository is at
//          https://github.com/matzke1/sawyer.




#ifndef Sawyer_HashMap_H
#define Sawyer_HashMap_H

#include <Sawyer/Optional.h>
#include <Sawyer/Sawyer.h>

#include <boost/range/iterator_range.hpp>
#include <boost/serialization/access.hpp>
#include <boost/serialization/nvp.hpp>
#include <boost/serialization/split_member.hpp>
#include <boost/unordered_map.hpp>
#include <stdexcept>

namespace Sawyer {
namespace Container {

template<class K, class T, class H = boost::hash<K>, class C = std::equal_to<K>,
         class A = std::allocator<std::pair<const K, T> > >
class HashMap {
public:
    typedef K Key;                                      
    typedef T Value;                                    
    typedef H Hasher;                                   
    typedef C Comparator;                               
    typedef A Allocator;                                
private:
    typedef boost::unordered_map<Key, Value, Hasher, Comparator, Allocator> ImplMap;
    ImplMap map_;

private:
    friend class boost::serialization::access;

    // Apparently no serialization functions for boost::unordered_map, so do it the hard way.
    template<class S>
    void save(S &s, const unsigned /*verion*/) const {
        size_t nElmts = map_.size();
        s & BOOST_SERIALIZATION_NVP(nElmts);
        for (typename ImplMap::const_iterator iter = map_.begin(); iter != map_.end(); ++iter) {
            const Key &key = iter->first;
            s & BOOST_SERIALIZATION_NVP(key);
            const Value &value = iter->second;
            s & BOOST_SERIALIZATION_NVP(value);
        }
    }

    template<class S>
    void load(S & s, const unsigned /*version*/) {
        size_t nElmts;
        s & BOOST_SERIALIZATION_NVP(nElmts);
        for (size_t i=0; i<nElmts; ++i) {
            Key key;
            s & BOOST_SERIALIZATION_NVP(key);
            Value value;
            s & BOOST_SERIALIZATION_NVP(value);
            map_.insert(std::make_pair(key, value));
        }
    }

    BOOST_SERIALIZATION_SPLIT_MEMBER();

public:
    class Node: private ImplMap::value_type {
        // This class MUST be binary compatible with ImplMap::value_type
    public:
        explicit Node(const std::pair<const Key, Value> &pair)
            : std::pair<const Key, Value>(pair) {}

        Node(const Key &key, Value &value)
            : std::pair<const Key, Value>(key, value) {}

        const Key& key() const { return this->first; }

        Value& value() { return this->second; }
        const Value& value() const { return this->second; }
    };
    
    // Iterators
private:
    template<class Derived, class Value, class BaseIterator>
    class ForwardIterator {
    public:
        // Five standard iterator types
        using iterator_category = std::forward_iterator_tag;
        using value_type = Value;
        using difference_type = std::ptrdiff_t;
        using pointer = Value*;
        using reference = Value&;

    protected:
        BaseIterator base_;
        ForwardIterator() {}
        ForwardIterator(const BaseIterator &base): base_(base) {}
    public:
        Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }
        Derived& operator++() { ++base_; return *derived(); }
        Derived operator++(int) { Derived old = *derived(); ++*this; return old; }
        template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base(); }
        template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base(); }
        const BaseIterator& base() const { return base_; }
    protected:
        Derived* derived() { return static_cast<Derived*>(this); }
        const Derived* derived() const { return static_cast<const Derived*>(this); }
    };

public:
    class NodeIterator: public ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> {
        typedef                ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> Super;
    public:
        NodeIterator() {}
        NodeIterator(const NodeIterator &other): Super(other) {}
        Node& operator*() const { return *(Node*)&*this->base_; } // boost iter's value cast to our own node type
        Node* operator->() const { return (Node*)&*this->base_; }
    private:
        friend class HashMap;
        NodeIterator(const typename ImplMap::iterator &base): Super(base) {}
    };

    class ConstNodeIterator: public ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> {
        typedef                     ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> Super;
    public:
        ConstNodeIterator() {}
        ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}
        ConstNodeIterator(const NodeIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
        const Node& operator*() const { return *(const Node*)&*this->base_; }
        const Node* operator->() const { return (const Node*)&*this->base_; }
    private:
        friend class HashMap;
        ConstNodeIterator(const typename ImplMap::const_iterator &base): Super(base) {}
        ConstNodeIterator(const typename ImplMap::iterator &base): Super(typename ImplMap::const_iterator(base)) {}
    };

    class ConstKeyIterator: public ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> {
        typedef                    ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> Super;
    public:
        ConstKeyIterator() {}
        ConstKeyIterator(const ConstKeyIterator &other): Super(other) {}
        ConstKeyIterator(const NodeIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
        ConstKeyIterator(const ConstNodeIterator &other): Super(other.base()) {}
        const Key& operator*() const { return this->base()->first; }
        const Key* operator->() const { return &this->base()->first; }
    };

    class ValueIterator: public ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> {
        typedef                 ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> Super;
    public:
        ValueIterator() {}
        ValueIterator(const ValueIterator &other): Super(other) {}
        ValueIterator(const NodeIterator &other): Super(other.base()) {}
        Value& operator*() const { return this->base()->second; }
        Value* operator->() const { return &this->base()->second; }
    };

    class ConstValueIterator: public ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> {
        typedef ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> Super;
    public:
        ConstValueIterator() {}
        ConstValueIterator(const ConstValueIterator &other): Super(other) {}
        ConstValueIterator(const ValueIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
        ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}
        ConstValueIterator(const NodeIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
        const Value& operator*() const { return this->base()->second; }
        const Value* operator->() const { return &this->base()->second; }
    };

    // Constructors
public:

    HashMap() {}

    HashMap(size_t n, const Hasher &hasher = Hasher(), const Comparator &cmp = Comparator(), const Allocator& alloc = Allocator())
        : map_(n, hasher, cmp, alloc) {}

    HashMap(const HashMap& other)
        : map_(other.map_) {}

    template<class K2, class T2, class H2, class C2, class A2>
    HashMap(const HashMap<K2, T2, H2, C2, A2> &other) {
        typedef typename HashMap<K2, T2, H2, C2, A2>::ConstNodeIterator OtherIterator;
        boost::iterator_range<OtherIterator> otherNodes = other.nodes();
        for (OtherIterator otherIter = otherNodes.begin(); otherIter != otherNodes.end(); ++otherIter)
            map_.insert(std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
    }
    
    template<class K2, class T2, class H2, class C2, class A2>
    HashMap& operator=(const HashMap<K2, T2, H2, C2, A2> &other) {
        typedef typename HashMap<K2, T2, H2, C2, A2>::ConstNodeIterator OtherIterator;
        clear();
        boost::iterator_range<OtherIterator> otherNodes = other.nodes();
        for (OtherIterator otherIter = otherNodes.begin(); otherIter != otherNodes.end(); ++otherIter)
            map_.insert(std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
        return *this;
    }

    // Iteration
public:

    boost::iterator_range<NodeIterator> nodes() {
        return boost::iterator_range<NodeIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
    }
    boost::iterator_range<ConstNodeIterator> nodes() const {
        return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
    }
    boost::iterator_range<ConstKeyIterator> keys() {
        return boost::iterator_range<ConstKeyIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
    }
    boost::iterator_range<ConstKeyIterator> keys() const {
        return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
    }
    boost::iterator_range<ValueIterator> values() {
        return boost::iterator_range<ValueIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
    }
    boost::iterator_range<ConstValueIterator> values() const {
        return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
    }
    // Size and capacity
public:

    bool isEmpty() const {
        return map_.empty();
    }

    size_t size() const {
        return map_.size();
    }

    size_t nBuckets() const {
        return map_.bucket_count();
    }

    double loadFactor() const {
        return map_.load_factor();
    }

    double maxLoadFactor() const {
        return map_.max_load_factor();
    }
    void maxLoadFactor(double mlf) {
        map_.max_load_factor(mlf);
    }
    void rehash(size_t nBuckets) {
        map_.rehash(nBuckets);
    }
    
    // Searching
public:

    NodeIterator find(const Key &key) {
        return map_.find(key);
    }
    ConstNodeIterator find(const Key &key) const {
        return map_.find(key);
    }
    bool exists(const Key &key) const {
        return map_.find(key) != map_.end();
    }

    // Accessors
public:

    Value& operator[](const Key &key) {
        return get(key);
    }
    const Value& operator[](const Key &key) const {
        return get(key);
    }
    Value& get(const Key &key) {
        typename ImplMap::iterator found = map_.find(key);
        if (found == map_.end())
            throw std::domain_error("key lookup failure; key is not in map domain");
        return found->second;
    }
    const Value& get(const Key &key) const {
        typename ImplMap::const_iterator found = map_.find(key);
        if (found == map_.end())
            throw std::domain_error("key lookup failure; key is not in map domain");
        return found->second;
    }
    Optional<Value> getOptional(const Key &key) const {
        typename ImplMap::const_iterator found = map_.find(key);
        return found == map_.end() ? Optional<Value>() : Optional<Value>(found->second);
    }

    Value& getOrElse(const Key &key, Value &dflt) {
        typename ImplMap::iterator found = map_.find(key);
        return found == map_.end() ? dflt : found->second;
    }
    const Value& getOrElse(const Key &key, const Value &dflt) const {
        typename ImplMap::const_iterator found = map_.find(key);
        return found == map_.end() ? dflt : found->second;
    }
    const Value& getOrDefault(const Key &key) const {
        static const Value dflt;
        typename ImplMap::const_iterator found = map_.find(key);
        return found==map_.end() ? dflt : found->second;
    }

    // Mutators
public:

    HashMap& insert(const Key &key, const Value &value) {
        std::pair<typename ImplMap::iterator, bool> inserted = map_.insert(std::make_pair(key, value));
        if (!inserted.second)
            inserted.first->second = value;
        return *this;
    }

    HashMap& insertDefault(const Key &key) {
        return insert(key, Value());
    }

    template<class OtherNodeIterator>
    HashMap& insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end) {
        for (OtherNodeIterator otherIter = begin; otherIter != end; ++otherIter)
            insert(Key(otherIter->key()), Value(otherIter->value()));
        return *this;
    }
    template<class OtherNodeIterator>
    HashMap& insertMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
        return insertMultiple(range.begin(), range.end());
    }
    Value& insertMaybe(const Key &key, const Value &value) {
        return map_.insert(std::make_pair(key, value)).first->second;
    }

    Value& insertMaybeDefault(const Key &key) {
        return insertMaybe(key, Value());
    }

    template<class OtherNodeIterator>
    HashMap& insertMaybeMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
        for (OtherNodeIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
            insertMaybe(Key(otherIter->key()), Value(otherIter->value()));
        return *this;
    }

    HashMap& clear() {
        map_.clear();
        return *this;
    }

    HashMap& erase(const Key &key) {
        map_.erase(key);
        return *this;
    }

    template<class OtherKeyIterator>
    HashMap& eraseMultiple(const boost::iterator_range<OtherKeyIterator> &range) {
        for (OtherKeyIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
            map_.erase(Key(*otherIter));
        return *this;
    }

    HashMap& eraseAt(const NodeIterator &iter) {
        map_.erase(iter.base());
        return *this;
    }
    HashMap& eraseAt(const ConstKeyIterator &iter) {
        map_.erase(iter.base());
        return *this;
    }
    HashMap& eraseAt(const ValueIterator &iter) {
        map_.erase(iter.base());
        return *this;
    }
    template<class Iter>
    HashMap& eraseAtMultiple(const Iter &begin, const Iter &end) {
        map_.erase(begin.base(), end.base());
        return *this;
    }
    template<class Iter>
    HashMap& eraseAtMultiple(const boost::iterator_range<Iter> &range) {
        map_.erase(range.begin().base(), range.end().base());
        return *this;
    }
};

} // namespace
} // namespace

#endif