source: src/GenPoly/ScopedMap.h@ 2a4b088

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors ctor deferred_resn demangler enum forall-pointer-decay gc_noraii jacob/cs343-translation jenkins-sandbox memory new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new string with_gc
Last change on this file since 2a4b088 was 933667d, checked in by Aaron Moss <a3moss@…>, 10 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.