forked from abscondment/rubyvor
-
Notifications
You must be signed in to change notification settings - Fork 0
/
test_priority_queue.rb
129 lines (105 loc) · 2.61 KB
/
test_priority_queue.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
require 'rubygems'
require 'minitest/unit'
require File.dirname(__FILE__) + '/../lib/ruby_vor'
class TestPriorityQueue < MiniTest::Unit::TestCase
def test_heap_order_property
# min heap by default
q = RubyVor::PriorityQueue.new
items = [1,2,3,4,5,6,99,4,-20,101,5412,2,-1,-1,-1,33.0,0,55,7,12321,123.123,-123.123,0,0,0]
items.each{|i| q.push(i)}
items.sort!
idx = 0
# Test peek
assert_equal q.peek.data, items[0]
while min = q.pop
# Test pop
assert_equal min.data, items[idx]
# Test peek
assert_equal q.peek.data, items[idx + 1] if idx + 1 < items.length
idx += 1
end
end
def test_heapify
q = RubyVor::PriorityQueue.new
# Create a randomized data set.
#
# Not ideal for unit tests, since they *should* be done
# on static data so that failure/success is deterministic...
# but works for me.
100.times{ q.push(rand * 10000.0 - 5000.0)}
# Set things right.
q.heapify()
old_n = -1.0 * Float::MAX
while n = q.pop
assert n.priority >= old_n, 'Heap-order property violated'
old_n = n.priority
end
end
def test_bad_data
q = RubyVor::PriorityQueue.new
10.times { q.push(rand * 100.0 - 50.0) }
#
# Heapify
#
old_data = q.data[1]
q.data[1] = 45
assert_raises TypeError do
q.heapify()
end
q.data[1] = old_data
assert_nothing_raised do
q.heapify()
end
#
# Percolation
#
[100, -100].each do |i|
assert_raises IndexError do
q.percolate_up(i)
end
assert_raises IndexError do
q.percolate_down(i)
end
end
[:x, Class, nil, false].each do |i|
assert_raises TypeError do
q.percolate_up(i)
end
assert_raises TypeError do
q.percolate_down(i)
end
end
[0,1,2,3].each do |i|
assert_nothing_raised do
q.percolate_up(i)
end
assert_nothing_raised do
q.percolate_down(i)
end
end
end
def test_build_queue
n = 100
q = RubyVor::PriorityQueue.build_queue(n) do |queue_item|
queue_item.priority = rand * 10000.0 - 5000.0
end
assert_equal n, q.data.length
assert_equal n, q.size
old_n = -1.0 * Float::MAX
while n = q.pop
assert n.priority >= old_n, 'Heap-order property violated'
old_n = n.priority
end
end
private
def assert_nothing_raised(&b)
begin
yield
rescue Exception => e
flunk "#{mu_pp(e)} exception encountered, expected no exceptions"
return
end
pass()
end
end
MiniTest::Unit.autorun