|
|
#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:
// 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() ); }
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>
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 ( (*iter)->m_parent )
(*iter)->m_parent->remove( (*iter) );
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.
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.
Submit an article or tip