Programmatic Double-Elimination Bracket Generation

tree_solver.rb

# This takes a bracket size and generates the loser's bracket side of a double-elimination tournament
class TreeSolver
  attr_reader :size
  def initialize options = {}
    @size = options[:size] || 32
    @levels = 0
    calculate_levels
    @starting_point = options[:starting_point] || 2
  end

  def calculate_levels
    counter = @size + 0
    while counter != 2
      @levels += 2
      counter /= 2
    end
  end

  def nodes_for_level level
    offset = level + (level.odd? ? 1 : 0 )
    nodes_this_level = (2 ** (offset / 2))
  end

  def generate_node_for data, &block
    if data[:level] <= @levels
      if data[:level] == @levels
        left_position = data[:position] - 1
        right_position = data[:position] + 1

        block.call left_position, right_position, {}
      elsif data[:level].odd?
        left_position = data[:position] - 1
        right_position = remaining_nodes_below(data[:level]) + data[:position]
        
        block.call left_position, right_position

        generate_node_for({ position: right_position, parent_position: data[:position], level: data[:level] + 1 }, &block)
      else
        left_position = data[:parent_position] + 2
        right_position = data[:position] + 2

        block.call left_position, right_position

        generate_node_for({ position: left_position, parent_position: data[:position], level: data[:level] + 1 }, &block)
        generate_node_for({ position: right_position, parent_position: data[:position], level: data[:level] + 1 }, &block)
      end
    end
  end

  def remaining_nodes_below level
    (level..@levels).inject(0) { |sum, l| sum += nodes_for_level(l); sum } / nodes_for_level(level)
  end

  def solve
    bracket = BracketTree.new
    bracket.add({ position: @starting_point })

    generate_node_for(position: @starting_point, level: 1) do |left, right|
      bracket.add({ position: left })
      bracket.add({ position: right })
    end

    return bracket
  end
end