[52bbd67] | 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 |
|
---|
[0531b5d] | 19 | #include <cassert>
|
---|
[52bbd67] | 20 | #include <iterator>
|
---|
| 21 | #include <map>
|
---|
| 22 | #include <utility>
|
---|
| 23 | #include <vector>
|
---|
| 24 |
|
---|
| 25 | namespace 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 |
|
---|
[5ba653c] | 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 |
|
---|
[52bbd67] | 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();
|
---|
[5ba653c] | 87 | } else {
|
---|
| 88 | ++it;
|
---|
[52bbd67] | 89 | }
|
---|
[5ba653c] | 90 | return next_valid();
|
---|
[52bbd67] | 91 | }
|
---|
[f6d4204] | 92 | iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
|
---|
[52bbd67] | 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;
|
---|
[5ba653c] | 101 | return prev_valid();
|
---|
[52bbd67] | 102 | }
|
---|
[f6d4204] | 103 | iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
|
---|
[52bbd67] | 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 |
|
---|
[5ba653c] | 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 |
|
---|
[52bbd67] | 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();
|
---|
[5ba653c] | 163 | } else {
|
---|
| 164 | ++it;
|
---|
[52bbd67] | 165 | }
|
---|
[5ba653c] | 166 | return next_valid();
|
---|
[52bbd67] | 167 | }
|
---|
[f6d4204] | 168 | const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
|
---|
[52bbd67] | 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;
|
---|
[5ba653c] | 177 | return prev_valid();
|
---|
[52bbd67] | 178 | }
|
---|
[f6d4204] | 179 | const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
|
---|
[52bbd67] | 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();
|
---|
[0531b5d] | 201 | assert( ! scopes.empty() );
|
---|
[52bbd67] | 202 | }
|
---|
| 203 |
|
---|
| 204 | /// Default constructor initializes with one scope
|
---|
| 205 | ScopedMap() { beginScope(); }
|
---|
| 206 |
|
---|
[5ba653c] | 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(); }
|
---|
[52bbd67] | 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 |
|
---|
[933667d] | 214 | /// Gets the index of the current scope (counted from 1)
|
---|
| 215 | size_type currentScope() const { return scopes.size(); }
|
---|
| 216 |
|
---|
[52bbd67] | 217 | /// Finds the given key in the outermost scope it occurs; returns end() for none such
|
---|
| 218 | iterator find( const Key &key ) {
|
---|
[933667d] | 219 | for ( size_type i = scopes.size() - 1; ; --i ) {
|
---|
[52bbd67] | 220 | typename Scope::iterator val = scopes[i].find( key );
|
---|
| 221 | if ( val != scopes[i].end() ) return iterator( scopes, val, i );
|
---|
[933667d] | 222 | if ( i == 0 ) break;
|
---|
[52bbd67] | 223 | }
|
---|
| 224 | return end();
|
---|
| 225 | }
|
---|
[0531b5d] | 226 | const_iterator find( const Key &key ) const {
|
---|
| 227 | return const_iterator( const_cast< ScopedMap< Key, Value >* >(this)->find( key ) );
|
---|
| 228 | }
|
---|
[52bbd67] | 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();
|
---|
[933667d] | 233 | for ( size_type i = it.i - 1; ; --i ) {
|
---|
[52bbd67] | 234 | typename Scope::iterator val = scopes[i].find( key );
|
---|
| 235 | if ( val != scopes[i].end() ) return iterator( scopes, val, i );
|
---|
[933667d] | 236 | if ( i == 0 ) break;
|
---|
[52bbd67] | 237 | }
|
---|
| 238 | return end();
|
---|
| 239 | }
|
---|
[0531b5d] | 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 | }
|
---|
[52bbd67] | 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 ) ); }
|
---|
[0531b5d] | 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 | }
|
---|
[52bbd67] | 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: //
|
---|