-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Fast and flexible k-d trees for various types of point queries.
--   
--   This package includes static and dynamic versions of k-d trees, as
--   well as "Map" variants that store data at each point in the k-d tree
--   structure. Supports nearest neighbor, k nearest neighbors, points
--   within a given radius, and points within a given range. To learn to
--   use this package, start with the documentation for the
--   <a>Data.KdTree.Static</a> module.
@package kdt
@version 0.2.4

module Data.KdMap.Static

-- | Converts a point of type <tt>p</tt> with axis values of type
--   <tt>a</tt> into a list of axis values [a].
type PointAsListFn a p = p -> [a]

-- | Returns the squared distance between two points of type <tt>p</tt>
--   with axis values of type <tt>a</tt>.
type SquaredDistanceFn a p = p -> p -> a

-- | A <i>k</i>-d tree structure that stores points of type <tt>p</tt> with
--   axis values of type <tt>a</tt>. Additionally, each point is associated
--   with a value of type <tt>v</tt>.
data KdMap a p v

-- | Builds an empty <a>KdMap</a>.
empty :: Real a => PointAsListFn a p -> KdMap a p v

-- | Builds an empty <a>KdMap</a> using a user-specified squared distance
--   function.
emptyWithDist :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> KdMap a p v

-- | Builds a <a>KdMap</a> with a single point-value pair.
singleton :: Real a => PointAsListFn a p -> (p, v) -> KdMap a p v

-- | Builds a <a>KdMap</a> with a single point-value pair and a
--   user-specified squared distance function.
singletonWithDist :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> (p, v) -> KdMap a p v

-- | Builds a <tt>KdTree</tt> from a list of pairs of points (of type p)
--   and values (of type v) using a default squared distance function
--   <a>defaultSqrDist</a>.
--   
--   Average complexity: <i>O(n * log(n))</i> for <i>n</i> data points.
--   
--   Worst case time complexity: <i>O(n^2)</i> for <i>n</i> data points.
--   
--   Worst case space complexity: <i>O(n)</i> for <i>n</i> data points.
build :: Real a => PointAsListFn a p -> [(p, v)] -> KdMap a p v

-- | Builds a <a>KdMap</a> from a list of pairs of points (of type p) and
--   values (of type v), using a user-specified squared distance function.
--   
--   Average time complexity: <i>O(n * log(n))</i> for <i>n</i> data
--   points.
--   
--   Worst case time complexity: <i>O(n^2)</i> for <i>n</i> data points.
--   
--   Worst case space complexity: <i>O(n)</i> for <i>n</i> data points.
buildWithDist :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> [(p, v)] -> KdMap a p v

-- | Inserts a point-value pair into a <a>KdMap</a>. This can potentially
--   cause the internal tree structure to become unbalanced. If the tree
--   becomes too unbalanced, point queries will be very inefficient. If you
--   need to perform lots of point insertions on an already existing
--   <i>k</i>-d map, check out <tt>Data.KdMap.Dynamic.</tt><a>KdMap</a>.
--   
--   Average complexity: <i>O(log(n))</i> for <i>n</i> data points.
--   
--   Worst case time complexity: <i>O(n)</i> for <i>n</i> data points.
insertUnbalanced :: Real a => KdMap a p v -> p -> v -> KdMap a p v

-- | Inserts a list of point-value pairs into a <a>KdMap</a>. This can
--   potentially cause the internal tree structure to become unbalanced,
--   which leads to inefficient point queries.
--   
--   Average complexity: <i>O(n * log(n))</i> for <i>n</i> data points.
--   
--   Worst case time complexity: <i>O(n^2)</i> for <i>n</i> data points.
batchInsertUnbalanced :: Real a => KdMap a p v -> [(p, v)] -> KdMap a p v

-- | Given a <a>KdMap</a> and a query point, returns the point-value pair
--   in the <a>KdMap</a> with the point nearest to the query.
--   
--   Average time complexity: <i>O(log(n))</i> for <i>n</i> data points.
--   
--   Worst case time complexity: <i>O(n)</i> for <i>n</i> data points.
--   
--   Throws error if called on an empty <a>KdMap</a>.
nearest :: Real a => KdMap a p v -> p -> (p, v)

-- | Given a <a>KdMap</a>, a query point, and a radius, returns all
--   point-value pairs in the <a>KdMap</a> with points within the given
--   radius of the query point.
--   
--   Points are not returned in any particular order.
--   
--   Worst case time complexity: <i>O(n)</i> for <i>n</i> data points and a
--   radius that spans all points in the structure.
inRadius :: Real a => KdMap a p v -> a -> p -> [(p, v)]

-- | Given a <a>KdMap</a>, a query point, and a number <tt>k</tt>, returns
--   the <tt>k</tt> point-value pairs with the nearest points to the query.
--   
--   Neighbors are returned in order of increasing distance from query
--   point.
--   
--   Average time complexity: <i>log(k) * log(n)</i> for <i>k</i> nearest
--   neighbors on a structure with <i>n</i> data points.
--   
--   Worst case time complexity: <i>n * log(k)</i> for <i>k</i> nearest
--   neighbors on a structure with <i>n</i> data points.
kNearest :: Real a => KdMap a p v -> Int -> p -> [(p, v)]

-- | Finds all point-value pairs in a <a>KdMap</a> with points within a
--   given range, where the range is specified as a set of lower and upper
--   bounds.
--   
--   Points are not returned in any particular order.
--   
--   Worst case time complexity: <i>O(n)</i> for n data points and a range
--   that spans all the points.
--   
--   TODO: Maybe use known bounds on entire tree structure to be able to
--   automatically count whole portions of tree as being within given
--   range.
inRange :: Real a => KdMap a p v -> p -> p -> [(p, v)]

-- | Returns a list of all the point-value pairs in the <a>KdMap</a>.
--   
--   Time complexity: <i>O(n)</i> for <i>n</i> data points.
assocs :: KdMap a p v -> [(p, v)]

-- | Returns all points in the <a>KdMap</a>.
--   
--   Time complexity: <i>O(n)</i> for <i>n</i> data points.
keys :: KdMap a p v -> [p]

-- | Returns all values in the <a>KdMap</a>.
--   
--   Time complexity: <i>O(n)</i> for <i>n</i> data points.
elems :: KdMap a p v -> [v]

-- | Returns <a>True</a> if the given <a>KdMap</a> is empty.
null :: KdMap a p v -> Bool

-- | Returns the number of point-value pairs in the <a>KdMap</a>.
--   
--   Time complexity: <i>O(1)</i>
size :: KdMap a p v -> Int

-- | Performs a foldr over each point-value pair in the <a>KdMap</a>.
foldrWithKey :: ((p, v) -> b -> b) -> b -> KdMap a p v -> b

-- | A default implementation of squared distance given two points and a
--   <a>PointAsListFn</a>.
defaultSqrDist :: Num a => PointAsListFn a p -> SquaredDistanceFn a p

-- | A node of a <i>k</i>-d tree structure that stores a point of type
--   <tt>p</tt> with axis values of type <tt>a</tt>. Additionally, each
--   point is associated with a value of type <tt>v</tt>. Note: users
--   typically will not need to use this type, but we export it just in
--   case.
data TreeNode a p v
TreeNode :: TreeNode a p v -> (p, v) -> a -> TreeNode a p v -> TreeNode a p v
[_treeLeft] :: TreeNode a p v -> TreeNode a p v
[_treePoint] :: TreeNode a p v -> (p, v)
[_axisValue] :: TreeNode a p v -> a
[_treeRight] :: TreeNode a p v -> TreeNode a p v
Empty :: TreeNode a p v

-- | Returns <a>True</a> if tree structure adheres to k-d tree properties.
--   For internal testing use.
isValid :: Real a => KdMap a p v -> Bool
instance GHC.Generics.Generic (Data.KdMap.Static.KdMap a p v)
instance (GHC.Read.Read p, GHC.Read.Read v, GHC.Read.Read a) => GHC.Read.Read (Data.KdMap.Static.TreeNode a p v)
instance (GHC.Show.Show p, GHC.Show.Show v, GHC.Show.Show a) => GHC.Show.Show (Data.KdMap.Static.TreeNode a p v)
instance GHC.Generics.Generic (Data.KdMap.Static.TreeNode a p v)
instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData p, Control.DeepSeq.NFData v) => Control.DeepSeq.NFData (Data.KdMap.Static.KdMap a p v)
instance (GHC.Show.Show a, GHC.Show.Show p, GHC.Show.Show v) => GHC.Show.Show (Data.KdMap.Static.KdMap a p v)
instance GHC.Base.Functor (Data.KdMap.Static.KdMap a p)
instance Data.Foldable.Foldable (Data.KdMap.Static.KdMap a p)
instance Data.Traversable.Traversable (Data.KdMap.Static.KdMap a p)
instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData p, Control.DeepSeq.NFData v) => Control.DeepSeq.NFData (Data.KdMap.Static.TreeNode a p v)

module Data.KdMap.Dynamic

-- | Converts a point of type <tt>p</tt> with axis values of type
--   <tt>a</tt> into a list of axis values [a].
type PointAsListFn a p = p -> [a]

-- | Returns the squared distance between two points of type <tt>p</tt>
--   with axis values of type <tt>a</tt>.
type SquaredDistanceFn a p = p -> p -> a

-- | A dynamic <i>k</i>-d tree structure that stores points of type
--   <tt>p</tt> with axis values of type <tt>a</tt>. Additionally, each
--   point is associated with a value of type <tt>v</tt>.
data KdMap a p v

-- | Generates an empty <a>KdMap</a> with the default distance function.
empty :: Real a => PointAsListFn a p -> KdMap a p v

-- | Generates a <a>KdMap</a> with a single point-value pair using the
--   default distance function.
singleton :: Real a => PointAsListFn a p -> (p, v) -> KdMap a p v

-- | Generates an empty <a>KdMap</a> with a user-specified distance
--   function.
emptyWithDist :: PointAsListFn a p -> SquaredDistanceFn a p -> KdMap a p v

-- | Generates a <a>KdMap</a> with a single point-value pair using a
--   user-specified distance function.
singletonWithDist :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> (p, v) -> KdMap a p v

-- | Adds a given point-value pair to a <a>KdMap</a>.
--   
--   Average time complexity per insert for <i>n</i> inserts:
--   <i>O(log^2(n))</i>.
insert :: Real a => KdMap a p v -> p -> v -> KdMap a p v

-- | Same as <a>insert</a>, but takes point and value as a pair.
insertPair :: Real a => KdMap a p v -> (p, v) -> KdMap a p v

-- | Inserts a list of point-value pairs into the <a>KdMap</a>.
--   
--   TODO: This will be made far more efficient than simply repeatedly
--   inserting.
batchInsert :: Real a => KdMap a p v -> [(p, v)] -> KdMap a p v

-- | Given a <a>KdMap</a> and a query point, returns the point-value pair
--   in the <a>KdMap</a> with the point nearest to the query.
--   
--   Average time complexity: <i>O(log^2(n))</i>.
nearest :: Real a => KdMap a p v -> p -> (p, v)

-- | Given a <a>KdMap</a>, a query point, and a radius, returns all
--   point-value pairs in the <tt>KdTree</tt> with points within the given
--   radius of the query point.
--   
--   Points are not returned in any particular order.
--   
--   Worst case time complexity: <i>O(n)</i> for <i>n</i> data points.
inRadius :: Real a => KdMap a p v -> a -> p -> [(p, v)]

-- | Given a <a>KdMap</a>, a query point, and a number <tt>k</tt>, returns
--   the <tt>k</tt> point-value pairs with the nearest points to the query.
--   
--   Neighbors are returned in order of increasing distance from query
--   point.
--   
--   Average time complexity: <i>log(k) * log^2(n)</i> for <i>k</i> nearest
--   neighbors on a structure with <i>n</i> data points.
--   
--   Worst case time complexity: <i>n * log(k)</i> for <i>k</i> nearest
--   neighbors on a structure with <i>n</i> data points.
kNearest :: Real a => KdMap a p v -> Int -> p -> [(p, v)]

-- | Finds all point-value pairs in a <a>KdMap</a> with points within a
--   given range, where the range is specified as a set of lower and upper
--   bounds.
--   
--   Points are not returned in any particular order.
--   
--   Worst case time complexity: <i>O(n)</i> for n data points and a range
--   that spans all the points.
inRange :: Real a => KdMap a p v -> p -> p -> [(p, v)]

-- | Returns a list of all the point-value pairs in the <a>KdMap</a>.
--   
--   Time complexity: <i>O(n)</i> for <i>n</i> data points.
assocs :: KdMap a p v -> [(p, v)]

-- | Returns all points in the <a>KdMap</a>.
--   
--   Time complexity: <i>O(n)</i> for <i>n</i> data points.
keys :: KdMap a p v -> [p]

-- | Returns all values in the <a>KdMap</a>.
--   
--   Time complexity: <i>O(n)</i> for <i>n</i> data points.
elems :: KdMap a p v -> [v]

-- | Returns whether the <a>KdMap</a> is empty.
null :: KdMap a p v -> Bool

-- | Returns the number of elements in the <a>KdMap</a>.
--   
--   Time complexity: <i>O(1)</i>
size :: KdMap a p v -> Int

-- | Performs a foldr over each point-value pair in the <a>KdMap</a>.
foldrWithKey :: ((p, v) -> b -> b) -> b -> KdMap a p v -> b

-- | A default implementation of squared distance given two points and a
--   <a>PointAsListFn</a>.
defaultSqrDist :: Num a => PointAsListFn a p -> SquaredDistanceFn a p

-- | Returns size of each internal <i>k</i>-d tree that makes up the
--   dynamic structure. For internal testing use.
subtreeSizes :: KdMap a p v -> [Int]
instance GHC.Generics.Generic (Data.KdMap.Dynamic.KdMap a p v)
instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData p, Control.DeepSeq.NFData v) => Control.DeepSeq.NFData (Data.KdMap.Dynamic.KdMap a p v)
instance (GHC.Show.Show a, GHC.Show.Show p, GHC.Show.Show v) => GHC.Show.Show (Data.KdMap.Dynamic.KdMap a p v)
instance GHC.Base.Functor (Data.KdMap.Dynamic.KdMap a p)
instance Data.Foldable.Foldable (Data.KdMap.Dynamic.KdMap a p)
instance Data.Traversable.Traversable (Data.KdMap.Dynamic.KdMap a p)

module Data.KdTree.Dynamic

-- | Converts a point of type <tt>p</tt> with axis values of type
--   <tt>a</tt> into a list of axis values [a].
type PointAsListFn a p = p -> [a]

-- | Returns the squared distance between two points of type <tt>p</tt>
--   with axis values of type <tt>a</tt>.
type SquaredDistanceFn a p = p -> p -> a

-- | A dynamic <i>k</i>-d tree structure that stores points of type
--   <tt>p</tt> with axis values of type <tt>a</tt>.
data KdTree a p

-- | Generates an empty <a>KdTree</a> with the default distance function.
empty :: Real a => PointAsListFn a p -> KdTree a p

-- | Generates a <a>KdTree</a> with a single point using the default
--   distance function.
singleton :: Real a => PointAsListFn a p -> p -> KdTree a p

-- | Generates an empty <a>KdTree</a> with a user-specified distance
--   function.
emptyWithDist :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> KdTree a p

-- | Generates a <a>KdTree</a> with a single point using a user-specified
--   distance function.
singletonWithDist :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> p -> KdTree a p

-- | Adds a given point to a <a>KdTree</a>.
--   
--   Average time complexity per insert for <i>n</i> inserts:
--   <i>O(log^2(n))</i>.
insert :: Real a => KdTree a p -> p -> KdTree a p

-- | Given a <a>KdTree</a> and a query point, returns the nearest point in
--   the <a>KdTree</a> to the query point.
--   
--   Average time complexity: <i>O(log^2(n))</i>.
nearest :: Real a => KdTree a p -> p -> p

-- | Given a <a>KdTree</a>, a query point, and a radius, returns all points
--   in the <a>KdTree</a> that are within the given radius of the query
--   points.
--   
--   Points are not returned in any particular order.
--   
--   Worst case time complexity: <i>O(n)</i> for <i>n</i> data points.
inRadius :: Real a => KdTree a p -> a -> p -> [p]

-- | Given a <a>KdTree</a>, a query point, and a number <tt>k</tt>, returns
--   the <tt>k</tt> nearest points in the <a>KdTree</a> to the query point.
--   
--   Neighbors are returned in order of increasing distance from query
--   point.
--   
--   Average time complexity: <i>log(k) * log^2(n)</i> for <i>k</i> nearest
--   neighbors on a structure with <i>n</i> data points.
--   
--   Worst case time complexity: <i>n * log(k)</i> for <i>k</i> nearest
--   neighbors on a structure with <i>n</i> data points.
kNearest :: Real a => KdTree a p -> Int -> p -> [p]

-- | Finds all points in a <a>KdTree</a> with points within a given range,
--   where the range is specified as a set of lower and upper bounds.
--   
--   Points are not returned in any particular order.
--   
--   Worst case time complexity: <i>O(n)</i> for n data points and a range
--   that spans all the points.
inRange :: Real a => KdTree a p -> p -> p -> [p]

-- | Returns a list of all the points in the <a>KdTree</a>.
--   
--   Time complexity: <i>O(n)</i>
toList :: KdTree a p -> [p]

-- | Returns whether the <a>KdTree</a> is empty.
null :: KdTree a p -> Bool

-- | Returns the number of elements in the <a>KdTree</a>.
--   
--   Time complexity: <i>O(1)</i>
size :: KdTree a p -> Int

-- | A default implementation of squared distance given two points and a
--   <a>PointAsListFn</a>.
defaultSqrDist :: Num a => PointAsListFn a p -> SquaredDistanceFn a p
instance Data.Foldable.Foldable (Data.KdTree.Dynamic.KdTree a)
instance (GHC.Show.Show a, GHC.Show.Show p) => GHC.Show.Show (Data.KdTree.Dynamic.KdTree a p)

module Data.KdTree.Static

-- | Converts a point of type <tt>p</tt> with axis values of type
--   <tt>a</tt> into a list of axis values [a].
type PointAsListFn a p = p -> [a]

-- | Returns the squared distance between two points of type <tt>p</tt>
--   with axis values of type <tt>a</tt>.
type SquaredDistanceFn a p = p -> p -> a

-- | A <i>k</i>-d tree structure that stores points of type <tt>p</tt> with
--   axis values of type <tt>a</tt>.
data KdTree a p

-- | Builds an empty <a>KdTree</a>.
empty :: Real a => PointAsListFn a p -> KdTree a p

-- | Builds an empty <a>KdTree</a> using a user-specified squared distance
--   function.
emptyWithDist :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> KdTree a p

-- | Builds a <a>KdTree</a> with a single point.
singleton :: Real a => PointAsListFn a p -> p -> KdTree a p

-- | Builds a <a>KdTree</a> with a single point using a user-specified
--   squared distance function.
singletonWithDist :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> p -> KdTree a p

-- | Builds a <a>KdTree</a> from a list of data points using a default
--   squared distance function <a>defaultSqrDist</a>.
--   
--   Average complexity: <i>O(n * log(n))</i> for <i>n</i> data points.
--   
--   Worst case time complexity: <i>O(n^2)</i> for <i>n</i> data points.
--   
--   Worst case space complexity: <i>O(n)</i> for <i>n</i> data points.
build :: Real a => PointAsListFn a p -> [p] -> KdTree a p

-- | Builds a <a>KdTree</a> from a list of data points using a
--   user-specified squared distance function.
--   
--   Average time complexity: <i>O(n * log(n))</i> for <i>n</i> data
--   points.
--   
--   Worst case time complexity: <i>O(n^2)</i> for <i>n</i> data points.
--   
--   Worst case space complexity: <i>O(n)</i> for <i>n</i> data points.
buildWithDist :: Real a => PointAsListFn a p -> SquaredDistanceFn a p -> [p] -> KdTree a p

-- | Inserts a point into a <a>KdTree</a>. This can potentially cause the
--   internal tree structure to become unbalanced. If the tree becomes too
--   unbalanced, point queries will be very inefficient. If you need to
--   perform lots of point insertions on an already existing <i>k</i>-d
--   tree, check out <tt>Data.KdTree.Dynamic.</tt><a>KdTree</a>.
--   
--   Average complexity: <i>O(log(n))</i> for <i>n</i> data points.
--   
--   Worse case time complexity: <i>O(n)</i> for <i>n</i> data points.
insertUnbalanced :: Real a => KdTree a p -> p -> KdTree a p

-- | Inserts a list of points into a <a>KdTree</a>. This can potentially
--   cause the internal tree structure to become unbalanced, which leads to
--   inefficient point queries.
--   
--   Average complexity: <i>O(n * log(n))</i> for <i>n</i> data points.
--   
--   Worst case time complexity: <i>O(n^2)</i> for <i>n</i> data points.
batchInsertUnbalanced :: Real a => KdTree a p -> [p] -> KdTree a p

-- | Given a <a>KdTree</a> and a query point, returns the nearest point in
--   the <a>KdTree</a> to the query point.
--   
--   Average time complexity: <i>O(log(n))</i> for <i>n</i> data points.
--   
--   Worst case time complexity: <i>O(n)</i> for <i>n</i> data points.
--   
--   Throws an error if called on an empty <a>KdTree</a>.
nearest :: Real a => KdTree a p -> p -> p

-- | Given a <a>KdTree</a>, a query point, and a radius, returns all points
--   in the <a>KdTree</a> that are within the given radius of the query
--   point.
--   
--   Points are not returned in any particular order.
--   
--   Worst case time complexity: <i>O(n)</i> for <i>n</i> data points and a
--   radius that subsumes all points in the structure.
inRadius :: Real a => KdTree a p -> a -> p -> [p]

-- | Given a <a>KdTree</a>, a query point, and a number <tt>k</tt>, returns
--   the <tt>k</tt> nearest points in the <a>KdTree</a> to the query point.
--   
--   Neighbors are returned in order of increasing distance from query
--   point.
--   
--   Average time complexity: <i>log(k) * log(n)</i> for <i>k</i> nearest
--   neighbors on a structure with <i>n</i> data points.
--   
--   Worst case time complexity: <i>n * log(k)</i> for <i>k</i> nearest
--   neighbors on a structure with <i>n</i> data points.
kNearest :: Real a => KdTree a p -> Int -> p -> [p]

-- | Finds all points in a <a>KdTree</a> with points within a given range,
--   where the range is specified as a set of lower and upper bounds.
--   
--   Points are not returned in any particular order.
--   
--   Worst case time complexity: <i>O(n)</i> for n data points and a range
--   that spans all the points.
inRange :: Real a => KdTree a p -> p -> p -> [p]

-- | Returns a list of all the points in the <a>KdTree</a>.
--   
--   Time complexity: <i>O(n)</i> for <i>n</i> data points.
toList :: KdTree a p -> [p]
null :: KdTree a p -> Bool

-- | Returns the number of elements in the <a>KdTree</a>.
--   
--   Time complexity: <i>O(1)</i>
size :: KdTree a p -> Int

-- | A default implementation of squared distance given two points and a
--   <a>PointAsListFn</a>.
defaultSqrDist :: Num a => PointAsListFn a p -> SquaredDistanceFn a p
instance GHC.Generics.Generic (Data.KdTree.Static.KdTree a p)
instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData p) => Control.DeepSeq.NFData (Data.KdTree.Static.KdTree a p)
instance (GHC.Show.Show a, GHC.Show.Show p) => GHC.Show.Show (Data.KdTree.Static.KdTree a p)
instance Data.Foldable.Foldable (Data.KdTree.Static.KdTree a)
