18480907774

Committed 13 Oct 2025 11:33PM UTC coverage: 67.167% (+1.8%) from 65.37%

Build # 18480907774

Build Type

push

github

Committed by

vigna

Commit Message

Further methods moved to bit_vec_ops; added missing docs; iterators on atomic bit vector no longer take an exclusive reference

Run Details

13 of 29 new or added lines in 2 files covered. (44.83%)

360 existing lines in 5 files now uncovered.

3852 of 5735 relevant lines covered (67.17%)

117331163.32 hits per line

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

65.43

/src/array/partial_array.rs

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

//! Immutable partial array implementations.

use crate::bits::BitVec;
use crate::dict::EliasFanoBuilder;
use crate::dict::elias_fano::EfDict;
use crate::rank_sel::Rank9;
use crate::traits::{BitVecOps, BitVecOpsMut};
use crate::traits::{RankUnchecked, SuccUnchecked};
use mem_dbg::*;

/// Builder for creating an immutable partial array.
///
/// The builder allows you to specify the array length and then add
/// (position, value) pairs. Positions must be added in strictly
/// increasing order.
///
/// To get a builder you can use either [new_dense] or [new_sparse].
#[derive(Debug, Clone, MemDbg, MemSize)]
pub struct PartialArrayBuilder<T, B> {
    builder: B,
    values: Vec<T>,
    len: usize,
    min_next_pos: usize,
}

/// Creates a new builder for a dense partial array of the given length.
///
/// A dense partial array stores a bit vector of the given length to mark
/// which positions contain values, and use ranking on this bit vector to
/// map positions to indices in a contiguous value array.
///
/// If your set of values is really sparse, consider using a
/// [sparse partial array](new_sparse).
///
/// # Examples
///
/// ```rust
/// use sux::array::partial_array;
///
/// let mut builder = partial_array::new_dense(10);
/// builder.set(1, "foo");
/// builder.set(2, "hello");
/// builder.set(7, "world");
///
/// let array = builder.build();
/// assert_eq!(array.get(1), Some(&"foo"));
/// assert_eq!(array.get(2), Some(&"hello"));
/// assert_eq!(array.get(3), None);
/// assert_eq!(array.get(7), Some(&"world"));
/// ```
pub fn new_dense<T>(len: usize) -> PartialArrayBuilder<T, BitVec<Box<[usize]>>> {
    PartialArrayBuilder {
        builder: BitVec::new(len).into(),
        values: vec![],
        len,
        min_next_pos: 0,
    }
}

impl<T> PartialArrayBuilder<T, BitVec<Box<[usize]>>> {
    /// Sets a value at the given position.
    ///
    /// The provided position must be greater than the last position set.
    pub fn set(&mut self, position: usize, value: T) {
        if position < self.min_next_pos {
            panic!(
                "Positions must be set in increasing order: got {} after {}",
                position,
                self.min_next_pos - 1
            );
        }
        if position >= self.len {
            panic!(
                "Position {} is out of bounds for array of len {}",
                position, self.len
            );
        }
        // SAFETY: position < len
        unsafe {
            self.builder.set_unchecked(position, true);
        }
        self.values.push(value);
        self.min_next_pos = position + 1;
    }

    /// Builds the immutable dense partial array.
    pub fn build(self) -> PartialArray<T, Rank9<BitVec<Box<[usize]>>>> {
        let (bit_vec, values) = (self.builder, self.values);
        let rank9 = Rank9::new(bit_vec);
        let values = values.into_boxed_slice();

        PartialArray {
            index: rank9,
            values,
        }
    }
}

/// Creates a new builder for a sparse partial array of the given length.
///
/// A sparse partial array stores the non-empty positions of the array in an
/// [Elias-Fano](crate::dict::EliasFano) structure.
///
/// If your set of values is really dense, consider using a [dense partial
/// array](new_dense).
///
/// # Examples
///
/// ```rust
/// use sux::array::partial_array;
///
/// let mut builder = partial_array::new_sparse(10, 3);
/// builder.set(1, "foo");
/// builder.set(2, "hello");
/// builder.set(7, "world");
///
/// let array = builder.build();
/// assert_eq!(array.get(1), Some(&"foo"));
/// assert_eq!(array.get(2), Some(&"hello"));
/// assert_eq!(array.get(3), None);
/// assert_eq!(array.get(7), Some(&"world"));
/// ```
///
/// Note that you must specify the number of values in advance.
pub fn new_sparse<T>(len: usize, num_values: usize) -> PartialArrayBuilder<T, EliasFanoBuilder> {
    dbg!(len, num_values);

    PartialArrayBuilder {
        builder: EliasFanoBuilder::new(num_values, len),
        values: vec![],
        len,
        min_next_pos: 0,
    }
}

impl<T> PartialArrayBuilder<T, EliasFanoBuilder> {
    /// Sets a value at the given position.
    ///
    /// The provided position must be greater than the last position
    /// set.
    pub fn set(&mut self, position: usize, value: T) {
        dbg!(position);
        if position < self.min_next_pos {
            panic!(
                "Positions must be set in increasing order: got {} after {}",
                position,
                self.min_next_pos - 1
            );
        }
        if position >= self.len {
            panic!(
                "Position {} is out of bounds for array of len {}",
                position, self.len
            );
        }
        // SAFETY: conditions have been just checked.
        unsafe { self.builder.push_unchecked(position) };
        self.values.push(value);
        self.min_next_pos = position + 1;
    }

    /// Builds the immutable sparse partial array.
    pub fn build(self) -> PartialArray<T, (EfDict, usize)> {
        let (builder, values) = (self.builder, self.values);
        let ef_dict = builder.build_with_dict();
        let values = values.into_boxed_slice();

        PartialArray {
            index: (ef_dict, self.min_next_pos),
            values,
        }
    }
}

/// Extends the builder with an iterator of (position, value) pairs.
///
/// Position must be in strictly increasing order. The first returned
/// position must be greater than the last position set.
impl<T> Extend<(usize, T)> for PartialArrayBuilder<T, BitVec<Box<[usize]>>> {
    fn extend<I: IntoIterator<Item = (usize, T)>>(&mut self, iter: I) {
        for (pos, val) in iter {
            self.set(pos, val);
        }
    }
}

/// Extends the builder with an iterator of (position, value) pairs.
///
/// Position must be in strictly increasing order. The first returned
/// position must be greater than the last position set.
impl<T> Extend<(usize, T)> for PartialArrayBuilder<T, EliasFanoBuilder> {
    fn extend<I: IntoIterator<Item = (usize, T)>>(&mut self, iter: I) {
        for (pos, val) in iter {
            self.set(pos, val);
        }
    }
}

/// An immutable partial array that supports efficient queries
/// in compacted storage.
///
/// This structure stores a *partial array*—an array in which only
/// some positions contain values. There is a [dense](new_dense)
/// and a [sparse](new_sparse) implementation with different
/// space/time trade-offs.
///
/// See [`PartialArrayBuilder`] for details on how to create a partial array.
#[derive(Debug, Clone, MemDbg, MemSize)]
#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct PartialArray<T, P> {
    index: P,
    values: Box<[T]>,
}

impl<T, P> PartialArray<T, P> {
    /// Returns the number of values stored in the array.
    #[inline(always)]
    pub fn num_values(&self) -> usize {
        self.values.len()
    }
}

impl<T> PartialArray<T, Rank9<BitVec<Box<[usize]>>>> {
    /// Returns the total length of the array.
    ///
    /// This is the length that was specified when creating the builder,
    /// not the number of values actually stored.
    #[inline(always)]
    pub fn len(&self) -> usize {
        self.index.len()
    }

    /// Returns true if the array length is 0.
    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Gets a reference to the value at the given position.
    ///
    /// Returns `Some(&value)` if a value is present at the position,
    /// or `None` if no value was stored there.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use sux::array::partial_array;
    /// let mut builder = partial_array::new_dense(10);
    /// builder.set(5, 42);
    ///
    /// let array = builder.build();
    /// assert_eq!(array.get(5), Some(&42));
    /// assert_eq!(array.get(6), None);
    /// ```
    pub fn get(&self, position: usize) -> Option<&T> {
        if position >= self.len() {
            panic!(
                "Position {} is out of bounds for array of len {}",
                position,
                self.len()
            );
        }
        // Check if there's a value at this position
        // SAFETY: position < len()
        if !unsafe { self.index.get_unchecked(position) } {
            return None;
        }

        // Use ranking to find the index in the values array
        // SAFETY: position < len()
        let value_index = unsafe { self.index.rank_unchecked(position) };

        // SAFETY: necessarily value_index < num_values().
        Some(unsafe { self.values.get_unchecked(value_index) })
    }
}

impl<T> PartialArray<T, (EfDict, usize)> {
    /// Returns the total length of the array.
    ///
    /// This is the length that was specified when creating the builder,
    /// not the number of values actually stored.
    #[inline(always)]
    pub fn len(&self) -> usize {
        self.index.0.upper_bound()
    }

    /// Returns true if the array len is 0.
    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.index.0.len() == 0
    }

    /// Gets a reference to the value at the given position.
    ///
    /// Returns `Some(&value)` if a value is present at the position,
    /// or `None` if no value was stored there.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use sux::array::partial_array;
    /// let mut builder = partial_array::new_sparse(10, 1);
    /// builder.set(5, 42);
    ///
    /// let array = builder.build();
    /// assert_eq!(array.get(5), Some(&42));
    /// assert_eq!(array.get(6), None);
    /// ```
    pub fn get(&self, position: usize) -> Option<&T> {
        if position >= self.index.1 {
            if position >= self.len() {
                panic!(
                    "Position {} is out of bounds for array of len {}",
                    position,
                    self.len()
                );
            }
            return None;
        }
        // Check if there's a value at this position
        // SAFETY: position <= last set position
        let (index, pos) = unsafe { self.index.0.succ_unchecked::<false>(position) };

        if pos != position {
            None
        } else {
            // SAFETY: necessarily value_index < num values.
            Some(unsafe { self.values.get_unchecked(index) })
        }
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2025 Sebastiano Vigna
3	*
4	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
5	*/
6
7	//! Immutable partial array implementations.
8
9	use crate::bits::BitVec;
10	use crate::dict::EliasFanoBuilder;
11	use crate::dict::elias_fano::EfDict;
12	use crate::rank_sel::Rank9;
13	use crate::traits::{BitVecOps, BitVecOpsMut};
14	use crate::traits::{RankUnchecked, SuccUnchecked};
15	use mem_dbg::*;
16
17	/// Builder for creating an immutable partial array.
18	///
19	/// The builder allows you to specify the array length and then add
20	/// (position, value) pairs. Positions must be added in strictly
21	/// increasing order.
22	///
23	/// To get a builder you can use either [new_dense] or [new_sparse].
24	#[derive(Debug, Clone, MemDbg, MemSize)]
25	pub struct PartialArrayBuilder<T, B> {
26	builder: B,
27	values: Vec<T>,
28	len: usize,
29	min_next_pos: usize,
30	}
31
32	/// Creates a new builder for a dense partial array of the given length.
33	///
34	/// A dense partial array stores a bit vector of the given length to mark
35	/// which positions contain values, and use ranking on this bit vector to
36	/// map positions to indices in a contiguous value array.
37	///
38	/// If your set of values is really sparse, consider using a
39	/// [sparse partial array](new_sparse).
40	///
41	/// # Examples
42	///
43	/// ```rust
44	/// use sux::array::partial_array;
45	///
46	/// let mut builder = partial_array::new_dense(10);
47	/// builder.set(1, "foo");
48	/// builder.set(2, "hello");
49	/// builder.set(7, "world");
50	///
51	/// let array = builder.build();
52	/// assert_eq!(array.get(1), Some(&"foo"));
53	/// assert_eq!(array.get(2), Some(&"hello"));
54	/// assert_eq!(array.get(3), None);
55	/// assert_eq!(array.get(7), Some(&"world"));
56	/// ```
57	pub fn new_dense<T>(len: usize) -> PartialArrayBuilder<T, BitVec<Box<[usize]>>> {	6✔
58	PartialArrayBuilder {
59	builder: BitVec::new(len).into(),	24✔
60	values: vec![],	6✔
61	len,
62	min_next_pos: 0,
63	}
64	}
65
66	impl<T> PartialArrayBuilder<T, BitVec<Box<[usize]>>> {
67	/// Sets a value at the given position.
68	///
69	/// The provided position must be greater than the last position set.
70	pub fn set(&mut self, position: usize, value: T) {	7✔
71	if position < self.min_next_pos {	7✔
72	panic!(	1✔
73	"Positions must be set in increasing order: got {} after {}",	×
74	position,	×
UNCOV 75	self.min_next_pos - 1	×
76	);
77	}
78	if position >= self.len {	6✔
79	panic!(	1✔
80	"Position {} is out of bounds for array of len {}",	1✔
UNCOV 81	position, self.len	×
82	);
83	}
84	// SAFETY: position < len
85	unsafe {
UNCOV 86	self.builder.set_unchecked(position, true);	×
87	}
88	self.values.push(value);	×
UNCOV 89	self.min_next_pos = position + 1;	×
90	}
91
92	/// Builds the immutable dense partial array.
93	pub fn build(self) -> PartialArray<T, Rank9<BitVec<Box<[usize]>>>> {	4✔
94	let (bit_vec, values) = (self.builder, self.values);	12✔
95	let rank9 = Rank9::new(bit_vec);	12✔
96	let values = values.into_boxed_slice();	12✔
97
98	PartialArray {
99	index: rank9,
100	values,
101	}
102	}
103	}
104
105	/// Creates a new builder for a sparse partial array of the given length.
106	///
107	/// A sparse partial array stores the non-empty positions of the array in an
108	/// [Elias-Fano](crate::dict::EliasFano) structure.
109	///
110	/// If your set of values is really dense, consider using a [dense partial
111	/// array](new_dense).
112	///
113	/// # Examples
114	///
115	/// ```rust
116	/// use sux::array::partial_array;
117	///
118	/// let mut builder = partial_array::new_sparse(10, 3);
119	/// builder.set(1, "foo");
120	/// builder.set(2, "hello");
121	/// builder.set(7, "world");
122	///
123	/// let array = builder.build();
124	/// assert_eq!(array.get(1), Some(&"foo"));
125	/// assert_eq!(array.get(2), Some(&"hello"));
126	/// assert_eq!(array.get(3), None);
127	/// assert_eq!(array.get(7), Some(&"world"));
128	/// ```
129	///
130	/// Note that you must specify the number of values in advance.
131	pub fn new_sparse<T>(len: usize, num_values: usize) -> PartialArrayBuilder<T, EliasFanoBuilder> {	6✔
132	dbg!(len, num_values);	18✔
133
134	PartialArrayBuilder {
135	builder: EliasFanoBuilder::new(num_values, len),	24✔
136	values: vec![],	6✔
137	len,
138	min_next_pos: 0,
139	}
140	}
141
142	impl<T> PartialArrayBuilder<T, EliasFanoBuilder> {
143	/// Sets a value at the given position.
144	///
145	/// The provided position must be greater than the last position
146	/// set.
147	pub fn set(&mut self, position: usize, value: T) {	7✔
148	dbg!(position);	14✔
149	if position < self.min_next_pos {	7✔
150	panic!(	1✔
151	"Positions must be set in increasing order: got {} after {}",	×
152	position,	×
UNCOV 153	self.min_next_pos - 1	×
154	);
155	}
156	if position >= self.len {	6✔
157	panic!(	1✔
158	"Position {} is out of bounds for array of len {}",	1✔
UNCOV 159	position, self.len	×
160	);
161	}
162	// SAFETY: conditions have been just checked.
163	unsafe { self.builder.push_unchecked(position) };	×
164	self.values.push(value);	×
UNCOV 165	self.min_next_pos = position + 1;	×
166	}
167
168	/// Builds the immutable sparse partial array.
169	pub fn build(self) -> PartialArray<T, (EfDict, usize)> {	4✔
170	let (builder, values) = (self.builder, self.values);	12✔
171	let ef_dict = builder.build_with_dict();	12✔
172	let values = values.into_boxed_slice();	12✔
173
174	PartialArray {
175	index: (ef_dict, self.min_next_pos),	4✔
176	values,
177	}
178	}
179	}
180
181	/// Extends the builder with an iterator of (position, value) pairs.
182	///
183	/// Position must be in strictly increasing order. The first returned
184	/// position must be greater than the last position set.
185	impl<T> Extend<(usize, T)> for PartialArrayBuilder<T, BitVec<Box<[usize]>>> {
186	fn extend<I: IntoIterator<Item = (usize, T)>>(&mut self, iter: I) {	×
187	for (pos, val) in iter {	×
UNCOV 188	self.set(pos, val);	×
189	}
190	}
191	}
192
193	/// Extends the builder with an iterator of (position, value) pairs.
194	///
195	/// Position must be in strictly increasing order. The first returned
196	/// position must be greater than the last position set.
197	impl<T> Extend<(usize, T)> for PartialArrayBuilder<T, EliasFanoBuilder> {
198	fn extend<I: IntoIterator<Item = (usize, T)>>(&mut self, iter: I) {	×
199	for (pos, val) in iter {	×
UNCOV 200	self.set(pos, val);	×
201	}
202	}
203	}
204
205	/// An immutable partial array that supports efficient queries
206	/// in compacted storage.
207	///
208	/// This structure stores a partial array—an array in which only
209	/// some positions contain values. There is a [dense](new_dense)
210	/// and a [sparse](new_sparse) implementation with different
211	/// space/time trade-offs.
212	///
213	/// See [`PartialArrayBuilder`] for details on how to create a partial array.
214	#[derive(Debug, Clone, MemDbg, MemSize)]
215	#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
216	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
217	pub struct PartialArray<T, P> {
218	index: P,
219	values: Box<[T]>,
220	}
221
222	impl<T, P> PartialArray<T, P> {
223	/// Returns the number of values stored in the array.
224	#[inline(always)]
225	pub fn num_values(&self) -> usize {	6✔
226	self.values.len()	12✔
227	}
228	}
229
230	impl<T> PartialArray<T, Rank9<BitVec<Box<[usize]>>>> {
231	/// Returns the total length of the array.
232	///
233	/// This is the length that was specified when creating the builder,
234	/// not the number of values actually stored.
235	#[inline(always)]
236	pub fn len(&self) -> usize {	1,014✔
237	self.index.len()	2,028✔
238	}
239
240	/// Returns true if the array length is 0.
241	#[inline(always)]
242	pub fn is_empty(&self) -> bool {	1✔
243	self.len() == 0	1✔
244	}
245
246	/// Gets a reference to the value at the given position.
247	///
248	/// Returns `Some(&value)` if a value is present at the position,
249	/// or `None` if no value was stored there.
250	///
251	/// # Examples
252	///
253	/// ```rust
254	/// use sux::array::partial_array;
255	/// let mut builder = partial_array::new_dense(10);
256	/// builder.set(5, 42);
257	///
258	/// let array = builder.build();
259	/// assert_eq!(array.get(5), Some(&42));
260	/// assert_eq!(array.get(6), None);
261	/// ```
262	pub fn get(&self, position: usize) -> Option<&T> {	1,011✔
263	if position >= self.len() {	2,022✔
264	panic!(	1✔
265	"Position {} is out of bounds for array of len {}",	×
266	position,	×
UNCOV 267	self.len()	×
268	);
269	}
270	// Check if there's a value at this position
271	// SAFETY: position < len()
272	if !unsafe { self.index.get_unchecked(position) } {	2,020✔
273	return None;	1,006✔
274	}
275
276	// Use ranking to find the index in the values array
277	// SAFETY: position < len()
278	let value_index = unsafe { self.index.rank_unchecked(position) };	16✔
279
280	// SAFETY: necessarily value_index < num_values().
281	Some(unsafe { self.values.get_unchecked(value_index) })	8✔
282	}
283	}
284
285	impl<T> PartialArray<T, (EfDict, usize)> {
286	/// Returns the total length of the array.
287	///
288	/// This is the length that was specified when creating the builder,
289	/// not the number of values actually stored.
290	#[inline(always)]
291	pub fn len(&self) -> usize {	504✔
292	self.index.0.upper_bound()	1,008✔
293	}
294
295	/// Returns true if the array len is 0.
296	#[inline(always)]
297	pub fn is_empty(&self) -> bool {	1✔
298	self.index.0.len() == 0	1✔
299	}
300
301	/// Gets a reference to the value at the given position.
302	///
303	/// Returns `Some(&value)` if a value is present at the position,
304	/// or `None` if no value was stored there.
305	///
306	/// # Examples
307	///
308	/// ```rust
309	/// use sux::array::partial_array;
310	/// let mut builder = partial_array::new_sparse(10, 1);
311	/// builder.set(5, 42);
312	///
313	/// let array = builder.build();
314	/// assert_eq!(array.get(5), Some(&42));
315	/// assert_eq!(array.get(6), None);
316	/// ```
317	pub fn get(&self, position: usize) -> Option<&T> {	1,011✔
318	if position >= self.index.1 {	1,011✔
319	if position >= self.len() {	1,004✔
320	panic!(	1✔
321	"Position {} is out of bounds for array of len {}",	×
322	position,	×
UNCOV 323	self.len()	×
324	);
325	}
326	return None;	501✔
327	}
328	// Check if there's a value at this position
329	// SAFETY: position <= last set position
UNCOV 330	let (index, pos) = unsafe { self.index.0.succ_unchecked::<false>(position) };	×
331
UNCOV 332	if pos != position {	×
333	None	505✔
334	} else {
335	// SAFETY: necessarily value_index < num values.
336	Some(unsafe { self.values.get_unchecked(index) })	4✔
337	}
338	}
339	}

vigna / sux-rs / 18480907774

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