Naïve implementation of a coalescing priority queue.

coalescing_priority_queue.rb

require 'algorithms'

# Hybrid data structure: A priority queue in which each value pushed
# also contains an indentifying key. If a new value with that same key
# is pushed before the previous one is popped, then only the one with
# the higher priority will actually be available. The implementation
# also guarantees that should multiple values with the same key and
# the same priority be pushed, the queue with will function in a
# last-in-first-out manner.

class CoalescingPriorityQueue

  ValueStruct = Struct.new(:identifier, :value, :priority, :max_priority_count)
  MetadataStruct = Struct.new(:max_priority, :counter_by_max_priority)

  def initialize
    @priority_queue = Containers::PriorityQueue.new
    @metadata_by_identifier = Hash.new
  end

  def push(identifier, value, priority)
    metadata = @metadata_by_identifier[identifier]
    if metadata
      if metadata.max_priority < priority
        metadata.max_priority = priority
        metadata.counter_by_max_priority = 1
      elsif metadata.max_priority == priority
        metadata.counter_by_max_priority += 1
      end
    else
      @metadata_by_identifier[identifier] = metadata = MetadataStruct.new(priority, 0)
    end

    value_struct = ValueStruct.new(identifier, value, priority, metadata.counter_by_max_priority)
    @priority_queue.push(value_struct, priority)

    value
  end

  def pop
    while (value_struct = @priority_queue.pop)
      metadata = @metadata_by_identifier[value_struct.identifier]
      if value_struct.priority == metadata.max_priority &&
         value_struct.max_priority_count == metadata.counter_by_max_priority
        @metadata_by_identifier.delete(identifier)
        break
      end
    end

    value_struct.value if value_struct
  end

  def peek
    while (value_struct = @priority_queue.next)
      metadata = @metadata_by_identifier[value_struct.identifier]
      if value_struct.priority == metadata.max_priority &&
         value_struct.max_priority_count == metadata.counter_by_max_priority
        break
      else
        # Throw away this value since it's stale for it's identifier.
        # - Yes, this is a mutating operation inside of "peek". Think of it as GC.
        @priority_queue.pop
      end
    end

    value_struct.value if value_struct
  end
  alias_method :next, :peek

end