class Tree::TreeNode

TreeNode Class Description

This class models the nodes for an N-ary tree data structue. 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 within the tree.

The node content is not required to be unique across different nodes in the tree, and can be nil as well.

The class provides various traversal methods to navigate the tree, methods to modify contents of the node or to change position of the node in the tree and methods to change structure of 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 and 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.

Example

The following example implements this tree structure:

                  +------------+
                  |    ROOT    |
                  +-----+------+
          +-------------+------------+
          |                          |
  +-------+-------+          +-------+-------+
  |  CHILD 1      |          |  CHILD 2      |
  +-------+-------+          +---------------+
          |
          |
  +-------+-------+
  | GRANDCHILD 1  |
  +---------------+

require 'tree'

root_node = ::new(“ROOT”, “Root Content”)

root_node << ::new(“CHILD1”, “Child1 Content”) << ::new(“GRANDCHILD1”, “GrandChild1 Content”)

root_node << ::new(“CHILD2”, “Child2 Content”)

root_node.printTree

child1 = root_node

grand_child1 = root_node[“GRANDCHILD1”]

siblings_of_child1 = child1.siblings

children_of_root = root_node.children

# Process all nodes

root_node.each { |node| node.content.reverse }

root_node.remove!(child1) # Remove the child

Attributes

content[RW]

Content of this node. Can be nil.

name[R]

Name of this node. Expected to be unique within the tree.

parent[R]

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

Public Class Methods

new(name, content = nil) click to toggle source

Constructor which expects the name of the node. Name of the node is expected to be unique across the tree.

The content can be of any type, defaults to nil.

# File lib/tree.rb, line 136
def initialize(name, content = nil)
  raise "Node name HAS to be provided" if name == nil
  @name = name
  @content = content
  self.setAsRoot!

  @childrenHash = Hash.new
  @children = []
end

Public Instance Methods

<<(child) click to toggle source

Convenience synonym for #add method.

This method allows an easy method to add node hierarchies to the tree on a given path via chaining the method calls to successive child nodes.

Example: root << child << grand_child

Returns the added child node.

# File lib/tree.rb, line 194
def <<(child)
  add(child)
end
<=>(other) click to toggle source

Provides a comparision operation for the nodes.

Comparision is based on the natural character-set ordering of the *node name*.

# File lib/tree.rb, line 494
def <=>(other)
  return +1 if other == nil
  self.name <=> other.name
end
[](name_or_index) click to toggle source

Returns the requested node from the set of immediate children.

If the argument is numeric, then the in-sequence array of children is accessed (see Tree#children). If the argument is NOT numeric, then it is assumed to be name of the child node to be returned.

Raises an exception is the requested child node is not found.

# File lib/tree.rb, line 354
def [](name_or_index)
  raise "Name_or_index needs to be provided" if name_or_index == nil

  if name_or_index.kind_of?(Integer)
    @children[name_or_index]
  else
    @childrenHash[name_or_index]
  end
end
add(child) click to toggle source

Adds the specified child node to the receiver node.

This method can also be used for grafting a subtree into the receiver node's tree, if the specified child node is the root of a subtree (i.e., has child nodes under it).

The receiver 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 the receiver node.

Returns the added child node.

An exception is raised if another child node with the same name exists.

# File lib/tree.rb, line 210
def add(child)
  raise "Child already added" if @childrenHash.has_key?(child.name)

  @childrenHash[child.name]  = child
  @children << child
  child.parent = self
  return child
end
breadth() click to toggle source

Returns breadth of the tree at the receiver 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.

# File lib/tree.rb, line 589
def breadth
  isRoot? ? 1 : parent.children.size
end
breadth_each() { |node_to_traverse| ... } click to toggle source

Performs breadth first traversal of the tree starting at the receiver node. The traversal at a given level is from left to right.

# File lib/tree.rb, line 327
def breadth_each &block
  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
end
children() { |child| ... } click to toggle source

Returns an array of all the immediate children of the receiver node.

If a block is given, yields each child node to the block traversing from left to right.

# File lib/tree.rb, line 288
def children
  if block_given?
    @children.each {|child| yield child}
  else
    @children
  end
end
depth() click to toggle source

Returns depth of the tree from the receiver node. A single leaf node has a depth of 1.

This method is DEPRECATED and may be removed in the subsequent releases. Note that the value returned by this method is actually the:

height + 1 of the node, NOT the depth.

For correct and conventional behavior, please use #nodeDepth and #nodeHeight methods instead.

# File lib/tree.rb, line 571
def depth
  begin
    require 'structured_warnings'   # To enable a nice way of deprecating of the depth method.
    warn DeprecatedMethodWarning, 'This method is deprecated.  Please use nodeDepth() or nodeHeight() instead (bug # 22535)'
  rescue LoadError
    # Oh well. Will use the standard Kernel#warn.  Behavior will be identical.
    warn 'Tree::TreeNode#depth() method is deprecated.  Please use nodeDepth() or nodeHeight() instead (bug # 22535)'
  end

  return 1 if isLeaf?
  1 + @children.collect { |child| child.depth }.max
end
detached_copy() click to toggle source

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

# File lib/tree.rb, line 148
def detached_copy
  Tree::TreeNode.new(@name, @content ? @content.clone : nil)
end
each() { |node| ... } click to toggle source

Traverses every node (including the receiver node) from the (sub)tree by yielding the node to the specified block.

The traversal is depth-first and from left to right in pre-ordered sequence.

# File lib/tree.rb, line 314
def each &block             # :yields: node
  yield self
  children { |child| child.each(&block) }
end
each_leaf() { |node| ... } click to toggle source

Yields all leaf nodes from the receiver 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.

# File lib/tree.rb, line 343
def each_leaf &block
  self.each { |node| yield(node) if node.isLeaf? }
end
firstChild() click to toggle source

Returns the first child of the receiver node.

Will return nil if no children are present.

# File lib/tree.rb, line 299
def firstChild
  children.first
end
firstSibling() click to toggle source

Returns the first sibling for the receiver node. If this is the root node, returns itself.

'First' sibling is defined as follows:

First sibling

The left-most child of the receiver's parent, which may be the receiver itself

# File lib/tree.rb, line 417
def firstSibling
  isRoot? ? self : parent.children.first
end
freezeTree!() click to toggle source

Freezes all nodes in the (sub)tree rooted at the receiver node.

# File lib/tree.rb, line 500
def freezeTree!
  each {|node| node.freeze}
end
hasChildren?() click to toggle source

Returns true if the receiver node has any immediate child nodes.

# File lib/tree.rb, line 275
def hasChildren?
  @children.length != 0
end
hasContent?() click to toggle source

Returns true if the receiver node has any associated content.

# File lib/tree.rb, line 257
def hasContent?
  @content != nil
end
isFirstSibling?() click to toggle source

Returns true if the receiver node is the first sibling.

# File lib/tree.rb, line 422
def isFirstSibling?
  firstSibling == self
end
isLastSibling?() click to toggle source

Returns true if the receivere node is the last sibling.

# File lib/tree.rb, line 440
def isLastSibling?
  lastSibling == self
end
isLeaf?() click to toggle source

Returns true if the receiver node is a 'leaf' - i.e., one without any children.

# File lib/tree.rb, line 281
def isLeaf?
  !hasChildren?
end
isOnlyChild?() click to toggle source

Returns true if the receiver node is the only child of its parent.

# File lib/tree.rb, line 467
def isOnlyChild?
  parent.children.size == 1
end
isRoot?() click to toggle source

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

# File lib/tree.rb, line 270
def isRoot?
  @parent == nil
end
lastChild() click to toggle source

Returns the last child of the receiver node.

Will return nil if no children are present.

# File lib/tree.rb, line 306
def lastChild
  children.last
end
lastSibling() click to toggle source

Returns the last sibling for the receiver node. If this is the root node, returns itself.

'Last' sibling is defined as follows:

Last sibling

The right-most child of the receiver's parent, which may be the receiver itself

# File lib/tree.rb, line 435
def lastSibling
  isRoot? ? self : parent.children.last
end
length() click to toggle source

Convenience synonym for Tree#size

# File lib/tree.rb, line 374
def length
  size()
end
marshal_dump() click to toggle source

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

# File lib/tree.rb, line 505
def marshal_dump
  self.collect { |node| node.createDumpRep }
end
marshal_load(dumped_tree_array) click to toggle source

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

# File lib/tree.rb, line 521
def marshal_load(dumped_tree_array)
  nodes = { }
  for node_hash in dumped_tree_array do
    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
nextSibling() click to toggle source

Returns the next sibling for the receiver node. The 'next' node is defined as the node to right of the receiver node.

Will return nil if no subsequent node is present.

# File lib/tree.rb, line 475
def nextSibling
  if myidx = parent.children.index(self)
    parent.children.at(myidx + 1)
  end
end
nodeDepth() click to toggle source

Returns depth of the receiver 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.

Note that the deprecated method #depth was incorrectly computing this value. Please replace all calls to the old method with #nodeDepth instead.

# File lib/tree.rb, line 557
def nodeDepth
  return 0 if isRoot?
  1 + parent.nodeDepth
end
nodeHeight() click to toggle source

Returns height of the (sub)tree from the receiver 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.

# File lib/tree.rb, line 546
def nodeHeight
  return 0 if isLeaf?
  1 + @children.collect { |child| child.nodeHeight }.max
end
parentage() click to toggle source

Returns an array of ancestors of the receiver node in reversed order (the first element is the immediate parent of the receiver).

Returns nil if the receiver is a root node.

# File lib/tree.rb, line 165
def parentage
  return nil if isRoot?

  parentageArray = []
  prevParent = self.parent
  while (prevParent)
    parentageArray << prevParent
    prevParent = prevParent.parent
  end

  parentageArray
end
preordered_each() { |node| ... } click to toggle source

Traverses the tree in a pre-ordered sequence. This is equivalent to #each

# File lib/tree.rb, line 321
def preordered_each &block  # :yields: node
  each(&block)
end
previousSibling() click to toggle source

Returns the previous sibling for the receiver node. The 'previous' node is defined as the node to left of the receiver node.

Will return nil if no predecessor node is present.

# File lib/tree.rb, line 485
def previousSibling
  if myidx = parent.children.index(self)
    parent.children.at(myidx - 1) if myidx > 0
  end
end
printTree(level = 0) click to toggle source

Pretty prints the tree starting with the receiver node.

# File lib/tree.rb, line 379
def printTree(level = 0)

  if isRoot?
    print "*"
  else
    print "|" unless parent.isLastSibling?
    print(' ' * (level - 1) * 4)
    print(isLastSibling? ? "+" : "|")
    print "---"
    print(hasChildren? ? "+" : ">")
  end

  puts " #{name}"

  children { |child| child.printTree(level + 1)}
end
remove!(child) click to toggle source

Removes the specified child node from the receiver node.

This method can also be used for pruning a subtree, in cases where the removed child node is the root of the subtree to be pruned.

The removed child node is orphaned but accessible if an alternate reference exists. If accesible via an alternate reference, the removed child will report itself as a root node for its subtree.

Returns the child node.

# File lib/tree.rb, line 228
def remove!(child)
  @childrenHash.delete(child.name)
  @children.delete(child)
  child.setAsRoot! unless child == nil
  return child
end
removeAll!() click to toggle source

Removes all children from the receiver node.

Returns the receiver node.

# File lib/tree.rb, line 247
def removeAll!
  for child in @children
    child.setAsRoot!
  end
  @childrenHash.clear
  @children.clear
  self
end
removeFromParent!() click to toggle source

Removes the receiver node from its parent. The reciever node becomes the new root for its subtree.

If this is the root node, then does nothing.

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

# File lib/tree.rb, line 240
def removeFromParent!
  @parent.remove!(self) unless isRoot?
end
root() click to toggle source

Returns root node for the (sub)tree to which the receiver node belongs.

Note that a root node's root is itself (beware of any loop construct that may become infinite!)

# File lib/tree.rb, line 402
def root
  root = self
  root = root.parent while !root.isRoot?
  root
end
siblings() { |sibling| ... } click to toggle source

Returns an array of siblings for the receiver node. The receiver node is excluded.

If a block is provided, yields each of the sibling nodes to the block. The root always has nil siblings.

# File lib/tree.rb, line 452
def siblings
  return nil if isRoot?

  if block_given?
    for sibling in parent.children
      yield sibling if sibling != self
    end
  else
    siblings = []
    parent.children {|my_sibling| siblings << my_sibling if my_sibling != self}
    siblings
  end
end
size() click to toggle source

Returns the total number of nodes in this (sub)tree, including the receiver node.

Size of the tree is defined as:

Size

Total number nodes in the subtree including the receiver node.

# File lib/tree.rb, line 369
def size
  @children.inject(1) {|sum, node| sum + node.size}
end
to_s() click to toggle source

Print the string representation of this node. This is primary for debugging purposes.

# File lib/tree.rb, line 153
def to_s
  "Node Name: #{@name}" +
    " Content: " + (@content || "<Empty>") +
    " Parent: " + (isRoot?()  ? "<None>" : @parent.name) +
    " Children: #{@children.length}" +
    " Total Nodes: #{size()}"
end