29426297655

Committed 15 Jul 2026 03:02PM UTC coverage: 74.502%. First build

Build # 29426297655

Build Type

Pull #111

github

Committed by

web-flow

Commit Message

Merge 94de354d0 into 4d383f6b9

Pull Request Pull Request #111: Harden succinct structures and construction contracts

Coverage Stats

850 of 1056 new or added lines in 40 files covered. (80.49%)

9046 of 12142 relevant lines covered (74.5%)

18306116.8 hits per line

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

68.89

/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.
//!
//! [partial array]: PartialArray

use std::marker::PhantomData;

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

use crate::bits::{BitFieldVec, 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::Unaligned;
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] 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`] on the Elias–Fano structure, because it requires just
/// [`SelectZeroUnchecked`], whereas [`Succ`] would require
/// [`SelectUnchecked`] as well.
///
/// [Elias–Fano]: crate::dict::EliasFano
/// [`SuccUnchecked`]: crate::traits::SuccUnchecked
/// [`SelectZeroUnchecked`]: crate::traits::SelectZeroUnchecked
/// [`Succ`]: crate::traits::Succ
/// [`SelectUnchecked`]: crate::traits::SelectUnchecked
#[doc(hidden)]
#[derive(Debug, Clone, MemSize, MemDbg)]
#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
#[cfg_attr(feature = "serde", derive(serde::Serialize))]
pub struct SparseIndex<D, L = BitFieldVec<Box<[u64]>>, I = Box<[usize]>> {
    ef: EliasFano<u64, SelectZeroAdaptConst<BitVec<D>, I>, 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, MemSize, MemDbg)]
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].
///
/// # 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"));
/// ```
///
/// [sparse partial array]: new_sparse
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.
    ///
    /// # Panics
    ///
    /// Panics if `position` is not strictly greater than the previous position
    /// set, or if `position >= len`.
    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.
    #[must_use]
    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] structure.
///
/// If your set of values is really dense, consider using a [dense partial array].
///
/// # 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"));
/// ```
///
/// You must specify the number of values in advance.
///
/// # Panics
///
/// Panics if `num_values > len`, because strictly increasing in-bounds
/// positions cannot satisfy that capacity, or if the underlying Elias--Fano
/// structures would exceed `usize` in length (for example when `num_values` is
/// near `usize::MAX`).
///
/// [Elias-Fano]: crate::dict::EliasFano
/// [dense partial array]: new_dense
pub fn new_sparse<T>(
    len: usize,
    num_values: usize,
) -> PartialArrayBuilder<T, EliasFanoBuilder<u64>> {
    assert!(
        num_values <= len,
        "number of values ({num_values}) must not exceed array length ({len})"
    );
    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.
    ///
    /// # Panics
    ///
    /// Panics if `position` is not strictly greater than the previous position
    /// set, if `position >= len`, or if more than the declared number of values
    /// are 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);
        // usize fits u64 on all supported targets, so this cast is lossless. The
        // checked push panics "Too many values" past the declared capacity,
        // upholding EliasFano's unchecked "at most n pushes" precondition.
        self.builder.push(position as u64);
        self.values.push(value);
        self.min_next_pos = position + 1;
    }

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

vigna / sux-rs / 29426297655

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