Class: Philiprehberger::Tree::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/philiprehberger/tree/node.rb

Overview

A generic tree node with traversal, search, and serialization.

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(value) ⇒ Node

Create a new tree node.

Parameters:

  • value (Object) —

    the value to store



19
20
21
22
23
 
# File 'lib/philiprehberger/tree/node.rb', line 19

def initialize(value)
  @value = value
  @children = []
  @parent = nil
end

Instance Attribute Details

#children ⇒ Array<Node> (readonly)

Returns child nodes.

Returns:

  • (Array<Node>) —

    child nodes



11
12
13
 
# File 'lib/philiprehberger/tree/node.rb', line 11

def children
  @children
end

#parent ⇒ Node? (readonly)

Returns parent node (nil for root).

Returns:

  • (Node, nil) —

    parent node (nil for root)



14
15
16
 
# File 'lib/philiprehberger/tree/node.rb', line 14

def parent
  @parent
end

#value ⇒ Object (readonly)

Returns the value stored in this node.

Returns:

  • (Object) —

    the value stored in this node



8
9
10
 
# File 'lib/philiprehberger/tree/node.rb', line 8

def value
  @value
end

Class Method Details

.from_h(hash) ⇒ Node

Reconstruct a tree from a hash (inverse of #to_h).

Parameters:

  • hash (Hash) —

    hash with :value and :children keys

Returns:

  • (Node) —

    the reconstructed tree



253
254
255
256
257
258
259
260
261
 
# File 'lib/philiprehberger/tree/node.rb', line 253

def self.from_h(hash)
  node = new(hash[:value])
  (hash[:children] || []).each do |child_hash|
    child = from_h(child_hash)
    child.instance_variable_set(:@parent, node)
    node.children << child
  end
  node
end

Instance Method Details

#==(other) ⇒ Boolean

Structural equality: same value, same number of children, and children are recursively equal.

Parameters:

  • other (Node) —

    the node to compare with

Returns:

  • (Boolean) 


148
149
150
151
152
153
154
 
# File 'lib/philiprehberger/tree/node.rb', line 148

def ==(other)
  return false unless other.is_a?(Node)
  return false unless @value == other.value
  return false unless @children.size == other.children.size

  @children.zip(other.children).all? { |a, b| a == b }
end

#add_child(value) ⇒ Node

Add a child node with the given value.

Parameters:

  • value (Object) —

    value for the new child node

Returns:

  • (Node) —

    the newly created child node



29
30
31
32
33
34
 
# File 'lib/philiprehberger/tree/node.rb', line 29

def add_child(value)
  child = value.is_a?(Node) ? value : Node.new(value)
  child.instance_variable_set(:@parent, self)
  @children << child
  child
end

#ancestors ⇒ Array<Node>

Return an array of ancestor nodes from parent up to root.

Returns:

  • (Array<Node>) —

    ancestors from parent to root (empty for root)



159
160
161
162
163
164
165
166
167
 
# File 'lib/philiprehberger/tree/node.rb', line 159

def ancestors
  result = []
  node = @parent
  while node
    result << node
    node = node.parent
  end
  result
end

#depth ⇒ Integer

Return the depth of this node (distance from root).

Returns:

  • (Integer) 


66
67
68
69
70
71
72
73
74
 
# File 'lib/philiprehberger/tree/node.rb', line 66

def depth
  node = self
  d = 0
  while node.parent
    d += 1
    node = node.parent
  end
  d
end

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

Iterate breadth-first over the subtree.

Yields:

  • (Node) —

    each node in breadth-first order

Returns:

  • (Enumerator) —

    if no block given



107
108
109
110
111
112
113
114
115
116
 
# File 'lib/philiprehberger/tree/node.rb', line 107

def each_bfs(&block)
  return enum_for(:each_bfs) unless block

  queue = [self]
  until queue.empty?
    node = queue.shift
    block.call(node)
    queue.concat(node.children)
  end
end

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

Iterate depth-first (pre-order) over the subtree.

Yields:

  • (Node) —

    each node in depth-first order

Returns:

  • (Enumerator) —

    if no block given



96
97
98
99
100
101
 
# File 'lib/philiprehberger/tree/node.rb', line 96

def each_dfs(&block)
  return enum_for(:each_dfs) unless block

  block.call(self)
  @children.each { |child| child.each_dfs(&block) }
end

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

Iterate depth-first (post-order) over the subtree. Children are visited before the parent.

Yields:

  • (Node) —

    each node in depth-first post-order

Returns:

  • (Enumerator) —

    if no block given



123
124
125
126
127
128
 
# File 'lib/philiprehberger/tree/node.rb', line 123

def each_post_order(&block)
  return enum_for(:each_post_order) unless block

  @children.each { |child| child.each_post_order(&block) }
  block.call(self)
end

#each_with_depth(current_depth = 0) {|Node, Integer| ... } ⇒ Enumerator

Iterate depth-first yielding each node with its depth level.

Yields:

  • (Node, Integer) —

    each node and its depth

Returns:

  • (Enumerator) —

    if no block given



288
289
290
291
292
293
 
# File 'lib/philiprehberger/tree/node.rb', line 288

def each_with_depth(current_depth = 0, &block)
  return enum_for(:each_with_depth, current_depth) unless block

  block.call(self, current_depth)
  @children.each { |child| child.each_with_depth(current_depth + 1, &block) }
end

#find {|Node| ... } ⇒ Node?

Find the first node matching the block.

Yields:

  • (Node) —

    predicate block

Returns:

  • (Node, nil) —

    the first matching node, or nil



182
183
184
185
186
187
 
# File 'lib/philiprehberger/tree/node.rb', line 182

def find(&block)
  return nil unless block

  each_dfs { |node| return node if block.call(node) }
  nil
end

#find_by_value(value) ⇒ Node?

Find the first node whose value matches the given value (==).

Parameters:

  • value (Object) —

    value to search for

Returns:

  • (Node, nil) —

    the first matching node, or nil



193
194
195
 
# File 'lib/philiprehberger/tree/node.rb', line 193

def find_by_value(value)
  find { |n| n.value == value }
end

#flatten ⇒ Array

Return all values as a flat array in depth-first pre-order.

Returns:

  • (Array) —

    all node values



280
281
282
 
# File 'lib/philiprehberger/tree/node.rb', line 280

def flatten
  each_dfs.map(&:value)
end

#height ⇒ Integer

Return the height of the subtree rooted at this node.

Returns:

  • (Integer) 


79
80
81
82
83
 
# File 'lib/philiprehberger/tree/node.rb', line 79

def height
  return 0 if leaf?

  1 + @children.map(&:height).max
end

#include?(value) ⇒ Boolean

Check whether any node in the subtree has the given value.

Parameters:

  • value (Object) —

    value to search for

Returns:

  • (Boolean) 


201
202
203
 
# File 'lib/philiprehberger/tree/node.rb', line 201

def include?(value)
  !find_by_value(value).nil?
end

#leaf? ⇒ Boolean

Check if this node is a leaf (has no children).

Returns:

  • (Boolean) 


59
60
61
 
# File 'lib/philiprehberger/tree/node.rb', line 59

def leaf?
  @children.empty?
end

#leaves ⇒ Array<Node>

Return all leaf nodes in the subtree.

Returns:



235
236
237
 
# File 'lib/philiprehberger/tree/node.rb', line 235

def leaves
  each_dfs.select(&:leaf?)
end

#map {|Object| ... } ⇒ Node

Return a new tree with the same structure but transformed values.

Yields:

  • (Object) —

    the value of each node

Returns:

  • (Node) —

    a new tree with mapped values



267
268
269
270
271
272
273
274
275
 
# File 'lib/philiprehberger/tree/node.rb', line 267

def map(&block)
  mapped = Node.new(block.call(@value))
  @children.each do |child|
    child_mapped = child.map(&block)
    child_mapped.instance_variable_set(:@parent, mapped)
    mapped.children << child_mapped
  end
  mapped
end

#path_to(value) ⇒ Array<Node>?

Return the path from root to the first node with the given value.

Parameters:

  • value (Object) —

    value to search for

Returns:

  • (Array<Node>, nil) —

    array of nodes from root to target, or nil if not found



219
220
221
222
223
224
225
226
227
228
229
230
 
# File 'lib/philiprehberger/tree/node.rb', line 219

def path_to(value)
  target = find { |n| n.value == value }
  return nil unless target

  path = []
  node = target
  while node
    path.unshift(node)
    node = node.parent
  end
  path
end

#print_tree(indent: '', last: true) ⇒ String

Print a visual representation of the tree.

Parameters:

  • indent (String) (defaults to: '') —

    prefix for indentation (used internally)

  • last (Boolean) (defaults to: true) —

    whether this is the last sibling (used internally)

Returns:

  • (String) —

    the tree as a formatted string



300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
 
# File 'lib/philiprehberger/tree/node.rb', line 300

def print_tree(indent: '', last: true)
  lines = []
  connector = if root?
                ''
              else
                (last ? '└── ' : '├── ')
              end
  lines << "#{indent}#{connector}#{@value}"

  child_indent = indent + (if root?
                             ''
                           else
                             (last ? '    ' : '│   ')
                           end)
  @children.each_with_index do |child, i|
    lines << child.print_tree(indent: child_indent, last: i == @children.size - 1)
  end

  lines.join("\n")
end

#remove_child(value) ⇒ Node?

Remove a child node by value.

Parameters:

  • value (Object) —

    value of the child to remove

Returns:

  • (Node, nil) —

    the removed child node, or nil if not found



40
41
42
43
44
45
46
47
 
# File 'lib/philiprehberger/tree/node.rb', line 40

def remove_child(value)
  index = @children.index { |c| c.value == value }
  return nil unless index

  child = @children.delete_at(index)
  child.instance_variable_set(:@parent, nil)
  child
end

#root? ⇒ Boolean

Check if this node is the root (has no parent).

Returns:

  • (Boolean) 


52
53
54
 
# File 'lib/philiprehberger/tree/node.rb', line 52

def root?
  @parent.nil?
end

#select {|Node| ... } ⇒ Array<Node>

Return all nodes in the subtree matching the predicate block.

Yields:

  • (Node) —

    predicate block

Returns:

  • (Array<Node>) —

    all matching nodes (empty if none or no block)



209
210
211
212
213
 
# File 'lib/philiprehberger/tree/node.rb', line 209

def select(&block)
  return [] unless block

  each_dfs.select(&block)
end

#siblings ⇒ Array<Node>

Return sibling nodes (children of the same parent, excluding self).

Returns:

  • (Array<Node>) —

    sibling nodes (empty for root)



172
173
174
175
176
 
# File 'lib/philiprehberger/tree/node.rb', line 172

def siblings
  return [] unless @parent

  @parent.children.reject { |c| c.equal?(self) }
end

#size ⇒ Integer

Return the total number of nodes in the subtree rooted at this node.

Returns:

  • (Integer) 


88
89
90
 
# File 'lib/philiprehberger/tree/node.rb', line 88

def size
  1 + @children.sum(&:size)
end

#subtree ⇒ Node

Return a deep copy of this node and all descendants, detached from parent.

Returns:

  • (Node) —

    a new tree rooted at a copy of this node



133
134
135
136
137
138
139
140
141
 
# File 'lib/philiprehberger/tree/node.rb', line 133

def subtree
  copy = Node.new(@value)
  @children.each do |child|
    child_copy = child.subtree
    child_copy.instance_variable_set(:@parent, copy)
    copy.children << child_copy
  end
  copy
end

#to_h ⇒ Hash

Serialize the subtree to a hash.

Returns:

  • (Hash) —

    hash with :value and :children keys



242
243
244
245
246
247
 
# File 'lib/philiprehberger/tree/node.rb', line 242

def to_h
  {
    value: @value,
    children: @children.map(&:to_h)
  }
end