geo/algorithm/relate/geomgraph/
node_map.rs

1use super::{CoordNode, CoordPos, EdgeEnd};
2use crate::{Coord, GeoFloat};
3
4use std::collections::BTreeMap;
5use std::fmt;
6use std::marker::PhantomData;
7
8/// A map of nodes, indexed by the coordinate of the node
9#[derive(Clone, PartialEq)]
10pub(crate) struct NodeMap<F, NF>
11where
12    F: GeoFloat,
13    NF: NodeFactory<F>,
14{
15    map: BTreeMap<NodeKey<F>, NF::Node>,
16    _node_factory: PhantomData<NF>,
17}
18
19/// Creates the node stored in `NodeMap`
20pub(crate) trait NodeFactory<F: GeoFloat>: PartialEq {
21    type Node;
22    fn create_node(coordinate: Coord<F>) -> Self::Node;
23}
24
25impl<F, NF> fmt::Debug for NodeMap<F, NF>
26where
27    F: GeoFloat,
28    NF: NodeFactory<F>,
29{
30    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
31        f.debug_struct("NodeMap")
32            .field("map.len()", &self.map.len())
33            .finish()
34    }
35}
36
37#[derive(Clone)]
38struct NodeKey<F: GeoFloat>(Coord<F>);
39
40impl<F: GeoFloat> std::cmp::Ord for NodeKey<F> {
41    fn cmp(&self, other: &NodeKey<F>) -> std::cmp::Ordering {
42        debug_assert!(!self.0.x.is_nan());
43        debug_assert!(!self.0.y.is_nan());
44        debug_assert!(!other.0.x.is_nan());
45        debug_assert!(!other.0.y.is_nan());
46        crate::utils::lex_cmp(&self.0, &other.0)
47    }
48}
49
50impl<F: GeoFloat> std::cmp::PartialOrd for NodeKey<F> {
51    fn partial_cmp(&self, other: &NodeKey<F>) -> Option<std::cmp::Ordering> {
52        Some(self.cmp(other))
53    }
54}
55
56impl<F: GeoFloat> std::cmp::PartialEq for NodeKey<F> {
57    fn eq(&self, other: &NodeKey<F>) -> bool {
58        debug_assert!(!self.0.x.is_nan());
59        debug_assert!(!self.0.y.is_nan());
60        debug_assert!(!other.0.x.is_nan());
61        debug_assert!(!other.0.y.is_nan());
62        self.0 == other.0
63    }
64}
65
66impl<F: GeoFloat> std::cmp::Eq for NodeKey<F> {}
67
68impl<F, NF> NodeMap<F, NF>
69where
70    F: GeoFloat,
71    NF: NodeFactory<F>,
72{
73    pub fn new() -> Self {
74        NodeMap {
75            map: BTreeMap::new(),
76            _node_factory: PhantomData,
77        }
78    }
79    /// Adds a `NF::Node` with the given `Coord`.
80    ///
81    /// Note: Coords must be non-NaN.
82    pub fn insert_node_with_coordinate(&mut self, coord: Coord<F>) -> &mut NF::Node {
83        debug_assert!(
84            !coord.x.is_nan() && !coord.y.is_nan(),
85            "NaN coordinates are not supported"
86        );
87        let key = NodeKey(coord);
88        self.map
89            .entry(key)
90            .or_insert_with(|| NF::create_node(coord))
91    }
92
93    /// returns the `NF::Node`, if any, matching `coord`
94    pub fn find(&self, coord: Coord<F>) -> Option<&NF::Node> {
95        self.map.get(&NodeKey(coord))
96    }
97
98    /// Iterates across `NF::Node`s in lexical order of their `Coord`
99    pub fn iter(&self) -> impl Iterator<Item = &NF::Node> {
100        self.map.values()
101    }
102
103    /// Iterates across `NF::Node`s in lexical order of their `Coord`
104    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut NF::Node> {
105        self.map.values_mut()
106    }
107
108    /// Iterates across `NF::Node`s in lexical order of their `Coord`
109    pub fn into_iter(self) -> impl Iterator<Item = NF::Node> {
110        self.map.into_values()
111    }
112}
geo/algorithm/relate/geomgraph/node_map.rs

geo/algorithm/relate/geomgraph/
node_map.rs
