source: src/Common/ScopedMap.h @ 6253fc3

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexerpthread-emulationqualifiedEnum
Last change on this file since 6253fc3 was 6253fc3, checked in by Aaron Moss <a3moss@…>, 5 years ago

Add annotation field to ScopedMap?, annotate TypedefTable? with int

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