source: src/GenPoly/ScopedSet.h @ 7cf8006

ADTast-experimental
Last change on this file since 7cf8006 was b8b6c44, checked in by Rob Schluntz <rschlunt@…>, 6 years ago

Add get_level to ScopedSet?
  • Property mode set to 100644
File size: 8.1 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                        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();
232                        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        };
250} // namespace GenPoly
251
252// Local Variables: //
253// tab-width: 4 //
254// mode: c++ //
255// compile-command: "make install" //
256// End: //
Note: See TracBrowser for help on using the repository browser.