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}