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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
module Concurrent
module Collection
# @!macro priority_queue
#
# @!visibility private
# @!macro internal_implementation_note
class RubyNonConcurrentPriorityQueue
# @!macro priority_queue_method_initialize
def initialize(opts = {})
order = opts.fetch(:order, :max)
@comparator = [:min, :low].include?(order) ? -1 : 1
clear
end
# @!macro priority_queue_method_clear
def clear
@queue = [nil]
@length = 0
true
end
# @!macro priority_queue_method_delete
def delete(item)
return false if empty?
original_length = @length
k = 1
while k <= @length
if @queue[k] == item
swap(k, @length)
@length -= 1
sink(k)
@queue.pop
else
k += 1
end
end
@length != original_length
end
# @!macro priority_queue_method_empty
def empty?
size == 0
end
# @!macro priority_queue_method_include
def include?(item)
@queue.include?(item)
end
alias_method :has_priority?, :include?
# @!macro priority_queue_method_length
def length
@length
end
alias_method :size, :length
# @!macro priority_queue_method_peek
def peek
empty? ? nil : @queue[1]
end
# @!macro priority_queue_method_pop
def pop
return nil if empty?
max = @queue[1]
swap(1, @length)
@length -= 1
sink(1)
@queue.pop
max
end
alias_method :deq, :pop
alias_method :shift, :pop
# @!macro priority_queue_method_push
def push(item)
raise ArgumentError.new('cannot enqueue nil') if item.nil?
@length += 1
@queue << item
swim(@length)
true
end
alias_method :<<, :push
alias_method :enq, :push
# @!macro priority_queue_method_from_list
def self.from_list(list, opts = {})
queue = new(opts)
list.each{|item| queue << item }
queue
end
private
# Exchange the values at the given indexes within the internal array.
#
# @param [Integer] x the first index to swap
# @param [Integer] y the second index to swap
#
# @!visibility private
def swap(x, y)
temp = @queue[x]
@queue[x] = @queue[y]
@queue[y] = temp
end
# Are the items at the given indexes ordered based on the priority
# order specified at construction?
#
# @param [Integer] x the first index from which to retrieve a comparable value
# @param [Integer] y the second index from which to retrieve a comparable value
#
# @return [Boolean] true if the two elements are in the correct priority order
# else false
#
# @!visibility private
def ordered?(x, y)
(@queue[x] <=> @queue[y]) == @comparator
end
# Percolate down to maintain heap invariant.
#
# @param [Integer] k the index at which to start the percolation
#
# @!visibility private
def sink(k)
while (j = (2 * k)) <= @length do
j += 1 if j < @length && ! ordered?(j, j+1)
break if ordered?(k, j)
swap(k, j)
k = j
end
end
# Percolate up to maintain heap invariant.
#
# @param [Integer] k the index at which to start the percolation
#
# @!visibility private
def swim(k)
while k > 1 && ! ordered?(k/2, k) do
swap(k, k/2)
k = k/2
end
end
end
end
end
|
