GraphIteratorMap.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_GraphIteratorMap_H
#define Sawyer_GraphIteratorMap_H

#include <Sawyer/Graph.h>
#include <Sawyer/Optional.h>
#include <boost/range/iterator_range.hpp>

namespace Sawyer {
namespace Container {

template<class K, class V>
class GraphIteratorMap {
public:
    typedef K Key;                                      
    typedef V Value;                                    
    class Node {
        Key key_;                                       
        Value value_;                                   
    public:
        Node(const Key &key, const Value &value)
            : key_(key), value_(value) {}

        const Key& key() const { return key_; }

        Value& value() { return value_; }
        const Value& value() const { return value_; }
    };

private:
    // These members are mutable so that we can delay the sorting until the last possible minute while still appearing to
    // have a const-correct interface.
    typedef std::vector<Node> StlVector;
    mutable StlVector items_;                           // the pointers to graph edges or vertices stored in this container
    mutable bool needsUpdate_;                          // true if the items_ are possibly not sorted

    // Iterators
private:
    template<class Derived, class Value, class BaseIterator>
    class BidirectionalIterator: public std::iterator<std::bidirectional_iterator_tag, 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 StlVector::iterator> {
        typedef                BidirectionalIterator<NodeIterator, Node, typename StlVector::iterator> Super;
    public:
        NodeIterator() {}

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

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

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

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

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

        ConstNodeIterator(const NodeIterator &other)    // implicit
            : Super(typename StlVector::const_iterator(other.base())) {}

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

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

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

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

        ConstKeyIterator(const NodeIterator &other)     // implicit
            : Super(typename StlVector::const_iterator(other.base())) {}

        ConstKeyIterator(const ConstNodeIterator &other) // implicit
            : Super(other.base()) {}

        const Key& operator*() const {
            return this->base()->key();
        }

        const Key* operator->() const {
            return &this->base()->key();
        }
    };

    class ValueIterator: public BidirectionalIterator<ValueIterator, Value, typename StlVector::iterator> {
        typedef                 BidirectionalIterator<ValueIterator, Value, typename StlVector::iterator> Super;
    public:
        ValueIterator() {}

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

        ValueIterator(const NodeIterator &other) // implicit
            : Super(other.base()) {}

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

        Value* operator->() const {
            return &this->base()->value();
        }
    };
    
    class ConstValueIterator: public BidirectionalIterator<ConstValueIterator, const Value, typename StlVector::const_iterator> {
        typedef BidirectionalIterator<ConstValueIterator, const Value, typename StlVector::const_iterator> Super;
    public:
        ConstValueIterator() {}

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

        ConstValueIterator(const ValueIterator &other)  // implicit
            : Super(typename StlVector::const_iterator(other.base())) {}

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

        ConstValueIterator(const NodeIterator &other)   // implicit
            : Super(typename StlVector::const_iterator(other.base())) {}

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

        const Value* operator->() const {
            return &this->base()->value();
        }
    };
    
public:
    // Standard types needed by C++ containers with random access iterators for the C++-style iterating functions like begin()
    // and end().
    typedef typename StlVector::value_type value_type;
    typedef typename StlVector::allocator_type allocator_type;
    typedef typename StlVector::reference reference;
    typedef typename StlVector::pointer pointer;
    typedef typename StlVector::const_pointer const_pointer;
    typedef typename StlVector::iterator iterator;
    typedef typename StlVector::const_iterator const_iterator;
    typedef typename StlVector::reverse_iterator reverse_iterator;
    typedef typename StlVector::const_reverse_iterator const_reverse_iterator;
    typedef typename StlVector::difference_type difference_type;
    typedef typename StlVector::size_type size_type;

    // Constructors
public:
    GraphIteratorMap()
        : needsUpdate_(false) {}

    // Mutators
public:
    void updateIdNumbers() {
        needsUpdate_ = true;
    }

    void insert(const Key &item, const Value &value) {
        update();
        Node node(item, value);
        typename std::vector<Node>::iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
        if (items_.end() == lb || lb->key()->id() != item->id()) {
            items_.insert(lb, node);
        } else {
            lb->value() = value;
        }
    }

    Value& insertMaybe(const Key &item, const Value &value) {
        update();
        Node node(item, value);
        typename std::vector<Node>::iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
        if (items_.end() == lb || lb->key()->id() != item->id())
            lb = items_.insert(lb, node);
        return lb->value();
    }

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

    void erase(const Key &item) {
        update();
        Node node(item, Value());
        typename std::vector<Node>::iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
        if (lb != items_.end() && lb->key()->id() == item->id())
            items_.erase(lb);
    }

    void clear() {
        items_.clear();
        needsUpdate_ = false;
    }

    // Queries
public:
    bool exists(const Key &item) const {
        update();
        Node node(item, Value());
        typename std::vector<Node>::const_iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
        return lb != items_.end() && lb->key()->id() == item->id();
    }
    
    Sawyer::Optional<Value> find(const Key &item) const {
        update();
        Node node(item, Value());
        typename std::vector<Node>::const_iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
        if (lb != items_.end() && lb->key()->id() == item->id()) {
            return lb->value();
        } else {
            return Sawyer::Nothing();
        }
    }

    Value operator[](const Key &item) const {
        update();
        return *find(item);
    }
    
    // Iteration

    boost::iterator_range<NodeIterator> nodes() {
        update();
        return boost::iterator_range<NodeIterator>(NodeIterator(items_.begin()), NodeIterator(items_.end()));
    }
    boost::iterator_range<ConstNodeIterator> nodes() const {
        update();
        return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(items_.begin()), ConstNodeIterator(items_.end()));
    }
    boost::iterator_range<ConstKeyIterator> keys() {
        update();
        return boost::iterator_range<ConstKeyIterator>(NodeIterator(items_.begin()), NodeIterator(items_.end()));
    }
    boost::iterator_range<ConstKeyIterator> keys() const {
        update();
        return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(items_.begin()), ConstNodeIterator(items_.end()));
    }
    boost::iterator_range<ValueIterator> values() {
        update();
        return boost::iterator_range<ValueIterator>(NodeIterator(items_.begin()), NodeIterator(items_.end()));
    }
    boost::iterator_range<ConstValueIterator> values() const {
        update();
        return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(items_.begin()), ConstNodeIterator(items_.end()));
    }
    // Undocumented C++-style iterators iterator over the key+value nodes.
    NodeIterator begin() { return NodeIterator(items_.begin()); }
    ConstNodeIterator begin() const { return NodeIterator(items_.begin()); }
    NodeIterator end() { return NodeIterator(items_.end()); }
    ConstNodeIterator end() const { return NodeIterator(items_.end()); }

    // Internal functions
private:
    static bool sortById(const Node &a, const Node &b) {
        return a.key()->id() < b.key()->id();
    }

    void update() const {
        if (needsUpdate_) {
            std::sort(items_.begin(), items_.end(), sortById);
            needsUpdate_ = false;
        } else {
            check();
        }
    }

    void check() const {
        for (size_t i = 1; i < items_.size(); ++i)
            ASSERT_require(sortById(items_[i-1], items_[i]));
    }
};

} // namespace
} // namespace

#endif