Class: Bogo::PriorityQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/bogo/priority_queue.rb

Overview

Note:

does not allow duplicate objects to be queued

Specialized priority based queue

Instance Method Summary collapse

Constructor Details

#initialize(*args) ⇒ self

Create a new priority queue



8
9
10
11
12
13
 
# File 'lib/bogo/priority_queue.rb', line 8

def initialize(*args)
  @lock = Mutex.new
  @queue = Hash.new
  @block_costs = 0
  @reverse_sort = args.include?(:highscore)
end

Instance Method Details

#empty? ⇒ TrueClass, FalseClass

Returns:

  • (TrueClass, FalseClass) 


81
82
83
 
# File 'lib/bogo/priority_queue.rb', line 81

def empty?
  size == 0
end

#include?(object) ⇒ TrueClass, FalseClass

Returns:

  • (TrueClass, FalseClass) 


86
87
88
89
90
 
# File 'lib/bogo/priority_queue.rb', line 86

def include?(object)
  lock.synchronize do
    queue.keys.include?(object)
  end
end

#multi_push(items) ⇒ self

Push multiple items onto the queue at once

Parameters:

Returns:

  • (self) 


42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/bogo/priority_queue.rb', line 42

def multi_push(items)
  lock.synchronize do
    items.each do |item_pair|
      item, cost = item_pair
      if(queue[item])
        raise ArgumentError,
          "Item already exists in queue. Items must be unique! (#{item})"
      end
      unless(cost.is_a?(Numeric) || cost.is_a?(Proc))
        raise ArgumentError,
          "Cost must be provided as parameter or proc! (item: #{item})"
      end
      @block_costs += 1 if cost.is_a?(Proc)
      queue[item] = cost
    end
  end
  sort!
  self
end

#pop ⇒ Object, NilClass

Returns item or nil if empty.

Returns:

  • (Object, NilClass) —

    item or nil if empty



63
64
65
66
67
68
69
70
71
 
# File 'lib/bogo/priority_queue.rb', line 63

def pop
  sort! if @block_costs > 0
  lock.synchronize do
    item, score = queue.first
    @block_costs -= 1 if score.respond_to?(:call)
    queue.delete(item)
    item
  end
end

#push(item, cost = nil) { ... } ⇒ self

Push new item to the queue

Parameters:

  • item (Object)
  • cost (Float) (defaults to: nil)

Yields:

  • provide cost via proc

Returns:

  • (self) 


21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/bogo/priority_queue.rb', line 21

def push(item, cost=nil, &block)
  lock.synchronize do
    if(queue[item])
      raise ArgumentError,
        "Item already exists in queue. Items must be unique! (#{item})"
    end
    unless(cost || block_given?)
      raise ArgumentError,
        'Cost must be provided as parameter or block!'
    end
    @block_costs += 1 if cost.nil?
    queue[item] = cost || block
  end
  sort!
  self
end

#size ⇒ Integer

Returns current size of queue.

Returns:

  • (Integer) —

    current size of queue



74
75
76
77
78
 
# File 'lib/bogo/priority_queue.rb', line 74

def size
  lock.synchronize do
    queue.size
  end
end

#sort! ⇒ Object

Sort the queue based on cost



93
94
95
96
97
98
99
100
101
102
103
104
105
 
# File 'lib/bogo/priority_queue.rb', line 93

def sort!
  lock.synchronize do
    queue.replace(
      Hash[
        queue.sort do |x,y|
          x,y = y,x if @reverse_sort
          (x.last.respond_to?(:call) ? x.last.call : x.last).to_f <=>
            (y.last.respond_to?(:call) ? y.last.call : y.last).to_f
        end
      ]
    )
  end
end