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

Source
use crate::envelope::Envelope;
use crate::object::RTreeObject;
use crate::params::RTreeParams;

#[cfg(not(test))]
use alloc::vec::Vec;

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

#[derive(Debug, Clone)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(
    feature = "serde",
    serde(bound(
        serialize = "T: Serialize, T::Envelope: Serialize",
        deserialize = "T: Deserialize<'de>, T::Envelope: Deserialize<'de>"
    ))
)]

/// An internal tree node.
///
/// For most applications, using this type should not be required.
pub enum RTreeNode<T>
where
    T: RTreeObject,
{
    /// A leaf node, only containing the r-tree object
    Leaf(T),
    /// A parent node containing several child nodes
    Parent(ParentNode<T>),
}

/// Represents an internal parent node.
///
/// For most applications, using this type should not be required. Allows read access to this
/// node's envelope and its children.
#[derive(Debug, Clone)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct ParentNode<T>
where
    T: RTreeObject,
{
    pub(crate) children: Vec<RTreeNode<T>>,
    pub(crate) envelope: T::Envelope,
}

impl<T> RTreeObject for RTreeNode<T>
where
    T: RTreeObject,
{
    type Envelope = T::Envelope;

    fn envelope(&self) -> Self::Envelope {
        match self {
            RTreeNode::Leaf(ref t) => t.envelope(),
            RTreeNode::Parent(ref data) => data.envelope.clone(),
        }
    }
}

#[doc(hidden)]
impl<T> RTreeNode<T>
where
    T: RTreeObject,
{
    pub fn is_leaf(&self) -> bool {
        match self {
            RTreeNode::Leaf(..) => true,
            RTreeNode::Parent(..) => false,
        }
    }
}

impl<T> ParentNode<T>
where
    T: RTreeObject,
{
    /// Returns this node's children
    pub fn children(&self) -> &[RTreeNode<T>] {
        &self.children
    }

    /// Returns the smallest envelope that encompasses all children.
    pub fn envelope(&self) -> T::Envelope {
        self.envelope.clone()
    }

    pub(crate) fn new_root<Params>() -> Self
    where
        Params: RTreeParams,
    {
        ParentNode {
            envelope: Envelope::new_empty(),
            children: Vec::with_capacity(Params::MAX_SIZE + 1),
        }
    }

    pub(crate) fn new_parent(children: Vec<RTreeNode<T>>) -> Self {
        let envelope = envelope_for_children(&children);

        ParentNode { envelope, children }
    }

    #[cfg(test)]
    #[allow(missing_docs)]
    pub fn sanity_check<Params>(&self, check_max_size: bool) -> Option<usize>
    where
        Params: RTreeParams,
    {
        if self.children.is_empty() {
            Some(0)
        } else {
            let mut result = None;
            self.sanity_check_inner::<Params>(check_max_size, 1, &mut result);
            result
        }
    }

    #[cfg(test)]
    fn sanity_check_inner<Params>(
        &self,
        check_max_size: bool,
        height: usize,
        leaf_height: &mut Option<usize>,
    ) where
        Params: RTreeParams,
    {
        if height > 1 {
            let min_size = Params::MIN_SIZE;
            assert!(self.children.len() >= min_size);
        }
        let mut envelope = T::Envelope::new_empty();
        if check_max_size {
            let max_size = Params::MAX_SIZE;
            assert!(self.children.len() <= max_size);
        }

        for child in &self.children {
            match child {
                RTreeNode::Leaf(ref t) => {
                    envelope.merge(&t.envelope());
                    if let Some(ref leaf_height) = leaf_height {
                        assert_eq!(height, *leaf_height);
                    } else {
                        *leaf_height = Some(height);
                    }
                }
                RTreeNode::Parent(ref data) => {
                    envelope.merge(&data.envelope);
                    data.sanity_check_inner::<Params>(check_max_size, height + 1, leaf_height);
                }
            }
        }
        assert_eq!(self.envelope, envelope);
    }
}

pub fn envelope_for_children<T>(children: &[RTreeNode<T>]) -> T::Envelope
where
    T: RTreeObject,
{
    let mut result = T::Envelope::new_empty();
    for child in children {
        result.merge(&child.envelope());
    }
    result
}

Line	Count	Source
1		use crate::envelope::Envelope;
2		use crate::object::RTreeObject;
3		use crate::params::RTreeParams;
4
5		#[cfg(not(test))]
6		use alloc::vec::Vec;
7
8		#[cfg(feature = "serde")]
9		use serde::{Deserialize, Serialize};
10
11		#[derive(Debug, Clone)]
12		#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
13		#[cfg_attr(
14		feature = "serde",
15		serde(bound(
16		serialize = "T: Serialize, T::Envelope: Serialize",
17		deserialize = "T: Deserialize<'de>, T::Envelope: Deserialize<'de>"
18		))
19		)]
20
21		/// An internal tree node.
22		///
23		/// For most applications, using this type should not be required.
24		pub enum RTreeNode<T>
25		where
26		T: RTreeObject,
27		{
28		/// A leaf node, only containing the r-tree object
29		Leaf(T),
30		/// A parent node containing several child nodes
31		Parent(ParentNode<T>),
32		}
33
34		/// Represents an internal parent node.
35		///
36		/// For most applications, using this type should not be required. Allows read access to this
37		/// node's envelope and its children.
38		#[derive(Debug, Clone)]
39		#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
40		pub struct ParentNode<T>
41		where
42		T: RTreeObject,
43		{
44		pub(crate) children: Vec<RTreeNode<T>>,
45		pub(crate) envelope: T::Envelope,
46		}
47
48		impl<T> RTreeObject for RTreeNode<T>
49		where
50		T: RTreeObject,
51		{
52		type Envelope = T::Envelope;
53
54	0	fn envelope(&self) -> Self::Envelope {
55	0	match self {
56	0	RTreeNode::Leaf(ref t) => t.envelope(),
57	0	RTreeNode::Parent(ref data) => data.envelope.clone(),
58		}
59	0	} Unexecuted instantiation: <rstar::node::RTreeNode<geo::algorithm::relate::geomgraph::index::segment::Segment<f64>> as rstar::object::RTreeObject>::envelope Unexecuted instantiation: <rstar::node::RTreeNode<_> as rstar::object::RTreeObject>::envelope
60		}
61
62		#[doc(hidden)]
63		impl<T> RTreeNode<T>
64		where
65		T: RTreeObject,
66		{
67	0	pub fn is_leaf(&self) -> bool {
68	0	match self {
69	0	RTreeNode::Leaf(..) => true,
70	0	RTreeNode::Parent(..) => false,
71		}
72	0	}
73		}
74
75		impl<T> ParentNode<T>
76		where
77		T: RTreeObject,
78		{
79		/// Returns this node's children
80	0	pub fn children(&self) -> &[RTreeNode<T>] {
81	0	&self.children
82	0	} Unexecuted instantiation: <rstar::node::ParentNode<geo::algorithm::relate::geomgraph::index::segment::Segment<f64>>>::children Unexecuted instantiation: <rstar::node::ParentNode<_>>::children
83
84		/// Returns the smallest envelope that encompasses all children.
85	0	pub fn envelope(&self) -> T::Envelope {
86	0	self.envelope.clone()
87	0	} Unexecuted instantiation: <rstar::node::ParentNode<geo::algorithm::relate::geomgraph::index::segment::Segment<f64>>>::envelope Unexecuted instantiation: <rstar::node::ParentNode<_>>::envelope
88
89	0	pub(crate) fn new_root<Params>() -> Self
90	0	where
91	0	Params: RTreeParams,
92		{
93	0	ParentNode {
94	0	envelope: Envelope::new_empty(),
95	0	children: Vec::with_capacity(Params::MAX_SIZE + 1),
96	0	}
97	0	} Unexecuted instantiation: <rstar::node::ParentNode<geo::algorithm::relate::geomgraph::index::segment::Segment<f64>>>::new_root::<rstar::params::DefaultParams> Unexecuted instantiation: <rstar::node::ParentNode<_>>::new_root::<_>
98
99	0	pub(crate) fn new_parent(children: Vec<RTreeNode<T>>) -> Self {
100	0	let envelope = envelope_for_children(&children);
101
102	0	ParentNode { envelope, children }
103	0	} Unexecuted instantiation: <rstar::node::ParentNode<geo::algorithm::relate::geomgraph::index::segment::Segment<f64>>>::new_parent Unexecuted instantiation: <rstar::node::ParentNode<_>>::new_parent
104
105		#[cfg(test)]
106		#[allow(missing_docs)]
107		pub fn sanity_check<Params>(&self, check_max_size: bool) -> Option<usize>
108		where
109		Params: RTreeParams,
110		{
111		if self.children.is_empty() {
112		Some(0)
113		} else {
114		let mut result = None;
115		self.sanity_check_inner::<Params>(check_max_size, 1, &mut result);
116		result
117		}
118		}
119
120		#[cfg(test)]
121		fn sanity_check_inner<Params>(
122		&self,
123		check_max_size: bool,
124		height: usize,
125		leaf_height: &mut Option<usize>,
126		) where
127		Params: RTreeParams,
128		{
129		if height > 1 {
130		let min_size = Params::MIN_SIZE;
131		assert!(self.children.len() >= min_size);
132		}
133		let mut envelope = T::Envelope::new_empty();
134		if check_max_size {
135		let max_size = Params::MAX_SIZE;
136		assert!(self.children.len() <= max_size);
137		}
138
139		for child in &self.children {
140		match child {
141		RTreeNode::Leaf(ref t) => {
142		envelope.merge(&t.envelope());
143		if let Some(ref leaf_height) = leaf_height {
144		assert_eq!(height, *leaf_height);
145		} else {
146		*leaf_height = Some(height);
147		}
148		}
149		RTreeNode::Parent(ref data) => {
150		envelope.merge(&data.envelope);
151		data.sanity_check_inner::<Params>(check_max_size, height + 1, leaf_height);
152		}
153		}
154		}
155		assert_eq!(self.envelope, envelope);
156		}
157		}
158
159	0	pub fn envelope_for_children<T>(children: &[RTreeNode<T>]) -> T::Envelope
160	0	where
161	0	T: RTreeObject,
162		{
163	0	let mut result = T::Envelope::new_empty();
164	0	for child in children {
165	0	result.merge(&child.envelope());
166	0	}
167	0	result
168	0	} Unexecuted instantiation: rstar::node::envelope_for_children::<geo::algorithm::relate::geomgraph::index::segment::Segment<f64>> Unexecuted instantiation: rstar::node::envelope_for_children::<_>

Coverage Report

Created: 2026-03-23 07:13