kdt 0.2.5 → 0.2.6
raw patch · 4 files changed
+64/−59 lines, 4 filesdep +containersPVP ok
version bump matches the API change (PVP)
Dependencies added: containers
API changes (from Hackage documentation)
Files
- app-src/Tests/DynamicTest.hs +30/−27
- app-src/Tests/StaticTest.hs +28/−31
- changelog.md +3/−0
- kdt.cabal +3/−1
app-src/Tests/DynamicTest.hs view
@@ -3,11 +3,13 @@ import qualified Data.KdMap.Static as KDM import Data.KdMap.Dynamic -import Control.Monad+import Control.Monad (unless) import Data.Bits import Data.List+import qualified Data.Set as Set+import Data.Set (isSubsetOf) import Data.Point2d-import System.Exit+import System.Exit (exitFailure) import Test.QuickCheck #if MIN_VERSION_QuickCheck(2,7,0)@@ -15,6 +17,8 @@ import Test.QuickCheck.All #endif +import Tests.TestHelpers (nearestsLinear, withinDistanceOfKthNearest)+ testElements :: [p] -> [(p, Int)] testElements ps = zip ps [1 ..] @@ -45,38 +49,35 @@ prop_validNumElements :: [Point2d] -> Bool prop_validNumElements = checkNumElements pointAsList2d distSqr2d -checkNearestEqualToBatch :: (Eq p, Real a) => PointAsListFn a p ->- SquaredDistanceFn a p ->- ([p], p) ->- Bool-checkNearestEqualToBatch p2l d2 (ps, query) =- let kdt = KDM.buildWithDist p2l d2 $ testElements ps- kdtAnswer = KDM.nearest kdt query- dkdt = batchInsert (emptyWithDist p2l d2) $ testElements ps+checkNearestConsistentWithLinear :: (Eq p, Real a) => PointAsListFn a p ->+ SquaredDistanceFn a p ->+ ([p], p) ->+ Bool+checkNearestConsistentWithLinear p2l d2 (ps, query) =+ let dkdt = batchInsert (emptyWithDist p2l d2) $ testElements ps dkdtAnswer = nearest dkdt query- in dkdtAnswer == kdtAnswer+ in dkdtAnswer `elem` nearestsLinear p2l (testElements ps) query -prop_nearestEqualToBatch :: Point2d -> Property-prop_nearestEqualToBatch query =+prop_nearestConsistentWithLinear :: Point2d -> Property+prop_nearestConsistentWithLinear query = forAll (listOf1 arbitrary) $ \xs ->- checkNearestEqualToBatch pointAsList2d distSqr2d (xs, query)+ checkNearestConsistentWithLinear pointAsList2d distSqr2d (xs, query) -checkKNearestEqualToBatch :: (Eq p, Real a) => PointAsListFn a p ->- SquaredDistanceFn a p ->- ([p], Int, p) ->- Bool-checkKNearestEqualToBatch p2l d2 (ps, k, query) =- let kdt = KDM.buildWithDist p2l d2 $ testElements ps- kdtAnswer = KDM.kNearest kdt k query- dkdt = batchInsert (emptyWithDist p2l d2) $ testElements ps+checkKNearestConsistentWithLinear :: (Ord p, Real a) => PointAsListFn a p ->+ SquaredDistanceFn a p ->+ ([p], Int, p) ->+ Bool+checkKNearestConsistentWithLinear p2l d2 (ps, k, query) =+ let dkdt = batchInsert (emptyWithDist p2l d2) $ testElements ps dkdtAnswer = kNearest dkdt k query- in dkdtAnswer == kdtAnswer+ possibleNearest = withinDistanceOfKthNearest p2l (testElements ps) query k+ in Set.fromList dkdtAnswer `isSubsetOf` Set.fromList possibleNearest -prop_kNearestEqualToBatch :: Point2d -> Property-prop_kNearestEqualToBatch query =+prop_kNearestConsistentWithLinear :: Point2d -> Property+prop_kNearestConsistentWithLinear query = forAll (listOf1 arbitrary) $ \xs -> forAll (choose (1, length xs)) $ \k ->- checkKNearestEqualToBatch pointAsList2d distSqr2d (xs, k, query)+ checkKNearestConsistentWithLinear pointAsList2d distSqr2d (xs, k, query) checkInRadiusEqualToBatch :: (Ord p, Real a) => PointAsListFn a p -> SquaredDistanceFn a p ->@@ -110,7 +111,9 @@ -- Run all tests return [] runTests :: IO Bool-runTests = $quickCheckAll+runTests = $(forAllProperties) $+ -- Vastly increase success counts; finds more bugs and our properties are cheap.+ quickCheckWithResult stdArgs{ maxSuccess = 2000 } main :: IO () main = do
app-src/Tests/StaticTest.hs view
@@ -2,18 +2,21 @@ import Data.KdMap.Static as KDM -import Control.Monad-import Data.List-import Data.Ord+import Control.Monad (unless)+import Data.List (null, sort, sortBy)+import qualified Data.Set as Set+import Data.Set (isSubsetOf) import Data.Point2d-import System.Exit-import Test.QuickCheck+import System.Exit (exitFailure)+import Test.QuickCheck (Property, arbitrary, forAllProperties, forAll, listOf1, choose, Args(..), stdArgs, quickCheckWithResult) #if MIN_VERSION_QuickCheck(2,7,0) #else import Test.QuickCheck.All #endif +import Tests.TestHelpers (nearestsLinear, withinDistanceOfKthNearest)+ testElements :: [p] -> [(p, Int)] testElements ps = zip ps [0 ..] @@ -37,19 +40,15 @@ prop_validNumElements :: Property prop_validNumElements = forAll (listOf1 arbitrary) $ checkNumElements pointAsList2d -nearestLinear :: Real a => KDM.PointAsListFn a p -> [(p, v)] -> p -> (p, v)-nearestLinear pointAsList xs query =- minimumBy (comparing (KDM.defaultSqrDist pointAsList query . fst)) xs--checkNearestEqualToLinear :: (Eq p, Real a) => KDM.PointAsListFn a p -> ([p], p) -> Bool-checkNearestEqualToLinear pointAsList (ps, query) =+checkNearestConsistentWithLinear :: (Eq p, Real a, Show p) => KDM.PointAsListFn a p -> ([p], p) -> Bool+checkNearestConsistentWithLinear pointAsList (ps, query) = let kdt = build pointAsList $ testElements ps- in nearest kdt query == nearestLinear pointAsList (testElements ps) query+ in nearest kdt query `elem` nearestsLinear pointAsList (testElements ps) query -prop_nearestEqualToLinear :: Point2d -> Property-prop_nearestEqualToLinear query =+prop_nearestConsistentWithLinear :: Point2d -> Property+prop_nearestConsistentWithLinear query = forAll (listOf1 arbitrary) $ \xs ->- checkNearestEqualToLinear pointAsList2d (xs, query)+ checkNearestConsistentWithLinear pointAsList2d (xs, query) inRadiusLinear :: Real a => KDM.PointAsListFn a p -> [(p, v)] -> p -> a -> [(p, v)] inRadiusLinear pointAsList xs query radius =@@ -68,22 +67,18 @@ forAll (choose (0.0, 1000.0)) $ \radius -> checkInRadiusEqualToLinear pointAsList2d radius (xs, query) -kNearestLinear :: Real a => KDM.PointAsListFn a p -> [(p, v)] -> p -> Int -> [(p, v)]-kNearestLinear pointAsList xs query k =- take k $ sortBy (comparing (defaultSqrDist pointAsList query . fst)) xs--checkKNearestEqualToLinear :: (Ord p, Real a) => KDM.PointAsListFn a p -> Int -> ([p], p) -> Bool-checkKNearestEqualToLinear pointAsList k (xs, query) =+checkKNearestConsistentWithLinear :: (Ord p, Real a) => KDM.PointAsListFn a p -> Int -> ([p], p) -> Bool+checkKNearestConsistentWithLinear pointAsList k (xs, query) = let kdt = build pointAsList $ testElements xs kdtKNear = kNearest kdt k query- linearKNear = kNearestLinear pointAsList (testElements xs) query k- in kdtKNear == linearKNear+ possibleNearest = withinDistanceOfKthNearest pointAsList (testElements xs) query k+ in Set.fromList kdtKNear `isSubsetOf` Set.fromList possibleNearest -prop_kNearestEqualToLinear :: Point2d -> Property-prop_kNearestEqualToLinear query =+prop_kNearestConsistentWithLinear :: Point2d -> Property+prop_kNearestConsistentWithLinear query = forAll (listOf1 arbitrary) $ \xs -> forAll (choose (1, length xs)) $ \k ->- checkKNearestEqualToLinear pointAsList2d k (xs, query)+ checkKNearestConsistentWithLinear pointAsList2d k (xs, query) checkKNearestSorted :: (Eq p, Real a) => KDM.PointAsListFn a p -> ([p], p) -> Bool checkKNearestSorted _ ([], _) = True@@ -125,23 +120,25 @@ prop_equalAxisValueEqualToLinear :: Point2d -> Property prop_equalAxisValueEqualToLinear query = forAll (listOf1 arbitrary) $ \xs@(Point2d x y : _) ->- checkNearestEqualToLinear pointAsList2d (Point2d x (y + 1) : xs, query)+ checkNearestConsistentWithLinear pointAsList2d (Point2d x (y + 1) : xs, query) prop_unbalancedInsertValid :: Property prop_unbalancedInsertValid = forAll (listOf1 arbitrary) $ isValid . batchInsertUnbalanced (empty pointAsList2d) . testElements -prop_unbalancedInsertNNEqualToLinear :: Point2d -> Property-prop_unbalancedInsertNNEqualToLinear query =+prop_unbalancedInsertNNConsistentWithLinear :: Point2d -> Property+prop_unbalancedInsertNNConsistentWithLinear query = forAll (listOf1 arbitrary) $ \xs -> let kdm = batchInsertUnbalanced (empty pointAsList2d) $ testElements xs- in nearest kdm query == nearestLinear pointAsList2d (testElements xs) query+ in nearest kdm query `elem` nearestsLinear pointAsList2d (testElements xs) query -- Run all tests return [] runTests :: IO Bool-runTests = $quickCheckAll+runTests = $(forAllProperties) $+ -- Vastly increase success counts; finds more bugs and our properties are cheap.+ quickCheckWithResult stdArgs{ maxSuccess = 2000 } main :: IO () main = do
changelog.md view
@@ -1,3 +1,6 @@+# 0.2.6+* Fixed some failing tests (thanks to @nh2)+ # 0.2.5 * Fixed a minor compile error under GHC 9 caused by ambiguous use of "singleton".
kdt.cabal view
@@ -2,7 +2,7 @@ -- see http://haskell.org/cabal/users-guide/ name: kdt-version: 0.2.5+version: 0.2.6 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@@ -50,6 +50,7 @@ ghc-options: -Wall -O3 build-depends: base >=4.6 && <5, kdt -any,+ containers >= 0.6.0.1, QuickCheck >=2.5, deepseq >=1.3, deepseq-generics >=0.2.0.0@@ -63,6 +64,7 @@ ghc-options: -Wall -O3 build-depends: base >=4.6 && <5, kdt -any,+ containers >= 0.6.0.1, QuickCheck >=2.5, deepseq >=1.3, deepseq-generics >=0.2.0.0