π End-to-end encrypted cloud for everything.
Dart 2faandroidauthye2eeencryptionend-to-end-encryptionfluttergolanggoogle-photosgoogle-photos-alternativeiosopensourcephotosprivacyprivacy-toolstypescriptzero-knowledge
use std::cmp::Ordering;
use std::collections::BTreeMap;
use std::fs;
use std::path::Path;
use unicode_normalization::UnicodeNormalization;
use unicode_normalization::char::is_combining_mark;
use crate::binary::{ByteReader, f32_at, range, u16_at, u24_at, u32_at};
use crate::{Coordinate, CountryCode, Error};
const MAGIC: &[u8; 4] = b"CITY";
const VERSION: u16 = 2;
const HEADER_LEN: usize = 76;
const NODE_LEN: usize = 3;
const POINT_LEN: usize = 15;
const NAME_OFFSET_LEN: usize = 3;
const MAX_U24: usize = 0x00ff_ffff;
const MAX_CATCHMENT_KM: f64 = 30.0;
const MAX_OVERRIDE_DISTANCE_KM: f64 = 3.0;
const SECTION: &str = "city index";
#[derive(Clone, Debug, PartialEq)]
pub struct City {
pub point_index: u32,
pub source_id: u32,
pub name: String,
pub country_name: String,
pub country_code: CountryCode,
pub latitude: f64,
pub longitude: f64,
pub rank: u8,
}
#[derive(Clone, Debug, PartialEq)]
pub struct CityMatch {
pub city: City,
pub coordinate_indices: Vec<u32>,
}
#[derive(Clone, Copy, Debug)]
struct Layout {
point_count: usize,
override_count: usize,
name_count: usize,
country_count: usize,
nodes: usize,
points: usize,
name_offsets: usize,
names: usize,
country_offsets: usize,
countries: usize,
country_codes: usize,
rank_ends: [usize; 4],
}
#[derive(Clone, Copy)]
struct Point {
latitude: f32,
longitude: f32,
name: usize,
country: usize,
source_id: u32,
}
#[derive(Clone, Copy)]
struct SearchBounds {
minimum_latitude: f64,
maximum_latitude: f64,
minimum_longitude: f64,
maximum_longitude: f64,
}
#[derive(Clone, Copy)]
struct Tree {
nodes: usize,
node_count: usize,
}
impl SearchBounds {
const fn new(
minimum_latitude: f64,
maximum_latitude: f64,
minimum_longitude: f64,
maximum_longitude: f64,
) -> Self {
Self {
minimum_latitude,
maximum_latitude,
minimum_longitude,
maximum_longitude,
}
}
}
pub(crate) struct SearchPattern {
characters: Vec<char>,
fallback: Vec<usize>,
}
impl SearchPattern {
pub(crate) fn new(query: &str) -> Option<Self> {
let characters: Vec<char> = search_characters(query).collect();
if characters.is_empty() {
return None;
}
let mut fallback = vec![0; characters.len()];
let mut matched = 0;
for index in 1..characters.len() {
while matched > 0 && characters[index] != characters[matched] {
matched = fallback[matched - 1];
}
if characters[index] == characters[matched] {
matched += 1;
fallback[index] = matched;
}
}
Some(Self {
characters,
fallback,
})
}
pub(crate) fn matches(&self, value: &str) -> bool {
let mut matched = 0;
for character in search_characters(value) {
while matched > 0 && character != self.characters[matched] {
matched = self.fallback[matched - 1];
}
if character == self.characters[matched] {
matched += 1;
if matched == self.characters.len() {
return true;
}
}
}
false
}
}
fn search_characters(value: &str) -> impl Iterator<Item = char> + '_ {
value
.nfd()
.filter(|&character| !is_combining_mark(character))
.flat_map(char::to_lowercase)
}
pub fn normalize_search_text(value: &str) -> String {
search_characters(value).collect()
}
pub struct CityIndex {
bytes: Box<[u8]>,
layout: Layout,
}
impl CityIndex {
pub fn from_path(path: impl AsRef<Path>) -> crate::Result<Self> {
Self::from_bytes(fs::read(path)?)
}
pub fn from_bytes(bytes: impl Into<Box<[u8]>>) -> crate::Result<Self> {
let bytes = bytes.into();
let layout = validate(&bytes)?;
Ok(Self { bytes, layout })
}
pub const fn len(&self) -> usize {
self.layout.point_count
}
pub const fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn search(&self, query: &str, limit: usize) -> Vec<City> {
if limit == 0 {
return Vec::new();
}
let matching_names = self.matching_names(query);
if no_names_match(&matching_names) {
return Vec::new();
}
let mut cities = Vec::new();
for point_index in 0..self.layout.point_count {
let point = self.point(point_index);
if matching_names
.as_ref()
.is_none_or(|matches| matches[point.name])
{
cities.push(self.city(point_index));
if cities.len() == limit {
break;
}
}
}
cities
}
pub fn country_names(&self) -> impl Iterator<Item = (CountryCode, &str)> {
(0..self.layout.country_count).map(|index| (self.country_code(index), self.country(index)))
}
pub fn country_name(&self, code: CountryCode) -> Option<&str> {
self.country_names()
.find(|&(candidate, _)| candidate == code)
.map(|(_, name)| name)
}
pub fn match_coordinates(&self, coordinates: &[Coordinate], query: &str) -> Vec<CityMatch> {
self.match_coordinates_in(coordinates, query, self.tree(), MAX_CATCHMENT_KM)
}
pub fn match_override_coordinates(
&self,
coordinates: &[Coordinate],
query: &str,
) -> Vec<CityMatch> {
self.match_coordinates_in(
coordinates,
query,
self.override_tree(),
MAX_OVERRIDE_DISTANCE_KM,
)
}
fn match_coordinates_in(
&self,
coordinates: &[Coordinate],
query: &str,
tree: Tree,
maximum_distance_km: f64,
) -> Vec<CityMatch> {
if coordinates.is_empty() {
return Vec::new();
}
let matching_names = self.matching_names(query);
if no_names_match(&matching_names) {
return Vec::new();
}
let mut matches = BTreeMap::<usize, Vec<u32>>::new();
let mut candidates = Vec::new();
let mut eligible = Vec::new();
let mut stack = Vec::new();
for (coordinate_index, &coordinate) in coordinates.iter().enumerate() {
if !coordinate.is_valid() {
continue;
}
self.range_around(
tree,
coordinate,
maximum_distance_km,
&mut candidates,
&mut stack,
);
eligible.clear();
for &point_index in &candidates {
let point = self.point(point_index);
if matching_names
.as_ref()
.is_some_and(|matches| !matches[point.name])
{
continue;
}
let distance_km = distance_km(
coordinate.latitude,
coordinate.longitude,
f64::from(point.latitude),
f64::from(point.longitude),
);
let rank = self.rank(point_index);
if distance_km <= maximum_distance_km.min(catchment_km(rank)) {
eligible.push(Candidate {
point: point_index,
distance_km,
rank,
source_id: point.source_id,
});
}
}
let Some(nearest) = eligible
.iter()
.map(|candidate| candidate.distance_km)
.reduce(f64::min)
else {
continue;
};
let prominence_window = (0.5 + nearest * 0.25).min(2.0);
#[expect(
clippy::expect_used,
reason = "The nearest candidate is included in the prominence window"
)]
let best = eligible
.iter()
.filter(|candidate| candidate.distance_km <= nearest + prominence_window)
.min_by(compare_candidates)
.expect("eligible candidates are nonempty");
matches
.entry(best.point)
.or_default()
.push(coordinate_index as u32);
}
matches
.into_iter()
.map(|(point, coordinate_indices)| CityMatch {
city: self.city(point),
coordinate_indices,
})
.collect()
}
fn matching_names(&self, query: &str) -> Option<Vec<bool>> {
let pattern = SearchPattern::new(query)?;
Some(
(0..self.layout.name_count)
.map(|index| {
let (name, alias) = self.name_parts(index);
pattern.matches(name) || alias.is_some_and(|alias| pattern.matches(alias))
})
.collect(),
)
}
fn range_around(
&self,
tree: Tree,
coordinate: Coordinate,
maximum_distance_km: f64,
result: &mut Vec<usize>,
stack: &mut Vec<(usize, usize, u8)>,
) {
result.clear();
let latitude_delta = maximum_distance_km / 110.574;
let longitude_scale = coordinate.latitude.to_radians().cos().abs().max(0.01);
let longitude_delta = (maximum_distance_km / (111.320 * longitude_scale)).min(180.0);
let minimum_latitude = (coordinate.latitude - latitude_delta).max(-90.0);
let maximum_latitude = (coordinate.latitude + latitude_delta).min(90.0);
if longitude_delta >= 180.0 {
self.range_into(
tree,
SearchBounds::new(minimum_latitude, maximum_latitude, -180.0, 180.0),
result,
stack,
);
return;
}
let minimum_longitude = coordinate.longitude - longitude_delta;
let maximum_longitude = coordinate.longitude + longitude_delta;
if minimum_longitude < -180.0 {
self.range_into(
tree,
SearchBounds::new(
minimum_latitude,
maximum_latitude,
minimum_longitude + 360.0,
180.0,
),
result,
stack,
);
self.range_into(
tree,
SearchBounds::new(
minimum_latitude,
maximum_latitude,
-180.0,
maximum_longitude,
),
result,
stack,
);
} else if maximum_longitude > 180.0 {
self.range_into(
tree,
SearchBounds::new(minimum_latitude, maximum_latitude, minimum_longitude, 180.0),
result,
stack,
);
self.range_into(
tree,
SearchBounds::new(
minimum_latitude,
maximum_latitude,
-180.0,
maximum_longitude - 360.0,
),
result,
stack,
);
} else {
self.range_into(
tree,
SearchBounds::new(
minimum_latitude,
maximum_latitude,
minimum_longitude,
maximum_longitude,
),
result,
stack,
);
}
}
fn range_into(
&self,
tree: Tree,
bounds: SearchBounds,
result: &mut Vec<usize>,
stack: &mut Vec<(usize, usize, u8)>,
) {
if tree.node_count == 0 {
return;
}
stack.clear();
stack.push((0, tree.node_count, 0));
while let Some((node_index, subtree_size, axis)) = stack.pop() {
let point_index = self.node(tree, node_index);
let point = self.point(point_index);
let latitude = f64::from(point.latitude);
let longitude = f64::from(point.longitude);
if (bounds.minimum_latitude..=bounds.maximum_latitude).contains(&latitude)
&& (bounds.minimum_longitude..=bounds.maximum_longitude).contains(&longitude)
{
result.push(point_index);
}
let left_size = subtree_size / 2;
let right_size = subtree_size - left_size - 1;
let next_axis = axis ^ 1;
if axis == 0 {
if bounds.minimum_latitude <= latitude && left_size > 0 {
stack.push((node_index + 1, left_size, next_axis));
}
if bounds.maximum_latitude >= latitude && right_size > 0 {
stack.push((node_index + left_size + 1, right_size, next_axis));
}
} else {
if bounds.minimum_longitude <= longitude && left_size > 0 {
stack.push((node_index + 1, left_size, next_axis));
}
if bounds.maximum_longitude >= longitude && right_size > 0 {
stack.push((node_index + left_size + 1, right_size, next_axis));
}
}
}
}
fn city(&self, point_index: usize) -> City {
let point = self.point(point_index);
City {
point_index: point_index as u32,
source_id: point.source_id,
name: self.name(point.name).to_owned(),
country_name: self.country(point.country).to_owned(),
country_code: self.country_code(point.country),
latitude: f64::from(point.latitude),
longitude: f64::from(point.longitude),
rank: self.rank(point_index),
}
}
fn tree(&self) -> Tree {
Tree {
nodes: self.layout.nodes,
node_count: self.layout.point_count,
}
}
fn override_tree(&self) -> Tree {
Tree {
nodes: self.layout.nodes + self.layout.point_count * NODE_LEN,
node_count: self.layout.override_count,
}
}
fn node(&self, tree: Tree, index: usize) -> usize {
ByteReader::at(&self.bytes, tree.nodes + index * NODE_LEN).u24() as usize
}
fn point(&self, index: usize) -> Point {
let mut reader = ByteReader::at(&self.bytes, self.layout.points + index * POINT_LEN);
Point {
latitude: reader.f32(),
longitude: reader.f32(),
name: reader.u24() as usize,
country: usize::from(reader.byte()),
source_id: reader.u24(),
}
}
fn rank(&self, point_index: usize) -> u8 {
self.layout
.rank_ends
.iter()
.position(|&end| point_index < end)
.map_or(0, |index| 4 - index as u8)
}
fn name(&self, index: usize) -> &str {
self.name_parts(index).0
}
fn name_parts(&self, index: usize) -> (&str, Option<&str>) {
let value = table_entry_u24(
&self.bytes,
self.layout.name_offsets,
self.layout.names,
index,
);
value
.split_once('\0')
.map_or((value, None), |(name, alias)| (name, Some(alias)))
}
fn country(&self, index: usize) -> &str {
table_entry_u32(
&self.bytes,
self.layout.country_offsets,
self.layout.countries,
index,
)
}
fn country_code(&self, index: usize) -> CountryCode {
let offset = self.layout.country_codes + index * 2;
CountryCode::from_validated([self.bytes[offset], self.bytes[offset + 1]])
}
}
#[derive(Clone, Copy)]
struct Candidate {
point: usize,
distance_km: f64,
rank: u8,
source_id: u32,
}
fn no_names_match(matching_names: &Option<Vec<bool>>) -> bool {
matching_names
.as_ref()
.is_some_and(|matches| !matches.iter().any(|&matched| matched))
}
fn validate(bytes: &[u8]) -> crate::Result<Layout> {
if bytes.len() < HEADER_LEN {
return Err(invalid("truncated"));
}
if &bytes[..4] != MAGIC {
return Err(invalid("invalid magic"));
}
let version = read_u16(bytes, 4)?;
if version != VERSION {
return Err(Error::invalid(
SECTION,
format!("unsupported format version {version}"),
));
}
if usize::from(read_u16(bytes, 6)?) != HEADER_LEN {
return Err(invalid("unexpected header length"));
}
if usize::from(read_u16(bytes, 18)?) != POINT_LEN
|| usize::from(read_u16(bytes, 20)?) != NODE_LEN
|| usize::from(read_u16(bytes, 22)?) != NAME_OFFSET_LEN
{
return Err(invalid("unexpected record length"));
}
let layout = Layout {
point_count: read_usize(bytes, 8)?,
override_count: read_usize(bytes, 72)?,
name_count: read_usize(bytes, 12)?,
country_count: usize::from(read_u16(bytes, 16)?),
nodes: read_usize(bytes, 24)?,
points: read_usize(bytes, 28)?,
name_offsets: read_usize(bytes, 32)?,
names: read_usize(bytes, 36)?,
country_offsets: read_usize(bytes, 40)?,
countries: read_usize(bytes, 44)?,
country_codes: read_usize(bytes, 48)?,
rank_ends: [
read_usize(bytes, 56)?,
read_usize(bytes, 60)?,
read_usize(bytes, 64)?,
read_usize(bytes, 68)?,
],
};
let declared_length = read_usize(bytes, 52)?;
validate_sections(bytes, layout, declared_length)?;
validate_strings(bytes, layout)?;
validate_points(bytes, layout)?;
validate_tree(
bytes,
layout,
Tree {
nodes: layout.nodes,
node_count: layout.point_count,
},
)?;
validate_tree(
bytes,
layout,
Tree {
nodes: layout.nodes + layout.point_count * NODE_LEN,
node_count: layout.override_count,
},
)?;
Ok(layout)
}
fn validate_sections(bytes: &[u8], layout: Layout, declared_length: usize) -> crate::Result<()> {
if layout.point_count > MAX_U24
|| layout.name_count > MAX_U24
|| layout.override_count > layout.point_count
|| layout.country_count > 256
|| (layout.point_count > 0 && (layout.name_count == 0 || layout.country_count == 0))
|| layout.rank_ends[3] > layout.point_count
|| layout.rank_ends.windows(2).any(|ends| ends[0] > ends[1])
{
return Err(invalid("invalid section count"));
}
let nodes = range(layout.nodes, layout.point_count, NODE_LEN)
.ok_or(invalid("node section overflow"))?;
let override_nodes = range(nodes.end, layout.override_count, NODE_LEN)
.ok_or(invalid("override-node section overflow"))?;
let points = range(layout.points, layout.point_count, POINT_LEN)
.ok_or(invalid("point section overflow"))?;
let name_offsets = offset_table_range(layout.name_offsets, layout.name_count, NAME_OFFSET_LEN)?;
let name_bytes = terminal_offset(
bytes,
layout.name_offsets,
layout.name_count,
NAME_OFFSET_LEN,
)?;
let country_offsets = offset_table_range(layout.country_offsets, layout.country_count, 4)?;
let country_bytes = terminal_offset(bytes, layout.country_offsets, layout.country_count, 4)?;
let country_codes = range(layout.country_codes, layout.country_count, 2)
.ok_or(invalid("country-code section overflow"))?;
let names_end = layout
.names
.checked_add(name_bytes)
.ok_or(invalid("name section overflow"))?;
let countries_end = layout
.countries
.checked_add(country_bytes)
.ok_or(invalid("country section overflow"))?;
if layout.nodes != HEADER_LEN
|| layout.points != override_nodes.end
|| layout.name_offsets != points.end
|| layout.names != name_offsets.end
|| layout.country_offsets != names_end
|| layout.countries != country_offsets.end
|| layout.country_codes != countries_end
|| country_codes.end != bytes.len()
|| declared_length != bytes.len()
{
return Err(invalid("sections are not contiguous"));
}
Ok(())
}
fn validate_strings(bytes: &[u8], layout: Layout) -> crate::Result<()> {
validate_table(
bytes,
layout.name_offsets,
layout.names,
layout.name_count,
NAME_OFFSET_LEN,
"name table",
)?;
validate_table(
bytes,
layout.country_offsets,
layout.countries,
layout.country_count,
4,
"country-name table",
)?;
for index in 0..layout.name_count {
let value = table_entry_u24(bytes, layout.name_offsets, layout.names, index);
if value.split('\0').any(str::is_empty) {
return Err(invalid("invalid city name"));
}
}
let mut seen_codes = [false; 26 * 26];
for index in 0..layout.country_count {
let offset = layout.country_codes + index * 2;
let code = [bytes[offset], bytes[offset + 1]];
if !code.iter().all(u8::is_ascii_uppercase) {
return Err(invalid("invalid country code"));
}
let slot = usize::from(code[0] - b'A') * 26 + usize::from(code[1] - b'A');
if seen_codes[slot] {
return Err(invalid("duplicate country code"));
}
seen_codes[slot] = true;
}
Ok(())
}
fn validate_points(bytes: &[u8], layout: Layout) -> crate::Result<()> {
for index in 0..layout.point_count {
let offset = layout.points + index * POINT_LEN;
let latitude = f32_at(bytes, offset).ok_or(invalid("truncated"))?;
let longitude = f32_at(bytes, offset + 4).ok_or(invalid("truncated"))?;
let name = u24_at(bytes, offset + 8).ok_or(invalid("truncated"))? as usize;
let country = usize::from(bytes[offset + 11]);
if !latitude.is_finite()
|| !(-90.0..=90.0).contains(&latitude)
|| !longitude.is_finite()
|| !(-180.0..=180.0).contains(&longitude)
|| name >= layout.name_count
|| country >= layout.country_count
{
return Err(invalid("invalid city point"));
}
}
Ok(())
}
fn validate_tree(bytes: &[u8], layout: Layout, tree: Tree) -> crate::Result<()> {
if tree.node_count == 0 {
return Ok(());
}
let mut visited_points = vec![false; layout.point_count];
let mut stack = vec![(0usize, tree.node_count, 0u8, -90.0, 90.0, -180.0, 180.0)];
while let Some((node_index, size, axis, min_lat, max_lat, min_lng, max_lng)) = stack.pop() {
if size == 0
|| node_index
.checked_add(size)
.is_none_or(|end| end > tree.node_count)
{
return Err(invalid("invalid tree layout"));
}
let point =
u24_at(bytes, tree.nodes + node_index * NODE_LEN).ok_or(invalid("truncated"))? as usize;
if point >= layout.point_count || visited_points[point] {
return Err(invalid("invalid tree node"));
}
visited_points[point] = true;
let mut reader = ByteReader::at(bytes, layout.points + point * POINT_LEN);
let latitude = f64::from(reader.f32());
let longitude = f64::from(reader.f32());
if !(min_lat..=max_lat).contains(&latitude) || !(min_lng..=max_lng).contains(&longitude) {
return Err(invalid("invalid KD ordering"));
}
let left_size = size / 2;
let right_size = size - left_size - 1;
let next_axis = axis ^ 1;
if axis == 0 {
if left_size > 0 {
stack.push((
node_index + 1,
left_size,
next_axis,
min_lat,
latitude,
min_lng,
max_lng,
));
}
if right_size > 0 {
stack.push((
node_index + left_size + 1,
right_size,
next_axis,
latitude,
max_lat,
min_lng,
max_lng,
));
}
} else {
if left_size > 0 {
stack.push((
node_index + 1,
left_size,
next_axis,
min_lat,
max_lat,
min_lng,
longitude,
));
}
if right_size > 0 {
stack.push((
node_index + left_size + 1,
right_size,
next_axis,
min_lat,
max_lat,
longitude,
max_lng,
));
}
}
}
if tree.node_count == layout.point_count && visited_points.iter().any(|&visited| !visited) {
return Err(invalid("tree does not cover every point"));
}
Ok(())
}
fn validate_table(
bytes: &[u8],
offsets: usize,
blob: usize,
count: usize,
offset_len: usize,
name: &'static str,
) -> crate::Result<()> {
let blob_length = terminal_offset(bytes, offsets, count, offset_len)?;
let mut previous = 0;
for index in 0..count {
let start = string_offset(bytes, offsets + index * offset_len, offset_len)?;
let end = string_offset(bytes, offsets + (index + 1) * offset_len, offset_len)?;
if start != previous || end <= start || end > blob_length {
return Err(invalid("invalid string offsets"));
}
std::str::from_utf8(&bytes[blob + start..blob + end])
.map_err(|_| Error::invalid(SECTION, format!("invalid UTF-8 in {name}")))?;
previous = end;
}
Ok(())
}
fn offset_table_range(
offset: usize,
count: usize,
stride: usize,
) -> crate::Result<std::ops::Range<usize>> {
range(
offset,
count
.checked_add(1)
.ok_or(invalid("offset count overflow"))?,
stride,
)
.ok_or(invalid("offset table overflow"))
}
fn terminal_offset(
bytes: &[u8],
offset: usize,
count: usize,
stride: usize,
) -> crate::Result<usize> {
let terminal = offset
.checked_add(
count
.checked_mul(stride)
.ok_or(invalid("offset table overflow"))?,
)
.ok_or(invalid("offset table overflow"))?;
string_offset(bytes, terminal, stride)
}
fn string_offset(bytes: &[u8], offset: usize, length: usize) -> crate::Result<usize> {
match length {
NAME_OFFSET_LEN => Ok(u24_at(bytes, offset).ok_or(invalid("truncated"))? as usize),
4 => Ok(u32_at(bytes, offset).ok_or(invalid("truncated"))? as usize),
_ => unreachable!("validated offset length"),
}
}
fn table_entry_u24(bytes: &[u8], offsets: usize, blob: usize, index: usize) -> &str {
let mut reader = ByteReader::at(bytes, offsets + index * NAME_OFFSET_LEN);
let start = reader.u24() as usize;
let end = reader.u24() as usize;
#[expect(
clippy::expect_used,
reason = "Index construction validates the string table as UTF-8"
)]
std::str::from_utf8(&bytes[blob + start..blob + end]).expect("validated UTF-8")
}
fn table_entry_u32(bytes: &[u8], offsets: usize, blob: usize, index: usize) -> &str {
let mut reader = ByteReader::at(bytes, offsets + index * 4);
let start = reader.u32() as usize;
let end = reader.u32() as usize;
#[expect(
clippy::expect_used,
reason = "Index construction validates the string table as UTF-8"
)]
std::str::from_utf8(&bytes[blob + start..blob + end]).expect("validated UTF-8")
}
fn read_u16(bytes: &[u8], offset: usize) -> crate::Result<u16> {
u16_at(bytes, offset).ok_or(invalid("truncated"))
}
fn read_usize(bytes: &[u8], offset: usize) -> crate::Result<usize> {
Ok(u32_at(bytes, offset).ok_or(invalid("truncated"))? as usize)
}
fn invalid(reason: &'static str) -> Error {
Error::invalid(SECTION, reason)
}
#[expect(
clippy::trivially_copy_pass_by_ref,
reason = "Iterator::min_by passes references to borrowed candidates"
)]
fn compare_candidates(left: &&Candidate, right: &&Candidate) -> Ordering {
right
.rank
.cmp(&left.rank)
.then_with(|| left.distance_km.total_cmp(&right.distance_km))
.then_with(|| left.source_id.cmp(&right.source_id))
}
fn catchment_km(rank: u8) -> f64 {
[8.0, 10.0, 14.0, 20.0, 30.0][usize::from(rank)]
}
pub(crate) fn distance_km(lat1: f64, lng1: f64, lat2: f64, lng2: f64) -> f64 {
let lat1 = lat1.to_radians();
let lat2 = lat2.to_radians();
let delta_latitude = lat2 - lat1;
let delta_longitude = (lng2 - lng1).to_radians();
let a = (delta_latitude / 2.0).sin().powi(2)
+ lat1.cos() * lat2.cos() * (delta_longitude / 2.0).sin().powi(2);
6371.0 * 2.0 * a.sqrt().atan2((1.0 - a).sqrt())
}