source: src/Common/ScopedMap.h @ 21a2a7d

ADTast-experimental
Last change on this file since 21a2a7d was 21a2a7d, checked in by Andrew Beach <ajbeach@…>, 16 months ago

Replaced ScopedMap::erase with a version that should avoid the order of declaration problems and also better reflects how it is actually used.

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