qgar::GenTree< T > Class Template Reference
[Graphs and trees]

#include <qgarlib/GenTree.H>

List of all members.

---

Detailed Description

template<class T>
class qgar::GenTree< T >

A tree whose nodes contain data of type T.

Such a tree is represented by:

• a pointer to the root node of the tree,
• a pointer to the current node, i.e. last accessed node.

See class qgar::GenTreeNode for the way the inner nodes are linked together.

Warning:

• For efficiency reasons, the validity of pointers given as arguments to function members is not checked. In particular:

  • pointers may be equal to 0, which will undoubtedly be the cause of a further program abortion,
  • pointed nodes may not belong to the current graph, with similar consequences.

• The deletion of a tree causes the deletion of all its nodes. Consequently, a program abortion may occur when:

  • an ill-formed tree contains multiple occurrences of (pointers to) a same node, or contains null pointers,
  • nodes are explicitely deleted, using operator <tt>delete, before exiting the block of program containing the tree.

Author:

Gérald Masini

Date:

Jul 3, 2001 16:23

Since:

Qgar 2.0

Definition at line 356 of file GenTree.H.

Public Types
Types
typedef T	value_type
	Type of the data stored in nodes.
typedef value_type &	reference
	Reference to qgar::GenTree::value_type.
typedef const value_type &	const_reference
	Constant reference to qgar::GenTree::value_type.
typedef value_type *	pointer
	Pointer to qgar::GenTree::value_type.
typedef const value_type *	const_pointer
	Constant pointer to qgar::GenTree::value_type.
Public Member Functions
Constructors
	GenTree ()
	Default constructor.
	GenTree (const GenTree< value_type > &aTree)
	Copy constructor.
	GenTree (const_reference aData)
	Create a tree with a single node containing the given data.
	GenTree (GenTreeNode< value_type > *aPNode)
	Create a tree from a given node.
Destructor
virtual	~GenTree ()
	Virtual destructor.
Predicates
bool	empty () const
	Is tree empty?
Access to links
WARNING The behavior of functions taking a pointer to a node as extra argument is undefined if: The tree is empty, or the given node does not belong to the tree.
GenTreeNode< value_type > *	pRoot () const
	Get pointer to the root of the tree.
GenTreeNode< value_type > *	pCurrent () const
	Get pointer to the current node.
GenTreeNode< value_type > *	pParent () const
	Get pointer to the parent of the current node.
GenTreeNode< value_type > *	pParent (GenTreeNode< value_type > *aPNode) const
	Get pointer to the parent of the given node.
GenTreeNode< value_type > *	pLSibling () const
	Get pointer to the left sibling of the current node.
GenTreeNode< value_type > *	pLSibling (GenTreeNode< value_type > *aPNode) const
	Get pointer to the left sibling of the given node.
GenTreeNode< value_type > *	pRSibling () const
	Get pointer to the right sibling of the current node.
GenTreeNode< value_type > *	pRSibling (GenTreeNode< value_type > *aPNode) const
	Get pointer to the right sibling of the given node.
GenTreeNode< value_type > *	pFirstChild () const
	Get pointer to the first child of the current node.
GenTreeNode< value_type > *	pFirstChild (GenTreeNode< value_type > *aPNode) const
	Get pointer to the first child of the given node.
Access to data
WARNING The behavior of functions taking a pointer to a node as extra extra argument is undefined if: The tree is empty, or the given node does not belong to the tree.
const_reference	accessData () const
	Get data stored in current node.
const_reference	accessData (GenTreeNode< value_type > *aPNode) const
	Get data stored in given node.
value_type	data () const
	Get a copy of the data stored in current node.
value_type	data (GenTreeNode< value_type > *aPNode) const
	Get a copy of the data stored in current node.
Moving in the tree
WARNING If the destination node does not exist, the pointer to the current node is set to 0. When a pointer to a node is given as argument, the corresponding node is supposed to belong to the tree!
void	gotoRoot ()
	The root becomes the current node.
void	gotoParent ()
	The parent of the current node becomes the current node.
void	gotoParent (GenTreeNode< value_type > *aPNode)
	The parent of the given node becomes the current node.
void	gotoLSibling ()
	The left sibling of the current node becomes the current node.
void	gotoLSibling (GenTreeNode< value_type > *aPNode)
	The left sibling of the given node becomes the current node.
void	gotoRSibling ()
	The right sibling of the current node becomes the current node.
void	gotoRSibling (GenTreeNode< value_type > *aPNode)
	The right sibling of the given node becomes the current node.
void	gotoFirstChild ()
	The first child of the current node becomes the current node.
void	gotoFirstChild (GenTreeNode< value_type > *aPNode)
	The first child of the given node becomes the current node.
Store data in nodes
WARNING The behavior of functions taking a pointer to a node as extra extra argument is undefined if: The tree is empty, or the given node does not belong to the tree.
void	setData (const_reference aData)
	Store data in current node.
void	setData (const_reference aData, GenTreeNode< value_type > *aPNode)
	Store data in given node.
Insert new nodes
WARNING When a pointer to a node is given as argument, the corresponding node is supposed to belong to the tree!
void	insertParent (const_reference aData)
	Insert a node containing given data as parent of current root.
void	insertLSibling (const_reference aData) throw (QgarErrorUser)
	Insert a node containing given data as left sibling of current node, which must not be the root.
void	insertLSibling (const_reference aData, GenTreeNode< value_type > *aPNode) throw (QgarErrorUser)
	Insert a node containing given data as left sibling of given node, which must not be the root.
void	insertRSibling (const_reference aData) throw (QgarErrorUser)
	Insert a node containing given data as right sibling of current node, which must not be the root.
void	insertRSibling (const_reference aData, GenTreeNode< value_type > *aPNode) throw (QgarErrorUser)
	Insert a node containing given data as right sibling of given node, which must not be the root.
void	insertFirstChild (const_reference aData)
	Insert a node containing given data as first child of current node.
void	insertFirstChild (const_reference aData, GenTreeNode< value_type > *aPNode)
	Insert a node containing given data as first child of given node.
Merge
WARNING All the nodes of the given tree are duplicated. When a pointer to a node is given as argument, the corresponding node is supposed to belong to the tree!
void	mergeLSibling (const GenTree< value_type > &aTree) throw (QgarErrorUser)
	Merge given tree as left sibling of current node, which must not be the root.
void	mergeLSibling (const GenTree< value_type > &aTree, GenTreeNode< value_type > *aPNode) throw (QgarErrorUser)
	Merge given tree as left sibling of given node, which must not be the root.
void	mergeRSibling (const GenTree< value_type > &aTree) throw (QgarErrorUser)
	Merge given tree as right sibling of current node, which must not be the root.
void	mergeRSibling (const GenTree< value_type > &aTree, GenTreeNode< value_type > *aPNode) throw (QgarErrorUser)
	Merge given tree as right sibling of current node, which must not be the root.
void	mergeFirstChild (const GenTree< value_type > &aTree)
	Merge given tree as first child of current node.
void	mergeFirstChild (const GenTree< value_type > &aTree, GenTreeNode< value_type > *aPNode)
	Merge given tree as first child of current node.
Remove nodes
GenTreeNode< value_type > *	remove ()
	Remove current node and return it.
GenTreeNode< value_type > *	remove (GenTreeNode< value_type > *aPNode)
	Remove given node and return it.
Operators
GenTree< value_type > &	operator= (const GenTree< value_type > &aTree)
	Assignment.
Protected Attributes
Representation of a tree
GenTreeNode< value_type > *	_pRoot
	Pointer to the root of the tree.
GenTreeNode< value_type > *	_pCurrent
	Pointer to the current node.
Private Member Functions
Auxiliaries
GenTreeNode< value_type > *	PRIVATEdeepCopy (GenTreeNode< value_type > *aPNode, GenTreeNode< value_type > *aPFCopy=0, GenTreeNode< value_type > *aPLSCopy=0) const
	Perform a deep copy of a part of the tree and return a pointer to the root of the copy.
void	PRIVATEdelete (GenTreeNode< value_type > *aPNode)
	Delete the (sub)tree of given root.

---

Member Typedef Documentation

template<class T> typedef const value_type* qgar::GenTree< T >::const_pointer

Constant pointer to qgar::GenTree::value_type. Definition at line 391 of file GenTree.H.

template<class T> typedef const value_type& qgar::GenTree< T >::const_reference

Constant reference to qgar::GenTree::value_type. Definition at line 381 of file GenTree.H.

template<class T> typedef value_type* qgar::GenTree< T >::pointer

Pointer to qgar::GenTree::value_type. Definition at line 386 of file GenTree.H.

template<class T> typedef value_type& qgar::GenTree< T >::reference

Reference to qgar::GenTree::value_type. Definition at line 376 of file GenTree.H.

template<class T> typedef T qgar::GenTree< T >::value_type

Type of the data stored in nodes. Definition at line 371 of file GenTree.H.

---

Constructor & Destructor Documentation

template<class T> qgar::GenTree< T >::GenTree (   )

Default constructor. Create an empty tree. Definition at line 305 of file GenTree.TCC.

template<class T> qgar::GenTree< T >::GenTree (  const GenTree< value_type > &  aTree  )

Copy constructor. The current node of the resulting tree is its root. Warning: Perform a deep copy: All the nodes of the given tree are duplicated. Definition at line 331 of file GenTree.TCC. References qgar::GenTree< T >::_pCurrent, and qgar::GenTree< T >::_pRoot.

template<class T> qgar::GenTree< T >::GenTree (  const_reference  aData  )

Create a tree with a single node containing the given data. This node becomes the current node. Parameters: aData  data to be stored in the node

template<class T> qgar::GenTree< T >::GenTree (  GenTreeNode< value_type > *  aPNode  )

Create a tree from a given node. If the pointer is 0, create an empty tree. Otherwise, the given node is considered as a root of a tree, which is copied to become the current tree. The current node is the root. Parameters: aPNode  a pointer to a node Warning: Perform a deep copy.

template<class T> qgar::GenTree< T >::~GenTree (   )  [virtual]

Virtual destructor. Definition at line 380 of file GenTree.TCC. References qgar::GenTree< T >::_pRoot, and qgar::GenTree< T >::PRIVATEdelete().

---

Member Function Documentation

template<class T> const_reference qgar::GenTree< T >::accessData (  GenTreeNode< value_type > *  aPNode  )  const [inline]

Get data stored in given node. Parameters: aPNode  a pointer to a node

template<class T> const T & qgar::GenTree< T >::accessData (   )  const [inline]

Get data stored in current node. Definition at line 514 of file GenTree.TCC. References qgar::GenTree< T >::_pCurrent, and qgar::GenTreeNode< T >::accessData().

template<class T> value_type qgar::GenTree< T >::data (  GenTreeNode< value_type > *  aPNode  )  const [inline]

Get a copy of the data stored in current node. Parameters: aPNode  a pointer to a node

template<class T> T qgar::GenTree< T >::data (   )  const [inline]

Get a copy of the data stored in current node. Definition at line 534 of file GenTree.TCC. References qgar::GenTree< T >::_pCurrent, and qgar::GenTreeNode< T >::data().

template<class T> bool qgar::GenTree< T >::empty (   )  const

Is tree empty? Definition at line 394 of file GenTree.TCC. References qgar::GenTree< T >::_pRoot. Referenced by qgar::GenTree< T >::mergeFirstChild(), and qgar::GenTree< T >::remove().

template<class T> void qgar::GenTree< T >::gotoFirstChild (  GenTreeNode< value_type > *  aPNode  )  [inline]

The first child of the given node becomes the current node. Parameters: aPNode  a pointer to a node

template<class T> void qgar::GenTree< T >::gotoFirstChild (   )  [inline]

The first child of the current node becomes the current node. Definition at line 628 of file GenTree.TCC. References qgar::GenTree< T >::_pCurrent, and qgar::GenTreeNode< T >::pFirstChild().

template<class T> void qgar::GenTree< T >::gotoLSibling (  GenTreeNode< value_type > *  aPNode  )  [inline]

The left sibling of the given node becomes the current node. Parameters: aPNode  a pointer to a node

template<class T> void qgar::GenTree< T >::gotoLSibling (   )  [inline]

The left sibling of the current node becomes the current node. Definition at line 588 of file GenTree.TCC. References qgar::GenTree< T >::_pCurrent, and qgar::GenTreeNode< T >::pLSibling().

template<class T> void qgar::GenTree< T >::gotoParent (  GenTreeNode< value_type > *  aPNode  )  [inline]

The parent of the given node becomes the current node. Parameters: aPNode  a pointer to a node

template<class T> void qgar::GenTree< T >::gotoParent (   )  [inline]

The parent of the current node becomes the current node. Definition at line 569 of file GenTree.TCC. References qgar::GenTree< T >::_pCurrent, and qgar::GenTreeNode< T >::pParent().

template<class T> void qgar::GenTree< T >::gotoRoot (   )  [inline]

The root becomes the current node. Definition at line 559 of file GenTree.TCC. References qgar::GenTree< T >::_pCurrent, and qgar::GenTree< T >::_pRoot. Referenced by qgar::ConnectedComponentsImpl::run().

template<class T> void qgar::GenTree< T >::gotoRSibling (  GenTreeNode< value_type > *  aPNode  )  [inline]

The right sibling of the given node becomes the current node. Parameters: aPNode  a pointer to a node

template<class T> void qgar::GenTree< T >::gotoRSibling (   )  [inline]

The right sibling of the current node becomes the current node. Definition at line 608 of file GenTree.TCC. References qgar::GenTree< T >::_pCurrent, and qgar::GenTreeNode< T >::pRSibling().

template<class T> void qgar::GenTree< T >::insertFirstChild (  const_reference  aData, GenTreeNode< value_type > *  aPNode )  [inline]

Insert a node containing given data as first child of given node. GIV GIV |\ /|\ | \ / | \ | \ ===> / | \ | \ / | \ | \ / | \ fc<-->rs<- NEW<-->fc<-->rs<- /|\ /|\ /|\ /|\ The first child of the given node becomes the right sibling of the given node. The new node becomes the first child of the given node. The given node becomes the current node. Parameters: aData  data to be stored in the new node aPNode  a pointer to a node

template<class T> void qgar::GenTree< T >::insertFirstChild (  const_reference  aData  )

Insert a node containing given data as first child of current node. CUR CUR |\ /|\ | \ / | \ | \ ===> / | \ | \ / | \ | \ / | \ fc<-->rs<- NEW<-->fc<-->rs<- /|\ /|\ /|\ /|\ If the tree is empty, the new node becomes the only node of the tree, i.e. the root and the current node. Otherwise: The first child of the current node becomes the right sibling of the given node. The new node becomes the first child of the current node. The current node remains unchanged. Parameters: aData  data to be stored in the new node

template<class T> void qgar::GenTree< T >::insertLSibling (  const_reference  aData, GenTreeNode< value_type > *  aPNode )  throw (QgarErrorUser) [inline]

Insert a node containing given data as left sibling of given node, which must not be the root. p p /|\ /|\ / | \ / | \ / | \ ===> / | \ / | \ / | \ / | \ / | \ ->ls<-->GIV<-->rs<- ->ls<-->NEW<-->GIV<-->rs<- /|\ /|\ /|\ /|\ /|\ /|\ If the given node has a left sibling, the latter becomes the left sibling of the new node; otherwise, the new node becomes the first child of the parent node. The given node becomes the right sibling of the new node. The parent of the given node becomes the parent of the new node. The given node becomes the current node Parameters: aData  data to be stored in the new node aPNode  a pointer to a node Exceptions: qgar::QgarErrorUser  (current node is the root)

template<class T> void qgar::GenTree< T >::insertLSibling (  const_reference  aData  )  throw (QgarErrorUser)

Insert a node containing given data as left sibling of current node, which must not be the root. p p /|\ /|\ / | \ / | \ / | \ ===> / | \ / | \ / | \ / | \ / | \ ->ls<-->CUR<-->rs<- ->ls<-->NEW<-->CUR<-->rs<- /|\ /|\ /|\ /|\ /|\ /|\ If the tree is empty, the new node becomes the only node of the tree, i.e. the root and the current node. Otherwise: If the current node has a left sibling, the latter becomes the left sibling of the new node; otherwise, the new node becomes the first child of the parent node. The current node becomes the right sibling of the new node. The parent of the current node becomes the parent of the new node. The current node remains unchanged. Parameters: aData  data to be stored in the new node Exceptions: qgar::QgarErrorUser  (current node is the root)

template<class T> void qgar::GenTree< T >::insertParent (  const_reference  aData  )

Insert a node containing given data as parent of current root. NEW | | ROOT ===> ROOT /|\ /|\ If the tree is empty, the new node becomes the only node of the tree, i.e. the root and the current node. Otherwise: The new node becomes the parent of the current root. The current root becomes the first child of the new node. The new node becomes the new root of the tree. The current node remains unchanged. Parameters: aData  data to be stored in the new node Referenced by qgar::ConnectedComponentsImpl::run().

template<class T> void qgar::GenTree< T >::insertRSibling (  const_reference  aData, GenTreeNode< value_type > *  aPNode )  throw (QgarErrorUser) [inline]

Insert a node containing given data as right sibling of given node, which must not be the root. p p /|\ /|\ / | \ / | \ / | \ ===> / | \ / | \ / | \ / | \ / | \ ->ls<-->GIV<-->rs<- ->ls<-->GIV<-->NEW<-->rs<- /|\ /|\ /|\ /|\ /|\ /|\ The right sibling of the given node becomes the right sibling of the new node. The given node becomes the left sibling of the new node. The parent of the given node becomes the parent of the new node. The given node becomes the current node. Parameters: aData  data to be stored in the new node aPNode  a pointer to a node Exceptions: qgar::QgarErrorUser  (current node is the root)

template<class T> void qgar::GenTree< T >::insertRSibling (  const_reference  aData  )  throw (QgarErrorUser)

Insert a node containing given data as right sibling of current node, which must not be the root. p p /|\ /|\ / | \ / | \ / | \ ===> / | \ / | \ / | \ / | \ / | \ ->ls<-->CUR<-->rs<- ->ls<-->CUR<-->NEW<-->rs<- /|\ /|\ /|\ /|\ /|\ /|\ If the tree is empty, the new node becomes the only node of the tree, i.e. the root and the current node. Otherwise: The right sibling of the current node becomes the right sibling of the new node. The current node becomes the left sibling of the new node. The parent of the current node becomes the parent of the new node. The current node remains unchanged. Parameters: aData  data to be stored in the new node Exceptions: qgar::QgarErrorUser  (current node is the root)

template<class T> void qgar::GenTree< T >::mergeFirstChild (  const GenTree< value_type > &  aTree, GenTreeNode< value_type > *  aPNode )

Merge given tree as first child of current node. GIV GIV |\ /|\ | \ / | \ | \ ===> / | \ | \ / | \ | \ / | \ fc<-->rs<- NEW<-->fc<-->rs<- /|\ /|\ /|\ / | \ c1 c2 c3 NEW /|\ / | \ c1 c2 c3 If the given tree is empty, the function has no effect. Otherwise: The first child of the given node becomes the right sibling of the root of the given tree. The root of the given tree becomes the first child of the given node. The given node becomes the parent of the root of the given tree. The given node becomes the current node. Parameters: aTree  a tree aPNode  a pointer to a node Warning: The given node is supposed to belong to the current tree!

template<class T> void qgar::GenTree< T >::mergeFirstChild (  const GenTree< value_type > &  aTree  )

Merge given tree as first child of current node. CUR CUR |\ /|\ | \ / | \ | \ ===> / | \ | \ / | \ | \ / | \ fc<-->rs<- GIV<-->fc<-->rs<- /|\ /|\ /|\ / | \ c1 c2 c3 GIV /|\ / | \ c1 c2 c3 If the given tree is empty, the function has no effect. If the current tree is empty, the given tree becomes the current tree. The new root becomes the current node. Otherwise: The first child of the current node becomes the right sibling of the root of the given tree. The root of the given tree becomes the first child of the current node. The current node becomes the parent of the root of the given tree. The current node remains unchanged. Parameters: aTree  a tree Definition at line 1182 of file GenTree.TCC. References qgar::GenTree< T >::_pRoot, qgar::GenTree< T >::empty(), qgar::GenTree< T >::PRIVATEdeepCopy(), qgar::GenTree< T >::pRoot(), qgar::GenTreeNode< T >::setPLSibling(), qgar::GenTreeNode< T >::setPParent(), and qgar::GenTreeNode< T >::setPRSibling().

template<class T> void qgar::GenTree< T >::mergeLSibling (  const GenTree< value_type > &  aTree, GenTreeNode< value_type > *  aPNode )  throw (QgarErrorUser)

Merge given tree as left sibling of given node, which must not be the root. p p /|\ /|\ / | \ / | \ / | \ ===> / | \ / | \ / | \ / | \ / | \ ->ls<-->GIV<-->rs<- ->ls<-->NEW<-->GIV<-->rs<- /|\ /|\ /|\ /|\ /|\ /|\ /|\ / | \ c1 c2 c3 NEW /|\ / | \ c1 c2 c3 If the given tree is empty, the function has no effect. Otherwise: The left sibling of the given node becomes the left sibling of the root of the given tree. The given node becomes the right sibling of the root of the given tree. The parent of the given node becomes the parent of the root of the given tree. The given node becomes the current node. . Warning: The given node is supposed to belong to the current tree! Parameters: aTree  a tree aPNode  a pointer to a node Exceptions: qgar::QgarErrorUser  (current node is the root)

template<class T> void qgar::GenTree< T >::mergeLSibling (  const GenTree< value_type > &  aTree  )  throw (QgarErrorUser)

Merge given tree as left sibling of current node, which must not be the root. p p /|\ /|\ / | \ / | \ / | \ ===> / | \ / | \ / | \ / | \ / | \ ->ls<-->CUR<-->rs<- ->ls<-->GIV<-->CUR<-->rs<- /|\ /|\ /|\ /|\ /|\ /|\ /|\ / | \ c1 c2 c3 GIV /|\ / | \ c1 c2 c3 If the given tree is empty, the function has no effect. If the current tree is empty, the given tree becomes the current tree. The new root becomes the current node. Otherwise: The left sibling of the current node becomes the left sibling of the root of the given tree. The current node becomes the right sibling of the root of the given tree. The parent of the current node becomes the parent of the root of the given tree. The current node remains unchanged. Parameters: aTree  a tree Exceptions: qgar::QgarErrorUser  (current node is the root) Definition at line 971 of file GenTree.TCC. References qgar::GenTreeNode< T >::setPLSibling(), qgar::GenTreeNode< T >::setPParent(), and qgar::GenTreeNode< T >::setPRSibling().

template<class T> void qgar::GenTree< T >::mergeRSibling (  const GenTree< value_type > &  aTree, GenTreeNode< value_type > *  aPNode )  throw (QgarErrorUser)

Merge given tree as right sibling of current node, which must not be the root. p p /|\ /|\ / | \ / | \ / | \ ===> / | \ / | \ / | \ / | \ / | \ ->ls<-->GIV<-->rs<- ->ls<-->GIV<-->NEW<-->rs<- /|\ /|\ /|\ /|\ /|\ /|\ /|\ / | \ c1 c2 c3 NEW /|\ / | \ c1 c2 c3 If the given tree is empty, the function has no effect. Otherwise: The right sibling of the given node becomes the right sibling of the root of the given tree. The given node becomes the left sibling of the root of the given tree. The parent of the given node becomes the parent of the root of the given tree. The given node becomes the current node. Parameters: aTree  a tree aPNode  a pointer to a node Warning: The given node is supposed to belong to the current tree! Exceptions: qgar::QgarErrorUser  (current node is the root)

template<class T> void qgar::GenTree< T >::mergeRSibling (  const GenTree< value_type > &  aTree  )  throw (QgarErrorUser)

Merge given tree as right sibling of current node, which must not be the root. p p /|\ /|\ / | \ / | \ / | \ ===> / | \ / | \ / | \ / | \ / | \ ->ls<-->CUR<-->rs<- ->ls<-->CUR<-->GIV<-->rs<- /|\ /|\ /|\ /|\ /|\ /|\ /|\ / | \ c1 c2 c3 GIV /|\ / | \ c1 c2 c3 If the given tree is empty, the function has no effect. If the current tree is empty, the given tree becomes the current tree. The new root becomes the current node. Otherwise: The right sibling of the current node becomes the right sibling of the root of the given tree. The current node becomes the left sibling of the root of the given tree. The parent of the current node becomes the parent of the root of the given tree. The current node remains unchanged. Parameters: aTree  a tree Exceptions: qgar::QgarErrorUser  (current node is the root) Definition at line 1080 of file GenTree.TCC. References qgar::GenTreeNode< T >::setPLSibling(), qgar::GenTreeNode< T >::setPParent(), and qgar::GenTreeNode< T >::setPRSibling().

template<class T> GenTree< T > & qgar::GenTree< T >::operator= (  const GenTree< value_type > &  aTree  )

Assignment. The current node of the resulting tree is its root. Parameters: aTree  a tree Warning: Perform a deep copy: All the nodes of the given tree are duplicated. Definition at line 1367 of file GenTree.TCC. References qgar::GenTree< T >::_pRoot, and qgar::GenTree< T >::PRIVATEdeepCopy().

template<class T> GenTreeNode< T > * qgar::GenTree< T >::pCurrent (   )  const [inline]

Get pointer to the current node. Definition at line 419 of file GenTree.TCC. References qgar::GenTree< T >::_pCurrent.

template<class T> GenTreeNode<value_type>* qgar::GenTree< T >::pFirstChild (  GenTreeNode< value_type > *  aPNode  )  const [inline]

Get pointer to the first child of the given node. Parameters: aPNode  a pointer to a node

template<class T> GenTreeNode< T > * qgar::GenTree< T >::pFirstChild (   )  const [inline]

Get pointer to the first child of the current node. Definition at line 489 of file GenTree.TCC. References qgar::GenTree< T >::_pCurrent, and qgar::GenTreeNode< T >::pFirstChild().

template<class T> GenTreeNode<value_type>* qgar::GenTree< T >::pLSibling (  GenTreeNode< value_type > *  aPNode  )  const [inline]

Get pointer to the left sibling of the given node. Parameters: aPNode  a pointer to a node

template<class T> GenTreeNode< T > * qgar::GenTree< T >::pLSibling (   )  const [inline]

Get pointer to the left sibling of the current node. Definition at line 449 of file GenTree.TCC. References qgar::GenTree< T >::_pCurrent, and qgar::GenTreeNode< T >::pLSibling().

template<class T> GenTreeNode<value_type>* qgar::GenTree< T >::pParent (  GenTreeNode< value_type > *  aPNode  )  const [inline]

Get pointer to the parent of the given node. Parameters: aPNode  a pointer to a node

template<class T> GenTreeNode< T > * qgar::GenTree< T >::pParent (   )  const [inline]

Get pointer to the parent of the current node. Definition at line 429 of file GenTree.TCC. References qgar::GenTree< T >::_pCurrent, and qgar::GenTreeNode< T >::pParent().

template<class T> GenTreeNode<value_type>* qgar::GenTree< T >::PRIVATEdeepCopy (  GenTreeNode< value_type > *  aPNode, GenTreeNode< value_type > *  aPFCopy = 0, GenTreeNode< value_type > *  aPLSCopy = 0 )  const [private]

Perform a deep copy of a part of the tree and return a pointer to the root of the copy. Parameters: aPNode  pointer a node, representing the root of the subtree to be copied aPFCopy  pointer to link the copy of the given node to its parent (default 0) aPLSCopy  pointer to link the copy of the given node to its left sibling (default 0) Referenced by qgar::GenTree< T >::mergeFirstChild(), and qgar::GenTree< T >::operator=().

template<class T> void qgar::GenTree< T >::PRIVATEdelete (  GenTreeNode< value_type > *  aPNode  )  [private]

Delete the (sub)tree of given root. Parameters: aPNode  pointer to the root of the subtree to be deleted Referenced by qgar::GenTree< T >::~GenTree().

template<class T> GenTreeNode< T > * qgar::GenTree< T >::pRoot (   )  const [inline]

Get pointer to the root of the tree. Definition at line 409 of file GenTree.TCC. References qgar::GenTree< T >::_pRoot. Referenced by qgar::ConnectedComponents::ConnectedComponents(), qgar::GenTree< T >::mergeFirstChild(), qgar::ConnectedComponents::operator=(), qgar::ConnectedComponents::pRoot(), and qgar::ConnectedComponentsImpl::run().

template<class T> GenTreeNode<value_type>* qgar::GenTree< T >::pRSibling (  GenTreeNode< value_type > *  aPNode  )  const [inline]

Get pointer to the right sibling of the given node. Parameters: aPNode  a pointer to a node

template<class T> GenTreeNode< T > * qgar::GenTree< T >::pRSibling (   )  const [inline]

Get pointer to the right sibling of the current node. Definition at line 469 of file GenTree.TCC. References qgar::GenTree< T >::_pCurrent, and qgar::GenTreeNode< T >::pRSibling().

template<class T> GenTreeNode<value_type>* qgar::GenTree< T >::remove (  GenTreeNode< value_type > *  aPNode  )

Remove given node and return it. p p /|\ /| / | \ / | / | \ ===> / | / | \ / | / | \ / | ->ls<-->GIV<-->rs<- ->ls<-->rs<- /|\ /|\ /|\ /|\ /|\ Parameters: aPNode  a pointer to a node Warning: The (sub)tree whose root is the given node is not deleted: The deletion must be explicitely performed by the user. If the given node is the current node, the root becomes the current node after the removal. Otherwise, the current node remains unchanged. The given node is supposed to belong to the current tree!

template<class T> GenTreeNode< T > * qgar::GenTree< T >::remove (   )

Remove current node and return it. p p /|\ /| / | \ / | / | \ ===> / | / | \ / | / | \ / | ->ls<-->CUR<-->rs<- ->ls<-->rs<- /|\ /|\ /|\ /|\ /|\ No effect if the tree is empty. Warning: The (sub)tree whose root is the initial current node is not deleted: The deletion must be explicitely performed by the user. The root becomes the current node after the removal. Definition at line 1274 of file GenTree.TCC. References qgar::GenTree< T >::_pRoot, qgar::GenTree< T >::empty(), qgar::GenTreeNode< T >::pParent(), qgar::GenTreeNode< T >::setPFirstChild(), qgar::GenTreeNode< T >::setPLSibling(), and qgar::GenTreeNode< T >::setPRSibling().

template<class T> void qgar::GenTree< T >::setData (  const_reference  aData, GenTreeNode< value_type > *  aPNode )  [inline]

Store data in given node. Parameters: aData  data to be stored in current node aPNode  a pointer to a node

template<class T> void qgar::GenTree< T >::setData (  const_reference  aData  )  [inline]

Store data in current node. Parameters: aData  data to be stored in current node

---

Member Data Documentation

template<class T> GenTreeNode<value_type>* qgar::GenTree< T >::_pCurrent [protected]

Pointer to the current node. Definition at line 1266 of file GenTree.H. Referenced by qgar::GenTree< T >::accessData(), qgar::GenTree< T >::data(), qgar::GenTree< T >::GenTree(), qgar::GenTree< T >::gotoFirstChild(), qgar::GenTree< T >::gotoLSibling(), qgar::GenTree< T >::gotoParent(), qgar::GenTree< T >::gotoRoot(), qgar::GenTree< T >::gotoRSibling(), qgar::GenTree< T >::pCurrent(), qgar::GenTree< T >::pFirstChild(), qgar::GenTree< T >::pLSibling(), qgar::GenTree< T >::pParent(), and qgar::GenTree< T >::pRSibling().

template<class T> GenTreeNode<value_type>* qgar::GenTree< T >::_pRoot [protected]

Pointer to the root of the tree. Definition at line 1261 of file GenTree.H. Referenced by qgar::GenTree< T >::empty(), qgar::GenTree< T >::GenTree(), qgar::GenTree< T >::gotoRoot(), qgar::GenTree< T >::mergeFirstChild(), qgar::GenTree< T >::operator=(), qgar::GenTree< T >::pRoot(), qgar::GenTree< T >::remove(), and qgar::GenTree< T >::~GenTree().

---

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

• GenTree.H
• GenTree.TCC