Generic Node. More...

#include <rtree.h>

Inheritance diagram for RNode< T, N, bAlloc >:
Collaboration diagram for RNode< T, N, bAlloc >:

Public Member Functions

 RNode (void)
 RNode (T *tree)
virtual void Clear (void)
N * GetParent (void) const
N * GetFirst (void) const
N * GetLast (void) const
N * GetPrev (void) const
N * GetNext (void) const
size_t GetNbNodes (void) const
size_t GetNbTotalNodes (void) const
size_t GetDepth (void) const
template<class TUse >
N * GetNode (const TUse &tag) const
virtual bool IsEmpty (void)
bool VerifyNode (size_t id)
virtual double GetUpOperationCost (void) const
virtual ~RNode (void)

Protected Attributes

N * Parent
N * Prev
N * Next
N * First
N * Last
size_t NbSubNodes
size_t Depth

Detailed Description

template<class T, class N, bool bAlloc>
singleton R::RNode< T, N, bAlloc >

Generic Node.

Template Parameters
TThe class of the tree. It must inherit from RTree.
NThe class of the nodes of the tree. It must inherit from RNode.
bAllocSpecify if the elements are deallocated by the tree. This class represent a generic node. The user has to derived from this class to create elements that can be handle by a RTree.

To make the necessary comparisons, the tree uses member functions of the class representing the elements (class C). These functions have the signature:

int Compare(const TUse& tag) const;

At least, a compare function must be implemented in the class N:

int Compare(const N&) const;

Here is an example:

#include <rtree.h>
#include <rnode.h>
#include <rnodecursor.h>
using namespace R;
class MyTree; // Forward declaration
class MyNode : public RNode<MyTree,MyNode,true>
RString Name;
MyNode(const RString& name) : RNode<MyTree,MyNode,true>(), Name(name) {}
int Compare(const MyNode& node) const {return(Name.Compare(node.Name));}
void DoSomething(void)
for(size_t i=0;i<GetDepth();i++)
cout<<" ";
friend class R::RNodeCursor<MyTree,MyNode>;
class MyTree : public RTree<MyTree,MyNode,true>
MyTree(void) : RTree<MyTree,MyNode,true>() {}
friend class R::RNodeCursor<MyTree,MyNode>;
int main()
MyTree Tree;
MyNode *a,*b,*c,*d,*m;
Tree.InsertNode(0,a=new MyNode("mammal"));
Tree.InsertNode(a,m=new MyNode("rabbit"));
Tree.InsertNode(a,d=new MyNode("carnivore"));
Tree.InsertNode(m,b=new MyNode("fox"));
Tree.InsertNode(m,c=new MyNode("dog"));
Note that RNodeCursor class is defined as friend class for both, the node class and the tree class. This is necessary to use the RNodeCursor class.

In practice, all child nodes of a given node (or the root node) are stored as a doubly linked list.

Constructor & Destructor Documentation

RNode ( void  )

Default constructor.

RNode ( T *  tree)

Default constructor.

treeThe tree.
virtual ~RNode ( void  )

Destruct the node.

Member Function Documentation

virtual void Clear ( void  )

Clear the node.

N* GetParent ( void  ) const
a pointer to the concept tree.
a pointer to the concept tree. Return the parent of the node.
Pointer to N.
N* GetFirst ( void  ) const
the first child node. If null, the node has no children.
N* GetLast ( void  ) const
the last child node. If null, the node has no children.
N* GetPrev ( void  ) const
the previous node of the same parent. If null, the node is the first child.
N* GetNext ( void  ) const
the next node of the same parent. If null, the node is the last child.
size_t GetNbNodes ( void  ) const
the number of child nodes.
size_t GetNbTotalNodes ( void  ) const
the total number of child nodes (including all possible children).
size_t GetDepth ( void  ) const

Get the depth of the node.

N* GetNode ( const TUse &  tag) const

Get a pointer to a certain child node. In practice, In practice, the search is done by parsing the tree starting from the first child node inserted.

Template Parameters
TUseThe type of the tag used for the search.
tagThe tag used.
Return the pointer or 0 if the element is not a child node.
virtual bool IsEmpty ( void  )

Method call to insert a node.

nodeNode to insert. Test if the tag is empty, i.e. it has no child nodes.

Reimplemented in RXMLTag.

bool VerifyNode ( size_t  id)

Verify the integrity of the node.

idIdentifier identifying the node for the caller.
true if the node seems coherent.
virtual double GetUpOperationCost ( void  ) const

Get the cost of an Up operation of the current node. By default, the cost equals to 1.

In their paper TreeRank: A Similarity Measure for Nearest Neighbor Searching in Phylogenetic Databases, Wang, Shan, Shasha and Piel define the up operation as the operation that moves a token from one node to its parent.

Cost of the up operation.

Field Documentation

N* Parent

Parent Node.

N* Prev

Previous node.

N* Next

Next node.

N* First

First child node.

N* Last

Last child node.

size_t NbSubNodes

Number of child nodes

size_t Depth

Depth of the node.