source: src/InitTweak/diet_map.h @ 86bd7c1f

//
// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// diet_map.h -- 
//
// Author           : Rodolfo G. Esteves
// Created On       : Mon May 18 07:44:20 2015
// Last Modified By : Peter A. Buhr
// Last Modified On : Tue May 19 16:41:17 2015
// Update Count     : 2
//

#include <cassert>
#include <string>
#include <stack>

namespace diet {
        /* A DIET ( Discrete Interval Encoding Tree ) range-map
         */

        class diet_tree_exception : public std::exception {
          public:
                diet_tree_exception() {}
                diet_tree_exception( std::string _what ) : what( _what ) {}
                ~diet_tree_exception() throw () {}

                std::string get_what() const { return what; }
                void set_what( std::string newValue ) { what = newValue; }
          private:
                std::string what;
        };

        template < typename T > class diet_tree_node;
        template < typename T > class diet_tree_iterator;

        template< typename key_type >
        class diet_tree {
                typedef key_type OrderedValue;
                typedef OrderedValue T;
                friend class diet_tree_iterator<T>;
          public:
                typedef OrderedValue value_type;
                typedef diet_tree_iterator<OrderedValue> iterator;
                typedef std::pair<value_type, value_type> pair_type;

                diet_tree() : root(0), left(0), right(0) {}
                ~diet_tree() {
                        if ( root != 0 ) { delete root; root = 0; }
                        if ( left != 0 ) { delete left; left = 0; }
                        if ( right != 0 ) { delete right; right = 0; }
                }

                void insert( value_type _lo, value_type _hi ) {
                        if ( _lo > _hi ) return; // throw exception?
                        if ( root == 0 )
                                root = new diet_tree_node<value_type>(_lo, _hi);
                        else {
                                value_type lo = root->get_lo(), hi = root->get_hi();
                                if ( _lo < lo ) {
                                        if ( _hi > hi ) {
                                                /* can either minimize the work or minimize the number of nodes.
                                                   Let's minimize the work. */
                                                if ( left == 0 ) left = new diet_tree<T>();
                                                left->insert( _lo, lo );
                                                if ( right == 0 ) right = new diet_tree<T>();
                                                right->insert( _hi, hi );
                                                return;
                                        } else if ( _hi < lo ) {
                                                if ( left == 0 ) left = new diet_tree<T>();
                                                left->insert( _lo, _hi );
                                        } else if ( _hi <= hi ) {
                                                if ( left == 0 ) left = new diet_tree<T>();
                                                left->insert( _lo, _hi );
                                                root->set_range(_hi,hi);
                                        }
                                } else if (_lo >= lo && _hi <= hi ) {
                                        root->set_range(_lo,_hi);
                                } else if ( _hi > hi) {
                                        if ( _lo > hi ) {
                                                if ( right == 0 ) right = new diet_tree<T>();
                                                right->insert( _lo, _hi );
                                        } else if ( _lo < hi ) {
                                                root->set_range(lo, _lo);
                                                if ( right == 0 ) right = new diet_tree<T>();
                                                right->insert(_lo, _hi);
                                        } // if
                                } // if
                        } // if
                        return;
                }

                void insert( std::pair<value_type, value_type> p ) {
                        insert(p.first, p.second);
                }

                pair_type get_range_pair() const {
                        return pair_type(root->get_lo(),root->get_hi());
                }

                /*
                  void display( std::ostream &os = std::cout ) {
                  if ( root != 0 ) {
                  if ( left != 0 ) left->display(os);
                  os << "(" << root->get_lo() << ", " << root->get_hi() << ")" << std::endl;
                  if ( right != 0 ) right->display(os);
                  }
                  return;
                  }
                */

                iterator begin() { return iterator( this ); }
                iterator end() { return iterator( (diet_tree< value_type > *)0 ); }

          protected:
                diet_tree( diet_tree_node< OrderedValue > *_root ) : root( _root ) {}
          private:
                diet_tree_node< value_type > *root;
                diet_tree< value_type > *left, *right;
        };

        template< typename OrderedValue >
        class diet_tree_node {
          public:
                typedef OrderedValue value_type;

                diet_tree_node( const OrderedValue &_lo, const OrderedValue &_hi )
                        : lo( _lo ), hi( _hi ) {
                        if ( lo >= hi ) throw diet_tree_exception( "Invalid range" );
                }

                void set_range(const OrderedValue &newLo, const OrderedValue &newHi)
                        { lo = newLo; hi = newHi; }
                OrderedValue get_lo() const { return lo; }
                OrderedValue get_hi() const { return hi; }

          private:
                OrderedValue lo, hi;
        };

        /* forward iterator */
        template < typename T >
        class diet_tree_iterator {
                typedef diet_tree_iterator<T> self;
                typedef typename diet_tree<T>::pair_type pair_type;

          public:
                //    typedef forward_iterator_tag iterator_category;

                diet_tree_iterator( diet_tree<T> *_tree ) : current( _tree ) {
                        // current is allowed to be 0 only for `end'
                        if (_tree != 0) go_leftmost();
                }

                ~diet_tree_iterator() {}
                pair_type operator*() {
                        if ( current == 0 ) throw diet_tree_exception( "Invalid dereference" );
                        return current->get_range_pair();
                }

                bool operator==( const diet_tree_iterator<T> &other ) { return current == other.current;  }
                bool operator!=( const diet_tree_iterator<T> &other ) { return current != other.current;  }

                diet_tree_iterator<T> operator++() {
                        assert(current != 0);
                        if ( current->right == 0 )
                                if ( ! st.empty() )
                                        { current = st.top(); st.pop(); }
                                else
                                        current = 0;
                        else {
                                current = current->right;
                                go_leftmost();
                        } // if
                        return *this;
                }

                diet_tree_iterator<T> operator++(int) {
                        self temp = *this;
                        this->operator++();
                        return temp;
                }

          private:
                void go_leftmost() {
                        assert(current != 0);
                        diet_tree<T> *next = 0;
                        while ( current->left != 0 ) {
                                next = current->left; st.push( current ); current = next;
                        }
                        return;
                }

                void defrag() {
                        /* join adjacent trees */
                        return;
                }

                diet_tree<T> *current;
                std::stack< diet_tree<T> * > st;
        };

        template < typename Key, typename Value >
        class diet_tree_assoc_node : public diet_tree_node<Key> {
          public:
                typedef Key key_type;
                typedef Value data_type;
                typedef std::pair<Key,Value> value_type;
          private:
                Value data;
        };
} // namespace diet

// Local Variables: //
// tab-width: 4 //
// mode: c++ //
// compile-command: "make install" //
// End: //