Class: FlatKit::InternalNode

Inherits:
Object
  • Object
show all
Includes:
Comparable
Defined in:
lib/flat_kit/internal_node.rb

Overview

Private: This is a class used internally by MergeTree and should not be used outside of that context.

The InternalNode represents a single element of the tournament tree altorithm holding references to the to other internal nodes that competed in this node and which one is the winner.

A reference to the leaf node that is associated with the winner is also kept here.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(left:, right:) ⇒ InternalNode

Returns a new instance of InternalNode.



26
27
28
29
30
31
32
33
34
35
 
# File 'lib/flat_kit/internal_node.rb', line 26

def initialize(left:, right:)
  @left = left
  @left.next_level = self

  @right = right
  @right.next_level = self
  @next_level = nil

  play
end

Instance Attribute Details

#leaf ⇒ Object

winning leaf node



24
25
26
 
# File 'lib/flat_kit/internal_node.rb', line 24

def leaf
  @leaf
end

#left ⇒ Object

Internal Nodes



18
19
20
 
# File 'lib/flat_kit/internal_node.rb', line 18

def left
  @left
end

#next_level ⇒ Object

Who to tell



21
22
23
 
# File 'lib/flat_kit/internal_node.rb', line 21

def next_level
  @next_level
end

#right ⇒ Object

Internal Nodes



18
19
20
 
# File 'lib/flat_kit/internal_node.rb', line 18

def right
  @right
end

#winner ⇒ Object

Internal Nodes



18
19
20
 
# File 'lib/flat_kit/internal_node.rb', line 18

def winner
  @winner
end

Instance Method Details

#<=>(other) ⇒ Object 



81
82
83
84
85
 
# File 'lib/flat_kit/internal_node.rb', line 81

def <=>(other)
  return -1 if other.sentinel?

  value <=> (other.value)
end

#leaf? ⇒ Boolean

Returns:

  • (Boolean) 


45
46
47
 
# File 'lib/flat_kit/internal_node.rb', line 45

def leaf?
  false
end

#play ⇒ Object 



75
76
77
78
79
 
# File 'lib/flat_kit/internal_node.rb', line 75

def play
  @winner = (left <= right) ? left : right
  @leaf = winner.leaf unless @winner.sentinel?
  next_level.play if next_level
end

#player_finished(node) ⇒ Object

We are being told that the passed in node no longer has data in it and is to be removed from the tree.

We replace our reference to this node with a sentinal node so that comparisons work correctly.

After updating the node, we then need to check and see if both of our child nodes are sentinels, and if so, then tell our parent to remove us from the tree.



59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/flat_kit/internal_node.rb', line 59

def player_finished(node)
  if left.equal?(node)
    @left = SentinelInternalNode.new
    @left.next_level = self
  elsif right.equal?(node)
    @right = SentinelInternalNode.new
    @right.next_level = self
  else
    raise FlatKit::Error, "Unknown player #{node}"
  end

  return unless @right.sentinel? && @left.sentinel?

  next_level.player_finished(self) if next_level
end

#sentinel? ⇒ Boolean

Returns:

  • (Boolean) 


41
42
43
 
# File 'lib/flat_kit/internal_node.rb', line 41

def sentinel?
  false
end

#value ⇒ Object 



37
38
39
 
# File 'lib/flat_kit/internal_node.rb', line 37

def value
  winner.value
end