source: src/GenPoly/ScopedMap.h @ f6d4204

aaron-thesisarm-ehcleanup-dtorsctordeferred_resndemanglerenumforall-pointer-decaygc_noraiijacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since f6d4204 was f6d4204, checked in by Aaron Moss <a3moss@…>, 6 years ago

Small bugfix for ScopedSet/Map? iterators

  • Property mode set to 100644
File size: 8.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 : Aaron B. Moss
12// Last Modified On : Wed Dec 2 11:37:00 2015
13// Update Count     : 1
14//
15
16#ifndef _SCOPEDMAP_H
17#define _SCOPEDMAP_H
18
19#include <cassert>
20#include <iterator>
21#include <map>
22#include <utility>
23#include <vector>
24
25namespace GenPoly {
26        /// A map where the items are placed into nested scopes;
27        /// inserted items are placed into the innermost scope, lookup looks from the innermost scope outward
28        template<typename Key, typename Value>
29        class ScopedMap {
30                typedef std::map< Key, Value > Scope;
31                typedef std::vector< Scope > ScopeList;
32
33                ScopeList scopes; ///< scoped list of maps
34        public:
35                typedef typename Scope::key_type key_type;
36                typedef typename Scope::mapped_type mapped_type;
37                typedef typename Scope::value_type value_type;
38                typedef typename ScopeList::size_type size_type;
39                typedef typename ScopeList::difference_type difference_type;
40                typedef typename Scope::reference reference;
41                typedef typename Scope::const_reference const_reference;
42                typedef typename Scope::pointer pointer;
43                typedef typename Scope::const_pointer const_pointer;
44               
45                class iterator : public std::iterator< std::bidirectional_iterator_tag,
46                                                       value_type > {
47                friend class ScopedMap;
48                friend class const_iterator;
49                        typedef typename std::map< Key, Value >::iterator wrapped_iterator;
50                        typedef typename std::vector< std::map< Key, Value > > scope_list;
51                        typedef typename scope_list::size_type size_type;
52
53                        /// Checks if this iterator points to a valid item
54                        bool is_valid() const {
55                                return it != (*scopes)[i].end();
56                        }
57
58                        /// Increments on invalid
59                        iterator& next_valid() {
60                                if ( ! is_valid() ) { ++(*this); }
61                                return *this;
62                        }
63
64                        /// Decrements on invalid
65                        iterator& prev_valid() {
66                                if ( ! is_valid() ) { --(*this); }
67                                return *this;
68                        }
69
70                        iterator(scope_list const &_scopes, const wrapped_iterator &_it, size_type _i)
71                                : scopes(&_scopes), it(_it), i(_i) {}
72                public:
73                        iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
74                        iterator& operator= (const iterator &that) {
75                                scopes = that.scopes; i = that.i; it = that.it;
76                                return *this;
77                        }
78                       
79                        reference operator* () { return *it; }
80                        pointer operator-> () { return it.operator->(); }
81
82                        iterator& operator++ () {
83                                if ( it == (*scopes)[i].end() ) {
84                                        if ( i == 0 ) return *this;
85                                        --i;
86                                        it = (*scopes)[i].begin();
87                                } else {
88                                        ++it;
89                                }
90                                return next_valid();
91                        }
92                        iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
93
94                        iterator& operator-- () {
95                                // may fail if this is the begin iterator; allowed by STL spec
96                                if ( it == (*scopes)[i].begin() ) {
97                                        ++i;
98                                        it = (*scopes)[i].end();
99                                }
100                                --it;
101                                return prev_valid();
102                        }
103                        iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
104
105                        bool operator== (const iterator &that) {
106                                return scopes == that.scopes && i == that.i && it == that.it;
107                        }
108                        bool operator!= (const iterator &that) { return !( *this == that ); }
109
110                private:
111                        scope_list const *scopes;
112                        wrapped_iterator it;
113                        size_type i;
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)[i].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 _i)
142                                : scopes(&_scopes), it(_it), i(_i) {}
143                public:
144                        const_iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
145                        const_iterator(const const_iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
146                        const_iterator& operator= (const iterator &that) {
147                                scopes = that.scopes; i = that.i; it = that.it;
148                                return *this;
149                        }
150                        const_iterator& operator= (const const_iterator &that) {
151                                scopes = that.scopes; i = that.i; 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)[i].end() ) {
160                                        if ( i == 0 ) return *this;
161                                        --i;
162                                        it = (*scopes)[i].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)[i].begin() ) {
173                                        ++i;
174                                        it = (*scopes)[i].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) {
182                                return scopes == that.scopes && i == that.i && it == that.it;
183                        }
184                        bool operator!= (const const_iterator &that) { return !( *this == that ); }
185
186                private:
187                        scope_list const *scopes;
188                        wrapped_const_iterator it;
189                        size_type i;
190                };
191               
192                /// Starts a new scope
193                void beginScope() {
194                        Scope scope;
195                        scopes.push_back(scope);
196                }
197
198                /// Ends a scope; invalidates any iterators pointing to elements of that scope
199                void endScope() {
200                        scopes.pop_back();
201                        assert( ! scopes.empty() );
202                }
203
204                /// Default constructor initializes with one scope
205                ScopedMap() { beginScope(); }
206
207                iterator begin() { return iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
208                const_iterator begin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
209                const_iterator cbegin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
210                iterator end() { return iterator(scopes, scopes[0].end(), 0); }
211                const_iterator end() const { return const_iterator(scopes, scopes[0].end(), 0); }
212                const_iterator cend() const { return const_iterator(scopes, scopes[0].end(), 0); }
213
214                /// Gets the index of the current scope (counted from 1)
215                size_type currentScope() const { return scopes.size(); }
216
217                /// Finds the given key in the outermost scope it occurs; returns end() for none such
218                iterator find( const Key &key ) {
219                        for ( size_type i = scopes.size() - 1; ; --i ) {
220                                typename Scope::iterator val = scopes[i].find( key );
221                                if ( val != scopes[i].end() ) return iterator( scopes, val, i );
222                                if ( i == 0 ) break;
223                        }
224                        return end();
225                }
226                const_iterator find( const Key &key ) const {
227                                return const_iterator( const_cast< ScopedMap< Key, Value >* >(this)->find( key ) );
228                }
229               
230                /// Finds the given key in the outermost scope inside the given scope where it occurs
231                iterator findNext( const_iterator &it, const Key &key ) {
232                        if ( it.i == 0 ) return end();
233                        for ( size_type i = it.i - 1; ; --i ) {
234                                typename Scope::iterator val = scopes[i].find( key );
235                                if ( val != scopes[i].end() ) return iterator( scopes, val, i );
236                                if ( i == 0 ) break;
237                        }
238                        return end();
239                }
240                const_iterator findNext( const_iterator &it, const Key &key ) const {
241                                return const_iterator( const_cast< ScopedMap< Key, Value >* >(this)->findNext( it, key ) );
242                }
243
244                /// Inserts the given key-value pair into the outermost scope
245                std::pair< iterator, bool > insert( const value_type &value ) {
246                        std::pair< typename Scope::iterator, bool > res = scopes.back().insert( value );
247                        return std::make_pair( iterator(scopes, res.first, scopes.size()-1), res.second );
248                }
249                std::pair< iterator, bool > insert( const Key &key, const Value &value ) { return insert( std::make_pair( key, value ) ); }
250
251                Value& operator[] ( const Key &key ) {
252                        iterator slot = find( key );
253                        if ( slot != end() ) return slot->second;
254                        return insert( key, Value() ).first->second;
255                }
256        };
257} // namespace GenPoly
258
259#endif // _SCOPEDMAP_H
260
261// Local Variables: //
262// tab-width: 4 //
263// mode: c++ //
264// compile-command: "make install" //
265// End: //
Note: See TracBrowser for help on using the repository browser.