class tree_node #( type T = int )
Implements a node of a tree.
| T | optional The type of data collected in a tree_node. The default is int. |
| tree_node | Implements a node of a tree. |
| Types | |
| tree_node_type | The shorthand of the tree node type specialized with type T. |
| Properties | |
| elem | The element stored at this tree node. |
| parent | The parent node of this tree node. |
| children | The child nodes this tree node has. |
| relatives | The tree nodes this tree node is related to. |
| location | The queue indicating the location of this tree node in a tree. |
| Functions | |
| new | Creates a new tree node. |
| add | virtual Creates a tree node of the given element and adds it as a new child. |
| graft | virtual Grafts the given tree node (and its children) as a new child. |
| prune | virtual Removes the specified child (and its descendants). |
| get_num_children | virtual Returns the number of (immediate) children of this tree node. |
| has_child | virtual Returns if this tree node has at least one child. |
int location[$]
The queue indicating the location of this tree node in a tree. Every child appends its index to the queue. The new, add, graft, and prune functions do not update the location automatically. You must call tree::update_locations to update the entire tree-node locations. To get a human-readable location string, use tree::get_location_name.
[0] -+-- [0,0] -+-- [0,0,0] ---- [0,0,0,0]
root | |
node | +-- [0,0,1]
|
+-- [0,1] -+-- [0,1,0] ---- [0,1,0,0]
| |
| +-- [0,1,1] -+-- [0,1,1,0]
| |
| +-- [0,1,1,1]
| |
| +-- [0,1,1,2]
+-- [0,2]
virtual function tree_node_type add( T e )
virtual Creates a tree node of the given element and adds it as a new child.
| e | An element to be added. |
Newly added tree node.
tree_node#(int) tn; tree_node#(int) tn_123 = new( 123 ); tn = tn_123.add( 234 ); // (123) ---- (234) <~~ tn tn = tn_123.add( 345 ); // (123) -+-- (234) // | // +-- (345) <~~ tn tn = tn_123.add( 456 ).add( 567 ); // chain // (123) -+-- (234) // | // +-- (345) // | // +-- (456) ---- (567) <~~ tn
virtual function tree_node_type graft( tree_node_type tn )
virtual Grafts the given tree node (and its children) as a new child.
| tn | A tree node to be grafted. |
A tree node to be grafted (tn).
tree_node#(int) tn_123; tree_node#(int) tn_234; tree_node#(int) tn_345; tree_node#(int) tn_456; tree_node#(int) tn; tn_123 = new( 123 ); tn_234 = tn_123.add( 234 ); // (123) --- (234) // \__ tn_234 tn_345 = new( 345 ); tn_456 = tn_345.add( 456 ); // (345) ---- (456) // \__ tn_345 tn = tn_234.graft( tn_345 ); // (123) ---- (234) --- (345) ---- (456) // \__ tn
virtual function tree_node_type prune( int index = 0 )
virtual Removes the specified child (and its descendants).
| index | optional The index of the child. The default is 0. If the specified child does not exist, this function does nothing. |
This tree node.
tree_node#(int) tn; tree_node#(int) tn_123 = new( 123 ); tn = tn_123.add( 234 ); tn = tn_123.add( 456 ).add( 567 ); tn = tn_123.add( 345 ); // (123) -+-- (234) // | // +-- (456) ---- (567) // | // +-- (345) tn = tn_123.prune( .index( 1 ) ); // (123) -+-- (234) // | // +-- (345)
virtual function int get_num_children()
virtual Returns the number of (immediate) children of this tree node. This function does not count the number of descendants recursively.
The number of children.
tree_node#(int) tn; tree_node#(int) tn_123 = new( 123 ); tn = tn_123.add( 234 ); tn = tn_123.add( 345 ); tn = tn_123.add( 456 ).add( 567 ); // (123) -+-- (234) // | // +-- (345) // | // +-- (456) ---- (567) assert( tn_123.get_num_children() == 3 ); // not 4
virtual function bit has_child()
virtual Returns if this tree node has at least one child.
If this tree node has a child (or children), returns 1. Otherwise, returns 0.
tree_node#(int) tn; tree_node#(int) tn_123 = new( 123 ); tn = tn_123.add( 234 ); tn = tn_123.add( 345 ); tn = tn_123.add( 456 ).add( 567 ); // (123) -+-- (234) // | // +-- (345) // | // +-- (456) ---- (567) assert( tn_123.has_child() == 1 );
Implements a node of a tree.
class tree_node #( type T = int )
Implements a tree structure.
class tree #( type T = int ) extends collection#( T )
The shorthand of the tree node type specialized with type T.
typedef tree_node#( T ) tree_node_type
The element stored at this tree node.
T elem
The parent node of this tree node.
tree_node_type parent
The child nodes this tree node has.
tree_node_type children[$]
The tree nodes this tree node is related to.
tree_node_type relatives[$]
The queue indicating the location of this tree node in a tree.
int location[$]
Creates a new tree node.
function new( T elem )
virtual Creates a tree node of the given element and adds it as a new child.
virtual function tree_node_type add( T e )
virtual Grafts the given tree node (and its children) as a new child.
virtual function tree_node_type graft( tree_node_type tn )
virtual Removes the specified child (and its descendants).
virtual function tree_node_type prune( int index = 0 )
virtual Returns the number of (immediate) children of this tree node.
virtual function int get_num_children()
virtual Returns if this tree node has at least one child.
virtual function bit has_child()
virtual Updates the tree_node::location of the entire tree.
virtual function void update_locations()
virtual Returns the human-readable location string of this node from the root.
virtual function string get_location_name( tree_node_type tn )