rangetree: support for building on freebsd-10
[blender.git] / extern / rangetree / range_tree.hh
1 /* This program is free software; you can redistribute it and/or
2    modify it under the terms of the GNU General Public License as
3    published by the Free Software Foundation; either version 2 of the
4    License, or (at your option) any later version.
5
6    This program is distributed in the hope that it will be useful, but
7    WITHOUT ANY WARRANTY; without even the implied warranty of
8    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
9    General Public License for more details.
10
11    You should have received a copy of the GNU General Public License
12    along with this program; if not, write to the Free Software
13    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
14    02110-1301, USA.
15 */
16
17 #include <cassert>
18 #include <climits>
19 #include <iostream>
20 #include <set>
21
22 #ifndef RANGE_TREE_DEBUG_PRINT_FUNCTION
23 #    define RANGE_TREE_DEBUG_PRINT_FUNCTION 0
24 #endif
25
26 template <typename T>
27 struct RangeTree {
28         struct Range {
29                 Range(T min_, T max_)
30                         : min(min_), max(max_), single(min_ == max_) {
31                         assert(min_ <= max_);
32                 }
33
34                 Range(T t)
35                         : min(t), max(t), single(true)
36                 {}
37
38                 Range& operator=(const Range& v) {
39                         *this = v;
40                         return *this;
41                 }
42
43                 bool operator<(const Range& v) const {
44                         return max < v.min;
45                 }
46
47                 const T min;
48                 const T max;
49                 const bool single;
50         };
51
52         typedef std::set<Range> Tree;
53         typedef typename Tree::iterator TreeIter;
54         typedef typename Tree::reverse_iterator TreeIterReverse;
55         typedef typename Tree::const_iterator TreeIterConst;
56
57         /* Initialize with a single range from 'min' to 'max', inclusive. */
58         RangeTree(T min, T max) {
59                 tree.insert(Range(min, max));
60         }
61
62         /* Initialize with a single range from 0 to 'max', inclusive. */
63         RangeTree(T max) {
64                 tree.insert(Range(0, max));
65         }
66
67         RangeTree(const RangeTree<T>& src) {
68                 tree = src.tree;
69         }
70
71         /* Remove 't' from the associated range in the tree. Precondition:
72            a range including 't' must exist in the tree. */
73         void take(T t) {
74                 #if RANGE_TREE_DEBUG_PRINT_FUNCTION
75                 std::cout << __func__ << "(" << t << ")\n";
76                 #endif
77
78                 /* Find the range that includes 't' and its neighbors */
79                 TreeIter iter = tree.find(Range(t));
80                 assert(iter != tree.end());
81                 Range cur = *iter;
82                 TreeIter prev = iter;
83                 TreeIter next = iter;
84                 --prev;
85                 ++next;
86
87                 /* Remove the original range (note that this does not
88                    invalidate the prev/next iterators) */
89                 tree.erase(iter);
90
91                 /* Construct two new ranges that together cover the original
92                    range, except for 't' */
93                 if (t > cur.min)
94                         tree.insert(Range(cur.min, t - 1));
95                 if (t + 1 <= cur.max)
96                         tree.insert(Range(t + 1, cur.max));
97         }
98
99         /* Take the first element out of the first range in the
100            tree. Precondition: tree must not be empty. */
101         T take_any() {
102                 #if RANGE_TREE_DEBUG_PRINT_FUNCTION
103                 std::cout << __func__ << "()\n";
104                 #endif
105
106                 /* Find the first element */
107                 TreeIter iter = tree.begin();
108                 assert(iter != tree.end());
109                 T first = iter->min;
110
111                 /* Take the first element */
112                 take(first);
113                 return first;
114         }
115
116         /* Return 't' to the tree, either expanding/merging existing
117            ranges or adding a range to cover it. Precondition: 't' cannot
118            be in an existing range. */
119         void release(T t) {
120                 #if RANGE_TREE_DEBUG_PRINT_FUNCTION
121                 std::cout << __func__ << "(" << t << ")\n";
122                 #endif
123
124                 /* TODO: these cases should be simplified/unified */
125
126                 TreeIter right = tree.upper_bound(t);
127                 if (right != tree.end()) {
128                         TreeIter left = right;
129                         if (left != tree.begin())
130                                 --left;
131
132                         if (left == right) {
133                                 /* 't' lies before any existing ranges */
134                                 if (t + 1 == left->min) {
135                                         /* 't' lies directly before the first range,
136                                            resize and replace that range */
137                                         const Range r(t, left->max);
138                                         tree.erase(left);
139                                         tree.insert(r);
140                                 }
141                                 else {
142                                         /* There's a gap between 't' and the first range,
143                                            add a new range */
144                                         tree.insert(Range(t));
145                                 }
146                         }
147                         else if ((left->max + 1 == t) &&
148                                 (t + 1 == right->min)) {
149                                 /* 't' fills a hole. Remove left and right, and insert a
150                                    new range that covers both. */
151                                 const Range r(left->min, right->max);
152                                 tree.erase(left);
153                                 tree.erase(right);
154                                 tree.insert(r);
155                         }
156                         else if (left->max + 1 == t) {
157                                 /* 't' lies directly after 'left' range, resize and
158                                    replace that range */
159                                 const Range r(left->min, t);
160                                 tree.erase(left);
161                                 tree.insert(r);
162                         }
163                         else if (t + 1 == right->min) {
164                                 /* 't' lies directly before 'right' range, resize and
165                                    replace that range */
166                                 const Range r(t, right->max);
167                                 tree.erase(right);
168                                 tree.insert(r);
169                         }
170                         else {
171                                 /* There's a gap between 't' and both adjacent ranges,
172                                    add a new range */
173                                 tree.insert(Range(t));
174                         }
175                 }
176                 else {
177                         /* 't' lies after any existing ranges */
178                         right = tree.end();
179                         right--;
180                         if (right->max + 1 == t) {
181                                 /* 't' lies directly after last range, resize and
182                                    replace that range */
183                                 const Range r(right->min, t);
184                                 tree.erase(right);
185                                 tree.insert(r);
186                         }
187                         else {
188                                 /* There's a gap between the last range and 't', add a
189                                    new range */
190                                 tree.insert(Range(t));
191                         }
192                 }
193         }
194
195         bool has(T t) const {
196                 TreeIterConst iter = tree.find(Range(t));
197                 return (iter != tree.end()) && (t <= iter->max);
198         }
199
200         bool has_range(T min, T max) const {
201                 TreeIterConst iter = tree.find(Range(min, max));
202                 return (iter != tree.end()) && (min == iter->min && max == iter->max);
203         }
204
205         bool empty() const {
206                 return tree.empty();
207         }
208
209         int size() const {
210                 return tree.size();
211         }
212
213         void print() const {
214                 std::cout << "RangeTree:\n";
215                 for (TreeIterConst iter = tree.begin(); iter != tree.end(); ++iter) {
216                         const Range& r = *iter;
217                         if (r.single)
218                                 std::cout << "  [" << r.min << "]\n";
219                         else
220                                 std::cout << "  [" << r.min << ", " << r.max << "]\n";
221                 }
222                 if (empty())
223                         std::cout << "  <empty>";
224                 std::cout << "\n";
225         }
226
227         unsigned int allocation_lower_bound() const {
228                 return tree.size() * sizeof(Range);
229         }
230
231 private:
232         Tree tree;
233 };