source: src/GenPoly/ErasableScopedMap.h@ 1b54b54

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr persistent-indexer pthread-emulation qualifiedEnum
Last change on this file since 1b54b54 was 6b0b624, checked in by Peter A. Buhr <pabuhr@…>, 8 years ago

change #ifndef to #pragma once
  • Property mode set to 100644
File size: 9.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 : Peter A. Buhr
12// Last Modified On : Sat Jul 22 09:23: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
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 /// erasing a key means that find() will no longer report any instance of the key in a scope further
28 /// out, but the erasure itself is scoped. Key erasure works by inserting a sentinal value into the
29 /// value field, and thus only works for Value types where a meaningful sentinal can be chosen.
30 template<typename Key, typename Value>
31 class ErasableScopedMap {
32 typedef std::map< Key, Value > Scope;
33 typedef std::vector< Scope > ScopeList;
34
35 ScopeList scopes; ///< scoped list of maps
36 Value erased; ///< sentinal value for erased keys
37 public:
38 typedef typename Scope::key_type key_type;
39 typedef typename Scope::mapped_type mapped_type;
40 typedef typename Scope::value_type value_type;
41 typedef typename ScopeList::size_type size_type;
42 typedef typename ScopeList::difference_type difference_type;
43 typedef typename Scope::reference reference;
44 typedef typename Scope::const_reference const_reference;
45 typedef typename Scope::pointer pointer;
46 typedef typename Scope::const_pointer const_pointer;
47
48 class iterator : public std::iterator< std::bidirectional_iterator_tag,
49 value_type > {
50 friend class ErasableScopedMap;
51 friend class const_iterator;
52 typedef typename std::map< Key, Value >::iterator wrapped_iterator;
53 typedef typename std::vector< std::map< Key, Value > > scope_list;
54 typedef typename scope_list::size_type size_type;
55
56 /// Checks if this iterator points to a valid item
57 bool is_valid() const {
58 return it != map->scopes[i].end() && it->second != map->erased;
59 }
60
61 /// Increments on invalid
62 iterator& next_valid() {
63 if ( ! is_valid() ) { ++(*this); }
64 return *this;
65 }
66
67 /// Decrements on invalid
68 iterator& prev_valid() {
69 if ( ! is_valid() ) { --(*this); }
70 return *this;
71 }
72
73 iterator(ErasableScopedMap< Key, Value > const &_map, const wrapped_iterator &_it, size_type _i)
74 : map(&_map), it(_it), i(_i) {}
75
76 public:
77 iterator(const iterator &that) : map(that.map), it(that.it), i(that.i) {}
78 iterator& operator= (const iterator &that) {
79 map = that.map; i = that.i; it = that.it;
80 return *this;
81 }
82
83 reference operator* () { return *it; }
84 pointer operator-> () { return it.operator->(); }
85
86 iterator& operator++ () {
87 if ( it == map->scopes[i].end() ) {
88 if ( i == 0 ) return *this;
89 --i;
90 it = map->scopes[i].begin();
91 } else {
92 ++it;
93 }
94 return next_valid();
95 }
96 iterator& operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
97
98 iterator& operator-- () {
99 // may fail if this is the begin iterator; allowed by STL spec
100 if ( it == map->scopes[i].begin() ) {
101 ++i;
102 it = map->scopes[i].end();
103 }
104 --it;
105 return prev_valid();
106 }
107 iterator& operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
108
109 bool operator== (const iterator &that) {
110 return map == that.map && i == that.i && it == that.it;
111 }
112 bool operator!= (const iterator &that) { return !( *this == that ); }
113
114 private:
115 ErasableScopedMap< Key, Value > const *map;
116 wrapped_iterator it;
117 size_type i;
118 };
119
120 class const_iterator : public std::iterator< std::bidirectional_iterator_tag,
121 value_type > {
122 friend class ErasableScopedMap;
123 typedef typename std::map< Key, Value >::iterator wrapped_iterator;
124 typedef typename std::map< Key, Value >::const_iterator wrapped_const_iterator;
125 typedef typename std::vector< std::map< Key, Value > > scope_list;
126 typedef typename scope_list::size_type size_type;
127
128 /// Checks if this iterator points to a valid item
129 bool is_valid() const {
130 return it != map->scopes[i].end() && it->second != map->erased;
131 }
132
133 /// Increments on invalid
134 const_iterator& next_valid() {
135 if ( ! is_valid() ) { ++(*this); }
136 return *this;
137 }
138
139 /// Decrements on invalid
140 const_iterator& prev_valid() {
141 if ( ! is_valid() ) { --(*this); }
142 return *this;
143 }
144
145 const_iterator(ErasableScopedMap< Key, Value > const &_map, const wrapped_const_iterator &_it, size_type _i)
146 : map(&_map), it(_it), i(_i) {}
147 public:
148 const_iterator(const iterator &that) : map(that.map), it(that.it), i(that.i) {}
149 const_iterator(const const_iterator &that) : map(that.map), it(that.it), i(that.i) {}
150 const_iterator& operator= (const iterator &that) {
151 map = that.map; i = that.i; it = that.it;
152 return *this;
153 }
154 const_iterator& operator= (const const_iterator &that) {
155 map = that.map; i = that.i; it = that.it;
156 return *this;
157 }
158
159 const_reference operator* () { return *it; }
160 const_pointer operator-> () { return it.operator->(); }
161
162 const_iterator& operator++ () {
163 if ( it == map->scopes[i].end() ) {
164 if ( i == 0 ) return *this;
165 --i;
166 it = map->scopes[i].begin();
167 } else {
168 ++it;
169 }
170 return next_valid();
171 }
172 const_iterator& operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
173
174 const_iterator& operator-- () {
175 // may fail if this is the begin iterator; allowed by STL spec
176 if ( it == map->scopes[i].begin() ) {
177 ++i;
178 it = map->scopes[i].end();
179 }
180 --it;
181 return prev_valid();
182 }
183 const_iterator& operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
184
185 bool operator== (const const_iterator &that) {
186 return map == that.map && i == that.i && it == that.it;
187 }
188 bool operator!= (const const_iterator &that) { return !( *this == that ); }
189
190 private:
191 ErasableScopedMap< Key, Value > const *map;
192 wrapped_const_iterator it;
193 size_type i;
194 };
195
196 /// Starts a new scope
197 void beginScope() {
198 Scope scope;
199 scopes.push_back(scope);
200 }
201
202 /// Ends a scope; invalidates any iterators pointing to elements of that scope
203 void endScope() {
204 scopes.pop_back();
205 assert( ! scopes.empty() );
206 }
207
208 /// Default constructor initializes with one scope
209 ErasableScopedMap( const Value &erased_ ) : erased( erased_ ) { beginScope(); }
210
211 iterator begin() { return iterator(*this, scopes.back().begin(), scopes.size()-1).next_valid(); }
212 const_iterator begin() const { return const_iterator(*this, scopes.back().begin(), scopes.size()-1).next_valid(); }
213 const_iterator cbegin() const { return const_iterator(*this, scopes.back().begin(), scopes.size()-1).next_valid(); }
214 iterator end() { return iterator(*this, scopes[0].end(), 0); }
215 const_iterator end() const { return const_iterator(*this, scopes[0].end(), 0); }
216 const_iterator cend() const { return const_iterator(*this, scopes[0].end(), 0); }
217
218 /// Gets the index of the current scope (counted from 1)
219 size_type currentScope() const { return scopes.size(); }
220
221 /// Finds the given key in the outermost scope it occurs; returns end() for none such
222 iterator find( const Key &key ) {
223 for ( size_type i = scopes.size() - 1; ; --i ) {
224 typename Scope::iterator val = scopes[i].find( key );
225 if ( val != scopes[i].end() ) {
226 return val->second == erased ? end() : iterator( *this, val, i );
227 }
228 if ( i == 0 ) break;
229 }
230 return end();
231 }
232 const_iterator find( const Key &key ) const {
233 return const_iterator( const_cast< ErasableScopedMap< Key, Value >* >(this)->find( key ) );
234 }
235
236 /// Finds the given key in the outermost scope inside the given scope where it occurs
237 iterator findNext( const_iterator &it, const Key &key ) {
238 if ( it.i == 0 ) return end();
239 for ( size_type i = it.i - 1; ; --i ) {
240 typename Scope::iterator val = scopes[i].find( key );
241 if ( val != scopes[i].end() ) {
242 return val->second == erased ? end() : iterator( *this, val, i );
243 }
244 if ( i == 0 ) break;
245 }
246 return end();
247 }
248 const_iterator findNext( const_iterator &it, const Key &key ) const {
249 return const_iterator( const_cast< ErasableScopedMap< Key, Value >* >(this)->findNext( it, key ) );
250 }
251
252 /// Inserts the given key-value pair into the outermost scope
253 std::pair< iterator, bool > insert( const value_type &value ) {
254 std::pair< typename Scope::iterator, bool > res = scopes.back().insert( value );
255 return std::make_pair( iterator(*this, res.first, scopes.size()-1), res.second );
256 }
257 std::pair< iterator, bool > insert( const Key &key, const Value &value ) { return insert( std::make_pair( key, value ) ); }
258
259 /// Marks the given element as erased from this scope inward; returns 1 for erased an element, 0 otherwise
260 size_type erase( const Key &key ) {
261 typename Scope::iterator val = scopes.back().find( key );
262 if ( val != scopes.back().end() ) {
263 val->second = erased;
264 return 1;
265 } else {
266 scopes.back().insert( val, std::make_pair( key, erased ) );
267 return 0;
268 }
269 }
270
271 Value& operator[] ( const Key &key ) {
272 iterator slot = find( key );
273 if ( slot != end() ) return slot->second;
274 return insert( key, Value() ).first->second;
275 }
276 };
277} // namespace GenPoly
278
279// Local Variables: //
280// tab-width: 4 //
281// mode: c++ //
282// compile-command: "make install" //
283// End: //
Note: See TracBrowser for help on using the repository browser.