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