23694127622

Committed 28 Mar 2026 08:54PM UTC coverage: 73.413% (-3.3%) from 76.733%

Build # 23694127622

Build Type

push

github

Committed by

vigna

Commit Message

fmt

Coverage Stats

6362 of 8666 relevant lines covered (73.41%)

92599433.09 hits per line

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

68.97

/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::{BitFieldVec, BitFieldVecU, 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::TryIntoUnaligned;
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, L = BitFieldVec<Box<[u64]>>> {
    ef: EliasFano<u64, SelectZeroAdaptConst<BitVec<D>, Box<[usize]>, 12, 3>, L>,
    /// 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 = 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]>, L: SliceByValue<Value = u64>, V: AsRef<[T]>>
    PartialArray<T, SparseIndex<D, L>, V>
where
    for<'b> &'b L: crate::traits::IntoUncheckedIterator<Item = u64>,
{
    /// 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]>,
    L: SliceByValue<Value = u64>,
    V: AsRef<[T]>,
> SliceByValue for PartialArray<T, SparseIndex<D, L>, V>
where
    for<'b> &'b L: crate::traits::IntoUncheckedIterator<Item = u64>,
{
    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()
    }
}

// ── Aligned ↔ Unaligned conversion ──────────────────────────────────

impl<D> TryIntoUnaligned for SparseIndex<D> {
    type Unaligned = SparseIndex<D, BitFieldVecU<Box<[u64]>>>;
    fn try_into_unaligned(
        self,
    ) -> Result<Self::Unaligned, crate::traits::UnalignedConversionError> {
        Ok(SparseIndex {
            ef: self.ef.try_into_unaligned()?,
            first_invalid_pos: self.first_invalid_pos,
        })
    }
}

impl<T, P: TryIntoUnaligned, V> TryIntoUnaligned for PartialArray<T, P, V> {
    type Unaligned = PartialArray<T, P::Unaligned, V>;
    fn try_into_unaligned(
        self,
    ) -> Result<Self::Unaligned, crate::traits::UnalignedConversionError> {
        Ok(PartialArray {
            index: self.index.try_into_unaligned()?,
            values: self.values,
            _marker: PhantomData,
        })
    }
}

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

vigna / sux-rs / 23694127622

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