1"""
  2# GeoKDTree
  3[![PyPI version](https://badge.fury.io/py/geokdtree.svg)](https://badge.fury.io/py/geokdtree)
  4[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
  5[![PyPI Downloads](https://pepy.tech/badge/geokdtree)](https://pypi.org/project/geokdtree/)
  6<!-- [![PyPI Downloads](https://img.shields.io/pypi/dm/geokdtree.svg?label=PyPI%20downloads)](https://pypi.org/project/geokdtree/) -->
  7
  8# GeoKDTree
  9
 10## Ultra-fast nearest-neighbor lookup for latitude/longitude data
 11
 12**GeoKDTree** is a lightweight, high-performance spatial indexing library for Python designed to find the *nearest geographic coordinate* from massive datasets in nanoseconds.
 13
 14It wraps a highly optimized KD-Tree with a geographic interface, allowing you to work directly with `(latitude, longitude)` pairs. No projections, no external dependencies, and no heavy GIS stacks.
 15
 16![geokdtree](https://raw.githubusercontent.com/connor-makowski/geokdtree/main/static/geokdtree.png)
 17
 18### Documentation
 19
 20- Docs: https://connor-makowski.github.io/geokdtree/geokdtree.html
 21- Git Repo: https://github.com/connor-makowski/geokdtree
 22
 23## Installation
 24
 25```bash
 26pip install geokdtree
 27```
 28
 29## Getting Started
 30
 31```python
 32from geokdtree import GeoKDTree
 33
 34example_points = [
 35    (34.0522, -118.2437),  # Los Angeles
 36    (40.7128, -74.0060),   # New York
 37    (37.7749, -122.4194),  # San Francisco
 38    (51.5074, -0.1278),    # London
 39    (48.8566, 2.3522),     # Paris
 40]
 41
 42geo_kd_tree = GeoKDTree(points=example_points)
 43
 44test_point = (47.6062, -122.3321)  # Seattle
 45# Find the index of the closest point in the original dataset
 46closest_idx = geo_kd_tree.closest_idx(test_point)
 47# Find the closest point itself
 48closest_point = geo_kd_tree.closest_point(test_point)
 49
 50print(f"Closest index (from original data) is {closest_idx}")
 51print(f"Closest point (from original data) is {closest_point}")
 52```
 53
 54## Why Use GeoKDTree?
 55
 56GeoKDTree is designed to solve one focused problem extremely well:
 57
 58**Fast nearest-neighbor lookup for latitude/longitude data at scale.**
 59
 60It is worth noting that the closest point found may not be the true closest point, but should be very close for most practical applications. See KD-Tree limitations for more details.
 61
 62### Extremely Fast Lookups
 63
 64Once constructed, nearest-neighbor queries consistently complete in **tens of nanoseconds**, even with very large datasets.
 65
 66Typical benchmark results from the included tests:
 67
 68| Number of Points | Build Time | Query Time |
 69| ---------------: | ---------: | ---------: |
 70|            1,000 |    ~1.7 ms |   ~0.02 ms |
 71|           10,000 |     ~25 ms |   ~0.05 ms |
 72|          100,000 |    ~350 ms |   ~0.05 ms |
 73|        1,000,000 |     ~6.8 s |   ~0.07 ms |
 74
 75This makes GeoKDTree well-suited for:
 76
 77* Real-time proximity queries
 78* Matching incoming coordinates against large reference datasets
 79* High-throughput geospatial APIs
 80* Pre-filtering before more expensive geospatial calculations
 81
 82> Exact timings depend on hardware, Python version, and data distribution. These values reflect typical results from the repository’s benchmarks.
 83
 84### Built for Geographic Coordinates
 85
 86GeoKDTree works directly with `(latitude, longitude)` pairs.
 87
 88You do **not** need to:
 89
 90* Project coordinates into planar space
 91* Use heavyweight GIS libraries
 92* Maintain custom spatial indexing code
 93
 94Just pass geographic coordinates and query.
 95
 96### Simple API, Minimal Overhead
 97
 98GeoKDTree intentionally keeps the API small and focused.
 99
100* Build once from a list of coordinates
101* Query nearest neighbors with a single method call
102* Retrieve indices or points directly from your original dataset
103
104There are no external C extensions or heavy dependencies, keeping installation and deployment simple.
105
106### Deterministic and Predictable Performance
107
108* Tree construction scales at approximately `O(n log n)`
109* Query performance scales at approximately `O(log n)`
110* No probabilistic approximations
111* No background indexing or caching
112
113This predictability is valuable for production systems where latency and reproducibility matter.
114
115## Supported Features
116
117See: https://connor-makowski.github.io/geokdtree/geokdtree.html
118
119## Contributing
120
121Issues, feature requests, and pull requests are welcome.
122Please open an issue to discuss changes or enhancements.
123
124# Development
125## Running Tests, Prettifying Code, and Updating Docs
126
127Make sure Docker is installed and running on a Unix system (Linux, MacOS, WSL2).
128
129- Create a docker container and drop into a shell
130    - `./run.sh`
131- Run all tests (see ./utils/test.sh)
132    - `./run.sh test`
133- Prettify the code (see ./utils/prettify.sh)
134    - `./run.sh prettify`
135- Update the docs (see ./utils/docs.sh)
136    - `./run.sh docs`
137
138- Note: You can and should modify the `Dockerfile` to test different python versions.
139
140"""
141
142try:
143    from geokdtree.cpp import GeoKDTree, KDTree
144
145    # print("Successfully imported from geokdtree.cpp. Using optimized implementation.")
146except ImportError:
147    # TODO: Find way to warn users if they were not able to build / import the C++ extension, as this will result in significantly slower performance.
148    # print("Unable to import geokdtree.cpp, falling back to pure Python implementation. This may result in significantly slower performance.")
149    from geokdtree.geokdtree import GeoKDTree
150    from geokdtree.kdtree import KDTree