Changeset c1fb3903


Ignore:
Timestamp:
Nov 14, 2022, 1:51:50 PM (2 years ago)
Author:
Andrew Beach <ajbeach@…>
Branches:
ADT, ast-experimental, master
Children:
1fb09ef
Parents:
19a8c40
Message:

Reformat/re-indent the ErasableScopedMap?. This should make it easier to follow and update to the current style.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/GenPoly/ErasableScopedMap.h

    r19a8c40 rc1fb3903  
    2323
    2424namespace 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;
     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 bidirection iterators, defined 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 );
    5988                        }
    60 
    61                         /// Increments on invalid
    62                         iterator& next_valid() {
    63                                 if ( ! is_valid() ) { ++(*this); }
    64                                 return *this;
     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 );
    65104                        }
    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         };
     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        /// Marks the given element as erased from this scope inward; returns 1 for erased an element, 0 otherwise
     121        size_type erase( const Key &key ) {
     122                typename Scope::iterator val = scopes.back().find( key );
     123                if ( val != scopes.back().end() ) {
     124                        val->second = erased;
     125                        return 1;
     126                } else {
     127                        scopes.back().insert( val, std::make_pair( key, erased ) );
     128                        return 0;
     129                }
     130        }
     131
     132        Value& operator[] ( const Key &key ) {
     133                iterator slot = find( key );
     134                if ( slot != end() ) return slot->second;
     135                return insert( key, Value() ).first->second;
     136        }
     137};
     138
     139template<typename Key, typename Value>
     140class ErasableScopedMap<Key, Value>::iterator :
     141                public std::iterator< std::bidirectional_iterator_tag, value_type > {
     142        friend class ErasableScopedMap;
     143        typedef typename std::map< Key, Value >::iterator wrapped_iterator;
     144        typedef typename std::vector< std::map< Key, Value > > scope_list;
     145        typedef typename scope_list::size_type size_type;
     146
     147        /// Checks if this iterator points to a valid item
     148        bool is_valid() const {
     149                return it != map->scopes[i].end() && it->second != map->erased;
     150        }
     151
     152        /// Increments on invalid
     153        iterator& next_valid() {
     154                if ( ! is_valid() ) { ++(*this); }
     155                return *this;
     156        }
     157
     158        /// Decrements on invalid
     159        iterator& prev_valid() {
     160                if ( ! is_valid() ) { --(*this); }
     161                return *this;
     162        }
     163
     164        iterator(ErasableScopedMap< Key, Value > const &_map, const wrapped_iterator &_it, size_type _i)
     165                        : map(&_map), it(_it), i(_i) {}
     166
     167public:
     168        iterator(const iterator &that) : map(that.map), it(that.it), i(that.i) {}
     169        iterator& operator= (const iterator &that) {
     170                map = that.map; i = that.i; it = that.it;
     171                return *this;
     172        }
     173
     174        reference operator* () { return *it; }
     175        pointer operator-> () { return it.operator->(); }
     176
     177        iterator& operator++ () {
     178                if ( it == map->scopes[i].end() ) {
     179                        if ( i == 0 ) return *this;
     180                        --i;
     181                        it = map->scopes[i].begin();
     182                } else {
     183                        ++it;
     184                }
     185                return next_valid();
     186        }
     187
     188        iterator& operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
     189
     190        iterator& operator-- () {
     191                // may fail if this is the begin iterator; allowed by STL spec
     192                if ( it == map->scopes[i].begin() ) {
     193                        ++i;
     194                        it = map->scopes[i].end();
     195                }
     196                --it;
     197                return prev_valid();
     198        }
     199        iterator& operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
     200
     201        bool operator== (const iterator &that) {
     202                return map == that.map && i == that.i && it == that.it;
     203        }
     204        bool operator!= (const iterator &that) { return !( *this == that ); }
     205
     206private:
     207        ErasableScopedMap< Key, Value > const *map;
     208        wrapped_iterator it;
     209        size_type i;
     210};
     211
     212template<typename Key, typename Value>
     213class ErasableScopedMap<Key, Value>::const_iterator :
     214                public std::iterator< std::bidirectional_iterator_tag, value_type > {
     215        friend class ErasableScopedMap;
     216        typedef typename std::map< Key, Value >::iterator wrapped_iterator;
     217        typedef typename std::map< Key, Value >::const_iterator wrapped_const_iterator;
     218        typedef typename std::vector< std::map< Key, Value > > scope_list;
     219        typedef typename scope_list::size_type size_type;
     220
     221        /// Checks if this iterator points to a valid item
     222        bool is_valid() const {
     223                return it != map->scopes[i].end() && it->second != map->erased;
     224        }
     225
     226        /// Increments on invalid
     227        const_iterator& next_valid() {
     228                if ( ! is_valid() ) { ++(*this); }
     229                return *this;
     230        }
     231
     232        /// Decrements on invalid
     233        const_iterator& prev_valid() {
     234                if ( ! is_valid() ) { --(*this); }
     235                return *this;
     236        }
     237
     238        const_iterator(ErasableScopedMap< Key, Value > const &_map, const wrapped_const_iterator &_it, size_type _i)
     239                        : map(&_map), it(_it), i(_i) {}
     240public:
     241        const_iterator(const iterator &that) : map(that.map), it(that.it), i(that.i) {}
     242        const_iterator(const const_iterator &that) : map(that.map), it(that.it), i(that.i) {}
     243        const_iterator& operator= (const iterator &that) {
     244                map = that.map; i = that.i; it = that.it;
     245                return *this;
     246        }
     247        const_iterator& operator= (const const_iterator &that) {
     248                map = that.map; i = that.i; it = that.it;
     249                return *this;
     250        }
     251
     252        const_reference operator* () { return *it; }
     253        const_pointer operator-> () { return it.operator->(); }
     254
     255        const_iterator& operator++ () {
     256                if ( it == map->scopes[i].end() ) {
     257                        if ( i == 0 ) return *this;
     258                        --i;
     259                        it = map->scopes[i].begin();
     260                } else {
     261                        ++it;
     262                }
     263                return next_valid();
     264        }
     265        const_iterator& operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
     266
     267        const_iterator& operator-- () {
     268                // may fail if this is the begin iterator; allowed by STL spec
     269                if ( it == map->scopes[i].begin() ) {
     270                        ++i;
     271                        it = map->scopes[i].end();
     272                }
     273                --it;
     274                return prev_valid();
     275        }
     276        const_iterator& operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
     277
     278        bool operator== (const const_iterator &that) {
     279                return map == that.map && i == that.i && it == that.it;
     280        }
     281        bool operator!= (const const_iterator &that) { return !( *this == that ); }
     282
     283private:
     284        ErasableScopedMap< Key, Value > const *map;
     285        wrapped_const_iterator it;
     286        size_type i;
     287};
     288
    277289} // namespace GenPoly
    278290
Note: See TracChangeset for help on using the changeset viewer.