/rust/registry/src/index.crates.io-1949cf8c6b5b557f/rstar-0.12.2/src/params.rs

Source
use crate::algorithm::rstar::RStarInsertionStrategy;
use crate::{Envelope, Point, RTree, RTreeObject};

/// Defines static parameters for an r-tree.
///
/// Internally, an r-tree contains several nodes, similar to a b-tree. These parameters change
/// the size of these nodes and can be used to fine-tune the tree's performance.
///
/// # Example
/// ```
/// use rstar::{RTreeParams, RTree, RStarInsertionStrategy};
///
/// // This example uses an rtree with larger internal nodes.
/// struct LargeNodeParameters;
///
/// impl RTreeParams for LargeNodeParameters
/// {
///     const MIN_SIZE: usize = 10;
///     const MAX_SIZE: usize = 30;
///     const REINSERTION_COUNT: usize = 5;
///     type DefaultInsertionStrategy = RStarInsertionStrategy;
/// }
///
/// // Optional but helpful: Define a type alias for the new r-tree
/// type LargeNodeRTree<T> = RTree<T, LargeNodeParameters>;
///
/// # fn main() {
/// // The only difference from now on is the usage of "new_with_params" instead of "new"
/// let mut large_node_tree: LargeNodeRTree<_> = RTree::new_with_params();
/// // Using the r-tree should allow inference for the point type
/// large_node_tree.insert([1.0, -1.0f32]);
/// // There is also a bulk load method with parameters:
/// # let some_elements = vec![[0.0, 0.0]];
/// let tree: LargeNodeRTree<_> = RTree::bulk_load_with_params(some_elements);
/// # }
/// ```
pub trait RTreeParams: Send + Sync {
    /// The minimum size of an internal node. `MIN_SIZE` must be greater than zero, and up to half
    /// as large as `MAX_SIZE`.
    ///
    /// Choosing a value around one half or one third of `MAX_SIZE` is recommended. Larger values
    /// should yield slightly better tree quality, while lower values may benefit insertion
    /// performance.
    const MIN_SIZE: usize;

    /// The maximum size of an internal node. Larger values will improve insertion performance
    /// but increase the average query time.
    const MAX_SIZE: usize;

    /// The number of nodes that the insertion strategy tries to occasionally reinsert to
    /// maintain a good tree quality. Must be smaller than `MAX_SIZE` - `MIN_SIZE`.
    /// Larger values will improve query times but increase insertion time.
    const REINSERTION_COUNT: usize;

    /// The insertion strategy which is used when calling [RTree::insert].
    type DefaultInsertionStrategy: InsertionStrategy;
}

/// The default parameters used when creating an r-tree without specific parameters.
#[derive(Clone, Copy, PartialEq, Eq, Default)]
pub struct DefaultParams;

impl RTreeParams for DefaultParams {
    const MIN_SIZE: usize = 3;
    const MAX_SIZE: usize = 6;
    const REINSERTION_COUNT: usize = 2;
    type DefaultInsertionStrategy = RStarInsertionStrategy;
}

/// Defines how points are inserted into an r-tree.
///
/// Different strategies try to minimize both _insertion time_ (how long does it take to add a new
/// object into the tree?) and _querying time_ (how long does an average nearest neighbor query
/// take?).
/// Currently, only one insertion strategy is implemented: R* (R-star) insertion. R* insertion
/// tries to minimize querying performance while yielding reasonable insertion times, making it a
/// good default strategy. More strategies may be implemented in the future.
///
/// Only calls to [RTree::insert] are affected by this strategy.
///
/// This trait is not meant to be implemented by the user.
pub trait InsertionStrategy {
    #[doc(hidden)]
    fn insert<T, Params>(tree: &mut RTree<T, Params>, t: T)
    where
        Params: RTreeParams,
        T: RTreeObject;
}

pub fn verify_parameters<T: RTreeObject, P: RTreeParams>() {
    assert!(
        P::MAX_SIZE >= 4,
        "MAX_SIZE too small. Must be larger than 4."
    );

    assert!(P::MIN_SIZE > 0, "MIN_SIZE must be at least 1",);
    let max_min_size = (P::MAX_SIZE + 1) / 2;
    assert!(
        P::MIN_SIZE <= max_min_size,
        "MIN_SIZE too large. Must be less or equal to {:?}",
        max_min_size
    );

    let max_reinsertion_count = P::MAX_SIZE - P::MIN_SIZE;
    assert!(
        P::REINSERTION_COUNT < max_reinsertion_count,
        "REINSERTION_COUNT too large. Must be smaller than {:?}",
        max_reinsertion_count
    );

    let dimension = <T::Envelope as Envelope>::Point::DIMENSIONS;
    assert!(
        dimension > 1,
        "Point dimension too small - must be at least 2"
    );
}

Coverage Report

Created: 2026-03-31 07:09

Line	Count	Source
1		use crate::algorithm::rstar::RStarInsertionStrategy;
2		use crate::{Envelope, Point, RTree, RTreeObject};
3
4		/// Defines static parameters for an r-tree.
5		///
6		/// Internally, an r-tree contains several nodes, similar to a b-tree. These parameters change
7		/// the size of these nodes and can be used to fine-tune the tree's performance.
8		///
9		/// # Example
10		/// ```
11		/// use rstar::{RTreeParams, RTree, RStarInsertionStrategy};
12		///
13		/// // This example uses an rtree with larger internal nodes.
14		/// struct LargeNodeParameters;
15		///
16		/// impl RTreeParams for LargeNodeParameters
17		/// {
18		/// const MIN_SIZE: usize = 10;
19		/// const MAX_SIZE: usize = 30;
20		/// const REINSERTION_COUNT: usize = 5;
21		/// type DefaultInsertionStrategy = RStarInsertionStrategy;
22		/// }
23		///
24		/// // Optional but helpful: Define a type alias for the new r-tree
25		/// type LargeNodeRTree<T> = RTree<T, LargeNodeParameters>;
26		///
27		/// # fn main() {
28		/// // The only difference from now on is the usage of "new_with_params" instead of "new"
29		/// let mut large_node_tree: LargeNodeRTree<_> = RTree::new_with_params();
30		/// // Using the r-tree should allow inference for the point type
31		/// large_node_tree.insert([1.0, -1.0f32]);
32		/// // There is also a bulk load method with parameters:
33		/// # let some_elements = vec![[0.0, 0.0]];
34		/// let tree: LargeNodeRTree<_> = RTree::bulk_load_with_params(some_elements);
35		/// # }
36		/// ```
37		pub trait RTreeParams: Send + Sync {
38		/// The minimum size of an internal node. `MIN_SIZE` must be greater than zero, and up to half
39		/// as large as `MAX_SIZE`.
40		///
41		/// Choosing a value around one half or one third of `MAX_SIZE` is recommended. Larger values
42		/// should yield slightly better tree quality, while lower values may benefit insertion
43		/// performance.
44		const MIN_SIZE: usize;
45
46		/// The maximum size of an internal node. Larger values will improve insertion performance
47		/// but increase the average query time.
48		const MAX_SIZE: usize;
49
50		/// The number of nodes that the insertion strategy tries to occasionally reinsert to
51		/// maintain a good tree quality. Must be smaller than `MAX_SIZE` - `MIN_SIZE`.
52		/// Larger values will improve query times but increase insertion time.
53		const REINSERTION_COUNT: usize;
54
55		/// The insertion strategy which is used when calling [RTree::insert].
56		type DefaultInsertionStrategy: InsertionStrategy;
57		}
58
59		/// The default parameters used when creating an r-tree without specific parameters.
60		#[derive(Clone, Copy, PartialEq, Eq, Default)]
61		pub struct DefaultParams;
62
63		impl RTreeParams for DefaultParams {
64		const MIN_SIZE: usize = 3;
65		const MAX_SIZE: usize = 6;
66		const REINSERTION_COUNT: usize = 2;
67		type DefaultInsertionStrategy = RStarInsertionStrategy;
68		}
69
70		/// Defines how points are inserted into an r-tree.
71		///
72		/// Different strategies try to minimize both _insertion time_ (how long does it take to add a new
73		/// object into the tree?) and _querying time_ (how long does an average nearest neighbor query
74		/// take?).
75		/// Currently, only one insertion strategy is implemented: R* (R-star) insertion. R* insertion
76		/// tries to minimize querying performance while yielding reasonable insertion times, making it a
77		/// good default strategy. More strategies may be implemented in the future.
78		///
79		/// Only calls to [RTree::insert] are affected by this strategy.
80		///
81		/// This trait is not meant to be implemented by the user.
82		pub trait InsertionStrategy {
83		#[doc(hidden)]
84		fn insert<T, Params>(tree: &mut RTree<T, Params>, t: T)
85		where
86		Params: RTreeParams,
87		T: RTreeObject;
88		}
89
90	0	pub fn verify_parameters<T: RTreeObject, P: RTreeParams>() {
91	0	assert!(
92	0	P::MAX_SIZE >= 4,
93		"MAX_SIZE too small. Must be larger than 4."
94		);
95
96	0	assert!(P::MIN_SIZE > 0, "MIN_SIZE must be at least 1",);
97	0	let max_min_size = (P::MAX_SIZE + 1) / 2;
98	0	assert!(
99	0	P::MIN_SIZE <= max_min_size,
100		"MIN_SIZE too large. Must be less or equal to {:?}",
101		max_min_size
102		);
103
104	0	let max_reinsertion_count = P::MAX_SIZE - P::MIN_SIZE;
105	0	assert!(
106	0	P::REINSERTION_COUNT < max_reinsertion_count,
107		"REINSERTION_COUNT too large. Must be smaller than {:?}",
108		max_reinsertion_count
109		);
110
111	0	let dimension = <T::Envelope as Envelope>::Point::DIMENSIONS;
112	0	assert!(
113	0	dimension > 1,
114		"Point dimension too small - must be at least 2"
115		);
116	0	} Unexecuted instantiation: rstar::params::verify_parameters::<geo::algorithm::relate::geomgraph::index::segment::Segment<f64>, rstar::params::DefaultParams> Unexecuted instantiation: rstar::params::verify_parameters::<_, _>