#include <stdio.h>
#include <boost/intrusive/set.hpp>

namespace bi = boost::intrusive;

// The "myrange" type represents a simple range of integers from _start until
// _end-1 (i.e., not including _end). Our intention below is to hold a set of
// such non-intersecting myranges.
class myrange {
public:
    myrange(uintptr_t start, uintptr_t end) : _start(start), _end(end) {}
    int _start;
    int _end;
    boost::intrusive::set_member_hook<> _myrange_list_hook;
};
// Because the ranges we'll hold in the set are guaranteed to be non-intersecting,
// we can simply sort them by the start field
class myrange_compare {
public:
    bool operator ()(const myrange& a, const myrange& b) const { return a._start < b._start; }
};
typedef boost::intrusive::set<myrange,
                              bi::compare<myrange_compare>,
                              bi::member_hook<myrange,
                                              bi::set_member_hook<>,
                                              &myrange::_myrange_list_hook>,
                              bi::optimize_size<true>
                              > myrange_set;


int main() {
    myrange_set ranges;
    ranges.insert(*new myrange(2, 5));
    ranges.insert(*new myrange(5, 8));
    ranges.insert(*new myrange(8, 10));
    ranges.insert(*new myrange(10, 13));

    // In this sorted list of ranges, we want to find all the ranges which
    // intersect another one - say [5, 10).
    // We can do this with equal_range using the "comp" comparison function:
    // a range is comp-smaller than a second if it is entirely before the
    // second range:
    auto comp = [] (const myrange& x, const myrange& y) {
    	return x._end <= y._start;
    };
    myrange r(5, 10);
    auto range = ranges.equal_range(r, comp);

    printf("equal_range: (%d, %d) - (%d, %d)\n", range.first->_start, range.first->_end, range.second->_start, range.second->_end);

    auto lb = ranges.lower_bound(r, comp);
    printf("lower_bound: (%d, %d)\n", lb->_start, lb->_end);
    auto ub = ranges.upper_bound(r, comp);
    printf("upper_bound: (%d, %d)\n", ub->_start, ub->_end);
    return 0;
}