-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A set data structure with approximate searching
--
-- 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 you are searching for.
@package bktrees
@version 0.2
-- | 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 a metric on the type of elements. Therefore all elements must
-- implement the Metric type class, rather than the more usual
-- Ord.
--
-- 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 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'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 example,
-- the discrete metric (distance x y | y == x = 0 | otherwise =
-- 1) makes BK-trees behave abysmally. The metrics mentioned above
-- should give good performance characteristics.
module Data.Set.BKTree
-- | The type of Burkhard-Keller trees.
data BKTree a
-- | A type is Metric if is has a function distance which has
-- the following properties:
--
--
--
-- All types of elements to BKTree must implement Metric.
--
-- This definition of a metric deviates from the mathematical one in that
-- it returns an integer instead of a real number. The reason for
-- choosing integers is that I wanted to avoid the rather unpredictable
-- rounding of floating point numbers.
class (Eq a) => Metric a
distance :: (Metric a) => a -> a -> Int
-- | Test if the tree is empty.
null :: BKTree a -> Bool
-- | Size of the tree.
size :: BKTree a -> Int
-- | The empty tree.
empty :: BKTree a
-- | Constructs a tree from a list
fromList :: (Metric a) => [a] -> BKTree a
-- | The tree with a single element
singleton :: a -> BKTree a
-- | 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
-- | Checks whether an element is in the tree.
member :: (Metric a) => a -> BKTree a -> Bool
-- | Approximate searching. memberDistance n a tree will
-- return true if there is an element in tree which has a
-- distance less than or equal to n from a.
memberDistance :: (Metric a) => Int -> a -> BKTree a -> Bool
-- | Removes an element from the tree. If an element occurs several times
-- in the tree then only one occurrence will be deleted.
delete :: (Metric a) => a -> BKTree a -> BKTree a
-- | Merges two trees
union :: (Metric a) => BKTree a -> BKTree a -> BKTree a
-- | Merges several trees
unions :: (Metric a) => [BKTree a] -> BKTree a
-- | Returns all the elements of the tree
elems :: BKTree a -> [a]
-- | 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]
-- | closest a tree returns the element in tree
-- which is closest to a together with the distance. Returns
-- Nothing if the tree is empty.
closest :: (Metric a) => a -> BKTree a -> Maybe (a, Int)
instance (Eq a) => Metric [a]
instance Metric Char
instance Metric Integer
instance Metric Int