Click here to Skip to main content
12,630,386 members (30,276 online)
Click here to Skip to main content

Stats

41.6K views
660 downloads
18 bookmarked
Posted

Typed Iteration over a Composite

, 13 Oct 2004
Implementation of STL compliant type sensitive composite iterators.
#pragma once

#include <list>
#include <algorithm>

namespace Types {

template <typename T>
class CGenericTree
{
public:
	// Forward declarations and friends
	class shallow_iterator;
	class const_shallow_iterator;
	class deep_iterator;
	class const_deep_iterator;
	friend class shallow_iterator;
	friend class const_shallow_iterator;
	friend class deep_iterator;
	friend class const_deep_iterator;
private:
	// Typedefs
	typedef typename T* _tptr;
	typedef typename const T* _ctptr;
	typedef typename std::list<T*>::iterator container_iterator;
	typedef typename std::list<T*>::const_iterator const_container_iterator;
public:
	class shallow_iterator
	{
		friend class CGenericTree<T>;
	public:
		// Normal constructors and destructors
		shallow_iterator() :
			m_iterator() {}
		shallow_iterator( const shallow_iterator &src ) :
			m_iterator( src.m_iterator ) {}
		shallow_iterator &operator=( const shallow_iterator &rhs )
			{ if ( this != &rhs ) m_iterator = rhs.m_iterator; return *this; }
		~shallow_iterator() {}
		// Equality operator
		bool operator==( const shallow_iterator &rhs ) const
			{ return m_iterator == rhs.m_iterator; }
		bool operator!=( const shallow_iterator &rhs ) const
			{ return m_iterator != rhs.m_iterator; }
		// Referencing operators
		_tptr& operator*()
			{ return *m_iterator; }
		_tptr* operator->()
			{ return  m_iterator.operator->(); }
		// Increment/decrement operators
		shallow_iterator& operator++()
			{ ++m_iterator; return *this; }
		shallow_iterator operator++(int)
			{ shallow_iterator tmp = *this; ++*this; return tmp; }
		shallow_iterator& operator--()
			{ --m_iterator; return *this; }
		shallow_iterator operator--(int)
			{ shallow_iterator tmp = *this; --*this; return tmp; }
	private:
		// Private constructor off a normal iterator
		explicit shallow_iterator( const container_iterator &iter ) :
			m_iterator( iter ) {}
		// Get the internal storage iterator
		container_iterator GetIterator() { return m_iterator; }
		// Internal storage is a normal iterator
		container_iterator m_iterator;
	};
	class const_shallow_iterator
	{
		friend class CGenericTree<T>;
	public:
		// Normal constructors and destructors
		const_shallow_iterator() :
			m_iterator() {}
		const_shallow_iterator( const const_shallow_iterator &src ) :
			m_iterator( src.m_iterator ) {}
		const_shallow_iterator &operator=( const const_shallow_iterator &rhs )
			{ if ( this != &rhs ) { m_iterator = rhs.m_iterator; } return *this; }
		~const_shallow_iterator() {}
		// Equality operator
		bool operator==( const const_shallow_iterator &rhs ) const
			{ return m_iterator == rhs.m_iterator; }
		bool operator!=( const const_shallow_iterator &rhs ) const
			{ return m_iterator != rhs.m_iterator; }
		// Referencing operators
		const _ctptr& operator*() const
			{ return *m_iterator; }
		const _ctptr* operator->() const
			{ return  m_iterator.operator->(); }
		// Increment/decrement operators
		const_shallow_iterator& operator++()
			{ ++m_iterator; return *this; }
		const_shallow_iterator operator++(int)
			{ const_shallow_iterator tmp = *this; ++*this; return tmp; }
		const_shallow_iterator& operator--()
			{ --m_iterator; return *this; }
		const_shallow_iterator operator--(int)
			{ const_shallow_iterator tmp = *this; --*this; return tmp; }
	private:
		// Private constructor off a normal iterator
		explicit const_shallow_iterator( const const_container_iterator &iter ) :
			m_iterator( iter ) {}
		// Get the internal storage iterator
		const_container_iterator GetIterator()
			{ return m_iterator; }
		// Internal storage is a normal iterator
		const_container_iterator m_iterator;
	};
	class deep_iterator
	{
		friend class CGenericTree<T>;
	public:
		// Normal constructors and destructors
		deep_iterator() : m_iterator( NULL ) {}
		deep_iterator( const deep_iterator &src ) :
			m_iterator( src.m_iterator ) {}
		deep_iterator &operator=( const deep_iterator &rhs )
			{ if ( this != &rhs ) m_iterator = rhs.m_iterator; return *this; }
		~deep_iterator()
			{ m_iterator = NULL; }
		// Equality operator
		bool operator==( const deep_iterator &rhs ) const
			{ return m_iterator == rhs.m_iterator; }
		bool operator!=( const deep_iterator &rhs ) const
			{ return m_iterator != rhs.m_iterator; }
		// Referencing operators
		_tptr& operator*()
			{ return m_iterator; }
		_tptr* operator->()
			{ return &**this; }
		// Increment operators
		deep_iterator& operator++()
			{ if ( m_iterator ) m_iterator = m_iterator->GetNext(); return *this; }
		deep_iterator operator++(int)
			{ deep_iterator tmp = *this; ++*this; return tmp; }
	private:
		// Private constructor off a pointer
		explicit deep_iterator( T *src ) :
			m_iterator( src ) {}
		// Internal storage is simply a pointer
		T* m_iterator;
	};
	class const_deep_iterator
	{
		friend class CGenericTree<T>;
	public:
		// Normal constructors and destructors
		const_deep_iterator() :
			m_iterator( NULL ) {}
		const_deep_iterator( const const_deep_iterator &src ) :
			m_iterator( src.m_iterator ) {}
		const_deep_iterator &operator=( const const_deep_iterator &rhs )
			{ if ( this != &rhs ) m_iterator = rhs.m_iterator; return *this; }
		~const_deep_iterator()
			{ m_iterator = NULL; }
		// Equality operator
		bool operator==( const const_deep_iterator &rhs ) const
			{ return m_iterator == rhs.m_iterator; }
		bool operator!=( const const_deep_iterator &rhs ) const
			{ return m_iterator != rhs.m_iterator; }
		// Referencing operators
		const _ctptr& operator*() const
			{ return m_iterator; }
		const _ctptr* operator->() const
			{ return &**this; }
		// Increment operators
		const_deep_iterator& operator++()
			{ if ( m_iterator ) m_iterator = m_iterator->GetNext(); return *this; }
		const_deep_iterator operator++(int)
			{ const_deep_iterator tmp = *this; ++*this; return tmp; }
	private:
		// Private constructor off a pointer
		explicit const_deep_iterator( const T *src ) :
			m_iterator( src ) {}
		// Internal storage is simply a pointer
		const T *m_iterator;
	};
private:
	// Helper function for tree-deep iterators
	T* GetNext();
	T* GetNext( T *src );
	const T* GetNext() const;
	const T* GetNext( const T *src ) const;
public:
	// Typed shallow iterator
	template <typename child>
	class typed_iterator
	{
		friend class CGenericTree<T>;
	public:
		// Normal constructors and destructors
		typed_iterator<child>() :
			m_iterator(),
			m_end() {}
		typed_iterator<child>( const typed_iterator<child> &src ) :
			m_iterator( src.m_iterator ),
			m_end( src.m_end ) {}
		typed_iterator<child> &operator=( const typed_iterator<child> &rhs )
			{ if ( this != &rhs ) { m_iterator = rhs.m_iterator; m_end = src.m_end; } return *this; }
		~typed_iterator<child>() {}
		// Equality operator
		bool operator==( const typed_iterator<child> &rhs ) const
			{ return m_iterator == rhs.m_iterator; }
		bool operator!=( const typed_iterator<child> &rhs ) const
			{ return m_iterator != rhs.m_iterator; }
		// Referencing operators
		child* operator*()
			{ return dynamic_cast<child*>( *m_iterator ); }
		child** operator->()
			{ return &**this; }
		// Increment/decrement operators
		typename typed_iterator<child>& operator++();
		typename typed_iterator<child> operator++(int)
			{ typed_iterator<child> tmp = *this; ++*this; return tmp; }
	private:
		// Private constructor off a normal iterator
		explicit typed_iterator<child>( const container_iterator &iter, const container_iterator &end );
		// Internal storage is a normal iterator
		container_iterator m_iterator;
		container_iterator m_end;
	};
	template <typename child>
	class const_typed_iterator
	{
		friend class CGenericTree<T>;
	public:
		// Normal constructors and destructors
		const_typed_iterator<child>() :
			m_iterator(),
			m_end() {}
		const_typed_iterator<child>( const const_typed_iterator<child> &src ) :
			m_iterator( src.m_iterator ),
			m_end( src.m_end ) {}
		const_typed_iterator<child> &operator=( const const_typed_iterator<child> &rhs )
			{ if ( this != &rhs ) { m_iterator = rhs.m_iterator; m_end = src.m_end; } return *this; }
		~const_typed_iterator<child>() {}
		// Equality operator
		bool operator==( const const_typed_iterator<child> &rhs ) const
			{ return m_iterator == rhs.m_iterator; }
		bool operator!=( const const_typed_iterator<child> &rhs ) const
			{ return m_iterator != rhs.m_iterator; }
		// Referencing operators
		const child* operator*() const
			{ return dynamic_cast<const child*>( *m_iterator ); }
		const child** operator->() const
			{ return &**this; }
		// Increment/decrement operators
		typename const_typed_iterator<child>& operator++();
		typename const_typed_iterator<child> operator++(int)
			{ const_typed_iterator<child> tmp = *this; ++*this; return tmp; }
	private:
		// Private constructor off a normal iterator
		explicit const_typed_iterator<child>( const const_container_iterator &iter, const const_container_iterator &end );
		// Internal storage is a normal iterator
		const_container_iterator m_iterator;
		const_container_iterator m_end;
	};
	// Typed deep iterator
	template <typename child>
	class typed_deep_iterator
	{
		friend class CGenericTree<T>;
	public:
		// Normal constructors and destructors
		typed_deep_iterator<child>() : m_iterator( NULL ), m_end( NULL ) {}
		typed_deep_iterator<child>( const typed_deep_iterator<child> &src ) :
			m_iterator( src.m_iterator ), m_end( src.m_end ) {}
		typed_deep_iterator<child> &operator=( const typed_deep_iterator<child> &rhs )
			{ if ( this != &rhs ) { m_iterator = rhs.m_iterator; m_end = rhs.m_end; } return *this; }
		~typed_deep_iterator<child>()
			{ m_iterator = NULL; m_end = NULL; }
		// Equality operator
		bool operator==( const typed_deep_iterator<child> &rhs ) const
			{ return m_iterator == rhs.m_iterator; }
		bool operator!=( const typed_deep_iterator<child> &rhs ) const
			{ return m_iterator != rhs.m_iterator; }
		// Referencing operators
		child* operator*()
			{ return dynamic_cast<child*>( m_iterator ); }
		child** operator->()
			{ return &**this; }
		// Increment operators
		typed_deep_iterator<child>& operator++()
			{ increment(); while( m_iterator != m_end && !dynamic_cast<child*>( m_iterator ) ) increment(); return *this; }
		typed_deep_iterator<child> operator++(int)
			{ typed_deep_iterator tmp = *this; ++*this; return tmp; }
	private:
		// Private constructor off a pointer
		explicit typed_deep_iterator<child>( T *src, T *end ) :
			m_iterator( src ), m_end( end )
			{ while ( m_iterator != m_end && !dynamic_cast<child*>( m_iterator ) ) increment(); }
		// Private increment operator
		void increment()
			{ if ( m_iterator ) m_iterator = m_iterator->GetNext(); }
		// Internal storage is simply a pointer
		T* m_iterator;
		T* m_end;
	};
	template <typename child>
	class const_typed_deep_iterator
	{
		friend class CGenericTree<T>;
	public:
		// Normal constructors and destructors
		const_typed_deep_iterator<child>() : m_iterator( NULL ), m_end( NULL ) {}
		const_typed_deep_iterator<child>( const const_typed_deep_iterator<child> &src ) :
			m_iterator( src.m_iterator ), m_end( src.m_end ) {}
		const_typed_deep_iterator<child> &operator=( const const_typed_deep_iterator<child> &rhs )
			{ if ( this != &rhs ) { m_iterator = rhs.m_iterator; m_end = rhs.m_end; } return *this; }
		~const_typed_deep_iterator<child>()
			{ m_iterator = NULL; m_end = NULL; }
		// Equality operator
		bool operator==( const const_typed_deep_iterator<child> &rhs ) const
			{ return m_iterator == rhs.m_iterator; }
		bool operator!=( const const_typed_deep_iterator<child> &rhs ) const
			{ return m_iterator != rhs.m_iterator; }
		// Referencing operators
		const child* operator*() const
			{ return dynamic_cast<const child*>( m_iterator ); }
		const child** operator->() const
			{ return &**this; }
		// Increment operators
		const_typed_deep_iterator<child>& operator++()
			{ increment(); while( m_iterator != m_end && !dynamic_cast<const child*>( m_iterator ) ) increment(); return *this; }
		const_typed_deep_iterator<child> operator++(int)
			{ const_typed_deep_iterator tmp = *this; ++*this; return tmp; }
	private:
		// Private constructor off a pointer
		explicit const_typed_deep_iterator<child>( const T *src, const T *end ) :
			m_iterator( src ), m_end( end )
			{ while ( m_iterator != m_end && !dynamic_cast<const child*>( m_iterator ) ) increment(); }
		// Private increment operator
		void increment()
			{ if ( m_iterator ) m_iterator = m_iterator->GetNext(); }
		// Internal storage is simply a pointer
		const T* m_iterator;
		const T* m_end;
	};

public:
	// Constructors and destructors
	CGenericTree() : m_parent( NULL ) {}
	CGenericTree( const CGenericTree &src );
	CGenericTree &operator=( const CGenericTree &rhs );
	~CGenericTree() { DeleteAllChildren(); }
	virtual T* Clone() = 0;

private:
	void CopyAllChildren( const CGenericTree &src );
	void DeleteAllChildren();

public:
	// Iterator begin/end functions
	shallow_iterator begin_shallow()
		{ return shallow_iterator( m_children.begin() ); }
	shallow_iterator end_shallow()
		{ return shallow_iterator( m_children.end() ); }
	const_shallow_iterator begin_shallow() const
		{ return const_shallow_iterator( m_children.begin() ); }
	const_shallow_iterator end_shallow() const
		{ return const_shallow_iterator( m_children.end() ); }
	deep_iterator begin_deep()
		{ return deep_iterator( static_cast<T*>(this) ); }
	deep_iterator end_deep()
		{ return deep_iterator( end_val() ); }
	const_deep_iterator begin_deep() const
		{ return const_deep_iterator( static_cast<const T*>(this) ); }
	const_deep_iterator end_deep() const
		{ return deep_iterator( end_val() ); }
	template <typename child>
	typename typed_iterator<child> begin_typed()
		{ return typed_iterator<child>( m_children.begin(), m_children.end() ); }
	template <typename child>
	typename typed_iterator<child> end_typed()
		{ return typed_iterator<child>( m_children.end(), m_children.end() ); }
	template <typename child>
	typename const_typed_iterator<child> begin_typed() const
		{ return const_typed_iterator<child>( m_children.begin(), m_children.end() ); }
	template <typename child>
	typename const_typed_iterator<child> end_typed() const
		{ return const_typed_iterator<child>( m_children.end(), m_children.end() ); }
	template <typename child>
	typename typed_deep_iterator<child> begin_deep_typed()
		{ return typed_deep_iterator<child>( static_cast<T*>(this), end_val() ); }
	template <typename child>
	typename typed_deep_iterator<child> end_deep_typed()
		{ return typed_deep_iterator<child>( end_val(), end_val() ); }
	template <typename child>
	typename const_typed_deep_iterator<child> begin_deep_typed() const
		{ return const_typed_deep_iterator<child>( static_cast<const T*>(this), end_val() ); }
	template <typename child>
	typename const_typed_deep_iterator<child> end_deep_typed() const
		{ return const_typed_deep_iterator<child>( end_val(), end_val() ); }
private:
	// Helper functions for deep_iterators
	T* end_val()
		{ if ( m_parent ) return
		m_parent->GetNext( static_cast<T*>(this) );
		else return NULL; }
	const T* end_val() const
		{ if ( m_parent ) return
		m_parent->GetNext( static_cast<const T*>(this) );
		else return NULL; }
		
public:
	// Tree navigation
	T* GetParent();
	const T* GetParent() const;
	unsigned int size() const
		{ return (unsigned int) m_children.size(); }
	bool empty() const
		{ return m_children.empty(); }

	// Add and remove entries from the tree
	void DeleteFromTree();
	void push_back( T* entry );
	T* remove( T* entry );
	T* remove( shallow_iterator iter );
	T* remove( deep_iterator iter );

private:
	// This list of children of this tree element
	std::list<T*> m_children;
	// The parent of this object
	T* m_parent;

};

template <typename T>
T*
CGenericTree<T>::GetNext()
{
	if ( m_children.empty() )
	{
		if ( m_parent )
			return m_parent->GetNext( static_cast<T*>(this) );
		else
			return NULL;
	}
	return m_children.front();
}

template <typename T>
T*
CGenericTree<T>::GetNext( T *src )
{
	container_iterator iter = ++( find( m_children.begin(), m_children.end(), src ) );
	if ( iter != m_children.end() )
		return *iter;
	if ( m_parent )
		return m_parent->GetNext( static_cast<T*>(this) );
	return NULL;
}

template <typename T>
const T*
CGenericTree<T>::GetNext() const
{
	if ( m_children.empty() )
	{
		if ( m_parent )
			return m_parent->GetNext( static_cast<const T*>(this) );
		else
			return NULL;
	}
	return m_children.front();
}

template <typename T>
const T*
CGenericTree<T>::GetNext( const T *src ) const
{
	const_container_iterator iter = ++( find( m_children.begin(), m_children.end(), src ) );
	if ( iter != m_children.end() )
		return *iter;
	if ( m_parent )
		return m_parent->GetNext( static_cast<const T*>(this) );
	return NULL;
}

template <typename T>
template <typename child>
typename CGenericTree<T>::typed_iterator<child>&
CGenericTree<T>::typed_iterator<child>::operator++()
{
	++m_iterator;
	// Now increment until we either get the correct type or reach the end
	while ( m_iterator != m_end && !dynamic_cast<child*>( *m_iterator ) )
		++m_iterator;
	return *this;
}

template <typename T>
template <typename child>
CGenericTree<T>::typed_iterator<child>::typed_iterator( const container_iterator &iter, const container_iterator &end ) :
m_iterator( iter ),
m_end( end )
{
	// Now increment until we either get the correct type or reach the end
	while ( m_iterator != m_end && !dynamic_cast<child*>( *m_iterator ) )
		++m_iterator;
}

template <typename T>
template <typename child>
typename CGenericTree<T>::const_typed_iterator<child>&
CGenericTree<T>::const_typed_iterator<child>::operator++()
{
	++m_iterator;
	// Now increment until we either get the correct type or reach the end
	while ( m_iterator != m_end && !dynamic_cast<const child*>( *m_iterator ) )
		++m_iterator;
	return *this;
}

template <typename T>
template <typename child>
CGenericTree<T>::const_typed_iterator<child>::const_typed_iterator( const const_container_iterator &iter, const const_container_iterator &end ) :
m_iterator( iter ),
m_end( end )
{
	// Now increment until we either get the correct type or reach the end
	while ( m_iterator != m_end && !dynamic_cast<const child*>( *m_iterator ) )
		++m_iterator;
}

template <typename T>
CGenericTree<T>::CGenericTree( const CGenericTree<T> &src ) : m_parent( NULL )
{
	CopyAllChildren( src );
}

template <typename T>
CGenericTree<T> &
CGenericTree<T>::operator=( const CGenericTree<T> &rhs )
{
	if ( this != &rhs )
	{
		DeleteAllChildren();
		m_parent = NULL;
		CopyAllChildren( rhs );
	}
	return *this;
}

template <typename T>
void
CGenericTree<T>::CopyAllChildren( const CGenericTree<T> &src )
{
	const_container_iterator iter = src.m_children.begin();
	for ( ; iter != src.m_children.end(); ++iter )
		push_back( (*iter)->Clone() );
}

template <typename T>
void
CGenericTree<T>::DeleteAllChildren()
{
	container_iterator iter = m_children.begin();
	for ( ; iter != m_children.end(); ++iter )
		delete (*iter);
	m_children.clear();
}

template <typename T>
void
CGenericTree<T>::DeleteFromTree()
{
	if ( m_parent )
		m_parent->remove( (T*) this );
	delete this;
}

template <typename T>
T*
CGenericTree<T>::GetParent()
{
	return m_parent;
}

template <typename T>
const T*
CGenericTree<T>::GetParent() const
{
	return m_parent;
}

template <typename T>
void
CGenericTree<T>::push_back( T* entry )
{
	m_children.push_back( entry );
	entry->m_parent = static_cast<T*>(this);
}

template <typename T>
T*
CGenericTree<T>::remove( T* entry )
{
	container_iterator iter = find( m_children.begin(), m_children.end(), entry );
	if ( iter != m_children.end() )
		m_children.erase( iter );
	entry->m_parent = NULL;
	return entry;
}

template <typename T>
T*
CGenericTree<T>::remove( shallow_iterator iter )
{
	T *node = *iter;
	if ( iter != end_shallow() )
		m_children.erase( iter.GetIterator() );
	node->m_parent = NULL;
	return node;
}

template <typename T>
T*
CGenericTree<T>::remove( deep_iterator iter )
{
	T *node = *iter;
	if ( node->m_parent )
		node->m_parent->remove( node );
	return node;
}

}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Dave Handley
Web Developer
United Kingdom United Kingdom
I started programming on 8 bit machines as a teenager, writing my first compiled programming language before I was 16. I went on to study Engineering and Computer Science at Oxford University, getting a first and the University Prize for the best results in Computer Science. Since then I have worked in a variety of roles, involving systems management and development management on a wide variety of platforms. Now I manage a software development company producing CAD software for Windows using C++.

My 3 favourite reference books are: Design Patterns, Gamma et al; The C++ Standard Library, Josuttis; and Computer Graphics, Foley et al.

Outside computers, I am also the drummer in a band, The Unbelievers and we have just released our first album. I am a pretty good juggler and close up magician, and in my more insane past, I have cycled from Spain to Eastern Turkey, and cycled across the Namib desert.

You may also be interested in...

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.161205.3 | Last Updated 14 Oct 2004
Article Copyright 2004 by Dave Handley
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid