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"



429
430
431
432
433
434
435
436
 
# File 'lib/depq.rb', line 429

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

Class Method Details

.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



1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
 
# File 'lib/depq.rb', line 1404

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]



1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
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
 
# File 'lib/depq.rb', line 1297

def Depq.nlargest(n, iter)
  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]



1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
 
# File 'lib/depq.rb', line 1350

def Depq.nsmallest(n, iter)
  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



672
673
674
675
676
 
# File 'lib/depq.rb', line 672

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



592
593
594
595
596
597
598
 
# File 'lib/depq.rb', line 592

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



953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
 
# File 'lib/depq.rb', line 953

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_entry(last)
    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



1096
1097
1098
1099
 
# File 'lib/depq.rb', line 1096

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



1053
1054
1055
1056
1057
1058
1059
 
# File 'lib/depq.rb', line 1053

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



1076
1077
1078
1079
1080
 
# File 'lib/depq.rb', line 1076

def delete_max_priority
  loc = delete_max_locator
  return nil unless loc
  [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



1031
1032
1033
1034
 
# File 'lib/depq.rb', line 1031

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



988
989
990
991
992
993
994
 
# File 'lib/depq.rb', line 988

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



1011
1012
1013
1014
1015
 
# File 'lib/depq.rb', line 1011

def delete_min_priority
  loc = delete_min_locator
  return nil unless loc
  [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



1160
1161
1162
1163
1164
 
# File 'lib/depq.rb', line 1160

def delete_unspecified
  loc = delete_unspecified_locator
  return nil unless loc
  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



1117
1118
1119
1120
1121
 
# File 'lib/depq.rb', line 1117

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



1139
1140
1141
1142
1143
 
# File 'lib/depq.rb', line 1139

def delete_unspecified_priority
  loc = delete_unspecified_locator
  return nil unless loc
  [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
}



1275
1276
1277
1278
1279
1280
 
# File 'lib/depq.rb', line 1275

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



1235
1236
1237
1238
1239
1240
 
# File 'lib/depq.rb', line 1235

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

#each_with_priority ⇒ Object

iterate over the values and priorities in the queue.

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]



1255
1256
1257
1258
1259
1260
 
# File 'lib/depq.rb', line 1255

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) 


609
610
611
 
# File 'lib/depq.rb', line 609

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



904
905
906
 
# File 'lib/depq.rb', line 904

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>



862
863
864
865
866
 
# File 'lib/depq.rb', line 862

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



885
886
887
 
# File 'lib/depq.rb', line 885

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



840
841
842
 
# File 'lib/depq.rb', line 840

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>



798
799
800
801
802
 
# File 'lib/depq.rb', line 798

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



821
822
823
 
# File 'lib/depq.rb', line 821

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]



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

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



920
921
922
923
924
 
# File 'lib/depq.rb', line 920

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

#initialize_copy(obj) ⇒ Object

:nodoc:



538
539
540
541
542
543
544
545
546
547
548
549
550
 
# File 'lib/depq.rb', line 538

def initialize_copy(obj) # :nodoc:
  if defined? @ary
    @ary = @ary.dup
    0.step(@ary.length-1, ARY_SLICE_SIZE) {|k|
      i = k / ARY_SLICE_SIZE
      loc1 = @ary[k]
      priority = @ary[k+1]
      loc2 = Depq::Locator.new(loc1.value, priority)
      loc2.send(:internal_inserted, self, i)
      @ary[k] = loc2
    }
  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



753
754
755
756
 
# File 'lib/depq.rb', line 753

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



776
777
778
779
780
781
 
# File 'lib/depq.rb', line 776

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



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

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

#inspect ⇒ Object

:nodoc:



552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
 
# File 'lib/depq.rb', line 552

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:



568
569
570
571
572
573
574
575
576
577
578
579
580
 
# File 'lib/depq.rb', line 568

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



1214
1215
1216
1217
1218
1219
1220
 
# File 'lib/depq.rb', line 1214

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



1186
1187
1188
1189
1190
1191
1192
 
# File 'lib/depq.rb', line 1186

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



626
627
628
 
# File 'lib/depq.rb', line 626

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]



654
655
656
 
# File 'lib/depq.rb', line 654

def totalcount
  @totalcount
end