Changeset 85dd381 for src


Ignore:
Timestamp:
Feb 3, 2023, 10:13:49 AM (15 months ago)
Author:
Andrew Beach <ajbeach@…>
Branches:
ADT, ast-experimental, master
Children:
db9d7a9
Parents:
98a2b1dc
Message:

Fixed indentation in ScopedSet? and moved the iterator details to the bottom of the file.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/GenPoly/ScopedSet.h

    r98a2b1dc r85dd381  
    2121
    2222namespace GenPoly {
    23         /// A set where the items are placed into nested scopes;
    24         /// inserted items are placed into the innermost scope, lookup looks from the innermost scope outward
    25         template<typename Value>
    26         class ScopedSet {
    27                 typedef std::set< Value > Scope;
    28                 typedef std::vector< Scope > ScopeList;
    29 
    30                 ScopeList scopes; ///< scoped list of sets
    31         public:
    32                 typedef typename Scope::key_type key_type;
    33                 typedef typename Scope::value_type value_type;
    34                 typedef typename ScopeList::size_type size_type;
    35                 typedef typename ScopeList::difference_type difference_type;
    36                 typedef typename Scope::reference reference;
    37                 typedef typename Scope::const_reference const_reference;
    38                 typedef typename Scope::pointer pointer;
    39                 typedef typename Scope::const_pointer const_pointer;
    40 
    41                 class iterator : public std::iterator< std::bidirectional_iterator_tag,
    42                                                        value_type > {
    43                 friend class ScopedSet;
    44                 friend class const_iterator;
    45                         typedef typename std::set< Value >::iterator wrapped_iterator;
    46                         typedef typename std::vector< std::set< Value > > scope_list;
    47                         typedef typename scope_list::size_type size_type;
    48 
    49                         /// Checks if this iterator points to a valid item
    50                         bool is_valid() const {
    51                                 return it != (*scopes)[i].end();
    52                         }
    53 
    54                         /// Increments on invalid
    55                         iterator& next_valid() {
    56                                 if ( ! is_valid() ) { ++(*this); }
    57                                 return *this;
    58                         }
    59 
    60                         /// Decrements on invalid
    61                         iterator& prev_valid() {
    62                                 if ( ! is_valid() ) { --(*this); }
    63                                 return *this;
    64                         }
    65 
    66                         iterator(scope_list const &_scopes, const wrapped_iterator &_it, size_type _i)
    67                                 : scopes(&_scopes), it(_it), i(_i) {}
    68                 public:
    69                         iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
    70                         iterator& operator= (const iterator &that) {
    71                                 scopes = that.scopes; i = that.i; it = that.it;
    72                                 return *this;
    73                         }
    74 
    75                         reference operator* () { return *it; }
    76                         pointer operator-> () { return it.operator->(); }
    77 
    78                         iterator& operator++ () {
    79                                 if ( it == (*scopes)[i].end() ) {
    80                                         if ( i == 0 ) return *this;
    81                                         --i;
    82                                         it = (*scopes)[i].begin();
    83                                 } else {
    84                                         ++it;
    85                                 }
    86                                 return next_valid();
    87                         }
    88                         iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
    89 
    90                         iterator& operator-- () {
    91                                 // may fail if this is the begin iterator; allowed by STL spec
    92                                 if ( it == (*scopes)[i].begin() ) {
    93                                         ++i;
    94                                         it = (*scopes)[i].end();
    95                                 }
    96                                 --it;
    97                                 return prev_valid();
    98                         }
    99                         iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
    100 
    101                         bool operator== (const iterator &that) {
    102                                 return scopes == that.scopes && i == that.i && it == that.it;
    103                         }
    104                         bool operator!= (const iterator &that) { return !( *this == that ); }
    105 
    106                         size_type get_level() const { return i; }
    107 
    108                 private:
    109                         scope_list const *scopes;
    110                         wrapped_iterator it;
    111                         size_type i;
    112                 };
    113 
    114                 class const_iterator : public std::iterator< std::bidirectional_iterator_tag,
    115                                                              value_type > {
    116                 friend class ScopedSet;
    117                         typedef typename std::set< Value >::iterator wrapped_iterator;
    118                         typedef typename std::set< Value >::const_iterator wrapped_const_iterator;
    119                         typedef typename std::vector< std::set< Value > > scope_list;
    120                         typedef typename scope_list::size_type size_type;
    121 
    122                         /// Checks if this iterator points to a valid item
    123                         bool is_valid() const {
    124                                 return it != (*scopes)[i].end();
    125                         }
    126 
    127                         /// Increments on invalid
    128                         const_iterator& next_valid() {
    129                                 if ( ! is_valid() ) { ++(*this); }
    130                                 return *this;
    131                         }
    132 
    133                         /// Decrements on invalid
    134                         const_iterator& prev_valid() {
    135                                 if ( ! is_valid() ) { --(*this); }
    136                                 return *this;
    137                         }
    138 
    139                         const_iterator(scope_list const &_scopes, const wrapped_const_iterator &_it, size_type _i)
    140                                 : scopes(&_scopes), it(_it), i(_i) {}
    141                 public:
    142                         const_iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
    143                         const_iterator(const const_iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
    144                         const_iterator& operator= (const iterator &that) {
    145                                 scopes = that.scopes; i = that.i; it = that.it;
    146                                 return *this;
    147                         }
    148                         const_iterator& operator= (const const_iterator &that) {
    149                                 scopes = that.scopes; i = that.i; it = that.it;
    150                                 return *this;
    151                         }
    152 
    153                         const_reference operator* () { return *it; }
    154                         const_pointer operator-> () { return it.operator->(); }
    155 
    156                         const_iterator& operator++ () {
    157                                 if ( it == (*scopes)[i].end() ) {
    158                                         if ( i == 0 ) return *this;
    159                                         --i;
    160                                         it = (*scopes)[i].begin();
    161                                 } else {
    162                                         ++it;
    163                                 }
    164                                 return next_valid();
    165                         }
    166                         const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
    167 
    168                         const_iterator& operator-- () {
    169                                 // may fail if this is the begin iterator; allowed by STL spec
    170                                 if ( it == (*scopes)[i].begin() ) {
    171                                         ++i;
    172                                         it = (*scopes)[i].end();
    173                                 }
    174                                 --it;
    175                                 return prev_valid();
    176                         }
    177                         const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
    178 
    179                         bool operator== (const const_iterator &that) {
    180                                 return scopes == that.scopes && i == that.i && it == that.it;
    181                         }
    182                         bool operator!= (const const_iterator &that) { return !( *this == that ); }
    183 
    184                         size_type get_level() const { return i; }
    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();
    201                 }
    202 
    203                 /// Default constructor initializes with one scope
    204                 ScopedSet() { beginScope(); }
    205 
    206                 iterator begin() { return iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
    207                 const_iterator begin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
    208                 const_iterator cbegin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
    209                 iterator end() { return iterator(scopes, scopes[0].end(), 0); }
    210                 const_iterator end() const { return const_iterator(scopes, scopes[0].end(), 0); }
    211                 const_iterator cend() const { return const_iterator(scopes, scopes[0].end(), 0); }
    212 
    213                 /// Gets the index of the current scope (counted from 1)
    214                 size_type currentScope() const { return scopes.size(); }
    215 
    216                 /// Finds the given key in the outermost scope it occurs; returns end() for none such
    217                 iterator find( const Value &key ) {
    218                         for ( size_type i = scopes.size() - 1; ; --i ) {
    219                                 typename Scope::iterator val = scopes[i].find( key );
    220                                 if ( val != scopes[i].end() ) return iterator( scopes, val, i );
    221                                 if ( i == 0 ) break;
    222                         }
    223                         return end();
    224                 }
    225                 const_iterator find( const Value &key ) const {
    226                         return const_iterator( const_cast< ScopedSet< Value >* >(this)->find( key ) );
    227                 }
    228 
    229                 /// Finds the given key in the outermost scope inside the given scope where it occurs
    230                 iterator findNext( const_iterator &it, const Value &key ) {
    231                         if ( it.i == 0 ) return end();
     23
     24/// A set where the items are placed into nested scopes;
     25/// inserted items are placed into the innermost scope, lookup looks from the innermost scope outward
     26template<typename Value>
     27class ScopedSet {
     28        typedef std::set< Value > Scope;
     29        typedef std::vector< Scope > ScopeList;
     30
     31        ScopeList scopes; ///< scoped list of sets
     32public:
     33        typedef typename Scope::key_type key_type;
     34        typedef typename Scope::value_type value_type;
     35        typedef typename ScopeList::size_type size_type;
     36        typedef typename ScopeList::difference_type difference_type;
     37        typedef typename Scope::reference reference;
     38        typedef typename Scope::const_reference const_reference;
     39        typedef typename Scope::pointer pointer;
     40        typedef typename Scope::const_pointer const_pointer;
     41
     42        // Both iterator types are complete bidirectional iterators, see below.
     43        class iterator;
     44        class const_iterator;
     45
     46        /// Starts a new scope
     47        void beginScope() {
     48                Scope scope;
     49                scopes.push_back(scope);
     50        }
     51
     52        /// Ends a scope; invalidates any iterators pointing to elements of that scope
     53        void endScope() {
     54                scopes.pop_back();
     55        }
     56
     57        /// Default constructor initializes with one scope
     58        ScopedSet() { beginScope(); }
     59
     60        iterator begin() { return iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
     61        const_iterator begin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
     62        const_iterator cbegin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
     63        iterator end() { return iterator(scopes, scopes[0].end(), 0); }
     64        const_iterator end() const { return const_iterator(scopes, scopes[0].end(), 0); }
     65        const_iterator cend() const { return const_iterator(scopes, scopes[0].end(), 0); }
     66
     67        /// Gets the index of the current scope (counted from 1)
     68        size_type currentScope() const { return scopes.size(); }
     69
     70        /// Finds the given key in the outermost scope it occurs; returns end() for none such
     71        iterator find( const Value &key ) {
     72                for ( size_type i = scopes.size() - 1; ; --i ) {
     73                        typename Scope::iterator val = scopes[i].find( key );
     74                        if ( val != scopes[i].end() ) return iterator( scopes, val, i );
     75                        if ( i == 0 ) break;
     76                }
     77                return end();
     78        }
     79        const_iterator find( const Value &key ) const {
     80                return const_iterator( const_cast< ScopedSet< Value >* >(this)->find( key ) );
     81        }
     82
     83        /// Finds the given key in the outermost scope inside the given scope where it occurs
     84        iterator findNext( const_iterator &it, const Value &key ) {
     85                if ( it.i == 0 ) return end();
    23286                        for ( size_type i = it.i - 1; ; --i ) {
    233                                 typename Scope::iterator val = scopes[i].find( key );
    234                                 if ( val != scopes[i].end() ) return iterator( scopes, val, i );
    235                                 if ( i == 0 ) break;
    236                         }
    237                         return end();
    238                 }
    239                 const_iterator findNext( const_iterator &it, const Value &key ) const {
    240                         return const_iterator( const_cast< ScopedSet< Value >* >(this)->findNext( it, key ) );
    241                 }
    242 
    243                 /// Inserts the given value into the outermost scope
    244                 std::pair< iterator, bool > insert( const value_type &value ) {
    245                         std::pair< typename Scope::iterator, bool > res = scopes.back().insert( value );
    246                         return std::make_pair( iterator(scopes, res.first, scopes.size()-1), res.second );
    247                 }
    248 
    249         };
     87                        typename Scope::iterator val = scopes[i].find( key );
     88                        if ( val != scopes[i].end() ) return iterator( scopes, val, i );
     89                        if ( i == 0 ) break;
     90                }
     91                return end();
     92        }
     93        const_iterator findNext( const_iterator &it, const Value &key ) const {
     94                return const_iterator( const_cast< ScopedSet< Value >* >(this)->findNext( it, key ) );
     95        }
     96
     97        /// Inserts the given value into the outermost scope
     98        std::pair< iterator, bool > insert( const value_type &value ) {
     99                std::pair< typename Scope::iterator, bool > res = scopes.back().insert( value );
     100                return std::make_pair( iterator(scopes, res.first, scopes.size()-1), res.second );
     101        }
     102};
     103
     104template<typename Value>
     105class ScopedSet<Value>::iterator :
     106                public std::iterator< std::bidirectional_iterator_tag, value_type > {
     107        friend class ScopedSet;
     108        friend class const_iterator;
     109        typedef typename std::set< Value >::iterator wrapped_iterator;
     110        typedef typename std::vector< std::set< Value > > scope_list;
     111        typedef typename scope_list::size_type size_type;
     112
     113        /// Checks if this iterator points to a valid item
     114        bool is_valid() const {
     115                return it != (*scopes)[i].end();
     116        }
     117
     118        /// Increments on invalid
     119        iterator& next_valid() {
     120                if ( ! is_valid() ) { ++(*this); }
     121                return *this;
     122        }
     123
     124        /// Decrements on invalid
     125        iterator& prev_valid() {
     126                if ( ! is_valid() ) { --(*this); }
     127                return *this;
     128        }
     129
     130        iterator(scope_list const &_scopes, const wrapped_iterator &_it, size_type _i)
     131                : scopes(&_scopes), it(_it), i(_i) {}
     132public:
     133        iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
     134        iterator& operator= (const iterator &that) {
     135                scopes = that.scopes; i = that.i; it = that.it;
     136                return *this;
     137        }
     138
     139        reference operator* () { return *it; }
     140        pointer operator-> () { return it.operator->(); }
     141
     142        iterator& operator++ () {
     143                if ( it == (*scopes)[i].end() ) {
     144                        if ( i == 0 ) return *this;
     145                        --i;
     146                        it = (*scopes)[i].begin();
     147                } else {
     148                        ++it;
     149                }
     150                return next_valid();
     151        }
     152        iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
     153
     154        iterator& operator-- () {
     155                // may fail if this is the begin iterator; allowed by STL spec
     156                if ( it == (*scopes)[i].begin() ) {
     157                        ++i;
     158                        it = (*scopes)[i].end();
     159                }
     160                --it;
     161                return prev_valid();
     162        }
     163        iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
     164
     165        bool operator== (const iterator &that) {
     166                return scopes == that.scopes && i == that.i && it == that.it;
     167        }
     168        bool operator!= (const iterator &that) { return !( *this == that ); }
     169
     170        size_type get_level() const { return i; }
     171
     172private:
     173        scope_list const *scopes;
     174        wrapped_iterator it;
     175        size_type i;
     176};
     177
     178template<typename Value>
     179class ScopedSet<Value>::const_iterator :
     180                public std::iterator< std::bidirectional_iterator_tag, value_type > {
     181        friend class ScopedSet;
     182        typedef typename std::set< Value >::iterator wrapped_iterator;
     183        typedef typename std::set< Value >::const_iterator wrapped_const_iterator;
     184        typedef typename std::vector< std::set< Value > > scope_list;
     185        typedef typename scope_list::size_type size_type;
     186
     187        /// Checks if this iterator points to a valid item
     188        bool is_valid() const {
     189                return it != (*scopes)[i].end();
     190        }
     191
     192        /// Increments on invalid
     193        const_iterator& next_valid() {
     194                if ( ! is_valid() ) { ++(*this); }
     195                return *this;
     196        }
     197
     198        /// Decrements on invalid
     199        const_iterator& prev_valid() {
     200                if ( ! is_valid() ) { --(*this); }
     201                return *this;
     202        }
     203
     204        const_iterator(scope_list const &_scopes, const wrapped_const_iterator &_it, size_type _i)
     205                : scopes(&_scopes), it(_it), i(_i) {}
     206public:
     207        const_iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
     208        const_iterator(const const_iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
     209        const_iterator& operator= (const iterator &that) {
     210                scopes = that.scopes; i = that.i; it = that.it;
     211                return *this;
     212        }
     213        const_iterator& operator= (const const_iterator &that) {
     214                scopes = that.scopes; i = that.i; it = that.it;
     215                return *this;
     216        }
     217
     218        const_reference operator* () { return *it; }
     219        const_pointer operator-> () { return it.operator->(); }
     220
     221        const_iterator& operator++ () {
     222                if ( it == (*scopes)[i].end() ) {
     223                        if ( i == 0 ) return *this;
     224                        --i;
     225                        it = (*scopes)[i].begin();
     226                } else {
     227                        ++it;
     228                }
     229                return next_valid();
     230        }
     231        const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
     232
     233        const_iterator& operator-- () {
     234                // may fail if this is the begin iterator; allowed by STL spec
     235                if ( it == (*scopes)[i].begin() ) {
     236                        ++i;
     237                        it = (*scopes)[i].end();
     238                }
     239                --it;
     240                return prev_valid();
     241        }
     242        const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
     243
     244        bool operator== (const const_iterator &that) {
     245                return scopes == that.scopes && i == that.i && it == that.it;
     246        }
     247        bool operator!= (const const_iterator &that) { return !( *this == that ); }
     248
     249        size_type get_level() const { return i; }
     250
     251private:
     252        scope_list const *scopes;
     253        wrapped_const_iterator it;
     254        size_type i;
     255};
     256
    250257} // namespace GenPoly
    251258
Note: See TracChangeset for help on using the changeset viewer.