| 1 |
Source: haskell-psqueues |
| 2 |
Maintainer: Debian Haskell Group <[email protected]> |
| 3 |
Uploaders: |
| 4 |
Ilias Tsitsimpis <[email protected]>, |
| 5 |
Priority: optional |
| 6 |
Section: haskell |
| 7 |
Rules-Requires-Root: no |
| 8 |
Build-Depends: |
| 9 |
dh-sequence-haskell, |
| 10 |
debhelper-compat (= 13), |
| 11 |
ghc (>= 9.4), |
| 12 |
ghc-prof, |
| 13 |
haskell-devscripts (>= 0.13), |
| 14 |
libghc-hashable-dev (>= 1.1.2.3), |
| 15 |
libghc-hashable-dev (<< 1.6), |
| 16 |
libghc-hashable-prof, |
| 17 |
Build-Depends-Indep: |
| 18 |
ghc-doc, |
| 19 |
libghc-hashable-doc, |
| 20 |
Standards-Version: 4.7.0 |
| 21 |
Homepage: https://hackage.haskell.org/package/psqueues |
| 22 |
Vcs-Browser: https://salsa.debian.org/haskell-team/DHG_packages/tree/master/p/haskell-psqueues |
| 23 |
Vcs-Git: https://salsa.debian.org/haskell-team/DHG_packages.git [p/haskell-psqueues] |
| 24 |
X-Description: Pure priority search queues |
| 25 |
This package provides Priority Search Queues in three different flavors. |
| 26 |
. |
| 27 |
* OrdPSQ k p v, which uses the Ord k instance to provide fast insertion, |
| 28 |
deletion and lookup. This implementation is based on Ralf Hinze's "A Simple |
| 29 |
Implementation Technique for Priority Search Queues". Hence, it is similar to |
| 30 |
the PSQueue library, although it is considerably faster and provides a |
| 31 |
slightly different API. |
| 32 |
. |
| 33 |
* IntPSQ p v is a far more efficient implementation. It fixes the key type |
| 34 |
to Int and uses a radix tree (like IntMap) with an additional min-heap |
| 35 |
property. |
| 36 |
. |
| 37 |
* HashPSQ k p v is a fairly straightforward extension of IntPSQ: it |
| 38 |
simply uses the keys' hashes as indices in the IntPSQ. If there are any hash |
| 39 |
collisions, it uses an OrdPSQ to resolve those. The performance of this |
| 40 |
implementation is comparable to that of IntPSQ, but it is more widely |
| 41 |
applicable since the keys are not restricted to Int, but rather to any |
| 42 |
Hashable datatype. |
| 43 |
. |
| 44 |
Each of the three implementations provides the same API, so they can be used |
| 45 |
interchangeably. |
| 46 |
. |
| 47 |
Typical applications of Priority Search Queues include: |
| 48 |
. |
| 49 |
* Caches, and more specifically LRU Caches; |
| 50 |
. |
| 51 |
* Schedulers; |
| 52 |
. |
| 53 |
* Pathfinding algorithms, such as Dijkstra's and A*. |
| 54 |
|
| 55 |
Package: libghc-psqueues-dev |
| 56 |
Architecture: any |
| 57 |
Depends: |
| 58 |
${haskell:Depends}, |
| 59 |
${misc:Depends}, |
| 60 |
${shlibs:Depends}, |
| 61 |
Recommends: |
| 62 |
${haskell:Recommends}, |
| 63 |
Suggests: |
| 64 |
${haskell:Suggests}, |
| 65 |
Conflicts: |
| 66 |
${haskell:Conflicts}, |
| 67 |
Provides: |
| 68 |
${haskell:Provides}, |
| 69 |
Description: ${haskell:ShortDescription}${haskell:ShortBlurb} |
| 70 |
${haskell:LongDescription} |
| 71 |
. |
| 72 |
${haskell:Blurb} |
| 73 |
|
| 74 |
Package: libghc-psqueues-prof |
| 75 |
Architecture: any |
| 76 |
Depends: |
| 77 |
${haskell:Depends}, |
| 78 |
${misc:Depends}, |
| 79 |
Recommends: |
| 80 |
${haskell:Recommends}, |
| 81 |
Suggests: |
| 82 |
${haskell:Suggests}, |
| 83 |
Conflicts: |
| 84 |
${haskell:Conflicts}, |
| 85 |
Provides: |
| 86 |
${haskell:Provides}, |
| 87 |
Description: ${haskell:ShortDescription}${haskell:ShortBlurb} |
| 88 |
${haskell:LongDescription} |
| 89 |
. |
| 90 |
${haskell:Blurb} |
| 91 |
|
| 92 |
Package: libghc-psqueues-doc |
| 93 |
Architecture: all |
| 94 |
Section: doc |
| 95 |
Depends: |
| 96 |
${haskell:Depends}, |
| 97 |
${misc:Depends}, |
| 98 |
Recommends: |
| 99 |
${haskell:Recommends}, |
| 100 |
Suggests: |
| 101 |
${haskell:Suggests}, |
| 102 |
Conflicts: |
| 103 |
${haskell:Conflicts}, |
| 104 |
Description: ${haskell:ShortDescription}${haskell:ShortBlurb} |
| 105 |
${haskell:LongDescription} |
| 106 |
. |
| 107 |
${haskell:Blurb} |