README

= 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 update - you can change the priority of inserted values (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
* several utility methods: nlargest, nsmallest, merge, astar_search

== Install

  gem install depq

== Links

* ((<source repository on github|URL:http://github.com/akr/depq>))
* ((<depq on rubygems.org|URL:http://rubygems.org/gems/depq>))

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

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.

== Author

Tanaka Akira <akr@fsij.org>

== License

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:

 1. Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.
 2. Redistributions in binary form must reproduce the above
    copyright notice, this list of conditions and the following
    disclaimer in the documentation and/or other materials provided
    with the distribution.
 3. The name of the author may not be used to endorse or promote
    products derived from this software without specific prior
    written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

(The modified BSD licence)