1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tools/reorder/interval_map.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,326 @@
1.4 +/* -*- Mode: C++ -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#ifndef interval_map_h__
1.10 +#define interval_map_h__
1.11 +
1.12 +/*
1.13 +
1.14 + A utility class that maps an interval to an object, allowing clients
1.15 + to look up the object by a point within the interval.
1.16 +
1.17 + */
1.18 +
1.19 +// TODO:
1.20 +// - removing intervals
1.21 +// - container iterators
1.22 +
1.23 +#include <fstream>
1.24 +#include <assert.h>
1.25 +
1.26 +template<class coord, class T>
1.27 +class interval_map {
1.28 +protected:
1.29 + class const_iterator;
1.30 + friend class const_iterator;
1.31 +
1.32 + struct node {
1.33 + T m_data;
1.34 + coord m_min;
1.35 + coord m_max;
1.36 + node *m_before; // intervals before this one
1.37 + node *m_within; // intervals within this one
1.38 + node *m_after; // intervals after this one
1.39 + int m_bal;
1.40 + };
1.41 +
1.42 +public:
1.43 + /**
1.44 + * A unidirectional const iterator that is used to enumerate the
1.45 + * intervals that overlap a specific point.
1.46 + */
1.47 + class const_iterator {
1.48 + protected:
1.49 + const node *m_node;
1.50 + const coord m_point;
1.51 +
1.52 + friend class interval_map;
1.53 + const_iterator(const node *n, const coord &point)
1.54 + : m_node(n), m_point(point) {}
1.55 +
1.56 + void advance();
1.57 +
1.58 + public:
1.59 + const_iterator() : m_node(0), m_point(0) {}
1.60 +
1.61 + const_iterator(const const_iterator &iter)
1.62 + : m_node(iter.m_node), m_point(iter.m_point) {}
1.63 +
1.64 + const_iterator &
1.65 + operator=(const const_iterator &iter) {
1.66 + m_node = iter.m_node;
1.67 + m_point = iter.m_point; }
1.68 +
1.69 + const T &
1.70 + operator*() const { return m_node->m_data; }
1.71 +
1.72 + const T *
1.73 + operator->() const { return &m_node->m_data; }
1.74 +
1.75 + const_iterator &
1.76 + operator++() { advance(); return *this; }
1.77 +
1.78 + const_iterator
1.79 + operator++(int) {
1.80 + const_iterator temp(*this);
1.81 + advance();
1.82 + return temp; }
1.83 +
1.84 + bool
1.85 + operator==(const const_iterator &iter) const {
1.86 + return m_node == iter.m_node; }
1.87 +
1.88 + bool
1.89 + operator!=(const const_iterator &iter) const {
1.90 + return !iter.operator==(*this); }
1.91 + };
1.92 +
1.93 + interval_map() : m_root(0) {}
1.94 +
1.95 + ~interval_map() { delete m_root; }
1.96 +
1.97 + /**
1.98 + * Insert aData for the interval [aMin, aMax]
1.99 + */
1.100 + void put(coord min, coord max, const T &data) {
1.101 + put_into(&m_root, min, max, data);
1.102 +#ifdef DEBUG
1.103 + verify(m_root, 0);
1.104 +#endif
1.105 + }
1.106 +
1.107 +
1.108 + /**
1.109 + * Return an iterator that will enumerate the data for all intervals
1.110 + * intersecting |aPoint|.
1.111 + */
1.112 + const_iterator get(coord point) const;
1.113 +
1.114 + /**
1.115 + * Return an iterator that marks the end-point of iteration.
1.116 + */
1.117 + const_iterator end() const {
1.118 + return const_iterator(0, 0); }
1.119 +
1.120 +protected:
1.121 + void put_into(node **link, coord min, coord max, const T &data, bool *subsumed = 0);
1.122 +
1.123 + void left_rotate(node **link, node *node);
1.124 + void right_rotate(node **link, node *node);
1.125 +#ifdef DEBUG
1.126 + void verify(node *node, int depth);
1.127 +#endif
1.128 + node *m_root;
1.129 +};
1.130 +
1.131 +template<class coord, class T>
1.132 +void
1.133 +interval_map<coord, T>::put_into(node **root, coord min, coord max, const T &data, bool *subsumed)
1.134 +{
1.135 + assert(min < max);
1.136 + node *interval = *root;
1.137 +
1.138 + if (interval) {
1.139 + bool before = min < interval->m_min;
1.140 + bool after = max > interval->m_max;
1.141 +
1.142 + if (!before || !after) {
1.143 + // The interval we're adding does not completely subsume
1.144 + // the |interval|. So we've got one of these situations:
1.145 + //
1.146 + // |======| |======| |======|
1.147 + // |------| |--| |------|
1.148 + //
1.149 + // where |==| is the existing interval, and |--| is the
1.150 + // new interval we're inserting. If there's left or right
1.151 + // slop, then we ``split'' the new interval in half:
1.152 + //
1.153 + // |======| |======|
1.154 + // |--|---| |---|--|
1.155 + //
1.156 + // and insert it both in the ``within'' and ``before'' (or
1.157 + // ``after'') subtrees.
1.158 + //
1.159 + if (before) {
1.160 + if (max > interval->m_min) {
1.161 + put_into(&interval->m_within, interval->m_min, max, data);
1.162 + max = interval->m_min;
1.163 + }
1.164 +
1.165 + bool was_subsumed = true;
1.166 + put_into(&interval->m_before, min, max, data, &was_subsumed);
1.167 +
1.168 + if (! was_subsumed) {
1.169 + if (interval->m_bal < 0) {
1.170 + if (interval->m_before->m_bal > 0)
1.171 + left_rotate(&interval->m_before, interval->m_before);
1.172 +
1.173 + right_rotate(root, interval);
1.174 + }
1.175 + else
1.176 + --interval->m_bal;
1.177 +
1.178 + if (subsumed)
1.179 + *subsumed = (interval->m_bal == 0);
1.180 + }
1.181 +
1.182 + return;
1.183 + }
1.184 +
1.185 + if (after) {
1.186 + if (min < interval->m_max) {
1.187 + put_into(&interval->m_within, min, interval->m_max, data);
1.188 + min = interval->m_max;
1.189 + }
1.190 +
1.191 + bool was_subsumed = true;
1.192 + put_into(&interval->m_after, min, max, data, &was_subsumed);
1.193 +
1.194 + if (! was_subsumed) {
1.195 + if (interval->m_bal > 0) {
1.196 + if (interval->m_after->m_bal < 0)
1.197 + right_rotate(&interval->m_after, interval->m_after);
1.198 +
1.199 + left_rotate(root, interval);
1.200 + }
1.201 + else
1.202 + ++interval->m_bal;
1.203 +
1.204 + if (subsumed)
1.205 + *subsumed = (interval->m_bal == 0);
1.206 + }
1.207 +
1.208 + return;
1.209 + }
1.210 +
1.211 + put_into(&interval->m_within, min, max, data);
1.212 + return;
1.213 + }
1.214 +
1.215 + // If we get here, the interval we're adding completely
1.216 + // subsumes |interval|. We'll go ahead and insert a new
1.217 + // interval immediately above |interval|, with |interval| as
1.218 + // the new interval's |m_within|.
1.219 + }
1.220 +
1.221 + if (subsumed)
1.222 + *subsumed = false;
1.223 +
1.224 + node *n = new node();
1.225 + n->m_data = data;
1.226 + n->m_before = n->m_after = 0;
1.227 + n->m_min = min;
1.228 + n->m_max = max;
1.229 + n->m_within = interval;
1.230 + n->m_bal = 0;
1.231 + *root = n;
1.232 +}
1.233 +
1.234 +/*
1.235 + * (*link) (*link)
1.236 + * | == left rotate ==> |
1.237 + * (x) (y)
1.238 + * / \ / \
1.239 + * a (y) <== right rotate == (x) c
1.240 + * / \ / \
1.241 + * b c a b
1.242 + */
1.243 +template<class coord, class T>
1.244 +void
1.245 +interval_map<coord, T>::left_rotate(node **link, node *x)
1.246 +{
1.247 + node *y = x->m_after;
1.248 + x->m_after = y->m_before;
1.249 + *link = y;
1.250 + y->m_before = x;
1.251 + --x->m_bal;
1.252 + --y->m_bal;
1.253 +}
1.254 +
1.255 +template<class coord, class T>
1.256 +void
1.257 +interval_map<coord, T>::right_rotate(node **link, node *y)
1.258 +{
1.259 + node *x = y->m_before;
1.260 + y->m_before = x->m_after;
1.261 + *link = x;
1.262 + x->m_after = y;
1.263 + ++y->m_bal;
1.264 + ++x->m_bal;
1.265 +}
1.266 +
1.267 +template<class coord, class T>
1.268 +interval_map<coord, T>::const_iterator
1.269 +interval_map<coord, T>::get(coord point) const
1.270 +{
1.271 + node *interval = m_root;
1.272 +
1.273 + while (interval) {
1.274 + if (point < interval->m_min)
1.275 + interval = interval->m_before;
1.276 + else if (point > interval->m_max)
1.277 + interval = interval->m_after;
1.278 + else
1.279 + break;
1.280 + }
1.281 +
1.282 + return const_iterator(interval, point);
1.283 +}
1.284 +
1.285 +
1.286 +template<class coord, class T>
1.287 +void
1.288 +interval_map<coord, T>::const_iterator::advance()
1.289 +{
1.290 + assert(m_node);
1.291 +
1.292 + m_node = m_node->m_within;
1.293 +
1.294 + while (m_node) {
1.295 + if (m_point < m_node->m_min)
1.296 + m_node = m_node->m_before;
1.297 + else if (m_point > m_node->m_max)
1.298 + m_node = m_node->m_after;
1.299 + else
1.300 + break;
1.301 + }
1.302 +}
1.303 +
1.304 +#ifdef DEBUG
1.305 +template<class coord, class T>
1.306 +void
1.307 +interval_map<coord, T>::verify(node<coord, T> *node, int depth)
1.308 +{
1.309 + if (node->m_after)
1.310 + verify(node->m_after, depth + 1);
1.311 +
1.312 + for (int i = 0; i < depth; ++i)
1.313 + cout << " ";
1.314 +
1.315 + hex(cout);
1.316 + cout << node << "(";
1.317 + dec(cout);
1.318 + cout << node->m_bal << ")";
1.319 + hex(cout);
1.320 + cout << "[" << node->m_min << "," << node->m_max << "]";
1.321 + cout << "@" << node->m_data;
1.322 + cout << endl;
1.323 +
1.324 + if (node->m_before)
1.325 + verify(node->m_before, depth + 1);
1.326 +}
1.327 +#endif // DEBUG
1.328 +
1.329 +#endif // interval_map_h__
