Generic Node. More...

#include <rtree.h>

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

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;
public:
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<<" ";
cout<<Name<<endl;
for(Cur.Start();!Cur.End();Cur.Next())
Cur()->DoSomething();
}
friend class R::RNodeCursor<MyTree,MyNode>;
};
class MyTree : public RTree<MyTree,MyNode,true>
{
public:
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"));
for(Cur.Start();!Cur.End();Cur.Next())
Cur()->DoSomething();
}
Remarks
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.

Parameters
treeThe tree.
virtual ~RNode ( void  )
virtual

Destruct the node.

Member Function Documentation

virtual void Clear ( void  )
virtual

Clear the node.

N* GetParent ( void  ) const
Returns
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
Returns
the first child node. If null, the node has no children.
N* GetLast ( void  ) const
Returns
the last child node. If null, the node has no children.
N* GetPrev ( void  ) const
Returns
the previous node of the same parent. If null, the node is the first child.
N* GetNext ( void  ) const
Returns
the next node of the same parent. If null, the node is the last child.
size_t GetNbNodes ( void  ) const
Returns
the number of child nodes.
size_t GetNbTotalNodes ( void  ) const
Returns
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.
Parameters
tagThe tag used.
Returns
Return the pointer or 0 if the element is not a child node.
virtual bool IsEmpty ( void  )
virtual

Method call to insert a node.

Parameters
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.

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

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.

Returns
Cost of the up operation.

Field Documentation

N* Parent
protected

Parent Node.

N* Prev
protected

Previous node.

N* Next
protected

Next node.

N* First
protected

First child node.

N* Last
protected

Last child node.

size_t NbSubNodes
protected

Number of child nodes

size_t Depth
protected

Depth of the node.