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
|
require File.dirname(__FILE__) + "/../../test_helper"
class PriorityQueueTest < Test::Unit::TestCase
include Ferret::Utils
PQ_STRESS_SIZE = 1000
def test_pq()
pq = PriorityQueue.new(4)
assert_equal(0, pq.size)
assert_equal(4, pq.capacity)
pq.insert("bword")
assert_equal(1, pq.size)
assert_equal("bword", pq.top)
pq.insert("cword")
assert_equal(2, pq.size)
assert_equal("bword", pq.top)
pq << "dword"
assert_equal(3, pq.size)
assert_equal("bword", pq.top)
pq << "eword"
assert_equal(4, pq.size)
assert_equal("bword", pq.top)
pq << "aword"
assert_equal(4, pq.size)
assert_equal("bword", pq.top, "aword < all other elements so ignore")
pq << "fword"
assert_equal(4, pq.size)
assert_equal("cword", pq.top, "bword got pushed off the bottom of the queue")
assert_equal("cword", pq.pop())
assert_equal(3, pq.size)
assert_equal("dword", pq.pop())
assert_equal(2, pq.size)
assert_equal("eword", pq.pop())
assert_equal(1, pq.size)
assert_equal("fword", pq.pop())
assert_equal(0, pq.size)
assert_nil(pq.top)
assert_nil(pq.pop)
end
def test_pq_clear()
pq = PriorityQueue.new(3)
pq << "word1"
pq << "word2"
pq << "word3"
assert_equal(3, pq.size)
pq.clear()
assert_equal(0, pq.size)
assert_nil(pq.top)
assert_nil(pq.pop)
end
#define PQ_STRESS_SIZE 1000
def test_stress_pq
pq = PriorityQueue.new(PQ_STRESS_SIZE)
PQ_STRESS_SIZE.times do
pq.insert("<#{rand(PQ_STRESS_SIZE)}>")
end
prev = pq.pop()
(PQ_STRESS_SIZE - 1).times do
curr = pq.pop()
assert(prev <= curr, "#{prev} should be less than #{curr}")
prev = curr
end
pq.clear()
end
def test_pq_block
pq = PriorityQueue.new(21) {|a, b| a > b}
100.times do
pq.insert("<#{rand(50)}>")
end
prev = pq.pop()
20.times do
curr = pq.pop()
assert(prev >= curr, "#{prev} should be greater than #{curr}")
prev = curr
end
assert_equal 0, pq.size
end
def test_pq_proc
pq = PriorityQueue.new({:less_than => lambda {|a, b| a.size > b.size}, :capacity => 21})
100.times do
pq.insert("x" * rand(50))
end
prev = pq.pop()
20.times do
curr = pq.pop()
assert(prev.size >= curr.size, "#{prev} should be greater than #{curr}")
prev = curr
end
assert_equal 0, pq.size
end
end
|
