Class: Tree::TreeNode

Inherits:
Object
  • Object
show all
Includes:
Comparable, Enumerable, Utils::HashConverter, Utils::JSONConverter, Utils::TreeMergeHandler, Utils::TreeMetricsHandler, Utils::TreePathHandler
Defined in:
lib/tree.rb

Overview

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

#!/usr/bin/env ruby
#
# example_basic.rb:: Basic usage of the tree library.
#
# Author:  Anupam Sengupta
# Time-stamp: <2022-06-19 22:52:29 anupam>
# Copyright (C) 2013, 2015, 2022 Anupam Sengupta 
#
# The following example implements this tree structure:
#
#                    +------------+
#                    |    ROOT    |
#                    +-----+------+
#            +-------------+------------+
#            |                          |
#    +-------+-------+          +-------+-------+
#    |  CHILD 1      |          |  CHILD 2      |
#    +-------+-------+          +---------------+
#            |
#            |
#    +-------+-------+
#    | GRANDCHILD 1  |
#    +---------------+
#
# frozen_string_literal: true

# ..... Example starts.
require 'tree' # Load the library

# ..... Create the root node first. Note that every node has a name and an
# ..... optional content payload.
root_node = Tree::TreeNode.new('ROOT', 'Root Content')
root_node.print_tree

# ..... Now insert the child nodes. Note that you can "chain" the child
# ..... insertions for a given path to any depth.
root_node << Tree::TreeNode.new('CHILD1', 'Child1 Content') \
          << Tree::TreeNode.new('GRANDCHILD1', 'GrandChild1 Content')
root_node << Tree::TreeNode.new('CHILD2', 'Child2 Content')

# ..... Lets print the representation to stdout. This is primarily used for
# ..... debugging purposes.
root_node.print_tree

# ..... Lets directly access children and grandchildren of the root. The can be
# ..... "chained" for a given path to any depth.
child1       = root_node['CHILD1']
grand_child1 = root_node['CHILD1']['GRANDCHILD1']

# ..... Now lets retrieve siblings of the current node as an array.
siblings_of_child1 = child1.siblings

# ..... Lets retrieve immediate children of the root node as an array.
children_of_root = root_node.children

# ..... Retrieve the parent of a node.
parent = child1.parent

# ..... This is a depth-first and L-to-R pre-ordered traversal.
root_node.each { |node| node.content.reverse }

# ..... Lets remove a child node from the root node.
root_node.remove!(child1)

noinspection RubyTooManyMethodsInspection

Author:

  • Anupam Sengupta

Direct Known Subclasses

BinaryTreeNode

Core Attributes collapse

Metrics and Measures collapse

Node Creation collapse

Structure Modification collapse

Tree Traversal collapse

Navigating the Child Nodes collapse

Navigating the Sibling Nodes collapse

Converting to/from JSON collapse

Merging Trees collapse

Node Path collapse

Instance Method Summary collapse

Constructor Details

#initialize(name, content = nil) ⇒ TreeNode

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.

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.

Parameters:

  • name (Object) —

    Name of the node. Conventional usage is to pass a String (Integer names may cause surprises)

  • content (Object) (defaults to: nil) —

    Content of the node.

Raises:

  • (ArgumentError) —

    Raised if the node name is empty.

See Also:



223
224
225
226
227
228
229
230
231
232
233
 
# 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

Instance Attribute Details

#breadth ⇒ Integer (readonly) Originally defined in module Utils::TreeMetricsHandler

Breadth of the tree at this node’s level. A single node without siblings has a breadth of 1.

Breadth is defined to be:

Breadth

Number of sibling nodes to this node + 1 (this node itself),

i.e., the number of children the parent of this node has.

Returns:

  • (Integer) —

    breadth of the node’s level.

#children? ⇒ Boolean (readonly) Also known as: has_children?

true if the this node has any child node.

Returns:

  • (Boolean) —

    true if child nodes exist.

See Also:



197
198
199
 
# File 'lib/tree.rb', line 197

def children?
  !@children.empty?
end

#content ⇒ Object

Content of this node. Can be nil. Note that there is no uniqueness constraint related to this attribute.

See Also:



120
121
122
 
# File 'lib/tree.rb', line 120

def content
  @content
end

#content? ⇒ Boolean (readonly) Also known as: has_content?

true if this node has content.

Returns:

  • (Boolean) —

    true if the node has content.



152
153
154
 
# File 'lib/tree.rb', line 152

def content?
  @content != nil
end

#in_degree ⇒ Integer (readonly) Originally defined in module Utils::TreeMetricsHandler

The incoming edge-count of this node.

In-degree is defined as:

In-degree

Number of edges arriving at the node (0 for root, 1 for

all other nodes)

  • In-degree = 0 for a root or orphaned node

  • In-degree = 1 for a node which has a parent

Returns:

  • (Integer) —

    The in-degree of this node.

#leaf? ⇒ Boolean (readonly) Also known as: is_leaf?

true if this node is a leaf - i.e., one without any children.

Returns:

  • (Boolean) —

    true if this is a leaf node.

See Also:



165
166
167
 
# File 'lib/tree.rb', line 165

def leaf?
  !children?
end

#length ⇒ Integer (readonly) Originally defined in module Utils::TreeMetricsHandler

Deprecated.

This method name is ambiguous and may be removed. Use

Convenience synonym for #size.

#size instead.

Returns:

  • (Integer) —

    The total number of nodes in this (sub)tree.

See Also:

#level ⇒ Object (readonly) Originally defined in module Utils::TreeMetricsHandler

Alias for #node_depth

See Also:

#name ⇒ Object

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 Also:



113
114
115
 
# File 'lib/tree.rb', line 113

def name
  @name
end

#node_depth ⇒ Integer (readonly) Originally defined in module Utils::TreeMetricsHandler

Depth of this node in its tree. Depth of a node is defined as:

Depth

Length of the node’s path to its root. Depth of a root node is

zero.

#level is an alias for this method.

Returns:

  • (Integer) —

    Depth of this node.

#node_height ⇒ Integer (readonly) Originally defined in module Utils::TreeMetricsHandler

Height of the (sub)tree from this node. Height of a node is defined as:

Height

Length of the longest downward path to a leaf from the node.

  • Height from a root node is height of the entire tree.

  • The height of a leaf node is zero.

Returns:

  • (Integer) —

    Height of the node.

#out_degree ⇒ Integer (readonly) Originally defined in module Utils::TreeMetricsHandler

The outgoing edge-count of this node.

Out-degree is defined as:

Out-degree

Number of edges leaving the node (zero for leafs)

Returns:

  • (Integer) —

    The out-degree of this node.

#parent ⇒ Object

Parent of this node. Will be nil for a root node.



124
125
126
 
# File 'lib/tree.rb', line 124

def parent
  @parent
end

#parentage ⇒ Array<Tree::TreeNode>? (readonly)

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.

Returns:

  • (Array<Tree::TreeNode>) —

    An array of ancestors of this node

  • (nil) —

    if this is a root node.



179
180
181
182
183
184
185
186
187
188
189
 
# 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

#root ⇒ Tree::TreeNode (readonly)

Root node for the (sub)tree to which this node belongs. A root node’s root is itself.

Returns:



131
132
133
134
135
 
# File 'lib/tree.rb', line 131

def root
  root = self
  root = root.parent until root.root?
  root
end

#root? ⇒ Boolean (readonly) Also known as: is_root?

Returns true if this is a root node. Note that orphaned children will also be reported as root nodes.

Returns:

  • (Boolean) —

    true if this is a root node.



142
143
144
 
# File 'lib/tree.rb', line 142

def root?
  @parent.nil?
end

#size ⇒ Integer (readonly) Originally defined in module Utils::TreeMetricsHandler

Total number of nodes in this (sub)tree, including this node.

Size of the tree is defined as:

Size

Total number nodes in the subtree including this node.

Returns:

  • (Integer) —

    Total number of nodes in this (sub)tree.

Instance Method Details

#<<(child) ⇒ Tree::TreeNode

Convenience synonym for #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.

Examples:

Add a child and grand-child to the root

root << child << grand_child

Parameters:

Returns:

See Also:



341
342
343
 
# File 'lib/tree.rb', line 341

def <<(child)
  add(child)
end

#<=>(other) ⇒ Integer

Provides a comparison operation for the nodes.

Comparison is based on the natural ordering of the node name objects.

Parameters:

Returns:

  • (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’.



942
943
944
945
946
 
# File 'lib/tree.rb', line 942

def <=>(other)
  return nil if other.nil? || !other.is_a?(Tree::TreeNode)

  name <=> other.name
end

#[](name_or_index) ⇒ Tree::TreeNode

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.

Parameters:

  • name_or_index (String|Number) —

    Name of the child, or its positional index in the array of child nodes.

Returns:

  • (Tree::TreeNode) —

    the requested child node. If the index in not in range, or the name is not present, then a nil is returned.

Raises:

  • (ArgumentError) —

    Raised if the name_or_index argument is nil.

See Also:



593
594
595
596
597
598
599
600
601
 
# 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

#add(child, at_index = -1)) ⇒ Tree::TreeNode

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.

Parameters:

  • child (Tree::TreeNode) —

    The child node to add.

  • at_index (optional, Number) (defaults to: -1)) —

    The optional position where the node is to be inserted.

Returns:

Raises:

  • (RuntimeError) —

    This exception is raised if another child node with the same name exists, or if an invalid insertion position is specified.

  • (ArgumentError) —

    This exception is raised if a nil node is passed as the argument.

See Also:



389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
 
# 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

#add_from_hash(children) ⇒ Array Originally defined in module Utils::HashConverter

Instantiate and insert child nodes from data in a Ruby Hash

This method is used in conjunction with from_hash to provide a convenient way of building and inserting child nodes present in a Ruby hashes.

This method will instantiate a node instance for each top- level key of the input hash, to be inserted as children of the receiver instance.

Nested hashes are expected and further child nodes will be created and added accordingly. If a hash key is a single value that value will be used as the name for the node. If a hash key is an Array, both node name and content will be populated.

A leaf element of the tree should be represented as a hash key with corresponding value nil or {}.

Examples:

root = Tree::TreeNode.new(:A, "Root content!")
root.add_from_hash({:B => {:D => {}}, [:C, "C content!"] => {}})

Parameters:

  • children (Hash) —

    The hash of child subtrees.

Returns:

  • (Array) —

    Array of child nodes added

Raises:

  • (ArgumentError) —

    This exception is raised if a non-hash is passed.

See Also:

Author:

#as_json(_options = {}) ⇒ Object Originally defined in module Utils::JSONConverter

Creates a JSON ready Hash for the #to_json method.

Rails uses JSON in ActiveSupport, and all Rails JSON encoding goes through as_json.

noinspection RubyUnusedLocalVariable

Parameters:

  • _options (Object) (defaults to: {})

Returns:

  • A hash based representation of the JSON

See Also:

Author:

Since:

  • 0.8.3

#breadth_each {|node| ... } ⇒ Tree::TreeNode, Enumerator

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.

noinspection RubyUnusedLocalVariable

Yield Parameters:

Returns:

  • (Tree::TreeNode) —

    this node, if a block if given

  • (Enumerator) —

    an enumerator on this tree, if a block is not given

See Also:



695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
 
# 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

#children {|child| ... } ⇒ Tree::TreeNode+

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.

Yield Parameters:

Returns:



723
724
725
726
727
728
729
730
 
# File 'lib/tree.rb', line 723

def children(&block)
  if block_given?
    @children.each(&block)
    self
  else
    @children.clone
  end
end

#detached_copy ⇒ Tree::TreeNode

Returns a copy of this node, with its parent and children links removed. The original node remains attached to its tree.

Returns:



239
240
241
242
243
244
245
246
247
 
# 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

#detached_subtree_copy ⇒ Tree::TreeNode Also known as: dup

Returns a copy of entire (sub-)tree from this node.

Returns:

Author:

  • Vincenzo Farruggia

Since:

  • 0.8.0



255
256
257
258
259
 
# 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

#each {|node| ... } ⇒ Tree::TreeNode, Enumerator

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.

noinspection RubyUnusedLocalVariable

Yield Parameters:

Returns:

  • (Tree::TreeNode) —

    this node, if a block if given

  • (Enumerator) —

    an enumerator on this tree, if a block is not given

See Also:



617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
 
# 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

#each_leaf {|node| ... } ⇒ Tree::TreeNode+

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.

noinspection RubyUnusedLocalVariable

Yield Parameters:

Returns:

See Also:



746
747
748
749
750
751
752
753
 
# 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

#each_level {|level| ... } ⇒ Tree::TreeNode, Enumerator

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.

Yield Parameters:

Returns:

  • (Tree::TreeNode) —

    this node, if a block if given

  • (Enumerator) —

    an enumerator on this tree, if a block is not given



764
765
766
767
768
769
770
771
772
773
774
775
 
# 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

#first_child ⇒ Tree::TreeNode

First child of this node. Will be nil if no children are present.

Returns:



785
786
787
 
# File 'lib/tree.rb', line 785

def first_child
  @children.first
end

#first_sibling ⇒ Tree::TreeNode

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

Returns:

See Also:



811
812
813
 
# File 'lib/tree.rb', line 811

def first_sibling
  root? ? self : parent.children.first
end

#first_sibling? ⇒ Boolean Also known as: is_first_sibling?

Returns true if this node is the first sibling at its level.

Returns:

  • (Boolean) —

    true if this is the first sibling.

See Also:



821
822
823
 
# File 'lib/tree.rb', line 821

def first_sibling?
  first_sibling == self
end

#freeze_tree! ⇒ Object

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.



562
563
564
 
# File 'lib/tree.rb', line 562

def freeze_tree!
  each(&:freeze)
end

#last_child ⇒ Tree::TreeNode

Last child of this node. Will be nil if no children are present.

Returns:



793
794
795
 
# File 'lib/tree.rb', line 793

def last_child
  @children.last
end

#last_sibling ⇒ Tree::TreeNode

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

Returns:

See Also:



839
840
841
 
# File 'lib/tree.rb', line 839

def last_sibling
  root? ? self : parent.children.last
end

#last_sibling? ⇒ Boolean Also known as: is_last_sibling?

Returns true if this node is the last sibling at its level.

Returns:

  • (Boolean) —

    true if this is the last sibling.

See Also:



849
850
851
 
# File 'lib/tree.rb', line 849

def last_sibling?
  last_sibling == self
end

#marshal_dump ⇒ Object

Returns a marshal-dump representation of the (sub)tree rooted at this node.



269
270
271
 
# File 'lib/tree.rb', line 269

def marshal_dump
  collect(&:create_dump_rep)
end

#marshal_load(dumped_tree_array) ⇒ Object

TODO:

This method probably should be a class method. It currently clobbers self and makes itself the root.

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.



295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
 
# 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

#merge(other_tree) ⇒ Tree::TreeNode Originally defined in module Utils::TreeMergeHandler

Merge two trees that share the same root node and returns a new tree.

The new tree contains the contents of the merge between other_tree and self. Duplicate nodes (coming from other_tree) will NOT be overwritten in self.

Parameters:

Returns:

Raises:

  • (TypeError) —

    This exception is raised if other_tree is not a TreeNode.

  • (ArgumentError) —

    This exception is raised if other_tree does not have the same root node as self.

Author:

Since:

  • 0.9.0

#merge!(other_tree) ⇒ Object Originally defined in module Utils::TreeMergeHandler

Merge in another tree (that shares the same root node) into this tree. Duplicate nodes (coming from other_tree) will NOT be overwritten in self.

Parameters:

Raises:

  • (TypeError) —

    This exception is raised if other_tree is not a TreeNode.

  • (ArgumentError) —

    This exception is raised if other_tree does not have the same root node as self.

Author:

Since:

  • 0.9.0

#next_sibling ⇒ Tree::treeNode

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.

Returns:

  • (Tree::treeNode) —

    the next sibling node, if present.

See Also:



907
908
909
910
911
912
 
# 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

#only_child? ⇒ Boolean Also known as: is_only_child?

true if this node is the only child of its parent.

As a special case, a root node will always return true.

Returns:

  • (Boolean) —

    true if this is the only child of its parent.

See Also:



891
892
893
 
# File 'lib/tree.rb', line 891

def only_child?
  root? ? true : parent.children.size == 1
end

#path_as_array ⇒ Array Originally defined in module Utils::TreePathHandler

Returns the node-names from this node to the root as an array. The first element is the root node name, and the last element is this node’s name.

node

Returns:

  • (Array) —

    The array containing the node names for the path to this

#path_as_string(separator = '=>') ⇒ String Originally defined in module Utils::TreePathHandler

Returns the path of this node from the root as a string, with the node names separated using the specified separator. The path is listed left to right from the root node.

Parameters:

  • separator (defaults to: '=>') —

    The optional separator to use. The default separator is ‘+=>+’.

Returns:

  • (String) —

    The node path with names separated using the specified separator.

#postordered_each {|node| ... } ⇒ Tree::TreeNode, Enumerator

Traverses the (sub)tree rooted at this node in post-ordered sequence.

noinspection RubyUnusedLocalVariable

Yield Parameters:

Returns:

  • (Tree::TreeNode) —

    this node, if a block if given

  • (Enumerator) —

    an enumerator on this tree, if a block is not given

See Also:



657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
 
# 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

#preordered_each {|node| ... } ⇒ Tree::TreeNode, Enumerator

Traverses the (sub)tree rooted at this node in pre-ordered sequence. This is a synonym of #each.

Yield Parameters:

Returns:

  • (Tree::TreeNode) —

    this node, if a block if given

  • (Enumerator) —

    an enumerator on this tree, if a block is not given

See Also:



644
645
646
 
# File 'lib/tree.rb', line 644

def preordered_each(&block) # :yields: node
  each(&block)
end

#previous_sibling ⇒ Tree::treeNode

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.

Returns:

  • (Tree::treeNode) —

    the previous sibling node, if present.

See Also:



924
925
926
927
928
929
 
# 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

#print_tree(level = node_depth, max_depth = nil, block = lambda { |node, prefix| puts "#{prefix} #{node.name}" }) ⇒ Object

Pretty prints the (sub)tree rooted at this node.

Parameters:

  • level (Integer) (defaults to: node_depth) —

    The indentation level (4 spaces) to start with.

  • max_depth (Integer) (defaults to: nil) —

    optional maximum depth at which the printing with stop.

  • block (Proc) (defaults to: lambda { |node, prefix| puts "#{prefix} #{node.name}" }) —

    optional block to use for rendering



954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
 
# 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

#remove!(child) ⇒ Tree::TreeNode

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.

Parameters:

Returns:

  • (Tree::TreeNode) —

    The removed child node, or nil if a nil was passed in as argument.

See Also:



498
499
500
501
502
503
504
505
 
# 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

#remove_all! ⇒ Tree::TreeNode

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.

Returns:

See Also:



541
542
543
544
545
546
547
 
# File 'lib/tree.rb', line 541

def remove_all!
  @children.each(&:remove_all!)

  @children_hash.clear
  @children.clear
  self
end

#remove_from_parent! ⇒ Tree:TreeNode

Removes this node from its parent. This node becomes the new root for its subtree.

If this is the root node, then does nothing.

Returns:

  • (Tree:TreeNode) —

    self (the removed node) if the operation is successful, nil otherwise.

See Also:



529
530
531
 
# File 'lib/tree.rb', line 529

def remove_from_parent!
  @parent.remove!(self) unless root?
end

#rename(new_name) ⇒ Object

Renames the node and updates the parent’s reference to it

Parameters:

  • new_name (Object) —

    Name of the node. Conventional usage is to pass a String (Integer names may cause surprises)

Returns:

  • (Object) —

    The old name



433
434
435
436
437
438
439
440
441
442
443
 
# 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

#rename_child(old_name, new_name) ⇒ Object

Renames the specified child node

Parameters:

  • old_name (Object) —

    old Name of the node. Conventional usage is to pass a String (Integer names may cause surprises)

  • new_name (Object) —

    new Name of the node. Conventional usage is to pass a String (Integer names may cause surprises)

Raises:

  • (ArgumentError) 


452
453
454
455
456
457
458
 
# 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

#replace!(old_child, new_child) ⇒ Tree::TreeNode

Replaces the specified child node with another child node on this node.

Parameters:

Returns:



466
467
468
469
470
471
472
473
 
# 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

#replace_with(node) ⇒ Tree::TreeNode

Replaces the node with another node

Parameters:

Returns:



480
481
482
 
# File 'lib/tree.rb', line 480

def replace_with(node)
  @parent.replace!(self, node)
end

#siblings {|sibling| ... } ⇒ Array<Tree::TreeNode>, Tree::TreeNode

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.

Yield Parameters:

Returns:

  • (Array<Tree::TreeNode>) —

    Array of siblings of this node. Will return an empty array for root

  • (Tree::TreeNode) —

    This node, if no block is given

See Also:



869
870
871
872
873
874
875
876
877
878
879
880
881
882
 
# 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

#to_h ⇒ Hash Originally defined in module Utils::HashConverter

Convert a node and its subtree into a Ruby hash.

Examples:

root = Tree::TreeNode.new(:root, "root content")
root << Tree::TreeNode.new(:child1, "child1 content")
root << Tree::TreeNode.new(:child2, "child2 content")
root.to_h # => {[:root, "root content"] =>
                     { [:child1, "child1 content"] =>
                                {}, [:child2, "child2 content"] => {}}}

Returns:

  • (Hash) —

    Hash representation of tree.

Author:

#to_json(*args) ⇒ Object Originally defined in module Utils::JSONConverter

Creates a JSON representation of this node including all it’s children. This requires the JSON gem to be available, or else the operation fails with a warning message. Uses the Hash output of #as_json method.

Returns:

  • The JSON representation of this subtree.

See Also:

Author:

Since:

  • 0.7.0

#to_s ⇒ String

Returns string representation of this node. This method is primarily meant for debugging purposes.

Returns:

  • (String) —

    A string representation of the node.



320
321
322
323
324
 
# 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