spec/runtime/interval_skip_list/interval_skip_list_spec.rb

   1 #require File.expand_path("#{File.dirname(__FILE__)}/spec_helper")
   2 #
   3 #MAX_INTERVAL = 100000
   4 #
   5 #describe IntervalSkipList do
   6 #  describe "#next_node_height" do
   7 #    attr_reader :list
   8 #
   9 #    before do
  10 #      @list = IntervalSkipList.new
  11 #    end
  12 #
  13 #    it "returns a number between 1 and the max_height of the list" do
  14 #      height = list.next_node_height
  15 #      height.should be <= list.max_height
  16 #      height.should be > 0
  17 #    end
  18 #  end
  19 #
  20 #  describe "a list with 1000 random intervals" do
  21 #    attr_reader :list, :inserted_ranges
  22 #
  23 #    before do
  24 #      @list = IntervalSkipList.new
  25 #      @inserted_ranges = []
  26 #
  27 #      0.upto(10) do |i|
  28 #        first, last = [rand(MAX_INTERVAL), rand(MAX_INTERVAL)].sort
  29 #        range = first..last
  30 #        list.insert(range, i)
  31 #        inserted_ranges.push(range)
  32 #      end
  33 #    end
  34 #
  35 #    it "functions correctly for stabbing queries" do
  36 #      10000.times do
  37 #        n = rand(MAX_INTERVAL)
  38 #        ranges = list.containing(n).sort
  39 #
  40 #        expected_ranges = []
  41 #        inserted_ranges.each_with_index do |range,i|
  42 #          expected_ranges.push(i) if n > range.first && n < range.last
  43 #        end
  44 #        expected_ranges.sort!
  45 #        unless ranges == expected_ranges
  46 #          puts "N = #{n}"
  47 #          puts "Expected: " + expected_ranges.inspect
  48 #          puts "Actual:   " + ranges.inspect
  49 #          expected_ranges.size.should be <= ranges.size
  50 #          puts "Missing containers: #{(expected_ranges.map {|o| o.object_id} - ranges.map {|o| o.object_id}).inspect}"
  51 #          puts "Unexpected containers: #{(ranges.map {|o| o.object_id} - expected_ranges.map {|o| o.object_id}).inspect}"
  52 #          puts "Inserted Ranges: #{inserted_ranges.inspect}"
  53 #          puts "Expected Ranges: #{expected_ranges.map {|i| inserted_ranges[i]}.inspect}"
  54 #        end
  55 #      end
  56 #    end
  57 #  end
  58 #end