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