source: src/GenPoly/ScopedSet.h@ baba5d8

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors ctor deferred_resn demangler enum forall-pointer-decay gc_noraii jacob/cs343-translation jenkins-sandbox memory new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new string with_gc
Last change on this file since baba5d8 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.