class Concurrent::Collection::RubyNonConcurrentPriorityQueue

@!macro priority_queue

@!visibility private @!macro internal_implementation_note

Public Class Methods

from_list(list, opts = {}) click to toggle source

@!macro priority_queue_method_from_list

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 89
def self.from_list(list, opts = {})
  queue = new(opts)
  list.each{|item| queue << item }
  queue
end
new(opts = {}) click to toggle source

@!macro priority_queue_method_initialize

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 11
def initialize(opts = {})
  order = opts.fetch(:order, :max)
  @comparator = [:min, :low].include?(order) ? -1 : 1
  clear
end

Public Instance Methods

<<(item)
Alias for: push
clear() click to toggle source

@!macro priority_queue_method_clear

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 18
def clear
  @queue = [nil]
  @length = 0
  true
end
delete(item) click to toggle source

@!macro priority_queue_method_delete

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 25
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
deq()
Alias for: pop
empty?() click to toggle source

@!macro priority_queue_method_empty

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 43
def empty?
  size == 0
end
enq(item)
Alias for: push
has_priority?(item)
Alias for: include?
include?(item) click to toggle source

@!macro priority_queue_method_include

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 48
def include?(item)
  @queue.include?(item)
end
Also aliased as: has_priority?
length() click to toggle source

@!macro priority_queue_method_length

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 54
def length
  @length
end
Also aliased as: size
peek() click to toggle source

@!macro priority_queue_method_peek

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 60
def peek
  empty? ? nil : @queue[1]
end
pop() click to toggle source

@!macro priority_queue_method_pop

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 65
def pop
  return nil if empty?
  max = @queue[1]
  swap(1, @length)
  @length -= 1
  sink(1)
  @queue.pop
  max
end
Also aliased as: deq, shift
push(item) click to toggle source

@!macro priority_queue_method_push

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 78
def push(item)
  raise ArgumentError.new('cannot enqueue nil') if item.nil?
  @length += 1
  @queue << item
  swim(@length)
  true
end
Also aliased as: <<, enq
shift()
Alias for: pop
size()
Alias for: length

Private Instance Methods

ordered?(x, y) click to toggle source

Are the items at the given indexes ordered based on the priority order specified at construction?

@param [Integer] x the first index from which to retrieve a comparable value @param [Integer] y the second index from which to retrieve a comparable value

@return [Boolean] true if the two elements are in the correct priority order

else false

@!visibility private

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 119
def ordered?(x, y)
  (@queue[x] <=> @queue[y]) == @comparator
end
sink(k) click to toggle source

Percolate down to maintain heap invariant.

@param [Integer] k the index at which to start the percolation

@!visibility private

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 128
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
swap(x, y) click to toggle source

Exchange the values at the given indexes within the internal array.

@param [Integer] x the first index to swap @param [Integer] y the second index to swap

@!visibility private

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 103
def swap(x, y)
  temp = @queue[x]
  @queue[x] = @queue[y]
  @queue[y] = temp
end
swim(k) click to toggle source

Percolate up to maintain heap invariant.

@param [Integer] k the index at which to start the percolation

@!visibility private

# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 147
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