bktrees 0.2 → 0.2.1

raw patch · 2 files changed

+41/−8 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/Set/BKTree.hs +40/−7
• bktrees.cabal +1/−1

@@ -200,7 +200,6 @@ elems Empty = [] elems (Node a _ imap) = a : concatMap elems (M.elems imap) - -- | @'elemsDistance' n a tree@ returns all the elements in @tree@ which are  --   at a 'distance' less than or equal to @n@ from the element @a@. elemsDistance :: Metric a => Int -> a -> BKTree a -> [a]@@ -218,12 +217,6 @@ fromList :: Metric a => [a] -> BKTree a fromList xs = constructTree (\a -> Just (a,[])) xs --- | Merges several trees-unions :: Metric a => [BKTree a] -> BKTree a-unions xs = constructTree split xs-  where split Empty = Nothing-        split (Node a _ imap) = Just (a,M.elems imap)- constructTree extract [] = Empty constructTree extract (a:as)     = case extract a of@@ -241,6 +234,10 @@                          Nothing    -> []         recurse bs@((k,_):_) = (k, constructTree extract (map snd bs)) +-- | Merges several trees+unions :: Metric a => [BKTree a] -> BKTree a+unions xs = fromList $ concat $ map elems xs+ -- | Merges two trees union :: Metric a => BKTree a -> BKTree a -> BKTree a union t1 t2 = unions [t1,t2]@@ -312,6 +309,13 @@ -- For testing functions that transform trees trans f xs = sem (f (fromList xs)) +invariant t = inv [] t++inv dict Empty = True+inv dict (Node a _ imap) +    = all (\ (d,b) -> distance a b == d) dict &&+      all (\ (d,t) -> inv ((d,a):dict) t) (M.toList imap)+ -- Tests for individual functions  prop_empty n = not (member (n::Int) empty)@@ -322,9 +326,14 @@  prop_fromList xs = sem (fromList xs) == L.sort xs +prop_fromListInv xs = invariant (fromList (xs :: [Int]))+ prop_insert n xs =      trans (insert n) xs == L.sort (n:xs) +prop_insertInv n xs =+    invariant (insert n (fromList (xs :: [Int])))+ prop_member n xs = member n (fromList xs) == L.elem (n::Int) xs  prop_memberDistance dist n xs = @@ -341,6 +350,9 @@        removeFirst (a:as) | a == n    = as                           | otherwise = a : removeFirst as +prop_deleteInv n xs =+    invariant (delete n (fromList (xs :: [Int])))+ prop_elems xs = L.sort (elems (fromList xs)) == L.sort (xs::[Int])  prop_elemsDistance dist n xs = @@ -352,10 +364,16 @@     sem (unions (map fromList xss)) ==      L.sort (concat (xss::[[Int]])) +prop_unionsInv xss =+    invariant (unions (map fromList (xss :: [[Int]])))+ prop_union xs ys =     sem (union (fromList xs) (fromList ys)) ==     L.sort (xs ++ (ys::[Int])) +prop_unionInv xs ys =+    invariant (union (fromList (xs :: [Int])) (fromList (ys :: [Int])))+ prop_closest n xs =   case (closest n (fromList xs),xs) of     (Nothing,[]) -> True@@ -385,20 +403,33 @@ prop_sizeUnions xss = size (unions trees) == sum (map size trees)   where trees = map fromList (xss :: [[Int]]) +prop_unionsMember xss =+    all (\x -> member x tree) (concat (xss :: [[Int]]))+  where tree = unions (map fromList xss)++prop_fromListMember xs =+    all (\x -> member x tree) (xs :: [Int])+  where tree = fromList xs+ -- All the tests  tests = [("empty",             quickCheck' prop_empty)         ,("null",              quickCheck' prop_null)         ,("singleton",         quickCheck' prop_singleton)         ,("fromList",          quickCheck' prop_fromList)+        ,("fromList inv",      quickCheck' prop_fromListInv)         ,("insert",            quickCheck' prop_insert)+        ,("insert inv",        quickCheck' prop_insertInv)         ,("member",            quickCheck' prop_member)         ,("memberDistance",    quickCheck' prop_memberDistance)         ,("delete",            quickCheck' prop_delete)+        ,("delete inv",        quickCheck' prop_deleteInv)         ,("elems",             quickCheck' prop_elems)         ,("elemsDistance",     quickCheck' prop_elemsDistance)         ,("unions",            quickCheck' prop_unions)+        ,("unions inv",        quickCheck' prop_unionsInv)         ,("union",             quickCheck' prop_union)+        ,("union inv",         quickCheck' prop_unionInv)         ,("closest",           quickCheck' prop_closest)         ,("size/empty",        quickCheck' prop_sizeEmpty)         ,("size/fromList",     quickCheck' prop_sizeFromList)@@ -407,6 +438,8 @@         ,("size/union",        quickCheck' prop_sizeUnion)         ,("size/unions",       quickCheck' prop_sizeUnions)         ,("insert/delete",     quickCheck' prop_insertDelete)+        ,("fromList/member",   quickCheck' prop_fromListMember)+        ,("unions/member",     quickCheck' prop_unionsMember)         ,("levenshtein",       quickCheck' prop_levenshtein)         ,("levenshtein repeat",quickCheck' prop_levenshteinRepeat)         ,("levenshtein length",quickCheck' prop_levenshteinLength)

@@ -1,5 +1,5 @@ name:		bktrees-version:	0.2+version:	0.2.1 license:	BSD3 license-file:	LICENSE author:		Josef Svenningsson