source: src/Common/ScopedMap.h@ bcd74f3

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since bcd74f3 was e0e9a0b, checked in by Aaron Moss <a3moss@…>, 6 years ago

Somewhat deeper clone for types with forall qualifiers.
  • Property mode set to 100644
File size: 11.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// ScopedMap.h --
8//
9// Author : Aaron B. Moss
10// Created On : Wed Dec 2 11:37:00 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Mon May 21 15:22:40 2018
13// Update Count : 3
14//
15
16#pragma once
17
18#include <cassert>
19#include <iterator>
20#include <map>
21#include <utility>
22#include <vector>
23
24/// Default (empty) ScopedMap note type
25struct EmptyNote {};
26
27/// A map where the items are placed into nested scopes;
28/// inserted items are placed into the innermost scope, lookup looks from the innermost scope outward.
29/// Scopes may be annotated with a value; the annotation defaults to empty
30template<typename Key, typename Value, typename Note = EmptyNote>
31class ScopedMap {
32 typedef std::map< Key, Value > MapType;
33 struct Scope {
34 MapType map;
35 Note note;
36
37 template<typename N>
38 Scope(N&& n) : map(), note(std::forward<N>(n)) {}
39
40 Scope() = default;
41 Scope(const Scope&) = default;
42 Scope(Scope&&) = default;
43 Scope& operator= (const Scope&) = default;
44 Scope& operator= (Scope&&) = default;
45 };
46 typedef std::vector< Scope > ScopeList;
47
48 ScopeList scopes; ///< scoped list of maps
49public:
50 typedef typename MapType::key_type key_type;
51 typedef typename MapType::mapped_type mapped_type;
52 typedef typename MapType::value_type value_type;
53 typedef typename ScopeList::size_type size_type;
54 typedef typename ScopeList::difference_type difference_type;
55 typedef typename MapType::reference reference;
56 typedef typename MapType::const_reference const_reference;
57 typedef typename MapType::pointer pointer;
58 typedef typename MapType::const_pointer const_pointer;
59
60 class iterator : public std::iterator< std::bidirectional_iterator_tag,
61 value_type > {
62 friend class ScopedMap;
63 friend class const_iterator;
64 typedef typename ScopedMap::MapType::iterator wrapped_iterator;
65 typedef typename ScopedMap::ScopeList scope_list;
66 typedef typename scope_list::size_type size_type;
67
68 /// Checks if this iterator points to a valid item
69 bool is_valid() const {
70 return it != (*scopes)[level].map.end();
71 }
72
73 /// Increments on invalid
74 iterator& next_valid() {
75 if ( ! is_valid() ) { ++(*this); }
76 return *this;
77 }
78
79 /// Decrements on invalid
80 iterator& prev_valid() {
81 if ( ! is_valid() ) { --(*this); }
82 return *this;
83 }
84
85 iterator(scope_list &_scopes, const wrapped_iterator &_it, size_type inLevel)
86 : scopes(&_scopes), it(_it), level(inLevel) {}
87 public:
88 iterator(const iterator &that) : scopes(that.scopes), it(that.it), level(that.level) {}
89 iterator& operator= (const iterator &that) {
90 scopes = that.scopes; level = that.level; it = that.it;
91 return *this;
92 }
93
94 reference operator* () { return *it; }
95 pointer operator-> () { return it.operator->(); }
96
97 iterator& operator++ () {
98 if ( it == (*scopes)[level].map.end() ) {
99 if ( level == 0 ) return *this;
100 --level;
101 it = (*scopes)[level].map.begin();
102 } else {
103 ++it;
104 }
105 return next_valid();
106 }
107 iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
108
109 iterator& operator-- () {
110 // may fail if this is the begin iterator; allowed by STL spec
111 if ( it == (*scopes)[level].map.begin() ) {
112 ++level;
113 it = (*scopes)[level].map.end();
114 }
115 --it;
116 return prev_valid();
117 }
118 iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
119
120 bool operator== (const iterator &that) const {
121 return scopes == that.scopes && level == that.level && it == that.it;
122 }
123 bool operator!= (const iterator &that) const { return !( *this == that ); }
124
125 size_type get_level() const { return level; }
126
127 Note& get_note() { return (*scopes)[level].note; }
128 const Note& get_note() const { return (*scopes)[level].note; }
129
130 private:
131 scope_list *scopes;
132 wrapped_iterator it;
133 size_type level;
134 };
135
136 class const_iterator : public std::iterator< std::bidirectional_iterator_tag,
137 value_type > {
138 friend class ScopedMap;
139 typedef typename ScopedMap::MapType::iterator wrapped_iterator;
140 typedef typename ScopedMap::MapType::const_iterator wrapped_const_iterator;
141 typedef typename ScopedMap::ScopeList scope_list;
142 typedef typename scope_list::size_type size_type;
143
144 /// Checks if this iterator points to a valid item
145 bool is_valid() const {
146 return it != (*scopes)[level].map.end();
147 }
148
149 /// Increments on invalid
150 const_iterator& next_valid() {
151 if ( ! is_valid() ) { ++(*this); }
152 return *this;
153 }
154
155 /// Decrements on invalid
156 const_iterator& prev_valid() {
157 if ( ! is_valid() ) { --(*this); }
158 return *this;
159 }
160
161 const_iterator(scope_list const &_scopes, const wrapped_const_iterator &_it, size_type inLevel)
162 : scopes(&_scopes), it(_it), level(inLevel) {}
163 public:
164 const_iterator(const iterator &that) : scopes(that.scopes), it(that.it), level(that.level) {}
165 const_iterator(const const_iterator &that) : scopes(that.scopes), it(that.it), level(that.level) {}
166 const_iterator& operator= (const iterator &that) {
167 scopes = that.scopes; level = that.level; it = that.it;
168 return *this;
169 }
170 const_iterator& operator= (const const_iterator &that) {
171 scopes = that.scopes; level = that.level; it = that.it;
172 return *this;
173 }
174
175 const_reference operator* () { return *it; }
176 const_pointer operator-> () { return it.operator->(); }
177
178 const_iterator& operator++ () {
179 if ( it == (*scopes)[level].map.end() ) {
180 if ( level == 0 ) return *this;
181 --level;
182 it = (*scopes)[level].map.begin();
183 } else {
184 ++it;
185 }
186 return next_valid();
187 }
188 const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
189
190 const_iterator& operator-- () {
191 // may fail if this is the begin iterator; allowed by STL spec
192 if ( it == (*scopes)[level].map.begin() ) {
193 ++level;
194 it = (*scopes)[level].map.end();
195 }
196 --it;
197 return prev_valid();
198 }
199 const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
200
201 bool operator== (const const_iterator &that) const {
202 return scopes == that.scopes && level == that.level && it == that.it;
203 }
204 bool operator!= (const const_iterator &that) const { return !( *this == that ); }
205
206 size_type get_level() const { return level; }
207
208 const Note& get_note() const { return (*scopes)[level].note; }
209
210 private:
211 scope_list const *scopes;
212 wrapped_const_iterator it;
213 size_type level;
214 };
215
216 /// Starts a new scope
217 void beginScope() {
218 scopes.emplace_back();
219 }
220
221 // Starts a new scope with the given note
222 template<typename N>
223 void beginScope( N&& n ) {
224 scopes.emplace_back( std::forward<N>(n) );
225 }
226
227 /// Ends a scope; invalidates any iterators pointing to elements of that scope
228 void endScope() {
229 scopes.pop_back();
230 assert( ! scopes.empty() );
231 }
232
233 /// Default constructor initializes with one scope
234 ScopedMap() : scopes() { beginScope(); }
235
236 /// Constructs with a given note on the outermost scope
237 template<typename N>
238 ScopedMap( N&& n ) : scopes() { beginScope(std::forward<N>(n)); }
239
240 iterator begin() { return iterator(scopes, scopes.back().map.begin(), currentScope()).next_valid(); }
241 const_iterator begin() const { return const_iterator(scopes, scopes.back().map.begin(), currentScope()).next_valid(); }
242 const_iterator cbegin() const { return const_iterator(scopes, scopes.back().map.begin(), currentScope()).next_valid(); }
243 iterator end() { return iterator(scopes, scopes[0].map.end(), 0); }
244 const_iterator end() const { return const_iterator(scopes, scopes[0].map.end(), 0); }
245 const_iterator cend() const { return const_iterator(scopes, scopes[0].map.end(), 0); }
246
247 /// Gets the index of the current scope (counted from 1)
248 size_type currentScope() const { return scopes.size() - 1; }
249
250 /// Gets the note at the given scope
251 Note& getNote() { return scopes.back().note; }
252 const Note& getNote() const { return scopes.back().note; }
253 Note& getNote( size_type i ) { return scopes[i].note; }
254 const Note& getNote( size_type i ) const { return scopes[i].note; }
255
256 /// Finds the given key in the outermost scope it occurs; returns end() for none such
257 iterator find( const Key &key ) {
258 for ( size_type i = scopes.size() - 1; ; --i ) {
259 typename MapType::iterator val = scopes[i].map.find( key );
260 if ( val != scopes[i].map.end() ) return iterator( scopes, val, i );
261 if ( i == 0 ) break;
262 }
263 return end();
264 }
265 const_iterator find( const Key &key ) const {
266 return const_iterator( const_cast< ScopedMap< Key, Value, Note >* >(this)->find( key ) );
267 }
268
269 /// Finds the given key in the provided scope; returns end() for none such
270 iterator findAt( size_type scope, const Key& key ) {
271 typename MapType::iterator val = scopes[scope].map.find( key );
272 if ( val != scopes[scope].map.end() ) return iterator( scopes, val, scope );
273 return end();
274 }
275 const_iterator findAt( size_type scope, const Key& key ) const {
276 return const_iterator( const_cast< ScopedMap< Key, Value, Note >* >(this)->findAt( scope, key ) );
277 }
278
279 /// Finds the given key in the outermost scope inside the given scope where it occurs
280 iterator findNext( const_iterator &it, const Key &key ) {
281 if ( it.level == 0 ) return end();
282 for ( size_type i = it.level - 1; ; --i ) {
283 typename MapType::iterator val = scopes[i].map.find( key );
284 if ( val != scopes[i].map.end() ) return iterator( scopes, val, i );
285 if ( i == 0 ) break;
286 }
287 return end();
288 }
289 const_iterator findNext( const_iterator &it, const Key &key ) const {
290 return const_iterator( const_cast< ScopedMap< Key, Value, Note >* >(this)->findNext( it, key ) );
291 }
292
293 /// Inserts the given key-value pair into the outermost scope
294 template< typename value_type_t >
295 std::pair< iterator, bool > insert( value_type_t&& value ) {
296 std::pair< typename MapType::iterator, bool > res = scopes.back().map.insert( std::forward<value_type_t>( value ) );
297 return std::make_pair( iterator(scopes, std::move( res.first ), scopes.size()-1), std::move( res.second ) );
298 }
299
300 template< typename value_type_t >
301 std::pair< iterator, bool > insert( iterator at, value_type_t&& value ) {
302 MapType& scope = (*at.scopes)[ at.level ].map;
303 std::pair< typename MapType::iterator, bool > res = scope.insert( std::forward<value_type_t>( value ) );
304 return std::make_pair( iterator(scopes, std::move( res.first ), at.level), std::move( res.second ) );
305 }
306
307 template< typename value_t >
308 std::pair< iterator, bool > insert( const Key &key, value_t&& value ) { return insert( std::make_pair( key, std::forward<value_t>( value ) ) ); }
309
310 template< typename value_type_t >
311 std::pair< iterator, bool > insertAt( size_type scope, value_type_t&& value ) {
312 std::pair< typename MapType::iterator, bool > res = scopes.at(scope).map.insert( std::forward<value_type_t>( value ) );
313 return std::make_pair( iterator(scopes, std::move( res.first ), scope), std::move( res.second ) );
314 }
315
316 template< typename value_t >
317 std::pair< iterator, bool > insertAt( size_type scope, const Key& key, value_t&& value ) {
318 return insertAt( scope, std::make_pair( key, std::forward<value_t>( value ) ) );
319 }
320
321 Value& operator[] ( const Key &key ) {
322 iterator slot = find( key );
323 if ( slot != end() ) return slot->second;
324 return insert( key, Value() ).first->second;
325 }
326
327 iterator erase( iterator pos ) {
328 MapType& scope = (*pos.scopes)[ pos.level ].map;
329 const typename iterator::wrapped_iterator& new_it = scope.erase( pos.it );
330 iterator it( *pos.scopes, new_it, pos.level );
331 return it.next_valid();
332 }
333
334 size_type count( const Key &key ) const {
335 size_type c = 0;
336 auto it = find( key );
337 auto end = cend();
338
339 while(it != end) {
340 c++;
341 it = findNext(it, key);
342 }
343
344 return c;
345 }
346
347};
348
349// Local Variables: //
350// tab-width: 4 //
351// mode: c++ //
352// compile-command: "make install" //
353// End: //
Note: See TracBrowser for help on using the repository browser.