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