source: src/Common/ScopedMap.h @ 6b0b624

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 6b0b624 was 6b0b624, checked in by Peter A. Buhr <pabuhr@…>, 4 years ago

change #ifndef to #pragma once

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