From adf753775394254435ccc6f6e0d029bb515aa093 Mon Sep 17 00:00:00 2001 From: Sergei Trofimovich Date: Tue, 19 Jan 2016 21:56:02 +0000 Subject: dev-haskell/psqueues: new package, a depend of dev-haskell/http2 Pure priority search queues. Package-Manager: portage-2.2.27 --- dev-haskell/psqueues/Manifest | 1 + dev-haskell/psqueues/metadata.xml | 48 ++++++++++++++++++++++++++++ dev-haskell/psqueues/psqueues-0.2.0.3.ebuild | 32 +++++++++++++++++++ 3 files changed, 81 insertions(+) create mode 100644 dev-haskell/psqueues/Manifest create mode 100644 dev-haskell/psqueues/metadata.xml create mode 100644 dev-haskell/psqueues/psqueues-0.2.0.3.ebuild (limited to 'dev-haskell') diff --git a/dev-haskell/psqueues/Manifest b/dev-haskell/psqueues/Manifest new file mode 100644 index 000000000000..eb679604c661 --- /dev/null +++ b/dev-haskell/psqueues/Manifest @@ -0,0 +1 @@ +DIST psqueues-0.2.0.3.tar.gz 23782 SHA256 ac8a60de9979f80948d0becfb35cdafe7e1fdfce062c0468e4e2abced9a85c69 SHA512 2af3fef2786ce61289f806fd483d1995a29f1a7f85eb918ae69e4873450c4b19e8c76f0e6f86f9e6fe7065b9cfb4672f48af2366bc2a537ed42b0e5dacb8a5a0 WHIRLPOOL 82d621ac9b0d546ccac42f789ffd2a5cd456e4cc89c37c68016d675f9716951af07a26919b576c4767d4d9edfea28d681c2eb0635f0e2b10be35cd2e020a75a1 diff --git a/dev-haskell/psqueues/metadata.xml b/dev-haskell/psqueues/metadata.xml new file mode 100644 index 000000000000..d4c0b904bde1 --- /dev/null +++ b/dev-haskell/psqueues/metadata.xml @@ -0,0 +1,48 @@ + + + + haskell + + The psqueues package provides + <http://en.wikipedia.org/wiki/Priority_queue Priority Search Queues> in + three different flavors. + + * @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. + + * @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 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. + + 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*. + + diff --git a/dev-haskell/psqueues/psqueues-0.2.0.3.ebuild b/dev-haskell/psqueues/psqueues-0.2.0.3.ebuild new file mode 100644 index 000000000000..2602962a53f5 --- /dev/null +++ b/dev-haskell/psqueues/psqueues-0.2.0.3.ebuild @@ -0,0 +1,32 @@ +# Copyright 1999-2015 Gentoo Foundation +# Distributed under the terms of the GNU General Public License v2 +# $Id$ + +EAPI=5 + +# ebuild generated by hackport 0.4.6.9999 + +CABAL_FEATURES="lib profile haddock hoogle hscolour test-suite" +inherit haskell-cabal + +DESCRIPTION="Pure priority search queues" +HOMEPAGE="http://hackage.haskell.org/package/psqueues" +SRC_URI="mirror://hackage/packages/archive/${PN}/${PV}/${P}.tar.gz" + +LICENSE="BSD" +SLOT="0/${PV}" +KEYWORDS="~amd64 ~x86" +IUSE="" + +RDEPEND=">=dev-haskell/hashable-1.2.1:=[profile?] =dev-lang/ghc-7.4.1:= +" +DEPEND="${RDEPEND} + >=dev-haskell/cabal-1.8 + test? ( >=dev-haskell/hunit-1.2 =dev-haskell/quickcheck-2.7 =dev-haskell/test-framework-0.8 =dev-haskell/test-framework-hunit-0.3 =dev-haskell/test-framework-quickcheck2-0.3