Index: translator/InitTweak/diet_map.h
===================================================================
--- translator/InitTweak/diet_map.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/InitTweak/diet_map.h	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,207 @@
+#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:
+*/
