blob: 2d1e9b1b631b4ec137d5c364f2b1a0eb28b10ba4 (
plain)
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
|
# frozen_string_literal: true
module SyntaxSuggest
# Keeps track of what elements are in the queue in
# priority and also ensures that when one element
# engulfs/covers/eats another that the larger element
# evicts the smaller element
class PriorityEngulfQueue
def initialize
@queue = PriorityQueue.new
end
def to_a
@queue.to_a
end
def empty?
@queue.empty?
end
def length
@queue.length
end
def peek
@queue.peek
end
def pop
@queue.pop
end
def push(block)
prune_engulf(block)
@queue << block
flush_deleted
self
end
private def flush_deleted
while @queue&.peek&.deleted?
@queue.pop
end
end
private def prune_engulf(block)
# If we're about to pop off the same block, we can skip deleting
# things from the frontier this iteration since we'll get it
# on the next iteration
return if @queue.peek && (block <=> @queue.peek) == 1
if block.starts_at != block.ends_at # A block of size 1 cannot engulf another
@queue.to_a.each { |b|
if b.starts_at >= block.starts_at && b.ends_at <= block.ends_at
b.delete
true
end
}
end
end
end
end
|
