[51b7345] | 1 | #include <cassert> |
---|
| 2 | #include <string> |
---|
| 3 | #include <stack> |
---|
| 4 | |
---|
| 5 | namespace diet { |
---|
| 6 | /* A DIET ( Discrete Interval Encoding Tree ) range-map |
---|
| 7 | */ |
---|
| 8 | |
---|
| 9 | class diet_tree_exception : public std::exception { |
---|
| 10 | public: |
---|
| 11 | diet_tree_exception() {} |
---|
| 12 | diet_tree_exception( std::string _what ) : what( _what ) {} |
---|
| 13 | ~diet_tree_exception() throw () {} |
---|
| 14 | |
---|
| 15 | std::string get_what() const { return what; } |
---|
| 16 | void set_what( std::string newValue ) { what = newValue; } |
---|
| 17 | private: |
---|
| 18 | std::string what; |
---|
| 19 | }; |
---|
| 20 | |
---|
| 21 | template < typename T > class diet_tree_node; |
---|
| 22 | template < typename T > class diet_tree_iterator; |
---|
| 23 | |
---|
| 24 | template< typename key_type > |
---|
| 25 | class diet_tree { |
---|
| 26 | typedef key_type OrderedValue; |
---|
| 27 | typedef OrderedValue T; |
---|
| 28 | friend class diet_tree_iterator<T>; |
---|
| 29 | public: |
---|
| 30 | typedef OrderedValue value_type; |
---|
| 31 | typedef diet_tree_iterator<OrderedValue> iterator; |
---|
| 32 | typedef std::pair<value_type, value_type> pair_type; |
---|
| 33 | |
---|
| 34 | diet_tree() : root(0), left(0), right(0) {} |
---|
| 35 | ~diet_tree() { |
---|
[a32b204] | 36 | if ( root != 0 ) { delete root; root = 0; } |
---|
| 37 | if ( left != 0 ) { delete left; left = 0; } |
---|
| 38 | if ( right != 0 ) { delete right; right = 0; } |
---|
[51b7345] | 39 | } |
---|
| 40 | |
---|
| 41 | void insert( value_type _lo, value_type _hi ) { |
---|
| 42 | if ( _lo > _hi ) return; // throw exception? |
---|
| 43 | if ( root == 0 ) |
---|
| 44 | root = new diet_tree_node<value_type>(_lo, _hi); |
---|
| 45 | else { |
---|
| 46 | value_type lo = root->get_lo(), hi = root->get_hi(); |
---|
[a32b204] | 47 | if ( _lo < lo ) { |
---|
| 48 | if ( _hi > hi ) { |
---|
[51b7345] | 49 | /* can either minimize the work or minimize the number of nodes. |
---|
| 50 | Let's minimize the work. */ |
---|
| 51 | if ( left == 0 ) left = new diet_tree<T>(); |
---|
| 52 | left->insert( _lo, lo ); |
---|
| 53 | if ( right == 0 ) right = new diet_tree<T>(); |
---|
| 54 | right->insert( _hi, hi ); |
---|
| 55 | return; |
---|
[a32b204] | 56 | } else if ( _hi < lo ) { |
---|
[51b7345] | 57 | if ( left == 0 ) left = new diet_tree<T>(); |
---|
| 58 | left->insert( _lo, _hi ); |
---|
[a32b204] | 59 | } else if ( _hi <= hi ) { |
---|
[51b7345] | 60 | if ( left == 0 ) left = new diet_tree<T>(); |
---|
| 61 | left->insert( _lo, _hi ); |
---|
| 62 | root->set_range(_hi,hi); |
---|
| 63 | } |
---|
| 64 | } else if (_lo >= lo && _hi <= hi ) { |
---|
| 65 | root->set_range(_lo,_hi); |
---|
| 66 | } else if ( _hi > hi) { |
---|
[a32b204] | 67 | if ( _lo > hi ) { |
---|
[51b7345] | 68 | if ( right == 0 ) right = new diet_tree<T>(); |
---|
| 69 | right->insert( _lo, _hi ); |
---|
[a32b204] | 70 | } else if ( _lo < hi ) { |
---|
[51b7345] | 71 | root->set_range(lo, _lo); |
---|
| 72 | if ( right == 0 ) right = new diet_tree<T>(); |
---|
| 73 | right->insert(_lo, _hi); |
---|
| 74 | } |
---|
| 75 | } |
---|
| 76 | } |
---|
| 77 | return; |
---|
| 78 | } |
---|
| 79 | |
---|
| 80 | void insert( std::pair<value_type, value_type> p ) { |
---|
| 81 | insert(p.first, p.second); |
---|
| 82 | } |
---|
| 83 | |
---|
| 84 | pair_type get_range_pair() const { |
---|
| 85 | return pair_type(root->get_lo(),root->get_hi()); |
---|
| 86 | } |
---|
| 87 | |
---|
| 88 | /* |
---|
| 89 | void display( std::ostream &os = std::cout ) { |
---|
| 90 | if ( root != 0 ) { |
---|
| 91 | if ( left != 0 ) left->display(os); |
---|
| 92 | os << "(" << root->get_lo() << ", " << root->get_hi() << ")" << std::endl; |
---|
| 93 | if ( right != 0 ) right->display(os); |
---|
| 94 | } |
---|
| 95 | return; |
---|
| 96 | } |
---|
| 97 | */ |
---|
| 98 | |
---|
| 99 | iterator begin() { return iterator( this ); } |
---|
| 100 | iterator end() { return iterator( (diet_tree< value_type > *)0 ); } |
---|
| 101 | |
---|
| 102 | protected: |
---|
| 103 | diet_tree( diet_tree_node< OrderedValue > *_root ) : root( _root ) {} |
---|
| 104 | private: |
---|
| 105 | diet_tree_node< value_type > *root; |
---|
| 106 | diet_tree< value_type > *left, *right; |
---|
| 107 | }; |
---|
| 108 | |
---|
| 109 | template< typename OrderedValue > |
---|
| 110 | class diet_tree_node { |
---|
| 111 | public: |
---|
| 112 | typedef OrderedValue value_type; |
---|
| 113 | |
---|
| 114 | diet_tree_node( const OrderedValue &_lo, const OrderedValue &_hi ) |
---|
| 115 | : lo( _lo ), hi( _hi ) { |
---|
| 116 | if ( lo >= hi ) throw diet_tree_exception( "Invalid range" ); |
---|
| 117 | } |
---|
| 118 | |
---|
| 119 | void set_range(const OrderedValue &newLo, const OrderedValue &newHi) |
---|
| 120 | { lo = newLo; hi = newHi; } |
---|
| 121 | OrderedValue get_lo() const { return lo; } |
---|
| 122 | OrderedValue get_hi() const { return hi; } |
---|
| 123 | |
---|
| 124 | private: |
---|
| 125 | OrderedValue lo, hi; |
---|
| 126 | }; |
---|
| 127 | |
---|
| 128 | /* forward iterator */ |
---|
| 129 | template < typename T > |
---|
| 130 | class diet_tree_iterator { |
---|
| 131 | typedef diet_tree_iterator<T> self; |
---|
| 132 | typedef typename diet_tree<T>::pair_type pair_type; |
---|
| 133 | |
---|
| 134 | public: |
---|
| 135 | // typedef forward_iterator_tag iterator_category; |
---|
| 136 | |
---|
| 137 | diet_tree_iterator( diet_tree<T> *_tree ) : current( _tree ) { |
---|
| 138 | // current is allowed to be 0 only for `end' |
---|
| 139 | if (_tree != 0) go_leftmost(); |
---|
| 140 | } |
---|
| 141 | |
---|
| 142 | ~diet_tree_iterator() {} |
---|
| 143 | pair_type operator*() { |
---|
| 144 | if ( current == 0 ) throw diet_tree_exception( "Invalid dereference" ); |
---|
| 145 | return current->get_range_pair(); |
---|
| 146 | } |
---|
| 147 | |
---|
| 148 | bool operator==( const diet_tree_iterator<T> &other ) { return current == other.current; } |
---|
| 149 | bool operator!=( const diet_tree_iterator<T> &other ) { return current != other.current; } |
---|
| 150 | |
---|
| 151 | diet_tree_iterator<T> operator++() { |
---|
| 152 | assert(current != 0); |
---|
| 153 | if ( current->right == 0 ) |
---|
[a32b204] | 154 | if ( ! st.empty() ) |
---|
[51b7345] | 155 | { current = st.top(); st.pop(); } |
---|
| 156 | else |
---|
| 157 | current = 0; |
---|
| 158 | else { |
---|
| 159 | current = current->right; |
---|
| 160 | go_leftmost(); |
---|
| 161 | } |
---|
| 162 | return *this; |
---|
| 163 | } |
---|
| 164 | |
---|
| 165 | diet_tree_iterator<T> operator++(int) { |
---|
| 166 | self temp = *this; |
---|
| 167 | this->operator++(); |
---|
| 168 | return temp; |
---|
| 169 | } |
---|
| 170 | |
---|
| 171 | private: |
---|
| 172 | void go_leftmost() { |
---|
| 173 | assert(current != 0); |
---|
| 174 | diet_tree<T> *next = 0; |
---|
[a32b204] | 175 | while ( current->left != 0 ) { |
---|
[51b7345] | 176 | next = current->left; st.push( current ); current = next; |
---|
| 177 | } |
---|
| 178 | return; |
---|
| 179 | } |
---|
| 180 | |
---|
| 181 | void defrag() { |
---|
| 182 | /* join adjacent trees */ |
---|
| 183 | return; |
---|
| 184 | } |
---|
| 185 | |
---|
| 186 | diet_tree<T> *current; |
---|
| 187 | std::stack< diet_tree<T> * > st; |
---|
| 188 | }; |
---|
| 189 | |
---|
| 190 | template < typename Key, typename Value > |
---|
| 191 | class diet_tree_assoc_node : public diet_tree_node<Key> { |
---|
| 192 | public: |
---|
| 193 | typedef Key key_type; |
---|
| 194 | typedef Value data_type; |
---|
| 195 | typedef std::pair<Key,Value> value_type; |
---|
| 196 | private: |
---|
| 197 | Value data; |
---|
| 198 | }; |
---|
| 199 | |
---|
| 200 | } // namespace diet |
---|
| 201 | |
---|
| 202 | |
---|
| 203 | /* |
---|
| 204 | Local Variables: |
---|
| 205 | mode: c++ |
---|
| 206 | End: |
---|
| 207 | */ |
---|