#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:
*/