(self, k, x, PQ, root)
| 317 | return nearest |
| 318 | |
| 319 | def _knn(self, k, x, PQ, root): |
| 320 | dist = self.metric |
| 321 | dist_to_ball = dist(x, root.centroid) - root.radius |
| 322 | dist_to_farthest_neighbor = dist(x, PQ.peek()["key"]) if len(PQ) > 0 else np.inf |
| 323 | |
| 324 | if dist_to_ball >= dist_to_farthest_neighbor and len(PQ) == k: |
| 325 | return PQ |
| 326 | if root.is_leaf: |
| 327 | targets = [None] * len(root.data) if root.targets is None else root.targets |
| 328 | for point, target in zip(root.data, targets): |
| 329 | dist_to_x = dist(x, point) |
| 330 | if len(PQ) == k and dist_to_x < dist_to_farthest_neighbor: |
| 331 | PQ.push(key=point, val=target, priority=dist_to_x) |
| 332 | else: |
| 333 | PQ.push(key=point, val=target, priority=dist_to_x) |
| 334 | else: |
| 335 | l_closest = dist(x, root.left.centroid) < dist(x, root.right.centroid) |
| 336 | PQ = self._knn(k, x, PQ, root.left if l_closest else root.right) |
| 337 | PQ = self._knn(k, x, PQ, root.right if l_closest else root.left) |
| 338 | return PQ |
| 339 | |
| 340 | |
| 341 | ####################################################################### |
no test coverage detected