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 | |
---|
22 | namespace 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: // |
---|