require 'test_helper'

class SelfBalancingBinaryTreeTest < ActiveSupport::TestCase
  test "insert" do
    n = SelfBalancingBinary::Tree.new
    assert_equal [], n.to_a
    n << 5
    assert_equal [5], n.to_a
    n << 5
    assert_equal [5,5], n.to_a
    n << 4
    assert_equal [4,5,5], n.to_a
    n << [ 4,5 ]
    assert_equal [4,4,5,5,5], n.to_a
    n = SelfBalancingBinary::Tree.new
    n << [ 6,5,4,3,2,1 ]
    assert_equal [1,2,3,4,5,6], n.to_a
    assert_nil n.find(8)
    assert_equal 5, n.find(5)
    assert_equal 1, n.find(1)
    assert_equal 6, n.find(6)
  end

  test "insert multiple types" do
    n = SelfBalancingBinary::Tree.new
    n << "hello"
    n << 5
  end

  test "insert a hash collision" do
    class HashCollidingString < String
      def hash
        1
      end
    end
    n = SelfBalancingBinary::Tree.new

    hello  = HashCollidingString.new('hello')
    hello2 = HashCollidingString.new('hello2')

    n << [ hello, hello2 ]
    assert_equal hello, n.find(hello)
    assert_equal hello2, n.find(hello2)
  end

  test 'self balance' do
    n = 100
    sample_size = 10
    1.upto(sample_size) do
      t = SelfBalancingBinary::Tree.new
      t << 1.upto(n).to_a.shuffle
      assert_operator t.root.depth, :<=, 2*(Math.log(n) / Math.log(2))
    end
    t = SelfBalancingBinary::Tree.new
    t << 1.upto(n).to_a
    assert_operator t.root.depth, :<=, 2*(Math.log(n) / Math.log(2))
    t = SelfBalancingBinary::Tree.new
    t << 1.upto(n).map{|i|n+1-i}
    assert_operator t.root.depth, :<=, 2*(Math.log(n) / Math.log(2))
  end
end