source: src/GenPoly/ErasableScopedMap.h @ e9b5043

ADTast-experimental
Last change on this file since e9b5043 was e9b5043, checked in by Andrew Beach <ajbeach@…>, 14 months ago

Added contains to some of our containers. Also changed some code to use the new method.

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