DenseIntegerSet.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.




// Set optimized to store densely-packed integers
#ifndef Sawyer_DenseIntegerSet_H
#define Sawyer_DenseIntegerSet_H

#include <Sawyer/Sawyer.h>
#include <Sawyer/Exception.h>
#include <Sawyer/Interval.h>
#include <boost/foreach.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/range/iterator_range.hpp>
#include <string>
#include <vector>

namespace Sawyer {
namespace Container {

template<typename T>
class DenseIntegerSet {
public:
    // Needed by iterators
    struct Member {
        Member *next, *prev;                            // circular list inc. head_; nulls imply member is not present in set
        Member(): next(NULL), prev(NULL) {}
        Member(Member *next, Member *prev): next(next), prev(prev) {}
    };

private:
    Interval<T> domain_;                                // domain of values that can be members of this set
    std::vector<Member> members_;                       // members forming a doubly-linked circular list inc. head_
    Member head_;                                       // head node of doubly-linked circular member list.
    size_t nMembers_;                                   // number of members contained in the set

public:
    typedef T Value;                                    
    //                                  Construction
public:
    DenseIntegerSet()
        : head_(&head_, &head_) {}

    explicit DenseIntegerSet(const Interval<Value> &domain)
        : domain_(domain), head_(&head_, &head_), nMembers_(0) {
        size_t n = (size_t)domain.greatest() - (size_t)domain.least() + 1;
        ASSERT_require(n != 0 || !domain.isEmpty());
        members_.resize(n);
    }

    DenseIntegerSet(Value least, Value greatest)
        : domain_(Interval<Value>::hull(least, greatest)), head_(&head_, &head_), nMembers_(0) {
        size_t n = (size_t)greatest - (size_t)least + 1;
        ASSERT_require(n != 0 || !domain_.isEmpty());
        members_.resize(n);
    }

    explicit DenseIntegerSet(Value n)
        : domain_(Interval<Value>::baseSize(0, n)), members_(n), head_(&head_, &head_), nMembers_(n) {
        if (0 == n)
            domain_ = Interval<Value>();
    }
    DenseIntegerSet(const DenseIntegerSet &other)
        : domain_(other.domain_), head_(&head_, &head_), nMembers_(0) {
        size_t n = (size_t)domain_.greatest() - (size_t)domain_.least() + 1;
        ASSERT_require(n != 0 || !domain_.isEmpty());
        members_.resize(n);
        BOOST_FOREACH (Value v, other.values())
            insert(v);
    }

    DenseIntegerSet& operator=(const DenseIntegerSet &other) {
        DenseIntegerSet tmp(domain());
        BOOST_FOREACH (Value v, other.values())
            tmp.insert(v);
        std::swap(domain_, tmp.domain_);
        std::swap(members_, tmp.members_);
        std::swap(nMembers_, tmp.nMembers_);

        // heads require some fixups because the prev/next pointers of the list and the heads point to the address of the head
        // in their original object, not the new object.
        std::swap(head_, tmp.head_);
        if (head_.next == &tmp.head_) {
            head_.next = head_.prev = &head_;
        } else {
            head_.prev->next = &head_;
            head_.next->prev = &head_;
        }

        // Fix up tmp's list too for completeness, although the only thing we do is delete it.
        if (tmp.head_.next == &head_) {
            tmp.head_.next = tmp.head_.prev = &tmp.head_;
        } else {
            tmp.head_.prev->next = &tmp.head_;
            tmp.head_.next->prev = &tmp.head_;
        }
        
        return *this;
    }
        
    //                                  Iterators
public:
    class ConstIterator: public std::iterator<std::bidirectional_iterator_tag, const Value> {
        friend class DenseIntegerSet;
        const DenseIntegerSet *set_;
        const Member *member_;
        mutable Value value_;                           // so we can return a const ref

        ConstIterator(const DenseIntegerSet *s, const Member *m)
            : set_(s), member_(m) {}
        
    public:
        bool operator==(const ConstIterator &other) const {
            return set_ == other.set_ && member_ == other.member_;
        }

        bool operator!=(const ConstIterator &other) const {
            return set_ != other.set_ || member_ != other.member_;
        }

        bool operator<(const ConstIterator &other) const {
            if (set_ != other.set_)
                return set_ < other.set_;
            return member_ < other.member_;
        }

        ConstIterator& operator++() {
            member_ = member_->next;
            return *this;
        }
        ConstIterator operator++(int) {
            ConstIterator retval = *this;
            ++*this;
            return retval;
        }
        ConstIterator& operator--() {
            member_ = member_->prev;
            return *this;
        }

        ConstIterator& operator--(int) {
            ConstIterator retval = *this;
            --*this;
            return retval;
        }
        const Value& operator*() const {
            value_ = set_->deref(*this);
            return value_;
        }
    };

    boost::iterator_range<ConstIterator> values() const {
        return boost::iterator_range<ConstIterator>(ConstIterator(this, head_.next), ConstIterator(this, &head_));
    }

    //                                  Predicates and queries
public:
    bool isEmpty() const {
        return head_.next == &head_;
    }

    size_t size() const {
        return nMembers_;
    }

    Interval<Value> domain() const {
        return domain_;
    }

    bool isStorable(Value v) const {
        return domain().isContaining(v);
    }

    bool exists(const Value &value) const {
        if (isEmpty() || !isStorable(value))
            return false;
        const Member &m = members_[value - domain_.least()];
        return head_.next == &m || m.prev != NULL;
    }

    template<class SawyerContainer>
    bool existsAny(const SawyerContainer &other) const {
        BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values()) {
            if (exists(otherValue))
                return true;
        }
        return false;
    }

    template<class SawyerContainer>
    bool existsAll(const SawyerContainer &other) const {
        BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values()) {
            if (!exists(otherValue))
                return false;
        }
        return true;
    }

    template<class SawyerContainer>
    bool operator==(const SawyerContainer &other) const {
        return size() == other.size() && existsAll(other);
    }

    template<class SawyerContainer>
    bool operator!=(const SawyerContainer &other) const {
        return size() != other.size() || !existsAll(other);
    }

    //                                  Modifiers
public:
    void clear() {
        Member *next = NULL;
        for (Member *m = head_.next; m != &head_; m = next) {
            next = m->next;
            m->prev = m->next = NULL;
        }
        head_.next = head_.prev = &head_;
        nMembers_ = 0;
    }

    bool insert(Value value) {
        if (!isStorable(value)) {
            std::string mesg;
            if (domain_.isEmpty()) {
                mesg = "cannot insert a value into a destination set with an empty domain";
            } else {
                mesg = "cannot insert " + boost::lexical_cast<std::string>(value) + " into a destination set whose domain is [" +
                       boost::lexical_cast<std::string>(domain_.least()) + ", " +
                       boost::lexical_cast<std::string>(domain_.greatest()) + "]";
            }
            throw Exception::DomainError(mesg);
        }
        Member &m = members_[value - domain_.least()];
        if (m.next)
            return false;                               // already a member
        m.prev = head_.prev;
        m.next = &head_;
        head_.prev->next = &m;
        head_.prev = &m;
        ++nMembers_;
        return true;
    }

    void insertAll() {
        if (!members_.empty()) {
            for (size_t i=0; i<members_.size(); ++i) {
                if (0 == i) {
                    members_[0].prev = &head_;
                    head_.next = &members_[0];
                } else {
                    members_[i].prev = &members_[i-1];
                }
                if (i+1 < members_.size()) {
                    members_[i].next = &members_[i+1];
                } else {
                    members_[i].next = &head_;
                    head_.prev = &members_[i];
                }
            }
            nMembers_ = members_.size();
        }
    }

    template<class SawyerContainer>
    void insertMany(const SawyerContainer &other) {
        BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values())
            insert(otherValue);
    }

    template<class SawyerContainer>
    DenseIntegerSet& operator|=(const SawyerContainer &other) {
        insertMany(other);
        return *this;
    }
    bool erase(Value value) {
        if (!exists(value))
            return false;
        Member &m = members_[value - domain_.least()];
        m.prev->next = m.next;
        m.next->prev = m.prev;
        m.next = m.prev = NULL;
        ASSERT_require(nMembers_ > 0);
        --nMembers_;
        return true;
    }

    ConstIterator erase(const ConstIterator &iter) {
        ASSERT_require2(iter.set_ != this, "iterator does not belong to this set");
        ASSERT_require2(iter.member_ != &head_, "cannot erase the end iterator");
        ASSERT_require2(iter.member_->next != NULL, "iterator no longer points to a member of this set");
        ConstIterator retval = iter;
        ++retval;
        Member &m = iter->member_;
        m.prev->next = m.next;
        m.next->prev = m.prev;
        m.next = m.prev = NULL;
        ASSERT_require(nMembers_ > 0);
        --nMembers_;
        return retval;
    }
    template<class SawyerContainer>
    void eraseMany(const SawyerContainer &other) {
        BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values())
            erase(otherValue);
    }

    template<class SawyerContainer>
    DenseIntegerSet& operator-=(const SawyerContainer &other) {
        eraseMany(other);
        return *this;
    }
    template<class SawyerContainer>
    void intersect(const SawyerContainer &other) {
        DenseIntegerSet tmp(*this);
        clear();
        BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values()) {
            if (tmp.exists(otherValue))
                insert(otherValue);
        }
    }

    template<class SawyerContainer>
    DenseIntegerSet& operator&=(const SawyerContainer &other) {
        intersect(other);
        return *this;
    }
    //                                  Set-theoretic operations
public:
    template<class SawyerContainer>
    DenseIntegerSet operator&(const SawyerContainer &other) const {
        DenseIntegerSet retval = *this;
        retval &= other;
        return retval;
    }

    template<class SawyerContainer>
    DenseIntegerSet operator|(const SawyerContainer &other) const {
        DenseIntegerSet retval = *this;
        retval |= other;
        return retval;
    }

    template<class SawyerContainer>
    DenseIntegerSet operator-(const SawyerContainer &other) const {
        DenseIntegerSet retval = *this;
        retval -= other;
        return retval;
    }

    //                                  Internal stuff
public:
    // Dereference an iterator to get a value.
    Value deref(const ConstIterator &iter) const {
        const Member *m = iter.member_;
        ASSERT_require2(m != &head_, "dereferencing an end iterator");
        ASSERT_require2(m->next != NULL, "dereferencing erased member");
        return domain_.least() + (m - &members_[0]);
    }
};

} // namespace
} // namespace

#endif