20332219103

Committed 18 Dec 2025 09:26AM UTC coverage: 74.654% (+0.03%) from 74.624%

Build # 20332219103

Build Type

Pull #91

github

Committed by

web-flow

Commit Message

Merge fa079d0ba into 412c3dabf

Pull Request Pull Request #91: Add PartialValueArray

Run Details

56 of 74 new or added lines in 1 file covered. (75.68%)

14 existing lines in 1 file now uncovered.

4530 of 6068 relevant lines covered (74.65%)

121143985.0 hits per line

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

76.74

/src/array/partial_value_array.rs

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

//! Immutable partial array implementations for cheaply-clonable values
//!
//! This supports storing values in [`BitFieldVec`] to save memory.

use std::marker::PhantomData;

use mem_dbg::*;
use value_traits::slices::SliceByValue;

use crate::bits::BitFieldVec;
use crate::bits::BitVec;
use crate::dict::EliasFanoBuilder;
use crate::dict::elias_fano::EliasFano;
use crate::rank_sel::{Rank9, SelectZeroAdaptConst};
use crate::traits::Word;
use crate::traits::{BitVecOps, BitVecOpsMut};
use crate::traits::{RankUnchecked, SuccUnchecked};

/// An internal index for sparse partial arrays.
///
/// We cannot use directly an [Elias–Fano](crate::dict::EliasFano) structure
/// because we need to keep track of the first invalid position; and we need to
/// keep track of the first invalid position because we want to implement just
/// [`SuccUnchecked`](crate::traits::SuccUnchecked) on the Elias–Fano structure,
/// because it requires just
/// [`SelectZeroUnchecked`](crate::traits::SelectZeroUnchecked), whereas
/// [`Succ`](crate::traits::Succ) would require
/// [`SelectUnchecked`](crate::traits::SelectUnchecked) as well.
#[doc(hidden)]
#[derive(Debug, Clone, MemDbg, MemSize)]
#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct SparseIndex<D> {
    ef: EliasFano<SelectZeroAdaptConst<BitVec<D>, D, 12, 3>>,
    /// self.ef should be not be queried for values >= self.first_invalid_position
    first_invalid_pos: usize,
}

type DenseIndex = Rank9<BitVec<Box<[usize]>>>;

/// 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 PartialValueArrayBuilder<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_value_array;
///
/// let mut builder = partial_value_array::new_dense(10);
/// builder.set(1, 123u32);
/// builder.set(2, 45678);
/// builder.set(7, 90);
///
/// let array = builder.build_bitfieldvec();
/// assert_eq!(array.get(1), Some(123));
/// assert_eq!(array.get(2), Some(45678));
/// assert_eq!(array.get(3), None);
/// assert_eq!(array.get(7), Some(90));
/// ```
pub fn new_dense<T>(len: usize) -> PartialValueArrayBuilder<T, BitVec<Box<[usize]>>> {
    PartialValueArrayBuilder {
        builder: BitVec::new(len).into(),
        values: vec![],
        len,
        min_next_pos: 0,
    }
}

fn build_bitfieldvec<T: Word>(values: Vec<T>) -> BitFieldVec<T> {
    let bit_width = values
        .iter()
        .map(|value| value.len())
        .max()
        .unwrap_or(1)
        .try_into()
        .expect("bit_width overflowed usize");
    let mut bfv = BitFieldVec::with_capacity(bit_width, values.len());
    for value in values {
        bfv.push(value);
    }
    bfv
}

impl<T: Clone> PartialValueArrayBuilder<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 using [`BitFieldVec`] as backend.
    pub fn build_bitfieldvec(self) -> PartialValueArray<T, DenseIndex, BitFieldVec<T>>
    where
        T: Word,
    {
        let (bit_vec, values) = (self.builder, self.values);
        let rank9 = Rank9::new(bit_vec);
        let values = build_bitfieldvec(values);

        PartialValueArray {
            index: rank9,
            values,
            _marker: PhantomData,
        }
    }
}

/// 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_value_array;
///
/// let mut builder = partial_value_array::new_sparse(10, 3);
/// builder.set(1, 123u32);
/// builder.set(2, 45678);
/// builder.set(7, 90);
///
/// let array = builder.build_bitfieldvec();
/// assert_eq!(array.get(1), Some(123));
/// assert_eq!(array.get(2), Some(45678));
/// assert_eq!(array.get(3), None);
/// assert_eq!(array.get(7), Some(90));
/// ```
///
/// Note that you must specify the number of values in advance.
pub fn new_sparse<T>(
    len: usize,
    num_values: usize,
) -> PartialValueArrayBuilder<T, EliasFanoBuilder> {
    PartialValueArrayBuilder {
        builder: EliasFanoBuilder::new(num_values, len),
        values: vec![],
        len,
        min_next_pos: 0,
    }
}

impl<T: Clone> PartialValueArrayBuilder<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) {
        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 using [`BitFieldVec`] as backend.
    pub fn build_bitfieldvec(
        self,
    ) -> PartialValueArray<T, SparseIndex<Box<[usize]>>, BitFieldVec<T>>
    where
        T: Word,
    {
        let (builder, values) = (self.builder, self.values);
        let ef_dict = builder.build_with_dict();
        let values = build_bitfieldvec(values);

        PartialValueArray {
            index: SparseIndex {
                ef: ef_dict,
                first_invalid_pos: self.min_next_pos,
            },
            values,
            _marker: PhantomData,
        }
    }
}

/// 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: Clone> Extend<(usize, T)> for PartialValueArrayBuilder<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: Clone> Extend<(usize, T)> for PartialValueArrayBuilder<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 [`PartialValueArrayBuilder`] 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 PartialValueArray<T: Clone, P, V: SliceByValue<Value = T>> {
    index: P,
    values: V,
    _marker: PhantomData<T>,
}

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

impl<T: Clone, V: SliceByValue<Value = T>> PartialValueArray<T, DenseIndex, V> {
    /// 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_value_array;
    /// let mut builder = partial_value_array::new_dense(10);
    /// builder.set(5, 42u32);
    ///
    /// let array = builder.build_bitfieldvec();
    /// 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_value_unchecked(value_index) })
    }
}

impl<T: Clone, D: AsRef<[usize]>, V: SliceByValue<Value = T>>
    PartialValueArray<T, SparseIndex<D>, V>
{
    /// 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.ef.upper_bound()
    }

    /// Returns true if the array len is 0.
    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.index.ef.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_value_array;
    /// let mut builder = partial_value_array::new_sparse(10, 1);
    /// builder.set(5, 42u32);
    ///
    /// let array = builder.build_bitfieldvec();
    /// 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.first_invalid_pos {
            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.ef.succ_unchecked::<false>(position) };

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

1	/*
2	* SPDX-FileCopyrightText: 2025 Inria
3	* SPDX-FileCopyrightText: 2025 Sebastiano Vigna
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7
8	//! Immutable partial array implementations for cheaply-clonable values
9	//!
10	//! This supports storing values in [`BitFieldVec`] to save memory.
11
12	use std::marker::PhantomData;
13
14	use mem_dbg::*;
15	use value_traits::slices::SliceByValue;
16
17	use crate::bits::BitFieldVec;
18	use crate::bits::BitVec;
19	use crate::dict::EliasFanoBuilder;
20	use crate::dict::elias_fano::EliasFano;
21	use crate::rank_sel::{Rank9, SelectZeroAdaptConst};
22	use crate::traits::Word;
23	use crate::traits::{BitVecOps, BitVecOpsMut};
24	use crate::traits::{RankUnchecked, SuccUnchecked};
25
26	/// An internal index for sparse partial arrays.
27	///
28	/// We cannot use directly an [Elias–Fano](crate::dict::EliasFano) structure
29	/// because we need to keep track of the first invalid position; and we need to
30	/// keep track of the first invalid position because we want to implement just
31	/// [`SuccUnchecked`](crate::traits::SuccUnchecked) on the Elias–Fano structure,
32	/// because it requires just
33	/// [`SelectZeroUnchecked`](crate::traits::SelectZeroUnchecked), whereas
34	/// [`Succ`](crate::traits::Succ) would require
35	/// [`SelectUnchecked`](crate::traits::SelectUnchecked) as well.
36	#[doc(hidden)]
37	#[derive(Debug, Clone, MemDbg, MemSize)]
38	#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
39	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
40	pub struct SparseIndex<D> {
41	ef: EliasFano<SelectZeroAdaptConst<BitVec<D>, D, 12, 3>>,
42	/// self.ef should be not be queried for values >= self.first_invalid_position
43	first_invalid_pos: usize,
44	}
45
46	type DenseIndex = Rank9<BitVec<Box<[usize]>>>;
47
48	/// Builder for creating an immutable partial array.
49	///
50	/// The builder allows you to specify the array length and then add
51	/// (position, value) pairs. Positions must be added in strictly
52	/// increasing order.
53	///
54	/// To get a builder you can use either [new_dense] or [new_sparse].
55	#[derive(Debug, Clone, MemDbg, MemSize)]
56	pub struct PartialValueArrayBuilder<T, B> {
57	builder: B,
58	values: Vec<T>,
59	len: usize,
60	min_next_pos: usize,
61	}
62
63	/// Creates a new builder for a dense partial array of the given length.
64	///
65	/// A dense partial array stores a bit vector of the given length to mark
66	/// which positions contain values, and use ranking on this bit vector to
67	/// map positions to indices in a contiguous value array.
68	///
69	/// If your set of values is really sparse, consider using a
70	/// [sparse partial array](new_sparse).
71	///
72	/// # Examples
73	///
74	/// ```rust
75	/// use sux::array::partial_value_array;
76	///
77	/// let mut builder = partial_value_array::new_dense(10);
78	/// builder.set(1, 123u32);
79	/// builder.set(2, 45678);
80	/// builder.set(7, 90);
81	///
82	/// let array = builder.build_bitfieldvec();
83	/// assert_eq!(array.get(1), Some(123));
84	/// assert_eq!(array.get(2), Some(45678));
85	/// assert_eq!(array.get(3), None);
86	/// assert_eq!(array.get(7), Some(90));
87	/// ```
88	pub fn new_dense<T>(len: usize) -> PartialValueArrayBuilder<T, BitVec<Box<[usize]>>> {	5✔
89	PartialValueArrayBuilder {
90	builder: BitVec::new(len).into(),	20✔
91	values: vec![],	5✔
92	len,
93	min_next_pos: 0,
94	}
95	}
96
97	fn build_bitfieldvec<T: Word>(values: Vec<T>) -> BitFieldVec<T> {	9✔
98	let bit_width = values	18✔
99	.iter()
100	.map(\|value\| value.len())	31✔
101	.max()
102	.unwrap_or(1)
103	.try_into()
104	.expect("bit_width overflowed usize");
105	let mut bfv = BitFieldVec::with_capacity(bit_width, values.len());	45✔
106	for value in values {	31✔
107	bfv.push(value);	22✔
108	}
109	bfv	9✔
110	}
111
112	impl<T: Clone> PartialValueArrayBuilder<T, BitVec<Box<[usize]>>> {
113	/// Sets a value at the given position.
114	///
115	/// The provided position must be greater than the last position set.
116	pub fn set(&mut self, position: usize, value: T) {	6✔
117	if position < self.min_next_pos {	6✔
118	panic!(	1✔
NEW 119	"Positions must be set in increasing order: got {} after {}",	×
NEW 120	position,	×
121	self.min_next_pos - 1	1✔
122	);
123	}
124	if position >= self.len {	5✔
NEW 125	panic!(	×
NEW 126	"Position {} is out of bounds for array of len {}",	×
NEW 127	position, self.len	×
128	);
129	}
130	// SAFETY: position < len
131	unsafe {
132	self.builder.set_unchecked(position, true);	10✔
133	}
134	self.values.push(value);	15✔
135	self.min_next_pos = position + 1;	5✔
136	}
137
138	/// Builds the immutable dense partial array using [`BitFieldVec`] as backend.
139	pub fn build_bitfieldvec(self) -> PartialValueArray<T, DenseIndex, BitFieldVec<T>>	4✔
140	where
141	T: Word,
142	{
143	let (bit_vec, values) = (self.builder, self.values);	12✔
144	let rank9 = Rank9::new(bit_vec);	12✔
145	let values = build_bitfieldvec(values);	12✔
146
147	PartialValueArray {
148	index: rank9,
149	values,
150	_marker: PhantomData,
151	}
152	}
153	}
154
155	/// Creates a new builder for a sparse partial array of the given length.
156	///
157	/// A sparse partial array stores the non-empty positions of the array in an
158	/// [Elias-Fano](crate::dict::EliasFano) structure.
159	///
160	/// If your set of values is really dense, consider using a [dense partial
161	/// array](new_dense).
162	///
163	/// # Examples
164	///
165	/// ```rust
166	/// use sux::array::partial_value_array;
167	///
168	/// let mut builder = partial_value_array::new_sparse(10, 3);
169	/// builder.set(1, 123u32);
170	/// builder.set(2, 45678);
171	/// builder.set(7, 90);
172	///
173	/// let array = builder.build_bitfieldvec();
174	/// assert_eq!(array.get(1), Some(123));
175	/// assert_eq!(array.get(2), Some(45678));
176	/// assert_eq!(array.get(3), None);
177	/// assert_eq!(array.get(7), Some(90));
178	/// ```
179	///
180	/// Note that you must specify the number of values in advance.
181	pub fn new_sparse<T>(	6✔
182	len: usize,
183	num_values: usize,
184	) -> PartialValueArrayBuilder<T, EliasFanoBuilder> {
185	PartialValueArrayBuilder {
186	builder: EliasFanoBuilder::new(num_values, len),	24✔
187	values: vec![],	6✔
188	len,
189	min_next_pos: 0,
190	}
191	}
192
193	impl<T: Clone> PartialValueArrayBuilder<T, EliasFanoBuilder> {
194	/// Sets a value at the given position.
195	///
196	/// The provided position must be greater than the last position
197	/// set.
198	pub fn set(&mut self, position: usize, value: T) {	9✔
199	if position < self.min_next_pos {	9✔
200	panic!(	1✔
NEW 201	"Positions must be set in increasing order: got {} after {}",	×
NEW 202	position,	×
203	self.min_next_pos - 1	1✔
204	);
205	}
206	if position >= self.len {	8✔
NEW 207	panic!(	×
NEW 208	"Position {} is out of bounds for array of len {}",	×
NEW 209	position, self.len	×
210	);
211	}
212	// SAFETY: conditions have been just checked.
213	unsafe { self.builder.push_unchecked(position) };	24✔
214	self.values.push(value);	24✔
215	self.min_next_pos = position + 1;	8✔
216	}
217
218	/// Builds the immutable sparse partial array using [`BitFieldVec`] as backend.
219	pub fn build_bitfieldvec(	5✔
220	self,
221	) -> PartialValueArray<T, SparseIndex<Box<[usize]>>, BitFieldVec<T>>
222	where
223	T: Word,
224	{
225	let (builder, values) = (self.builder, self.values);	15✔
226	let ef_dict = builder.build_with_dict();	15✔
227	let values = build_bitfieldvec(values);	15✔
228
229	PartialValueArray {
230	index: SparseIndex {	10✔
231	ef: ef_dict,
232	first_invalid_pos: self.min_next_pos,
233	},
234	values,
235	_marker: PhantomData,
236	}
237	}
238	}
239
240	/// Extends the builder with an iterator of (position, value) pairs.
241	///
242	/// Position must be in strictly increasing order. The first returned
243	/// position must be greater than the last position set.
244	impl<T: Clone> Extend<(usize, T)> for PartialValueArrayBuilder<T, BitVec<Box<[usize]>>> {
NEW 245	fn extend<I: IntoIterator<Item = (usize, T)>>(&mut self, iter: I) {	×
NEW 246	for (pos, val) in iter {	×
NEW 247	self.set(pos, val);	×
248	}
249	}
250	}
251
252	/// Extends the builder with an iterator of (position, value) pairs.
253	///
254	/// Position must be in strictly increasing order. The first returned
255	/// position must be greater than the last position set.
256	impl<T: Clone> Extend<(usize, T)> for PartialValueArrayBuilder<T, EliasFanoBuilder> {
NEW 257	fn extend<I: IntoIterator<Item = (usize, T)>>(&mut self, iter: I) {	×
NEW 258	for (pos, val) in iter {	×
NEW 259	self.set(pos, val);	×
260	}
261	}
262	}
263
264	/// An immutable partial array that supports efficient queries
265	/// in compacted storage.
266	///
267	/// This structure stores a partial array—an array in which only
268	/// some positions contain values. There is a [dense](new_dense)
269	/// and a [sparse](new_sparse) implementation with different
270	/// space/time trade-offs.
271	///
272	/// See [`PartialValueArrayBuilder`] for details on how to create a partial array.
273	#[derive(Debug, Clone, MemDbg, MemSize)]
274	#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
275	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
276	pub struct PartialValueArray<T: Clone, P, V: SliceByValue<Value = T>> {
277	index: P,
278	values: V,
279	_marker: PhantomData<T>,
280	}
281
282	impl<T: Clone, P, V: SliceByValue<Value = T>> PartialValueArray<T, P, V> {
283	/// Returns the number of values stored in the array.
284	#[inline(always)]
285	pub fn num_values(&self) -> usize {	8✔
286	self.values.len()	16✔
287	}
288	}
289
290	impl<T: Clone, V: SliceByValue<Value = T>> PartialValueArray<T, DenseIndex, V> {
291	/// Returns the total length of the array.
292	///
293	/// This is the length that was specified when creating the builder,
294	/// not the number of values actually stored.
295	#[inline(always)]
296	pub fn len(&self) -> usize {	6✔
297	self.index.len()	12✔
298	}
299
300	/// Returns true if the array length is 0.
301	#[inline(always)]
302	pub fn is_empty(&self) -> bool {	1✔
303	self.len() == 0	1✔
304	}
305
306	/// Gets a reference to the value at the given position.
307	///
308	/// Returns `Some(&value)` if a value is present at the position,
309	/// or `None` if no value was stored there.
310	///
311	/// # Examples
312	///
313	/// ```rust
314	/// use sux::array::partial_value_array;
315	/// let mut builder = partial_value_array::new_dense(10);
316	/// builder.set(5, 42u32);
317	///
318	/// let array = builder.build_bitfieldvec();
319	/// assert_eq!(array.get(5), Some(42));
320	/// assert_eq!(array.get(6), None);
321	/// ```
322	pub fn get(&self, position: usize) -> Option<T> {	1,011✔
323	if position >= self.len() {	2,022✔
324	panic!(	1✔
NEW 325	"Position {} is out of bounds for array of len {}",	×
NEW 326	position,	×
327	self.len()	2✔
328	);
329	}
330	// Check if there's a value at this position
331	// SAFETY: position < len()
332	if !unsafe { self.index.get_unchecked(position) } {	2,020✔
333	return None;	1,006✔
334	}
335
336	// Use ranking to find the index in the values array
337	// SAFETY: position < len()
338	let value_index = unsafe { self.index.rank_unchecked(position) };	16✔
339
340	// SAFETY: necessarily value_index < num_values().
341	Some(unsafe { self.values.get_value_unchecked(value_index) })	8✔
342	}
343	}
344
345	impl<T: Clone, D: AsRef<[usize]>, V: SliceByValue<Value = T>>
346	PartialValueArray<T, SparseIndex<D>, V>
347	{
348	/// Returns the total length of the array.
349	///
350	/// This is the length that was specified when creating the builder,
351	/// not the number of values actually stored.
352	#[inline(always)]
353	pub fn len(&self) -> usize {	7✔
354	self.index.ef.upper_bound()	14✔
355	}
356
357	/// Returns true if the array len is 0.
358	#[inline(always)]
359	pub fn is_empty(&self) -> bool {	1✔
360	self.index.ef.len() == 0	1✔
361	}
362
363	/// Gets a reference to the value at the given position.
364	///
365	/// Returns `Some(&value)` if a value is present at the position,
366	/// or `None` if no value was stored there.
367	///
368	/// # Examples
369	///
370	/// ```rust
371	/// use sux::array::partial_value_array;
372	/// let mut builder = partial_value_array::new_sparse(10, 1);
373	/// builder.set(5, 42u32);
374	///
375	/// let array = builder.build_bitfieldvec();
376	/// assert_eq!(array.get(5), Some(42));
377	/// assert_eq!(array.get(6), None);
378	/// ```
379	pub fn get(&self, position: usize) -> Option<T> {	1,031✔
380	if position >= self.index.first_invalid_pos {	1,031✔
381	if position >= self.len() {	1,012✔
382	panic!(	1✔
383	"Position {} is out of bounds for array of len {}",	×
384	position,	×
385	self.len()	2✔
386	);
387	}
388	return None;	505✔
389	}
390	// Check if there's a value at this position
391	// SAFETY: position <= last set position
392	let (index, pos) = unsafe { self.index.ef.succ_unchecked::<false>(position) };	2,100✔
393
394	if pos != position {	525✔
395	None	515✔
396	} else {
397	// SAFETY: necessarily value_index < num values.
398	Some(unsafe { self.values.get_value_unchecked(index) })	20✔
399	}
400	}
401	}

vigna / sux-rs / 20332219103

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