GraphIteratorSet.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_GraphIteratorSet_H
#define Sawyer_GraphIteratorSet_H

#include <Sawyer/Graph.h>

namespace Sawyer {
namespace Container {

template<class T>
class GraphIteratorSet {
public:
    typedef T 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<Value> 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
public:
    typedef typename StlVector::const_iterator ConstIterator;

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

    // Iteration
public:
    boost::iterator_range<ConstIterator> values() const {
        update();
        return boost::iterator_range<ConstIterator>(items_.begin(), items_.end());
    }

    // Mutators
public:
    void updateIdNumbers() {
        needsUpdate_ = true;
    }
    
    void insert(const Value &item) {
        update();
        insertUnique(item);
    }

    void insert(const GraphIteratorSet &other) {
        update();
        BOOST_FOREACH (const Value &item, other.values()) {
            insert(item);
        }
    }
    
    template<class SrcIterator>
    void insert(const SrcIterator &begin, const SrcIterator &end) {
        update();
        for (SrcIterator i = begin; i != end; ++i)
            insertUnique(*i);
    }

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

    Value popFront() {
        update();
        ASSERT_forbid(isEmpty());
        Value retval = items_[0];
        items_.erase(items_.begin());
        return retval;
    }
    
    void clear() {
        items_.clear();
        needsUpdate_ = false;
    }
    
    // Queries
public:
    bool exists(const Value &item) const {
        update();
        typename std::vector<Value>::iterator lb = std::lower_bound(items_.begin(), items_.end(), item, sortById);
        return lb != items_.end() && (*lb)->id() == item->id();
    }

    bool isEmpty() const {
        return items_.empty();
    }
    bool empty() const { return isEmpty(); } // undocumented compatibility

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

    // Internal stuff
private:
    static bool sortById(const Value &a, const Value &b) {
        return a->id() < b->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]));
    }
    
    void insertUnique(const Value &item) {
        typename std::vector<Value>::iterator lb = std::lower_bound(items_.begin(), items_.end(), item, sortById);
        if (lb == items_.end() || (*lb)->id() != item->id())
            items_.insert(lb, item);
    }
};

} // namespace
} // namespace

#endif