source: src/Common/ScopedMap.h @ 6071efc

ADTast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 6071efc was 22f94a4, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Merge branch 'master' into new-ast

  • 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-> () const { 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.