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

#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

#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 



156
157
158
159
160
161
 
# File 'lib/philiprehberger/priority_queue.rb', line 156

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

#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