14999125721

Committed 13 May 2025 02:22PM UTC coverage: 49.654% (-5.7%) from 55.382%

Build # 14999125721

Build Type

push

github

Committed by

zommiommy

Commit Message

wip hyperball cli

Run Details

4 of 147 new or added lines in 4 files covered. (2.72%)

477 existing lines in 46 files now uncovered.

3663 of 7377 relevant lines covered (49.65%)

25650535.86 hits per line

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

54.55

/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))
        }
    }

    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 {	28✔
83	let nodes_per_iter = number_of_nodes.div_ceil(how_many);	112✔
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> {	167✔
97	if self.remaining == 0 {	167✔
98	return None;	28✔
99	}
UNCOV 100	if self.remaining != self.how_many {	×
101	self.lender.advance_by(self.nodes_per_iter).ok()?;	444✔
102	}
103	self.remaining -= 1;	139✔
UNCOV 104	Some(self.lender.clone().take(self.nodes_per_iter))	×
105	}
106	}
107
108	impl<L: lender::Lender + Clone> ExactSizeIterator for Iter<L> {
109	fn len(&self) -> usize {	×
110	self.remaining	×
111	}
112	}
113
114	pub type Lender<'a, S> = lender::Take<<S as SequentialLabeling>::Lender<'a>>;
115	pub type IntoIterator<'a, S> = Iter<<S as SequentialLabeling>::Lender<'a>>;
116	}
117
118	/// Ready-made implementation for the random-access case.
119	///
120	/// This implementation uses the [`iter_from`](SequentialLabeling::iter_from) at
121	/// regular intervals. To use it, you have to implement the trait by specifying
122	/// the associated types `Lender` and `IntoIterator` using the [`ra::Lender`]
123	/// and [`ra::IntoIterator`] types aliases, and then return a [`ra::Iter`]
124	/// structure.
125	///
126	/// # Examples
127	///
128	/// The code for [`BvGraph`](crate::graphs::bvgraph::random_access::BvGraph) is
129	/// ```ignore
130	/// impl<F: RandomAccessDecoderFactory> SplitLabeling for BvGraph<F>
131	/// where
132	/// for<'a> <F as RandomAccessDecoderFactory>::Decoder<'a>: Send + Sync,
133	/// {
134	/// type Lender<'a> = split::ra::Lender<'a, BvGraph<F>> where Self: 'a;
135	/// type IntoIterator<'a> = split::ra::IntoIterator<'a, BvGraph<F>> where Self: 'a;
136	///
137	/// fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
138	/// split::ra::Iter::new(self, how_many)
139	/// }
140	/// }
141	/// ```
142	pub mod ra {
143	use crate::prelude::{RandomAccessLabeling, SequentialLabeling};
144
145	pub struct Iter<'a, R: RandomAccessLabeling> {
146	labeling: &'a R,
147	nodes_per_iter: usize,
148	how_many: usize,
149	i: usize,
150	}
151
152	impl<'a, R: RandomAccessLabeling> Iter<'a, R> {
153	pub fn new(labeling: &'a R, how_many: usize) -> Self {	1✔
154	let nodes_per_iter = labeling.num_nodes().div_ceil(how_many);	5✔
155	Self {
156	labeling,
157	nodes_per_iter,
158	how_many,
159	i: 0,
160	}
161	}
162	}
163
164	impl<'a, R: RandomAccessLabeling> Iterator for Iter<'a, R> {
165	type Item = Lender<'a, R>;
166
167	fn next(&mut self) -> Option<Self::Item> {	11✔
168	use lender::Lender;
169
170	if self.i == self.how_many {	11✔
171	return None;	1✔
172	}
UNCOV 173	self.i += 1;	×
174	Some(
UNCOV 175	self.labeling	×
UNCOV 176	.iter_from((self.i - 1) * self.nodes_per_iter)	×
UNCOV 177	.take(self.nodes_per_iter),	×
178	)
179	}
180	}
181
182	impl<R: RandomAccessLabeling> ExactSizeIterator for Iter<'_, R> {
183	fn len(&self) -> usize {	×
184	self.how_many - self.i	×
185	}
186	}
187
188	pub type Lender<'a, R> = lender::Take<<R as SequentialLabeling>::Lender<'a>>;
189	pub type IntoIterator<'a, R> = Iter<'a, R>;
190	}

vigna / webgraph-rs / 14999125721

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