source: src/GenPoly/ScopedSet.h @ afc1045

aaron-thesisarm-ehcleanup-dtorsctordeferred_resndemanglergc_noraiijacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newstringwith_gc
Last change on this file since afc1045 was afc1045, checked in by Aaron Moss <a3moss@…>, 6 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.