Class: Algorithmix::DataStructure::Generic::PriorityQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/algorithmix/data_structure/generic/priority_queue.rb

Instance Method Summary collapse

Constructor Details

#initialize(obj = nil, copy: false, min: false) ⇒ PriorityQueue

Creates a new priority queue.

Parameters:

  • obj (#to_a) (defaults to: nil) —

    can be any object, which responds to #to_a method

Raises:

  • ArgumentError, if given object doesn’t respond to to_a method.



17
18
19
20
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 17

def initialize(obj = nil, copy: false, min: false)
  @binary_heap = Heap::BinaryHeap.new(obj, copy: copy, min: min)
  @max = min ? false : true
end

Instance Method Details

#!=(priority_queue) ⇒ true, false

Comapres contents of the queue and a queue given as argument.

Parameters:

Returns:

  • (true, false) —

    true if contents are different, false otherwise

Raises:

  • ArgumentError, if given object is not a PriorityQueue.



97
98
99
100
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 97

def !=(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#!= for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  to_a != priority_queue.to_a
end

#&(priority_queue) ⇒ PriorityQueue

Finds the intersection of contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



209
210
211
212
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 209

def &(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#& for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  PriorityQueue.new(@binary_heap & priority_queue.send(:binary_heap), min: !@max)
end

#+(priority_queue) ⇒ PriorityQueue

Concatenates contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



138
139
140
141
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 138

def +(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#+ for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  PriorityQueue.new(@binary_heap + priority_queue.send(:binary_heap), min: !@max)
end

#-(priority_queue) ⇒ PriorityQueue

Finds the difference of contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



236
237
238
239
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 236

def -(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#- for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  PriorityQueue.new(@binary_heap - priority_queue.send(:binary_heap), min: !@max)
end

#<< ⇒ PriorityQueue

Inserts a value in the queue.

Parameters:

  • value

Returns:



43
44
45
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 43

def <<
  push(value)
end

#<=>(priority_queue) ⇒ Object

Comapres contents of the queue and a queue given as argument.

Parameters:

Returns:

  • 1 if content of the queue is > content of the given queue, 0 if contents are euqal, -1 if content of the given queue is > content of the queue

Raises:

  • ArgumentError, if given object is not a PriorityQueue.



113
114
115
116
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 113

def <=>(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#<=> for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  to_a <=> priority_queue.to_a
end

#==(priority_queue) ⇒ true, false

Comapres contents of the queue and a queue given as argument.

Parameters:

Returns:

  • (true, false) —

    true if contents are equal, false otherwise

Raises:

  • ArgumentError, if given object is not a PriorityQueue.



81
82
83
84
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 81

def ==(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#== for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  to_a == priority_queue.to_a
end

#^(priority_queue) ⇒ PriorityQueue

Finds the symmetric difference of contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



263
264
265
266
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 263

def ^(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#^ for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  PriorityQueue.new(@binary_heap ^ priority_queue.send(:binary_heap), min: !@max)
end

#apply(&block) ⇒ PriorityQueue

Applies a function to each element of the queue.

Parameters:

  • &block

Returns:



340
341
342
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 340

def apply(&block)
  map(&block)
end

#apply!(&block) ⇒ PriorityQueue

Applies a function to each element of the queue.

Parameters:

  • &block

Returns:



345
346
347
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 345

def apply!(&block)
  map!(&block)
end

#assign(obj, copy: false) ⇒ Object

Assigns content of an object, to content of the queue.

Parameters:

Returns:

  • self object [PriorityQeue]

Raises:

  • ArgumentError



28
29
30
31
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 28

def assign(obj, copy: false)
  @binary_heap.assign(obj, copy: copy)
  self
end

#clear ⇒ PriorityQueue

Clears content of the queue.

Returns:



128
129
130
131
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 128

def clear
  @binary_heap.clear
  self
end

#concat(priority_queue) ⇒ PriorityQueue

Concatenates contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



144
145
146
147
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 144

def concat(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#concat for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  self + priority_queue
end

#concat!(priority_queue) ⇒ PriorityQueue

Concatenates contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



160
161
162
163
164
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 160

def concat!(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#concat! for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  @binary_heap.concat!(priority_queue.send(:binary_heap))
  self
end

#diff?(priority_queue) ⇒ true, false

Comapres contents of the queue and a queue given as argument.

Parameters:

Returns:

  • (true, false) —

    true if contents are different, false otherwise

Raises:

  • ArgumentError, if given object is not a PriorityQueue.



103
104
105
106
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 103

def diff?(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#diff? for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  self != priority_queue
end

#difference(priority_queue) ⇒ PriorityQueue

Finds the difference of contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



242
243
244
245
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 242

def difference(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#difference for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  self - priority_queue
end

#difference!(priority_queue) ⇒ PriorityQueue

Finds the difference of contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



252
253
254
255
256
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 252

def difference!(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#difference! for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  @binary_heap.difference!(priority_queue.send(:binary_heap))
  self
end

#empty? ⇒ Boolean

Returns information for the content of the queue - are there any elements, or no.

Returns:

  • (Boolean) 


72
73
74
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 72

def empty?
  @binary_heap.empty?
end

#eql?(priority_queue) ⇒ true, false

Comapres contents of the queue and a queue given as argument.

Parameters:

Returns:

  • (true, false) —

    true if contents are equal, false otherwise

Raises:

  • ArgumentError, if given object is not a PriorityQueue.



87
88
89
90
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 87

def eql?(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#eql? for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  self == priority_queue
end

#filter(&block) ⇒ PriorityQueue

Filters elements of the queue by given condition.

Parameters:

  • &block

Returns:



303
304
305
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 303

def filter(&block)
  select(&block)
end

#filter!(&block) ⇒ PriorityQueue

Filters elements of the queue by given condition.

Parameters:

  • &block

Returns:



308
309
310
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 308

def filter!(&block)
  select!(&block)
end

#find_all(&block) ⇒ PriorityQueue

Filters elements of the queue by given condition.

Parameters:

  • &block

Returns:



313
314
315
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 313

def find_all(&block)
  select(&block)
end

#find_all!(&block) ⇒ PriorityQueue

Filters elements of the queue by given condition.

Parameters:

  • &block

Returns:



318
319
320
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 318

def find_all!(&block)
  select!(&block)
end

#front ⇒ Object

Returns the element with the highest or lowest priority without removing it from the queue.



57
58
59
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 57

def front
  @binary_heap.top
end

#intersect(priority_queue) ⇒ PriorityQueue

Finds the intersection of contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



215
216
217
218
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 215

def intersect(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#intersect for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  self & priority_queue
end

#intersect!(priority_queue) ⇒ PriorityQueue

Finds the intersection contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



225
226
227
228
229
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 225

def intersect!(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#intersect! for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  @binary_heap.intersect!(priority_queue.send(:binary_heap))
  self
end

#length ⇒ Object

Returns number of elements in the queue.



67
68
69
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 67

def length
  @binary_heap.size
end

#map(&block) ⇒ PriorityQueue

Applies a function to each element of the queue.

Parameters:

  • &block

Returns:



326
327
328
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 326

def map(&block)
  PriorityQueue.new(@binary_heap.map { |e| block.call(e)}, min: !@max)
end

#map!(&block) ⇒ PriorityQueue

Applies a function to each element of the queue.

Parameters:

  • &block

Returns:



334
335
336
337
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 334

def map!(&block)
  @binary_heap.map! { |e| block.call(e) }
  self
end

#merge(priority_queue) ⇒ PriorityQueue

Concatenates contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



150
151
152
153
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 150

def merge(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#merge for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  self + priority_queue
end

#merge!(priority_queue) ⇒ PriorityQueue

Concatenates contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



171
172
173
174
175
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 171

def merge!(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#merge! for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  @binary_heap.merge!(priority_queue.send(:binary_heap))
  self
end

#pop ⇒ Object

Removes the element with highest or lowest priority of the queue.

Returns:

  • element with the highest or lowest priority

Raises:

  • Algorithmix::EmptyContainerError, if the queue is empty.



51
52
53
54
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 51

def pop
  raise EmptyContainerError, "The priority queue is empty." if @binary_heap.empty?
  @binary_heap.extract
end

#push(value) ⇒ PriorityQueue

Inserts a value in the queue.

Parameters:

  • value

Returns:



37
38
39
40
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 37

def push(value)
  @binary_heap.insert(value)
  self
end

#select(&block) ⇒ PriorityQueue

Filters elements of the queue by given condition.

Parameters:

  • &block

Returns:



289
290
291
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 289

def select(&block)
  PriorityQueue.new(@binary_heap.select { |e| block.call(e) }, min: !@max)
end

#select!(&block) ⇒ PriorityQueue

Filters elements of the queue by given condition.

Parameters:

  • &block

Returns:



297
298
299
300
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 297

def select!(&block)
  @binary_heap.select! { |e| block.call(e) }
  self
end

#size ⇒ Object

Returns number of elements in the queue.



62
63
64
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 62

def size
  @binary_heap.size
end

#symmetric_difference(priority_queue) ⇒ PriorityQueue

Finds the symmetric difference of contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



269
270
271
272
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 269

def symmetric_difference(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#symmetric_difference for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  self ^ priority_queue
end

#symmetric_difference!(priority_queue) ⇒ PriorityQueue

Finds the symmetric difference of contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



279
280
281
282
283
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 279

def symmetric_difference!(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#symmetric_difference! for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  @binary_heap.symmetric_difference!(priority_queue.send(:binary_heap))
  self
end

#to_a ⇒ Object

Converts content of the queue to an array.

Returns:

  • array with elements of the queue



121
122
123
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 121

def to_a
  @binary_heap.to_a
end

#union(priority_queue) ⇒ PriorityQueue

Unites contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



188
189
190
191
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 188

def union(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#union for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  self | priority_queue
end

#union!(priority_queue) ⇒ PriorityQueue

Unites contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



198
199
200
201
202
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 198

def union!(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#union! for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
   @binary_heap = @binary_heap | priority_queue.send(:binary_heap)
  self
end

#|(priority_queue) ⇒ PriorityQueue

Unites contents of the queue and a queue given as argument.

Parameters:

Returns:

Raises:

  • ArgumentError, if given object is not a priority queue



182
183
184
185
 
# File 'lib/algorithmix/data_structure/generic/priority_queue.rb', line 182

def |(priority_queue)
  raise ArgumentError, "Undefined method PriorityQueue#| for #{priority_queue}:#{priority_queue.class}" unless priority_queue.is_a?(PriorityQueue)
  PriorityQueue.new(@binary_heap | priority_queue.send(:binary_heap), min: !@max)
end