source: src/GenPoly/ScopedSet.h@ 3da470c

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors ctor deferred_resn demangler enum forall-pointer-decay gc_noraii jacob/cs343-translation jenkins-sandbox memory new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new string with_gc
Last change on this file since 3da470c was afc1045, checked in by Aaron Moss <a3moss@…>, 10 years ago

Hoist OffsetPackExpr to top level expression
  • Property mode set to 100644
File size: 7.3 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 : Aaron B. Moss
12// Last Modified On : Thu Dec 3 11:51:00 2015
13// Update Count : 1
14//
15
16#ifndef _SCOPEDSET_H
17#define _SCOPEDSET_H
18
19#include <iterator>
20#include <set>
21#include <vector>
22
23namespace GenPoly {
24 /// A set where the items are placed into nested scopes;
25 /// inserted items are placed into the innermost scope, lookup looks from the innermost scope outward
26 template<typename Value>
27 class ScopedSet {
28 typedef std::set< Value > Scope;
29 typedef std::vector< Scope > ScopeList;
30
31 ScopeList scopes; ///< scoped list of sets
32 public:
33 typedef typename Scope::key_type key_type;
34 typedef typename Scope::value_type value_type;
35 typedef typename ScopeList::size_type size_type;
36 typedef typename ScopeList::difference_type difference_type;
37 typedef typename Scope::reference reference;
38 typedef typename Scope::const_reference const_reference;
39 typedef typename Scope::pointer pointer;
40 typedef typename Scope::const_pointer const_pointer;
41
42 class iterator : public std::iterator< std::bidirectional_iterator_tag,
43 value_type > {
44 friend class ScopedSet;
45 friend class const_iterator;
46 typedef typename std::set< Value >::iterator wrapped_iterator;
47 typedef typename std::vector< std::set< Value > > scope_list;
48 typedef typename scope_list::size_type size_type;
49
50 iterator(scope_list const &_scopes, const wrapped_iterator &_it, size_type _i)
51 : scopes(&_scopes), it(_it), i(_i) {}
52 public:
53 iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
54 iterator& operator= (const iterator &that) {
55 scopes = that.scopes; i = that.i; it = that.it;
56 return *this;
57 }
58
59 reference operator* () { return *it; }
60 pointer operator-> () { return it.operator->(); }
61
62 iterator& operator++ () {
63 if ( it == (*scopes)[i].end() ) {
64 if ( i == 0 ) return *this;
65 --i;
66 it = (*scopes)[i].begin();
67 return *this;
68 }
69 ++it;
70 return *this;
71 }
72 iterator& operator++ (int) { iterator tmp = *this; ++(*this); return tmp; }
73
74 iterator& operator-- () {
75 // may fail if this is the begin iterator; allowed by STL spec
76 if ( it == (*scopes)[i].begin() ) {
77 ++i;
78 it = (*scopes)[i].end();
79 }
80 --it;
81 return *this;
82 }
83 iterator& operator-- (int) { iterator tmp = *this; --(*this); return tmp; }
84
85 bool operator== (const iterator &that) {
86 return scopes == that.scopes && i == that.i && it == that.it;
87 }
88 bool operator!= (const iterator &that) { return !( *this == that ); }
89
90 private:
91 scope_list const *scopes;
92 wrapped_iterator it;
93 size_type i;
94 };
95
96 class const_iterator : public std::iterator< std::bidirectional_iterator_tag,
97 value_type > {
98 friend class ScopedSet;
99 typedef typename std::set< Value >::iterator wrapped_iterator;
100 typedef typename std::set< Value >::const_iterator wrapped_const_iterator;
101 typedef typename std::vector< std::set< Value > > scope_list;
102 typedef typename scope_list::size_type size_type;
103
104 const_iterator(scope_list const &_scopes, const wrapped_const_iterator &_it, size_type _i)
105 : scopes(&_scopes), it(_it), i(_i) {}
106 public:
107 const_iterator(const iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
108 const_iterator(const const_iterator &that) : scopes(that.scopes), it(that.it), i(that.i) {}
109 const_iterator& operator= (const iterator &that) {
110 scopes = that.scopes; i = that.i; it = that.it;
111 return *this;
112 }
113 const_iterator& operator= (const const_iterator &that) {
114 scopes = that.scopes; i = that.i; it = that.it;
115 return *this;
116 }
117
118 const_reference operator* () { return *it; }
119 const_pointer operator-> () { return it.operator->(); }
120
121 const_iterator& operator++ () {
122 if ( it == (*scopes)[i].end() ) {
123 if ( i == 0 ) return *this;
124 --i;
125 it = (*scopes)[i].begin();
126 return *this;
127 }
128 ++it;
129 return *this;
130 }
131 const_iterator& operator++ (int) { const_iterator tmp = *this; ++(*this); return tmp; }
132
133 const_iterator& operator-- () {
134 // may fail if this is the begin iterator; allowed by STL spec
135 if ( it == (*scopes)[i].begin() ) {
136 ++i;
137 it = (*scopes)[i].end();
138 }
139 --it;
140 return *this;
141 }
142 const_iterator& operator-- (int) { const_iterator tmp = *this; --(*this); return tmp; }
143
144 bool operator== (const const_iterator &that) {
145 return scopes == that.scopes && i == that.i && it == that.it;
146 }
147 bool operator!= (const const_iterator &that) { return !( *this == that ); }
148
149 private:
150 scope_list const *scopes;
151 wrapped_const_iterator it;
152 size_type i;
153 };
154
155 /// Starts a new scope
156 void beginScope() {
157 Scope scope;
158 scopes.push_back(scope);
159 }
160
161 /// Ends a scope; invalidates any iterators pointing to elements of that scope
162 void endScope() {
163 scopes.pop_back();
164 }
165
166 /// Default constructor initializes with one scope
167 ScopedSet() { beginScope(); }
168
169 iterator begin() { return iterator(scopes, scopes.back().begin(), scopes.size()-1); }
170 const_iterator begin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1); }
171 const_iterator cbegin() const { return const_iterator(scopes, scopes.back().begin(), scopes.size()-1); }
172 iterator end() { return iterator(scopes, scopes[0].end(), 0); }
173 const_iterator end() const { return const_iterator(scopes, scopes[0].end(), 0); }
174 const_iterator cend() const { return const_iterator(scopes, scopes[0].end(), 0); }
175
176 /// Gets the index of the current scope (counted from 1)
177 size_type currentScope() const { return scopes.size(); }
178
179 /// Finds the given key in the outermost scope it occurs; returns end() for none such
180 iterator find( const Value &key ) {
181 for ( size_type i = scopes.size() - 1; ; --i ) {
182 typename Scope::iterator val = scopes[i].find( key );
183 if ( val != scopes[i].end() ) return iterator( scopes, val, i );
184 if ( i == 0 ) break;
185 }
186 return end();
187 }
188 const_iterator find( const Value &key ) const {
189 return const_iterator( const_cast< ScopedSet< Value >* >(this)->find( key ) );
190 }
191
192 /// Finds the given key in the outermost scope inside the given scope where it occurs
193 iterator findNext( const_iterator &it, const Value &key ) {
194 if ( it.i == 0 ) return end();
195 for ( size_type i = it.i - 1; ; --i ) {
196 typename Scope::iterator val = scopes[i].find( key );
197 if ( val != scopes[i].end() ) return iterator( scopes, val, i );
198 if ( i == 0 ) break;
199 }
200 return end();
201 }
202 const_iterator findNext( const_iterator &it, const Value &key ) const {
203 return const_iterator( const_cast< ScopedSet< Value >* >(this)->findNext( it, key ) );
204 }
205
206 /// Inserts the given value into the outermost scope
207 std::pair< iterator, bool > insert( const value_type &value ) {
208 std::pair< typename Scope::iterator, bool > res = scopes.back().insert( value );
209 return std::make_pair( iterator(scopes, res.first, scopes.size()-1), res.second );
210 }
211
212 };
213} // namespace GenPoly
214
215#endif // _SCOPEDSET_H
216
217// Local Variables: //
218// tab-width: 4 //
219// mode: c++ //
220// compile-command: "make install" //
221// End: //
Note: See TracBrowser for help on using the repository browser.