source: src/Common/ScopedMap.h @ 5408b59

ADTast-experimental
Last change on this file since 5408b59 was df00c78, checked in by Peter A. Buhr <pabuhr@…>, 2 years ago

formatting

  • 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 : 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        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, value_type > {
61        friend class ScopedMap;
62        friend class const_iterator;
63                typedef typename ScopedMap::MapType::iterator wrapped_iterator;
64                typedef typename ScopedMap::ScopeList scope_list;
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 {
69                        return it != (*scopes)[level].map.end();
70                }
71
72                /// Increments on invalid
73                iterator & next_valid() {
74                        if ( ! is_valid() ) { ++(*this); }
75                        return *this;
76                }
77
78                /// Decrements on invalid
79                iterator & prev_valid() {
80                        if ( ! is_valid() ) { --(*this); }
81                        return *this;
82                }
83
84                iterator(scope_list & _scopes, const wrapped_iterator & _it, size_type inLevel)
85                        : scopes(&_scopes), it(_it), level(inLevel) {}
86        public:
87                iterator(const iterator & that) : scopes(that.scopes), it(that.it), level(that.level) {}
88                iterator & operator= (const iterator & that) {
89                        scopes = that.scopes; level = that.level; it = that.it;
90                        return *this;
91                }
92
93                reference operator* () { return *it; }
94                pointer operator-> () const { return it.operator->(); }
95
96                iterator & operator++ () {
97                        if ( it == (*scopes)[level].map.end() ) {
98                                if ( level == 0 ) return *this;
99                                --level;
100                                it = (*scopes)[level].map.begin();
101                        } else {
102                                ++it;
103                        }
104                        return next_valid();
105                }
106                iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
107
108                iterator & operator-- () {
109                        // may fail if this is the begin iterator; allowed by STL spec
110                        if ( it == (*scopes)[level].map.begin() ) {
111                                ++level;
112                                it = (*scopes)[level].map.end();
113                        }
114                        --it;
115                        return prev_valid();
116                }
117                iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
118
119                bool operator== (const iterator & that) const {
120                        return scopes == that.scopes && level == that.level && it == that.it;
121                }
122                bool operator!= (const iterator & that) const { return !( *this == that ); }
123
124                size_type get_level() const { return level; }
125
126                Note & get_note() { return (*scopes)[level].note; }
127                const Note & get_note() const { return (*scopes)[level].note; }
128
129        private:
130                scope_list *scopes;
131                wrapped_iterator it;
132                size_type level;
133        };
134
135        class const_iterator : public std::iterator< std::bidirectional_iterator_tag,
136                                                     value_type > {
137        friend class ScopedMap;
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;
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 {
145                        return it != (*scopes)[level].map.end();
146                }
147
148                /// Increments on invalid
149                const_iterator & next_valid() {
150                        if ( ! is_valid() ) { ++(*this); }
151                        return *this;
152                }
153
154                /// Decrements on invalid
155                const_iterator & prev_valid() {
156                        if ( ! is_valid() ) { --(*this); }
157                        return *this;
158                }
159
160                const_iterator(scope_list const & _scopes, const wrapped_const_iterator & _it, size_type inLevel)
161                        : scopes(&_scopes), it(_it), level(inLevel) {}
162        public:
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) {
166                        scopes = that.scopes; level = that.level; it = that.it;
167                        return *this;
168                }
169                const_iterator & operator= (const const_iterator & that) {
170                        scopes = that.scopes; level = that.level; it = that.it;
171                        return *this;
172                }
173
174                const_reference operator* () { return *it; }
175                const_pointer operator-> () { return it.operator->(); }
176
177                const_iterator & operator++ () {
178                        if ( it == (*scopes)[level].map.end() ) {
179                                if ( level == 0 ) return *this;
180                                --level;
181                                it = (*scopes)[level].map.begin();
182                        } else {
183                                ++it;
184                        }
185                        return next_valid();
186                }
187                const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
188
189                const_iterator & operator-- () {
190                        // may fail if this is the begin iterator; allowed by STL spec
191                        if ( it == (*scopes)[level].map.begin() ) {
192                                ++level;
193                                it = (*scopes)[level].map.end();
194                        }
195                        --it;
196                        return prev_valid();
197                }
198                const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
199
200                bool operator== (const const_iterator & that) const {
201                        return scopes == that.scopes && level == that.level && it == that.it;
202                }
203                bool operator!= (const const_iterator & that) const { return !( *this == that ); }
204
205                size_type get_level() const { return level; }
206
207                const Note & get_note() const { return (*scopes)[level].note; }
208
209        private:
210                scope_list const *scopes;
211                wrapped_const_iterator it;
212                size_type level;
213        };
214
215        /// Starts a new scope
216        void beginScope() {
217                scopes.emplace_back();
218        }
219
220        // Starts a new scope with the given note
221        template<typename N>
222        void beginScope( N && n ) {
223                scopes.emplace_back( std::forward<N>(n) );
224        }
225
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
233        ScopedMap() : scopes() { beginScope(); }
234
235        /// Constructs with a given note on the outermost scope
236        template<typename N>
237        ScopedMap( N && n ) : scopes() { beginScope(std::forward<N>(n)); }
238
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); }
245
246        /// Gets the index of the current scope (counted from 1)
247        size_type currentScope() const { return scopes.size() - 1; }
248
249        /// Gets the note at the given scope
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; }
254
255        /// Finds the given key in the outermost scope it occurs; returns end() for none such
256        iterator find( const Key & key ) {
257                for ( size_type i = scopes.size() - 1; ; --i ) {
258                        typename MapType::iterator val = scopes[i].map.find( key );
259                        if ( val != scopes[i].map.end() ) return iterator( scopes, val, i );
260                        if ( i == 0 ) break;
261                }
262                return end();
263        }
264        const_iterator find( const Key & key ) const {
265                        return const_iterator( const_cast< ScopedMap< Key, Value, Note >* >(this)->find( key ) );
266        }
267
268        /// Finds the given key in the provided scope; returns end() for none such
269        iterator findAt( size_type scope, const Key & key ) {
270                typename MapType::iterator val = scopes[scope].map.find( key );
271                if ( val != scopes[scope].map.end() ) return iterator( scopes, val, scope );
272                return end();
273        }
274        const_iterator findAt( size_type scope, const Key & key ) const {
275                return const_iterator( const_cast< ScopedMap< Key, Value, Note >* >(this)->findAt( scope, key ) );
276        }
277
278        /// Finds the given key in the outermost scope inside the given scope where it occurs
279        iterator findNext( const_iterator & it, const Key & key ) {
280                if ( it.level == 0 ) return end();
281                for ( size_type i = it.level - 1; ; --i ) {
282                        typename MapType::iterator val = scopes[i].map.find( key );
283                        if ( val != scopes[i].map.end() ) return iterator( scopes, val, i );
284                        if ( i == 0 ) break;
285                }
286                return end();
287        }
288        const_iterator findNext( const_iterator & it, const Key & key ) const {
289                        return const_iterator( const_cast< ScopedMap< Key, Value, Note >* >(this)->findNext( it, key ) );
290        }
291
292        /// Inserts the given key-value pair into the outermost scope
293        template< typename value_type_t >
294        std::pair< iterator, bool > insert( value_type_t && value ) {
295                std::pair< typename MapType::iterator, bool > res = scopes.back().map.insert( std::forward<value_type_t>( value ) );
296                return std::make_pair( iterator(scopes, std::move( res.first ), scopes.size()-1), std::move( res.second ) );
297        }
298
299        template< typename value_type_t >
300        std::pair< iterator, bool > insert( iterator at, value_type_t && value ) {
301                MapType & scope = (*at.scopes)[ at.level ].map;
302                std::pair< typename MapType::iterator, bool > res = scope.insert( std::forward<value_type_t>( value ) );
303                return std::make_pair( iterator(scopes, std::move( res.first ), at.level), std::move( res.second ) );
304        }
305
306        template< typename value_t >
307        std::pair< iterator, bool > insert( const Key & key, value_t && value ) { return insert( std::make_pair( key, std::forward<value_t>( value ) ) ); }
308
309        template< typename value_type_t >
310        std::pair< iterator, bool > insertAt( size_type scope, value_type_t && value ) {
311                std::pair< typename MapType::iterator, bool > res = scopes.at(scope).map.insert( std::forward<value_type_t>( value ) );
312                return std::make_pair( iterator(scopes, std::move( res.first ), scope), std::move( res.second ) );
313        }
314
315        template< typename value_t >
316        std::pair< iterator, bool > insertAt( size_type scope, const Key & key, value_t && value ) {
317                return insertAt( scope, std::make_pair( key, std::forward<value_t>( value ) ) );
318        }
319
320        Value & operator[] ( const Key & key ) {
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 ) {
327                MapType & scope = (*pos.scopes)[ pos.level ].map;
328                const typename iterator::wrapped_iterator & new_it = scope.erase( pos.it );
329                iterator it( *pos.scopes, new_it, pos.level );
330                return it.next_valid();
331        }
332
333        size_type count( const Key & key ) const {
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: //
Note: See TracBrowser for help on using the repository browser.