Class: Rooted::Node
- Inherits:
-
Linked::Item
- Object
- Linked::Item
- Rooted::Node
- 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
-
.[](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.
Instance Method Summary collapse
-
#+(other) ⇒ Node
Add two roots together to create a larger tree.
-
#==(other) ⇒ true
Compare one node (sub)structure with another.
-
#ancestors {|Node| ... } ⇒ Enumerator
Iterates over the nodes above this in the tree hierarchy and yields them to a block.
-
#child(index = nil) ⇒ Node
(also: #[])
Accessor method for any of the n children under this node.
-
#children(rtl: false, &block) ⇒ Object
Yields each of the node children.
-
#each {|Node| ... } ⇒ Enumerator
If no block is given.
-
#edges {|Array<Node>| ... } ⇒ Enumerator
Iterates over each edge in the tree.
-
#leafs(rtl: false, &block) ⇒ Object
Iterates over each of the leafs.
-
#max_degree ⇒ Integer
The highest child count of the nodes in the subtree.
-
#max_depth(offset = depth) ⇒ Integer
The maximum node depth under this node.
-
#parent ⇒ Node
Access the parent node.
-
#root ⇒ Node
The root of the tree structure that the node is part of.
-
#size ⇒ Integer
Calculate the size in vertecies of the subtree.
-
#to_a(flatten: false) ⇒ Array<Node, Array>
Converts the tree structure to a nested array of the nodes.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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
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 |