-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathpriority_queue.rb
More file actions
152 lines (120 loc) · 2.22 KB
/
priority_queue.rb
File metadata and controls
152 lines (120 loc) · 2.22 KB
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
151
152
class PriorityQueue
def initialize(max_size = Float::INFINITY, &metric)
@heap = Heap.new(&metric)
@max_size = max_size
end
def enqueue(item)
if full?
if belongs?(item)
@heap.replace(item)
end
else
@heap.insert(item)
end
end
def peek_all
@heap.peek_all
end
private
def full?
@heap.size == @max_size
end
def belongs?(item)
@heap > item
end
end
class Heap
def initialize(&metric)
@metric = metric
@ary = []
end
def insert(item)
@ary << item
@sift_up ||= Sift::Up.new(self)
@sift_up.perform
end
def replace(item)
@ary[0] = item
@sift_down ||= Sift::Down.new(self)
@sift_down.perform
end
def size
@ary.size
end
def >(item)
@metric.(peek) > @metric.(item)
end
def peek_all
@ary
end
private
def peek
peek_all[head_i]
end
def head_i
0
end
def tail_i
size - 1
end
class Sift
class << self
def delegate(*exprs)
exprs.each do |expr|
raise "invalid method name" if /[$"A-Z]/ =~ expr
meth = /^@?(.*)$/.match(expr).captures.first
define_method(meth) { @heap.instance_eval(expr.to_s) }
end
end
end
delegate :@ary, :@metric, :head_i, :tail_i
def initialize(heap)
@heap = heap
end
def perform
current_i = start_i
loop do
next_i = get_next_i(current_i)
break if current_i == next_i
swap(current_i, next_i)
current_i = next_i
end
end
private
def swap(i, j)
ary[i], ary[j] = ary[j], ary[i]
end
def get_next_i(current_i)
next_is = get_next_is(current_i)
next_is << current_i
next_is.max_by do |i|
if in_bounds?(i)
self.class::SIGN * metric.(ary[i])
else
-Float::INFINITY
end
end
end
def in_bounds?(i)
head_i <= i && i <= tail_i
end
class Up < self
SIGN = -1
def get_next_is(i)
[(i - 1) / 2]
end
def start_i
tail_i
end
end
class Down < self
SIGN = 1
def get_next_is(i)
[2 * i + 1, 2 * i + 2]
end
def start_i
head_i
end
end
end
end