source: src/InitTweak/diet_map.h @ ec79847

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

licencing: seventh groups of files

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