daily pastebin goal
17%
SHARE
TWEET

Untitled

a guest Jan 14th, 2018 51 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top