lib/syntax_suggest/priority_engulf_queue.rb

   1 # frozen_string_literal: true
   2
   3 module SyntaxSuggest
   4   # Keeps track of what elements are in the queue in
   5   # priority and also ensures that when one element
   6   # engulfs/covers/eats another that the larger element
   7   # evicts the smaller element
   8   class PriorityEngulfQueue
   9     def initialize
  10       @queue = PriorityQueue.new
  11     end
  12
  13     def to_a
  14       @queue.to_a
  15     end
  16
  17     def empty?
  18       @queue.empty?
  19     end
  20
  21     def length
  22       @queue.length
  23     end
  24
  25     def peek
  26       @queue.peek
  27     end
  28
  29     def pop
  30       @queue.pop
  31     end
  32
  33     def push(block)
  34       prune_engulf(block)
  35       @queue << block
  36       flush_deleted
  37
  38       self
  39     end
  40
  41     private def flush_deleted
  42       while @queue&.peek&.deleted?
  43         @queue.pop
  44       end
  45     end
  46
  47     private def prune_engulf(block)
  48       # If we're about to pop off the same block, we can skip deleting
  49       # things from the frontier this iteration since we'll get it
  50       # on the next iteration
  51       return if @queue.peek && (block <=> @queue.peek) == 1
  52
  53       if block.starts_at != block.ends_at # A block of size 1 cannot engulf another
  54         @queue.to_a.each { |b|
  55           if b.starts_at >= block.starts_at && b.ends_at <= block.ends_at
  56             b.delete
  57             true
  58           end
  59         }
  60       end
  61     end
  62   end
  63 end