Class: Tree::TreeNode

Inherits:
Object
  • Object
show all
Includes:
Comparable, Enumerable, Utils::CamelCaseMethodHandler, Utils::JSONConverter, Utils::TreeMergeHandler, Utils::TreeMetricsHandler
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

Author:

Direct Known Subclasses

BinaryTreeNode

Core Attributes (collapse)

Attributes included from Utils::TreeMetricsHandler

#breadth, #depth, #in_degree, #length, #level, #node_depth, #node_height, #out_degree, #size

Node Creation (collapse)

Structure Modification (collapse)

Tree Traversal (collapse)

Navigating the Child Nodes (collapse)

Navigating the Sibling Nodes (collapse)

Instance Method Summary (collapse)

Methods included from Utils::TreeMergeHandler

#merge, #merge!

Methods included from Utils::JSONConverter

#as_json, included, #to_json

Methods included from Utils::CamelCaseMethodHandler

included

Methods included from Utils::TreeMetricsHandler

included

Constructor Details

- (TreeNode) initialize(name, content = nil)

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.

Raises:

  • (ArgumentError)

    Raised if the node name is empty.

See Also:



209
210
211
212
213
214
215
216
217
218
219
220
221
# File 'lib/tree.rb', line 209

def initialize(name, content = nil)
  raise ArgumentError, "Node name HAS to be provided!" if name == nil
  @name, @content = name, content

  if name.kind_of?(Integer)
    warn StandardWarning,
         "Using integer as node name. Semantics of TreeNode[] may not be what you expect! #{name} #{content}"
  end

  self.set_as_root!
  @children_hash = Hash.new
  @children = []
end

Dynamic Method Handling

This class handles dynamic methods through the method_missing method in the class Tree::Utils::CamelCaseMethodHandler

Instance Attribute Details

- (Object) content

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

See Also:

  • name


115
116
117
# File 'lib/tree.rb', line 115

def content
  @content
end

- (Boolean) has_children? (readonly)

true if the this node has any child node.

See Also:



186
187
188
# File 'lib/tree.rb', line 186

def has_children?
  @children.length != 0
end

- (Boolean) has_content? (readonly)

true if this node has content.



145
146
147
# File 'lib/tree.rb', line 145

def has_content?
  @content != nil
end

- (Boolean) is_leaf? (readonly)

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

See Also:



156
157
158
# File 'lib/tree.rb', line 156

def is_leaf?
  !has_children?
end

- (Boolean) is_root? (readonly)

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



137
138
139
# File 'lib/tree.rb', line 137

def is_root?
  @parent == nil
end

- (Object) name (readonly)

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.

See Also:

  • content


108
109
110
# File 'lib/tree.rb', line 108

def name
  @name
end

- (Object) parent

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



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

def parent
  @parent
end

- (Array<Tree::TreeNode>?) parentage (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.



168
169
170
171
172
173
174
175
176
177
178
# File 'lib/tree.rb', line 168

def parentage
  return nil if is_root?

  parentage_array = []
  prev_parent = self.parent
  while (prev_parent)
    parentage_array << prev_parent
    prev_parent = prev_parent.parent
  end
  parentage_array
end

- (Tree::TreeNode) root (readonly)

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



126
127
128
129
130
# File 'lib/tree.rb', line 126

def root
  root = self
  root = root.parent while !root.is_root?
  root
end

Instance Method Details

- (Tree::TreeNode) <<(child)

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

See Also:



320
321
322
# File 'lib/tree.rb', line 320

def <<(child)
  add(child)
end

- (Integer) <=>(other)

Provides a comparision operation for the nodes.

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



800
801
802
803
# File 'lib/tree.rb', line 800

def <=>(other)
  return +1 if other == nil
  self.name <=> other.name
end

- (Tree::TreeNode) [](name_or_index, num_as_name = false)

Note:

The use of Integer names is allowed by using the optional num_as_name flag.

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). However, if the second optional num_as_name argument is true, then the name is used literally as a name, and NOT as an index

  • If the name argument is NOT an Integer, then it is taken to be the name of the child node to be returned.

If a non-Integer name is passed, and the num_as_name parameter is also true, then a warning is thrown (as this is a redundant use of the num_as_name flag.)

Raises:

  • (ArgumentError)

    Raised if the name_or_index argument is nil.

See Also:



497
498
499
500
501
502
503
504
505
506
507
508
# File 'lib/tree.rb', line 497

def [](name_or_index, num_as_name=false)
  raise ArgumentError, "Name_or_index needs to be provided!" if name_or_index == nil

  if name_or_index.kind_of?(Integer) and not num_as_name
    @children[name_or_index]
  else
    if num_as_name and not name_or_index.kind_of?(Integer)
      warn StandardWarning, "Redundant use of the `num_as_name` flag for non-integer node name"
    end
    @children_hash[name_or_index]
  end
end

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

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-existant position is used.

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:



355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
# File 'lib/tree.rb', line 355

def add(child, at_index = -1)
  raise ArgumentError, "Attempting to add a nil node" unless child # Only handles the immediate child scenario
  raise ArgumentError, "Attempting add node to itself" if self.equal?(child)
  raise ArgumentError, "Attempting add root as a child" if self.equal?(root) unless self.is_root?

  # Lazy mans 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)

  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
  return child
end

- (Tree::TreeNode, Enumerator) breadth_each {|node| ... }

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.

Yield Parameters:

See Also:



598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
# File 'lib/tree.rb', line 598

def breadth_each(&block)
  return self.to_enum 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

  return self if block_given?
end

- (Tree::TreeNode+) children {|child| ... }

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:



624
625
626
627
628
629
630
631
# File 'lib/tree.rb', line 624

def children
  if block_given?
    @children.each {|child| yield child}
    return self
  else
    return @children.clone
  end
end

- (Tree::TreeNode) detached_copy

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



227
228
229
# File 'lib/tree.rb', line 227

def detached_copy
  Tree::TreeNode.new(@name, @content ? @content.clone : nil)
end

- (Tree::TreeNode) detached_subtree_copy Also known as: dup

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

Author:

  • Vincenzo Farruggia

Since:

  • 0.8.0



237
238
239
240
241
# File 'lib/tree.rb', line 237

def detached_subtree_copy
  new_node = detached_copy
  children { |child| new_node << child.detached_subtree_copy }
  new_node
end

- (Tree::TreeNode, Enumerator) each {|node| ... }

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.

Yield Parameters:

See Also:



522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
# File 'lib/tree.rb', line 522

def each(&block)             # :yields: node

 return self.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
    if current                    # The node 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.clone.concat(node_stack)
    end
  end

  return self if block_given?
end

- (Tree::TreeNode+) each_leaf {|node| ... }

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.

Yield Parameters:

See Also:



645
646
647
648
649
650
651
652
# File 'lib/tree.rb', line 645

def each_leaf &block
  if block_given?
    self.each { |node| yield(node) if node.is_leaf? }
    return self
  else
    self.select { |node| node.is_leaf?}
  end
end

- (Tree::TreeNode) first_child

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



662
663
664
# File 'lib/tree.rb', line 662

def first_child
  children.first
end

- (Tree::TreeNode) first_sibling

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



686
687
688
# File 'lib/tree.rb', line 686

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

- (Object) freeze_tree!

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.



457
458
459
# File 'lib/tree.rb', line 457

def freeze_tree!
  each {|node| node.freeze}
end

- (Boolean) is_first_sibling?

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



696
697
698
# File 'lib/tree.rb', line 696

def is_first_sibling?
  first_sibling == self
end

- (Boolean) is_last_sibling?

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



720
721
722
# File 'lib/tree.rb', line 720

def is_last_sibling?
  last_sibling == self
end

- (Boolean) 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.

See Also:



755
756
757
# File 'lib/tree.rb', line 755

def is_only_child?
  is_root? ? true : parent.children.size == 1
end

- (Tree::TreeNode) last_child

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



670
671
672
# File 'lib/tree.rb', line 670

def last_child
  children.last
end

- (Tree::TreeNode) last_sibling

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



710
711
712
# File 'lib/tree.rb', line 710

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

- (Object) marshal_dump

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



251
252
253
# File 'lib/tree.rb', line 251

def marshal_dump
  self.collect { |node| node.create_dump_rep }
end

- (Object) marshal_load(dumped_tree_array)

TODO:

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

Loads a marshalled dump of a tree and returns the root node of the reconstructed tree. See the Marshal class for additional details.



272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
# File 'lib/tree.rb', line 272

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 then
      nodes[name] = current_node = Tree::TreeNode.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

- (Tree::treeNode) next_sibling

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.



768
769
770
771
772
773
# File 'lib/tree.rb', line 768

def next_sibling
  return nil if is_root?

  myidx = parent.children.index(self)
  parent.children.at(myidx + 1) if myidx
end

- (Tree::TreeNode, Enumerator) postordered_each {|node| ... }

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

Yield Parameters:

See Also:



562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
# File 'lib/tree.rb', line 562

def postordered_each(&block)
  return self.to_enum 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.
  markednode = Struct.new(:node, :visited)
  node_stack = [markednode.new(self, false)] # Start with self

  until node_stack.empty?
    peek_node = node_stack[0]
    if peek_node.node.has_children? and not 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| markednode.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

  return self if block_given?
end

- (Tree::TreeNode, Enumerator) preordered_each {|node| ... }

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

Yield Parameters:

See Also:



550
551
552
# File 'lib/tree.rb', line 550

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

- (Tree::treeNode) previous_sibling

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.



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

def previous_sibling
  return nil if is_root?

  myidx = parent.children.index(self)
  parent.children.at(myidx - 1) if myidx && myidx > 0
end

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



809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
# File 'lib/tree.rb', line 809

def print_tree(level = 0, block = lambda { |node, prefix|  puts "#{prefix} #{node.name}" })
  prefix = ''
  if is_root?
    prefix << '*'
  else
    prefix << '|' unless parent.is_last_sibling?
    prefix << (' ' * (level - 1) * 4)
    prefix << (is_last_sibling? ? '+' : '|')
    prefix << '---'
    prefix << (has_children? ? '+' : '>')
  end

  block.call(self, prefix)

  children { |child| child.print_tree(level + 1, block) if child } # Child might be 'nil'
end

- (Tree::TreeNode) remove!(child)

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.



397
398
399
400
401
402
403
404
# File 'lib/tree.rb', line 397

def remove!(child)
  return nil unless child

  @children_hash.delete(child.name)
  @children.delete(child)
  child.set_as_root!
  child
end

- (Tree::TreeNode) remove_all!

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.



436
437
438
439
440
441
442
# File 'lib/tree.rb', line 436

def remove_all!
  @children.each { |child| child.set_as_root! }

  @children_hash.clear
  @children.clear
  self
end

- (Tree:TreeNode) remove_from_parent!

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

If this is the root node, then does nothing.

See Also:



425
426
427
# File 'lib/tree.rb', line 425

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

- (Array<Tree::TreeNode>, Tree::TreeNode) siblings {|sibling| ... }

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:

See Also:



736
737
738
739
740
741
742
743
744
745
746
# File 'lib/tree.rb', line 736

def siblings
  if block_given?
    parent.children.each { |sibling| yield sibling if sibling != self }
    return self
  else
    return [] if is_root?
    siblings = []
    parent.children {|my_sibling| siblings << my_sibling if my_sibling != self}
    siblings
  end
end

- (String) to_s

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



297
298
299
300
301
302
303
# File 'lib/tree.rb', line 297

def to_s
  "Node Name: #{@name}" +
    " Content: " + (@content.to_s || "<Empty>") +
    " Parent: " + (is_root?()  ? "<None>" : @parent.name.to_s) +
    " Children: #{@children.length}" +
    " Total Nodes: #{size()}"
end