Class: Philiprehberger::PriorityQueue::Queue

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/philiprehberger/priority_queue.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(mode: :min, &comparator) ⇒ Queue

Returns a new instance of Queue.



12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/philiprehberger/priority_queue.rb', line 12

def initialize(mode: :min, &comparator)
  @heap = []
  @size = 0
  @insertion_counter = 0
  @item_index = {}

  @comparator = if comparator
                  comparator
                elsif mode == :max
                  ->(a, b) { b <=> a }
                else
                  ->(a, b) { a <=> b }
                end
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



10
11
12
 
# File 'lib/philiprehberger/priority_queue.rb', line 10

def size
  @size
end

Instance Method Details

#<<(item_with_priority) ⇒ Object

Raises:

  • (ArgumentError) 


37
38
39
40
41
 
# File 'lib/philiprehberger/priority_queue.rb', line 37

def <<(item_with_priority)
  raise ArgumentError, 'Expected a hash with :item and :priority keys' unless item_with_priority.is_a?(Hash)

  push(item_with_priority[:item], priority: item_with_priority[:priority])
end

#bulk_push(items_hash) ⇒ self

Insert multiple items from a hash in one call.

Parameters:

  • items_hash (Hash) —

    a mapping of item to priority

Returns:

  • (self) —

    the queue, for chaining

Raises:

  • (ArgumentError) —

    if items_hash is not a Hash



161
162
163
164
165
166
 
# File 'lib/philiprehberger/priority_queue.rb', line 161

def bulk_push(items_hash)
  raise ArgumentError, "Expected a Hash, got #{items_hash.class}" unless items_hash.is_a?(Hash)

  items_hash.each { |item, priority| push(item, priority: priority) }
  self
end

#change_priority(item, new_priority) ⇒ Object

Raises:

  • (ArgumentError) 


76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/philiprehberger/priority_queue.rb', line 76

def change_priority(item, new_priority)
  idx = @item_index[item]
  raise ArgumentError, "Item not found in queue: #{item.inspect}" if idx.nil?

  old_priority = @heap[idx][0]
  @heap[idx] = [new_priority, @heap[idx][1], item]

  cmp = @comparator.call(new_priority, old_priority)
  if cmp.negative?
    bubble_up(idx)
  elsif cmp.positive?
    bubble_down(idx)
  end
  self
end

#clear ⇒ Object 



100
101
102
103
104
105
 
# File 'lib/philiprehberger/priority_queue.rb', line 100

def clear
  @heap.clear
  @item_index.clear
  @size = 0
  self
end

#delete(item) ⇒ Object 



132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/philiprehberger/priority_queue.rb', line 132

def delete(item)
  idx = @item_index[item]
  return nil if idx.nil?

  if idx == @size - 1
    entry = @heap.pop
    @size -= 1
    @item_index.delete(item)
    return entry[2]
  end

  swap(idx, @size - 1)
  entry = @heap.pop
  @size -= 1
  @item_index.delete(item)
  bubble_up(idx)
  bubble_down(idx)
  entry[2]
end

#drain ⇒ Object 



126
127
128
129
130
 
# File 'lib/philiprehberger/priority_queue.rb', line 126

def drain
  result = []
  result << pop until empty?
  result
end

#each(&block) ⇒ Object 



107
108
109
110
111
112
113
 
# File 'lib/philiprehberger/priority_queue.rb', line 107

def each(&block)
  return enum_for(:each) unless block

  sorted = @heap.sort { |a, b| compare_entries(a, b) }
  sorted.each { |entry| block.call(entry[2], entry[0]) }
  self
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


72
73
74
 
# File 'lib/philiprehberger/priority_queue.rb', line 72

def empty?
  @size.zero?
end

#find {|item, priority| ... } ⇒ Array, ...

Find the first [item, priority] pair in priority order for which the block returns a truthy value.

Yields:

  • (item, priority) —

    pairs in priority order

Yield Parameters:

  • item (Object) —

    the item

  • priority (Object) —

    the priority

Returns:

  • (Array, nil) —

    the first matching [item, priority] pair, or nil when none match

  • (Enumerator) —

    if no block is given



189
190
191
192
193
194
195
196
 
# File 'lib/philiprehberger/priority_queue.rb', line 189

def find(&block)
  return enum_for(:find) unless block

  each do |item, priority|
    return [item, priority] if block.call(item, priority)
  end
  nil
end

#include?(item) ⇒ Boolean

Returns:

  • (Boolean) 


96
97
98
 
# File 'lib/philiprehberger/priority_queue.rb', line 96

def include?(item)
  @item_index.key?(item)
end

#merge(other) ⇒ Object 



198
199
200
201
202
203
 
# File 'lib/philiprehberger/priority_queue.rb', line 198

def merge(other)
  merged = self.class.new(&@comparator)
  @heap.each { |entry| merged.push(entry[2], priority: entry[0]) }
  other.each_entry { |entry| merged.push(entry[2], priority: entry[0]) }
  merged
end

#peek ⇒ Object 



54
55
56
57
58
 
# File 'lib/philiprehberger/priority_queue.rb', line 54

def peek
  return nil if empty?

  @heap[0][2]
end

#peek_priority ⇒ Object 



120
121
122
123
124
 
# File 'lib/philiprehberger/priority_queue.rb', line 120

def peek_priority
  return nil if empty?

  @heap[0][0]
end

#pop ⇒ Object 



43
44
45
46
47
48
49
50
51
52
 
# File 'lib/philiprehberger/priority_queue.rb', line 43

def pop
  return nil if empty?

  swap(0, @size - 1)
  entry = @heap.pop
  @size -= 1
  @item_index.delete(entry[2])
  bubble_down(0) unless empty?
  entry[2]
end

#pop_n(n) ⇒ Object

Raises:

  • (ArgumentError) 


60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/philiprehberger/priority_queue.rb', line 60

def pop_n(n)
  raise ArgumentError, "n must be non-negative, got #{n}" if n.negative?

  result = []
  n.times do
    break if empty?

    result << pop
  end
  result
end

#priorities ⇒ Object 



152
153
154
 
# File 'lib/philiprehberger/priority_queue.rb', line 152

def priorities
  @heap.map { |entry| entry[0] }.uniq.sort
end

#priority_of(item) ⇒ Object?

Look up the priority of the first matching item.

Uses a linear scan (O(n)) over internal storage and returns the priority associated with the first entry whose item is == to the argument.

Parameters:

  • item (Object) —

    the item to look up

Returns:

  • (Object, nil) —

    the priority of the first match, or nil when not present



176
177
178
179
 
# File 'lib/philiprehberger/priority_queue.rb', line 176

def priority_of(item)
  entry = @heap.find { |e| e[2] == item }
  entry.nil? ? nil : entry[0]
end

#push(item, priority:) ⇒ Object 



27
28
29
30
31
32
33
34
35
 
# File 'lib/philiprehberger/priority_queue.rb', line 27

def push(item, priority:)
  entry = [priority, @insertion_counter, item]
  @insertion_counter += 1
  @heap << entry
  @item_index[item] = @size
  @size += 1
  bubble_up(@size - 1)
  self
end

#push_many(items) ⇒ Object 



115
116
117
118
 
# File 'lib/philiprehberger/priority_queue.rb', line 115

def push_many(items)
  items.each { |h| push(h[:item], priority: h[:priority]) }
  self
end

#to_a ⇒ Object 



92
93
94
 
# File 'lib/philiprehberger/priority_queue.rb', line 92

def to_a
  @heap.sort { |a, b| compare_entries(a, b) }.map { |entry| entry[2] }
end