Sawyer/Map.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_Map_H
#define Sawyer_Map_H

#include <Sawyer/Interval.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/map.hpp>
#include <stdexcept>

namespace Sawyer {

namespace Container {

template<class K,
         class T,
         class Cmp = std::less<K>,
         class Alloc = std::allocator<std::pair<const K, T> > >
class Map {
public:
    typedef K Key;                                      
    typedef T Value;                                    
    typedef Cmp Comparator;                             
    typedef Alloc Allocator;                            
private:
    typedef std::map<Key, Value, Comparator, Alloc> StlMap;
    StlMap map_;

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

    template<class S>
    void serialize(S &s, const unsigned /*version*/) {
        s & BOOST_SERIALIZATION_NVP(map_);
    }

public:
    class Node: private std::pair<const Key, Value> {
        // This class MUST BE binary compatible with its super class (see NodeIterator::operator* below)
    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) {}
    public:
        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 BidirectionalIterator {

    public:
        // Five standard iterator types
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type = Value;
        using difference_type = std::ptrdiff_t;
        using pointer = Value*;
        using reference = Value&;

    protected:
        BaseIterator base_;
        BidirectionalIterator() {}
        BidirectionalIterator(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; }

        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 BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> {
        typedef                BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> Super;
    public:
        NodeIterator() {}

        NodeIterator(const NodeIterator &other): Super(other) {}

        // std::map stores std::pair nodes, but we want to return Node, which must have the same layout.
        Node& operator*() const { return *(Node*)&*this->base_; }

        Node* operator->() const { return (Node*)&*this->base_; }
    private:
        friend class Map;
        NodeIterator(const typename StlMap::iterator &base): Super(base) {}
    };

    class ConstNodeIterator: public BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> {
        typedef                     BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> Super;
    public:
        ConstNodeIterator() {}

        ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}

        ConstNodeIterator(const NodeIterator &other): Super(typename StlMap::const_iterator(other.base())) {}

        // std::map stores std::pair nodes, but we want to return Node, which must have the same layout.
        const Node& operator*() const { return *(const Node*)&*this->base_; }

        const Node* operator->() const { return (const Node*)&*this->base_; }
    private:
        friend class Map;
        ConstNodeIterator(const typename StlMap::const_iterator &base): Super(base) {}
        ConstNodeIterator(const typename StlMap::iterator &base): Super(typename StlMap::const_iterator(base)) {}
    };

    class ConstKeyIterator: public BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> {
        typedef                    BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> Super;
    public:
        ConstKeyIterator() {}

        ConstKeyIterator(const ConstKeyIterator &other): Super(other) {}

        ConstKeyIterator(const NodeIterator &other): Super(typename StlMap::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 BidirectionalIterator<ValueIterator, Value, typename StlMap::iterator> {
        typedef                 BidirectionalIterator<ValueIterator, Value, typename StlMap::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 BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> {
        typedef BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> Super;
    public:
        ConstValueIterator() {}

        ConstValueIterator(const ConstValueIterator &other): Super(other) {}

        ConstValueIterator(const ValueIterator &other): Super(typename StlMap::const_iterator(other.base())) {}

        ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}

        ConstValueIterator(const NodeIterator &other): Super(typename StlMap::const_iterator(other.base())) {}

        const Value& operator*() const { return this->base()->second; }

        const Value* operator->() const { return &this->base()->second; }
    };


    //                                  Constructors
public:

    Map() {}

    explicit Map(const Comparator &comparator, const Allocator &allocator = Allocator())
        : map_(comparator, allocator) {}

    Map(const Map& other) {
        map_ = other.map_;
    }

    template<class Key2, class T2, class Cmp2, class Alloc2>
    Map(const Map<Key2, T2, Cmp2, Alloc2> &other) {
        typedef typename Map<Key2, T2, Cmp2, Alloc2>::ConstNodeIterator OtherIterator;
        boost::iterator_range<OtherIterator> otherNodes = other.nodes();
        for (OtherIterator otherIter=otherNodes.begin(); otherIter!=otherNodes.end(); ++otherIter)
            map_.insert(map_.end(), std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
    }

    template<class Key2, class T2, class Cmp2, class Alloc2>
    Map& operator=(const Map<Key2, T2, Cmp2, Alloc2> &other) {
        typedef typename Map<Key2, T2, Cmp2, Alloc2>::ConstNodeIterator OtherIterator;
        clear();
        boost::iterator_range<OtherIterator> otherNodes = other.nodes();
        for (OtherIterator otherIter=otherNodes.begin(); otherIter!=otherNodes.end(); ++otherIter)
            map_.insert(map_.end(), 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();
    }

    Key least() const {
        ASSERT_forbid(isEmpty());
        return map_.begin()->first;
    }

    Key greatest() const {
        ASSERT_forbid(isEmpty());
        typename StlMap::const_iterator last = map_.end();
        --last;
        return last->first;
    }

    Interval<Key> hull() const {
        return isEmpty() ? Interval<Key>() : Interval<Key>::hull(least(), greatest());
    }

    
    //                                  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();
    }

    NodeIterator lowerBound(const Key &key) {
        return map_.lower_bound(key);
    }
    ConstNodeIterator lowerBound(const Key &key) const {
        return map_.lower_bound(key);
    }
    NodeIterator upperBound(const Key &key) {
        return map_.upper_bound(key);
    }
    ConstNodeIterator upperBound(const Key &key) const {
        return map_.upper_bound(key);
    }
    //                                  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 StlMap::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 StlMap::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 StlMap::const_iterator found = map_.find(key);
        return found == map_.end() ? Optional<Value>() : Optional<Value>(found->second);
    }

    Value& getOrElse(const Key &key, Value &dflt) {
        typename StlMap::iterator found = map_.find(key);
        return found == map_.end() ? dflt : found->second;
    }
    const Value& getOrElse(const Key &key, const Value &dflt) const {
        typename StlMap::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 StlMap::const_iterator found = map_.find(key);
        return found==map_.end() ? dflt : found->second;
    }
    
    //                                  Mutators
public:

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

    Map& insertDefault(const Key &key) {
        map_[key] = T();
        return *this;
    }
    
    template<class OtherNodeIterator>
    Map& 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>
    Map& 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 map_.insert(std::make_pair(key, T())).first->second;
    }

    template<class OtherNodeIterator>
    Map& 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;
    }

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

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

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

    Map& eraseAt(const NodeIterator &iter) {
        map_.erase(iter.base());
        return *this;
    }
    Map& eraseAt(const ConstKeyIterator &iter) {
        // std::map can't erase using a const_iterator
        ASSERT_require(iter != keys().end());
        typename StlMap::iterator stdIter = map_.find(*iter);
        ASSERT_require(stdIter != map_.end());
        map_.erase(stdIter);
        return *this;
    }
    Map& eraseAt(const ValueIterator &iter) {
        map_.erase(iter.base());
        return *this;
    }
    template<class Iter>
    Map& eraseAtMultiple(const Iter &begin, const Iter &end) {
        map_.erase(begin.base(), end.base());
        return *this;
    }
    template<class Iter>
    Map& eraseAtMultiple(const boost::iterator_range<Iter> &range) {
        map_.erase(range.begin().base(), range.end().base());
        return *this;
    }
};

} // namespace
} // namespace

#endif