kdt 0.2.2 → 0.2.3
raw patch · 7 files changed
+69/−40 lines, 7 filesdep +heapdep −pqueuedep ~MonadRandomdep ~QuickCheckdep ~basePVP ok
version bump matches the API change (PVP)
Dependencies added: heap
Dependencies removed: pqueue
Dependency ranges changed: MonadRandom, QuickCheck, base, criterion, deepseq, mersenne-random-pure64
API changes (from Hackage documentation)
Files
- app-src/Benchmarks/KDTBenchmark.hs +13/−6
- app-src/Tests/DynamicTest.hs +5/−2
- app-src/Tests/StaticTest.hs +5/−2
- changelog.md +3/−0
- kdt.cabal +17/−17
- lib-src/Data/KdMap/Dynamic.hs +7/−3
- lib-src/Data/KdMap/Static.hs +19/−10
app-src/Benchmarks/KDTBenchmark.hs view
@@ -1,12 +1,16 @@+{-# LANGUAGE FlexibleContexts #-}+ import Data.Point2d import Data.KdTree.Static as KDT import Data.KdTree.Dynamic as DKDT +import Control.DeepSeq import Control.Monad import qualified Control.Monad.Random as CMR import Criterion.Main import Data.List-import qualified Data.PQueue.Prio.Max as Q+import Data.Maybe+import qualified Data.Heap as Q import System.Random.Mersenne.Pure64 zeroOnePointSampler :: CMR.Rand PureMT Point2d@@ -46,12 +50,15 @@ -- knn implemented with priority queue kNearestNeighborsLinear :: [Point2d] -> Int -> Point2d -> [Point2d]-kNearestNeighborsLinear ps k query = reverse $ map snd $ Q.toList $ foldl' f Q.empty ps+kNearestNeighborsLinear ps k query =+ reverse $ map snd $ Q.toAscList $ foldl' f (Q.empty :: Q.MaxPrioHeap Double Point2d) ps where f q p = let insertBounded queue dist x- | Q.size queue < k = Q.insert dist x queue- | otherwise = if dist < fst (Q.findMax queue)- then Q.insert dist x $ Q.deleteMax queue- else queue+ | Q.size queue < k = Q.insert (dist, x) queue+ | otherwise =+ let ((farthestDist, _), rest) = fromJust $ Q.view queue+ in if dist < farthestDist+ then Q.insert (dist, x) rest+ else queue in insertBounded q (distSqr2d query p) p rangeLinear :: Point2d -> Point2d -> [Point2d] -> [Point2d]
app-src/Tests/DynamicTest.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE TemplateHaskell #-}+{-# LANGUAGE TemplateHaskell, CPP #-} import qualified Data.KdMap.Static as KDM import Data.KdMap.Dynamic@@ -9,8 +9,11 @@ import Data.Point2d import System.Exit import Test.QuickCheck--- This import only required for QuickCheck <2.7++#if MIN_VERSION_QuickCheck(2,7,0)+#else import Test.QuickCheck.All+#endif testElements :: [p] -> [(p, Int)] testElements ps = zip ps [1 ..]
app-src/Tests/StaticTest.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE TemplateHaskell #-}+{-# LANGUAGE TemplateHaskell, CPP #-} import Data.KdMap.Static as KDM @@ -8,8 +8,11 @@ import Data.Point2d import System.Exit import Test.QuickCheck--- This import only required for QuickCheck <2.7++#if MIN_VERSION_QuickCheck(2,7,0)+#else import Test.QuickCheck.All+#endif testElements :: [p] -> [(p, Int)] testElements ps = zip ps [0 ..]
changelog.md view
@@ -1,3 +1,6 @@+# 0.2.3+* For internal priority queue implementation, use the heap library instead of pqueue library in order to build on ghc 7.10.+ # 0.2.2 * Relax lower version bound on QuickCheck to 2.5.
kdt.cabal view
@@ -2,7 +2,7 @@ -- see http://haskell.org/cabal/users-guide/ name: kdt-version: 0.2.2+version: 0.2.3 synopsis: Fast and flexible k-d trees for various types of point queries. description: This package includes static and dynamic versions of k-d trees, as well as \"Map\" variants that store data at each point in the@@ -35,9 +35,9 @@ other-extensions: DeriveGeneric, TemplateHaskell ghc-options: -Wall -O3 ghc-prof-options: -Wall -O3 -fprof-auto- build-depends: base >=4.6 && <4.8,- deepseq >=1.3 && <1.4,- pqueue >=1.2.1 && <1.3,+ build-depends: base >=4.6 && <5,+ deepseq >=1.3,+ heap >=1.0.0, deepseq-generics >=0.1.1.1 hs-source-dirs: lib-src default-language: Haskell2010@@ -48,10 +48,10 @@ other-modules: Data.Point2d hs-source-dirs: app-src ghc-options: -Wall -O3- build-depends: base >=4.6 && <4.8,+ build-depends: base >=4.6 && <5, kdt -any,- QuickCheck >=2.5 && <2.8,- deepseq >=1.3 && <1.4,+ QuickCheck >=2.5,+ deepseq >=1.3, deepseq-generics >=0.1.1.1 default-language: Haskell2010 @@ -61,10 +61,10 @@ other-modules: Data.Point2d hs-source-dirs: app-src ghc-options: -Wall -O3- build-depends: base >=4.6 && <4.8,+ build-depends: base >=4.6 && <5, kdt -any,- QuickCheck >=2.5 && <2.8,- deepseq >=1.3 && <1.4,+ QuickCheck >=2.5,+ deepseq >=1.3, deepseq-generics >=0.1.1.1 default-language: Haskell2010 @@ -76,13 +76,13 @@ ghc-options: -Wall -O3 ghc-prof-options: -Wall -O3 -fprof-auto "-with-rtsopts=-p"- build-depends: base >=4.6 && <4.8,+ build-depends: base >=4.6 && <5, kdt -any,- MonadRandom >= 0.1.12 && <0.4,- mersenne-random-pure64 >=0.2.0.4 && <0.3,- criterion >= 1.0.0.0 && <1.1,- pqueue >=1.2.1 && <1.3,- QuickCheck >=2.5 && <2.8,- deepseq >=1.3 && <1.4,+ MonadRandom >= 0.1.12,+ mersenne-random-pure64 >=0.2.0.4,+ criterion >=1.0.0.0,+ QuickCheck >=2.5,+ heap >=1.0.0,+ deepseq >=1.3, deepseq-generics >=0.1.1.1 default-language: Haskell2010
lib-src/Data/KdMap/Dynamic.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE DeriveGeneric, CPP #-} module Data.KdMap.Dynamic ( -- * Usage@@ -40,13 +40,17 @@ import Prelude hiding (null) +#if MIN_VERSION_base(4,8,0)+#else import Control.Applicative hiding (empty)-import Data.Bits import Data.Foldable+import Data.Traversable+#endif++import Data.Bits import Data.Function import Data.List as L hiding (insert, null) import qualified Data.List (null)-import Data.Traversable import Control.DeepSeq import Control.DeepSeq.Generics (genericRnf)
lib-src/Data/KdMap/Static.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE DeriveGeneric, CPP, FlexibleContexts #-} module Data.KdMap.Static ( -- * Usage@@ -43,13 +43,19 @@ import GHC.Generics import Control.Applicative hiding (empty)++#if MIN_VERSION_base(4,8,0)+import Data.Foldable hiding (null)+#else import Data.Foldable+import Data.Traversable+#endif+ import Prelude hiding (null) import qualified Data.List as L import Data.Maybe import Data.Ord-import qualified Data.PQueue.Prio.Max as Q-import Data.Traversable+import qualified Data.Heap as Q -- $usage --@@ -379,23 +385,26 @@ -- neighbors on a structure with /n/ data points. kNearest :: Real a => KdMap a p v -> Int -> p -> [(p, v)] kNearest (KdMap pointAsList distSqr t _) numNeighbors query =- reverse $ map snd $ Q.toList $ go (cycle $ pointAsList query) Q.empty t+ reverse $ map snd $ Q.toAscList $ go (cycle $ pointAsList query)+ (Q.empty :: Q.MaxPrioHeap a (p,v)) t where- -- go :: [Double] -> Q.MaxPQueue Double (p, d) -> TreeNode p d -> KQueue p d+ -- go :: [a] -> Q.MaxPrioHeap a (p, v) -> TreeNode a p v -> Q.MaxPrioHeap a (p, v) go [] _ _ = error "kNearest.go: no empty lists allowed!" go _ q Empty = q go (queryAxisValue : qvs) q (TreeNode left (k, v) nodeAxisVal right) = let insertBounded queue dist x- | Q.size queue < numNeighbors = Q.insert dist x queue- | otherwise = if dist < fst (Q.findMax queue)- then Q.insert dist x $ Q.deleteMax queue- else queue+ | Q.size queue < numNeighbors = Q.insert (dist, x) queue+ | otherwise = let ((farthestDist, _), rest) = fromJust $ Q.view queue+ in if dist < farthestDist+ then Q.insert (dist, x) rest+ else queue q' = insertBounded q (distSqr k query) (k, v) kNear queue onsideSubtree offsideSubtree = let queue' = go qvs queue onsideSubtree checkOffsideTree = Q.size queue' < numNeighbors ||- (queryAxisValue - nodeAxisVal)^(2 :: Int) < fst (Q.findMax queue')+ (queryAxisValue - nodeAxisVal)^(2 :: Int) <+ (fst . fst) (fromJust $ Q.view queue') in if checkOffsideTree then go qvs queue' offsideSubtree else queue'