Update `nearest_node` interface

[mmiller-max]

This PR addresses and closes #45.

Changes

1. nearest_node updated so now only returns a single node for each point given. If a single point is given (whether a GeoLocation, vector of lat/lon, Node or node ID) then a tuple of (id, dist) is returned. If a vector of points is given, then a tuple of ([ids...], [dists...]) is returned.

2. Added nearest_nodes allows for the nearest n nodes. If a single point is given, returns a tuple of ([ids...], [dists...]). If a vector of points is given, returns a tuple of ([[ids...]...], [[dists...]...]).

3. Concretely type kdtree field of OSMGraph - improves performance

4. Quite a bit of refactoring including removing function return typing - we can let Julia work this out.

Performance

I've benchmarked each of these functions against main, and main with the kdtree field concretely typed. For each test below, the first time is main, the second is with kdtree concretely typed and the third is with the changes in this PR. It can be seen that in all cases the refactoring is faster and allocates less.

# nearest_node benchmark

using BenchmarkTools
using LightOSM

include("../test/stub.jl")

g = basic_osm_graph_stub()

point = GeoLocation(-38.07541, 145.3331)
@btime nearest_node($g, $point) 
# 568.536 ns (14 allocations: 912 bytes)
# 533.730 ns (14 allocations: 912 bytes)
# 488.462 ns (14 allocations: 864 bytes)

points = [GeoLocation(-38.07541, 145.3331)]
@btime nearest_node($g, $points) 
# 556.594 ns (13 allocations: 832 bytes)
# 512.807 ns (13 allocations: 832 bytes)
# 470.240 ns (11 allocations: 768 bytes)

point = [-38.07541, 145.3331]
@btime nearest_node($g, $point)
# 710.695 ns (17 allocations: 976 bytes)
# 666.665 ns (17 allocations: 976 bytes)
# 615.240 ns (16 allocations: 896 bytes)

point = [[-38.07541, 145.3331]]
@btime nearest_node($g, $point)
# 716.978 ns (17 allocations: 976 bytes)
# 673.116 ns (17 allocations: 976 bytes)
# 625.000 ns (15 allocations: 912 bytes)

node = first(values(g.nodes))
@btime nearest_node($g, $node)
# 706.543 ns (19 allocations: 1.25 KiB)
# 660.642 ns (19 allocations: 1.25 KiB)
# 499.352 ns (14 allocations: 928 bytes)

node_id = node.id
@btime nearest_node($g, $node_id)
# 704.764 ns (19 allocations: 1.25 KiB)
# 662.208 ns (19 allocations: 1.25 KiB)
# 500.865 ns (14 allocations: 928 bytes)

nodes = [node]
@btime nearest_node($g, $nodes)
# 706.858 ns (19 allocations: 1.25 KiB)
# 663.478 ns (19 allocations: 1.25 KiB)
# 507.337 ns (14 allocations: 928 bytes)

node_ids = [node_id]
@btime nearest_node($g, $node_ids)
# 684.007 ns (18 allocations: 1.19 KiB)
# 641.313 ns (18 allocations: 1.19 KiB)
# 486.964 ns (13 allocations: 864 bytes)

##############################################
# nearest_nodes (using nearest_node on main) #
##############################################

point = GeoLocation(-38.07541, 145.3331)
@btime nearest_nodes($g, $point, 2) 
# 583.331 ns (14 allocations: 960 bytes)
# 541.005 ns (14 allocations: 960 bytes)
# 514.974 ns (13 allocations: 848 bytes)

points = [GeoLocation(-38.07541, 145.3331)]
@btime nearest_nodes($g, $points, 2) 
# 583.105 ns (14 allocations: 960 bytes)
# 523.995 ns (13 allocations: 880 bytes)
# 496.778 ns (12 allocations: 816 bytes)

point = [-38.07541, 145.3331]
@btime nearest_nodes($g, $point, 2)
# 720.803 ns (17 allocations: 1.00 KiB)
# 676.282 ns (17 allocations: 1.00 KiB)
# 641.216 ns (15 allocations: 880 bytes)

point = [[-38.07541, 145.3331]]
@btime nearest_nodes($g, $point, 2)
# 723.684 ns (17 allocations: 1.00 KiB)
# 680.281 ns (17 allocations: 1.00 KiB)
# 655.280 ns (16 allocations: 960 bytes)

node = first(values(g.nodes))
@btime nearest_nodes($g, $node, 2)
# 724.500 ns (19 allocations: 1.28 KiB)
# 680.281 ns (19 allocations: 1.28 KiB)
# 532.630 ns (14 allocations: 944 bytes)

node_id = node.id
@btime nearest_nodes($g, $node_id, 2)
# 724.624 ns (19 allocations: 1.28 KiB)
# 681.563 ns (19 allocations: 1.28 KiB)
# 633.820 ns (14 allocations: 944 bytes)

nodes = [node]
@btime nearest_nodes($g, $nodes, 2)
# 726.779 ns (19 allocations: 1.28 KiB)
# 681.947 ns (19 allocations: 1.28 KiB)
# 586.111 ns (16 allocations: 1.05 KiB)

node_ids = [node_id]
@btime nearest_nodes($g, $node_ids, 2)
# 705.986 ns (18 allocations: 1.22 KiB)
# 659.638 ns (18 allocations: 1.22 KiB)
# 565.446 ns (15 allocations: 1008 bytes)

[codecov-commenter]

Codecov Report

Merging #63 (59c3da8) into master (076c7a2) will increase coverage by 0.65%. The diff coverage is 100.00%.

@@            Coverage Diff             @@
##           master      #63      +/-   ##
==========================================
+ Coverage   71.58%   72.24%   +0.65%     
==========================================
  Files          11       11              
  Lines         894      915      +21     
==========================================
+ Hits          640      661      +21     
  Misses        254      254              

Impacted Files	Coverage Δ
src/types.jl	79.16% <ø> (ø)
src/nearest_node.jl	100.00% <100.00%> (ø)

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 076c7a2...59c3da8. Read the comment docs.