23377228256

Committed 21 Mar 2026 10:01AM UTC coverage: 76.275% (-0.2%) from 76.442%

Build # 23377228256

Build Type

push

github

Committed by

vigna

Commit Message

From EliasFano, try_from generic prefix sums

Coverage Stats

1 of 18 new or added lines in 1 file covered. (5.56%)

106 existing lines in 4 files now uncovered.

5430 of 7119 relevant lines covered (76.27%)

110381855.01 hits per line

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

76.92

/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](PartialArray) implementations.

use std::marker::PhantomData;

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

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

// Rank9 is inherently u64-based, so the dense index must use u64 backing
// regardless of usize.
type DenseIndex = Rank9<BitVec<Box<[u64]>>>;

/// 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<u64, SelectZeroAdaptConst<BitVec<D>, Box<[usize]>, 12, 3>>,
    /// self.ef should not be queried for values >= self.first_invalid_position
    first_invalid_pos: 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 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 uses 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<[u64]>>> {
    let n_of_words = len.div_ceil(64);
    // SAFETY: the backing has exactly enough words for len bits
    let bit_vec = unsafe { BitVec::from_raw_parts(vec![0u64; n_of_words].into_boxed_slice(), len) };
    PartialArrayBuilder {
        builder: bit_vec,
        values: vec![],
        len,
        min_next_pos: 0,
    }
}

impl<T> PartialArrayBuilder<T, BitVec<Box<[u64]>>> {
    /// 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
            );
        }
        panic_if_out_of_bounds!(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<[u64]>>>> {
        let (bit_vec, values) = (self.builder, self.values);
        let rank9 = Rank9::new(bit_vec);
        let values = values.into_boxed_slice();

        PartialArray {
            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_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<u64>> {
    PartialArrayBuilder {
        builder: EliasFanoBuilder::<u64>::new(num_values, len as u64),
        values: vec![],
        len,
        min_next_pos: 0,
    }
}

impl<T> PartialArrayBuilder<T, EliasFanoBuilder<u64>> {
    /// 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
            );
        }
        panic_if_out_of_bounds!(position, self.len);
        // SAFETY: conditions have been just checked
        unsafe { self.builder.push_unchecked(position as u64) };
        self.values.push(value);
        self.min_next_pos = position + 1;
    }

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

        PartialArray {
            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> Extend<(usize, T)> for PartialArrayBuilder<T, BitVec<Box<[u64]>>> {
    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<u64>> {
    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.
///
/// For convenience, this structure implements [`SliceByValue`].
///
/// 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, V: AsRef<[T]> = Box<[T]>> {
    index: P,
    values: V,
    _marker: PhantomData<T>,
}

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

impl<T, V: AsRef<[T]>> PartialArray<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_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> {
        panic_if_out_of_bounds!(position, self.len());

        // SAFETY: we just checked
        unsafe { self.get_unchecked(position) }
    }

    /// # Safety
    ///
    /// position < len()
    pub unsafe fn get_unchecked(&self, position: usize) -> Option<&T> {
        // Check if there's a value at this position
        // SAFETY: position < len() guaranteed by caller
        if !unsafe { self.index.get_unchecked(position) } {
            return None;
        }

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

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

impl<T, D: Backend<Word = usize> + AsRef<[usize]>, V: AsRef<[T]>>
    PartialArray<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() as usize
    }

    /// Returns true if the array len is 0.
    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.index.ef.upper_bound() == 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> {
        panic_if_out_of_bounds!(position, self.len());

        // SAFETY: we just checked
        unsafe { self.get_unchecked(position) }
    }

    /// # Safety
    ///
    /// position < len()
    pub unsafe fn get_unchecked(&self, position: usize) -> Option<&T> {
        if position >= self.index.first_invalid_pos {
            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 as u64) };

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

/// Returns an option even when using `get_value_unchecked` because it should be safe to call
/// whenever `position < len()`.
impl<T: Clone, V: AsRef<[T]>> SliceByValue for PartialArray<T, DenseIndex, V> {
    type Value = Option<T>;

    fn len(&self) -> usize {
        self.len()
    }

    unsafe fn get_value_unchecked(&self, position: usize) -> Self::Value {
        // SAFETY: position < len() guaranteed by caller
        unsafe { self.get_unchecked(position) }.cloned()
    }
}

/// Returns an option even when using `get_value_unchecked` because it should be safe to call
/// whenever `position < len()`.
impl<T: Clone, D: Backend<Word = usize> + AsRef<[usize]>, V: AsRef<[T]>> SliceByValue
    for PartialArray<T, SparseIndex<D>, V>
{
    type Value = Option<T>;

    fn len(&self) -> usize {
        self.len()
    }

    unsafe fn get_value_unchecked(&self, position: usize) -> Self::Value {
        // SAFETY: position < len() guaranteed by caller
        unsafe { self.get_unchecked(position) }.cloned()
    }
}

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

vigna / sux-rs / 23377228256

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