class tree #( type T = int ) extends collection#( T )
Implements a tree structure.
| T | optional The type of data collected in a tree. The default is int. |
| tree | Implements a tree structure. |
| Types | |
| tree_node_type | The shorthand of the tree_node type specialized with type T. |
| tree_type | The shorthand of the tree type specialized with type T. |
| Properties | |
| root | The root node of the tree. |
| Functions | |
| new | Creates a new tree. |
| add | virtual Creates a new tree_node of the given element and adds it to the root. |
| add_to_node | virtual Creates a new tree_node of the given element and adds it to the tree as the child of the specified parent. |
| graft | virtual Grafts the given tree_node (and its children) to the tree as the child of the specified parent. |
| clear | virtual Removes all of the elements from this tree. |
| clone | virtual Returns a shallow copy of this tree. |
| is_empty | virtual Returns 1 if this tree contains no elements. |
| get_iterator | virtual Returns an iterator over the elements in this tree. |
| get_breadth_first_iterator | virtual Returns a tree_breadth_first_iterator over the elements in this tree. |
| get_last_node | virtual Returns the last tree node in the breadth-first order. |
| update_locations | virtual Updates the tree_node::location of the entire tree. |
| get_location_name | virtual Returns the human-readable location string of this node from the root. |
typedef tree_node#( T ) tree_node_type
The shorthand of the tree_node type specialized with type T.
typedef tree#( T ) tree_type
The shorthand of the tree type specialized with type T.
function new( collection#(T) c = null, comparator#(T) cmp = null, formatter#(T) fmtr = null )
Creates a new tree.
| c | optional A collection whose elements are to be added to this tree. |
| cmp | optional A strategy object used to compare the elements of type T. If not specified or null, comparator #(T) is used. The default is null. |
| fmtr | optional A strategy object that provides a function to convert the element of type T to a string. If not specified or null, hex_formatter #(T) is used. The default is null. |
tree#(int) int_tree = new();
virtual function bit add( T e )
virtual Creates a new tree_node of the given element and adds it to the root. If the root is empty, make the newly created tree_node as the root.
| e | An element to be added to the root. |
If this tree changed as a result of the call, 1 is returned. Otherwise, 0 is returned.
tree#(int) int_tree = new(); assert( int_tree.add( 123 ) ); // (123) // \__ root node assert( int_tree.add( 234 ) ); // (123) ---- (234) assert( int_tree.add( 345 ) ); // (123) -+-- (234) // | // +-- (345)
virtual function tree_node_type add_to_node( T e, tree_node_type parent = null )
virtual Creates a new tree_node of the given element and adds it to the tree as the child of the specified parent.
| e | An element to be added to the tree. |
| parent | optional The parent tree_node. If the parent is null, add the node to the root. If the root is empty, make the newly created tree_node as the root. Default is null. |
Newly added tree_node.
tree#(int) int_tree = new(); tree_node#(int) tn_123; tree_node#(int) tn_234; tree_node#(int) tn_345; tn_123 = int_tree.add_to_node( 123 ); // (123) // \__ root node tn_234 = int_tree.add_to_node( 234, .parent( tn_123 ) ); // (123) ---- (234) tn_345 = int_tree.add_to_node( 345, .parent( tn_234 ) ); // (123) ---- (234) ---- (345)
virtual function tree_node_type graft( tree_node_type tn, tree_node_type parent = null )
virtual Grafts the given tree_node (and its children) to the tree as the child of the specified parent.
| tn | A tree node to be grafted. |
| parent | optional The parent tree_node. If the parent is null, add the node to the root. If the root is empty, make the tn as the root. Default is null. |
A tree node to be grafted (tn).
tree#(int) int_tree = new(); tree_node#(int) tn; tree_node#(int) tn_123; tree_node#(int) tn_234; tree_node#(int) tn_345; tree_node#(int) tn_456; tn_123 = int_tree.add_to_node( 123 ); tn_234 = int_tree.add_to_node( 234, .parent( tn_123 ) ); // (123) ---- (234) // \__ tn_234 tn_345 = new( 345 ); tn_456 = tn_345.add( 456 ); // (345) ---- (456) // \__ tn_345 tn = int_tree.graft( tn_345, .parent( tn_234 ) ); // (123) ---- (234) ---- (345) --- (456) // \__ tn
virtual function collection#( T ) clone()
virtual Returns a shallow copy of this tree. Only the root is copied. The children are not cloned.
A copy of this tree.
tree#(int) int_tree = new(); collection#(int) cloned; assert( int_tree.add( 123 ) ); assert( int_tree.add( 234 ) ); cloned = int_tree.clone(); assert( cloned.size() == 2 );
virtual function iterator#( T ) get_iterator()
virtual Returns an iterator over the elements in this tree. This function is equivalent to get_breadth_first_iterator.
An iterator.
tree#(int) int_tree = new();
tree_node#(int) tn_123;
tree_node#(int) tn_234;
tree_node#(int) tn_345;
tree_node#(int) tn_456;
iterator#(int) it;
string s;
tn_123 = int_tree.add_to_node( 123 );
tn_234 = int_tree.add_to_node( 234, .parent( tn_123 ) );
tn_345 = int_tree.add_to_node( 345, .parent( tn_123 ) );
tn_456 = int_tree.add_to_node( 456, .parent( tn_234 ) );
// (123) -+-- (234) ---- (456)
// |
// +-- (345)
it = int_tree.get_iterator();
while ( it.has_next() ) s = { s, $sformatf( "%0d ", it.next() ) };
assert( s == "123 234 345 456 " );
virtual function iterator#( T ) get_breadth_first_iterator()
virtual Returns a tree_breadth_first_iterator over the elements in this tree.
An iterator.
tree#(int) int_tree = new();
tree_node#(int) tn_123;
tree_node#(int) tn_234;
tree_node#(int) tn_345;
tree_node#(int) tn_456;
iterator#(int) it;
string s;
tn_123 = int_tree.add_to_node( 123 );
tn_234 = int_tree.add_to_node( 234, .parent( tn_123 ) );
tn_345 = int_tree.add_to_node( 345, .parent( tn_123 ) );
tn_456 = int_tree.add_to_node( 456, .parent( tn_234 ) );
// (123) -+-- (234) ---- (456)
// |
// +-- (345)
it = int_tree.get_breadth_first_iterator();
while ( it.has_next() ) s = { s, $sformatf( "%0d ", it.next() ) };
assert( s == "123 234 345 456 " );
virtual function tree_node_type get_last_node()
virtual Returns the last tree node in the breadth-first order.
The last node. If the last tree node does not exist, returns null.
tree#(int) int_tree = new(); assert( int_tree.add( 123 ) ); assert( int_tree.add( 234 ) ); assert( int_tree.get_last_node().elem == 234 );
virtual function void update_locations()
virtual Updates the tree_node::location of the entire tree.
None.
virtual function string get_location_name( tree_node_type tn )
virtual Returns the human-readable location string of this node from the root. The user must call update_locations prior to this function if the tree structure has changed since the last call of this function (this function does not call update_locations by itself). See tree_node::location for more detail.
| tn | The tree_node to get its location name. |
The location string.
tree#(int) t = new(); tree_node#(int) tn_234; tree_node#(int) tn_345; tree_node#(int) tn_456; tree_node#(int) tn_567; tree_node#(int) root; root = t.add_to_node( 123 ); tn_234 = t.add_to_node( 234 ); tn_345 = t.add_to_node( 345 ); tn_456 = t.add_to_node( 456 ); tn_567 = t.add_to_node( 567, .parent( tn_456 ) ); // (123) -+-- (234) // | // +-- (345) // | // +-- (456) ---- (567) t.update_locations(); assert( t.get_location_name( tn_567 ) == "[0,2,0]" );
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
Implements a node of a tree.
class tree_node #( type T = int )
The shorthand of the tree type specialized with type T.
typedef tree#( T ) tree_type
The root node of the tree.
tree_node_type root
Creates a new tree.
function new( collection#(T) c = null, comparator#(T) cmp = null, formatter#(T) fmtr = null )
virtual Creates a new tree_node of the given element and adds it to the root.
virtual function bit add( T e )
virtual Creates a new tree_node of the given element and adds it to the tree as the child of the specified parent.
virtual function tree_node_type add_to_node( T e, tree_node_type parent = null )
virtual Grafts the given tree_node (and its children) to the tree as the child of the specified parent.
virtual function tree_node_type graft( tree_node_type tn, tree_node_type parent = null )
virtual Removes all of the elements from this tree.
virtual function void clear()
virtual Returns a shallow copy of this tree.
virtual function collection#( T ) clone()
virtual Returns 1 if this tree contains no elements.
virtual function bit is_empty()
virtual Returns an iterator over the elements in this tree.
virtual function iterator#( T ) get_iterator()
virtual Returns a tree_breadth_first_iterator over the elements in this tree.
virtual function iterator#( T ) get_breadth_first_iterator()
Provides a breadth-first iterator to a tree.
class tree_breadth_first_iterator #( type T = int ) extends iterator#( T )
virtual Returns the last tree node in the breadth-first order.
virtual function tree_node_type get_last_node()
virtual Updates the tree_node::location of the entire tree.
virtual function void update_locations()
The queue indicating the location of this tree node in a tree.
int location[$]
virtual Returns the human-readable location string of this node from the root.
virtual function string get_location_name( tree_node_type tn )
singleton Provides strategies to compare objects.
class comparator#( type T = int )
singleton Provides a strategy to convert an object of type T to a string using a hexadecimal format.
class hex_formatter #( type T = int ) extends formatter#( T )