Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version
Go to top

Composites and Visitors - a Templatised Approach

, 13 Oct 2004
An article on a templatised implementation of composite and visitor interaction.
composites_visitor_demo.zip
composites_visitors.exe
composites_visitor_src.zip
composites_visitors
composite_visitor_demo.zip
composites_visitors.exe
composite_visitor_src.zip
generictreenodynamic.zip
#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( CGenericTree<T> *src ) : m_iterator( dynamic_cast<T*> ( 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 CGenericTree<T> *src ) : m_iterator( dynamic_cast<const T*> ( src ) ) {}
		// Internal storage is simply a pointer
		const T *m_iterator;
	};
private:
	// Helper function for tree-deep iterators
	T* GetNext();
	T* GetNext( CGenericTree<T> *src );
	const T* GetNext() const;
	const T* GetNext( const CGenericTree<T> *src ) const;

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( this ); }
	deep_iterator end_deep() { if ( m_parent ) return deep_iterator( m_parent->GetNext( this ) ); else return deep_iterator( NULL ); }
	const_deep_iterator begin_deep() const { return const_deep_iterator( this ); }
	const_deep_iterator end_deep() const { if ( m_parent ) return const_deep_iterator( m_parent->GetNext( this ) ); else return const_deep_iterator( NULL ); }

	// 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
	CGenericTree<T>* m_parent;

};

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

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

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

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

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 )
{
	for ( const_container_iterator iter = src.m_children.begin(); iter != src.m_children.end(); ++iter )
		push_back( (*iter)->Clone() );
}

template <typename T>
void
CGenericTree<T>::DeleteAllChildren()
{
	for ( container_iterator iter = m_children.begin(); 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 dynamic_cast<T*> (m_parent);
}

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

template <typename T>
void
CGenericTree<T>::push_back( T* entry )
{
	m_children.push_back( entry );
	entry->m_parent = 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 )
{
	if ( iter != end_shallow() )
		m_children.erase( iter.GetIterator() );
	(*iter)->m_parent = NULL;
	return *iter;
}

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

}

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.

| Advertise | Privacy | Mobile
Web04 | 2.8.140922.1 | Last Updated 14 Oct 2004
Article Copyright 2004 by Dave Handley
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid