Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/GenPoly/ScopedSet.h

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