class Tree::TreeNode
TreeNode
Class Description¶ ↑
This class models the nodes for an N-ary tree data structure. The nodes are named, and have a place-holder for the node data (i.e., content of the node). The node names are required to be unique amongst the sibling/peer nodes. Note that the name is implicitly used as an ID within the data structure).
The node’s content is not required to be unique across different nodes in the tree, and can be nil
as well.
The class provides various methods to navigate the tree, traverse the structure, modify contents of the node, change position of the node in the tree, and to make structural changes to the tree.
A node can have any number of child nodes attached to it and hence can be used to create N-ary trees. Access to the child nodes can be made in order (with the conventional left to right access), or randomly.
The node also provides direct access to its parent node as well as other superior parents in the path to root of the tree. In addition, a node can also access its sibling nodes, if present.
Note that while this implementation does not explicitly support directed graphs, the class itself makes no restrictions on associating a node’s content with multiple nodes in the tree. However, having duplicate nodes within the structure is likely to cause unpredictable behavior.
Example¶ ↑
{include:file:examples/example_basic.rb}
@author Anupam Sengupta noinspection RubyTooManyMethodsInspection
Attributes
@!attribute [rw] content Content of this node. Can be nil
. Note that there is no uniqueness constraint related to this attribute.
@see name
@!attribute [r] name
Name of this node. Expected to be unique within the tree.
Note that the name attribute really functions as an ID within the tree structure, and hence the uniqueness constraint is required.
This may be changed in the future, but for now it is best to retain unique names within the tree structure, and use the content
attribute for any non-unique node requirements.
If you want to change the name, you probably want to call rename
instead. Note that name=
is a protected method.
@see content @see rename
@!attribute [r] parent Parent of this node. Will be nil
for a root node.
Public Class Methods
Source
# File lib/tree.rb, line 223 def initialize(name, content = nil) raise ArgumentError, 'Node name HAS to be provided!' if name.nil? name = name.to_s if name.is_a?(Integer) @name = name @content = content set_as_root! @children_hash = {} @children = [] end
Creates a new node with a name and optional content. The node name is expected to be unique within the tree.
The content can be of any type, and defaults to nil
.
@param [Object] name Name of the node. Conventional usage is to pass a
String (Integer names may cause *surprises*)
@param [Object] content Content of the node.
@raise [ArgumentError] Raised if the node name is empty.
@note If the name is an Integer
, then the semantics of {#[]} access
method can be surprising, as an +Integer+ parameter to that method normally acts as an index to the children array, and follows the _zero-based_ indexing convention.
@see []
Public Instance Methods
Source
# File lib/tree.rb, line 341 def <<(child) add(child) end
Convenience synonym for {Tree::TreeNode#add} method.
This method allows an easy mechanism to add node hierarchies to the tree on a given path via chaining the method calls to successive child nodes.
@example Add a child and grand-child to the root
root << child << grand_child
@param [Tree::TreeNode] child the child node to add.
@return [Tree::TreeNode] The added child node.
@see Tree::TreeNode#add
Source
# File lib/tree.rb, line 942 def <=>(other) return nil if other.nil? || !other.is_a?(Tree::TreeNode) name <=> other.name end
Provides a comparison operation for the nodes.
Comparison is based on the natural ordering of the node name objects.
@param [Tree::TreeNode] other The other node to compare against.
@return [Integer] +1 if this node is a ‘successor’, 0 if equal and -1 if
this node is a 'predecessor'. Returns 'nil' if the other object is not a 'Tree::TreeNode'.
Source
# File lib/tree.rb, line 593 def [](name_or_index) raise ArgumentError, 'Name_or_index needs to be provided!' if name_or_index.nil? if name_or_index.is_a?(Integer) @children[name_or_index] else @children_hash[name_or_index] end end
Returns the requested node from the set of immediate children.
-
If the
name
argument is an Integer, then the in-sequence array of children is accessed using the argument as the index (zero-based). -
If the
name
argument is NOT an Integer, then it is taken to be the name of the child node to be returned. -
To use an Integer as the name, convert it to a String first using +<integer>.to_s+.
@param [String|Number] name_or_index Name of the child, or its
positional index in the array of child nodes.
@return [Tree::TreeNode] the requested child node. If the index
in not in range, or the name is not present, then a +nil+ is returned.
@raise [ArgumentError] Raised if the name_or_index
argument is nil
.
@see add
@see initialize
Source
# File lib/tree.rb, line 389 def add(child, at_index = -1) # Only handles the immediate child scenario raise ArgumentError, 'Attempting to add a nil node' unless child raise ArgumentError, 'Attempting add node to itself' if equal?(child) raise ArgumentError, 'Attempting add root as a child' if child.equal?(root) # Lazy man's unique test, won't test if children of child are unique in # this tree too. raise "Child #{child.name} already added!"\ if @children_hash.include?(child.name) child.parent&.remove! child # Detach from the old parent if insertion_range.include?(at_index) @children.insert(at_index, child) else raise 'Attempting to insert a child at a non-existent location'\ " (#{at_index}) "\ 'when only positions from '\ "#{insertion_range.min} to #{insertion_range.max} exist." end @children_hash[child.name] = child child.parent = self child end
Adds the specified child node to this node.
This method can also be used for grafting a subtree into this node’s tree, if the specified child node is the root of a subtree (i.e., has child nodes under it).
this node becomes parent of the node passed in as the argument, and the child is added as the last child (“right most”) in the current set of children of this node.
Additionally you can specify a insert position. The new node will be inserted BEFORE that position. If you don’t specify any position the node will be just appended. This feature is provided to make implementation of node movement within the tree very simple.
If an insertion position is provided, it needs to be within the valid range of:
-children.size..children.size
This is to prevent nil
nodes being created as children if a non-existent position is used.
If the new node being added has an existing parent node, then it will be removed from this pre-existing parent prior to being added as a child to this node. I.e., the child node will effectively be moved from its old parent to this node. In this situation, after the operation is complete, the node will no longer exist as a child for its old parent.
@param [Tree::TreeNode] child The child node to add.
@param [optional, Number] at_index The optional position where the node is
to be inserted.
@return [Tree::TreeNode] The added child node.
@raise [RuntimeError] This exception is raised if another child node with
the same name exists, or if an invalid insertion position is specified.
@raise [ArgumentError] This exception is raised if a nil
node is passed
as the argument.
@see <<
Source
# File lib/tree.rb, line 695 def breadth_each return to_enum(:breadth_each) unless block_given? node_queue = [self] # Create a queue with self as the initial entry # Use a queue to do breadth traversal until node_queue.empty? node_to_traverse = node_queue.shift yield node_to_traverse # Enqueue the children from left to right. node_to_traverse.children { |child| node_queue.push child } end self if block_given? end
Performs breadth-first traversal of the (sub)tree rooted at this node. The traversal at a given level is from left-to-right. this node itself is the first node to be traversed.
@yieldparam node [Tree::TreeNode] Each node.
@see preordered_each
@see breadth_each
@return [Tree::TreeNode] this node, if a block if given @return [Enumerator] an enumerator on this tree, if a block is not given noinspection RubyUnusedLocalVariable
Source
# File lib/tree.rb, line 723 def children(&block) if block_given? @children.each(&block) self else @children.clone end end
An array of all the immediate children of this node. The child nodes are ordered “left-to-right” in the returned array.
If a block is given, yields each child node to the block traversing from left to right.
@yieldparam child [Tree::TreeNode] Each child node.
@return [Tree::TreeNode] This node, if a block is given
@return [Array<Tree::TreeNode>] An array of the child nodes, if no block
is given.
Source
# File lib/tree.rb, line 197 def children? !@children.empty? end
@!attribute [r] children? true
if the this node has any child node.
@return [Boolean] true
if child nodes exist.
@see leaf?
Source
# File lib/tree.rb, line 152 def content? @content != nil end
@!attribute [r] content? true
if this node has content.
@return [Boolean] true
if the node has content.
Source
# File lib/tree.rb, line 239 def detached_copy cloned_content = begin @content&.clone rescue TypeError @content end self.class.new(@name, cloned_content) end
Returns a copy of this node, with its parent and children links removed. The original node remains attached to its tree.
@return [Tree::TreeNode] A copy of this node.
Source
# File lib/tree.rb, line 255 def detached_subtree_copy new_node = detached_copy children { |child| new_node << child.detached_subtree_copy } new_node end
Returns a copy of entire (sub-)tree from this node.
@author Vincenzo Farruggia @since 0.8.0
@return [Tree::TreeNode] A copy of (sub-)tree from this node.
Alias for {Tree::TreeNode#detached_subtree_copy}
Source
# File lib/tree.rb, line 617 def each # :yields: node return to_enum unless block_given? node_stack = [self] # Start with this node until node_stack.empty? current = node_stack.shift # Pop the top-most node next unless current # Might be 'nil' (esp. for binary trees) yield current # and process it # Stack children of the current node at top of the stack node_stack = current.children.concat(node_stack) end self if block_given? end
Traverses each node (including this node) of the (sub)tree rooted at this node by yielding the nodes to the specified block.
The traversal is depth-first and from left-to-right in pre-ordered sequence.
@yieldparam node [Tree::TreeNode] Each node.
@see preordered_each
@see breadth_each
@return [Tree::TreeNode] this node, if a block if given @return [Enumerator] an enumerator on this tree, if a block is not given noinspection RubyUnusedLocalVariable
Source
# File lib/tree.rb, line 746 def each_leaf if block_given? each { |node| yield(node) if node.leaf? } self else self.select(&:leaf?) end end
Yields every leaf node of the (sub)tree rooted at this node to the specified block.
May yield this node as well if this is a leaf node. Leaf traversal is depth-first and left-to-right.
@yieldparam node [Tree::TreeNode] Each leaf node.
@see each
@see breadth_each
@return [Tree::TreeNode] this node, if a block if given @return [Array<Tree::TreeNode>] An array of the leaf nodes noinspection RubyUnusedLocalVariable
Source
# File lib/tree.rb, line 764 def each_level if block_given? level = [self] until level.empty? yield level level = level.map(&:children).flatten end self else each end end
Yields every level of the (sub)tree rooted at this node to the specified block.
Will yield this node as well since it is considered the first level.
@yieldparam level [Array<Tree::TreeNode>] All nodes in the level
@return [Tree::TreeNode] this node, if a block if given @return [Enumerator] an enumerator on this tree, if a block is not given
Source
# File lib/tree.rb, line 785 def first_child @children.first end
First child of this node. Will be nil
if no children are present.
@return [Tree::TreeNode] The first child, or nil
if none is present.
Source
# File lib/tree.rb, line 811 def first_sibling root? ? self : parent.children.first end
First sibling of this node. If this is the root node, then returns itself.
‘First’ sibling is defined as follows:
- First sibling
-
The left-most child of this node’s parent, which may be
this node itself
@return [Tree::TreeNode] The first sibling node.
@see first_sibling?
@see last_sibling
Source
# File lib/tree.rb, line 821 def first_sibling? first_sibling == self end
Returns true
if this node is the first sibling at its level.
@return [Boolean] true
if this is the first sibling.
@see last_sibling?
@see first_sibling
Source
# File lib/tree.rb, line 562 def freeze_tree! each(&:freeze) end
Freezes all nodes in the (sub)tree rooted at this node.
The nodes become immutable after this operation. In effect, the entire tree’s structure and contents become read-only and cannot be changed.
Source
# File lib/tree.rb, line 793 def last_child @children.last end
Last child of this node. Will be nil
if no children are present.
@return [Tree::TreeNode] The last child, or nil
if none is present.
Source
# File lib/tree.rb, line 839 def last_sibling root? ? self : parent.children.last end
Last sibling of this node. If this is the root node, then returns itself.
‘Last’ sibling is defined as follows:
- Last sibling
-
The right-most child of this node’s parent, which may be
this node itself
@return [Tree::TreeNode] The last sibling node.
@see last_sibling?
@see first_sibling
Source
# File lib/tree.rb, line 849 def last_sibling? last_sibling == self end
Returns true
if this node is the last sibling at its level.
@return [Boolean] true
if this is the last sibling.
@see first_sibling?
@see last_sibling
Source
# File lib/tree.rb, line 165 def leaf? !children? end
@!attribute [r] leaf? true
if this node is a leaf - i.e., one without any children.
@return [Boolean] true
if this is a leaf node.
@see children?
Source
# File lib/tree.rb, line 269 def marshal_dump collect(&:create_dump_rep) end
Returns a marshal-dump representation of the (sub)tree rooted at this node.
Source
# File lib/tree.rb, line 295 def marshal_load(dumped_tree_array) nodes = {} dumped_tree_array.each do |node_hash| name = node_hash[:name] parent_name = node_hash[:parent] content = Marshal.load(node_hash[:content]) if parent_name nodes[name] = current_node = self.class.new(name, content) nodes[parent_name].add current_node else # This is the root node, hence initialize self. initialize(name, content) nodes[name] = self # Add self to the list of nodes end end end
Loads a marshaled dump of a tree and returns the root node of the reconstructed tree. See the Marshal class for additional details.
NOTE: This is a potentially unsafe method with similar concerns as with the Marshal#load method, and should not be used with untrusted user provided data.
@todo This method probably should be a class method. It currently clobbers
self and makes itself the root.
Source
# File lib/tree.rb, line 907 def next_sibling return nil if root? idx = parent.children.index(self) parent.children.at(idx + 1) if idx end
Next sibling for this node. The next node is defined as the node to right of this node.
Will return nil
if no subsequent node is present, or if this is a root node.
@return [Tree::treeNode] the next sibling node, if present.
@see previous_sibling
@see siblings
Source
# File lib/tree.rb, line 891 def only_child? root? ? true : parent.children.size == 1 end
true
if this node is the only child of its parent.
As a special case, a root node will always return true
.
@return [Boolean] true
if this is the only child of its parent.
@see siblings
Source
# File lib/tree.rb, line 179 def parentage return nil if root? parentage_array = [] prev_parent = parent while prev_parent parentage_array << prev_parent prev_parent = prev_parent.parent end parentage_array end
@!attribute [r] parentage An array of ancestors of this node in reversed order (the first element is the immediate parent of this node).
Returns nil
if this is a root node.
@return [Array<Tree::TreeNode>] An array of ancestors of this node @return [nil] if this is a root node.
Source
# File lib/tree.rb, line 657 def postordered_each return to_enum(:postordered_each) unless block_given? # Using a marked node in order to skip adding the children of nodes that # have already been visited. This allows the stack depth to be controlled, # and also allows stateful backtracking. marked_node = Struct.new(:node, :visited) node_stack = [marked_node.new(self, false)] # Start with self until node_stack.empty? peek_node = node_stack[0] if peek_node.node.children? && !peek_node.visited peek_node.visited = true # Add the children to the stack. Use the marking structure. marked_children = peek_node.node.children.map { |node| marked_node.new(node, false) } node_stack = marked_children.concat(node_stack) next else yield node_stack.shift.node # Pop and yield the current node end end self if block_given? end
Traverses the (sub)tree rooted at this node in post-ordered sequence.
@yieldparam node [Tree::TreeNode] Each node.
@see preordered_each
@see breadth_each
@return [Tree::TreeNode] this node, if a block if given @return [Enumerator] an enumerator on this tree, if a block is not given noinspection RubyUnusedLocalVariable
Source
# File lib/tree.rb, line 644 def preordered_each(&block) # :yields: node each(&block) end
Traverses the (sub)tree rooted at this node in pre-ordered sequence. This is a synonym of {Tree::TreeNode#each}.
@yieldparam node [Tree::TreeNode] Each node.
@see each
@see breadth_each
@return [Tree::TreeNode] this node, if a block if given @return [Enumerator] an enumerator on this tree, if a block is not given
Source
# File lib/tree.rb, line 924 def previous_sibling return nil if root? idx = parent.children.index(self) parent.children.at(idx - 1) if idx&.positive? end
Previous sibling of this node. Previous node is defined to be the node to left of this node.
Will return nil
if no predecessor node is present, or if this is a root node.
@return [Tree::treeNode] the previous sibling node, if present.
@see next_sibling
@see siblings
Source
# File lib/tree.rb, line 954 def print_tree(level = node_depth, max_depth = nil, block = lambda { |node, prefix| puts "#{prefix} #{node.name}" }) prefix = ''.dup # dup NEEDs to be invoked to make this mutable. if root? prefix << '*' else prefix << '|' unless parent.last_sibling? prefix << (' ' * (level - 1) * 4) prefix << (last_sibling? ? '+' : '|') prefix << '---' prefix << (children? ? '+' : '>') end block.call(self, prefix) # Exit if the max level is defined, and reached. return unless max_depth.nil? || level < max_depth # Child might be 'nil' children do |child| child&.print_tree(level + 1, max_depth, block) end end
Pretty prints the (sub)tree rooted at this node.
@param [Integer] level The indentation level (4 spaces) to start with. @param [Integer] max_depth optional maximum depth at which the printing
with stop.
@param [Proc] block optional block to use for rendering
Source
# File lib/tree.rb, line 498 def remove!(child) return nil unless child @children_hash.delete(child.name) @children.delete(child) child.set_as_root! child end
Removes the specified child node from this node.
This method can also be used for pruning a sub-tree, in cases where the removed child node is the root of the sub-tree to be pruned.
The removed child node is orphaned but accessible if an alternate reference exists. If accessible via an alternate reference, the removed child will report itself as a root node for its sub-tree.
@param [Tree::TreeNode] child The child node to remove.
@return [Tree::TreeNode] The removed child node, or nil
if a nil
was passed in as argument.
@see remove_from_parent!
@see remove_all!
Source
# File lib/tree.rb, line 541 def remove_all! @children.each(&:remove_all!) @children_hash.clear @children.clear self end
Removes all children from this node. If an independent reference exists to the child nodes, then these child nodes report themselves as roots after this operation.
@return [Tree::TreeNode] this node (self
)
@see remove!
@see remove_from_parent!
Source
# File lib/tree.rb, line 529 def remove_from_parent! @parent.remove!(self) unless root? end
Removes this node from its parent. This node becomes the new root for its subtree.
If this is the root node, then does nothing.
@return [Tree:TreeNode] self
(the removed node) if the operation is
successful, +nil+ otherwise.
@see remove_all!
Source
# File lib/tree.rb, line 433 def rename(new_name) old_name = @name if root? self.name = new_name else @parent.rename_child old_name, new_name end old_name end
Renames the node and updates the parent’s reference to it
@param [Object] new_name Name of the node. Conventional usage is to pass a
String (Integer names may cause *surprises*)
@return [Object] The old name
Source
# File lib/tree.rb, line 452 def rename_child(old_name, new_name) raise ArgumentError, "Invalid child name specified: #{old_name}"\ unless @children_hash.key?(old_name) @children_hash[new_name] = @children_hash.delete(old_name) @children_hash[new_name].name = new_name end
Renames the specified child node
@param [Object] old_name old Name of the node. Conventional usage is to
pass a String (Integer names may cause *surprises*)
@param [Object] new_name new Name of the node. Conventional usage is to
pass a String (Integer names may cause *surprises*)
Source
# File lib/tree.rb, line 466 def replace!(old_child, new_child) child_index = @children.find_index(old_child) old_child = remove! old_child add new_child, child_index old_child end
Replaces the specified child node with another child node on this node.
@param [Tree::TreeNode] old_child The child node to be replaced. @param [Tree::TreeNode] new_child The child node to be replaced with.
@return [Tree::TreeNode] The removed child node
Source
# File lib/tree.rb, line 480 def replace_with(node) @parent.replace!(self, node) end
Replaces the node with another node
@param [Tree::TreeNode] node The node to replace this node with
@return [Tree::TreeNode] The replaced child node
Source
# File lib/tree.rb, line 131 def root root = self root = root.parent until root.root? root end
@!attribute [r] root Root node for the (sub)tree to which this node belongs. A root node’s root is itself.
@return [Tree::TreeNode] Root of the (sub)tree.
Source
# File lib/tree.rb, line 142 def root? @parent.nil? end
@!attribute [r] root? Returns true
if this is a root node. Note that orphaned children will also be reported as root nodes.
@return [Boolean] true
if this is a root node.
Source
# File lib/tree.rb, line 869 def siblings if block_given? parent.children.each { |sibling| yield sibling if sibling != self } self else return [] if root? siblings = [] parent.children do |my_sibling| siblings << my_sibling if my_sibling != self end siblings end end
An array of siblings for this node. This node is excluded.
If a block is provided, yields each of the sibling nodes to the block. The root always has nil
siblings.
@yieldparam sibling [Tree::TreeNode] Each sibling node.
@return [Array<Tree::TreeNode>] Array of siblings of this node. Will
return an empty array for *root*
@return [Tree::TreeNode] This node, if no block is given
@see first_sibling
@see last_sibling
Source
# File lib/tree.rb, line 320 def to_s "Node Name: #{@name} Content: #{@content.to_s || '<Empty>'} " \ "Parent: #{root? ? '<None>' : @parent.name.to_s} " \ "Children: #{@children.length} Total Nodes: #{size}" end
Returns string representation of this node. This method is primarily meant for debugging purposes.
@return [String] A string representation of the node.
Private Instance Methods
Source
# File lib/tree.rb, line 419 def insertion_range max = @children.size min = -(max + 1) min..max end
Return a range of valid insertion positions. Used in the add
method.