rstar/
point.rs

1use core::fmt::Debug;
2use num_traits::{Bounded, Num, Signed, Zero};
3
4/// Defines a number type that is compatible with rstar.
5///
6/// rstar works out of the box with the following standard library types:
7///  - i8, i16, i32, i64, i128, isize
8///  - [Wrapping](core::num::Wrapping) versions of the above
9///  - f32, f64
10///
11/// This type cannot be implemented directly. Instead, it is required to implement
12/// all required traits from the `num_traits` crate.
13///
14/// # Example
15/// ```
16/// # extern crate num_traits;
17/// use num_traits::{Bounded, Num, Signed};
18///
19/// #[derive(Clone, Copy, PartialEq, PartialOrd, Debug)]
20/// struct MyFancyNumberType(f32);
21///
22/// impl num_traits::Bounded for MyFancyNumberType {
23///   // ... details hidden ...
24/// # fn min_value() -> Self { Self(Bounded::min_value()) }
25/// #
26/// # fn max_value() -> Self { Self(Bounded::max_value()) }
27/// }
28///
29/// impl Signed for MyFancyNumberType {
30///   // ... details hidden ...
31/// # fn abs(&self) -> Self { unimplemented!() }
32/// #
33/// # fn abs_sub(&self, other: &Self) -> Self { unimplemented!() }
34/// #
35/// # fn signum(&self) -> Self { unimplemented!() }
36/// #
37/// # fn is_positive(&self) -> bool { unimplemented!() }
38/// #
39/// # fn is_negative(&self) -> bool { unimplemented!() }
40/// }
41///
42/// impl Num for MyFancyNumberType {
43///   // ... details hidden ...
44/// # type FromStrRadixErr = num_traits::ParseFloatError;
45/// # fn from_str_radix(str: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> { unimplemented!() }
46/// }
47///
48/// // Lots of traits are still missing to make the above code compile, but
49/// // let's assume they're implemented. `MyFancyNumberType` type now readily implements
50/// // RTreeNum and can be used with r-trees:
51/// # fn main() {
52/// use rstar::RTree;
53/// let mut rtree = RTree::new();
54/// rtree.insert([MyFancyNumberType(0.0), MyFancyNumberType(0.0)]);
55/// # }
56///
57/// # impl num_traits::Zero for MyFancyNumberType {
58/// #   fn zero() -> Self { unimplemented!() }
59/// #   fn is_zero(&self) -> bool { unimplemented!() }
60/// # }
61/// #
62/// # impl num_traits::One for MyFancyNumberType {
63/// #   fn one() -> Self { unimplemented!() }
64/// # }
65/// #
66/// # impl core::ops::Mul for MyFancyNumberType {
67/// #   type Output = Self;
68/// #   fn mul(self, rhs: Self) -> Self { unimplemented!() }
69/// # }
70/// #
71/// # impl core::ops::Add for MyFancyNumberType {
72/// #   type Output = Self;
73/// #   fn add(self, rhs: Self) -> Self { unimplemented!() }
74/// # }
75/// #
76/// # impl core::ops::Sub for MyFancyNumberType {
77/// #   type Output = Self;
78/// #   fn sub(self, rhs: Self) -> Self { unimplemented!() }
79/// # }
80/// #
81/// # impl core::ops::Div for MyFancyNumberType {
82/// #   type Output = Self;
83/// #   fn div(self, rhs: Self) -> Self { unimplemented!() }
84/// # }
85/// #
86/// # impl core::ops::Rem for MyFancyNumberType {
87/// #   type Output = Self;
88/// #   fn rem(self, rhs: Self) -> Self { unimplemented!() }
89/// # }
90/// #
91/// # impl core::ops::Neg for MyFancyNumberType {
92/// #   type Output = Self;
93/// #   fn neg(self) -> Self { unimplemented!() }
94/// # }
95/// #
96/// ```
97///
98pub trait RTreeNum: Bounded + Num + Clone + Copy + Signed + PartialOrd + Debug {}
99
100impl<S> RTreeNum for S where S: Bounded + Num + Clone + Copy + Signed + PartialOrd + Debug {}
101
102/// Defines a point type that is compatible with rstar.
103///
104/// This trait should be used for interoperability with other point types, not to define custom objects
105/// that can be inserted into r-trees. Use [`crate::RTreeObject`] or
106/// [`crate::primitives::GeomWithData`] instead.
107/// This trait defines points, not points with metadata.
108///
109/// `Point` is implemented out of the box for arrays like `[f32; 2]` or `[f64; 7]` (for any number of dimensions),
110/// and for tuples like `(int, int)` and `(f64, f64, f64)` so tuples with only elements of the same type (up to dimension 9).
111///
112///
113/// # Implementation example
114/// Supporting a custom point type might look like this:
115///
116/// ```
117/// use rstar::Point;
118///
119/// #[derive(Copy, Clone, PartialEq, Debug)]
120/// struct IntegerPoint
121/// {
122///     x: i32,
123///     y: i32
124/// }
125///
126/// impl Point for IntegerPoint
127/// {
128///   type Scalar = i32;
129///   const DIMENSIONS: usize = 2;
130///
131///   fn generate(mut generator: impl FnMut(usize) -> Self::Scalar) -> Self
132///   {
133///     IntegerPoint {
134///       x: generator(0),
135///       y: generator(1)
136///     }
137///   }
138///
139///   fn nth(&self, index: usize) -> Self::Scalar
140///   {
141///     match index {
142///       0 => self.x,
143///       1 => self.y,
144///       _ => unreachable!()
145///     }
146///   }
147///
148///   fn nth_mut(&mut self, index: usize) -> &mut Self::Scalar
149///   {
150///     match index {
151///       0 => &mut self.x,
152///       1 => &mut self.y,
153///       _ => unreachable!()
154///     }
155///   }
156/// }
157/// ```
158pub trait Point: Clone + PartialEq + Debug {
159    /// The number type used by this point type.
160    type Scalar: RTreeNum;
161
162    /// The number of dimensions of this point type.
163    const DIMENSIONS: usize;
164
165    /// Creates a new point value with given values for each dimension.
166    ///
167    /// The value that each dimension should be initialized with is given by the parameter `generator`.
168    /// Calling `generator(n)` returns the value of dimension `n`, `n` will be in the range `0 .. Self::DIMENSIONS`,
169    /// and will be called with values of `n` in ascending order.
170    fn generate(generator: impl FnMut(usize) -> Self::Scalar) -> Self;
171
172    /// Returns a single coordinate of this point.
173    ///
174    /// Returns the coordinate indicated by `index`. `index` is always smaller than `Self::DIMENSIONS`.
175    fn nth(&self, index: usize) -> Self::Scalar;
176
177    /// Mutable variant of [nth](#methods.nth).
178    fn nth_mut(&mut self, index: usize) -> &mut Self::Scalar;
179}
180
181impl<T> PointExt for T where T: Point {}
182
183/// Utility functions for Point
184pub trait PointExt: Point {
185    /// Returns a new Point with all components set to zero.
186    fn new() -> Self {
187        Self::from_value(Zero::zero())
188    }
189
190    /// Applies `f` to each pair of components of `self` and `other`.
191    fn component_wise(
192        &self,
193        other: &Self,
194        mut f: impl FnMut(Self::Scalar, Self::Scalar) -> Self::Scalar,
195    ) -> Self {
196        Self::generate(|i| f(self.nth(i), other.nth(i)))
197    }
198
199    /// Returns whether all pairs of components of `self` and `other` pass test closure `f`. Short circuits if any result is false.
200    fn all_component_wise(
201        &self,
202        other: &Self,
203        mut f: impl FnMut(Self::Scalar, Self::Scalar) -> bool,
204    ) -> bool {
205        (0..Self::DIMENSIONS).all(|i| f(self.nth(i), other.nth(i)))
206    }
207
208    /// Returns the dot product of `self` and `rhs`.
209    fn dot(&self, rhs: &Self) -> Self::Scalar {
210        self.component_wise(rhs, |l, r| l * r)
211            .fold(Zero::zero(), |acc, val| acc + val)
212    }
213
214    /// Folds (aka reduces or injects) the Point component wise using `f` and returns the result.
215    /// fold() takes two arguments: an initial value, and a closure with two arguments: an 'accumulator', and the value of the current component.
216    /// The closure returns the value that the accumulator should have for the next iteration.
217    ///
218    /// The `start_value` is the value the accumulator will have on the first call of the closure.
219    ///
220    /// After applying the closure to every component of the Point, fold() returns the accumulator.
221    fn fold<T>(&self, start_value: T, mut f: impl FnMut(T, Self::Scalar) -> T) -> T {
222        (0..Self::DIMENSIONS).fold(start_value, |accumulated, i| f(accumulated, self.nth(i)))
223    }
224
225    /// Returns a Point with every component set to `value`.
226    fn from_value(value: Self::Scalar) -> Self {
227        Self::generate(|_| value)
228    }
229
230    /// Returns a Point with each component set to the smallest of each component pair of `self` and `other`.
231    fn min_point(&self, other: &Self) -> Self {
232        self.component_wise(other, min_inline)
233    }
234
235    /// Returns a Point with each component set to the biggest of each component pair of `self` and `other`.
236    fn max_point(&self, other: &Self) -> Self {
237        self.component_wise(other, max_inline)
238    }
239
240    /// Returns the squared length of this Point as if it was a vector.
241    fn length_2(&self) -> Self::Scalar {
242        self.fold(Zero::zero(), |acc, cur| cur * cur + acc)
243    }
244
245    /// Substracts `other` from `self` component wise.
246    fn sub(&self, other: &Self) -> Self {
247        self.component_wise(other, |l, r| l - r)
248    }
249
250    /// Adds `other` to `self` component wise.
251    fn add(&self, other: &Self) -> Self {
252        self.component_wise(other, |l, r| l + r)
253    }
254
255    /// Multiplies `self` with `scalar` component wise.
256    fn mul(&self, scalar: Self::Scalar) -> Self {
257        self.map(|coordinate| coordinate * scalar)
258    }
259
260    /// Applies `f` to `self` component wise.
261    fn map(&self, mut f: impl FnMut(Self::Scalar) -> Self::Scalar) -> Self {
262        Self::generate(|i| f(self.nth(i)))
263    }
264
265    /// Returns the squared distance between `self` and `other`.
266    fn distance_2(&self, other: &Self) -> Self::Scalar {
267        self.sub(other).length_2()
268    }
269}
270
271#[inline]
272pub fn min_inline<S>(a: S, b: S) -> S
273where
274    S: RTreeNum,
275{
276    if a < b {
277        a
278    } else {
279        b
280    }
281}
282
283#[inline]
284pub fn max_inline<S>(a: S, b: S) -> S
285where
286    S: RTreeNum,
287{
288    if a > b {
289        a
290    } else {
291        b
292    }
293}
294
295impl<S, const N: usize> Point for [S; N]
296where
297    S: RTreeNum,
298{
299    type Scalar = S;
300
301    const DIMENSIONS: usize = N;
302
303    fn generate(mut generator: impl FnMut(usize) -> S) -> Self {
304        // The same implementation used in std::array::from_fn
305        // Since this is a const generic it gets unrolled
306        let mut idx = 0;
307        [(); N].map(|_| {
308            let res = generator(idx);
309            idx += 1;
310            res
311        })
312    }
313
314    #[inline]
315    fn nth(&self, index: usize) -> Self::Scalar {
316        self[index]
317    }
318
319    #[inline]
320    fn nth_mut(&mut self, index: usize) -> &mut Self::Scalar {
321        &mut self[index]
322    }
323}
324
325macro_rules! count_exprs {
326    () => (0);
327    ($head:expr) => (1);
328    ($head:expr, $($tail:expr),*) => (1 + count_exprs!($($tail),*));
329}
330
331macro_rules! fixed_type {
332    ($expr:expr, $type:ty) => {
333        $type
334    };
335}
336
337macro_rules! impl_point_for_tuple {
338    ($($index:expr => $name:ident),+) => {
339        impl<S> Point for ($(fixed_type!($index, S),)+)
340        where
341            S: RTreeNum
342        {
343            type Scalar = S;
344
345            const DIMENSIONS: usize = count_exprs!($($index),*);
346
347            fn generate(mut generator: impl FnMut(usize) -> S) -> Self {
348                ($(generator($index),)+)
349            }
350
351            #[inline]
352            fn nth(&self, index: usize) -> Self::Scalar {
353                let ($($name,)+) = self;
354
355                match index {
356                    $($index => *$name,)+
357                    _ => unreachable!("index {} out of bounds for tuple", index),
358                }
359            }
360
361            #[inline]
362            fn nth_mut(&mut self, index: usize) -> &mut Self::Scalar {
363                let ($($name,)+) = self;
364
365                match index {
366                    $($index => $name,)+
367                    _ => unreachable!("index {} out of bounds for tuple", index),
368                }
369            }
370        }
371    };
372}
373
374impl_point_for_tuple!(0 => a);
375impl_point_for_tuple!(0 => a, 1 => b);
376impl_point_for_tuple!(0 => a, 1 => b, 2 => c);
377impl_point_for_tuple!(0 => a, 1 => b, 2 => c, 3 => d);
378impl_point_for_tuple!(0 => a, 1 => b, 2 => c, 3 => d, 4 => e);
379impl_point_for_tuple!(0 => a, 1 => b, 2 => c, 3 => d, 4 => e, 5 => f);
380impl_point_for_tuple!(0 => a, 1 => b, 2 => c, 3 => d, 4 => e, 5 => f, 6 => g);
381impl_point_for_tuple!(0 => a, 1 => b, 2 => c, 3 => d, 4 => e, 5 => f, 6 => g, 7 => h);
382impl_point_for_tuple!(0 => a, 1 => b, 2 => c, 3 => d, 4 => e, 5 => f, 6 => g, 7 => h, 8 => i);
383impl_point_for_tuple!(0 => a, 1 => b, 2 => c, 3 => d, 4 => e, 5 => f, 6 => g, 7 => h, 8 => i, 9 => j);
384
385#[cfg(test)]
386mod tests {
387    use super::*;
388    use core::num::Wrapping;
389
390    #[test]
391    fn test_types() {
392        fn assert_impl_rtreenum<S: RTreeNum>() {}
393
394        assert_impl_rtreenum::<i8>();
395        assert_impl_rtreenum::<i16>();
396        assert_impl_rtreenum::<i32>();
397        assert_impl_rtreenum::<i64>();
398        assert_impl_rtreenum::<i128>();
399        assert_impl_rtreenum::<isize>();
400        assert_impl_rtreenum::<Wrapping<i8>>();
401        assert_impl_rtreenum::<Wrapping<i16>>();
402        assert_impl_rtreenum::<Wrapping<i32>>();
403        assert_impl_rtreenum::<Wrapping<i64>>();
404        assert_impl_rtreenum::<Wrapping<i128>>();
405        assert_impl_rtreenum::<Wrapping<isize>>();
406        assert_impl_rtreenum::<f32>();
407        assert_impl_rtreenum::<f64>();
408    }
409
410    macro_rules! test_tuple_configuration {
411        ($($index:expr),*) => {
412            let a = ($($index),*);
413            $(assert_eq!(a.nth($index), $index));*
414        }
415    }
416
417    #[test]
418    fn test_tuples() {
419        // Test a couple of simple cases
420        let simple_int = (0, 1, 2);
421        assert_eq!(simple_int.nth(2), 2);
422        let simple_float = (0.5, 0.67, 1234.56);
423        assert_eq!(simple_float.nth(2), 1234.56);
424        let long_int = (0, 1, 2, 3, 4, 5, 6, 7, 8);
425        assert_eq!(long_int.nth(8), 8);
426
427        // Generate the code to test every nth function for every Tuple length
428        test_tuple_configuration!(0, 1);
429        test_tuple_configuration!(0, 1, 2);
430        test_tuple_configuration!(0, 1, 2, 3);
431        test_tuple_configuration!(0, 1, 2, 3, 4);
432        test_tuple_configuration!(0, 1, 2, 3, 4, 5);
433        test_tuple_configuration!(0, 1, 2, 3, 4, 5, 6);
434        test_tuple_configuration!(0, 1, 2, 3, 4, 5, 6, 7);
435        test_tuple_configuration!(0, 1, 2, 3, 4, 5, 6, 7, 8);
436    }
437}
rstar/point.rs

rstar/
point.rs
