Class: Depq

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

Overview

Depq - Double-Ended Priority Queue

depq is double-ended stable priority queue with priority update operation implemented using implicit heap.

Features

  • queue - you can insert and delete values

  • priority - you can get a value with minimum priority

  • double-ended - you can get a value with maximum priority too

  • stable - you will get the value inserted first with minimum/maximum priority

  • priority change - you can change the priority of a inserted value. (usable for Dijkstra’s shortest path algorithm and various graph algorithms)

  • implicit heap - compact heap representation using array. most operations are O(log n) at worst

  • iterator operations: nlargest, nsmallest and merge

Introduction

Simple Insertion/Deletion

You can insert values into a Depq object. You can delete the values from the object from ascending/descending order. delete_min deletes the minimum value. It is used for ascending order.

q = Depq.new
q.insert "durian"
q.insert "banana"
p q.delete_min     #=> "banana"
q.insert "orange"
q.insert "apple"
q.insert "melon"
p q.delete_min     #=> "apple"
p q.delete_min     #=> "durian"
p q.delete_min     #=> "melon"
p q.delete_min     #=> "orange"
p q.delete_min     #=> nil

delete_max is similar to delete_min except it deletes maximum element instead of minimum. It is used for descending order.

The Order

The order is defined by the priorities corresponds to the values and comparison operator specified for the queue.

q = Depq.new(:casecmp)   # use casecmp instead of <=>.
q.insert 1, "Foo"          # specify the priority for 1 as "Foo"
q.insert 2, "bar"
q.insert 3, "Baz"
p q.delete_min     #=> 2   # "bar" is minimum
p q.delete_min     #=> 3
p q.delete_min     #=> 1   # "Foo" is maximum
p q.delete_min     #=> nil

If there are multiple values with same priority, subpriority is used to compare them. subpriority is an integer which can be specified by 3rd argument of insert. If it is not specified, total number of inserted elements is used. So Depq is “stable” which means that the element inserted first is deleted first.

q = Depq.new
q.insert "a", 1    # "a", "c" and "e" has same priority: 1
q.insert "b", 0    # "b", "d" and "f" has same priority: 0
q.insert "c", 1
q.insert "d", 0
q.insert "e", 1
q.insert "f", 0
p q.delete_min     #=> "b"         first element with priority 0
p q.delete_min     #=> "d"
p q.delete_min     #=> "f"         last element with priority 0
p q.delete_min     #=> "a"         first element with priority 1
p q.delete_min     #=> "c"
p q.delete_min     #=> "e"         last element with priority 1

Note that delete_max is also stable. This means delete_max deletes the element with maximum priority with “minimum” subpriority.

q = Depq.new
q.insert "a", 1    # "a", "c" and "e" has same priority: 1
q.insert "b", 0    # "b", "d" and "f" has same priority: 0
q.insert "c", 1
q.insert "d", 0
q.insert "e", 1
q.insert "f", 0
p q.delete_max     #=> "a"         first element with priority 1
p q.delete_max     #=> "c"
p q.delete_max     #=> "e"         last element with priority 1
p q.delete_max     #=> "b"         first element with priority 0
p q.delete_max     #=> "d"
p q.delete_max     #=> "f"         last element with priority 0

Update Element

An inserted element can be modified and/or deleted. The element to be modified is specified by Depq::Locator object. It is returned by insert, find_min_locator, etc.

q = Depq.new
d = q.insert "durian", 1
m = q.insert "mangosteen", 2
c = q.insert "cherry", 3
p m                         #=> #<Depq::Locator: "mangosteen":2>
p m.value                   #=> "mangosteen"
p m.priority                #=> 2
p q.find_min               #=> "durian"
p q.find_min_locator       #=> #<Depq::Locator: "durian":1>
m.update("mangosteen", 0)
p q.find_min               #=> "mangosteen"
p q.find_min_locator       #=> #<Depq::Locator: "mangosteen":0>
q.delete_element d
p q.delete_min             #=> "mangosteen"
p q.delete_min             #=> "cherry"
p q.delete_min             #=> nil

For example, this feature can be used for graph algorithms such as Dijkstra’s shortest path finding algorithm, A* search algorithm, etc.

def dijkstra_shortest_path(start, edges)
  h = {}
  edges.each {|v1, v2, w|
    (h[v1] ||= []) << [v2, w]
  }
  h.default = []
  q = Depq.new
  visited = {start => q.insert([start], 0)}
  until q.empty?
    path, w1 = q.delete_min_priority
    v1 = path.last
    h[v1].each {|v2, w2|
      if !visited[v2]
        visited[v2] = q.insert(path+[v2], w1 + w2)
      elsif w1 + w2 < visited[v2].priority
        visited[v2].update(path+[v2], w1 + w2)     # update val/prio
      end
    }
  end
  result = []
  visited.each_value {|loc|
    result << [loc.value, loc.priority]
  }
  result
end

E = [
  ['A', 'B', 2],
  ['A', 'C', 4],
  ['B', 'C', 1],
  ['C', 'B', 2],
  ['B', 'D', 3],
  ['C', 'D', 1],
]
p dijkstra_shortest_path('A', E)
#=> [[["A"], 0],
#    [["A", "B"], 2],
#    [["A", "B", "C"], 3],
#    [["A", "B", "C", "D"], 4]]

Internal Heap Algorithm

Depq uses min-heap, max-heap or interval-heap internally. When delete_min is used, min-heap is constructed. When delete_max is used, max-heap is constructed. When delete_min and delete_max is used, interval-heap is constructed.

Defined Under Namespace

Classes: Locator

Constant Summary collapse

ARY_SLICE_SIZE =

:stopdoc:

3

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(cmp = :<=>) ⇒ Depq

Create a Depq object.

The optional argument, cmp, specify the method to compare priorities. It should be a symbol or a comparator like a Proc which takes two arguments and returns -1, 0, 1. If it is omitted, :<=> is used.

q = Depq.new
q.insert "Foo"
q.insert "bar"
p q.delete_min   #=> "Foo"
p q.delete_min   #=> "bar"

q = Depq.new(:casecmp)
q.insert "Foo"
q.insert "bar"
p q.delete_min   #=> "bar"
p q.delete_min   #=> "Foo"

q = Depq.new(lambda {|a,b| a.casecmp(b) })
q.insert "Foo"
q.insert "bar"
p q.delete_min   #=> "bar"
p q.delete_min   #=> "Foo"

class Cmp
  def call(a,b) a.casecmp(b) end
end
q = Depq.new(Cmp.new)
q.insert "Foo"
q.insert "bar"
p q.delete_min   #=> "bar"
p q.delete_min   #=> "Foo"



436
437
438
439
440
441
442
 
# File 'lib/depq.rb', line 436

def initialize(cmp = :<=>)
  @cmp = cmp
  @ary = []
  @heapsize = 0
  @mode = nil
  @totalcount = 0
end

Class Method Details

.astar_search(start, heuristics = nil, &find_nexts) ⇒ Object

search a graph using A* search algorithm.

The graph is defined by start argument and the given block. start specifies the start node for searching. The block should takes a node and return an array of pairs. The pair is an 2-element array which contains the next node and cost of the given node to the next node.

The optional argument, heuristics specifies conservative estimation to goal. It should be a Hash or a Proc that heuristics[node] returns an estimated cost to goal. The estimated cost must be smaller or equal to the true cost. If heuristics is not given, Hash.new(0) is used. This means Depq.astar_search behaves as Dijkstra’s algorithm in that case.

Depq.astar_search returns an enumerator. It yields 3 values: previous node, current node and total cost between start node to current node. When current node is start node, nil is given for previous node.

#    7    5    1
#  A--->B--->C--->D
#  |    |    |    |
# 2|   4|   1|   3|
#  |    |    |    |
#  V    V    V    V
#  E--->F--->G--->H
#    3    3    5
#
g = {
  :A => [[:B, 7], [:E, 2]],
  :B => [[:C, 5], [:F, 4]],
  :C => [[:D, 1], [:G, 1]],
  :D => [[:H, 3]],
  :E => [[:F, 3]],
  :F => [[:G, 3]],
  :G => [[:H, 5]],
  :H => []
}
# This doesn't specify _heuristics_.  So This is Dijkstra's algorithm.
Depq.astar_search(:A) {|n| g[n] }.each {|prev, curr, cost| p [prev, curr, cost] }
#=> [nil, :A, 0]
#   [:A, :E, 2]
#   [:E, :F, 5]
#   [:A, :B, 7]
#   [:F, :G, 8]
#   [:B, :C, 12]
#   [:G, :H, 13]  # H found.
#   [:C, :D, 13]

# heuristics using Manhattan distance assuming the goal is H.
h = {
  :A => 4,
  :B => 3,
  :C => 2,
  :D => 1,
  :E => 3,
  :F => 2,
  :G => 1,
  :H => 0
}
# This specify _heuristics_.  So This is A* search algorithm.
Depq.astar_search(:A, h) {|n| g[n] }.each {|prev, curr, cost| p [prev, curr, cost] }
#=> [nil, :A, 0]
#   [:A, :E, 2]
#   [:E, :F, 5]
#   [:F, :G, 8]
#   [:A, :B, 7]
#   [:G, :H, 13]  # H found.  Bit better than Dijkstra's algorithm.
#   [:B, :C, 12]
#   [:C, :D, 13]

cf. en.wikipedia.org/wiki/A*_search_algorithm



1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
 
# File 'lib/depq.rb', line 1551

def Depq.astar_search(start, heuristics=nil, &find_nexts)
  Enumerator.new {|y|
    heuristics ||= Hash.new(0)
    h = Hash.new {|_, k| h[k] = heuristics[k] }
    q = Depq.new
    visited = {start => q.insert([nil, start], h[start])}
    until q.empty?
      path, w1 = q.delete_min_priority
      v1 = path.last
      w1 -= h[v1]
      y.yield [path.first, path.last, w1]
      find_nexts.call(v1).each {|v2, w2|
        w3 = w1 + w2 + h[v2]
        if !visited[v2]
          visited[v2] = q.insert([path.last,v2], w3)
        elsif w3 < visited[v2].priority
          visited[v2].update([path.last,v2], w3)
        end
      }
    end
    nil
  }
end

.merge(*iters, &b) ⇒ Object

iterates over iterators specified by arguments.

The iteration order is sorted, from minimum to maximum, if all the arugment iterators are sorted.

Depq.merge(1..4, 3..6) {|v| p v }
#=> 1
#   2
#   3
#   3
#   4
#   4
#   5
#   6



1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
 
# File 'lib/depq.rb', line 1444

def Depq.merge(*iters, &b)
  q = Depq.new
  iters.each {|enum|
    enum = enum.to_enum unless enum.kind_of? Enumerator
    begin
      val = enum.next
    rescue StopIteration
      next
    end
    q.insert enum, val
  }
  loop = lambda {|y, meth|
    until q.empty?
      loc = q.find_min_locator
      enum = loc.value
      val = loc.priority
      y.send meth, val
      begin
        val = enum.next
      rescue StopIteration
        q.delete_locator loc
        next
      end
      loc.update enum, val
    end
  }
  if block_given?
    loop.call(b, :call)
  else
    Enumerator.new {|y|
      loop.call(y, :yield)
    }
  end
end

.nlargest(n, iter) ⇒ Object

:call-seq:

Depq.nlargest(n, iter)
Depq.nlargest(n, iter) {|e| order }

returns the largest n elements in iter as an array.

The result array is ordered from the minimum element.

p Depq.nlargest(3, [5, 2, 3, 1, 4, 6, 7]) #=> [5, 6, 7]

If the block is given, the elements are compared by the corresponding block values.

p Depq.nlargest(3, [5, 2, 3, 1, 4, 6, 7]) {|e| -e } #=> [3, 2, 1]

Raises:

  • (ArgumentError) 


1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
 
# File 'lib/depq.rb', line 1333

def Depq.nlargest(n, iter)
  raise ArgumentError, "n is negative" if n < 0
  return [] if n == 0
  limit = (n * Math.log(1+n)).ceil
  limit = 1024 if limit < 1024
  q = Depq.new
  threshold = nil
  iter.each {|e|
    if block_given?
      v = yield e
    else
      v = e
    end
    if q.size < n
      if q.size == 0
        threshold = v
      else
        threshold = v if (v <=> threshold) < 0
      end
      q.insert e, v
    else
      if (v <=> threshold) > 0
        q.insert e, v
        if limit < q.size
          tmp = []
          n.times { tmp << q.delete_max_locator }
          q.clear
          tmp.each {|loc| q.insert_locator loc }
          threshold = tmp.last.priority
        end
      end
    end
  }
  n = q.size if q.size < n
  a = []
  n.times { a << q.delete_max }
  a.reverse!
  a
end

.nsmallest(n, iter) ⇒ Object

:call-seq:

Depq.nsmallest(n, iter)
Depq.nsmallest(n, iter) {|e| order }

returns the smallest n elements in iter as an array.

The result array is ordered from the minimum element.

p Depq.nsmallest(5, [5, 2, 3, 1, 4, 6, 7]) #=> [1, 2, 3, 4, 5]

If the block is given, the elements are compared by the corresnponding block values.

p Depq.nsmallest(5, [5, 2, 3, 1, 4, 6, 7]) {|e| -e } #=> [7, 6, 5, 4, 3]

Raises:

  • (ArgumentError) 


1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
 
# File 'lib/depq.rb', line 1388

def Depq.nsmallest(n, iter)
  raise ArgumentError, "n is negative" if n < 0
  return [] if n == 0
  limit = (n * Math.log(1+n)).ceil
  limit = 1024 if limit < 1024
  q = Depq.new
  threshold = nil
  iter.each {|e|
    if block_given?
      v = yield e
    else
      v = e
    end
    if q.size < n
      if q.size == 0
        threshold = v
      else
        threshold = v if (v <=> threshold) > 0
      end
      q.insert e, v
    else
      if (v <=> threshold) < 0
        q.insert e, v
        if limit < q.size
          tmp = []
          n.times { tmp << q.delete_min_locator }
          q.clear
          tmp.each {|loc| q.insert_locator loc }
          threshold = tmp.last.priority
        end
      end
    end
  }
  n = q.size if q.size < n
  a = []
  n.times {
    a << q.delete_min
  }
  a
end

Instance Method Details

#clear ⇒ Object

make the queue empty.

Note that totalcount is not changed.

q = Depq.new
q.insert 1
q.insert 1
p q.size         #=> 2
p q.totalcount   #=> 2
q.clear
p q.size         #=> 0
p q.totalcount   #=> 2
p q.find_min     #=> nil



708
709
710
711
712
 
# File 'lib/depq.rb', line 708

def clear
  @ary.clear
  @heapsize = 0
  @mode = nil
end

#compare_priority(priority1, priority2) ⇒ Object

compare priority1 and priority2.

q = Depq.new
p q.compare_priority("a", "b") #=> -1
p q.compare_priority("a", "a") #=> 0
p q.compare_priority("b", "a") #=> 1

q = Depq.new(:casecmp)
p q.compare_priority("a", "A") #=> 0



628
629
630
631
632
633
634
 
# File 'lib/depq.rb', line 628

def compare_priority(priority1, priority2)
  if @cmp.kind_of? Symbol
    priority1.__send__(@cmp, priority2)
  else
    @cmp.call(priority1, priority2)
  end
end

#delete_locator(loc) ⇒ Object

delete the element specified by the locator.

q = Depq.new
q.insert 3
loc = q.insert 2
q.insert 1
q.delete_locator loc
p q.delete_min           #=> 1
p q.delete_min           #=> 3
p q.delete_min           #=> nil



991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
 
# File 'lib/depq.rb', line 991

def delete_locator(loc)
  check_locator(loc)
  index = loc.send(:index)
  if @heapsize <= index
    priority, subpriority = get_entry_ps(index)
    last = self.size - 1
    if index != last
      loc2, priority2, subpriority2 = get_entry(last)
      set_entry(index, loc2, priority2, subpriority2)
      loc2.send(:index=, index)
    end
    delete_last_entry
    loc.send(:internal_deleted, priority, subpriority)
    loc
  else
    mode_heapify
    @heapsize = mode_call(:delete_loc, loc)
    loc
  end
end

#delete_max ⇒ Object Also known as: pop

delete the maximum element in the queue and returns the value.

This method returns the value of the deleted element. nil is returned if the queue is empty.

q = Depq.new
q.insert 3
q.insert 1
q.insert 2
p q.delete_max   #=> 3
p q.delete_max   #=> 2
p q.delete_max   #=> 1
p q.delete_max   #=> nil



1132
1133
1134
1135
 
# File 'lib/depq.rb', line 1132

def delete_max
  loc = delete_max_locator
  loc and loc.value
end

#delete_max_locator ⇒ Object

delete the maximum element in the queue and returns the locator.

This method returns the locator for the deleted element. nil is returned if the queue is empty.

q = Depq.new
q.insert 2
q.insert 1
q.insert 3
p q.delete_max_locator   #=> #<Depq::Locator: 3 (no queue)>
p q.delete_max_locator   #=> #<Depq::Locator: 2 (no queue)>
p q.delete_max_locator   #=> #<Depq::Locator: 1 (no queue)>
p q.delete_max_locator   #=> nil



1090
1091
1092
1093
1094
1095
1096
 
# File 'lib/depq.rb', line 1090

def delete_max_locator
  return nil if empty?
  use_max
  loc = mode_call(:find_max_loc)
  @heapsize = mode_call(:delete_loc, loc)
  loc
end

#delete_max_priority ⇒ Object

delete the maximum element in the queue and returns the value and its priority.

This method returns an array which contains the value and its priority of the deleted element. nil is returned if the queue is empty.

q = Depq.new
q.insert "durian", 1
q.insert "banana", 3
q.insert "melon", 2
p q.delete_max_priority  #=> ["banana", 3]
p q.delete_max_priority  #=> ["melon", 2]
p q.delete_max_priority  #=> ["durian", 1]
p q.delete_max_priority  #=> nil



1113
1114
1115
1116
 
# File 'lib/depq.rb', line 1113

def delete_max_priority
  loc = delete_max_locator
  loc and [loc.value, loc.priority]
end

#delete_min ⇒ Object Also known as: shift, dequeue, deq

delete the minimum element in the queue and returns the value.

This method returns the value of the deleted element. nil is returned if the queue is empty.

q = Depq.new
q.insert 3
q.insert 1
q.insert 2
p q.delete_min   #=> 1
p q.delete_min   #=> 2
p q.delete_min   #=> 3
p q.delete_min   #=> nil



1068
1069
1070
1071
 
# File 'lib/depq.rb', line 1068

def delete_min
  loc = delete_min_locator
  loc and loc.value
end

#delete_min_locator ⇒ Object

delete the minimum element in the queue and returns the locator.

This method returns the locator for the deleted element. nil is returned if the queue is empty.

q = Depq.new
q.insert 2
q.insert 1
q.insert 3
p q.delete_min_locator   #=> #<Depq::Locator: 1 (no queue)>
p q.delete_min_locator   #=> #<Depq::Locator: 2 (no queue)>
p q.delete_min_locator   #=> #<Depq::Locator: 3 (no queue)>
p q.delete_min_locator   #=> nil



1026
1027
1028
1029
1030
1031
1032
 
# File 'lib/depq.rb', line 1026

def delete_min_locator
  return nil if empty?
  use_min
  loc = mode_call(:find_min_loc)
  @heapsize = mode_call(:delete_loc, loc)
  loc
end

#delete_min_priority ⇒ Object

delete the minimum element in the queue and returns the value and its priority.

This method returns an array which contains the value and its priority of the deleted element. nil is returned if the queue is empty.

q = Depq.new
q.insert "durian", 1
q.insert "banana", 3
q.insert "melon", 2
p q.delete_min_priority  #=> ["durian", 1]
p q.delete_min_priority  #=> ["melon", 2]
p q.delete_min_priority  #=> ["banana", 3]
p q.delete_min_priority  #=> nil



1049
1050
1051
1052
 
# File 'lib/depq.rb', line 1049

def delete_min_priority
  loc = delete_min_locator
  loc and [loc.value, loc.priority]
end

#delete_unspecified ⇒ Object

delete an element in the queue and returns the value. The element is choosen for fast deletion.

This method returns the value of the deleted element. nil is returned if the queue is empty.

q = Depq.new
q.insert 1
q.insert 4
q.insert 3
p q.delete_unspecified   #=> 3
p q.delete_unspecified   #=> 4
p q.delete_unspecified   #=> 1
p q.delete_unspecified   #=> nil



1195
1196
1197
1198
 
# File 'lib/depq.rb', line 1195

def delete_unspecified
  loc = delete_unspecified_locator
  loc and loc.value
end

#delete_unspecified_locator ⇒ Object

delete an element in the queue and returns the locator. The element is choosen for fast deletion.

This method returns the locator for the deleted element. nil is returned if the queue is empty.

q = Depq.new
q.insert 1
q.insert 4
q.insert 3
p q.delete_unspecified_locator #=> #<Depq::Locator: 3 (no queue)>
p q.delete_unspecified_locator #=> #<Depq::Locator: 4 (no queue)>
p q.delete_unspecified_locator #=> #<Depq::Locator: 1 (no queue)>
p q.delete_unspecified_locator #=> nil



1153
1154
1155
1156
1157
 
# File 'lib/depq.rb', line 1153

def delete_unspecified_locator
  return nil if empty?
  loc = get_entry_e(self.size-1)
  delete_locator(loc)
end

#delete_unspecified_priority ⇒ Object

delete an element in the queue and returns the value and its priority. The element is choosen for fast deletion.

This method returns an array which contains the value and its priority of the deleted element. nil is returned if the queue is empty.

q = Depq.new
q.insert "durian", 1
q.insert "banana", 3
q.insert "melon", 2
p q.delete_unspecified_priority  #=> ["melon", 2]
p q.delete_unspecified_priority  #=> ["banana", 3]
p q.delete_unspecified_priority  #=> ["durian", 1]
p q.delete_unspecified_priority  #=> nil



1175
1176
1177
1178
 
# File 'lib/depq.rb', line 1175

def delete_unspecified_priority
  loc = delete_unspecified_locator
  loc and [loc.value, loc.priority]
end

#each ⇒ Object

iterate over the values in the queue.

The iteration order is unspecified.

q = Depq.new
q.insert 3
q.insert 1
q.insert 2
p q.delete_min   #=> 1
q.each {|v|
  p v     #=> 2, 3
}



1311
1312
1313
1314
1315
1316
 
# File 'lib/depq.rb', line 1311

def each # :yield: value
  each_entry {|locator, priority|
    yield locator.value
  }
  nil
end

#each_locator ⇒ Object

iterate over the locators in the queue.

The iteration order is unspecified.

q = Depq.new
q.insert 3
q.insert 1
q.insert 2
p q.delete_min           #=> 1
q.each_locator {|v|
  p v     #=> #<Depq::Locator: 2>, #<Depq::Locator: 3>
}



1269
1270
1271
1272
1273
1274
 
# File 'lib/depq.rb', line 1269

def each_locator # :yield: locator
  each_entry {|locator,|
    yield locator
  }
  nil
end

#each_with_priority ⇒ Object

iterate over the values and priorities in the queue.

The iteration order is unspecified.

q = Depq.new
q.insert "durian", 1
q.insert "banana", 3
q.insert "melon", 2
q.each_with_priority {|val, priority|
  p [val, priority]
}
#=> ["durian", 1]
#   ["banana", 3]
#   ["melon", 2]



1291
1292
1293
1294
1295
1296
 
# File 'lib/depq.rb', line 1291

def each_with_priority # :yield: value, priority
  each_entry {|locator, priority|
    yield locator.value, priority
  }
  nil
end

#empty? ⇒ Boolean

returns true if the queue is empty.

q = Depq.new
p q.empty?       #=> true
q.insert 1
p q.empty?       #=> false
q.delete_max
p q.empty?       #=> true

Returns:

  • (Boolean) 


645
646
647
 
# File 'lib/depq.rb', line 645

def empty?
  @ary.empty?
end

#find_max ⇒ Object Also known as: max, last

returns the maximum value. This method returns nil if the queue is empty.

This method doesn’t delete the element from the queue.

q = Depq.new
p q.find_max     #=> nil
q.insert 3
q.insert 1
q.insert 2
p q.find_max     #=> 3
p q.find_max     #=> 3
p q.delete_max   #=> 3
p q.find_max     #=> 2



942
943
944
 
# File 'lib/depq.rb', line 942

def find_max
  loc = find_max_locator and loc.value
end

#find_max_locator ⇒ Object

return the locator for the maximum element. This method returns nil if the queue is empty.

This method doesn’t delete the element from the queue.

q = Depq.new
p q.find_max_locator     #=> nil
q.insert 3
q.insert 1
q.insert 2
p q.find_max_locator     #=> #<Depq::Locator: 3>
p q.find_max_locator     #=> #<Depq::Locator: 3>
p q.find_max_locator     #=> #<Depq::Locator: 3>
p q.delete_max           #=> 3
p q.find_max_locator     #=> #<Depq::Locator: 2>



900
901
902
903
904
 
# File 'lib/depq.rb', line 900

def find_max_locator
  return nil if empty?
  use_max
  mode_call(:find_max_loc)
end

#find_max_priority ⇒ Object

return the maximum value with its priority. This method returns nil if the queue is empty.

This method doesn’t delete the element from the queue.

q = Depq.new
p q.find_max_priority    #=> nil
q.insert "durian", 1
q.insert "banana", 3
q.insert "melon", 2
p q.find_max_priority    #=> ["banana", 3]
p q.find_max_priority    #=> ["banana", 3]
p q.delete_max           #=> "banana"
p q.find_max_priority    #=> ["melon", 2]
q.clear
p q.find_max_priority    #=> nil



923
924
925
 
# File 'lib/depq.rb', line 923

def find_max_priority
  loc = find_max_locator and [loc.value, loc.priority]
end

#find_min ⇒ Object Also known as: min, first

return the minimum value. This method returns nil if the queue is empty.

This method doesn’t delete the element from the queue.

q = Depq.new
p q.find_min     #=> nil
q.insert 3
q.insert 1
q.insert 2
p q.find_min     #=> 1
p q.find_min     #=> 1
p q.delete_min   #=> 1
p q.find_min     #=> 2



878
879
880
 
# File 'lib/depq.rb', line 878

def find_min
  loc = find_min_locator and loc.value
end

#find_min_locator ⇒ Object

return the locator for the minimum element. This method returns nil if the queue is empty.

This method doesn’t delete the element from the queue.

q = Depq.new
p q.find_min_locator     #=> nil
q.insert 3
q.insert 1
q.insert 2
p q.find_min_locator     #=> #<Depq::Locator: 1>
p q.find_min_locator     #=> #<Depq::Locator: 1>
p q.delete_min           #=> 1
p q.find_min_locator     #=> #<Depq::Locator: 2>



836
837
838
839
840
 
# File 'lib/depq.rb', line 836

def find_min_locator
  return nil if empty?
  use_min
  mode_call(:find_min_loc)
end

#find_min_priority ⇒ Object

return the minimum value with its priority. This method returns nil if the queue is empty.

This method doesn’t delete the element from the queue.

q = Depq.new
p q.find_min_priority    #=> nil
q.insert "durian", 1
q.insert "banana", 3
q.insert "melon", 2
p q.find_min_priority    #=> ["durian", 1]
p q.find_min_priority    #=> ["durian", 1]
p q.delete_min           #=> "durian"
p q.find_min_priority    #=> ["melon", 2]
q.clear
p q.find_min_priority    #=> nil



859
860
861
 
# File 'lib/depq.rb', line 859

def find_min_priority
  loc = find_min_locator and [loc.value, loc.priority]
end

#find_minmax ⇒ Object Also known as: minmax

returns the minimum and maximum value as a two-element array. If the queue is empty, [nil, nil] is returned.

q = Depq.new
p q.find_minmax  #=> [nil, nil]
q.insert 3
q.insert 1
q.insert 2
p q.find_minmax  #=> [1, 3]



974
975
976
977
 
# File 'lib/depq.rb', line 974

def find_minmax
  loc1, loc2 = self.find_minmax_locator
  [loc1 && loc1.value, loc2 && loc2.value]
end

#find_minmax_locator ⇒ Object

returns the locators for the minimum and maximum element as a two-element array. If the queue is empty, [nil, nil] is returned.

q = Depq.new
p q.find_minmax_locator #=> [nil, nil]
q.insert 3
q.insert 1
q.insert 2
p q.find_minmax_locator #=> [#<Depq::Locator: 1>, #<Depq::Locator: 3>]



958
959
960
961
962
 
# File 'lib/depq.rb', line 958

def find_minmax_locator
  return [nil, nil] if empty?
  use_minmax
  return mode_call(:find_minmax_loc)
end

#initialize_copy(obj) ⇒ Object

:nodoc:



573
574
575
576
577
578
579
580
581
582
583
584
585
586
 
# File 'lib/depq.rb', line 573

def initialize_copy(obj) # :nodoc:
  if defined? @ary
    @ary = @ary.dup
    n = @ary.length / ARY_SLICE_SIZE
    k = 0
    n.times {|i|
      loc1 = @ary[k]
      loc2 = Depq::Locator.allocate
      loc2.send(:initialize_in_queue, loc1.value, self, i)
      @ary[k] = loc2
      k += ARY_SLICE_SIZE
    }
  end
end

#insert(value, priority = value, subpriority = nil) ⇒ Object Also known as: add, put, enqueue, enq, <<

insert the value to the queue.

If priority is omitted, the value itself is used as the priority.

If subpriority is omitted or nil, totalcount is used for stability.

q = Depq.new
q.insert 3
q.insert 1
q.insert 2
p q.delete_min   #=> 1
p q.delete_min   #=> 2
p q.delete_min   #=> 3

q = Depq.new
q.insert 3, 10
q.insert 1, 20
q.insert 2, 30
p q.delete_min   #=> 3
p q.delete_min   #=> 1
p q.delete_min   #=> 2

This method returns a locator which locates the inserted element. It can be used to update the value and priority, or delete the element.

q = Depq.new
q.insert 3
loc1 = q.insert 1
loc2 = q.insert 2
q.insert 4
p q.delete_max           #=> 4
q.delete_locator loc1
loc2.update 8
p q.delete_max           #=> 8
p q.delete_max           #=> 3
p q.delete_max           #=> nil



791
792
793
794
 
# File 'lib/depq.rb', line 791

def insert(value, priority=value, subpriority=nil)
  loc = Locator.new(value, priority, subpriority)
  insert_locator(loc)
end

#insert_all(iter) ⇒ Object

insert all values in iter.

The argument, iter, should have each method.

This method returns nil.

q = Depq.new
q.insert_all [3,1,2]
p q.delete_min   #=> 1
p q.delete_min   #=> 2
p q.delete_min   #=> 3
p q.delete_min   #=> nil



814
815
816
817
818
819
 
# File 'lib/depq.rb', line 814

def insert_all(iter)
  iter.each {|v|
    insert v
  }
  nil
end

#insert_locator(loc) ⇒ Object

insert the locator to the queue.

If loc.subpriority is nil, totalcount is used for stability.

The locator should not already be inserted in a queue.

q = Depq.new
loc = Depq::Locator.new(1)
q.insert_locator loc
p q.delete_min           #=> 1



744
745
746
747
748
749
750
751
752
 
# File 'lib/depq.rb', line 744

def insert_locator(loc)
  priority = loc.priority
  subpriority = loc.subpriority || default_subpriority
  i = self.size
  loc.send(:internal_inserted, self, i)
  set_entry(i, loc, priority, subpriority)
  @totalcount += 1
  loc
end

#inspect ⇒ Object

:nodoc:



588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
 
# File 'lib/depq.rb', line 588

def inspect # :nodoc:
  unless defined? @cmp
    return "\#<#{self.class}: uninitialized>"
  end
  a = []
  each_entry {|loc, priority|
    value = loc.value
    s = value.inspect
    if value != priority
      s << ":" << priority.inspect
    end
    a << s
  }
  "\#<#{self.class}: #{a.join(' ')}>"
end

#pretty_print(q) ⇒ Object

:nodoc:



604
605
606
607
608
609
610
611
612
613
614
615
616
 
# File 'lib/depq.rb', line 604

def pretty_print(q) # :nodoc:
  q.object_group(self) {
    each_entry {|loc, priority|
      q.breakable
      value = loc.value
      q.pp value
      if value != priority
        q.text ':'
        q.pp priority
      end
    }
  }
end

#replace_max(value, priority = value, subpriority = nil) ⇒ Object

replaces the maximum element.

If priority is not given, value is used.

If subpriority is not given or nil, totalcount is used.

This is virtually same as delete_max and insert except the locator is reused. This method increment totalcount.

q = Depq.new
q.insert 1
q.insert 4
q.insert 3
p q.max           #=> 4
q.replace_max(2)
p q.delete_max    #=> 3
p q.delete_max    #=> 2
p q.delete_max    #=> 1
p q.delete_max    #=> nil



1248
1249
1250
1251
1252
1253
1254
 
# File 'lib/depq.rb', line 1248

def replace_max(value, priority=value, subpriority=nil)
  subpriority ||= @totalcount
  @totalcount += 1
  loc = find_max_locator
  loc.update(value, priority, subpriority)
  loc
end

#replace_min(value, priority = value, subpriority = nil) ⇒ Object

replaces the minimum element.

If priority is not given, value is used.

If subpriority is not given or nil, totalcount is used.

This is virtually same as delete_min and insert except the locator is reused. This method increment totalcount.

q = Depq.new
q.insert 2
q.insert 4
q.insert 3
p q.min           #=> 2
q.replace_min(5)
p q.delete_min    #=> 3
p q.delete_min    #=> 4
p q.delete_min    #=> 5
p q.delete_min    #=> nil



1220
1221
1222
1223
1224
1225
1226
 
# File 'lib/depq.rb', line 1220

def replace_min(value, priority=value, subpriority=nil)
  subpriority ||= @totalcount
  @totalcount += 1
  loc = find_min_locator
  loc.update(value, priority, subpriority)
  loc
end

#size ⇒ Object Also known as: length

returns the number of elements in the queue.

q = Depq.new
p q.size         #=> 0
q.insert 1
p q.size         #=> 1
q.insert 1
p q.size         #=> 2
q.delete_min
p q.size         #=> 1
q.delete_min
p q.size         #=> 0



662
663
664
 
# File 'lib/depq.rb', line 662

def size
  @ary.size / ARY_SLICE_SIZE
end

#totalcount ⇒ Object

returns the total number of elements inserted for the queue, ever.

The result is monotonically increased.

q = Depq.new
p [q.size, q.totalcount]        #=> [0, 0]
q.insert 1
p [q.size, q.totalcount]        #=> [1, 1]
q.insert 2
p [q.size, q.totalcount]        #=> [2, 2]
q.delete_min
p [q.size, q.totalcount]        #=> [1, 2]
q.insert 4
p [q.size, q.totalcount]        #=> [2, 3]
q.insert 3
p [q.size, q.totalcount]        #=> [3, 4]
q.insert 0
p [q.size, q.totalcount]        #=> [4, 5]
q.delete_min
p [q.size, q.totalcount]        #=> [3, 5]
q.insert 2
p [q.size, q.totalcount]        #=> [4, 6]



690
691
692
 
# File 'lib/depq.rb', line 690

def totalcount
  @totalcount
end