Module: PriorityQueueTest

Extended by:
PriorityQueueTest
Included in:
CPriorityQueueTest, PoorPriorityQueueTest, PriorityQueueTest, RubyPriorityQueueTest
Defined in:
lib/priority-queue/test/priority_queue_test.rb

Instance Method Summary collapse

Instance Method Details

#teardown ⇒ Object

Check that the order is maintained



21
22
23
24
25
26
27
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 21

def teardown
  last = @q.min_priority
  while priority = @q.delete_min_return_priority
    assert_operator(last, :<=, priority)
    last = priority
  end
end

#test_access ⇒ Object 



168
169
170
171
172
173
174
175
176
177
178
179
180
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 168

def test_access
  assert_equal(0, @q["node1"] = 0)
  assert_equal(["node1", 0], @q.min)
  assert_equal(1, @q["node2"] = 1)
  assert_equal(1, @q["node2"])
  assert_equal("node1", @q.min_key)
  assert_equal(2, @q["node3"] = 2)
  assert_equal(2, @q["node3"])
  assert_equal("node1", @q.min_key)
  assert_equal(-1, @q["node3"] = -1)
  assert_equal(-1, @q["node3"])
  assert_equal("node3", @q.min_key)
end

#test_decrease_priority ⇒ Object 



190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 190

def test_decrease_priority

  20.times do | i |
    @q.push i, i / 20.0
  end

  assert_equal([0, 0], @q.delete_min)

  @q[10] = -1
  @q[11] = -0.5

  [10, 11, (1..9).to_a, (12..19).to_a, nil].flatten.each do | shall |
    key, priority = *@q.delete_min
    assert_equal(shall, key)
  end
end

#test_delete ⇒ Object 



218
219
220
221
222
223
224
225
226
227
228
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 218

def test_delete
  @q[1] = 1
  @q[2] = 2
  @q[3] = 3
  assert_equal(1, @q[1])
  assert_equal([1,1], @q.min)
  assert_equal([1,1], @q.delete(1))
  assert_equal(nil, @q[1])
  assert_equal([2,2], @q.min)
  assert_equal(nil, @q.delete(1))
end

#test_delete_min ⇒ Object

Assure that delete min works



57
58
59
60
61
62
63
64
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 57

def test_delete_min
  assert_equal(nil, @q.delete_min, "Empty queue should pop nil")
  @q["n1"] = 0
  assert_equal(["n1", 0], @q.delete_min)
  @q["n1"] = 0
  @q["n2"] = -1
  assert_equal(["n2", -1], @q.delete_min)
end

#test_delete_min_return_key ⇒ Object 



66
67
68
69
70
71
72
73
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 66

def test_delete_min_return_key
  assert_equal(nil, @q.delete_min_return_key, "Empty queue should pop nil")
  @q["n1"] = 0
  assert_equal("n1", @q.delete_min_return_key)
  @q["n1"] = 0
  @q["n2"] = -1
  assert_equal("n2", @q.delete_min_return_key)
end

#test_delete_min_return_priority ⇒ Object 



75
76
77
78
79
80
81
82
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 75

def test_delete_min_return_priority
  assert_equal(nil, @q.delete_min_return_priority, "Empty queue should pop nil")
  @q["n1"] = 0
  assert_equal(0, @q.delete_min_return_priority)
  @q["n1"] = 0
  @q["n2"] = -1
  assert_equal(-1, @q.delete_min_return_priority)
end

#test_dup ⇒ Object 



246
247
248
249
250
251
252
253
254
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 246

def test_dup
  ('a'..'z').each do | n |
    @q[n] = n[0]
  end
  qq = @q.dup
  until @q.empty?
    assert_equal(@q.delete_min, qq.delete_min)
  end
end

#test_each ⇒ Object 



256
257
258
259
260
261
262
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 256

def test_each
  ('a'..'z').each do | n |
    @q[n] = n[0]
  end
  queue = ('a'..'z').inject([]) { | r, n | r << [n, n[0]] }
  assert_equal(queue.sort, @q.to_a.sort)
end

#test_empty? ⇒ Boolean

Returns:

  • (Boolean) 


90
91
92
93
94
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 90

def test_empty?
  assert_equal(true, @q.empty?, "Empty queue should return true on empty?")
  @q["node1"] = 10
  assert_equal(false, @q.empty?, "Filled queue should return false on empty?")
end

#test_example_1 ⇒ Object 



230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 230

def test_example_1
  assert_equal(0, @q["node1"] = 0)
  assert_equal(1, @q["node2"] = 1)
  assert_equal("node1", @q.min_key)
  assert_equal(0, @q[@q.min_key])
  assert_equal(0, @q.min_priority)

  @q["node2"] = -1
  assert_equal(["node2", -1], @q.delete_min)
  assert_equal(nil, @q["node2"])
  @q["node3"] = 1

  assert_equal(["node3", 1], @q.delete("node3"))
  assert_equal(nil, @q.delete("node2"))
end

#test_has_key? ⇒ Boolean

Returns:

  • (Boolean) 


84
85
86
87
88
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 84

def test_has_key?
  assert(!@q.has_key?(1))
  @q[1] = 1
  assert(@q.has_key?(1))
end

#test_increase_priority ⇒ Object 



207
208
209
210
211
212
213
214
215
216
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 207

def test_increase_priority
  20.times do | i |
    @q[i] = i
  end
  @q[10] = 5
  assert_equal([0,0], @q.delete_min)
  assert_equal(10, @q[10] = 10)
  assert_equal(20, @q[11] = 20)
  assert_equal([1,1], @q.delete_min)
end

#test_length ⇒ Object 



29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 29

def test_length
  20.times do | i |
    assert_equal(i, @q.length)
    @q[i] = i
  end
  10.times do | i |
    assert_equal(20-i, @q.length)
    @q.delete_min
  end
  10.times do | i |
    assert_equal(10+i, @q.length)
    @q[i] = i
  end
  @q.delete(5)
  assert_equal(19, @q.length)
end

#test_merge ⇒ Object 



46
47
48
49
50
51
52
53
54
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 46

def test_merge
  @q1 = @q.class.new
  @q2 = @q.class.new

  20.times do | i |
    @q1[i] = i
    @q2[i+20] = i+20
  end
end

#test_min ⇒ Object 



182
183
184
185
186
187
188
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 182

def test_min
  assert_equal(nil, @q.min)
  @q["node1"] = 10
  assert_equal(["node1", 10], @q.min)
  @q["node2"] = 5
  assert_equal(["node2", 5], @q.min)
end

#test_min_key ⇒ Object 



148
149
150
151
152
153
154
155
156
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 148

def test_min_key
  assert_equal(nil, @q.min_key)
  @q["node1"] = 0
  assert_equal("node1", @q.min_key)
  @q["node2"] = 1
  assert_equal("node1", @q.min_key)
  @q["node3"] = -1
  assert_equal("node3", @q.min_key)
end

#test_min_priority ⇒ Object 



158
159
160
161
162
163
164
165
166
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 158

def test_min_priority
  assert_equal(nil, @q.min_priority)
  @q["node1"] = 0
  assert_equal(0, @q.min_priority)
  @q["node2"] = 1
  assert_equal(0, @q.min_priority)
  @q["node3"] = -1
  assert_equal(-1, @q.min_priority)
end

#test_push ⇒ Object 



96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 96

def test_push
  20.times do | i |
    @q.push i, i+10
  end

  20.times do | i |
    @q.push i, i
  end
  
  20.times do | i |
    assert_equal([i, i], @q.delete_min)
  end

  assert_equal(nil, @q.delete_min)
end

#test_push_decrease_pop ⇒ Object 



124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 124

def test_push_decrease_pop
  50.times do | i |
    @q.push i, i
  end

  10.times do | i |
    assert_equal([i, i], @q.delete_min)
  end

  10.times do | i |
    @q[i+10] = i
  end

  10.times do | i |
    assert_equal([i+10, i], @q.delete_min)
  end

  30.times do | i |
    assert_equal([i+20, i+20], @q.delete_min)
  end

  assert_equal(nil, @q.delete_min)
end

#test_push_pop ⇒ Object 



112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/priority-queue/test/priority_queue_test.rb', line 112

def test_push_pop
  20.times do | i |
    @q.push i, i
  end

  20.times do | i |
    assert_equal([i, i], @q.delete_min)
  end

  assert_equal(nil, @q.delete_min)
end