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

rstar/
point.rs
