class Concurrent::Collection::RubyNonConcurrentPriorityQueue

def self.from_list(list, opts = {})
  queue = new(opts)
  list.each{|item| queue << item }
  queue
end

def clear
  @queue = [nil]
  @length = 0
  true
end

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) || swim(k)
      @queue.pop
    else
      k += 1
    end
  end
  @length != original_length
end

def empty?
  size == 0
end

def include?(item)
  @queue.include?(item)
end

def initialize(opts = {})
  order = opts.fetch(:order, :max)
  @comparator = [:min, :low].include?(order) ? -1 : 1
  clear
end

def length
  @length
end

def ordered?(x, y)
  (@queue[x] <=> @queue[y]) == @comparator
end

def peek
  empty? ? nil : @queue[1]
end

def pop
  return nil if empty?
  max = @queue[1]
  swap(1, @length)
  @length -= 1
  sink(1)
  @queue.pop
  max
end

def push(item)
  raise ArgumentError.new('cannot enqueue nil') if item.nil?
  @length += 1
  @queue << item
  swim(@length)
  true
end

def sink(k)
  success = false
  while (j = (2 * k)) <= @length do
    j += 1 if j < @length && ! ordered?(j, j+1)
    break if ordered?(k, j)
    swap(k, j)
    success = true
    k = j
  end
  success
end

def swap(x, y)
  temp = @queue[x]
  @queue[x] = @queue[y]
  @queue[y] = temp
end

def swim(k)
  success = false
  while k > 1 && ! ordered?(k/2, k) do
    swap(k, k/2)
    k = k/2
    success = true
  end
  success
end