#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;
};
class base_functor
{
public:
virtual ~base_functor() {} // Force base functor to be virtual
// Pure virtual operator() and Clone
virtual bool operator()( const T* value ) const = 0;
virtual base_functor *Clone() const = 0;
};
class functor_iterator
{
friend class CGenericTree<T>;
public:
// Normal constructors and destructors
functor_iterator() : m_iterator(), m_end(), m_functor( NULL ) {}
functor_iterator( const functor_iterator &src ) :
m_iterator( src.m_iterator ), m_end( src.m_end ), m_functor( src.m_functor->Clone() ) {}
functor_iterator &operator=( const functor_iterator &rhs )
{ if ( this != &rhs ) { m_iterator = rhs.m_iterator; m_end = rhs.m_end; m_functor = rhs.m_functor->Clone(); } return *this; }
~functor_iterator() { if ( m_functor ) delete m_functor; }
// Equality operators
bool operator==( const functor_iterator &rhs ) const
{ return m_iterator == rhs.m_iterator; }
bool operator!=( const functor_iterator &rhs ) const
{ return m_iterator != rhs.m_iterator; }
// Referencing operators
_tptr& operator*()
{ return *m_iterator; }
_tptr* operator->()
{ return &**this; }
// Increment/decrement operators
typename functor_iterator& operator++()
{ ++m_iterator; while ( m_iterator != m_end && m_functor && !(*m_functor)( *m_iterator ) ) ++m_iterator; return *this; }
typename functor_iterator operator++(int)
{ functor_iterator tmp = *this; ++*this; return tmp; }
private:
// Private constructor off a container iterator
explicit functor_iterator( const container_iterator &src, const container_iterator &end, const base_functor &functor ) :
m_iterator( src ), m_end( end ), m_functor( functor.Clone() )
{ while ( m_iterator != m_end && m_functor && !(*m_functor )( *m_iterator ) ) ++m_iterator; }
// Internal storage is a normal iterator
container_iterator m_iterator;
container_iterator m_end;
const base_functor *m_functor;
};
class deep_functor_iterator
{
friend class CGenericTree<T>;
public:
// Normal constructors and destructors
deep_functor_iterator() : m_iterator( NULL ), m_end( NULL ), m_functor( NULL ) {}
deep_functor_iterator( const deep_functor_iterator &src ) :
m_iterator( src.m_iterator ), m_end( src.m_end ), m_functor( src.m_functor->Clone() ) {}
deep_functor_iterator &operator=( const deep_functor_iterator &rhs )
{ if ( this != &rhs ) { m_iterator = rhs.m_iterator; m_end = rhs.m_end; m_functor = rhs.m_functor->Clone(); } return *this; }
~deep_functor_iterator() { if ( m_functor ) delete m_functor; }
// Equality operators
bool operator==( const deep_functor_iterator &rhs ) const
{ return m_iterator == rhs.m_iterator; }
bool operator!=( const deep_functor_iterator &rhs ) const
{ return m_iterator != rhs.m_iterator; }
// Referencing operators
_tptr& operator*()
{ return m_iterator; }
_tptr* operator->()
{ return &**this; }
// Increment/decrement operators
typename deep_functor_iterator& operator++()
{ increment(); while ( m_iterator != m_end && m_functor && !(*m_functor)( m_iterator ) ) increment(); return *this; }
typename deep_functor_iterator operator++(int)
{ deep_functor_iterator tmp = *this; ++*this; return tmp; }
private:
// Private constructor off a container iterator
explicit deep_functor_iterator( T *src, T *end, const base_functor &functor ) :
m_iterator( src ), m_end( end ), m_functor( functor.Clone() )
{ while ( m_iterator != m_end && m_functor && !(*m_functor )( 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;
const base_functor *m_functor;
};
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() ); }
functor_iterator begin_functor( const base_functor &functor )
{ return functor_iterator( m_children.begin(), m_children.end(), functor ); }
functor_iterator end_functor( const base_functor &functor )
{ return functor_iterator( m_children.end(), m_children.end(), functor ); }
deep_functor_iterator begin_deep_functor( const base_functor &functor )
{ return deep_functor_iterator( static_cast<T*>(this), end_val(), functor ); }
deep_functor_iterator end_deep_functor( const base_functor &functor )
{ return deep_functor_iterator( end_val(), end_val(), functor ); }
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;
}
}