Import the RangeTree library into extern
[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                 bool operator<(const Range& v) const {
39                         return max < v.min;
40                 }
41
42                 const T min;
43                 const T max;
44                 const bool single;
45         };
46
47         typedef std::set<Range> Tree;
48         typedef typename Tree::iterator TreeIter;
49         typedef typename Tree::reverse_iterator TreeIterReverse;
50         typedef typename Tree::const_iterator TreeIterConst;
51
52         /* Initialize with a single range from 'min' to 'max', inclusive. */
53         RangeTree(T min, T max) {
54                 tree.insert(Range(min, max));
55         }
56
57         /* Initialize with a single range from 0 to 'max', inclusive. */
58         RangeTree(T max) {
59                 tree.insert(Range(0, max));
60         }
61
62         RangeTree(const RangeTree<T>& src) {
63                 tree = src.tree;
64         }
65
66         /* Remove 't' from the associated range in the tree. Precondition:
67            a range including 't' must exist in the tree. */
68         void take(T t) {
69                 #if RANGE_TREE_DEBUG_PRINT_FUNCTION
70                 std::cout << __func__ << "(" << t << ")\n";
71                 #endif
72
73                 /* Find the range that includes 't' and its neighbors */
74                 TreeIter iter = tree.find(Range(t));
75                 assert(iter != tree.end());
76                 Range cur = *iter;
77                 TreeIter prev = iter;
78                 TreeIter next = iter;
79                 --prev;
80                 ++next;
81
82                 /* Remove the original range (note that this does not
83                    invalidate the prev/next iterators) */
84                 tree.erase(iter);
85
86                 /* Construct two new ranges that together cover the original
87                    range, except for 't' */
88                 if (t > cur.min)
89                         tree.insert(Range(cur.min, t - 1));
90                 if (t + 1 <= cur.max)
91                         tree.insert(Range(t + 1, cur.max));
92         }
93
94         /* Take the first element out of the first range in the
95            tree. Precondition: tree must not be empty. */
96         T take_any() {
97                 #if RANGE_TREE_DEBUG_PRINT_FUNCTION
98                 std::cout << __func__ << "()\n";
99                 #endif
100
101                 /* Find the first element */
102                 TreeIter iter = tree.begin();
103                 assert(iter != tree.end());
104                 T first = iter->min;
105
106                 /* Take the first element */
107                 take(first);
108                 return first;
109         }
110
111         /* Return 't' to the tree, either expanding/merging existing
112            ranges or adding a range to cover it. Precondition: 't' cannot
113            be in an existing range. */
114         void release(T t) {
115                 #if RANGE_TREE_DEBUG_PRINT_FUNCTION
116                 std::cout << __func__ << "(" << t << ")\n";
117                 #endif
118
119                 /* TODO: these cases should be simplified/unified */
120
121                 TreeIter right = tree.upper_bound(t);
122                 if (right != tree.end()) {
123                         TreeIter left = right;
124                         if (left != tree.begin())
125                                 --left;
126
127                         if (left == right) {
128                                 /* 't' lies before any existing ranges */
129                                 if (t + 1 == left->min) {
130                                         /* 't' lies directly before the first range,
131                                            resize and replace that range */
132                                         const Range r(t, left->max);
133                                         tree.erase(left);
134                                         tree.insert(r);
135                                 }
136                                 else {
137                                         /* There's a gap between 't' and the first range,
138                                            add a new range */
139                                         tree.insert(Range(t));
140                                 }
141                         }
142                         else if ((left->max + 1 == t) &&
143                                 (t + 1 == right->min)) {
144                                 /* 't' fills a hole. Remove left and right, and insert a
145                                    new range that covers both. */
146                                 const Range r(left->min, right->max);
147                                 tree.erase(left);
148                                 tree.erase(right);
149                                 tree.insert(r);
150                         }
151                         else if (left->max + 1 == t) {
152                                 /* 't' lies directly after 'left' range, resize and
153                                    replace that range */
154                                 const Range r(left->min, t);
155                                 tree.erase(left);
156                                 tree.insert(r);
157                         }
158                         else if (t + 1 == right->min) {
159                                 /* 't' lies directly before 'right' range, resize and
160                                    replace that range */
161                                 const Range r(t, right->max);
162                                 tree.erase(right);
163                                 tree.insert(r);
164                         }
165                         else {
166                                 /* There's a gap between 't' and both adjacent ranges,
167                                    add a new range */
168                                 tree.insert(Range(t));
169                         }
170                 }
171                 else {
172                         /* 't' lies after any existing ranges */
173                         right = tree.end();
174                         right--;
175                         if (right->max + 1 == t) {
176                                 /* 't' lies directly after last range, resize and
177                                    replace that range */
178                                 const Range r(right->min, t);
179                                 tree.erase(right);
180                                 tree.insert(r);
181                         }
182                         else {
183                                 /* There's a gap between the last range and 't', add a
184                                    new range */
185                                 tree.insert(Range(t));
186                         }
187                 }
188         }
189
190         bool has(T t) const {
191                 TreeIterConst iter = tree.find(Range(t));
192                 return (iter != tree.end()) && (t <= iter->max);
193         }
194
195         bool has_range(T min, T max) const {
196                 TreeIterConst iter = tree.find(Range(min, max));
197                 return (iter != tree.end()) && (min == iter->min && max == iter->max);
198         }
199
200         bool empty() const {
201                 return tree.empty();
202         }
203
204         int size() const {
205                 return tree.size();
206         }
207
208         void print() const {
209                 std::cout << "RangeTree:\n";
210                 for (TreeIterConst iter = tree.begin(); iter != tree.end(); ++iter) {
211                         const Range& r = *iter;
212                         if (r.single)
213                                 std::cout << "  [" << r.min << "]\n";
214                         else
215                                 std::cout << "  [" << r.min << ", " << r.max << "]\n";
216                 }
217                 if (empty())
218                         std::cout << "  <empty>";
219                 std::cout << "\n";
220         }
221
222         unsigned int allocation_lower_bound() const {
223                 return tree.size() * sizeof(Range);
224         }
225
226 private:
227         Tree tree;
228 };