Set.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_Container_Set_H
#define Sawyer_Container_Set_H
 
#include <Sawyer/Interval.h>
#include <Sawyer/Sawyer.h>
 
// Work around a bug in boost::serialization for 1.74.0
#include <boost/version.hpp>
#if BOOST_VERSION == 107400
     #include <boost/serialization/library_version_type.hpp>
#endif
 
#include <boost/foreach.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/serialization/serialization.hpp>        // needed by <boost/serialization/set.hpp> in boost 1.58 - 1.60
#include <boost/serialization/access.hpp>
#include <boost/serialization/nvp.hpp>
#include <boost/serialization/set.hpp>
#include <vector>
 
namespace Sawyer {
namespace Container {
 
template<typename T, class C = std::less<T>, class A = std::allocator<T> >
class Set {
    typedef std::set<T, C, A> InternalSet;
    InternalSet set_;
public:
    typedef T Value;                                    
    typedef C Comparator;                               
    typedef A Allocator;                                
    typedef typename InternalSet::const_iterator ConstIterator;  
    //                                  Serialization
private:
    friend class boost::serialization::access;
 
    template<class S>
    void serialize(S &s, const unsigned /*version*/) {
        s & BOOST_SERIALIZATION_NVP(set_);
    }
    
    //                                  Construction
public:
    explicit Set(const Comparator &comparator = Comparator(), const Allocator &allocator = Allocator())
        : set_(comparator, allocator) {}
 
    Set(const Value &value) /*implicit*/ {
        set_.insert(value);
    }
 
    template<class InputIterator>
    Set(InputIterator begin, InputIterator end,
        const Comparator &comparator = Comparator(), const Allocator &allocator = Allocator())
        : set_(begin, end, comparator, allocator) {}
 
    template<class InputIterator>
    explicit Set(const boost::iterator_range<InputIterator> &range,
                 const Comparator &/*comparator*/ = Comparator(), const Allocator &/*allocator*/ = Allocator())
        : set_(range.begin(), range.end()) {}
    Set(const Set &other)
        : set_(other.set_) {}
 
    Set& operator=(const Set &other) {
        set_ = other.set_;
        return *this;
    }
    
    //                                  Iterators
public:
    boost::iterator_range<ConstIterator> values() const {
        return boost::iterator_range<ConstIterator>(set_.begin(), set_.end());
    }
 
    //                                  Predicates and queries
public:
    bool isEmpty() const {
        return set_.empty();
    }
 
    bool exists(const Value &value) const {
        return 1 == set_.count(value);
    }
 
    bool existsAny(const Set &other) const {
        BOOST_FOREACH (const Value &otherValue, other.values()) {
            if (exists(otherValue))
                return true;
        }
        return false;
    }
 
    bool existsAll(const Set &other) const {
        BOOST_FOREACH (const Value &otherValue, other.values()) {
            if (!exists(otherValue))
                return false;
        }
        return true;
    }
    
    size_t size() const {
        return set_.size();
    }
 
    Value least() const {
        ASSERT_forbid(isEmpty());
        return *set_.begin();
    }
 
    Value greatest() const {
        ASSERT_forbid(isEmpty());
        ConstIterator i = set_.end();
        --i;
        return *i;
    }
 
    Interval<Value> hull() const {
        if (isEmpty())
            return Interval<Value>();
        return Interval<Value>::hull(least(), greatest());
    }
 
    bool operator==(const Set &other) const {
        return set_.size() == other.set_.size() && std::equal(set_.begin(), set_.end(), other.set_.begin());
    }
 
    bool operator!=(const Set &other) const {
        return (set_.size() != other.set_.size() ||
                std::mismatch(set_.begin(), set_.end(), other.set_.begin()).first != set_.end());
    }
    
    //                                  Mutators
public:
    bool insert(const Value &value) {
        return set_.insert(value).second;
    }
 
    bool insert(const Set &values) {
        bool isInserted = false;
        BOOST_FOREACH (const Value &value, values.values()) {
            if (set_.insert(value).second)
                isInserted = true;
        }
        return isInserted;
    }
 
    bool erase(const Value &value) {
        return 1 == set_.erase(value);
    }
 
    bool erase(const Set &values) {
        bool isErased = false;
        BOOST_FOREACH (const Value &value, values.values()) {
            if (1 == set_.erase(value))
                isErased = true;
        }
        return isErased;
    }
    
    void clear() {
        set_.clear();
    }
 
    Set& operator&=(const Set &other) {
        std::vector<Value> toErase;
        toErase.reserve(set_.size());
        BOOST_FOREACH (const Value &value, set_) {
            if (!other.exists(value))
                toErase.push_back(value);
        }
        BOOST_FOREACH (const Value &value, toErase)
            set_.erase(value);
        return *this;
    }
 
    Set& operator|=(const Set &other) {
        BOOST_FOREACH (const Value &v, other.values())
            set_.insert(v);
        return *this;
    }
 
    Set& operator-=(const Set &other) {
        std::vector<Value> toErase;
        toErase.reserve(set_.size());
        BOOST_FOREACH (const Value &value, set_) {
            if (other.exists(value))
                toErase.push_back(value);
        }
        BOOST_FOREACH (const Value &value, toErase)
            set_.erase(value);
        return *this;
    }
 
        
    //                                  Set-theoretic operations
public:
    Set operator&(const Set &other) const {
        Set retval = *this;
        retval &= other;
        return retval;
    }
 
    Set operator|(const Set &other) const {
        Set retval = *this;
        retval |= other;
        return retval;
    }
 
    Set operator-(const Set &other) const {
        Set retval = *this;
        retval -= other;
        return retval;
    }
};
 
} // namespace
} // namespace
 
#endif