diff options
Diffstat (limited to 'lib/syntax_suggest/priority_engulf_queue.rb')
-rw-r--r-- | lib/syntax_suggest/priority_engulf_queue.rb | 63 |
1 files changed, 63 insertions, 0 deletions
diff --git a/lib/syntax_suggest/priority_engulf_queue.rb b/lib/syntax_suggest/priority_engulf_queue.rb new file mode 100644 index 0000000000..2d1e9b1b63 --- /dev/null +++ b/lib/syntax_suggest/priority_engulf_queue.rb @@ -0,0 +1,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 |