1 | #include <stdio.h>
|
---|
2 | #include <boost/intrusive/set.hpp>
|
---|
3 |
|
---|
4 | namespace bi = boost::intrusive;
|
---|
5 |
|
---|
6 | // The "myrange" type represents a simple range of integers from _start until
|
---|
7 | // _end-1 (i.e., not including _end). Our intention below is to hold a set of
|
---|
8 | // such non-intersecting myranges.
|
---|
9 | class myrange {
|
---|
10 | public:
|
---|
11 | myrange(uintptr_t start, uintptr_t end) : _start(start), _end(end) {}
|
---|
12 | int _start;
|
---|
13 | int _end;
|
---|
14 | boost::intrusive::set_member_hook<> _myrange_list_hook;
|
---|
15 | };
|
---|
16 | // Because the ranges we'll hold in the set are guaranteed to be non-intersecting,
|
---|
17 | // we can simply sort them by the start field
|
---|
18 | class myrange_compare {
|
---|
19 | public:
|
---|
20 | bool operator ()(const myrange& a, const myrange& b) const { return a._start < b._start; }
|
---|
21 | };
|
---|
22 | typedef boost::intrusive::set<myrange,
|
---|
23 | bi::compare<myrange_compare>,
|
---|
24 | bi::member_hook<myrange,
|
---|
25 | bi::set_member_hook<>,
|
---|
26 | &myrange::_myrange_list_hook>,
|
---|
27 | bi::optimize_size<true>
|
---|
28 | > myrange_set;
|
---|
29 |
|
---|
30 |
|
---|
31 | int main() {
|
---|
32 | myrange_set ranges;
|
---|
33 | ranges.insert(*new myrange(2, 5));
|
---|
34 | ranges.insert(*new myrange(5, 8));
|
---|
35 | ranges.insert(*new myrange(8, 10));
|
---|
36 | ranges.insert(*new myrange(10, 13));
|
---|
37 |
|
---|
38 | // In this sorted list of ranges, we want to find all the ranges which
|
---|
39 | // intersect another one - say [5, 10).
|
---|
40 | // We can do this with equal_range using the "comp" comparison function:
|
---|
41 | // a range is comp-smaller than a second if it is entirely before the
|
---|
42 | // second range:
|
---|
43 | auto comp = [] (const myrange& x, const myrange& y) {
|
---|
44 | return x._end <= y._start;
|
---|
45 | };
|
---|
46 | myrange r(5, 10);
|
---|
47 | auto range = ranges.equal_range(r, comp);
|
---|
48 |
|
---|
49 | printf("equal_range: (%d, %d) - (%d, %d)\n", range.first->_start, range.first->_end, range.second->_start, range.second->_end);
|
---|
50 |
|
---|
51 | auto lb = ranges.lower_bound(r, comp);
|
---|
52 | printf("lower_bound: (%d, %d)\n", lb->_start, lb->_end);
|
---|
53 | auto ub = ranges.upper_bound(r, comp);
|
---|
54 | printf("upper_bound: (%d, %d)\n", ub->_start, ub->_end);
|
---|
55 | return 0;
|
---|
56 | }
|
---|