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