class FlatKit::InternalNode

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.

Attributes

leaf[RW]
left[RW]
next_level[RW]
right[RW]
winner[RW]

Public Class Methods

new(left:, right:) click to toggle source
# 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

Public Instance Methods

<=>(other) click to toggle source
# File lib/flat_kit/internal_node.rb, line 79
def <=>(other)
  return -1 if other.sentinel?
  value.<=>(other.value)
end
leaf?() click to toggle source
# File lib/flat_kit/internal_node.rb, line 41
def leaf?
  false
end
play() click to toggle source
# 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) click to toggle source

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.

# 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?() click to toggle source
# File lib/flat_kit/internal_node.rb, line 37
def sentinel?
  false
end
value() click to toggle source
# File lib/flat_kit/internal_node.rb, line 33
def value
  winner.value
end