michael@0: /* -*- Mode: C++ -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef interval_map_h__
michael@0: #define interval_map_h__
michael@0: 
michael@0: /*
michael@0: 
michael@0:   A utility class that maps an interval to an object, allowing clients
michael@0:   to look up the object by a point within the interval.
michael@0: 
michael@0:  */
michael@0: 
michael@0: // TODO:
michael@0: //   - removing intervals
michael@0: //   - container iterators
michael@0: 
michael@0: #include <fstream>
michael@0: #include <assert.h>
michael@0: 
michael@0: template<class coord, class T>
michael@0: class interval_map {
michael@0: protected:
michael@0:     class const_iterator;
michael@0:     friend class const_iterator;
michael@0: 
michael@0:     struct node {
michael@0:         T      m_data;
michael@0:         coord  m_min;
michael@0:         coord  m_max;
michael@0:         node  *m_before; // intervals before this one
michael@0:         node  *m_within; // intervals within this one
michael@0:         node  *m_after;  // intervals after this one
michael@0:         int    m_bal;
michael@0:     };
michael@0: 
michael@0: public:
michael@0:     /**
michael@0:      * A unidirectional const iterator that is used to enumerate the
michael@0:      * intervals that overlap a specific point.
michael@0:      */
michael@0:     class const_iterator {
michael@0:     protected:
michael@0:         const node  *m_node;
michael@0:         const coord  m_point;
michael@0: 
michael@0:         friend class interval_map;
michael@0:         const_iterator(const node *n, const coord &point)
michael@0:             : m_node(n), m_point(point) {}
michael@0: 
michael@0:         void advance();
michael@0: 
michael@0:     public:
michael@0:         const_iterator() : m_node(0), m_point(0) {}
michael@0: 
michael@0:         const_iterator(const const_iterator &iter)
michael@0:             : m_node(iter.m_node), m_point(iter.m_point) {}
michael@0: 
michael@0:         const_iterator &
michael@0:         operator=(const const_iterator &iter) {
michael@0:             m_node = iter.m_node;
michael@0:             m_point = iter.m_point; }
michael@0: 
michael@0:         const T &
michael@0:         operator*() const { return m_node->m_data; }
michael@0: 
michael@0:         const T *
michael@0:         operator->() const { return &m_node->m_data; }
michael@0: 
michael@0:         const_iterator &
michael@0:         operator++() { advance(); return *this; }
michael@0: 
michael@0:         const_iterator
michael@0:         operator++(int) {
michael@0:             const_iterator temp(*this);
michael@0:             advance();
michael@0:             return temp; }
michael@0: 
michael@0:         bool
michael@0:         operator==(const const_iterator &iter) const {
michael@0:             return m_node == iter.m_node; }
michael@0: 
michael@0:         bool
michael@0:         operator!=(const const_iterator &iter) const {
michael@0:             return !iter.operator==(*this); }
michael@0:     };
michael@0: 
michael@0:     interval_map() : m_root(0) {}
michael@0: 
michael@0:     ~interval_map() { delete m_root; }
michael@0: 
michael@0:     /**
michael@0:      * Insert aData for the interval [aMin, aMax]
michael@0:      */
michael@0:     void put(coord min, coord max, const T &data) {
michael@0:         put_into(&m_root, min, max, data);
michael@0: #ifdef DEBUG
michael@0:         verify(m_root, 0);
michael@0: #endif
michael@0:     }
michael@0: 
michael@0: 
michael@0:     /**
michael@0:      * Return an iterator that will enumerate the data for all intervals
michael@0:      * intersecting |aPoint|.
michael@0:      */
michael@0:     const_iterator get(coord point) const;
michael@0: 
michael@0:     /**
michael@0:      * Return an iterator that marks the end-point of iteration.
michael@0:      */
michael@0:     const_iterator end() const {
michael@0:         return const_iterator(0, 0); }
michael@0: 
michael@0: protected:
michael@0:     void put_into(node **link, coord min, coord max, const T &data, bool *subsumed = 0);
michael@0: 
michael@0:     void left_rotate(node **link, node *node);
michael@0:     void right_rotate(node **link, node *node);
michael@0: #ifdef DEBUG
michael@0:     void verify(node *node, int depth);
michael@0: #endif
michael@0:     node *m_root;
michael@0: };
michael@0: 
michael@0: template<class coord, class T>
michael@0: void
michael@0: interval_map<coord, T>::put_into(node **root, coord min, coord max, const T &data, bool *subsumed)
michael@0: {
michael@0:     assert(min < max);
michael@0:     node *interval = *root;
michael@0: 
michael@0:     if (interval) {
michael@0:         bool before = min < interval->m_min;
michael@0:         bool after = max > interval->m_max;
michael@0: 
michael@0:         if (!before || !after) {
michael@0:             // The interval we're adding does not completely subsume
michael@0:             // the |interval|. So we've got one of these situations:
michael@0:             //
michael@0:             //      |======|   |======|   |======|
michael@0:             //   |------|        |--|        |------|
michael@0:             //
michael@0:             // where |==| is the existing interval, and |--| is the
michael@0:             // new interval we're inserting. If there's left or right
michael@0:             // slop, then we ``split'' the new interval in half:
michael@0:             //
michael@0:             //      |======|              |======|
michael@0:             //   |--|---|                    |---|--|
michael@0:             //
michael@0:             // and insert it both in the ``within'' and ``before'' (or
michael@0:             // ``after'') subtrees.
michael@0:             //
michael@0:             if (before) {
michael@0:                 if (max > interval->m_min) {
michael@0:                     put_into(&interval->m_within, interval->m_min, max, data);
michael@0:                     max = interval->m_min;
michael@0:                 }
michael@0: 
michael@0:                 bool was_subsumed = true;
michael@0:                 put_into(&interval->m_before, min, max, data, &was_subsumed);
michael@0: 
michael@0:                 if (! was_subsumed) {
michael@0:                     if (interval->m_bal < 0) {
michael@0:                         if (interval->m_before->m_bal > 0)
michael@0:                             left_rotate(&interval->m_before, interval->m_before);
michael@0: 
michael@0:                         right_rotate(root, interval);
michael@0:                     }
michael@0:                     else
michael@0:                         --interval->m_bal;
michael@0: 
michael@0:                     if (subsumed)
michael@0:                         *subsumed = (interval->m_bal == 0);
michael@0:                 }
michael@0: 
michael@0:                 return;
michael@0:             }
michael@0: 
michael@0:             if (after) {
michael@0:                 if (min < interval->m_max) {
michael@0:                     put_into(&interval->m_within, min, interval->m_max, data);
michael@0:                     min = interval->m_max;
michael@0:                 }
michael@0: 
michael@0:                 bool was_subsumed = true;
michael@0:                 put_into(&interval->m_after, min, max, data, &was_subsumed);
michael@0: 
michael@0:                 if (! was_subsumed) {
michael@0:                     if (interval->m_bal > 0) {
michael@0:                         if (interval->m_after->m_bal < 0)
michael@0:                             right_rotate(&interval->m_after, interval->m_after);
michael@0: 
michael@0:                         left_rotate(root, interval);
michael@0:                     }
michael@0:                     else
michael@0:                         ++interval->m_bal;
michael@0: 
michael@0:                     if (subsumed)
michael@0:                         *subsumed = (interval->m_bal == 0);
michael@0:                 }
michael@0: 
michael@0:                 return;
michael@0:             }
michael@0: 
michael@0:             put_into(&interval->m_within, min, max, data);
michael@0:             return;
michael@0:         }
michael@0: 
michael@0:         // If we get here, the interval we're adding completely
michael@0:         // subsumes |interval|. We'll go ahead and insert a new
michael@0:         // interval immediately above |interval|, with |interval| as
michael@0:         // the new interval's |m_within|.
michael@0:     }
michael@0: 
michael@0:     if (subsumed)
michael@0:         *subsumed = false;
michael@0: 
michael@0:     node *n = new node();
michael@0:     n->m_data   = data;
michael@0:     n->m_before = n->m_after = 0;
michael@0:     n->m_min    = min;
michael@0:     n->m_max    = max;
michael@0:     n->m_within = interval;
michael@0:     n->m_bal    = 0;
michael@0:     *root = n;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  *    (*link)                               (*link)
michael@0:  *       |         == left rotate ==>          |
michael@0:  *      (x)                                   (y)
michael@0:  *     /   \                                 /   \
michael@0:  *    a    (y)    <== right rotate ==      (x)    c
michael@0:  *        /   \                           /   \
michael@0:  *       b     c                         a     b
michael@0:  */
michael@0: template<class coord, class T>
michael@0: void
michael@0: interval_map<coord, T>::left_rotate(node **link, node *x)
michael@0: {
michael@0:     node *y = x->m_after;
michael@0:     x->m_after = y->m_before;
michael@0:     *link = y;
michael@0:     y->m_before = x;
michael@0:     --x->m_bal;
michael@0:     --y->m_bal;
michael@0: }
michael@0: 
michael@0: template<class coord, class T>
michael@0: void
michael@0: interval_map<coord, T>::right_rotate(node **link, node *y)
michael@0: {
michael@0:     node *x = y->m_before;
michael@0:     y->m_before = x->m_after;
michael@0:     *link = x;
michael@0:     x->m_after = y;
michael@0:     ++y->m_bal;
michael@0:     ++x->m_bal;
michael@0: }
michael@0: 
michael@0: template<class coord, class T>
michael@0: interval_map<coord, T>::const_iterator
michael@0: interval_map<coord, T>::get(coord point) const
michael@0: {
michael@0:     node *interval = m_root;
michael@0: 
michael@0:     while (interval) {
michael@0:         if (point < interval->m_min)
michael@0:             interval = interval->m_before;
michael@0:         else if (point > interval->m_max)
michael@0:             interval = interval->m_after;
michael@0:         else
michael@0:             break;
michael@0:     }
michael@0: 
michael@0:     return const_iterator(interval, point);
michael@0: }
michael@0: 
michael@0: 
michael@0: template<class coord, class T>
michael@0: void
michael@0: interval_map<coord, T>::const_iterator::advance()
michael@0: {
michael@0:     assert(m_node);
michael@0: 
michael@0:     m_node = m_node->m_within;
michael@0: 
michael@0:     while (m_node) {
michael@0:         if (m_point < m_node->m_min)
michael@0:             m_node = m_node->m_before;
michael@0:         else if (m_point > m_node->m_max)
michael@0:             m_node = m_node->m_after;
michael@0:         else
michael@0:             break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: #ifdef DEBUG
michael@0: template<class coord, class T>
michael@0: void
michael@0: interval_map<coord, T>::verify(node<coord, T> *node, int depth)
michael@0: {
michael@0:     if (node->m_after)
michael@0:         verify(node->m_after, depth + 1);
michael@0: 
michael@0:     for (int i = 0; i < depth; ++i)
michael@0:         cout << "  ";
michael@0: 
michael@0:     hex(cout);
michael@0:     cout << node << "(";
michael@0:     dec(cout);
michael@0:     cout << node->m_bal << ")";
michael@0:     hex(cout);
michael@0:     cout << "[" << node->m_min << "," << node->m_max << "]";
michael@0:     cout << "@" << node->m_data;
michael@0:     cout << endl;
michael@0: 
michael@0:     if (node->m_before)
michael@0:         verify(node->m_before, depth + 1);
michael@0: }
michael@0: #endif // DEBUG
michael@0: 
michael@0: #endif // interval_map_h__