tools/reorder/interval_map.h@6474c204b198
tools/reorder/interval_map.h
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
1 /* -*- Mode: C++ -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 #ifndef interval_map_h__
7 #define interval_map_h__
9 /*
11 A utility class that maps an interval to an object, allowing clients
12 to look up the object by a point within the interval.
14 */
16 // TODO:
17 // - removing intervals
18 // - container iterators
20 #include <fstream>
21 #include <assert.h>
23 template<class coord, class T>
24 class interval_map {
25 protected:
26 class const_iterator;
27 friend class const_iterator;
29 struct node {
30 T m_data;
31 coord m_min;
32 coord m_max;
33 node *m_before; // intervals before this one
34 node *m_within; // intervals within this one
35 node *m_after; // intervals after this one
36 int m_bal;
37 };
39 public:
40 /**
41 * A unidirectional const iterator that is used to enumerate the
42 * intervals that overlap a specific point.
43 */
44 class const_iterator {
45 protected:
46 const node *m_node;
47 const coord m_point;
49 friend class interval_map;
50 const_iterator(const node *n, const coord &point)
51 : m_node(n), m_point(point) {}
53 void advance();
55 public:
56 const_iterator() : m_node(0), m_point(0) {}
58 const_iterator(const const_iterator &iter)
59 : m_node(iter.m_node), m_point(iter.m_point) {}
61 const_iterator &
62 operator=(const const_iterator &iter) {
63 m_node = iter.m_node;
64 m_point = iter.m_point; }
66 const T &
67 operator*() const { return m_node->m_data; }
69 const T *
70 operator->() const { return &m_node->m_data; }
72 const_iterator &
73 operator++() { advance(); return *this; }
75 const_iterator
76 operator++(int) {
77 const_iterator temp(*this);
78 advance();
79 return temp; }
81 bool
82 operator==(const const_iterator &iter) const {
83 return m_node == iter.m_node; }
85 bool
86 operator!=(const const_iterator &iter) const {
87 return !iter.operator==(*this); }
88 };
90 interval_map() : m_root(0) {}
92 ~interval_map() { delete m_root; }
94 /**
95 * Insert aData for the interval [aMin, aMax]
96 */
97 void put(coord min, coord max, const T &data) {
98 put_into(&m_root, min, max, data);
99 #ifdef DEBUG
100 verify(m_root, 0);
101 #endif
102 }
105 /**
106 * Return an iterator that will enumerate the data for all intervals
107 * intersecting |aPoint|.
108 */
109 const_iterator get(coord point) const;
111 /**
112 * Return an iterator that marks the end-point of iteration.
113 */
114 const_iterator end() const {
115 return const_iterator(0, 0); }
117 protected:
118 void put_into(node **link, coord min, coord max, const T &data, bool *subsumed = 0);
120 void left_rotate(node **link, node *node);
121 void right_rotate(node **link, node *node);
122 #ifdef DEBUG
123 void verify(node *node, int depth);
124 #endif
125 node *m_root;
126 };
128 template<class coord, class T>
129 void
130 interval_map<coord, T>::put_into(node **root, coord min, coord max, const T &data, bool *subsumed)
131 {
132 assert(min < max);
133 node *interval = *root;
135 if (interval) {
136 bool before = min < interval->m_min;
137 bool after = max > interval->m_max;
139 if (!before || !after) {
140 // The interval we're adding does not completely subsume
141 // the |interval|. So we've got one of these situations:
142 //
143 // |======| |======| |======|
144 // |------| |--| |------|
145 //
146 // where |==| is the existing interval, and |--| is the
147 // new interval we're inserting. If there's left or right
148 // slop, then we ``split'' the new interval in half:
149 //
150 // |======| |======|
151 // |--|---| |---|--|
152 //
153 // and insert it both in the ``within'' and ``before'' (or
154 // ``after'') subtrees.
155 //
156 if (before) {
157 if (max > interval->m_min) {
158 put_into(&interval->m_within, interval->m_min, max, data);
159 max = interval->m_min;
160 }
162 bool was_subsumed = true;
163 put_into(&interval->m_before, min, max, data, &was_subsumed);
165 if (! was_subsumed) {
166 if (interval->m_bal < 0) {
167 if (interval->m_before->m_bal > 0)
168 left_rotate(&interval->m_before, interval->m_before);
170 right_rotate(root, interval);
171 }
172 else
173 --interval->m_bal;
175 if (subsumed)
176 *subsumed = (interval->m_bal == 0);
177 }
179 return;
180 }
182 if (after) {
183 if (min < interval->m_max) {
184 put_into(&interval->m_within, min, interval->m_max, data);
185 min = interval->m_max;
186 }
188 bool was_subsumed = true;
189 put_into(&interval->m_after, min, max, data, &was_subsumed);
191 if (! was_subsumed) {
192 if (interval->m_bal > 0) {
193 if (interval->m_after->m_bal < 0)
194 right_rotate(&interval->m_after, interval->m_after);
196 left_rotate(root, interval);
197 }
198 else
199 ++interval->m_bal;
201 if (subsumed)
202 *subsumed = (interval->m_bal == 0);
203 }
205 return;
206 }
208 put_into(&interval->m_within, min, max, data);
209 return;
210 }
212 // If we get here, the interval we're adding completely
213 // subsumes |interval|. We'll go ahead and insert a new
214 // interval immediately above |interval|, with |interval| as
215 // the new interval's |m_within|.
216 }
218 if (subsumed)
219 *subsumed = false;
221 node *n = new node();
222 n->m_data = data;
223 n->m_before = n->m_after = 0;
224 n->m_min = min;
225 n->m_max = max;
226 n->m_within = interval;
227 n->m_bal = 0;
228 *root = n;
229 }
231 /*
232 * (*link) (*link)
233 * | == left rotate ==> |
234 * (x) (y)
235 * / \ / \
236 * a (y) <== right rotate == (x) c
237 * / \ / \
238 * b c a b
239 */
240 template<class coord, class T>
241 void
242 interval_map<coord, T>::left_rotate(node **link, node *x)
243 {
244 node *y = x->m_after;
245 x->m_after = y->m_before;
246 *link = y;
247 y->m_before = x;
248 --x->m_bal;
249 --y->m_bal;
250 }
252 template<class coord, class T>
253 void
254 interval_map<coord, T>::right_rotate(node **link, node *y)
255 {
256 node *x = y->m_before;
257 y->m_before = x->m_after;
258 *link = x;
259 x->m_after = y;
260 ++y->m_bal;
261 ++x->m_bal;
262 }
264 template<class coord, class T>
265 interval_map<coord, T>::const_iterator
266 interval_map<coord, T>::get(coord point) const
267 {
268 node *interval = m_root;
270 while (interval) {
271 if (point < interval->m_min)
272 interval = interval->m_before;
273 else if (point > interval->m_max)
274 interval = interval->m_after;
275 else
276 break;
277 }
279 return const_iterator(interval, point);
280 }
283 template<class coord, class T>
284 void
285 interval_map<coord, T>::const_iterator::advance()
286 {
287 assert(m_node);
289 m_node = m_node->m_within;
291 while (m_node) {
292 if (m_point < m_node->m_min)
293 m_node = m_node->m_before;
294 else if (m_point > m_node->m_max)
295 m_node = m_node->m_after;
296 else
297 break;
298 }
299 }
301 #ifdef DEBUG
302 template<class coord, class T>
303 void
304 interval_map<coord, T>::verify(node<coord, T> *node, int depth)
305 {
306 if (node->m_after)
307 verify(node->m_after, depth + 1);
309 for (int i = 0; i < depth; ++i)
310 cout << " ";
312 hex(cout);
313 cout << node << "(";
314 dec(cout);
315 cout << node->m_bal << ")";
316 hex(cout);
317 cout << "[" << node->m_min << "," << node->m_max << "]";
318 cout << "@" << node->m_data;
319 cout << endl;
321 if (node->m_before)
322 verify(node->m_before, depth + 1);
323 }
324 #endif // DEBUG
326 #endif // interval_map_h__
