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.



22
23
24
25
26
27
28
29
30
31
 
# File 'lib/flat_kit/internal_node.rb', line 22

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



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

def leaf
  @leaf
end

#left ⇒ Object

Internal Node



16
17
18
 
# File 'lib/flat_kit/internal_node.rb', line 16

def left
  @left
end

#next_level ⇒ Object

Who to tell



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

def next_level
  @next_level
end

#right ⇒ Object

Internal Node



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

def right
  @right
end

#winner ⇒ Object

Internal Node



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

def winner
  @winner
end

Instance Method Details

#<=>(other) ⇒ Object 



79
80
81
82
 
# File 'lib/flat_kit/internal_node.rb', line 79

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

#leaf? ⇒ Boolean

Returns:

  • (Boolean) 


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

def leaf?
  false
end

#play ⇒ Object 



71
72
73
74
75
76
77
 
# File 'lib/flat_kit/internal_node.rb', line 71

def play
  @winner = left <= right ? left : right
  if !@winner.sentinel? then
    @leaf = winner.leaf
  end
  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.



55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/flat_kit/internal_node.rb', line 55

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

  if @right.sentinel? && @left.sentinel? then
    next_level.player_finished(self) if next_level
  end
end

#sentinel? ⇒ Boolean

Returns:

  • (Boolean) 


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

def sentinel?
  false
end

#value ⇒ Object 



33
34
35
 
# File 'lib/flat_kit/internal_node.rb', line 33

def value
  winner.value
end