source: translator/InitTweak/diet_map.h @ 01aeade

//
// 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.
//
// XXX.cc -- 
//
// Author           : Richard C. Bilson
// Created On       : Mon May 18 07:44:20 2015
// Last Modified By : 
// Last Modified On : 
// Update Count     : 0
//
#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);
          }
        }
      }
      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();
      }
      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:
  mode: c++
  End:
*/
// Local Variables: //
// tab-width: 4 //
// mode: c++ //
// compile-command: "make install" //
// End: //