15928155839

Committed 27 Jun 2025 02:01PM UTC coverage: 50.358% (+0.004%) from 50.354%

Build # 15928155839

Build Type

push

github

Committed by

zommiommy

Commit Message

Fixed ArcListGraph

Run Details

2 of 3 new or added lines in 1 file covered. (66.67%)

147 existing lines in 11 files now uncovered.

3870 of 7685 relevant lines covered (50.36%)

24375193.78 hits per line

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

66.67

/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 with a single method that splits a labeling into `n` parts which are
/// thread safe.
///
/// Labeling implementing this trait can be analyzed in parallel by calling
/// [`split_iter`](SplitLabeling::split_iter) to split the labeling
/// [iterator](SequentialLabeling::Lender) into `n` parts.
///
/// 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
/// `Lender` and `IntoIterator`, and then just return a [`seq::Iter`] or
/// [`ra::Iter`] structure.
#[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;
    fn split_iter(&self, n: usize) -> Self::IntoIterator<'_>;
}

/// Ready-made implementation for the sequential case.
///
/// This implementation walks through the iterator of a labeling and
/// clones it at regular intervals. To use it, you have to implement the
/// trait by specifying the associated types `Lender` and `IntoIterator`
/// using the [`seq::Lender`] and [`seq::IntoIterator`] types 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 Lender<'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(&self, how_many: usize) -> Self::IntoIterator<'_> {
///         split::seq::Iter::new(self.iter(), how_many)
///     }
/// }
/// ```
pub mod seq {
    use crate::prelude::SequentialLabeling;

    pub struct Iter<L> {
        lender: L,
        nodes_per_iter: usize,
        how_many: usize,
        remaining: usize,
    }

    impl<L: lender::Lender> Iter<L> {
        pub fn new(lender: L, number_of_nodes: usize, how_many: usize) -> Self {
            let nodes_per_iter = number_of_nodes.div_ceil(how_many);
            Self {
                lender,
                nodes_per_iter,
                how_many,
                remaining: how_many,
            }
        }
    }

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

        fn next(&mut self) -> Option<Self::Item> {
            if self.remaining == 0 {
                return None;
            }
            if self.remaining != self.how_many {
                self.lender.advance_by(self.nodes_per_iter).ok()?;
            }
            self.remaining -= 1;
            Some(self.lender.clone().take(self.nodes_per_iter))
        }

        fn size_hint(&self) -> (usize, Option<usize>) {
            (self.remaining, Some(self.remaining))
        }
    }

    impl<L: lender::Lender + Clone> ExactSizeIterator for Iter<L> {
        fn len(&self) -> usize {
            self.remaining
        }
    }

    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 uses the [`iter_from`](SequentialLabeling::iter_from) at
/// regular intervals. To use it, you have to implement the trait by specifying
/// the associated types `Lender` and `IntoIterator` using the [`ra::Lender`]
/// and [`ra::IntoIterator`] types 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 Lender<'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(&self, how_many: usize) -> Self::IntoIterator<'_> {
///         split::ra::Iter::new(self, how_many)
///     }
/// }
/// ```
pub mod ra {
    use crate::prelude::{RandomAccessLabeling, SequentialLabeling};

    pub struct Iter<'a, R: RandomAccessLabeling> {
        labeling: &'a R,
        nodes_per_iter: usize,
        how_many: usize,
        i: usize,
    }

    impl<'a, R: RandomAccessLabeling> Iter<'a, R> {
        pub fn new(labeling: &'a R, how_many: usize) -> Self {
            let nodes_per_iter = labeling.num_nodes().div_ceil(how_many);
            Self {
                labeling,
                nodes_per_iter,
                how_many,
                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 == self.how_many {
                return None;
            }
            self.i += 1;
            Some(
                self.labeling
                    .iter_from((self.i - 1) * self.nodes_per_iter)
                    .take(self.nodes_per_iter),
            )
        }
    }

    impl<R: RandomAccessLabeling> ExactSizeIterator for Iter<'_, R> {
        fn len(&self) -> usize {
            self.how_many - self.i
        }
    }

    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 with a single method that splits a labeling into `n` parts which are
19	/// thread safe.
20	///
21	/// Labeling implementing this trait can be analyzed in parallel by calling
22	/// [`split_iter`](SplitLabeling::split_iter) to split the labeling
23	/// [iterator](SequentialLabeling::Lender) into `n` parts.
24	///
25	/// Note that the parts are required to be [`Send`] and [`Sync`], so that they
26	/// can be safely shared among threads.
27	///
28	/// Due to some limitations of the current Rust type system, we cannot provide
29	/// blanket implementations for this trait. However, we provide ready-made
30	/// implementations for the [sequential](seq) and [random-access](ra) cases. To
31	/// use them, you must implement the trait by specifying the associated types
32	/// `Lender` and `IntoIterator`, and then just return a [`seq::Iter`] or
33	/// [`ra::Iter`] structure.
34	#[autoimpl(for<S: trait + ?Sized> &S, &mut S, Rc<S>)]
35	pub trait SplitLabeling: SequentialLabeling {
36	type SplitLender<'a>: for<'next> NodeLabelsLender<'next, Label = <Self as SequentialLabeling>::Label>
37	+ Send
38	+ Sync
39	where
40	Self: 'a;
41	type IntoIterator<'a>: IntoIterator<Item = Self::SplitLender<'a>>
42	where
43	Self: 'a;
44	fn split_iter(&self, n: usize) -> Self::IntoIterator<'_>;
45	}
46
47	/// Ready-made implementation for the sequential case.
48	///
49	/// This implementation walks through the iterator of a labeling and
50	/// clones it at regular intervals. To use it, you have to implement the
51	/// trait by specifying the associated types `Lender` and `IntoIterator`
52	/// using the [`seq::Lender`] and [`seq::IntoIterator`] types aliases,
53	/// and then return a [`seq::Iter`] structure.
54	///
55	/// # Examples
56	///
57	/// The code for [`BvGraphSeq`](crate::graphs::bvgraph::sequential::BvGraphSeq) is:
58	/// ```ignore
59	/// impl<F: SequentialDecoderFactory> SplitLabeling for BvGraphSeq<F>
60	/// where
61	/// for<'a> <F as SequentialDecoderFactory>::Decoder<'a>: Clone + Send + Sync,
62	/// {
63	/// type Lender<'a> = split::seq::Lender<'a, BvGraphSeq<F>> where Self: 'a;
64	/// type IntoIterator<'a> = split::seq::IntoIterator<'a, BvGraphSeq<F>> where Self: 'a;
65	///
66	/// fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
67	/// split::seq::Iter::new(self.iter(), how_many)
68	/// }
69	/// }
70	/// ```
71	pub mod seq {
72	use crate::prelude::SequentialLabeling;
73
74	pub struct Iter<L> {
75	lender: L,
76	nodes_per_iter: usize,
77	how_many: usize,
78	remaining: usize,
79	}
80
81	impl<L: lender::Lender> Iter<L> {
82	pub fn new(lender: L, number_of_nodes: usize, how_many: usize) -> Self {	39✔
83	let nodes_per_iter = number_of_nodes.div_ceil(how_many);	156✔
84	Self {
85	lender,
86	nodes_per_iter,
87	how_many,
88	remaining: how_many,
89	}
90	}
91	}
92
93	impl<L: lender::Lender + Clone> Iterator for Iter<L> {
94	type Item = lender::Take<L>;
95
96	fn next(&mut self) -> Option<Self::Item> {	244✔
97	if self.remaining == 0 {	244✔
98	return None;	39✔
99	}
100	if self.remaining != self.how_many {	×
101	self.lender.advance_by(self.nodes_per_iter).ok()?;	664✔
102	}
103	self.remaining -= 1;	205✔
104	Some(self.lender.clone().take(self.nodes_per_iter))	×
105	}
106
UNCOV 107	fn size_hint(&self) -> (usize, Option<usize>) {	×
UNCOV 108	(self.remaining, Some(self.remaining))	×
109	}
110	}
111
112	impl<L: lender::Lender + Clone> ExactSizeIterator for Iter<L> {
113	fn len(&self) -> usize {	11✔
114	self.remaining	11✔
115	}
116	}
117
118	pub type Lender<'a, S> = lender::Take<<S as SequentialLabeling>::Lender<'a>>;
119	pub type IntoIterator<'a, S> = Iter<<S as SequentialLabeling>::Lender<'a>>;
120	}
121
122	/// Ready-made implementation for the random-access case.
123	///
124	/// This implementation uses the [`iter_from`](SequentialLabeling::iter_from) at
125	/// regular intervals. To use it, you have to implement the trait by specifying
126	/// the associated types `Lender` and `IntoIterator` using the [`ra::Lender`]
127	/// and [`ra::IntoIterator`] types aliases, and then return a [`ra::Iter`]
128	/// structure.
129	///
130	/// # Examples
131	///
132	/// The code for [`BvGraph`](crate::graphs::bvgraph::random_access::BvGraph) is
133	/// ```ignore
134	/// impl<F: RandomAccessDecoderFactory> SplitLabeling for BvGraph<F>
135	/// where
136	/// for<'a> <F as RandomAccessDecoderFactory>::Decoder<'a>: Send + Sync,
137	/// {
138	/// type Lender<'a> = split::ra::Lender<'a, BvGraph<F>> where Self: 'a;
139	/// type IntoIterator<'a> = split::ra::IntoIterator<'a, BvGraph<F>> where Self: 'a;
140	///
141	/// fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
142	/// split::ra::Iter::new(self, how_many)
143	/// }
144	/// }
145	/// ```
146	pub mod ra {
147	use crate::prelude::{RandomAccessLabeling, SequentialLabeling};
148
149	pub struct Iter<'a, R: RandomAccessLabeling> {
150	labeling: &'a R,
151	nodes_per_iter: usize,
152	how_many: usize,
153	i: usize,
154	}
155
156	impl<'a, R: RandomAccessLabeling> Iter<'a, R> {
157	pub fn new(labeling: &'a R, how_many: usize) -> Self {	12✔
158	let nodes_per_iter = labeling.num_nodes().div_ceil(how_many);	60✔
159	Self {
160	labeling,
161	nodes_per_iter,
162	how_many,
163	i: 0,
164	}
165	}
166	}
167
168	impl<'a, R: RandomAccessLabeling> Iterator for Iter<'a, R> {
169	type Item = Lender<'a, R>;
170
171	fn next(&mut self) -> Option<Self::Item> {	77✔
172	use lender::Lender;
173
174	if self.i == self.how_many {	77✔
175	return None;	1✔
176	}
177	self.i += 1;	×
178	Some(
UNCOV 179	self.labeling	×
UNCOV 180	.iter_from((self.i - 1) * self.nodes_per_iter)	×
UNCOV 181	.take(self.nodes_per_iter),	×
182	)
183	}
184	}
185
186	impl<R: RandomAccessLabeling> ExactSizeIterator for Iter<'_, R> {
187	fn len(&self) -> usize {	22✔
188	self.how_many - self.i	22✔
189	}
190	}
191
192	pub type Lender<'a, R> = lender::Take<<R as SequentialLabeling>::Lender<'a>>;
193	pub type IntoIterator<'a, R> = Iter<'a, R>;
194	}

vigna / webgraph-rs / 15928155839

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