Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/GenPoly/ErasableScopedMap.h

    rc1fb3903 r6b0b624  
    2323
    2424namespace 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.
    33 template<typename Key, typename Value>
    34 class 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;
    42 public:
    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 );
    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         /// 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 
    139 template<typename Key, typename Value>
    140 class 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 
    167 public:
    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 
    206 private:
    207         ErasableScopedMap< Key, Value > const *map;
    208         wrapped_iterator it;
    209         size_type i;
    210 };
    211 
    212 template<typename Key, typename Value>
    213 class 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) {}
    240 public:
    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 
    283 private:
    284         ErasableScopedMap< Key, Value > const *map;
    285         wrapped_const_iterator it;
    286         size_type i;
    287 };
    288 
     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        };
    289277} // namespace GenPoly
    290278
Note: See TracChangeset for help on using the changeset viewer.