consecutive_set.h

/*
 * Copyright 2008 Martin Christiansson (martin_ch at users.sourceforge.net)
 *
 * This library is free software; you can redistribute it and/or modify it under the
 * terms of the GNU Lesser General Public License as published by the Free Software
 * Foundation; either version 3 of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along with this
 * program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef __CONSECUTIVE_SET__H__
#define __CONSECUTIVE_SET__H__

#include <iostream>
#include <set>
#include <assert.h>


template<typename T>
class consecutive_set {
private:

    class subset_t {
    private:
        T start;
        T end;
    public:
        subset_t(T _start, T _end);

        bool operator<(const subset_t& cmp) const;
        T size() const;
        const T& get_start() const;
        const T& get_end() const;
        void set_start(T _start);
        void set_end(T _end);
        void clear();
    };

    typedef typename std::set<subset_t>::iterator iter_t;
    typedef typename std::set<subset_t>::const_iterator const_iter_t;
    std::set<subset_t> subsets;
    T num_elements;

    iter_t prev_iter(iter_t iter) const;
    iter_t next_iter(iter_t iter) const;
    void subset_erase(iter_t subset);
    void subset_insert(const subset_t& subset);
    void subset_insert_at(iter_t pos, const subset_t& subset);
    void subset_insert_at_end(const subset_t& subset);
    void subset_change(iter_t subset, T start, T end);
    void subset_symdiff(iter_t subset, T start, T end);

public:
    consecutive_set();

    consecutive_set(T start, T end);

    void swap(consecutive_set& set);

    std::ostream& print(std::ostream& os) const;

    bool is_consistent() const;

    consecutive_set sum(const consecutive_set& set) const;

    void sum_update(const consecutive_set& set);

    consecutive_set intersection(const consecutive_set& set) const;

    void intersection_update(const consecutive_set& set);

    consecutive_set diff(const consecutive_set& set) const;

    void diff_update(const consecutive_set& set);

    consecutive_set symdiff(const consecutive_set& set) const;

    void symdiff_update(const consecutive_set& set);

    bool is_subset(const consecutive_set& set) const;

    bool is_superset(const consecutive_set& set) const;

    void add(T value);

    void remove(T value);

    bool contains(T value) const;

    class empty_set_exception : public std::exception {
    public:
        virtual const char *what() const throw() {
            return "Set is empty";
        }
    };

    T pop();

    T pop(const consecutive_set& constraints);

    consecutive_set pop(T num_values);

    consecutive_set pop(T num_values, const consecutive_set& constraints);

    T pop_back();

    T pop_back(const consecutive_set& constraints);

    consecutive_set pop_back(T num_values);

    consecutive_set pop_back(T num_values, const consecutive_set& constraints);

    void clear();

    T size() const;

    bool operator<=(const consecutive_set& set) const;
    bool operator>=(const consecutive_set& set) const;
    consecutive_set& operator|=(const consecutive_set& set);
    consecutive_set& operator|=(T value);
    consecutive_set operator|(const consecutive_set& set) const;
    consecutive_set& operator&=(const consecutive_set& set);
    consecutive_set operator&(const consecutive_set& set) const;
    consecutive_set& operator-=(const consecutive_set& set);
    consecutive_set& operator-=(T value);
    consecutive_set operator-(const consecutive_set& set) const;
    consecutive_set& operator^=(const consecutive_set& set);
    consecutive_set operator^(const consecutive_set& set) const;
};

template<typename T>
consecutive_set<T>::subset_t::subset_t(T _start, T _end) : start(_start), end(_end) {
    assert(end >= start);
}

template<typename T>
inline bool consecutive_set<T>::subset_t::operator<(const subset_t& cmp) const {
    return start < cmp.start;
}

template<typename T>
inline T consecutive_set<T>::subset_t::size() const {
    return end - start;
}

template<typename T>
inline const T& consecutive_set<T>::subset_t::get_start() const {
    return start;
}

template<typename T>
inline const T& consecutive_set<T>::subset_t::get_end() const {
    return end;
}

template<typename T>
inline void consecutive_set<T>::subset_t::set_start(T _start) {
    start = _start;
}

template<typename T>
inline void consecutive_set<T>::subset_t::set_end(T _end) {
    end = _end;
}

template<typename T>
inline void consecutive_set<T>::subset_t::clear() {
    start = end = 0;
}

template<typename T>
inline typename consecutive_set<T>::iter_t consecutive_set<T>::prev_iter(iter_t iter) const {
    return --iter;
}

template<typename T>
inline typename consecutive_set<T>::iter_t consecutive_set<T>::next_iter(iter_t iter) const {
    return ++iter;
}

template<typename T>
void consecutive_set<T>::subset_erase(iter_t subset) {
    num_elements -= subset->size();
    subsets.erase(subset);
}

template<typename T>
void consecutive_set<T>::subset_insert(const subset_t& subset) {
    num_elements += subset.size();
    subsets.insert(subset);
}

template<typename T>
void consecutive_set<T>::subset_insert_at(iter_t pos, const subset_t& subset) {
    num_elements += subset.size();
    subsets.insert(pos, subset);
}

template<typename T>
inline void consecutive_set<T>::subset_insert_at_end(const subset_t& subset) {
    subset_insert_at(subsets.end(), subset);
}

template<typename T>
void consecutive_set<T>::subset_change(iter_t subset, T start, T end) {
    subset_t new_subset(start, end);
    num_elements += new_subset.size() - subset->size();
    subsets.erase(subset++);
    subsets.insert(subset, new_subset);
}

template<typename T>
void consecutive_set<T>::subset_symdiff(iter_t subset, T start, T end) {
    subset_t first_new_subset(start < subset->get_start() ? start : subset->get_start(),
            start > subset->get_start() ? start : subset->get_start());
    subset_t second_new_subset(end < subset->get_end() ? end : subset->get_end(),
            end > subset->get_end() ? end : subset->get_end());
    num_elements += first_new_subset.size() + second_new_subset.size() - subset->size();
    subsets.erase(subset++);
    subsets.insert(subset, first_new_subset);
    subsets.insert(subset, second_new_subset);
}

template<typename T>
consecutive_set<T>::consecutive_set() : num_elements(0) {
}

template<typename T>
consecutive_set<T>::consecutive_set(T start, T end) : num_elements(0) {
    assert(start <= end);
    subset_insert(subset_t(start, end + 1));
}

template<typename T>
void consecutive_set<T>::swap(consecutive_set& set) {
    T tmp_num_elements = num_elements;
    num_elements = set.num_elements;
    set.num_elements = tmp_num_elements;
    subsets.swap(set.subsets);
}

template<typename T>
std::ostream& consecutive_set<T>::print(std::ostream& os) const {
    os << "Size:    " << num_elements << std::endl;
    os << "Subsets: ";
    iter_t iter(subsets.begin());
    const char* separator = "";
    while(iter != subsets.end()) {
        os << separator << "[" << iter->get_start();
        if(iter->get_start() != iter->get_end() - 1)
            os << "-" << iter->get_end() - 1;
        os << "]";
        separator = ", ";
        ++iter;
    }
    os << std::endl;
    return os;
}

template<typename T>
bool consecutive_set<T>::is_consistent() const {
     T element_count(0);
     T last_end = 0;
     iter_t iter = subsets.begin();
     while(iter != subsets.end()) {
         if(iter != subsets.begin() && last_end >= iter->get_start())
             return false;
         last_end = iter->get_end();
         if(iter->get_start() >= iter->get_end())
             return false;
         element_count += iter->size();
         ++iter;
     }
     if(element_count != size())
         return false;

     return true;
}

template<typename T>
consecutive_set<T> consecutive_set<T>::sum(const consecutive_set& set) const {
    consecutive_set res;
    if(&set == this) return (res = *this);
    iter_t self_iter(subsets.begin());
    iter_t set_iter(set.subsets.begin());
    subset_t remainder(0,0);
    while(self_iter != subsets.end() || set_iter != set.subsets.end()) {
        iter_t& iter =
            self_iter == subsets.end() ? set_iter :
            set_iter == set.subsets.end() ? self_iter :
            self_iter->get_start() < set_iter->get_start() ? self_iter : set_iter;
        if(remainder.size() > 0) {
            if(iter->get_start() <= remainder.get_end()) {
                // Overlapping entries
                if(iter->get_end() > remainder.get_end()) {
                    remainder.set_end(iter->get_end());
                }
                ++iter;
                continue;
            }
            res.subset_insert_at_end(remainder);
        }
        remainder = *iter;
        ++iter;
    };

    if(remainder.size())
        res.subset_insert_at_end(remainder);

    return res;
}

template<typename T>
void consecutive_set<T>::sum_update(const consecutive_set& set) {
    if(&set == this) return;
    iter_t set_iter(set.subsets.begin());
    while(set_iter != set.subsets.end()) {
        iter_t iter(subsets.upper_bound(*set_iter));
        if(iter != subsets.begin() && prev_iter(iter)->get_end() >= set_iter->get_start()) {
            // Subset should be concatenated to previous subset
            --iter;
        } else if(iter == subsets.end() || iter->get_start() > set_iter->get_end()) {
            // Disjoint sets.Insert subset and update size.
            subset_insert_at(iter, *set_iter);
            ++set_iter;
            continue;
        }
        // Concatenate overlapping subsets
        T start = iter->get_start() < set_iter->get_start() ? iter->get_start() : set_iter->get_start();
        T end = iter->get_end() > set_iter->get_end() ? iter->get_end() : set_iter->get_end();
        while(iter != subsets.end() && iter->get_start() <= end) {
            // Remove overlapping subset and update size
            if(iter->get_end() > end) {
                end = iter->get_end();
            }
            subset_erase(iter++);
        }
        subset_insert_at(iter, subset_t(start, end));
        ++set_iter;
    }
}

template<typename T>
consecutive_set<T> consecutive_set<T>::intersection(const consecutive_set& set) const {
     consecutive_set res;
     if(&set == this) return (res = *this);
     iter_t iter(subsets.begin());
     iter_t set_iter(set.subsets.begin());
     while(iter != subsets.end() && set_iter != set.subsets.end()) {
         if(iter->get_end() <= set_iter->get_start()) {
             // Disjoint subsets
             ++iter;
         } else if(set_iter->get_end() <= iter->get_start()) {
             // Disjoint subsets
             ++set_iter;
         } else {
             // Overlapping subsets
             T start = iter->get_start() > set_iter->get_start() ? iter->get_start() : set_iter->get_start();
             T end = iter->get_end() < set_iter->get_end() ? iter->get_end() : set_iter->get_end();
             res.subset_insert_at_end(subset_t(start, end));
             if(iter->get_end() <= set_iter->get_end()) {
                 ++iter;
             } else {
                 ++set_iter;
             }
         }
     }
     return res;
}

template<typename T>
void consecutive_set<T>::intersection_update(const consecutive_set& set) {
    if(&set == this) return;
    iter_t iter(subsets.begin());
    while(iter != subsets.end()) {
        iter_t set_iter(set.subsets.upper_bound(*iter));
        if(set_iter != set.subsets.begin() && prev_iter(set_iter)->get_end() > iter->get_start()) {
            // Subset overlaps previous subset
            --set_iter;
        } else if(set_iter == set.subsets.end() || set_iter->get_start() >= iter->get_end()) {
            // Disjoint sets.Remove.
            subset_erase(iter++);
            continue;
        }
        // Find intersection of overlapping subsets
        T start = iter->get_start();
        T end = iter->get_end();
        subset_erase(iter++);
        while(set_iter != set.subsets.end() && set_iter->get_start() < end) {
            subset_t new_subset(start >= set_iter->get_start() ? start : set_iter->get_start(),
                    end <= set_iter->get_end() ? end : set_iter->get_end());
            subset_insert_at(iter, new_subset);
            ++set_iter;
        }
    }
}

template<typename T>
consecutive_set<T> consecutive_set<T>::diff(const consecutive_set& set) const {
    consecutive_set res;
    if(&set == this) return res;
    iter_t iter(subsets.begin());
    while(iter != subsets.end()) {
        iter_t set_iter(set.subsets.upper_bound(*iter));
        if(set_iter != set.subsets.begin() && prev_iter(set_iter)->get_end() > iter->get_start()) {
            // Subset overlaps previous subset.
            --set_iter;
        } else if(set_iter == set.subsets.end() || set_iter->get_start() >= iter->get_end()) {
            // Disjoint sets. Add to res set.
            res.subset_insert_at_end(*iter);
            ++iter;
            continue;
        }
        // Add difference of ovelapping subsets to res set
        T start = iter->get_start() < set_iter->get_start() ? iter->get_start() : set_iter->get_end();
        T end = iter->get_end();
        while(set_iter != set.subsets.end() && set_iter->get_start() < end) {
            if(start < set_iter->get_start()) {
                res.subset_insert_at_end(subset_t(start, set_iter->get_start()));
                start = set_iter->get_end();
            }
            ++set_iter;
        }
        if(start < end) {
            res.subset_insert_at_end(subset_t(start, end));
        }
        ++iter;
    }
    return res;
}

template<typename T>
void consecutive_set<T>::diff_update(const consecutive_set& set) {
    if(&set == this) {
        clear();
        return;
    }
    iter_t set_iter(set.subsets.begin());
    while(set_iter != set.subsets.end()) {
        iter_t iter(subsets.upper_bound(*set_iter));
        if(iter != subsets.begin() && prev_iter(iter)->get_end() > set_iter->get_start()) {
            // Subset overlaps previous subset.
            --iter;
        } else if(iter == subsets.end() || iter->get_start() >= set_iter->get_end()) {
            // Disjoint sets.Ignore.
            ++set_iter;
            continue;
        }
        // Concatenate overlapping subsets
        // Find intersection of overlapping subsets
        while(iter != subsets.end() && iter->get_start() < set_iter->get_end()) {

            if(iter->get_start() < set_iter->get_start()) {
                if(iter->get_end() > set_iter->get_end()) {
                    subset_symdiff(iter++, set_iter->get_start(), set_iter->get_end());
                } else { // iter->get_end() <= set_iter->get_end())
                    subset_change(iter++, iter->get_start(), set_iter->get_start());
                }
            } else { // iter->get_start() >= set_iter->get_start())
                if(iter->get_end() > set_iter->get_end()) {
                    subset_change(iter++, set_iter->get_end(), iter->get_end());
                } else { // iter->get_end() <= set_iter->get_end()
                    subset_erase(iter++);
                }
            }
        }
        ++set_iter;
    }
}

template<typename T>
consecutive_set<T> consecutive_set<T>::symdiff(const consecutive_set& set) const {
     consecutive_set res;
     if(&set == this) return res;
     iter_t self_iter(subsets.begin());
     iter_t set_iter(set.subsets.begin());
     if(self_iter == subsets.end())
         return (res = set);
     if(set_iter == set.subsets.end())
         return (res = *this);

     subset_t remainder(0, 0);
     while(self_iter != subsets.end() || set_iter != set.subsets.end()) {
         iter_t& iter =
              self_iter == subsets.end() ? set_iter :
              set_iter == set.subsets.end() ? self_iter :
              self_iter->get_start() < set_iter->get_start() ? self_iter : set_iter;

         if(remainder.size() > 0) {
             if(remainder.get_start() == iter->get_start()) {
                 if(remainder.get_end() < iter->get_end()) {
                     remainder = subset_t(remainder.get_end(), iter->get_end());
                 } else if(remainder.get_end() == iter->get_end()) {
                     remainder.clear();
                 } else { // remainder.get_end() > iter->get_end()
                     remainder.set_start(iter->get_end());
                 }
             } else { // remainder.get_start() < iter->get_start()
                 assert(remainder.get_start() < iter->get_start());
                 if(remainder.get_end() < iter->get_start()) {
                     res.subset_insert_at_end(remainder);
                     remainder = *iter;
                 } else if(remainder.get_end() == iter->get_start()) {
                     remainder.set_end(iter->get_end());
                 } else { // remainder.get_end() > iter->get_start()
                     res.subset_insert_at_end(subset_t(remainder.get_start(), iter->get_start()));
                     remainder.set_start(iter->get_end() < remainder.get_end() ? iter->get_end() : remainder.get_end());
                     remainder.set_end(iter->get_end() > remainder.get_end() ? iter->get_end() : remainder.get_end());
                 }
             }
         } else{
             remainder = *iter;
         }

         ++iter;
     }

     if (remainder.size() > 0) {
         res.subset_insert_at_end(remainder);
     }

     return res;
}

template<typename T>
void consecutive_set<T>::symdiff_update(const consecutive_set& set) {
    if(&set == this) {
        clear();
        return;
    }
    iter_t set_iter(set.subsets.begin());
    while(set_iter != set.subsets.end()) {
        iter_t iter(subsets.upper_bound(*set_iter));
        if(iter != subsets.begin() && prev_iter(iter)->get_end() >= set_iter->get_start()) {
            // Subset overlaps previous subset
            --iter;
        } else if(iter == subsets.end() || iter->get_start() > set_iter->get_end()) {
            // Disjoint sets
            subset_insert_at(iter, *(set_iter++));
            continue;
        }
        // Overlapping sets
        subset_t remainder(*set_iter);
        while(iter != subsets.end() && iter->get_start() <= remainder.get_end()) {
            if(iter->get_start() < remainder.get_start()) {
                if(iter->get_end() == remainder.get_start()) {
                    remainder.set_start(iter->get_start());
                    subset_erase(iter++);
                } else if (iter->get_end() < remainder.get_end()) {
                    T iter_start = iter->get_start();
                    T iter_end = iter->get_end();
                    subset_change(iter++, iter_start, remainder.get_start());
                    remainder.set_start(iter_end);
                } else if(iter->get_end() == remainder.get_end()) {
                    subset_change(iter, iter->get_start(), remainder.get_start());
                    remainder.clear();
                    break;
                } else { // iter->get_end() > remainder.get_end()
                    subset_symdiff(iter, remainder.get_start(), remainder.get_end());
                    remainder.clear();
                    break;
                }
            } else if(iter->get_start() == remainder.get_start()) {
                if(iter->get_end() < remainder.get_end()) {
                    remainder.set_start(iter->get_end());
                    subset_erase(iter++);
                } else if(iter->get_end() == remainder.get_end()) {
                    subset_erase(iter);
                    remainder.clear();
                    break;
                } else { // iter->get_end() > remainder.get_end()
                    subset_change(iter, remainder.get_end(), iter->get_end());
                    remainder.clear();
                    break;
                }
            } else if(iter->get_start() < remainder.get_end()) {
                if(iter->get_end() < remainder.get_end()) {
                    T iter_end = iter->get_end();
                    subset_change(iter++, remainder.get_start(), iter->get_start());
                    remainder.set_start(iter_end);
                } else if(iter->get_end() == remainder.get_end()) {
                    subset_change(iter, remainder.get_start(), iter->get_start());
                    remainder.clear();
                    break;
                } else { // iter->get_end() > remainder.get_end()
                    subset_symdiff(iter, remainder.get_start(), remainder.get_end());
                    remainder.clear();
                    break;
                }
            } else if(iter->get_start() == remainder.get_end()) {
                    subset_change(iter, remainder.get_start(), iter->get_end());
                    remainder.clear();
                    break;
            }
        }
        if(remainder.size() > 0) {
            subset_insert_at(iter, remainder);
        }
        ++set_iter;
    }
}

template<typename T>
bool consecutive_set<T>::is_subset(const consecutive_set& set) const {
    iter_t iter(subsets.begin());
    while(iter != subsets.end()) {
        iter_t set_iter(set.subsets.upper_bound(*iter));
        if(set_iter != set.subsets.begin() && prev_iter(set_iter)->get_end() > iter->get_start()) {
            // Subset overlaps previous subset
            --set_iter;
        } else if(set_iter == set.subsets.end()) {
            return false;
        }
        if (iter->get_start() < set_iter->get_start() || iter->get_end() > set_iter->get_end()) {
            return false;
        }
        ++iter;
    }
    return true;
}

template<typename T>
bool consecutive_set<T>::is_superset(const consecutive_set& set) const {
    iter_t set_iter(set.subsets.begin());
    while(set_iter != set.subsets.end()) {
        iter_t iter(subsets.upper_bound(*set_iter));
        if(iter != subsets.begin() && prev_iter(iter)->get_end() > set_iter->get_start()) {
            // Subset overlaps previous subset
            --iter;
        } else if(iter == subsets.end()) {
            return false;
        }
        if(set_iter->get_start() < iter->get_start() || set_iter->get_end() > iter->get_end()) {
            return false;
        }
        ++set_iter;
    }
    return true;
}

template<typename T>
void consecutive_set<T>::add(T value) {
    iter_t iter(subsets.upper_bound(subset_t(value, value)));
    if(iter != subsets.begin() && prev_iter(iter)->get_end() >= value) {
        // Subset should be concatenated to previous subset
        --iter;
    } else if(iter == subsets.end() || iter->get_start() > (value + 1)) {
        // Disjoint sets.Insert subset and update size.
        subset_insert_at(iter, subset_t(value, value + 1));
        return;
    }
    T start = iter->get_start();
    T end = iter->get_end();
    if(value == end) {
        if(next_iter(iter) != subsets.end() && next_iter(iter)->get_start() == value + 1) {
            end = next_iter(iter)->get_end();
            subset_erase(next_iter(iter));
            subset_change(iter, start, end);
            return;
        }

        ++end;
        subset_change(iter, start, end);
        return;
    }
    if(value == (start - 1)) {
        subset_change(iter, start - 1, end);
        return;
    }
    assert(value >= iter->get_start() && value < iter->get_end());
}

template<typename T>
void consecutive_set<T>::remove(T value) {
    assert(subsets.size() > 0);
    iter_t iter(subsets.upper_bound(subset_t(value, value)));
    if(iter != subsets.begin() && prev_iter(iter)->get_end() > value) {
        // Value exists in previous subset
        --iter;
        if(value == iter->get_start()) {
            subset_change(iter, value + 1, iter->get_end());
        } else if(value == (iter->get_end() - 1)) {
            subset_change(iter, iter->get_start(), iter->get_end() - 1);
        } else {
            subset_symdiff(iter, value, value + 1);
        }
        return;
    }
    assert(0 && "Attempting to remove value that doesn't exist in set");
}

template<typename T>
bool consecutive_set<T>::contains(T value) const {
    iter_t iter(subsets.upper_bound(subset_t(value, value)));
    return iter != subsets.begin() && prev_iter(iter)->get_end() > value;
}

template<typename T>
T consecutive_set<T>::pop() {
    if(!num_elements) throw empty_set_exception();
    iter_t iter(subsets.begin());
    T value = iter->get_start();
    assert(iter->size() >= 1);
    if(iter->size() > 1) {
        T start = value + 1;
        T end = iter->get_end();
        subset_change(iter, start, end);
    } else {
        subset_erase(iter);
    }
    return value;
}

template<typename T>
T consecutive_set<T>::pop(const consecutive_set& constraints) {
    iter_t constraints_iter(constraints.subsets.begin());
    while(constraints_iter != constraints.subsets.end()) {
        iter_t iter(subsets.upper_bound(*constraints_iter));
        if(iter != subsets.begin() && prev_iter(iter)->get_end() > constraints_iter->get_start()) {
            // Constraints is overlapping previous subset
            --iter;
        } else if(iter == subsets.end() || iter->get_start() >= constraints_iter->get_end()) {
            // Disjoint sets
            ++constraints_iter;
            continue;
        }

        // Overlapping sets
        if(iter->get_start() < constraints_iter->get_start()) {
            T value = constraints_iter->get_start();
            if(iter->get_end() > (constraints_iter->get_start() + 1)) {
                subset_symdiff(iter, value, value + 1);
            } else if(iter->get_end() == (constraints_iter->get_start() + 1)) {
                subset_change(iter, iter->get_start(), value);
            }
            return value;
        } else { // iter->get_start() >= constraints->get_start()
            T value = iter->get_start();
            if(iter->size() > 1) {
                subset_change(iter, value + 1, iter->get_end());
            } else {
                subset_erase(iter);
            }
            return value;
        }
        assert(0);
    }
    throw empty_set_exception();
}

template<typename T>
consecutive_set<T> consecutive_set<T>::pop(T num_values) {
    consecutive_set res;
    iter_t iter(subsets.begin());
    while(num_values > 0 && iter != subsets.end()) {
        if(iter->size() > num_values) {
            res.subset_insert_at_end(subset_t(iter->get_start(), iter->get_start() + num_values));
            subset_change(iter, iter->get_start() + num_values, iter->get_end());
            break;
        } else if(iter->size() == num_values) {
            res.subset_insert_at_end(*iter);
            subset_erase(iter);
            break;
        } else { // iter->size() < num_values
            res.subset_insert_at_end(*iter);
            num_values -= iter->size();
            subset_erase(iter++);
        }
    }
    return res;
}

template<typename T>
consecutive_set<T> consecutive_set<T>::pop(T num_values, const consecutive_set& constraints) {
    consecutive_set res;
    iter_t constraints_iter(constraints.subsets.begin());
    while(num_values > 0 && constraints_iter != constraints.subsets.end()) {
        iter_t iter(subsets.upper_bound(*constraints_iter));
        if(iter != subsets.begin() && prev_iter(iter)->get_end() > constraints_iter->get_start()) {
            // Constraints is overlapping previous subset
            --iter;
        } else if(iter == subsets.end() || iter->get_start() >= constraints_iter->get_end()) {
            // Disjoint sets
            ++constraints_iter;
            continue;
        }

        while(num_values > 0 && iter!= subsets.end() && iter->get_start() < constraints_iter->get_end()) {
            // Overlapping sets
            subset_t values(iter->get_start() > constraints_iter->get_start() ? iter->get_start() : constraints_iter->get_start(),
                    iter->get_end() < constraints_iter->get_end() ? iter->get_end() : constraints_iter->get_end());
            if(values.size() > num_values) {
                values.set_end(values.get_start() + num_values);
            }
            num_values -= values.size();
            res.subset_insert_at_end(values);
            if(iter->get_start() < values.get_start()) {
                assert(iter->get_end() >= values.get_end());
                if(iter->get_end() > values.get_end()) {
                    subset_symdiff(iter++, values.get_start(), values.get_end());
                } else if(iter->get_end() == values.get_end()) {
                    subset_change(iter++, iter->get_start(), values.get_start());
                }
            } else { // iter->get_start() >= values.get_start()
                if(iter->get_end() > values.get_end()) {
                    subset_change(iter++, values.get_end(), iter->get_end());
                } else {
                    subset_erase(iter++);
                }
            }
        }
        ++constraints_iter;
    }
    return res;
}

template<typename T>
T consecutive_set<T>::pop_back() {
    if(!num_elements) throw empty_set_exception();
    iter_t iter(subsets.end());
    --iter;
    T value(iter->get_end() - 1);
    if(iter->size() == 1) {
        subset_erase(iter);
    } else {
        T start = iter->get_start();
        T end = value;
        subset_change(iter, start, end);
    }
    return value;
}

template<typename T>
T consecutive_set<T>::pop_back(const consecutive_set& constraints) {
    if(constraints.size() == 0)
        throw empty_set_exception();
    iter_t constraints_iter(constraints.subsets.end());
    do {
        --constraints_iter;
        iter_t iter(subsets.upper_bound(subset_t(constraints_iter->get_end() - 1, constraints_iter->get_end())));
        if(iter != subsets.begin() && prev_iter(iter)->get_end() > constraints_iter->get_start()) {
            // Constraints is overlapping previous subset
            --iter;
        } else if(iter == subsets.end() || iter->get_start() >= constraints_iter->get_end()) {
            // Disjoint sets
            if(constraints_iter != constraints.subsets.begin()) {
                continue;
            } else {
                break;
            }
        }

        // Overlapping sets
        assert(iter->size() >= 1);
        if(iter->get_end() <= constraints_iter->get_end()) {
            T value = iter->get_end() - 1;
            if(iter->size() > 1) {
                subset_change(iter, iter->get_start(), value);
            } else { // iter->size() == 1
                subset_erase(iter);
            }
            return value;
        } else { // iter->get_end() > constraints_iter->get_end()
            T value = constraints_iter->get_end() - 1;
            assert(iter->size() > 1);
            if(value > iter->get_start()) {
                subset_symdiff(iter, value, value + 1);
            } else { // value == iter->get_start()
                subset_change(iter, value + 1, iter->get_end());
            }
            return value;
        }
    } while(constraints_iter != constraints.subsets.begin());
    throw empty_set_exception();
}

template<typename T>
consecutive_set<T> consecutive_set<T>::pop_back(T num_values) {
    consecutive_set res;
    iter_t iter(subsets.end());
    while(num_values > 0 && subsets.begin() != subsets.end()) {
        iter_t iter(subsets.end());
        --iter;
        if(iter->size() > num_values) {
            res.subset_insert_at(subsets.begin(), subset_t(iter->get_end() - num_values, iter->get_end()));
            subset_change(iter, iter->get_start(), iter->get_end() - num_values);
            break;
        } else if(iter->size() == num_values) {
            res.subset_insert_at(subsets.begin(), *iter);
            subset_erase(iter);
            break;
        } else { // iter->size() < num_values
            res.subset_insert_at(subsets.begin(), *iter);
            num_values -= iter->size();
            subset_erase(iter);
        }
    }

    return res;
}

template<typename T>
consecutive_set<T> consecutive_set<T>::pop_back(T num_values, const consecutive_set& constraints) {
    consecutive_set res;
    if(num_values == 0 || constraints.size() == 0)
        return res;
    iter_t constraints_iter(constraints.subsets.end());
    do {
        --constraints_iter;
        iter_t iter(subsets.upper_bound(subset_t(constraints_iter->get_end() - 1, constraints_iter->get_end())));
        if(iter != subsets.begin() && prev_iter(iter)->get_end() > constraints_iter->get_start()) {
            // Constraints is overlapping previous subset
            --iter;
        } else if(iter == subsets.end() || iter->get_start() >= constraints_iter->get_end()) {
            // Disjoint sets
            if(constraints_iter != constraints.subsets.begin()) {
                continue;
            } else {
                break;
            }
        }

        do {
            // Overlapping sets
            assert(iter->size() >= 1);
            subset_t values(iter->get_start() > constraints_iter->get_start() ? iter->get_start() : constraints_iter->get_start(),
                    iter->get_end() < constraints_iter->get_end() ? iter->get_end() : constraints_iter->get_end());
            if(values.size() > num_values) {
                values.set_start(values.get_end() - num_values);
            }
            num_values -= values.size();
            res.subset_insert_at_end(values);
            if(iter->get_start() < values.get_start()) {
                assert(iter->get_end() >= values.get_end());
                if(iter->get_end() > values.get_end()) {
                    subset_symdiff(iter++, values.get_start(), values.get_end());
                    --iter;
                } else if(iter->get_end() == values.get_end()) {
                    subset_change(iter++, iter->get_start(), values.get_start());
                }
            } else { // iter->get_start() >= values.get_start()
                if(iter->get_end() > values.get_end()) {
                    subset_change(iter++, values.get_end(), iter->get_end());
                } else {
                    subset_erase(iter++);
                }
            }
            --iter;
        } while(num_values > 0 && iter != subsets.begin() && (--iter)->get_end() > constraints_iter->get_start());
    } while(num_values > 0 && constraints_iter != constraints.subsets.begin());

    return res;
}

template<typename T>
void consecutive_set<T>::clear() {
    subsets.clear();
    num_elements = 0;
}

template<typename T>
inline T consecutive_set<T>::size() const {
    return num_elements;
}

template<typename T>
inline bool consecutive_set<T>::operator<=(const consecutive_set& set) const {
    return is_subset(set);
}

template<typename T>
inline bool consecutive_set<T>::operator>=(const consecutive_set& set) const {
    return is_superset(set);
}

template<typename T>
inline consecutive_set<T>& consecutive_set<T>::operator|=(const consecutive_set& set) {
    sum_update(set);
    return *this;
}

template<typename T>
inline consecutive_set<T>& consecutive_set<T>::operator|=(T value) {
    add(value);
    return *this;
}

template<typename T>
inline consecutive_set<T> consecutive_set<T>::operator|(const consecutive_set& set) const {
    return sum(set);
}

template<typename T>
inline consecutive_set<T>& consecutive_set<T>::operator&=(const consecutive_set& set) {
    intersection_update(set);
    return *this;
}

template<typename T>
inline consecutive_set<T> consecutive_set<T>::operator&(const consecutive_set& set) const {
    return intersection(set);
}

template<typename T>
inline consecutive_set<T>& consecutive_set<T>::operator-=(const consecutive_set& set) {
    diff_update(set);
    return *this;
}

template<typename T>
inline consecutive_set<T>& consecutive_set<T>::operator-=(T value) {
    remove(value);
    return *this;
}

template<typename T>
inline consecutive_set<T> consecutive_set<T>::operator-(const consecutive_set& set) const {
    return diff(set);
}

template<typename T>
inline consecutive_set<T>& consecutive_set<T>::operator^=(const consecutive_set& set) {
    symdiff_update(set);
    return *this;
}

template<typename T>
inline consecutive_set<T> consecutive_set<T>::operator^(const consecutive_set& set) const {
    return symdiff(set);
}

template<typename T>
inline std::ostream& operator<<(std::ostream& os, const consecutive_set<T>& set) {
    return set.print(os);
}

#endif // __CONSECUTIVE_SET__H__

---