source: src/GenPoly/ScopedSet.h @ 0982a05

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resnenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexerpthread-emulationqualifiedEnum
Last change on this file since 0982a05 was 6b0b624, checked in by Peter A. Buhr <pabuhr@…>, 7 years ago

change #ifndef to #pragma once
  • Property mode set to 100644
File size: 8.0 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// ScopedSet.h --
8//
9// Author           : Aaron B. Moss
10// Created On       : Thu Dec 3 11:51:00 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Sat Jul 22 09:22:17 2017
13// Update Count     : 2
14//
15
16#pragma once
17
18#include <iterator>
19#include <set>
20#include <vector>
21
22namespace 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                private:
107                        scope_list const *scopes;
108                        wrapped_iterator it;
109                        size_type i;
110                };
111
112                class const_iterator : public std::iterator< std::bidirectional_iterator_tag,
113                                                             value_type > {
114                friend class ScopedSet;
115                        typedef typename std::set< Value >::iterator wrapped_iterator;
116                        typedef typename std::set< Value >::const_iterator wrapped_const_iterator;
117                        typedef typename std::vector< std::set< Value > > scope_list;
118                        typedef typename scope_list::size_type size_type;
119
120                        /// Checks if this iterator points to a valid item
121                        bool is_valid() const {
122                                return it != (*scopes)[i].end();
123                        }
124
125                        /// Increments on invalid
126                        const_iterator& next_valid() {
127                                if ( ! is_valid() ) { ++(*this); }
128                                return *this;
129                        }
130
131                        /// Decrements on invalid
132                        const_iterator& prev_valid() {
133                                if ( ! is_valid() ) { --(*this); }
134                                return *this;
135                        }
136
137                        const_iterator(scope_list const &_scopes, const wrapped_const_iterator &_it, size_type _i)
138                                : scopes(&_scopes), it(_it), i(_i) {}
139                public:
140                        const_iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
141                        const_iterator(const const_iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
142                        const_iterator& operator= (const iterator &that) {
143                                scopes = that.scopes; i = that.i; it = that.it;
144                                return *this;
145                        }
146                        const_iterator& operator= (const const_iterator &that) {
147                                scopes = that.scopes; i = that.i; it = that.it;
148                                return *this;
149                        }
150
151                        const_reference operator* () { return *it; }
152                        const_pointer operator-> () { return it.operator->(); }
153
154                        const_iterator& operator++ () {
155                                if ( it == (*scopes)[i].end() ) {
156                                        if ( i == 0 ) return *this;
157                                        --i;
158                                        it = (*scopes)[i].begin();
159                                } else {
160                                        ++it;
161                                }
162                                return next_valid();
163                        }
164                        const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
165
166                        const_iterator& operator-- () {
167                                // may fail if this is the begin iterator; allowed by STL spec
168                                if ( it == (*scopes)[i].begin() ) {
169                                        ++i;
170                                        it = (*scopes)[i].end();
171                                }
172                                --it;
173                                return prev_valid();
174                        }
175                        const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
176
177                        bool operator== (const const_iterator &that) {
178                                return scopes == that.scopes && i == that.i && it == that.it;
179                        }
180                        bool operator!= (const const_iterator &that) { return !( *this == that ); }
181
182                private:
183                        scope_list const *scopes;
184                        wrapped_const_iterator it;
185                        size_type i;
186                };
187               
188                /// Starts a new scope
189                void beginScope() {
190                        Scope scope;
191                        scopes.push_back(scope);
192                }
193
194                /// Ends a scope; invalidates any iterators pointing to elements of that scope
195                void endScope() {
196                        scopes.pop_back();
197                }
198
199                /// Default constructor initializes with one scope
200                ScopedSet() { beginScope(); }
201
202                iterator begin() { return iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
203                const_iterator begin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
204                const_iterator cbegin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1).next_valid(); }
205                iterator end() { return iterator(scopes, scopes[0].end(), 0); }
206                const_iterator end() const { return const_iterator(scopes, scopes[0].end(), 0); }
207                const_iterator cend() const { return const_iterator(scopes, scopes[0].end(), 0); }
208
209                /// Gets the index of the current scope (counted from 1)
210                size_type currentScope() const { return scopes.size(); }
211
212                /// Finds the given key in the outermost scope it occurs; returns end() for none such
213                iterator find( const Value &key ) {
214                        for ( size_type i = scopes.size() - 1; ; --i ) {
215                                typename Scope::iterator val = scopes[i].find( key );
216                                if ( val != scopes[i].end() ) return iterator( scopes, val, i );
217                                if ( i == 0 ) break;
218                        }
219                        return end();
220                }
221                const_iterator find( const Value &key ) const {
222                        return const_iterator( const_cast< ScopedSet< Value >* >(this)->find( key ) );
223                }
224               
225                /// Finds the given key in the outermost scope inside the given scope where it occurs
226                iterator findNext( const_iterator &it, const Value &key ) {
227                        if ( it.i == 0 ) return end();
228                        for ( size_type i = it.i - 1; ; --i ) {
229                                typename Scope::iterator val = scopes[i].find( key );
230                                if ( val != scopes[i].end() ) return iterator( scopes, val, i );
231                                if ( i == 0 ) break;
232                        }
233                        return end();
234                }
235                const_iterator findNext( const_iterator &it, const Value &key ) const {
236                        return const_iterator( const_cast< ScopedSet< Value >* >(this)->findNext( it, key ) );
237                }
238
239                /// Inserts the given value into the outermost scope
240                std::pair< iterator, bool > insert( const value_type &value ) {
241                        std::pair< typename Scope::iterator, bool > res = scopes.back().insert( value );
242                        return std::make_pair( iterator(scopes, res.first, scopes.size()-1), res.second );
243                }
244               
245        };
246} // namespace GenPoly
247
248// Local Variables: //
249// tab-width: 4 //
250// mode: c++ //
251// compile-command: "make install" //
252// End: //
Note: See TracBrowser for help on using the repository browser.