1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

use crate::error::Error;
use crate::graph::node::NodeType;
use crate::graph::GetCellNode;
use h3ron::H3Cell;

/// find the nearest nodes in the graph
pub trait NearestGraphNodes {
    /// get an iterator over the closest corresponding nodes in the graph to the
    /// given cell. The iterator will return all nodes with the
    /// same, smallest `k` <= `max_distance_k` which are part of the graph.
    fn nearest_graph_nodes(
        &self,
        cell: &H3Cell,
        max_distance_k: u32,
    ) -> Result<NearestGraphNodesGetCellIter<Self>, Error>
    where
        Self: Sized;
}

pub struct NearestGraphNodesGetCellIter<'a, G> {
    graph: &'a G,
    neighbors_reversed: Vec<(u32, H3Cell)>,
    found_max_k: u32,
}

impl<'a, G> Iterator for NearestGraphNodesGetCellIter<'a, G>
where
    G: GetCellNode,
{
    type Item = (H3Cell, NodeType, u32);

    fn next(&mut self) -> Option<Self::Item> {
        while let Some((neighbor_k, neighbor_cell)) = self.neighbors_reversed.pop() {
            if neighbor_k > self.found_max_k {
                break;
            }

            if let Some(node_type) = self.graph.get_cell_node(&neighbor_cell) {
                self.found_max_k = neighbor_k;
                return Some((neighbor_cell, node_type, neighbor_k));
            }
        }
        None
    }
}

impl<G> NearestGraphNodes for G
where
    G: GetCellNode,
{
    fn nearest_graph_nodes(
        &self,
        cell: &H3Cell,
        max_distance_k: u32,
    ) -> Result<NearestGraphNodesGetCellIter<G>, Error> {
        let mut neighbors = cell.grid_disk_distances(0, max_distance_k)?;

        // reverse the order to gave the nearest neighbors first
        neighbors.sort_unstable_by_key(|neighbor| max_distance_k - neighbor.0);

        Ok(NearestGraphNodesGetCellIter {
            graph: self,
            neighbors_reversed: neighbors,
            found_max_k: max_distance_k,
        })
    }
}

#[cfg(test)]
mod tests {
    use crate::algorithm::NearestGraphNodes;
    use crate::graph::node::NodeType;
    use crate::graph::GetCellNode;
    use h3ron::collections::H3CellSet;
    use h3ron::{H3Cell, Index};

    impl GetCellNode for H3CellSet {
        fn get_cell_node(&self, cell: &H3Cell) -> Option<NodeType> {
            self.get(cell).map(|_| NodeType::OriginAndDestination)
        }
    }

    #[test]
    fn nearest_finds_given_cell_first() {
        let cell = H3Cell::new(0x89283080ddbffff_u64);
        let mut cellset = H3CellSet::default();
        for ring_cell in cell.grid_disk(3).unwrap().iter() {
            cellset.insert(ring_cell);
        }
        assert_eq!(cellset.nearest_graph_nodes(&cell, 3).unwrap().count(), 1);
        assert_eq!(
            cellset.nearest_graph_nodes(&cell, 3).unwrap().next(),
            Some((cell, NodeType::OriginAndDestination, 0))
        );
    }

    #[test]
    fn nearest_finds_all_with_same_k() {
        let cell = H3Cell::new(0x89283080ddbffff_u64);
        let mut cellset = H3CellSet::default();
        let mut expected = H3CellSet::default();
        for (_, ring_cell) in cell.grid_disk_distances(2, 3).unwrap().iter().take(2) {
            cellset.insert(*ring_cell);
            expected.insert(*ring_cell);
        }
        for (_, ring_cell) in cell.grid_disk_distances(4, 5).unwrap().iter().take(2) {
            cellset.insert(*ring_cell);
        }
        assert_eq!(cellset.nearest_graph_nodes(&cell, 8).unwrap().count(), 2);
        for (nearest_cell, _, _) in cellset.nearest_graph_nodes(&cell, 8).unwrap() {
            assert!(expected.contains(&nearest_cell));
        }
    }
}