tools/reorder/interval_map.h

   1 /* -*- Mode: C++ -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is ``interval_map''
  16  *
  17  * The Initial Developer of the Original Code is Netscape
  18  * Communications Corp.  Portions created by the Initial Developer are
  19  * Copyright (C) 2001 the Initial Developer. All Rights Reserved.
  20  *
  21  * Contributor(s):
  22  *   Chris Waterson <waterson@netscape.com>
  23  *
  24  * Alternatively, the contents of this file may be used under the terms of
  25  * either the GNU General Public License Version 2 or later (the "GPL"), or
  26  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27  * in which case the provisions of the GPL or the LGPL are applicable instead
  28  * of those above. If you wish to allow use of your version of this file only
  29  * under the terms of either the GPL or the LGPL, and not to allow others to
  30  * use your version of this file under the terms of the MPL, indicate your
  31  * decision by deleting the provisions above and replace them with the notice
  32  * and other provisions required by the GPL or the LGPL. If you do not delete
  33  * the provisions above, a recipient may use your version of this file under
  34  * the terms of any one of the MPL, the GPL or the LGPL.
  35  *
  36  * ***** END LICENSE BLOCK ***** */
  37
  38 #ifndef interval_map_h__
  39 #define interval_map_h__
  40
  41 /*
  42
  43   A utility class that maps an interval to an object, allowing clients
  44   to look up the object by a point within the interval.
  45
  46  */
  47
  48 // TODO:
  49 //   - removing intervals
  50 //   - container iterators
  51
  52 #include <fstream>
  53 #include <assert.h>
  54
  55 template<class coord, class T>
  56 class interval_map {
  57 protected:
  58     class const_iterator;
  59     friend class const_iterator;
  60
  61     struct node {
  62         T      m_data;
  63         coord  m_min;
  64         coord  m_max;
  65         node  *m_before; // intervals before this one
  66         node  *m_within; // intervals within this one
  67         node  *m_after;  // intervals after this one
  68         int    m_bal;
  69     };
  70
  71 public:
  72     /**
  73      * A unidirectional const iterator that is used to enumerate the
  74      * intervals that overlap a specific point.
  75      */
  76     class const_iterator {
  77     protected:
  78         const node  *m_node;
  79         const coord  m_point;
  80
  81         friend class interval_map;
  82         const_iterator(const node *n, const coord &point)
  83             : m_node(n), m_point(point) {}
  84
  85         void advance();
  86
  87     public:
  88         const_iterator() : m_node(0), m_point(0) {}
  89
  90         const_iterator(const const_iterator &iter)
  91             : m_node(iter.m_node), m_point(iter.m_point) {}
  92
  93         const_iterator &
  94         operator=(const const_iterator &iter) {
  95             m_node = iter.m_node;
  96             m_point = iter.m_point; }
  97
  98         const T &
  99         operator*() const { return m_node->m_data; }
 100
 101         const T *
 102         operator->() const { return &m_node->m_data; }
 103
 104         const_iterator &
 105         operator++() { advance(); return *this; }
 106
 107         const_iterator
 108         operator++(int) {
 109             const_iterator temp(*this);
 110             advance();
 111             return temp; }
 112
 113         bool
 114         operator==(const const_iterator &iter) const {
 115             return m_node == iter.m_node; }
 116
 117         bool
 118         operator!=(const const_iterator &iter) const {
 119             return !iter.operator==(*this); }
 120     };
 121
 122     interval_map() : m_root(0) {}
 123
 124     ~interval_map() { delete m_root; }
 125
 126     /**
 127      * Insert aData for the interval [aMin, aMax]
 128      */
 129     void put(coord min, coord max, const T &data) {
 130         put_into(&m_root, min, max, data);
 131 #ifdef DEBUG
 132         verify(m_root, 0);
 133 #endif
 134     }
 135
 136
 137     /**
 138      * Return an iterator that will enumerate the data for all intervals
 139      * intersecting |aPoint|.
 140      */
 141     const_iterator get(coord point) const;
 142
 143     /**
 144      * Return an iterator that marks the end-point of iteration.
 145      */
 146     const_iterator end() const {
 147         return const_iterator(0, 0); }
 148
 149 protected:
 150     void put_into(node **link, coord min, coord max, const T &data, bool *subsumed = 0);
 151
 152     void left_rotate(node **link, node *node);
 153     void right_rotate(node **link, node *node);
 154 #ifdef DEBUG
 155     void verify(node *node, int depth);
 156 #endif
 157     node *m_root;
 158 };
 159
 160 template<class coord, class T>
 161 void
 162 interval_map<coord, T>::put_into(node **root, coord min, coord max, const T &data, bool *subsumed)
 163 {
 164     assert(min < max);
 165     node *interval = *root;
 166
 167     if (interval) {
 168         bool before = min < interval->m_min;
 169         bool after = max > interval->m_max;
 170
 171         if (!before || !after) {
 172             // The interval we're adding does not completely subsume
 173             // the |interval|. So we've got one of these situations:
 174             //
 175             //      |======|   |======|   |======|
 176             //   |------|        |--|        |------|
 177             //
 178             // where |==| is the existing interval, and |--| is the
 179             // new interval we're inserting. If there's left or right
 180             // slop, then we ``split'' the new interval in half:
 181             //
 182             //      |======|              |======|
 183             //   |--|---|                    |---|--|
 184             //
 185             // and insert it both in the ``within'' and ``before'' (or
 186             // ``after'') subtrees.
 187             //
 188             if (before) {
 189                 if (max > interval->m_min) {
 190                     put_into(&interval->m_within, interval->m_min, max, data);
 191                     max = interval->m_min;
 192                 }
 193
 194                 bool was_subsumed = true;
 195                 put_into(&interval->m_before, min, max, data, &was_subsumed);
 196
 197                 if (! was_subsumed) {
 198                     if (interval->m_bal < 0) {
 199                         if (interval->m_before->m_bal > 0)
 200                             left_rotate(&interval->m_before, interval->m_before);
 201
 202                         right_rotate(root, interval);
 203                     }
 204                     else
 205                         --interval->m_bal;
 206
 207                     if (subsumed)
 208                         *subsumed = (interval->m_bal == 0);
 209                 }
 210
 211                 return;
 212             }
 213
 214             if (after) {
 215                 if (min < interval->m_max) {
 216                     put_into(&interval->m_within, min, interval->m_max, data);
 217                     min = interval->m_max;
 218                 }
 219
 220                 bool was_subsumed = true;
 221                 put_into(&interval->m_after, min, max, data, &was_subsumed);
 222
 223                 if (! was_subsumed) {
 224                     if (interval->m_bal > 0) {
 225                         if (interval->m_after->m_bal < 0)
 226                             right_rotate(&interval->m_after, interval->m_after);
 227
 228                         left_rotate(root, interval);
 229                     }
 230                     else
 231                         ++interval->m_bal;
 232
 233                     if (subsumed)
 234                         *subsumed = (interval->m_bal == 0);
 235                 }
 236
 237                 return;
 238             }
 239
 240             put_into(&interval->m_within, min, max, data);
 241             return;
 242         }
 243
 244         // If we get here, the interval we're adding completely
 245         // subsumes |interval|. We'll go ahead and insert a new
 246         // interval immediately above |interval|, with |interval| as
 247         // the new interval's |m_within|.
 248     }
 249
 250     if (subsumed)
 251         *subsumed = false;
 252
 253     node *n = new node();
 254     n->m_data   = data;
 255     n->m_before = n->m_after = 0;
 256     n->m_min    = min;
 257     n->m_max    = max;
 258     n->m_within = interval;
 259     n->m_bal    = 0;
 260     *root = n;
 261 }
 262
 263 /*
 264  *    (*link)                               (*link)
 265  *       |         == left rotate ==>          |
 266  *      (x)                                   (y)
 267  *     /   \                                 /   \
 268  *    a    (y)    <== right rotate ==      (x)    c
 269  *        /   \                           /   \
 270  *       b     c                         a     b
 271  */
 272 template<class coord, class T>
 273 void
 274 interval_map<coord, T>::left_rotate(node **link, node *x)
 275 {
 276     node *y = x->m_after;
 277     x->m_after = y->m_before;
 278     *link = y;
 279     y->m_before = x;
 280     --x->m_bal;
 281     --y->m_bal;
 282 }
 283
 284 template<class coord, class T>
 285 void
 286 interval_map<coord, T>::right_rotate(node **link, node *y)
 287 {
 288     node *x = y->m_before;
 289     y->m_before = x->m_after;
 290     *link = x;
 291     x->m_after = y;
 292     ++y->m_bal;
 293     ++x->m_bal;
 294 }
 295
 296 template<class coord, class T>
 297 interval_map<coord, T>::const_iterator
 298 interval_map<coord, T>::get(coord point) const
 299 {
 300     node *interval = m_root;
 301
 302     while (interval) {
 303         if (point < interval->m_min)
 304             interval = interval->m_before;
 305         else if (point > interval->m_max)
 306             interval = interval->m_after;
 307         else
 308             break;
 309     }
 310
 311     return const_iterator(interval, point);
 312 }
 313
 314
 315 template<class coord, class T>
 316 void
 317 interval_map<coord, T>::const_iterator::advance()
 318 {
 319     assert(m_node);
 320
 321     m_node = m_node->m_within;
 322
 323     while (m_node) {
 324         if (m_point < m_node->m_min)
 325             m_node = m_node->m_before;
 326         else if (m_point > m_node->m_max)
 327             m_node = m_node->m_after;
 328         else
 329             break;
 330     }
 331 }
 332
 333 #ifdef DEBUG
 334 template<class coord, class T>
 335 void
 336 interval_map<coord, T>::verify(node<coord, T> *node, int depth)
 337 {
 338     if (node->m_after)
 339         verify(node->m_after, depth + 1);
 340
 341     for (int i = 0; i < depth; ++i)
 342         cout << "  ";
 343
 344     hex(cout);
 345     cout << node << "(";
 346     dec(cout);
 347     cout << node->m_bal << ")";
 348     hex(cout);
 349     cout << "[" << node->m_min << "," << node->m_max << "]";
 350     cout << "@" << node->m_data;
 351     cout << endl;
 352
 353     if (node->m_before)
 354         verify(node->m_before, depth + 1);
 355 }
 356 #endif // DEBUG
 357
 358 #endif // interval_map_h__