geo/
utils.rs

1//! Internal utility functions, types, and data structures.
2
3use geo_types::{Coord, CoordFloat, CoordNum};
4use num_traits::FromPrimitive;
5
6/// Partition a mutable slice in-place so that it contains all elements for
7/// which `predicate(e)` is `true`, followed by all elements for which
8/// `predicate(e)` is `false`. Returns sub-slices to all predicated and
9/// non-predicated elements, respectively.
10///
11/// https://github.com/llogiq/partition/blob/master/src/lib.rs
12pub fn partition_slice<T, P>(data: &mut [T], predicate: P) -> (&mut [T], &mut [T])
13where
14    P: Fn(&T) -> bool,
15{
16    let len = data.len();
17    if len == 0 {
18        return (&mut [], &mut []);
19    }
20    let (mut l, mut r) = (0, len - 1);
21    loop {
22        while l < len && predicate(&data[l]) {
23            l += 1;
24        }
25        while r > 0 && !predicate(&data[r]) {
26            r -= 1;
27        }
28        if l >= r {
29            return data.split_at_mut(l);
30        }
31        data.swap(l, r);
32    }
33}
34
35pub enum EitherIter<I1, I2> {
36    A(I1),
37    B(I2),
38}
39
40impl<I1, I2> ExactSizeIterator for EitherIter<I1, I2>
41where
42    I1: ExactSizeIterator,
43    I2: ExactSizeIterator<Item = I1::Item>,
44{
45    #[inline]
46    fn len(&self) -> usize {
47        match self {
48            EitherIter::A(i1) => i1.len(),
49            EitherIter::B(i2) => i2.len(),
50        }
51    }
52}
53
54impl<T, I1, I2> Iterator for EitherIter<I1, I2>
55where
56    I1: Iterator<Item = T>,
57    I2: Iterator<Item = T>,
58{
59    type Item = T;
60
61    #[inline]
62    fn next(&mut self) -> Option<Self::Item> {
63        match self {
64            EitherIter::A(iter) => iter.next(),
65            EitherIter::B(iter) => iter.next(),
66        }
67    }
68
69    #[inline]
70    fn size_hint(&self) -> (usize, Option<usize>) {
71        match self {
72            EitherIter::A(iter) => iter.size_hint(),
73            EitherIter::B(iter) => iter.size_hint(),
74        }
75    }
76}
77
78// The Rust standard library has `max` for `Ord`, but not for `PartialOrd`
79pub fn partial_max<T: PartialOrd>(a: T, b: T) -> T {
80    if a > b { a } else { b }
81}
82
83// The Rust standard library has `min` for `Ord`, but not for `PartialOrd`
84pub fn partial_min<T: PartialOrd>(a: T, b: T) -> T {
85    if a < b { a } else { b }
86}
87
88use std::cmp::Ordering;
89
90/// Compare two coordinates lexicographically: first by the
91/// x coordinate, and break ties with the y coordinate.
92/// Expects none of coordinates to be uncomparable (eg. nan)
93#[inline]
94pub fn lex_cmp<T: CoordNum>(p: &Coord<T>, q: &Coord<T>) -> Ordering {
95    p.x.partial_cmp(&q.x)
96        .unwrap()
97        .then(p.y.partial_cmp(&q.y).unwrap())
98}
99
100/// Compute index of the least point in slice. Comparison is
101/// done using [`lex_cmp`].
102///
103/// Should only be called on a non-empty slice with no `nan`
104/// coordinates.
105pub fn least_index<T: CoordNum>(pts: &[Coord<T>]) -> usize {
106    pts.iter()
107        .enumerate()
108        .min_by(|(_, p), (_, q)| lex_cmp(p, q))
109        .unwrap()
110        .0
111}
112
113/// Compute index of the lexicographically least _and_ the
114/// greatest coordinate in one pass.
115///
116/// Should only be called on a non-empty slice with no `nan`
117/// coordinates.
118pub fn least_and_greatest_index<T: CoordNum>(pts: &[Coord<T>]) -> (usize, usize) {
119    assert_ne!(pts.len(), 0);
120    let (min, max) = pts
121        .iter()
122        .enumerate()
123        .fold((None, None), |(min, max), (idx, p)| {
124            (
125                if let Some((midx, min)) = min {
126                    if lex_cmp(p, min) == Ordering::Less {
127                        Some((idx, p))
128                    } else {
129                        Some((midx, min))
130                    }
131                } else {
132                    Some((idx, p))
133                },
134                if let Some((midx, max)) = max {
135                    if lex_cmp(p, max) == Ordering::Greater {
136                        Some((idx, p))
137                    } else {
138                        Some((midx, max))
139                    }
140                } else {
141                    Some((idx, p))
142                },
143            )
144        });
145    (min.unwrap().0, max.unwrap().0)
146}
147
148/// Normalize a longitude to coordinate to ensure it's within [-180,180]
149pub fn normalize_longitude<T: CoordFloat + FromPrimitive>(coord: T) -> T {
150    let one_eighty = T::from(180.0f64).unwrap();
151    let three_sixty = T::from(360.0f64).unwrap();
152    let five_forty = T::from(540.0f64).unwrap();
153
154    ((coord + five_forty) % three_sixty) - one_eighty
155}
156
157#[cfg(test)]
158mod test {
159    use super::{partial_max, partial_min};
160
161    #[test]
162    fn test_partial_max() {
163        assert_eq!(5, partial_max(5, 4));
164        assert_eq!(5, partial_max(5, 5));
165    }
166
167    #[test]
168    fn test_partial_min() {
169        assert_eq!(4, partial_min(5, 4));
170        assert_eq!(4, partial_min(4, 4));
171    }
172}
geo/utils.rs

geo/
utils.rs
