-- 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.2.1

module Data.Trees.KdTree
class Point p where dist2 a b = sum . map diff2 $ [0 .. dimension a - 1] where diff2 i = (coord i a - coord i b) ^ 2

-- | dimension returns the number of coordinates of a point.
dimension :: Point p => p -> Int

-- | coord gets the k'th coordinate, starting from 0.
coord :: Point p => Int -> p -> Double

-- | dist2 returns the squared distance between two points.
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 GHC.Show.Show point => GHC.Show.Show (Data.Trees.KdTree.KdTree point)
instance GHC.Classes.Ord point => GHC.Classes.Ord (Data.Trees.KdTree.KdTree point)
instance GHC.Classes.Eq point => GHC.Classes.Eq (Data.Trees.KdTree.KdTree point)
instance GHC.Show.Show Data.Trees.KdTree.Point3d
instance GHC.Classes.Ord Data.Trees.KdTree.Point3d
instance GHC.Classes.Eq Data.Trees.KdTree.Point3d
instance Data.Trees.KdTree.Point Data.Trees.KdTree.Point3d
instance GHC.Base.Functor Data.Trees.KdTree.KdTree
instance Data.Foldable.Foldable Data.Trees.KdTree.KdTree
instance Test.QuickCheck.Arbitrary.Arbitrary Data.Trees.KdTree.Point3d