Context Navigation

source: src/GenPoly/ScopedSet.h @ f403c46

ADTast-experimentalpthread-emulation

Last change on this file since f403c46 was b8b6c44, checked in by Rob Schluntz <rschlunt@…>, 6 years ago
Add get_level to ScopedSet?
Property mode set to `100644`
File size: 8.1 KB

Rev	Line
[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
	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;
[b8b6c44]	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	}
[b8b6c44]	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
[b8b6c44]	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
[b8b6c44]	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	};
[b8b6c44]	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	}
[b8b6c44]	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	}
[b8b6c44]	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.

Download in other formats: