-- 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
--   efficient searching through collections of points in O(log N) time on
--   average, using the nearestNeighbor function.
@package KdTree
@version 0.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 :: Point p => [p] -> Int -> KdTree p
axisFromDepth :: Point p => p -> Int -> Int
toList :: KdTree p -> [p]
subtrees :: KdTree p -> [KdTree p]
nearestNeighbor :: Point p => KdTree p -> p -> Maybe p

-- | invariant tells whether the KD tree property holds for a given tree
--   and all its subtrees. 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.
invariant :: Point p => KdTree p -> Bool
invariant' :: Point p => KdTree p -> Bool
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