source: src/GenPoly/ScopedSet.h@ 1b54b54

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr persistent-indexer pthread-emulation qualifiedEnum
Last change on this file since 1b54b54 was 6b0b624, checked in by Peter A. Buhr <pabuhr@…>, 8 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.