œN      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMSafe04A k--d tree structure that stores points of type p with axis values of type a?. Additionally, each point is associated with a value of type v.9Returns the squared distance between two points of type p with axis values of type a.Converts a point of type p with axis values of type a into a list of axis values [a]. A node of a k.-d tree structure that stores a point of type p with axis values of type a?. Additionally, each point is associated with a value of type vW. Note: users typically will not need to use this type, but we export it just in case. 3Performs a foldr over each point-value pair in the . Builds an empty . Builds an empty 3 using a user-specified squared distance function. Returns N if the given  is empty. Builds a P with a single point-value pair and a user-specified squared distance function. Builds a  with a single point-value pair. Builds a w 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:  O(n * log(n)) for n data points.Worst case time complexity: O(n^2) for n data points.Worst case space complexity: O(n) for n data points.EA default implementation of squared distance given two points and a . Builds a KdTreeo from a list of pairs of points (of type p) and values (of type v) using a default squared distance function .Average complexity:  O(n * log(n)) for n data points.Worst case time complexity: O(n^2) for n data points.Worst case space complexity: O(n) for n data points."Inserts a point-value pair into 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 k-d map, check out Data.KdMap.Dynamic..Average complexity:  O(log(n)) for n data points.Worst case time complexity: O(n) for n data points.+Inserts a list of point-value pairs into a z. This can potentially cause the internal tree structure to become unbalanced, which leads to inefficient point queries.Average complexity:  O(n * log(n)) for n data points.Worst case time complexity: O(n^2) for n data points.3Returns a list of all the point-value pairs in the .Time complexity: O(n) for n data points.Returns all points in the .Time complexity: O(n) for n data points.Returns all values in the .Time complexity: O(n) for n data points.Given a 9 and a query point, returns the point-value pair in the % with the point nearest to the query.Average time complexity:  O(log(n)) for n data points.Worst case time complexity: O(n) for n data points.#Throws error if called on an empty .Given a E, a query point, and a radius, returns all point-value pairs in the 9 with points within the given radius of the query point.0Points are not returned in any particular order.Worst case time complexity: O(n) for nB data points and a radius that spans all points in the structure.Given a , a query point, and a number k, returns the k9 point-value pairs with the nearest points to the query.INeighbors are returned in order of increasing distance from query point.Average time complexity: log(k) * log(n) for k( nearest neighbors on a structure with n data points.Worst case time complexity:  n * log(k) for k( nearest neighbors on a structure with n data points.!Finds all point-value pairs in a e with points within a given range, where the range is specified as a set of lower and upper bounds.0Points are not returned in any particular order.Worst case time complexity: O(n): 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./Returns the number of point-value pairs in the .Time complexity: O(1)Returns NM if tree structure adheres to k-d tree properties. For internal testing use./OPQRS TU V WXradius query pointClist of point-value pairs with points within given radius of querylower bounds of rangeupper bounds of range%point-value pairs within given rangeYZ[\]^_     $OPQRS TU V WXYZ[\]^_Safe0A k--d tree structure that stores points of type p with axis values of type a.Builds an empty . Builds an empty 3 using a user-specified squared distance function.! Builds a  with a single point." Builds a G with a single point using a user-specified squared distance function.$ Builds a G from a list of data points using a default squared distance function .Average complexity:  O(n * log(n)) for n data points.Worst case time complexity: O(n^2) for n data points.Worst case space complexity: O(n) for n data points.% Builds a N from a list of data points using a user-specified squared distance function.Average time complexity:  O(n * log(n)) for n data points.Worst case time complexity: O(n^2) for n data points.Worst case space complexity: O(n) for n data points.&Inserts a point into 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 k-d tree, check out Data.KdTree.Dynamic..Average complexity:  O(log(n)) for n data points.Worse case time complexity: O(n) for n data points.' Inserts a list of points into a z. This can potentially cause the internal tree structure to become unbalanced, which leads to inefficient point queries.Average complexity:  O(n * log(n)) for n data points.Worst case time complexity: O(n^2) for n data points.(Given a 6 and a query point, returns the nearest point in the  to the query point.Average time complexity:  O(log(n)) for n data points.Worst case time complexity: O(n) for n data points.&Throws an error if called on an empty .)Given a :, a query point, and a radius, returns all points in the 6 that are within the given radius of the query point.0Points are not returned in any particular order.Worst case time complexity: O(n) for nE data points and a radius that subsumes all points in the structure.*Given a , a query point, and a number k, returns the k nearest points in the  to the query point.INeighbors are returned in order of increasing distance from query point.Average time complexity: log(k) * log(n) for k( nearest neighbors on a structure with n data points.Worst case time complexity:  n * log(k) for k( nearest neighbors on a structure with n data points.+Finds all points in a d with points within a given range, where the range is specified as a set of lower and upper bounds.0Points are not returned in any particular order.Worst case time complexity: O(n): for n data points and a range that spans all the points.,(Returns a list of all the points in the .Time complexity: O(n) for n data points.-&Returns the number of elements in the .Time complexity: O(1)` !"#$2non-empty list of data points to be stored in the k-d tree%&'()radius query point8list of points in tree with given radius of query point*+lower bounds of rangeupper bounds of rangeall points within given range,-abc !"#$%&'()*+,- !"$%&'()*+,#-` !"#$%&'()*+,-abcSafe0. A dynamic k--d tree structure that stores points of type p with axis values of type a?. Additionally, each point is associated with a value of type v./3Performs a foldr over each point-value pair in the ..0Generates an empty .) with a user-specified distance function.1Returns whether the . is empty.2 Generates a .J with a single point-value pair using a user-specified distance function.3Generates an empty .$ with the default distance function.4 Generates a .E with a single point-value pair using the default distance function.5#Adds a given point-value pair to a ..'Average time complexity per insert for n inserts:  O(log^2(n)).6Same as 5&, but takes point and value as a pair.7Given a .9 and a query point, returns the point-value pair in the .% with the point nearest to the query.Average time complexity:  O(log^2(n)).8Given a ., a query point, and a number k, returns the k8 point-value pairs with the nearest points to the query.INeighbors are returned in order of increasing distance from query point.Average time complexity: log(k) * log^2(n) for k( nearest neighbors on a structure with n data points.Worst case time complexity:  n * log(k) for k( nearest neighbors on a structure with n data points.9Given a .E, a query point, and a radius, returns all point-value pairs in the KdTree9 with points within the given radius of the query point.0Points are not returned in any particular order.Worst case time complexity: O(n) for n data points.:!Finds all point-value pairs in a .e with points within a given range, where the range is specified as a set of lower and upper bounds.0Points are not returned in any particular order.Worst case time complexity: O(n): for n data points and a range that spans all the points.;&Returns the number of elements in the ..Time complexity: O(1)<3Returns a list of all the point-value pairs in the ..Time complexity: O(n) for n data points.=Returns all points in the ..Time complexity: O(n) for n data points.>Returns all values in the ..Time complexity: O(n) for n data points.?-Inserts a list of point-value pairs into the ..MTODO: This will be made far more efficient than simply repeatedly inserting.@Returns size of each internal kG-d tree that makes up the dynamic structure. For internal testing use..defgh/0123456789:lower bounds of rangeupper bounds of range%point-value pairs within given range;<=>?@ijklm./0123456789:;<=>?@.340256?798:<=>1;/@.defgh/0123456789:;<=>?@ijklmSafe A A dynamic k--d tree structure that stores points of type p with axis values of type a.BGenerates an empty A) with a user-specified distance function.CGenerates an empty A$ with the default distance function.DReturns whether the A is empty.E Generates a A? with a single point using a user-specified distance function.F Generates a A: with a single point using the default distance function.GAdds a given point to a A.'Average time complexity per insert for n inserts:  O(log^2(n)).HGiven a A6 and a query point, returns the nearest point in the A to the query point.Average time complexity:  O(log^2(n)).IGiven a A, a query point, and a number k, returns the k nearest points in the A to the query point.INeighbors are returned in order of increasing distance from query point.Average time complexity: log(k) * log^2(n) for k( nearest neighbors on a structure with n data points.Worst case time complexity:  n * log(k) for k( nearest neighbors on a structure with n data points.JGiven a A:, a query point, and a radius, returns all points in the A7 that are within the given radius of the query points.0Points are not returned in any particular order.Worst case time complexity: O(n) for n data points.KFinds all points in a Ad with points within a given range, where the range is specified as a set of lower and upper bounds.0Points are not returned in any particular order.Worst case time complexity: O(n): for n data points and a range that spans all the points.L&Returns the number of elements in the A.Time complexity: O(1)M(Returns a list of all the points in the A.Time complexity: O(n)AnBCDEFGHIJKlower bounds of rangeupper bounds of rangeall points within given rangeLMopABCDEFGHIJKLMACFBEGHJIKMDLAnBCDEFGHIJKLMopq       !" #!$% !&'$ !#()*+,-./0123456789:;<=>+,?56789<;@kdt_C6horgNY3Hf7aRibsHW07WData.KdMap.StaticData.KdTree.StaticData.KdMap.DynamicData.KdTree.DynamicKdMapKdTreeSquaredDistanceFn PointAsListFnTreeNode _treeLeft _treePoint _axisValue _treeRightEmpty foldrWithKeyempty emptyWithDistnullsingletonWithDist singleton buildWithDistdefaultSqrDistbuildinsertUnbalancedbatchInsertUnbalancedassocskeyselemsnearestinRadiuskNearestinRangesizeisValidtoListinsert insertPair batchInsert subtreeSizesghc-prim GHC.TypesTrue _pointAsList_distSqr _rootNode_size mapTreeNode foldrTreeNodetraverseTreeNode quickselectassocsInternalisTreeNodeValid$fTraversableKdMap$fFoldableKdMap$fFunctorKdMap $fShowKdMap $fNFDataKdMap$fNFDataTreeNode$fFoldableKdTree $fShowKdTree$fNFDataKdTree_trees _numNodes