class Rooted::Node

Nodes are mutable by default, since creating anyting but simple leafs would otherwise be imposible. Calling freeze on a node makes the entire subtree immutable. This is used by the Tree class which only operates on frozen node structures.

The following is an example of a rooted tree with maximum depth 2.

    r         - r, a, b, c, and d are internal vertices
 +--+---+     - vertices e, f, g, h, i, and j are leaves
 a  b   c     - vertices g, h, and i are siblings
+++ | +-+-+   - node a is an ancestor of j
d e f g h i   - j is a descendant of a
|
j

The terminology is mostly referenced from www.cs.columbia.edu/~cs4203/files/GT-Lec4.pdf.

Public Class Methods

[](value = nil) click to toggle source

Creates a new node with the given object as its value, unless a Node is passed, in which case it will be returned.

@param value [Object] the object to be used as value for a new Node, or a

Node object.

@return [Node] a Node object.

# File lib/rooted/node.rb, line 34
def self.[](value = nil)
  return value if value.is_a? self
  new value
end

Public Instance Methods

+(other) click to toggle source

Add two roots together to create a larger tree. A new common root will be created and returned. Note that if the any of the root nodes are not frozen they will be modified, and as a result seize to be roots.

@param other [Node] a Node-like object that responds true to root? @return [Node] a new root with the two nodes as children.

# File lib/rooted/node.rb, line 215
def +(other)
  unless root? && other.root?
    raise StructureException, 'Only roots can be added'
  end

  a = frozen? ? dup : self
  b = other.frozen? ? other.dup : other

  ab = self.class.new
  ab << a << b
end
==(other) click to toggle source

Compare one node (sub)structure with another.

@param other [Object] @return [true] if the two vertecies form identical subtrees. @reutrn [false] otherwise.

# File lib/rooted/node.rb, line 232
def ==(other)
  return false unless other.is_a? self.class
  return false unless degree == other.degree
  return false unless value == other.value

  children.to_a == other.children.to_a
end
[](index = nil)
Alias for: child
ancestors() { |node| ... } click to toggle source

Iterates over the nodes above this in the tree hierarchy and yields them to a block. If no block is given an enumerator is returned.

@yield [Node] each parent node. @return [Enumerator] if no block is given.

# File lib/rooted/node.rb, line 109
def ancestors
  return to_enum(__callee__) unless block_given?
  node = self
  loop do
    node = node.parent
    yield node
  end
end
child(index = nil) click to toggle source

Accessor method for any of the n children under this node. If called without an argument and the node has anything but exactly one child an exception will be raised.

@param index [Integer] the n:th child to be returned. If the index is

negative the indexing will be reversed and the children counted from the
last to the first.

@return [Node] the child at the n:th index.

# File lib/rooted/node.rb, line 139
def child(index = nil)
  unless index
    raise ArgumentError, 'No index for node with degree != 1' if degree != 1
    return first
  end

  rtl, index = wrap_index index

  raise RangeError, 'Child index out of range' if index >= degree

  children(rtl: rtl).each do |c|
    break c if index.zero?
    index -= 1
  end
end
Also aliased as: []
children(rtl: false, &block) click to toggle source

Yields each of the node children. The default order is left-to-right, but by passing rtl: true the order is reversed. If a block is not given an enumerator is returned.

Note that the block will catch any StopIteration that is raised and terminate early, returning the value of the exception.

@param rtl [true, false] reverses the iteration order if true. @return see each_item

# File lib/rooted/node.rb, line 127
def children(rtl: false, &block)
  rtl ? reverse_each_item(&block) : each_item(&block)
end
each() { |self| ... } click to toggle source

@yield [Node] first self is yielded and then the children who in turn

yield their children.

@return [Enumerator] if no block is given.

# File lib/rooted/node.rb, line 160
def each(&block)
  return to_enum(__callee__) unless block_given?
  yield self
  children { |v| v.each(&block) }
end
edges() { |self, v| ... } click to toggle source

Iterates over each edge in the tree.

@yield [Array<Node>] each connected node pair. @return [Enumerator] if no block is given.

# File lib/rooted/node.rb, line 200
def edges(&block)
  return to_enum(__callee__) unless block_given?

  children do |v|
    yield self, v
    v.edges(&block)
  end
end
leafs(rtl: false) { |self| ... } click to toggle source

Iterates over each of the leafs.

@param rtl [true, false] if true the iteration order is switched to right

to left.
# File lib/rooted/node.rb, line 190
def leafs(rtl: false, &block)
  return to_enum(__callee__, rtl: rtl) unless block_given?
  return yield self if leaf?
  children(rtl: rtl) { |v| v.leafs(rtl: rtl, &block) }
end
max_degree() click to toggle source

@return [Integer] the highest child count of the nodes in the subtree.

# File lib/rooted/node.rb, line 82
def max_degree
  children.map(&:degree).push(degree).max
end
max_depth(offset = depth) click to toggle source

@return [Integer] the maximum node depth under this node.

# File lib/rooted/node.rb, line 75
def max_depth(offset = depth)
  return offset if leaf?

  children.map { |c| c.max_depth offset + 1 }.max
end
parent() click to toggle source

Access the parent node. Raises a StopIteration if this node is the root.

@raise [StopIteration] if this node is the root.

@return [Node] the parent node.

# File lib/rooted/node.rb, line 99
def parent
  raise StopIteration if root?
  list
end
root() click to toggle source

@return [Node] the root of the tree structure that the node is part of.

# File lib/rooted/node.rb, line 64
def root
  return self if root?
  loop.reduce(self) { |node,| node.parent }
end
size() click to toggle source

Calculate the size in vertecies of the subtree.

@return [Integer] the number of nodes under this node, including self.

# File lib/rooted/node.rb, line 89
def size
  children.reduce(1) { |a, e| a + e.size }
end
to_a(flatten: false) click to toggle source

Converts the tree structure to a nested array of the nodes. Each internal node is placed at index zero of its own array, followed by an array of its children. Leaf nodes are not wraped in arrays but inserted directly.

Example

  r
 / \
a   b  => [r, [[a, [c]], b]]
|
c

@param flatten [true, false] the array is flattened if true. @return [Array<Node, Array>] a nested array of nodes.

# File lib/rooted/node.rb, line 180
def to_a(flatten: false)
  return each.to_a if flatten
  return self if leaf?
  [self, children.map(&:to_a)]
end

Private Instance Methods

wrap_index(index) click to toggle source
# File lib/rooted/node.rb, line 242
def wrap_index(index)
  if index.negative?
    [true, -1 - index]
  else
    [false, index]
  end
end