class Concurrent::Collection::RubyNonConcurrentPriorityQueue
@!macro priority_queue
@!visibility private @!macro internal_implementation_note
Public Class Methods
Source
# 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
@!macro priority_queue_method_from_list
Source
# 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
@!macro priority_queue_method_initialize
Public Instance Methods
Source
# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 18 def clear @queue = [nil] @length = 0 true end
@!macro priority_queue_method_clear
Source
# 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
@!macro priority_queue_method_delete
Source
# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 43 def empty? size == 0 end
@!macro priority_queue_method_empty
Source
# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 48 def include?(item) @queue.include?(item) end
@!macro priority_queue_method_include
Source
# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 54 def length @length end
@!macro priority_queue_method_length
Source
# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 60 def peek empty? ? nil : @queue[1] end
@!macro priority_queue_method_peek
Source
# 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
@!macro priority_queue_method_pop
Source
# 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
@!macro priority_queue_method_push
Private Instance Methods
Source
# File lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb, line 119 def ordered?(x, y) (@queue[x] <=> @queue[y]) == @comparator end
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
Source
# 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
Percolate down to maintain heap invariant.
@param [Integer] k the index at which to start the percolation
@!visibility private
Source
# 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
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
Source
# 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
Percolate up to maintain heap invariant.
@param [Integer] k the index at which to start the percolation
@!visibility private