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"



432
433
434
435
436
437
438
 
# File 'lib/depq.rb', line 432

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



1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
 
# File 'lib/depq.rb', line 1527

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



1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
 
# File 'lib/depq.rb', line 1420

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) 


1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
 
# File 'lib/depq.rb', line 1309

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) 


1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
 
# File 'lib/depq.rb', line 1364

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



684
685
686
687
688
 
# File 'lib/depq.rb', line 684

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



604
605
606
607
608
609
610
 
# File 'lib/depq.rb', line 604

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



967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
 
# File 'lib/depq.rb', line 967

def delete_locator(loc)
  check_locator(loc)
  index = loc.send(:index)
  if @heapsize <= index
    _, priority, subpriority = get_entry(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



1108
1109
1110
1111
 
# File 'lib/depq.rb', line 1108

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



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

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



1089
1090
1091
1092
 
# File 'lib/depq.rb', line 1089

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



1044
1045
1046
1047
 
# File 'lib/depq.rb', line 1044

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



1002
1003
1004
1005
1006
1007
1008
 
# File 'lib/depq.rb', line 1002

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



1025
1026
1027
1028
 
# File 'lib/depq.rb', line 1025

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



1171
1172
1173
1174
 
# File 'lib/depq.rb', line 1171

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



1129
1130
1131
1132
1133
 
# File 'lib/depq.rb', line 1129

def delete_unspecified_locator
  return nil if empty?
  loc, _ = get_entry(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



1151
1152
1153
1154
 
# File 'lib/depq.rb', line 1151

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
}



1287
1288
1289
1290
1291
1292
 
# File 'lib/depq.rb', line 1287

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>
}



1245
1246
1247
1248
1249
1250
 
# File 'lib/depq.rb', line 1245

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]



1267
1268
1269
1270
1271
1272
 
# File 'lib/depq.rb', line 1267

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) 


621
622
623
 
# File 'lib/depq.rb', line 621

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



918
919
920
 
# File 'lib/depq.rb', line 918

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>



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

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



899
900
901
 
# File 'lib/depq.rb', line 899

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



854
855
856
 
# File 'lib/depq.rb', line 854

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>



812
813
814
815
816
 
# File 'lib/depq.rb', line 812

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



835
836
837
 
# File 'lib/depq.rb', line 835

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]



950
951
952
953
 
# File 'lib/depq.rb', line 950

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>]



934
935
936
937
938
 
# File 'lib/depq.rb', line 934

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

#initialize_copy(obj) ⇒ Object

:nodoc:



549
550
551
552
553
554
555
556
557
558
559
560
561
562
 
# File 'lib/depq.rb', line 549

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



767
768
769
770
 
# File 'lib/depq.rb', line 767

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



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

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



720
721
722
723
724
725
726
727
728
 
# File 'lib/depq.rb', line 720

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:



564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
 
# File 'lib/depq.rb', line 564

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:



580
581
582
583
584
585
586
587
588
589
590
591
592
 
# File 'lib/depq.rb', line 580

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



1224
1225
1226
1227
1228
1229
1230
 
# File 'lib/depq.rb', line 1224

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



1196
1197
1198
1199
1200
1201
1202
 
# File 'lib/depq.rb', line 1196

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



638
639
640
 
# File 'lib/depq.rb', line 638

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]



666
667
668
 
# File 'lib/depq.rb', line 666

def totalcount
  @totalcount
end