A generic N-ary tree class. More...

#include <treeN.h>

Inheritance diagram for Yuni::Core::TreeN< T, TP, ChckP, ConvP >:

Collaboration diagram for Yuni::Core::TreeN< T, TP, ChckP, ConvP >:

Public Types
typedef T	Type
	The real type.

typedef T	Node
	Node.

typedef TreeN< T, TP, ChckP, ConvP >	TreeNNode
	The template class tree node.

typedef TP< TreeNNode >	ThreadingPolicy
	The threading policy.

typedef SmartPtr< Node, Policy::Ownership::COMReferenceCounted, ChckP, ConvP >	PtrThreadSafe
	A thread-safe node type.

typedef SmartPtr< Node, Policy::Ownership::COMReferenceCounted, ChckP, ConvP >	PtrSingleThreaded
	A default node type.

typedef Static::If< ThreadingPolicy::threadSafe, PtrThreadSafe, PtrSingleThreaded >::ResultType	Ptr
	Pointer to a node.

typedef Ptr::StoragePolicy	StoragePolicy
	The Storage policy.

typedef Ptr::OwnershipPolicy	OwnershipPolicy
	The Ownership policy.

typedef Ptr::ConversionPolicy	ConversionPolicy
	The Conversion policy.

typedef Ptr::CheckingPolicy	CheckingPolicy
	The Checking policy.

typedef Ptr::ConstnessPolicy	ConstnessPolicy
	The Constness policy.

typedef Ptr::ConstSmartPtrType	ConstPtr
	A const pointer.

typedef Ptr::NonConstSmartPtrType	NonConstPtr
	A non-const pointer.

typedef uint	SizeType
	Size.

typedef int	SignedSizeType
	Size (signed)

typedef std::vector< Ptr >	Vector
	A vector of nodes (std::vector)

typedef std::list< Ptr >	List
	A list of nodes (std::list)

Iterators
typedef IIterator< Private::Core::Tree::ChildIterator< Node >, false >	iterator

typedef IIterator< Private::Core::Tree::ChildIterator< Node >, true >	const_iterator

typedef IIterator< Private::Core::Tree::DepthPrefixIterator< Node >, false >	depth_prefix_iterator

typedef IIterator< Private::Core::Tree::DepthPrefixIterator< Node >, true >	const_depth_prefix_iterator

typedef IIterator< Private::Core::Tree::DepthInfixIterator< Node >, false >	depth_infix_iterator

typedef IIterator< Private::Core::Tree::DepthInfixIterator< Node >, true >	const_depth_infix_iterator

Public Member Functions
std::ostream &	print (std::ostream &out, bool recursive=true, uint level=0)
	Print the entire tree to the output stream. More...

Constructors & Destructor
	TreeN ()
	Default constructor.

virtual	~TreeN ()
	Destructor.

Parent of the node
Ptr	parent ()
	Get the parent of the node.

Ptr	parent () const
	Get the parent of the node.

void	parent (Ptr newParent)
	ReAttach to another parent.

void	detachFromParent ()
	Detach the node from its parent.

Adding
void	append (Ptr &node)
	Append a child node to the end of the list. More...

void	append (T *node)

void	push_back (Ptr &node)
	Append a child node at the end. More...

void	push_back (T *node)

void	push_front (Ptr &node)
	Append a child node at the begining. More...

void	push_front (T *node)

Removing
void	clear ()
	Remove all children.

bool	remove (Ptr &node)
	Remove a child node. More...

bool	remove (const SizeType index)
	Remove the n-th child of the node. More...

bool	remove (const SignedSizeType index)

Searching
iterator	begin ()
	Return iterator to the first child of the node.

const const_iterator	begin () const

depth_prefix_iterator	depth_prefix_begin ()

const const_depth_prefix_iterator	depth_prefix_begin () const

iterator	end ()
	Return iterator to the last child of the node.

const const_iterator	end () const

depth_prefix_iterator	depth_prefix_end ()

const const_depth_prefix_iterator	depth_prefix_end () const

Ptr	find (const SizeType index)
	Find the n-th child of the node. More...

Ptr	find (const SignedSizeType index)

bool	empty () const
	Get if the node has children.

SizeType	count () const

SizeType	size () const
	Alias for count()

Ptr	firstChild ()
	Get the first child.

const Ptr	firstChild () const

Ptr	lastChild ()
	Get the last child.

const Ptr	lastChild () const

Ptr	previousSibling ()
	Get the previous sibling.

const Ptr	previousSibling () const

Ptr	nextSibling ()
	Get the next sibling.

const Ptr	nextSibling () const

Extra
bool	leaf () const
	Get if the node is a leaf. More...

SizeType	depth () const
	Computes the depth of this node. More...

SizeType	treeHeight ()
	Computes the height from this node. More...

Comparisons
bool	equals (const Ptr &node) const
	Test if the current node is equals to another one. More...

Z-Order
void	bringToFront ()
	Move the node to the end. More...

void	sendToBack ()
	Move the node to the begining. More...


void	invalidate ()
	Schedule an asynchronous update of the item (depending upon the implementation)

bool	isInvalidated ()
	Get if the item is invalidated (depending upon the implementation)

Operators
Node &	operator+= (Ptr &node)
	Append a child at the end.

Node &	operator+= (T *node)
	Append a child at the end.

Node &	operator-= (Ptr &node)
	Remove a child node.

Node &	operator<< (Ptr &node)
	Append a child at the end.

Node &	operator<< (T *node)
	Append a child at the end.

Node &	operator== (const Ptr &node) const
	Comparison with another node.

Ptr	operator[] (const SizeType index)
	Get the n-th child of the node. More...

Ptr	operator[] (const SignedSizeType index)
	Get the n-th child of the node. More...

Pointer management
void	addRef () const
	Increment the internal reference counter.

bool	release () const
	Decrement the internal reference counter.

Protected Member Functions
virtual void	invalidateWL ()
	Invalidate the item.

virtual bool	isInvalidatedWL ()
	Get if the item is invalidated.

virtual void	printBeginWL (std::ostream &out, uint level) const
	(only used for debugging)

virtual void	printEndWL (std::ostream &out, uint level) const
	(only used for debugging)

void	clearWL ()
	Remove all children.

void	pushBackWL (Ptr &node)
	Append a child to the end of the list.

void	pushFrontWL (Ptr &node)
	Append a child to the end of the list.

void	detachFromParentWL ()
	Detach from the parent. More...

Ptr	findFromIndexWL (const SizeType index)
	Find a child node from its index (slow)

Protected Attributes
Node *	pParent
	Parent (weak pointer)

SizeType	pChildrenCount
	How many children do we have ?

Ptr	pPreviousSibling
	The previous sibling.

Ptr	pNextSibling
	The next sibling.

Ptr	pFirstChild
	The first child.

Ptr	pLastChild
	The last child.

Detailed Description

template<class T, template< class > class TP = Policy::ObjectLevelLockable, template< class > class ChckP = Policy::Checking::None, class ConvP = Policy::Conversion::Allow>
class Yuni::Core::TreeN< T, TP, ChckP, ConvP >

A generic N-ary tree class.

This class provides a generic and thread-safe implementation for N-ary trees. It behaves like an STL container class.

class MyNode : public Core::TreeN<MyNode, Policy::SingleThreaded>
{
public:
    MyNode()
        :pValue()
    {}
    explicit MyNode(const String& v)
        :pValue(v)
    {}
    virtual ~MyNode() {}
    String value()
    {
        MyNode::ThreadingPolicy::MutexLocker locker(*this);
        return pValue;
    }
    void value(const String& s)
    {
        MyNode::ThreadingPolicy::MutexLocker locker(*this);
        pValue = s;
    }
private:
    String pValue;
};
int main(void)
{
    MyNode::Ptr root(new MyNode("Here is a root node"));
    MyNode* n = new MyNode("SubNode 1");
    // Adding `n` as a child for the root node
    *root += n;
    // A few children for the node `n`
    // The operator `+=` and `<<` are equivalent
    n << new MyNode("SubSubNode 1") << new MyNode("SubSubNode 2")
        << new MyNode("SubSubNode 3");
    return 0;
}

Example of a pseudo XML tree :

class MyXMLNode : public Yuni::Core::TreeN<MyXMLNode>
{
public:
    MyXMLNode() :pValue() {}
    virtual MyXMLNode() {}
    Yuni::String value()
    {
        ThreadingPolicy::MutexLocker locker(*this);
        return pValue;
    }
    void value(const Yuni::String& v)
    {
        ThreadingPolicy::MutexLocker locker(*this);
        pValue = v;
    }
protected:
    virtual void printBeginWL(std::ostream& out, uint) const
    {
        out << "<node><![CDATA[" << pValue << "]]>";
    }
    virtual void printBeginWL(std::ostream& out, uint) const
    {
        out << "</node>";
    }
private:
    Yuni::String pValue;
};
int main(void)
{
    MyXMLNode::Ptr root(new MyXMLNode("root node"));
    MyXMLNode* sub = new MyXMLNode("Sub Node 1");
    // Adding sub nodes
    *root << sub << new MyXMLNode("Sub Node 2");
    // Adding sub-sub nodes
    *sub << new MyXMLNode("Sub Sub Node 1") << new MyXMLNode("Sub Sub Node 2");
    // print
    root->print(std::cout) << std::endl;
    return 0;
}

Note: Contrary to an STL-like container class, this class is not designed to be instantiated directly, but to be used as a base class.; Each node is managed by a smart pointer, and assuming the SingleThreaded policy is not used, it is safe to manipulate a node from everywhere.; When manipulating nodes, always prefer to use the Ptr typedef.; Any checking policy might be used (passed to the smart pointer). However, we want to be able to have NULL pointers.; This implementation will be more efficient when handling large datasets, and in a multithreaded context.

Template Parameters

T	The real type of the tree class (CRTP)
TP	The Threading policy
ChckP	The Checking policy
ConvP	The Conversion policy

Member Function Documentation

◆ append()

template<class T, template< class > class TP = Policy::ObjectLevelLockable, template< class > class ChckP = Policy::Checking::None, class ConvP = Policy::Conversion::Allow>

void Yuni::Core::TreeN< T, TP, ChckP, ConvP >::append ( Ptr & node )

Append a child node to the end of the list.

Parameters

node	The new child node

◆ bringToFront()

template<class T , template< class > class TP, template< class > class ChckP, class ConvP >

void Yuni::Core::TreeN< T, TP, ChckP, ConvP >::bringToFront ( )

Move the node to the end.

This method is especially useful when manipulating items on a layer. When iterating over all children, the last one can be considered as the last drawn thus the first visible item for the user.

◆ depth()

template<class T , template< class > class TP, template< class > class ChckP, class ConvP >

TreeN< T, TP, ChckP, ConvP >::SizeType Yuni::Core::TreeN< T, TP, ChckP, ConvP >::depth ( ) const

Computes the depth of this node.

The depth of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero.

◆ detachFromParentWL()

template<class T , template< class > class TP, template< class > class ChckP, class ConvP >

void Yuni::Core::TreeN< T, TP, ChckP, ConvP >::detachFromParentWL ( )

inlineprotected

Detach from the parent.

Note: This method assumes that we have a parent

◆ equals()

template<class T , template< class > class TP, template< class > class ChckP, class ConvP >

bool Yuni::Core::TreeN< T, TP, ChckP, ConvP >::equals ( const Ptr & node ) const

inline

Test if the current node is equals to another one.

Returns: True if the two nodes are equal, false otherwise

◆ find()

template<class T, template< class > class TP = Policy::ObjectLevelLockable, template< class > class ChckP = Policy::Checking::None, class ConvP = Policy::Conversion::Allow>

Ptr Yuni::Core::TreeN< T, TP, ChckP, ConvP >::find ( const SizeType index )

Find the n-th child of the node.

This method is only provided for convenience reasons. This method is slow and should be used with care.

Parameters

index Index of the child node to remove (zero-based) and this value can be out of bounds

Returns: A pointer to a Ptr, NULL of not found

◆ leaf()

template<class T , template< class > class TP, template< class > class ChckP, class ConvP >

bool Yuni::Core::TreeN< T, TP, ChckP, ConvP >::leaf ( ) const

inline

Get if the node is a leaf.

A leaf is merely a node without any children

Returns: True if this node is a leaf, False otherwise

◆ operator[]() [1/2]

template<class T, template< class > class TP = Policy::ObjectLevelLockable, template< class > class ChckP = Policy::Checking::None, class ConvP = Policy::Conversion::Allow>

Ptr Yuni::Core::TreeN< T, TP, ChckP, ConvP >::operator[] ( const SizeType index )

inline

Get the n-th child of the node.

See also: find()

◆ operator[]() [2/2]

template<class T, template< class > class TP = Policy::ObjectLevelLockable, template< class > class ChckP = Policy::Checking::None, class ConvP = Policy::Conversion::Allow>

Ptr Yuni::Core::TreeN< T, TP, ChckP, ConvP >::operator[] ( const SignedSizeType index )

inline

Get the n-th child of the node.

See also: find()

◆ print()

template<class T , template< class > class TP, template< class > class ChckP, class ConvP >

std::ostream & Yuni::Core::TreeN< T, TP, ChckP, ConvP >::print	(	std::ostream &	out,
		bool	recursive = `true`,
		uint	level = `0`
	)

Print the entire tree to the output stream.

Should only be used for debugging purposes only

◆ push_back()

template<class T , template< class > class TP, template< class > class ChckP, class ConvP >

void Yuni::Core::TreeN< T, TP, ChckP, ConvP >::push_back ( Ptr & node )

inline

Append a child node at the end.

Parameters

node	The new child node

◆ push_front()

template<class T , template< class > class TP, template< class > class ChckP, class ConvP >

void Yuni::Core::TreeN< T, TP, ChckP, ConvP >::push_front ( Ptr & node )

inline

Append a child node at the begining.

Parameters

node	The new child node

◆ remove() [1/2]

template<class T , template< class > class TP, template< class > class ChckP, class ConvP >

bool Yuni::Core::TreeN< T, TP, ChckP, ConvP >::remove ( Ptr & node )

inline

Remove a child node.

Returns: True if the node has been removed, False otherwise

◆ remove() [2/2]

template<class T, template< class > class TP = Policy::ObjectLevelLockable, template< class > class ChckP = Policy::Checking::None, class ConvP = Policy::Conversion::Allow>

bool Yuni::Core::TreeN< T, TP, ChckP, ConvP >::remove ( const SizeType index )

Remove the n-th child of the node.

This method is only provided for convenience reasons. This method is slow and should be used with care.

Parameters

index Index of the child node to remove (zero-based) and this value can be out of bounds

Returns: True if the node has been removed, False otherwise

◆ sendToBack()

template<class T , template< class > class TP, template< class > class ChckP, class ConvP >

void Yuni::Core::TreeN< T, TP, ChckP, ConvP >::sendToBack ( )

Move the node to the begining.

This method is especially useful when manipulating items on a layer When iterating over all children, the first one can be considered as the first drawn thus the last visible item for the user.

◆ treeHeight()

template<class T , template< class > class TP, template< class > class ChckP, class ConvP >

TreeN< T, TP, ChckP, ConvP >::SizeType Yuni::Core::TreeN< T, TP, ChckP, ConvP >::treeHeight ( )

Computes the height from this node.

The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a height of zero.

Returns: The height of the tree

The documentation for this class was generated from the following files:

src/yuni/core/tree/n/treeN.h
src/yuni/core/tree/n/treeN.hxx

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<class T, template< class > class TP = Policy::ObjectLevelLockable, template< class > class ChckP = Policy::Checking::None, class ConvP = Policy::Conversion::Allow> class Yuni::Core::TreeN< T, TP, ChckP, ConvP >

Member Function Documentation

◆ append()

◆ bringToFront()

◆ depth()

◆ detachFromParentWL()

◆ equals()

◆ find()

◆ leaf()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ print()

◆ push_back()

◆ push_front()

◆ remove() [1/2]

◆ remove() [2/2]

◆ sendToBack()

◆ treeHeight()

template<class T, template< class > class TP = Policy::ObjectLevelLockable, template< class > class ChckP = Policy::Checking::None, class ConvP = Policy::Conversion::Allow>
class Yuni::Core::TreeN< T, TP, ChckP, ConvP >