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