source: src/GenPoly/ScopedMap.h @ 933667d

aaron-thesisarm-ehcleanup-dtorsctordeferred_resndemanglergc_noraiijacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newstringwith_gc
Last change on this file since 933667d was 933667d, checked in by Aaron Moss <a3moss@…>, 6 years ago

Bugfixes for ScopedMap?

  • Property mode set to 100644
File size: 7.4 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 <iterator>
20#include <map>
21#include <utility>
22#include <vector>
23
24namespace GenPoly {
25        /// A map where the items are placed into nested scopes;
26        /// inserted items are placed into the innermost scope, lookup looks from the innermost scope outward
27        template<typename Key, typename Value>
28        class ScopedMap {
29                typedef std::map< Key, Value > Scope;
30                typedef std::vector< Scope > ScopeList;
31
32                ScopeList scopes; ///< scoped list of maps
33        public:
34                typedef typename Scope::key_type key_type;
35                typedef typename Scope::mapped_type mapped_type;
36                typedef typename Scope::value_type value_type;
37                typedef typename ScopeList::size_type size_type;
38                typedef typename ScopeList::difference_type difference_type;
39                typedef typename Scope::reference reference;
40                typedef typename Scope::const_reference const_reference;
41                typedef typename Scope::pointer pointer;
42                typedef typename Scope::const_pointer const_pointer;
43               
44                class iterator : public std::iterator< std::bidirectional_iterator_tag,
45                                                       value_type > {
46                friend class ScopedMap;
47                friend class const_iterator;
48                        typedef typename std::map< Key, Value >::iterator wrapped_iterator;
49                        typedef typename std::vector< std::map< Key, Value > > scope_list;
50                        typedef typename scope_list::size_type size_type;
51
52                        iterator(scope_list const &_scopes, const wrapped_iterator &_it, size_type _i)
53                                : scopes(&_scopes), it(_it), i(_i) {}
54                public:
55                        iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
56                        iterator& operator= (const iterator &that) {
57                                scopes = that.scopes; i = that.i; it = that.it;
58                                return *this;
59                        }
60                       
61                        reference operator* () { return *it; }
62                        pointer operator-> () { return it.operator->(); }
63
64                        iterator& operator++ () {
65                                if ( it == (*scopes)[i].end() ) {
66                                        if ( i == 0 ) return *this;
67                                        --i;
68                                        it = (*scopes)[i].begin();
69                                        return *this;
70                                }
71                                ++it;
72                                return *this;
73                        }
74                        iterator& operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
75
76                        iterator& operator-- () {
77                                // may fail if this is the begin iterator; allowed by STL spec
78                                if ( it == (*scopes)[i].begin() ) {
79                                        ++i;
80                                        it = (*scopes)[i].end();
81                                }
82                                --it;
83                                return *this;
84                        }
85                        iterator& operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
86
87                        bool operator== (const iterator &that) {
88                                return scopes == that.scopes && i == that.i && it == that.it;
89                        }
90                        bool operator!= (const iterator &that) { return !( *this == that ); }
91
92                private:
93                        scope_list const *scopes;
94                        wrapped_iterator it;
95                        size_type i;
96                };
97
98                class const_iterator : public std::iterator< std::bidirectional_iterator_tag,
99                                                             value_type > {
100                friend class ScopedMap;
101                        typedef typename std::map< Key, Value >::iterator wrapped_iterator;
102                        typedef typename std::map< Key, Value >::const_iterator wrapped_const_iterator;
103                        typedef typename std::vector< std::map< Key, Value > > scope_list;
104                        typedef typename scope_list::size_type size_type;
105
106                        const_iterator(scope_list const &_scopes, const wrapped_const_iterator &_it, size_type _i)
107                                : scopes(&_scopes), it(_it), i(_i) {}
108                public:
109                        const_iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
110                        const_iterator(const const_iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
111                        const_iterator& operator= (const iterator &that) {
112                                scopes = that.scopes; i = that.i; it = that.it;
113                                return *this;
114                        }
115                        const_iterator& operator= (const const_iterator &that) {
116                                scopes = that.scopes; i = that.i; it = that.it;
117                                return *this;
118                        }
119
120                        const_reference operator* () { return *it; }
121                        const_pointer operator-> () { return it.operator->(); }
122
123                        const_iterator& operator++ () {
124                                if ( it == (*scopes)[i].end() ) {
125                                        if ( i == 0 ) return *this;
126                                        --i;
127                                        it = (*scopes)[i].begin();
128                                        return *this;
129                                }
130                                ++it;
131                                return *this;
132                        }
133                        const_iterator& operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
134
135                        const_iterator& operator-- () {
136                                // may fail if this is the begin iterator; allowed by STL spec
137                                if ( it == (*scopes)[i].begin() ) {
138                                        ++i;
139                                        it = (*scopes)[i].end();
140                                }
141                                --it;
142                                return *this;
143                        }
144                        const_iterator& operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
145
146                        bool operator== (const const_iterator &that) {
147                                return scopes == that.scopes && i == that.i && it == that.it;
148                        }
149                        bool operator!= (const const_iterator &that) { return !( *this == that ); }
150
151                private:
152                        scope_list const *scopes;
153                        wrapped_const_iterator it;
154                        size_type i;
155                };
156               
157                /// Starts a new scope
158                void beginScope() {
159                        Scope scope;
160                        scopes.push_back(scope);
161                }
162
163                /// Ends a scope; invalidates any iterators pointing to elements of that scope
164                void endScope() {
165                        scopes.pop_back();
166                }
167
168                /// Default constructor initializes with one scope
169                ScopedMap() { beginScope(); }
170
171                iterator begin() { return iterator(scopes, scopes.back().begin(), scopes.size()-1); }
172                const_iterator begin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1); }
173                const_iterator cbegin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1); }
174                iterator end() { return iterator(scopes, scopes[0].end(), 0); }
175                const_iterator end() const { return const_iterator(scopes, scopes[0].end(), 0); }
176                const_iterator cend() const { return const_iterator(scopes, scopes[0].end(), 0); }
177
178                /// Gets the index of the current scope (counted from 1)
179                size_type currentScope() const { return scopes.size(); }
180
181                /// Finds the given key in the outermost scope it occurs; returns end() for none such
182                iterator find( const Key &key ) {
183                        for ( size_type i = scopes.size() - 1; ; --i ) {
184                                typename Scope::iterator val = scopes[i].find( key );
185                                if ( val != scopes[i].end() ) return iterator( scopes, val, i );
186                                if ( i == 0 ) break;
187                        }
188                        return end();
189                }
190                const_iterator find( const Key &key ) const { return const_iterator( find( key ) ); }
191               
192                /// Finds the given key in the outermost scope inside the given scope where it occurs
193                iterator findNext( const_iterator &it, const Key &key ) {
194                        if ( it.i == 0 ) return end();
195                        for ( size_type i = it.i - 1; ; --i ) {
196                                typename Scope::iterator val = scopes[i].find( key );
197                                if ( val != scopes[i].end() ) return iterator( scopes, val, i );
198                                if ( i == 0 ) break;
199                        }
200                        return end();
201                }
202                const_iterator findNext( const_iterator &it, const Key &key ) const { return const_iterator( findNext( it, key ) ); }
203
204                /// Inserts the given key-value pair into the outermost scope
205                std::pair< iterator, bool > insert( const value_type &value ) {
206                        std::pair< typename Scope::iterator, bool > res = scopes.back().insert( value );
207                        return std::make_pair( iterator(scopes, res.first, scopes.size()-1), res.second );
208                }
209                std::pair< iterator, bool > insert( const Key &key, const Value &value ) { return insert( std::make_pair( key, value ) ); }
210               
211        };
212} // namespace GenPoly
213
214#endif // _SCOPEDMAP_H
215
216// Local Variables: //
217// tab-width: 4 //
218// mode: c++ //
219// compile-command: "make install" //
220// End: //
Note: See TracBrowser for help on using the repository browser.