bktrees 0.1.3 → 0.2
raw patch · 2 files changed
+81/−50 lines, 2 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
+ Data.Set.BKTree: size :: BKTree a -> Int
Files
- Data/Set/BKTree.hs +79/−48
- bktrees.cabal +2/−2
Data/Set/BKTree.hs view
@@ -7,7 +7,7 @@ Stability : Alpha quality. Interface may change without notice. Portability : portable - Burhard-Keller trees provide an implementation of sets which apart+ Burkhard-Keller trees provide an implementation of sets which apart from the ordinary operations also has an approximate member search, allowing you to search for elements that are of a distance @n@ from the element you are searching for. The distance is determined using@@ -17,11 +17,11 @@ Useful metrics include the manhattan distance between two points, the Levenshtein edit distance between two strings, the number of- edges in the shortest path between two nodes in a undirected graph+ edges in the shortest path between two nodes in an undirected graph and the Hamming distance between two binary strings. Any euclidean space also has a metric. However, in this module we use int-valued- metrics and that doesn't quite with the metrics of euclidean spaces- which are real-values.+ metrics and that's not compatible with the metrics of euclidean + spaces which are real-values. The worst case complexity of many of these operations is quite bad, but the expected behavior varies greatly with the metric. For@@ -35,9 +35,8 @@ BKTree -- Metric ,Metric(..)--- ,Manhattan(..) --- ,null,empty+ ,null,size,empty ,fromList,singleton ,insert ,member,memberDistance@@ -126,8 +125,8 @@ -- BKTrees -- -------- --- | The type of Burhard-Keller trees.-data BKTree a = Node a (M.IntMap (BKTree a))+-- | The type of Burkhard-Keller trees.+data BKTree a = Node a !Int (M.IntMap (BKTree a)) | Empty #ifdef DEBUG deriving Show@@ -137,29 +136,34 @@ -- | Test if the tree is empty. null :: BKTree a -> Bool null (Empty) = True-null (Node _ _) = False+null (Node _ _ _) = False +-- | Size of the tree.+size :: BKTree a -> Int+size (Empty) = 0+size (Node _ s _) = s+ -- | The empty tree. empty :: BKTree a empty = Empty -- | The tree with a single element singleton :: a -> BKTree a-singleton a = Node a M.empty+singleton a = Node a 1 M.empty -- | Inserts an element into the tree. If an element is inserted several times -- it will be stored several times. insert :: Metric a => a -> BKTree a -> BKTree a-insert a Empty = Node a M.empty-insert a (Node b map) = Node b map'- where map' = M.insertWith recurse d (Node a M.empty) map+insert a Empty = Node a 1 M.empty+insert a (Node b size map) = Node b (size+1) map'+ where map' = M.insertWith recurse d (Node a 1 M.empty) map d = distance a b recurse _ tree = insert a tree -- | Checks whether an element is in the tree. member :: Metric a => a -> BKTree a -> Bool member a Empty = False-member a (Node b map) +member a (Node b _ map) | d == 0 = True | otherwise = case M.lookup d map of Nothing -> False@@ -171,35 +175,37 @@ -- @n@ from @a@. memberDistance :: Metric a => Int -> a -> BKTree a -> Bool memberDistance n a Empty = False-memberDistance n a (Node b map)+memberDistance n a (Node b _ map) | d <= n = True | otherwise = any (memberDistance n a) (M.elems subMap) where d = distance a b subMap = case M.split (d-n-1) map of- (_,mapRight) -> + (_,mapRight) -> case M.split (d+n+1) mapRight of (mapCenter,_) -> mapCenter -- | Removes an element from the tree. If an element occurs several times in --- the only the first occurrence will be deleted.+-- the tree then only one occurrence will be deleted. delete :: Metric a => a -> BKTree a -> BKTree a delete a Empty = Empty-delete a t@(Node b map) +delete a t@(Node b _ map) | d == 0 = unions (M.elems map)- | otherwise = Node b (M.update (Just . delete a) d map)+ | otherwise = Node b sz subtrees where d = distance a b+ subtrees = M.update (Just . delete a) d map+ sz = sum (L.map size (M.elems subtrees)) + 1 -- | Returns all the elements of the tree elems :: BKTree a -> [a] elems Empty = []-elems (Node a imap) = a : concatMap elems (M.elems imap)+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] elemsDistance n a Empty = []-elemsDistance n a (Node b imap) +elemsDistance n a (Node b _ imap) = (if d <= n then (b :) else id) $ concatMap (elemsDistance n a) (M.elems subMap) where d = distance a b@@ -210,33 +216,31 @@ -- | Constructs a tree from a list fromList :: Metric a => [a] -> BKTree a-fromList [] = Empty-fromList (a:as) = Node a $- M.fromAscList $- map recurse $- L.groupBy ((==) `on` fst) $- L.sortBy (compare `on` fst) $- map mkDistance $- as- where mkDistance b = (distance a b,b)- recurse bs@((k,_):_) = (k,fromList (map snd bs))+fromList xs = constructTree (\a -> Just (a,[])) xs -- | Merges several trees unions :: Metric a => [BKTree a] -> BKTree a-unions [] = Empty-unions (Empty:ts) = unions ts-unions (Node piv pmap:ts) = Node piv $- M.fromAscList $- map recurse $- L.groupBy ((==) `on` fst) $- L.sortBy (compare `on` fst) $- (M.toList pmap ++) $- concatMap mkDistance $- ts- where mkDistance n@(Node a _) = [(distance piv a,n)]- mkDistance _ = []- recurse bs@((k,_):_) = (k,unions (map snd bs))+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+ Nothing -> constructTree extract as+ Just (piv,rest) -> + (\imap -> Node piv (1 + sum (map size (M.elems imap))) imap) $+ M.fromAscList $+ map recurse $+ L.groupBy ((==) `on` fst) $+ L.sortBy (compare `on` fst) $+ concatMap (mkDist piv) $+ as ++ rest+ where mkDist piv m = case extract m of+ Just (a,_) -> [(distance piv a,m)]+ Nothing -> []+ recurse bs@((k,_):_) = (k, constructTree extract (map snd bs))+ -- | Merges two trees union :: Metric a => BKTree a -> BKTree a -> BKTree a union t1 t2 = unions [t1,t2]@@ -245,10 +249,10 @@ -- @a@ together with the distance. Returns @Nothing@ if the tree is empty. closest :: Metric a => a -> BKTree a -> Maybe (a,Int) closest a Empty = Nothing-closest a tree@(Node b _) = Just (closeLoop a (b,distance a b) tree)+closest a tree@(Node b _ _) = Just (closeLoop a (b,distance a b) tree) closeLoop a candidate Empty = candidate-closeLoop a candidate@(b,d) (Node x imap)+closeLoop a candidate@(b,d) (Node x _ imap) = L.foldl' (closeLoop a) newCand (M.elems subMap) where newCand = if j >= d then candidate@@ -303,7 +307,7 @@ where allDifferent xs ys = all (==False) (zipWith (==) xs ys) -- Semantics of BKTrees. Just a boring list of integers-sem tree = L.sort (elems tree)+sem tree = L.sort (elems tree) :: [Int] -- For testing functions that transform trees trans f xs = sem (f (fromList xs))@@ -316,8 +320,10 @@ prop_singleton n = elems (fromList [n]) == [n :: Int] +prop_fromList xs = sem (fromList xs) == L.sort xs+ prop_insert n xs = - trans (insert (n::Int)) xs == L.sort (n:xs)+ trans (insert n) xs == L.sort (n:xs) prop_member n xs = member n (fromList xs) == L.elem (n::Int) xs @@ -361,11 +367,30 @@ prop_insertDelete n xs = trans (delete n . insert n) xs == L.sort (xs::[Int]) +prop_sizeEmpty = size empty == 0++prop_sizeFromList xs = size (fromList xs) == length (xs :: [Int])++prop_sizeSucc n xs = size (insert (n::Int) tree) == size tree + 1+ where tree = fromList xs++prop_sizeDelete n xs + = size (delete (n::Int) tree) == + size tree - (if n `member` tree then 1 else 0)+ where tree = fromList xs++prop_sizeUnion xs ys = size (union treeXs treeYs) == size treeXs + size treeYs+ where (treeXs,treeYs) = (fromList xs, fromList (ys :: [Int]))++prop_sizeUnions xss = size (unions trees) == sum (map size trees)+ where trees = map fromList (xss :: [[Int]])+ -- All the tests tests = [("empty", quickCheck' prop_empty) ,("null", quickCheck' prop_null) ,("singleton", quickCheck' prop_singleton)+ ,("fromList", quickCheck' prop_fromList) ,("insert", quickCheck' prop_insert) ,("member", quickCheck' prop_member) ,("memberDistance", quickCheck' prop_memberDistance)@@ -375,6 +400,12 @@ ,("unions", quickCheck' prop_unions) ,("union", quickCheck' prop_union) ,("closest", quickCheck' prop_closest)+ ,("size/empty", quickCheck' prop_sizeEmpty)+ ,("size/fromList", quickCheck' prop_sizeFromList)+ ,("size/succ", quickCheck' prop_sizeSucc)+ ,("size/delete", quickCheck' prop_sizeDelete)+ ,("size/union", quickCheck' prop_sizeUnion)+ ,("size/unions", quickCheck' prop_sizeUnions) ,("insert/delete", quickCheck' prop_insertDelete) ,("levenshtein", quickCheck' prop_levenshtein) ,("levenshtein repeat",quickCheck' prop_levenshteinRepeat)
bktrees.cabal view
@@ -1,5 +1,5 @@ name: bktrees-version: 0.1.3+version: 0.2 license: BSD3 license-file: LICENSE author: Josef Svenningsson@@ -7,7 +7,7 @@ category: Data Structures synopsis: A set data structure with approximate searching description:- Burhard-Keller trees provide an implementation of sets + Burkhard-Keller trees provide an implementation of sets which apart from the ordinary operations also has an approximate member search, allowing you to search for elements that are of a certain distance from the element