gistfile1.txt

class BTree
  attr_reader :order

  class Node
    attr_reader :keys, :values, :branches

    def initialize(order, values = {})
      @order = order
      @keys = values.keys.sort
      @values = values
      @branches = []
    end

    def full?
      @keys.size == @order
    end

    def empty?
      @keys.size == 0
    end
  end

  def initialize(order)
    @order = order
    @root = Node.new(order)
  end

  def search(key)
    search_tree(@root, key).values[key]
  end

  # Returns either the node containing the key or the node
  # that should contain the node or it's direct parent.
  def search_tree(node, key)
    node.keys.each_with_index do |k, i|
      if k == key
        return node
      elsif key < k
        if node.branches[i]
          return search_tree(node.branches[i], key)
        else
          return node
        end
      end
    end

    if node.branches.last
      search_tree(node.branches.last, key)
    else
      node
    end
  end
  private :search_tree
end

class Column
  attr_reader :name, :type

  def initialize(name, type, opts)
    @name = name, @type = type, @opts = opts
  end
end

class Table
  attr_reader :name, :columns

  def initialize(name, columns)
    @name = name, @columns = columns
  end
end


# @table = Table.new(:users, [
#   Column.new(:id, :integer, :autoincrement => true, :null => false),
#   Column.new(:first_name, :string),
#   Column.new(:last_name, :string)
# ], :indexes => :wq
#                   :q
#                   :q
#                   )

bt = BTree.new(3)
r  = bt.instance_variable_get :@root

r.instance_variable_set :@keys,     [10, 20, 30]
r.instance_variable_set :@values,   {10 => "ten", 20 => "twenty", 30 => "thirty"}
r.instance_variable_set :@branches, [
  BTree::Node.new(3, 1 => "one", 2 => "two", 3 => "three"),
  BTree::Node.new(3, 11 => "eleven", 12 => "twelve", 13 => "thirteen"),
  BTree::Node.new(3, 21 => "twenty one", 22 => "twenty two", 23 => "twenty three"),
  BTree::Node.new(3, 31 => "thirty one", 32 => "thirty two", 33 => "thirty three")
]

[10,20,31,33,1,2,21,22,0,9,19,29,1000000,-1].each do |i|
puts "#{i}: #{bt.search i}"
end