source: translator/InitTweak/diet_map.h @ 1db2c5be

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsctordeferred_resndemanglerenumforall-pointer-decaygc_noraiijacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newstringwith_gc
Last change on this file since 1db2c5be was 51b7345, checked in by Peter A. Buhr <pabuhr@…>, 10 years ago

initial commit

  • Property mode set to 100644
File size: 5.3 KB
RevLine 
[51b7345]1#include <cassert>
2#include <string>
3#include <stack>
4
5namespace 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() {
36      if( root != 0 ) { delete root; root = 0; }
37      if( left != 0 ) { delete left; left = 0; }
38      if( right != 0 ) { delete right; right = 0; }
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();
47        if( _lo < lo ) {
48          if( _hi > hi ) {
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;
56          } else if( _hi < lo ) {
57            if ( left == 0 ) left = new diet_tree<T>();
58            left->insert( _lo, _hi );
59          } else if( _hi <= hi ) {
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) {
67          if( _lo > hi ) {
68            if ( right == 0 ) right = new diet_tree<T>();
69            right->insert( _lo, _hi );
70          } else if( _lo < hi ) {
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 )
154        if ( !st.empty() )
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;
175      while( current->left != 0 ) {
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*/
Note: See TracBrowser for help on using the repository browser.