23365769388

Committed 20 Mar 2026 10:52PM UTC coverage: 68.228% (-3.0%) from 71.245%

Build # 23365769388

Build Type

push

github

Committed by

vigna

Commit Message

No le_bins,be_bins for webgraph

Coverage Stats

6655 of 9754 relevant lines covered (68.23%)

46582760.24 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

78.43

/webgraph/src/traits/split.rs

/*
 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

//! Traits and basic implementations to support parallel completion by splitting
//! the [iterator](SequentialLabeling::Lender) of a labeling into multiple
//! iterators.

use std::rc::Rc;

use impl_tools::autoimpl;

use super::{labels::SequentialLabeling, lenders::NodeLabelsLender};

/// A trait providing methods to split the labeling
/// [iterator](SequentialLabeling::Lender) into multiple thread-safe parts.
///
/// The main method is [`split_iter_at`](SplitLabeling::split_iter_at), which
/// takes a sequence of cutpoints and splits the iteration at those points.
/// Each cutpoint is a node id; the sequence must be non-decreasing and contain
/// at least two elements.
///
/// The convenience method [`split_iter`](SplitLabeling::split_iter) provides a
/// default implementation that splits the iteration into `n` approximately
/// equal parts. It is implemented in terms of
/// [`split_iter_at`](SplitLabeling::split_iter_at), so implementors only need
/// to provide the latter.
///
/// Note that the parts are required to be [`Send`] and [`Sync`], so that they
/// can be safely shared among threads.
///
/// Due to some limitations of the current Rust type system, we cannot provide
/// blanket implementations for this trait. However, we provide ready-made
/// implementations for the [sequential](seq) and [random-access](ra) cases. To
/// use them, you must implement the trait by specifying the associated types
/// `SplitLender` and `IntoIterator`, and then just return a [`seq::Iter`] or
/// [`ra::Iter`] structure from [`split_iter_at`](SplitLabeling::split_iter_at).
#[autoimpl(for<S: trait + ?Sized> &S, &mut S, Rc<S>)]
pub trait SplitLabeling: SequentialLabeling {
    type SplitLender<'a>: for<'next> NodeLabelsLender<'next, Label = <Self as SequentialLabeling>::Label>
        + Send
        + Sync
    where
        Self: 'a;

    type IntoIterator<'a>: IntoIterator<Item = Self::SplitLender<'a>>
    where
        Self: 'a;

    /// Splits the labeling iterator at the given cutpoints.
    ///
    /// The cutpoints are a non-decreasing sequence of node ids with at least
    /// two elements. They define `n` − 1 segments, where `n` is the number of
    /// cutpoints, and the `i`-th segment covers nodes in [`cutpoints[i]` . . `cutpoints[i + 1]`).
    fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_>;

    /// Splits the labeling iterator into `n` approximately equal parts.
    ///
    /// This is a convenience method implemented in terms of
    /// [`split_iter_at`](SplitLabeling::split_iter_at).
    fn split_iter(&self, n: usize) -> Self::IntoIterator<'_> {
        let step = self.num_nodes().div_ceil(n);
        let num_nodes = self.num_nodes();
        self.split_iter_at((0..n + 1).map(move |i| (i * step).min(num_nodes)))
    }
}

/// Ready-made implementation for the sequential case.
///
/// This implementation walks through the iterator of a labeling and
/// clones it at the cutpoints, using
/// [`advance_by`](lender::Lender::advance_by) to skip nodes between
/// cutpoints. It is designed for labelings whose
/// [`iter_from`](SequentialLabeling::iter_from) is not more efficient than
/// sequential iteration (e.g., compressed graphs without an index); if
/// `iter_from` can seek efficiently, use [`ra::Iter`] instead.
///
/// To use it, you have to implement the trait by specifying the associated
/// types `SplitLender` and `IntoIterator` using the [`seq::Lender`] and
/// [`seq::IntoIterator`] type aliases, and then return a [`seq::Iter`]
/// structure.
///
/// # Examples
///
/// The code for [`BvGraphSeq`](crate::graphs::bvgraph::sequential::BvGraphSeq) is:
/// ```ignore
/// impl<F: SequentialDecoderFactory> SplitLabeling for BvGraphSeq<F>
/// where
///     for<'a> <F as SequentialDecoderFactory>::Decoder<'a>: Clone + Send + Sync,
/// {
///     type SplitLender<'a> = split::seq::Lender<'a, BvGraphSeq<F>> where Self: 'a;
///     type IntoIterator<'a> = split::seq::IntoIterator<'a, BvGraphSeq<F>> where Self: 'a;
///
///     fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_> {
///         split::seq::Iter::new(self.iter(), cutpoints)
///     }
/// }
/// ```
pub mod seq {
    use crate::prelude::SequentialLabeling;

    /// An iterator over segments of a sequential labeling defined by cutpoints.
    pub struct Iter<L> {
        lender: L,
        cutpoints: Vec<usize>,
        i: usize,
    }

    impl<L: lender::Lender> Iter<L> {
        /// Creates a new iterator from a lender and a sequence of cutpoints.
        ///
        /// The cutpoints must be a non-decreasing sequence with at least 2
        /// elements, and the last cutpoint must be at most the number of nodes
        /// in the labeling.
        pub fn new(lender: L, cutpoints: impl core::iter::IntoIterator<Item = usize>) -> Self {
            let cutpoints: Vec<usize> = cutpoints.into_iter().collect();
            assert!(
                cutpoints.len() >= 2,
                "cutpoints must have at least 2 elements"
            );
            assert!(
                cutpoints.windows(2).all(|w| w[0] <= w[1]),
                "cutpoints must be non-decreasing"
            );
            Self {
                lender,
                cutpoints,
                i: 0,
            }
        }
    }

    impl<L: lender::Lender + Clone> Iterator for Iter<L> {
        type Item = lender::Take<L>;

        fn next(&mut self) -> Option<Self::Item> {
            if self.i + 1 >= self.cutpoints.len() {
                return None;
            }
            if self.i > 0 {
                let advance = self.cutpoints[self.i] - self.cutpoints[self.i - 1];
                self.lender.advance_by(advance).ok()?;
            }
            let len = self.cutpoints[self.i + 1] - self.cutpoints[self.i];
            self.i += 1;
            Some(self.lender.clone().take(len))
        }

        fn size_hint(&self) -> (usize, Option<usize>) {
            let remaining = self.cutpoints.len() - 1 - self.i;
            (remaining, Some(remaining))
        }

        fn count(self) -> usize {
            self.cutpoints.len() - 1 - self.i
        }
    }

    impl<L: lender::Lender + Clone> ExactSizeIterator for Iter<L> {}
    impl<L: lender::Lender + Clone> core::iter::FusedIterator for Iter<L> {}

    pub type Lender<'a, S> = lender::Take<<S as SequentialLabeling>::Lender<'a>>;
    pub type IntoIterator<'a, S> = Iter<<S as SequentialLabeling>::Lender<'a>>;
}

/// Ready-made implementation for the random-access case.
///
/// This implementation calls [`iter_from`](SequentialLabeling::iter_from)
/// at each cutpoint, seeking directly to the desired position. It is
/// designed for labelings with an efficient `iter_from` (e.g., compressed
/// graphs with an index such as an `.ef` file). If `iter_from` is no
/// faster than sequential iteration (e.g.,
/// [`ArcListGraph`](crate::graphs::arc_list_graph::ArcListGraph)), use
/// [`seq::Iter`] instead.
///
/// The bound is [`RandomAccessLabeling`](crate::traits::RandomAccessLabeling)
/// rather than [`SequentialLabeling`] even though only `iter_from` is used: the
/// stronger bound ensures that `iter_from` is efficient, preventing silent
/// quadratic slowdowns.
///
/// To use it, you have to implement the trait by specifying the associated
/// types `SplitLender` and `IntoIterator` using the [`ra::Lender`] and
/// [`ra::IntoIterator`] type aliases, and then return a [`ra::Iter`]
/// structure.
///
/// # Examples
///
/// The code for [`BvGraph`](crate::graphs::bvgraph::random_access::BvGraph) is
/// ```ignore
/// impl<F: RandomAccessDecoderFactory> SplitLabeling for BvGraph<F>
/// where
///     for<'a> <F as RandomAccessDecoderFactory>::Decoder<'a>: Send + Sync,
/// {
///     type SplitLender<'a> = split::ra::Lender<'a, BvGraph<F>> where Self: 'a;
///     type IntoIterator<'a> = split::ra::IntoIterator<'a, BvGraph<F>> where Self: 'a;
///
///     fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_> {
///         split::ra::Iter::new(self, cutpoints)
///     }
/// }
/// ```
pub mod ra {
    use crate::prelude::{RandomAccessLabeling, SequentialLabeling};

    /// An iterator over segments of a random-access labeling defined by
    /// cutpoints.
    pub struct Iter<'a, R: RandomAccessLabeling> {
        labeling: &'a R,
        cutpoints: Vec<usize>,
        i: usize,
    }

    impl<'a, R: RandomAccessLabeling> Iter<'a, R> {
        /// Creates a new iterator from a labeling and a sequence of cutpoints.
        ///
        /// The cutpoints must be a non-decreasing sequence with at least 2
        /// elements, and the last cutpoint must be at most
        /// [`num_nodes()`](SequentialLabeling::num_nodes).
        pub fn new(
            labeling: &'a R,
            cutpoints: impl core::iter::IntoIterator<Item = usize>,
        ) -> Self {
            let cutpoints: Vec<usize> = cutpoints.into_iter().collect();
            assert!(
                cutpoints.len() >= 2,
                "cutpoints must have at least 2 elements"
            );
            assert!(
                cutpoints.windows(2).all(|w| w[0] <= w[1]),
                "cutpoints must be non-decreasing"
            );
            assert!(
                *cutpoints.last().unwrap() <= labeling.num_nodes(),
                "last cutpoint ({}) must be <= num_nodes ({})",
                cutpoints.last().unwrap(),
                labeling.num_nodes()
            );
            Self {
                labeling,
                cutpoints,
                i: 0,
            }
        }
    }

    impl<'a, R: RandomAccessLabeling> Iterator for Iter<'a, R> {
        type Item = Lender<'a, R>;

        fn next(&mut self) -> Option<Self::Item> {
            use lender::Lender;

            if self.i + 1 >= self.cutpoints.len() {
                return None;
            }
            let start = self.cutpoints[self.i];
            let end = self.cutpoints[self.i + 1];
            self.i += 1;
            Some(self.labeling.iter_from(start).take(end - start))
        }

        fn size_hint(&self) -> (usize, Option<usize>) {
            let remaining = self.cutpoints.len() - 1 - self.i;
            (remaining, Some(remaining))
        }

        fn count(self) -> usize {
            self.cutpoints.len() - 1 - self.i
        }
    }

    impl<R: RandomAccessLabeling> ExactSizeIterator for Iter<'_, R> {}
    impl<R: RandomAccessLabeling> core::iter::FusedIterator for Iter<'_, R> {}

    pub type Lender<'a, R> = lender::Take<<R as SequentialLabeling>::Lender<'a>>;
    pub type IntoIterator<'a, R> = Iter<'a, R>;
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Tommaso Fontana
3	* SPDX-FileCopyrightText: 2023 Sebastiano Vigna
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7
8	//! Traits and basic implementations to support parallel completion by splitting
9	//! the [iterator](SequentialLabeling::Lender) of a labeling into multiple
10	//! iterators.
11
12	use std::rc::Rc;
13
14	use impl_tools::autoimpl;
15
16	use super::{labels::SequentialLabeling, lenders::NodeLabelsLender};
17
18	/// A trait providing methods to split the labeling
19	/// [iterator](SequentialLabeling::Lender) into multiple thread-safe parts.
20	///
21	/// The main method is [`split_iter_at`](SplitLabeling::split_iter_at), which
22	/// takes a sequence of cutpoints and splits the iteration at those points.
23	/// Each cutpoint is a node id; the sequence must be non-decreasing and contain
24	/// at least two elements.
25	///
26	/// The convenience method [`split_iter`](SplitLabeling::split_iter) provides a
27	/// default implementation that splits the iteration into `n` approximately
28	/// equal parts. It is implemented in terms of
29	/// [`split_iter_at`](SplitLabeling::split_iter_at), so implementors only need
30	/// to provide the latter.
31	///
32	/// Note that the parts are required to be [`Send`] and [`Sync`], so that they
33	/// can be safely shared among threads.
34	///
35	/// Due to some limitations of the current Rust type system, we cannot provide
36	/// blanket implementations for this trait. However, we provide ready-made
37	/// implementations for the [sequential](seq) and [random-access](ra) cases. To
38	/// use them, you must implement the trait by specifying the associated types
39	/// `SplitLender` and `IntoIterator`, and then just return a [`seq::Iter`] or
40	/// [`ra::Iter`] structure from [`split_iter_at`](SplitLabeling::split_iter_at).
41	#[autoimpl(for<S: trait + ?Sized> &S, &mut S, Rc<S>)]
42	pub trait SplitLabeling: SequentialLabeling {
43	type SplitLender<'a>: for<'next> NodeLabelsLender<'next, Label = <Self as SequentialLabeling>::Label>
44	+ Send
45	+ Sync
46	where
47	Self: 'a;
48
49	type IntoIterator<'a>: IntoIterator<Item = Self::SplitLender<'a>>
50	where
51	Self: 'a;
52
53	/// Splits the labeling iterator at the given cutpoints.
54	///
55	/// The cutpoints are a non-decreasing sequence of node ids with at least
56	/// two elements. They define `n` − 1 segments, where `n` is the number of
57	/// cutpoints, and the `i`-th segment covers nodes in [`cutpoints[i]` . . `cutpoints[i + 1]`).
58	fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_>;
59
60	/// Splits the labeling iterator into `n` approximately equal parts.
61	///
62	/// This is a convenience method implemented in terms of
63	/// [`split_iter_at`](SplitLabeling::split_iter_at).
64	fn split_iter(&self, n: usize) -> Self::IntoIterator<'_> {	622,130✔
65	let step = self.num_nodes().div_ceil(n);	3,110,650✔
66	let num_nodes = self.num_nodes();	1,866,390✔
67	self.split_iter_at((0..n + 1).map(move \|i\| (i * step).min(num_nodes)))	11,820,668✔
68	}
69	}
70
71	/// Ready-made implementation for the sequential case.
72	///
73	/// This implementation walks through the iterator of a labeling and
74	/// clones it at the cutpoints, using
75	/// [`advance_by`](lender::Lender::advance_by) to skip nodes between
76	/// cutpoints. It is designed for labelings whose
77	/// [`iter_from`](SequentialLabeling::iter_from) is not more efficient than
78	/// sequential iteration (e.g., compressed graphs without an index); if
79	/// `iter_from` can seek efficiently, use [`ra::Iter`] instead.
80	///
81	/// To use it, you have to implement the trait by specifying the associated
82	/// types `SplitLender` and `IntoIterator` using the [`seq::Lender`] and
83	/// [`seq::IntoIterator`] type aliases, and then return a [`seq::Iter`]
84	/// structure.
85	///
86	/// # Examples
87	///
88	/// The code for [`BvGraphSeq`](crate::graphs::bvgraph::sequential::BvGraphSeq) is:
89	/// ```ignore
90	/// impl<F: SequentialDecoderFactory> SplitLabeling for BvGraphSeq<F>
91	/// where
92	/// for<'a> <F as SequentialDecoderFactory>::Decoder<'a>: Clone + Send + Sync,
93	/// {
94	/// type SplitLender<'a> = split::seq::Lender<'a, BvGraphSeq<F>> where Self: 'a;
95	/// type IntoIterator<'a> = split::seq::IntoIterator<'a, BvGraphSeq<F>> where Self: 'a;
96	///
97	/// fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_> {
98	/// split::seq::Iter::new(self.iter(), cutpoints)
99	/// }
100	/// }
101	/// ```
102	pub mod seq {
103	use crate::prelude::SequentialLabeling;
104
105	/// An iterator over segments of a sequential labeling defined by cutpoints.
106	pub struct Iter<L> {
107	lender: L,
108	cutpoints: Vec<usize>,
109	i: usize,
110	}
111
112	impl<L: lender::Lender> Iter<L> {
113	/// Creates a new iterator from a lender and a sequence of cutpoints.
114	///
115	/// The cutpoints must be a non-decreasing sequence with at least 2
116	/// elements, and the last cutpoint must be at most the number of nodes
117	/// in the labeling.
118	pub fn new(lender: L, cutpoints: impl core::iter::IntoIterator<Item = usize>) -> Self {	38✔
119	let cutpoints: Vec<usize> = cutpoints.into_iter().collect();	190✔
120	assert!(	38✔
121	cutpoints.len() >= 2,	38✔
122	"cutpoints must have at least 2 elements"	×
123	);
124	assert!(	38✔
125	cutpoints.windows(2).all(\|w\| w[0] <= w[1]),	456✔
126	"cutpoints must be non-decreasing"	×
127	);
128	Self {
129	lender,
130	cutpoints,
131	i: 0,
132	}
133	}
134	}
135
136	impl<L: lender::Lender + Clone> Iterator for Iter<L> {
137	type Item = lender::Take<L>;
138
139	fn next(&mut self) -> Option<Self::Item> {	228✔
140	if self.i + 1 >= self.cutpoints.len() {	456✔
141	return None;	38✔
142	}
143	if self.i > 0 {	190✔
144	let advance = self.cutpoints[self.i] - self.cutpoints[self.i - 1];	456✔
145	self.lender.advance_by(advance).ok()?;	608✔
146	}
147	let len = self.cutpoints[self.i + 1] - self.cutpoints[self.i];	570✔
148	self.i += 1;	190✔
149	Some(self.lender.clone().take(len))	570✔
150	}
151
152	fn size_hint(&self) -> (usize, Option<usize>) {	20✔
153	let remaining = self.cutpoints.len() - 1 - self.i;	40✔
154	(remaining, Some(remaining))	20✔
155	}
156
157	fn count(self) -> usize {	×
158	self.cutpoints.len() - 1 - self.i	×
159	}
160	}
161
162	impl<L: lender::Lender + Clone> ExactSizeIterator for Iter<L> {}
163	impl<L: lender::Lender + Clone> core::iter::FusedIterator for Iter<L> {}
164
165	pub type Lender<'a, S> = lender::Take<<S as SequentialLabeling>::Lender<'a>>;
166	pub type IntoIterator<'a, S> = Iter<<S as SequentialLabeling>::Lender<'a>>;
167	}
168
169	/// Ready-made implementation for the random-access case.
170	///
171	/// This implementation calls [`iter_from`](SequentialLabeling::iter_from)
172	/// at each cutpoint, seeking directly to the desired position. It is
173	/// designed for labelings with an efficient `iter_from` (e.g., compressed
174	/// graphs with an index such as an `.ef` file). If `iter_from` is no
175	/// faster than sequential iteration (e.g.,
176	/// [`ArcListGraph`](crate::graphs::arc_list_graph::ArcListGraph)), use
177	/// [`seq::Iter`] instead.
178	///
179	/// The bound is [`RandomAccessLabeling`](crate::traits::RandomAccessLabeling)
180	/// rather than [`SequentialLabeling`] even though only `iter_from` is used: the
181	/// stronger bound ensures that `iter_from` is efficient, preventing silent
182	/// quadratic slowdowns.
183	///
184	/// To use it, you have to implement the trait by specifying the associated
185	/// types `SplitLender` and `IntoIterator` using the [`ra::Lender`] and
186	/// [`ra::IntoIterator`] type aliases, and then return a [`ra::Iter`]
187	/// structure.
188	///
189	/// # Examples
190	///
191	/// The code for [`BvGraph`](crate::graphs::bvgraph::random_access::BvGraph) is
192	/// ```ignore
193	/// impl<F: RandomAccessDecoderFactory> SplitLabeling for BvGraph<F>
194	/// where
195	/// for<'a> <F as RandomAccessDecoderFactory>::Decoder<'a>: Send + Sync,
196	/// {
197	/// type SplitLender<'a> = split::ra::Lender<'a, BvGraph<F>> where Self: 'a;
198	/// type IntoIterator<'a> = split::ra::IntoIterator<'a, BvGraph<F>> where Self: 'a;
199	///
200	/// fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_> {
201	/// split::ra::Iter::new(self, cutpoints)
202	/// }
203	/// }
204	/// ```
205	pub mod ra {
206	use crate::prelude::{RandomAccessLabeling, SequentialLabeling};
207
208	/// An iterator over segments of a random-access labeling defined by
209	/// cutpoints.
210	pub struct Iter<'a, R: RandomAccessLabeling> {
211	labeling: &'a R,
212	cutpoints: Vec<usize>,
213	i: usize,
214	}
215
216	impl<'a, R: RandomAccessLabeling> Iter<'a, R> {
217	/// Creates a new iterator from a labeling and a sequence of cutpoints.
218	///
219	/// The cutpoints must be a non-decreasing sequence with at least 2
220	/// elements, and the last cutpoint must be at most
221	/// [`num_nodes()`](SequentialLabeling::num_nodes).
222	pub fn new(	622,112✔
223	labeling: &'a R,
224	cutpoints: impl core::iter::IntoIterator<Item = usize>,
225	) -> Self {
226	let cutpoints: Vec<usize> = cutpoints.into_iter().collect();	3,110,560✔
227	assert!(	622,112✔
228	cutpoints.len() >= 2,	622,112✔
229	"cutpoints must have at least 2 elements"	×
230	);
231	assert!(	622,112✔
232	cutpoints.windows(2).all(\|w\| w[0] <= w[1]),	6,221,162✔
233	"cutpoints must be non-decreasing"	×
234	);
235	assert!(	622,112✔
236	*cutpoints.last().unwrap() <= labeling.num_nodes(),	1,244,224✔
237	"last cutpoint ({}) must be <= num_nodes ({})",	×
238	cutpoints.last().unwrap(),	×
239	labeling.num_nodes()	×
240	);
241	Self {
242	labeling,
243	cutpoints,
244	i: 0,
245	}
246	}
247	}
248
249	impl<'a, R: RandomAccessLabeling> Iterator for Iter<'a, R> {
250	type Item = Lender<'a, R>;
251
252	fn next(&mut self) -> Option<Self::Item> {	3,110,581✔
253	use lender::Lender;
254
255	if self.i + 1 >= self.cutpoints.len() {	6,221,162✔
256	return None;	622,112✔
257	}
258	let start = self.cutpoints[self.i];	4,976,938✔
259	let end = self.cutpoints[self.i + 1];	4,976,938✔
260	self.i += 1;	2,488,469✔
261	Some(self.labeling.iter_from(start).take(end - start))	12,442,345✔
262	}
263
264	fn size_hint(&self) -> (usize, Option<usize>) {	24✔
265	let remaining = self.cutpoints.len() - 1 - self.i;	48✔
266	(remaining, Some(remaining))	24✔
267	}
268
269	fn count(self) -> usize {	×
270	self.cutpoints.len() - 1 - self.i	×
271	}
272	}
273
274	impl<R: RandomAccessLabeling> ExactSizeIterator for Iter<'_, R> {}
275	impl<R: RandomAccessLabeling> core::iter::FusedIterator for Iter<'_, R> {}
276
277	pub type Lender<'a, R> = lender::Take<<R as SequentialLabeling>::Lender<'a>>;
278	pub type IntoIterator<'a, R> = Iter<'a, R>;
279	}

vigna / webgraph-rs / 23365769388

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous