class Algorithmix::DataStructure::Generic::PriorityQueue

Attributes

binary_heap[R]

Public Class Methods

new(obj = nil, copy: false, min: false) click to toggle source

Creates a new priority queue.

@param obj [#to_a] can be any object, which responds to to_a method @kwarg copy [true, false] if set to true, makes a copy of content of the given object @kwarg min [true, false] sets the main property of the new priority queue. By default max priority queue is created. @raise ArgumentError, if given object doesn't respond to to_a method. @return [PriorityQueue]

# 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

Public Instance Methods

!=(priority_queue) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a PriorityQueue. @return [true, false] true if contents are different, false otherwise

# 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) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a priority queue @return [PriorityQueue] a new priority queue

# 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) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a priority queue @return [PriorityQueue] a new priority queue

# 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) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a priority queue @return [PriorityQueue] a new priority queue

# 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
<<() click to toggle source

(see push)

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 43
def <<
  push(value)
end
<=>(priority_queue) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a PriorityQueue. @return 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

# 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) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a PriorityQueue. @return [true, false] true if contents are equal, false otherwise

# 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) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a priority queue @return [PriorityQueue] a new priority queue

# 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) click to toggle source

(see map)

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 340
def apply(&block)
  map(&block)
end
apply!(&block) click to toggle source

(see map!)

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 345
def apply!(&block)
  map!(&block)
end
assign(obj, copy: false) click to toggle source

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

@param obj [#to_a] @kwarg copy [true, false] @raise ArgumentError @return self object [PriorityQeue]

# 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() click to toggle source

Clears content of the queue.

@return [PriorityQueue] self object

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 128
def clear
  @binary_heap.clear
  self
end
concat(priority_queue) click to toggle source

(see +)

# 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) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a priority queue @return [PriorityQueue] self object

# 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) click to toggle source

(see #!=)

# 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) click to toggle source

(see -)

# 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) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a priority queue @return [PriorityQueue] self object

# 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?() click to toggle source

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

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 72
def empty?
  @binary_heap.empty?
end
eql?(priority_queue) click to toggle source

(see #==)

# 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) click to toggle source

(see select)

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 303
def filter(&block)
  select(&block)
end
filter!(&block) click to toggle source

(see select!)

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 308
def filter!(&block)
  select!(&block)
end
find_all(&block) click to toggle source

(see select)

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 313
def find_all(&block)
  select(&block)
end
find_all!(&block) click to toggle source

(see select!)

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 318
def find_all!(&block)
  select!(&block)
end
front() click to toggle source

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

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 57
def front
  @binary_heap.top
end
intersect(priority_queue) click to toggle source

(see #&)

# 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) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a priority queue @return [PriorityQueue] self object

# 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() click to toggle source

(see size)

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 67
def length
  @binary_heap.size
end
map(&block) click to toggle source

Applies a function to each element of the queue.

@param &block @return [PriorityQueue] a new priority queue

# 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) click to toggle source

Applies a function to each element of the queue.

@param &block @return [PriorityQueue] self object

# 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) click to toggle source

(see +)

# 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) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a priority queue @return [PriorityQueue] self object

# 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() click to toggle source

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

@raise Algorithmix::EmptyContainerError, if the queue is empty. @return element with the highest or lowest priority

# 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) click to toggle source

Inserts a value in the queue.

@param value @return [PriorityQueue] self object

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 37
def push(value)
  @binary_heap.insert(value)
  self
end
select(&block) click to toggle source

Filters elements of the queue by given condition.

@param &block @return [PriorityQueue] a new priority queue

# 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) click to toggle source

Filters elements of the queue by given condition.

@param &block @return [PriorityQueue] self object

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 297
def select!(&block)
  @binary_heap.select! { |e| block.call(e) }
  self
end
size() click to toggle source

Returns number of elements in the queue.

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 62
def size
  @binary_heap.size
end
symmetric_difference(priority_queue) click to toggle source

(see #^)

# 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) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a priority queue @return [PriorityQueue] self object

# 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() click to toggle source

Converts content of the queue to an array.

@return array with elements of the queue

# File lib/algorithmix/data_structure/generic/priority_queue.rb, line 121
def to_a
  @binary_heap.to_a
end
union(priority_queue) click to toggle source

(see #|)

# 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) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a priority queue @return [PriorityQueue] self object

# 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) click to toggle source

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

@param priority_queue [PriorityQueue] @raise ArgumentError, if given object is not a priority queue @return [PriorityQueue] a new priority queue

# 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