Generic Tree. More...
#include <rtree.h>
Public Member Functions | |
RTree (void) | |
void | ClearNode (N *node) |
virtual void | Clear (void) |
N * | GetFirst (void) const |
N * | GetLast (void) const |
size_t | GetMaxDepth (void) const |
N * | GetTop (void) |
const N * | GetTop (void) const |
size_t | GetNbNodes (void) const |
size_t | GetNbTopNodes (void) const |
size_t | GetTab (N **tab, N *node, bool children=false) |
void | InsertNode (N *to, N *node) |
void | DeleteNodes (N *node, bool del=bAlloc) |
void | DeleteNode (N *node, bool del=bAlloc) |
void | UpdateDepth (N *node) |
void | MoveNode (N *to, N *node) |
template<bool a> | |
void | Copy (const RTree< T, N, a > &src) |
void | DeepCopy (N *src, N *newparent) |
template<class TUse > | |
N * | GetNode (const TUse &tag) const |
double | GetUpOperationsCost (const N *u, const N *v) const |
virtual | ~RTree (void) |
Protected Attributes | |
N * | First |
N * | Last |
size_t | NbTopNodes |
size_t | NbNodes |
size_t | MaxDepth |
Detailed Description
template<class T, class N, bool bAlloc>
class R::RTree< T, N, bAlloc >
Generic Tree.
- Template Parameters
-
T The class of the tree. It must inherit from RTree. N The class of the nodes in the tree. It must inherit from RNode. bAlloc Specify if the elements are deallocated by the tree. This class implement a generic tree of node of a given class N. The class N must derived from the RNode class.
Here is a example:
- 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.
The tree itself acts a root node, i.e. there may be several top nodes. Since the root node is not managed as an instance of the node class, the developer must always create at least one top node.
When you have to do multiple steps of insertions and deletes in the tree, it is a better idea to ensure the allocations and deallocations through a specific class inheriting from RTree rather than let the latest be the responsible. The RNodesGA class illustrates this approach.
Constructor & Destructor Documentation
RTree | ( | void | ) |
Construct the tree.
|
virtual |
Destruct the tree.
Member Function Documentation
void ClearNode | ( | N * | node | ) |
Call the RNode::Clear() method for a node and all its children.
- Parameters
-
node Node to clear.
|
virtual |
Clear the nodes of the tree. If the tree is not responsible for the deallocation, the method calls RNode::Clear() for each node.
Reimplemented in RXMLStruct.
N* GetFirst | ( | void | ) | const |
- Returns
- the first root node. If null, the tree is empty.
N* GetLast | ( | void | ) | const |
- Returns
- the last root node. If null, the tree is empty.
size_t GetMaxDepth | ( | void | ) | const |
- Returns
- the depth of the tree. If necessary, the depth is recomputed.
N* GetTop | ( | void | ) |
This method should be used with caution, since it works only if there is one top node. If several top nodes were inserted, an exception is generated.
- Returns
- the top node or 0 if no top node.
const N* GetTop | ( | void | ) | const |
This method should be used with caution, since it works only if there is one top node. If several top nodes were inserted, an exception is generated.
size_t GetNbNodes | ( | void | ) | const |
- Returns
- the total number of nodes in the tree.
size_t GetNbTopNodes | ( | void | ) | const |
- Returns
- the total number of top nodes in the tree.
size_t GetTab | ( | N ** | tab, |
N * | node, | ||
bool | children = false |
||
) |
Copy the nodes of a node into a temporary array. This array must have the right size.
- Parameters
-
tab Temporary array. node Parent node. If null, the array contains the top nodes. children Must the children be copied too.
- Returns
- Number of the nodes copied in the array
void InsertNode | ( | N * | to, |
N * | node | ||
) |
Insert a node and attached it to a parent. If the parent is null, the node is considered as one of the top node of the tree.
- Parameters
-
to Parent where the node is to attached. This node must already been attached to the tree. node Node to insert.
void DeleteNodes | ( | N * | node, |
bool | del = bAlloc |
||
) |
Delete all the child nodes of a given node.
- Parameters
-
node Pointer to the node. del Specify if the object must deleted or not. By default, the element is destruct if the container is responsible of the deallocation.
void DeleteNode | ( | N * | node, |
bool | del = bAlloc |
||
) |
Delete a node from the tree. Its child nodes are also deleted.
- Parameters
-
node Node to delete. del Specify if the object must deleted or not. By default, the element is destruct if the container is responsible of the deallocation.
void UpdateDepth | ( | N * | node | ) |
Update the depth of all child nodes of a given node. In practice, at each new step, the depth is incremented of 1.
This method is used by MoveNode.
- Parameters
-
node Parent node.
void MoveNode | ( | N * | to, |
N * | node | ||
) |
Move a node from one parent to another inside the same tree.
- Parameters
-
to Parent where the node is to attached. node Node to insert.
void Copy | ( | const RTree< T, N, a > & | src | ) |
Deep copy of a the tree.
- Template Parameters
-
a Determine if the source container is responsible for the deallocation.
- Parameters
-
src Source tree.
- Warning
- The tree is not emptied before the source tree is copied.
void DeepCopy | ( | N * | src, |
N * | newparent | ||
) |
Do a deep copy of a node of another tree.
- Parameters
-
src Source node in the another tree. newparent Parent node.
N* GetNode | ( | const TUse & | tag | ) | const |
Get a pointer to a certain node of the tree. In practice, the search is done by parsing the tree, starting from the first top node inserted.
- Template Parameters
-
TUse The type of the tag used for the search.
- Parameters
-
tag The tag used.
- Returns
- Return the pointer or 0 if the element is not in the tree.
double GetUpOperationsCost | ( | const N * | u, |
const N * | v | ||
) | const |
Get the cost of the Up operations to move a token from a node to another one.
In their paper TreeRank: A Similarity Measure for Nearest Neighbor Searching in Phylogenetic Databases, Wang, Shan, Shasha and Piel define a similarity measure between two trees based on the different costs of up operations of the nodes of each tree.
- Parameters
-
u First node. v Second node.
- Returns
- Cost of the up operations.
Field Documentation
|
protected |
First top node.
|
protected |
Last top node.
|
protected |
Number of top nodes.
|
protected |
Number of nodes.
|
protected |
Depth of the tree. The depth can be undefined, the value is then set to 'cNoRef'.