class Tree::TreeNode

TreeNode Class Description

The node class for the tree representation. the nodes are named and have a place-holder for the node data (i.e., the `content’ of the node). The node names are expected to be unique. In addition, the node provides navigation methods to traverse the tree.

The nodes can have any number of child nodes attached to it. Note that while this implementation does not support directed graphs, the class itself makes no restrictions on associating a node’s CONTENT with multiple parent nodes.

Example

The following code-snippet implements this tree structure:

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

require ‘tree’

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

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

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

myTreeRoot.printTree

child1 = myTreeRoot

grandChild1 = myTreeRoot[“GRANDCHILD1”]

siblingsOfChild1Array = child1.siblings

immediateChildrenArray = myTreeRoot.children

# Process all nodes

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

myTreeRoot.remove!(child1) # Remove the child

Attributes

content[RW]
name[R]
parent[R]

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, and is defaulted to nil.

# File lib/tree.rb, line 118
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 a convenient method to add children hierarchies in the tree.

E.g. root << child << grand_child

# File lib/tree.rb, line 167
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 for the node names.

# File lib/tree.rb, line 417
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 parameter is numeric, then the in-sequence array of children is accessed (see Tree#children). If the parameter is not numeric, then it is assumed to be the name of the child node to be returned.

# File lib/tree.rb, line 301
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. The child node’s parent is set to be the receiver. The child is added as the last child in the current list of children for the receiver node.

# File lib/tree.rb, line 174
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 this node level. A single node has a breadth of 1.

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

Performs breadth first traversal of the tree rooted at this node. The traversal in a given level is from left to right.

# File lib/tree.rb, line 277
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. If a block is given, yields each child node to the block.

# File lib/tree.rb, line 241
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 this node. A single leaf node has a depth of 1.

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

Returns a copy of this node, with the parent and children links removed.

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

Returns every node (including the receiver node) from the tree to the specified block. The traversal is depth first and from left to right in pre-ordered sequence.

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

Yields all leaf nodes from this node to the specified block. May yield this node as well if this is a leaf node. Leaf traversal depth first and left to right.

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

Returns the first child of this node. Will return nil if no children are present.

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

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

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

Freezes all nodes in the tree

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

Indicates whether this node has any immediate child nodes.

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

Indicates whether this node has any associated content.

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

Returns true if this node is the first sibling.

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

Returns true if his node is the last sibling

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

Indicates whether this node is a ‘leaf’ - i.e., one without any children

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

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

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

Indicates whether this node is a root node. Note that orphaned children will also be reported as root nodes.

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

Returns the last child of this node. Will return nil if no children are present.

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

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

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

Convenience synonym for Tree#size

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

Creates the marshal-dump represention of the tree rooted at this node.

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

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

# File lib/tree.rb, line 439
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 this node. Will return nil if no subsequent node is present.

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

Returns an array of ancestors in reversed order (the first element is the immediate parent). Returns nil if this is a root node.

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

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

  parentageArray
end
preordered_each(&block) click to toggle source

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

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

Returns the previous sibling for this node. Will return nil if no subsequent node is present.

# File lib/tree.rb, line 408
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 323
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. The removed children nodes are orphaned but available if an alternate reference exists.

Returns the child node.

# File lib/tree.rb, line 189
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.

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

Removes this node from its parent. If this is the root node, then does nothing.

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

Returns the root for this tree. Root’s root is itself.

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

Returns an array of siblings for this node. 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 380
def siblings
  return nil if isRoot?
  if block_given?
    for sibling in parent.children
      yield sibling if sibling != self
    end
  else
    siblings = []
    parent.children {|sibling| siblings << sibling if sibling != self}
    siblings
  end
end
size() click to toggle source

Returns the total number of nodes in this tree, rooted at the receiver node.

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

Print the string representation of this node.

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

Protected Instance Methods

createDumpRep() click to toggle source

Creates a dump representation and returns the same as a hash.

# File lib/tree.rb, line 433
def createDumpRep
  { :name => @name, :parent => (isRoot? ? nil : @parent.name),  :content => Marshal.dump(@content)}
end
parent=(parent) click to toggle source

Protected method to set the parent node. This method should NOT be invoked by client code.

# File lib/tree.rb, line 159
def parent=(parent)
  @parent = parent
end
setAsRoot!() click to toggle source

Protected method which sets this node as a root node.

# File lib/tree.rb, line 218
def setAsRoot!
  @parent = nil
end