psqueues 0.1.0.0 → 0.1.0.1

raw patch · 2 files changed

+44/−17 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG +5/−0
• psqueues.cabal +39/−17

@@ -0,0 +1,5 @@+- 0.1.0.1+    * Extend cabal description, include CHANGELOG++- 0.1.0.0+    * First release: <https://medium.com/@bttr/announcing-psqueues-8a0fe9fe939>

@@ -1,5 +1,5 @@ name: psqueues-version: 0.1.0.0+version: 0.1.0.1 license: BSD3 license-file: LICENSE maintainer: haskell@better.com@@ -7,29 +7,51 @@ synopsis: Pure priority search queues category: Data Structures description:-    A priority search queue manages a set of triples of the form-    @(key, priority, value)@ and allows for efficient lookup by key, and-    efficient lookup and removal of the element with minimal priority. This-    package contains three, performant implementations of priority search-    queues, which differ in the requirements on the type of keys.+    The psqueues package provides+    <http://en.wikipedia.org/wiki/Priority_queue Priority Search Queues> in+    three different flavors.     .-    * 'IntPSQ's are the most efficient structure, but require the keys to be-      of type 'Int'.+    * @OrdPSQ k p v@, which uses the @Ord k@ instance to provide fast insertion,+    deletion and lookup. This implementation is based on Ralf Hinze's+    <http://citeseer.ist.psu.edu/hinze01simple.html A Simple Implementation Technique for Priority Search Queues>.+    Hence, it is similar to the+    <http://hackage.haskell.org/package/PSQueue PSQueue> library, although it is+    considerably faster and provides a slightly different API.     .-    * 'OrdPSQ's just require the key to implement the `Ord` typeclass, but are-      the slowest structures of the three.+    * @IntPSQ p v@ is a far more efficient implementation. It fixes the key type+   to @Int@ and uses a <http://en.wikipedia.org/wiki/Radix_tree radix tree>+   (like @IntMap@) with an additional min-heap property.     .-    * 'HashPSQ's require the key to implement both the 'Ord' and 'Hashable'-      typeclasses. They use an 'IntMap' over the hash of the keys combined-      with a 'OrdPSQ' to manage collisions. Except for keys with a very fast-      comparison and small smaps 'HashPSQ's are faster than 'OrdPSQ's.+    * @HashPSQ k p v@ is a fairly straightforward extension of @IntPSQ@: it+    simply uses the keys' hashes as indices in the @IntPSQ@. If there are any+    hash collisions, it uses an @OrdPSQ@ to resolve those. The performance of+    this implementation is comparable to that of @IntPSQ@, but it is more widely+    applicable since the keys are not restricted to @Int@, but rather to any+    @Hashable@ datatype.     .-    Typical use cases for priority search queues are LRU caches, where the-    priority is the time of the last access, and timeout management, where the-    priority is the time at which the timeout should trigger.+    Each of the three implementations provides the same API, so they can be used+    interchangeably. The benchmarks show how they perform relative to one+    another, and also compared to the other Priority Search Queue+    implementations on Hackage:+    <http://hackage.haskell.org/package/PSQueue PSQueue>+    and+    <http://hackage.haskell.org/package/fingertree-psqueue fingertree-psqueue>.+    .+    <<http://i.imgur.com/KmbDKR6.png>>+    .+    <<http://i.imgur.com/ClT181D.png>>+    .+    Typical applications of Priority Search Queues include:+    .+    * Caches, and more specifically LRU Caches;+    .+    * Schedulers;+    .+    * Pathfinding algorithms, such as Dijkstra's and A*. build-type: Simple cabal-version:  >=1.8 extra-source-files:+    CHANGELOG  source-repository head     type:     git