source: src/GenPoly/ScopedSet.h@ 0fa04a04

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 0fa04a04 was b8b6c442, checked in by Rob Schluntz <rschlunt@…>, 7 years ago

Add get_level to ScopedSet
  • Property mode set to 100644
File size: 8.1 KB
RevLine 
[afc1045]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
[6b0b624]11// Last Modified By : Peter A. Buhr
12// Last Modified On : Sat Jul 22 09:22:17 2017
13// Update Count : 2
[afc1045]14//
15
[6b0b624]16#pragma once
[afc1045]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;
[b8b6c442]40
[afc1045]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
[5ba653c]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
[afc1045]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 }
[b8b6c442]74
[afc1045]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();
[5ba653c]83 } else {
84 ++it;
[afc1045]85 }
[5ba653c]86 return next_valid();
[afc1045]87 }
[f6d4204]88 iterator operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
[afc1045]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;
[5ba653c]97 return prev_valid();
[afc1045]98 }
[f6d4204]99 iterator operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
[afc1045]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
[b8b6c442]106 size_type get_level() const { return i; }
107
[afc1045]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
[5ba653c]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
[afc1045]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();
[5ba653c]161 } else {
162 ++it;
[afc1045]163 }
[5ba653c]164 return next_valid();
[afc1045]165 }
[f6d4204]166 const_iterator operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
[afc1045]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;
[5ba653c]175 return prev_valid();
[afc1045]176 }
[f6d4204]177 const_iterator operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
[afc1045]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
[b8b6c442]184 size_type get_level() const { return i; }
185
[afc1045]186 private:
187 scope_list const *scopes;
188 wrapped_const_iterator it;
189 size_type i;
190 };
[b8b6c442]191
[afc1045]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
[5ba653c]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(); }
[afc1045]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 }
[b8b6c442]228
[afc1045]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 }
[b8b6c442]248
[afc1045]249 };
250} // namespace GenPoly
251
252// Local Variables: //
253// tab-width: 4 //
254// mode: c++ //
255// compile-command: "make install" //
[6b0b624]256// End: //
Note: See TracBrowser for help on using the repository browser.