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


-- | KdTree, for efficient search in K-dimensional point clouds.
--   
--   This is a simple library for k-d trees in Haskell. It enables
--   searching through collections of points in O(log N) average time,
--   using the nearestNeighbor function.
@package KdTree
@version 0.2.1

module Data.Trees.KdTree
class Point p
dimension :: Point p => p -> Int
coord :: Point p => Int -> p -> Double
dist2 :: Point p => p -> p -> Double

-- | compareDistance p a b compares the distances of a and b to p.
compareDistance :: Point p => p -> p -> p -> Ordering
data Point3d
Point3d :: Double -> Double -> Double -> Point3d
p3x :: Point3d -> Double
p3y :: Point3d -> Double
p3z :: Point3d -> Double
data KdTree point
KdNode :: KdTree point -> point -> KdTree point -> Int -> KdTree point
kdLeft :: KdTree point -> KdTree point
kdPoint :: KdTree point -> point
kdRight :: KdTree point -> KdTree point
kdAxis :: KdTree point -> Int
KdEmpty :: KdTree point
fromList :: Point p => [p] -> KdTree p

-- | fromListWithDepth selects an axis based on depth so that the axis
--   cycles through all valid values.
fromListWithDepth :: Point p => [p] -> Int -> KdTree p
toList :: KdTree p -> [p]

-- | subtrees t returns a list containing t and all its subtrees, including
--   the empty leaf nodes.
subtrees :: KdTree p -> [KdTree p]

-- | nearestNeighbor tree p returns the nearest neighbor of p in tree.
nearestNeighbor :: Point p => KdTree p -> p -> Maybe p

-- | nearNeighbors tree p returns all neighbors within distance r from p in
--   tree.
nearNeighbors :: Point p => KdTree p -> Double -> p -> [p]

-- | isValid tells whether the K-D tree property holds for a given tree.
--   Specifically, it tests that all points in the left subtree lie to the
--   left of the plane, p is on the plane, and all points in the right
--   subtree lie to the right.
isValid :: Point p => KdTree p -> Bool

-- | allSubtreesAreValid tells whether the K-D tree property holds for the
--   given tree and all subtrees.
allSubtreesAreValid :: Point p => KdTree p -> Bool

-- | kNearestNeighbors tree k p returns the k closest points to p within
--   tree.
kNearestNeighbors :: (Eq p, Point p) => KdTree p -> Int -> p -> [p]

-- | remove t p removes the point p from t.
remove :: (Eq p, Point p) => KdTree p -> p -> KdTree p
instance Eq Point3d
instance Ord Point3d
instance Show Point3d
instance Eq point => Eq (KdTree point)
instance Ord point => Ord (KdTree point)
instance Show point => Show (KdTree point)
instance Arbitrary Point3d
instance Foldable KdTree
instance Functor KdTree
instance Point Point3d