source: src/GenPoly/ScopedSet.h @ dc2e7e0

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 dc2e7e0 was 5ba653c, checked in by Aaron Moss <a3moss@…>, 9 years ago

Fix latent empty-scope iteration bug in ScopedMap/Set?
  • Property mode set to 100644
File size: 8.1 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// ScopedSet.h --
8//
9// Author           : Aaron B. Moss
10// Created On       : Thu Dec 3 11:51:00 2015
11// Last Modified By : Aaron B. Moss
12// Last Modified On : Thu Dec 3 11:51:00 2015
13// Update Count     : 1
14//
15
16#ifndef _SCOPEDSET_H
17#define _SCOPEDSET_H
18
19#include <iterator>
20#include <set>
21#include <vector>
22
23namespace GenPoly {
24        /// A set where the items are placed into nested scopes;
25        /// inserted items are placed into the innermost scope, lookup looks from the innermost scope outward
26        template<typename Value>
27        class ScopedSet {
28                typedef std::set< Value > Scope;
29                typedef std::vector< Scope > ScopeList;
30
31                ScopeList scopes; ///< scoped list of sets
32        public:
33                typedef typename Scope::key_type key_type;
34                typedef typename Scope::value_type value_type;
35                typedef typename ScopeList::size_type size_type;
36                typedef typename ScopeList::difference_type difference_type;
37                typedef typename Scope::reference reference;
38                typedef typename Scope::const_reference const_reference;
39                typedef typename Scope::pointer pointer;
40                typedef typename Scope::const_pointer const_pointer;
41               
42                class iterator : public std::iterator< std::bidirectional_iterator_tag,
43                                                       value_type > {
44                friend class ScopedSet;
45                friend class const_iterator;
46                        typedef typename std::set< Value >::iterator wrapped_iterator;
47                        typedef typename std::vector< std::set< Value > > scope_list;
48                        typedef typename scope_list::size_type size_type;
49
50                        /// Checks if this iterator points to a valid item
51                        bool is_valid() const {
52                                return it != (*scopes)[i].end();
53                        }
54
55                        /// Increments on invalid
56                        iterator& next_valid() {
57                                if ( ! is_valid() ) { ++(*this); }
58                                return *this;
59                        }
60
61                        /// Decrements on invalid
62                        iterator& prev_valid() {
63                                if ( ! is_valid() ) { --(*this); }
64                                return *this;
65                        }
66
67                        iterator(scope_list const &_scopes, const wrapped_iterator &_it, size_type _i)
68                                : scopes(&_scopes), it(_it), i(_i) {}
69                public:
70                        iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
71                        iterator& operator= (const iterator &that) {
72                                scopes = that.scopes; i = that.i; it = that.it;
73                                return *this;
74                        }
75                       
76                        reference operator* () { return *it; }
77                        pointer operator-> () { return it.operator->(); }
78
79                        iterator& operator++ () {
80                                if ( it == (*scopes)[i].end() ) {
81                                        if ( i == 0 ) return *this;
82                                        --i;
83                                        it = (*scopes)[i].begin();
84                                } else {
85                                        ++it;
86                                }
87                                return next_valid();
88                        }
89                        iterator& operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
90
91                        iterator& operator-- () {
92                                // may fail if this is the begin iterator; allowed by STL spec
93                                if ( it == (*scopes)[i].begin() ) {
94                                        ++i;
95                                        it = (*scopes)[i].end();
96                                }
97                                --it;
98                                return prev_valid();
99                        }
100                        iterator& operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
101
102                        bool operator== (const iterator &that) {
103                                return scopes == that.scopes && i == that.i && it == that.it;
104                        }
105                        bool operator!= (const iterator &that) { return !( *this == that ); }
106
107                private:
108                        scope_list const *scopes;
109                        wrapped_iterator it;
110                        size_type i;
111                };
112
113                class const_iterator : public std::iterator< std::bidirectional_iterator_tag,
114                                                             value_type > {
115                friend class ScopedSet;
116                        typedef typename std::set< Value >::iterator wrapped_iterator;
117                        typedef typename std::set< Value >::const_iterator wrapped_const_iterator;
118                        typedef typename std::vector< std::set< Value > > scope_list;
119                        typedef typename scope_list::size_type size_type;
120
121                        /// Checks if this iterator points to a valid item
122                        bool is_valid() const {
123                                return it != (*scopes)[i].end();
124                        }
125
126                        /// Increments on invalid
127                        const_iterator& next_valid() {
128                                if ( ! is_valid() ) { ++(*this); }
129                                return *this;
130                        }
131
132                        /// Decrements on invalid
133                        const_iterator& prev_valid() {
134                                if ( ! is_valid() ) { --(*this); }
135                                return *this;
136                        }
137
138                        const_iterator(scope_list const &_scopes, const wrapped_const_iterator &_it, size_type _i)
139                                : scopes(&_scopes), it(_it), i(_i) {}
140                public:
141                        const_iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
142                        const_iterator(const const_iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
143                        const_iterator& operator= (const iterator &that) {
144                                scopes = that.scopes; i = that.i; it = that.it;
145                                return *this;
146                        }
147                        const_iterator& operator= (const const_iterator &that) {
148                                scopes = that.scopes; i = that.i; it = that.it;
149                                return *this;
150                        }
151
152                        const_reference operator* () { return *it; }
153                        const_pointer operator-> () { return it.operator->(); }
154
155                        const_iterator& operator++ () {
156                                if ( it == (*scopes)[i].end() ) {
157                                        if ( i == 0 ) return *this;
158                                        --i;
159                                        it = (*scopes)[i].begin();
160                                } else {
161                                        ++it;
162                                }
163                                return next_valid();
164                        }
165                        const_iterator& operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
166
167                        const_iterator& operator-- () {
168                                // may fail if this is the begin iterator; allowed by STL spec
169                                if ( it == (*scopes)[i].begin() ) {
170                                        ++i;
171                                        it = (*scopes)[i].end();
172                                }
173                                --it;
174                                return prev_valid();
175                        }
176                        const_iterator& operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
177
178                        bool operator== (const const_iterator &that) {
179                                return scopes == that.scopes && i == that.i && it == that.it;
180                        }
181                        bool operator!= (const const_iterator &that) { return !( *this == that ); }
182
183                private:
184                        scope_list const *scopes;
185                        wrapped_const_iterator it;
186                        size_type i;
187                };
188               
189                /// Starts a new scope
190                void beginScope() {
191                        Scope scope;
192                        scopes.push_back(scope);
193                }
194
195                /// Ends a scope; invalidates any iterators pointing to elements of that scope
196                void endScope() {
197                        scopes.pop_back();
198                }
199
200                /// Default constructor initializes with one scope
201                ScopedSet() { beginScope(); }
202
203                iterator begin() { return iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
204                const_iterator begin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
205                const_iterator cbegin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
206                iterator end() { return iterator(scopes, scopes[0].end(), 0); }
207                const_iterator end() const { return const_iterator(scopes, scopes[0].end(), 0); }
208                const_iterator cend() const { return const_iterator(scopes, scopes[0].end(), 0); }
209
210                /// Gets the index of the current scope (counted from 1)
211                size_type currentScope() const { return scopes.size(); }
212
213                /// Finds the given key in the outermost scope it occurs; returns end() for none such
214                iterator find( const Value &key ) {
215                        for ( size_type i = scopes.size() - 1; ; --i ) {
216                                typename Scope::iterator val = scopes[i].find( key );
217                                if ( val != scopes[i].end() ) return iterator( scopes, val, i );
218                                if ( i == 0 ) break;
219                        }
220                        return end();
221                }
222                const_iterator find( const Value &key ) const {
223                        return const_iterator( const_cast< ScopedSet< Value >* >(this)->find( key ) );
224                }
225               
226                /// Finds the given key in the outermost scope inside the given scope where it occurs
227                iterator findNext( const_iterator &it, const Value &key ) {
228                        if ( it.i == 0 ) return end();
229                        for ( size_type i = it.i - 1; ; --i ) {
230                                typename Scope::iterator val = scopes[i].find( key );
231                                if ( val != scopes[i].end() ) return iterator( scopes, val, i );
232                                if ( i == 0 ) break;
233                        }
234                        return end();
235                }
236                const_iterator findNext( const_iterator &it, const Value &key ) const {
237                        return const_iterator( const_cast< ScopedSet< Value >* >(this)->findNext( it, key ) );
238                }
239
240                /// Inserts the given value into the outermost scope
241                std::pair< iterator, bool > insert( const value_type &value ) {
242                        std::pair< typename Scope::iterator, bool > res = scopes.back().insert( value );
243                        return std::make_pair( iterator(scopes, res.first, scopes.size()-1), res.second );
244                }
245               
246        };
247} // namespace GenPoly
248
249#endif // _SCOPEDSET_H
250
251// Local Variables: //
252// tab-width: 4 //
253// mode: c++ //
254// compile-command: "make install" //
255// End: //
Note: See TracBrowser for help on using the repository browser.