Class: Rooted::Node

Inherits:
Linked::Item
  • Object
show all
Extended by:
Forwardable
Includes:
Linked::List
Defined in:
lib/rooted/node.rb

Overview

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.

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.[](value = nil) ⇒ Node

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

Parameters:

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

    the object to be used as value for a new Node, or a Node object.

Returns:

  • (Node) —

    a Node object.



34
35
36
37
 
# File 'lib/rooted/node.rb', line 34

def self.[](value = nil)
  return value if value.is_a? self
  new value
end

Instance Method Details

#+(other) ⇒ Node

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.

Parameters:

  • other (Node) —

    a Node-like object that responds true to #root?

Returns:

  • (Node) —

    a new root with the two nodes as children.



215
216
217
218
219
220
221
222
223
224
225
 
# 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) ⇒ true

Compare one node (sub)structure with another.

Parameters:

  • other (Object)

Returns:

  • (true) —

    if the two vertecies form identical subtrees.



232
233
234
235
236
237
238
 
# 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

#ancestors {|Node| ... } ⇒ Enumerator

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.

Yields:

  • (Node) —

    each parent node.

Returns:

  • (Enumerator) —

    if no block is given.



70
 
# File 'lib/rooted/node.rb', line 70

def_delegator :ancestors, :count, :depth

#child(index = nil) ⇒ Node Also known as: []

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.

Parameters:

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

    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.

Returns:

  • (Node) —

    the child at the n:th index.

Raises:

  • (RangeError) 


139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
# 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

#children(rtl: false, &block) ⇒ Object

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.

Parameters:

  • rtl (true, false) (defaults to: false) —

    reverses the iteration order if true.

Returns:

  • see #each_item



127
128
129
 
# File 'lib/rooted/node.rb', line 127

def children(rtl: false, &block)
  rtl ? reverse_each_item(&block) : each_item(&block)
end

#each {|Node| ... } ⇒ Enumerator

Returns if no block is given.

Yields:

  • (Node) —

    first self is yielded and then the children who in turn yield their children.

Returns:

  • (Enumerator) —

    if no block is given.



160
161
162
163
164
 
# 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 {|Array<Node>| ... } ⇒ Enumerator

Iterates over each edge in the tree.

Yields:

  • (Array<Node>) —

    each connected node pair.

Returns:

  • (Enumerator) —

    if no block is given.



200
201
202
203
204
205
206
207
 
# 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, &block) ⇒ Object

Iterates over each of the leafs.

Parameters:

  • rtl (true, false) (defaults to: false) —

    if true the iteration order is switched to right to left.



190
191
192
193
194
 
# 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 ⇒ Integer

Returns the highest child count of the nodes in the subtree.

Returns:

  • (Integer) —

    the highest child count of the nodes in the subtree.



82
83
84
 
# File 'lib/rooted/node.rb', line 82

def max_degree
  children.map(&:degree).push(degree).max
end

#max_depth(offset = depth) ⇒ Integer

Returns the maximum node depth under this node.

Returns:

  • (Integer) —

    the maximum node depth under this node.



75
76
77
78
79
 
# 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 ⇒ Node

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

Returns:

  • (Node) —

    the parent node.

Raises:

  • (StopIteration) —

    if this node is the root.



99
100
101
102
 
# File 'lib/rooted/node.rb', line 99

def parent
  raise StopIteration if root?
  list
end

#root ⇒ Node

Returns the root of the tree structure that the node is part of.

Returns:

  • (Node) —

    the root of the tree structure that the node is part of.



64
65
66
67
 
# File 'lib/rooted/node.rb', line 64

def root
  return self if root?
  loop.reduce(self) { |node,| node.parent }
end

#size ⇒ Integer

Calculate the size in vertecies of the subtree.

Returns:

  • (Integer) —

    the number of nodes under this node, including self.



89
90
91
 
# File 'lib/rooted/node.rb', line 89

def size
  children.reduce(1) { |a, e| a + e.size }
end

#to_a(flatten: false) ⇒ Array<Node, Array>

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

Parameters:

  • flatten (true, false) (defaults to: false) —

    the array is flattened if true.

Returns:

  • (Array<Node, Array>) —

    a nested array of nodes.



180
181
182
183
184
 
# 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