daily pastebin goal
14%
SHARE
TWEET

Untitled

a guest Jan 14th, 2018 49 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. require 'test_helper'
  2.  
  3. class SelfBalancingBinaryTreeTest < ActiveSupport::TestCase
  4.   test "insert" do
  5.     n = SelfBalancingBinary::Tree.new
  6.     assert_equal [], n.to_a
  7.     n << 5
  8.     assert_equal [5], n.to_a
  9.     n << 5
  10.     assert_equal [5,5], n.to_a
  11.     n << 4
  12.     assert_equal [4,5,5], n.to_a
  13.     n << [ 4,5 ]
  14.     assert_equal [4,4,5,5,5], n.to_a
  15.     n = SelfBalancingBinary::Tree.new
  16.     n << [ 6,5,4,3,2,1 ]
  17.     assert_equal [1,2,3,4,5,6], n.to_a
  18.     assert_nil n.find(8)
  19.     assert_equal 5, n.find(5)
  20.     assert_equal 1, n.find(1)
  21.     assert_equal 6, n.find(6)
  22.   end
  23.  
  24.   test "insert multiple types" do
  25.     n = SelfBalancingBinary::Tree.new
  26.     n << "hello"
  27.     n << 5
  28.   end
  29.  
  30.   test "insert a hash collision" do
  31.     class HashCollidingString < String
  32.       def hash
  33.         1
  34.       end
  35.     end
  36.     n = SelfBalancingBinary::Tree.new
  37.  
  38.     hello  = HashCollidingString.new('hello')
  39.     hello2 = HashCollidingString.new('hello2')
  40.  
  41.     n << [ hello, hello2 ]
  42.     assert_equal hello, n.find(hello)
  43.     assert_equal hello2, n.find(hello2)
  44.   end
  45.  
  46.   test 'self balance' do
  47.     n = 100
  48.     sample_size = 10
  49.     1.upto(sample_size) do
  50.       t = SelfBalancingBinary::Tree.new
  51.       t << 1.upto(n).to_a.shuffle
  52.       assert_operator t.root.depth, :<=, 2*(Math.log(n) / Math.log(2))
  53.     end
  54.     t = SelfBalancingBinary::Tree.new
  55.     t << 1.upto(n).to_a
  56.     assert_operator t.root.depth, :<=, 2*(Math.log(n) / Math.log(2))
  57.     t = SelfBalancingBinary::Tree.new
  58.     t << 1.upto(n).map{|i|n+1-i}
  59.     assert_operator t.root.depth, :<=, 2*(Math.log(n) / Math.log(2))
  60.   end
  61. end
RAW Paste Data
Top