24281101826

Committed 11 Apr 2026 11:03AM UTC coverage: 71.146% (+0.1%) from 71.047%

Build # 24281101826

Build Type

push

github

Committed by

vigna

Commit Message

Completed inline link removal

Coverage Stats

7200 of 10120 relevant lines covered (71.15%)

17328249.11 hits per line

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

96.3

/src/dict/mapped_rear_coded_list.rs

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

//! A [`RearCodedList`] indexed through a mapping.
//!
//! The typical use case of this structure is to compress and access efficiently
//! list of strings that are not in sorted order. You build a sorted
//! [`RearCodedList`], and then you [wrap the instance together with a
//! mapping] that maps the original order
//! to the sorted order.
//!
//! There is no constraint, however, on the mapping: it can also collapse indices;
//! and the rear-coded list can also be unsorted.
//!
//! As in the case of [`RearCodedList`], the structure is parameterized by the
//! input/output type and by the storage backend, but two versions are presently
//! implemented, and associated with a type alias:
//!
//! - [`MappedRearCodedListStr`]: stores UTF-8 elements (`AsRef<str>`),
//!   returning [`String`] on access;
//!
//! - [`MappedRearCodedListSliceU8`]: stores byte sequences (`AsRef<[u8]>`),
//!   returning `Vec<u8>` on access.
//!
//! These standard types use a `Box<[usize]>` for storing the mapping.
//! However, it is possible to use any type implementing the
//! [`SliceByValue`] trait from the [`value_traits`] crate.
//!
//! Besides the standard access by means of the [`IndexedSeq`] trait, this
//! structure also implements the `get_in_place` method, which makes it possible
//! to write the element directly into a user-provided buffer (a string or a
//! vector of bytes), avoiding allocations. [`MappedRearCodedListStr`] has an
//! additional [`get_bytes_in_place`] method that writes the bytes of the
//! string into a user-provided `Vec<u8>`.
//!
//! Mapped rear-coded lists can be iterated upon using either an
//! [`Iterator`] or a [`Lender`]. In the first case there will be an
//! allocation at each iteration, whereas in the second case a single buffer
//! will be reused. You can also [iterate from a given position]. The
//! iteration will not be as fast as in the non-mapped case, however, as it
//! is not possible to build the returned strings incrementally.
//!
//! Note that, contrarily to [`RearCodedList`], this structure does not provide
//! implementations for the [`IndexedDict`] trait,
//! independently of whether the underlying [`RearCodedList`] is sorted or not.
//!
//! Finally, the `mrcl` command-line tool can be used to create
//! a serialized mapped rear-coded list starting from a
//! serialized rear-coded list and a mapping.
//!
//! # Examples
//!
//! Here we build a sorted rear-coded list, and then we wrap it in a
//! [`MappedRearCodedListStr`] together with a permutation:
//!
//! ```
//! # use sux::traits::IndexedSeq;
//! # use sux::dict::RearCodedListBuilder;
//! # use sux::dict::MappedRearCodedListStr;
//! # use sux::bits::BitFieldVec;
//!
//! let mut rclb = RearCodedListBuilder::<str, true>::new(4);
//!
//! rclb.push("aa");
//! rclb.push("aab");
//! rclb.push("abc");
//! rclb.push("abdd");
//! rclb.push("abde\0f");
//! rclb.push("abdf");
//!
//! let rcl = rclb.build();
//! let mut map = BitFieldVec::<Vec<usize>>::new(4, 0);
//! for &v in &[5, 4, 2, 0, 1, 3] { map.push(v); } // permutation
//! let mrcl = MappedRearCodedListStr::from_parts(rcl, map.into());
//! assert_eq!(mrcl.get(0), "abdf");
//! assert_eq!(mrcl.get(1), "abde\0f");
//! assert_eq!(mrcl.get(2), "abc");
//! assert_eq!(mrcl.get(3), "aa");
//! assert_eq!(mrcl.get(4), "aab");
//! assert_eq!(mrcl.get(5), "abdd");
//! ```
//!
//! [`IndexedDict`]: crate::traits::IndexedDict
//! [`get_bytes_in_place`]: MappedRearCodedListStr::get_bytes_in_place
//! [`Iterator`]: MappedRearCodedList::iter
//! [`Lender`]: MappedRearCodedList::lender
//! [iterate from a given position]: MappedRearCodedList::lender_from
//! [wrap the instance together with a mapping]: MappedRearCodedList::from_parts
use crate::bits::BitFieldVec;
use crate::dict::rear_coded_list::RearCodedList;
use crate::traits::{IndexedSeq, IntoIteratorFrom, Types};
use lender::FusedLender;
use lender::{ExactSizeLender, IntoLender, Lender, Lending, check_covariance};
use mem_dbg::*;
use value_traits::slices::SliceByValue;

/// Main structure; please use the type aliases [`MappedRearCodedListStr`] and
/// [`MappedRearCodedListSliceU8`].
#[derive(Debug, Clone, MemSize, MemDbg)]
#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct MappedRearCodedList<
    I: ?Sized,
    O,
    D = Box<[u8]>,
    P = Box<[usize]>,
    Q = BitFieldVec,
    const SORTED: bool = true,
> {
    rcl: RearCodedList<I, O, D, P, SORTED>,
    map: Q,
}

/// A mapped rear-coded list of byte sequences.
pub type MappedRearCodedListSliceU8<const SORTED: bool = true> =
    MappedRearCodedList<[u8], Vec<u8>, Box<[u8]>, Box<[usize]>, BitFieldVec<Box<[usize]>>, SORTED>;
/// A mapped rear-coded list of strings.
pub type MappedRearCodedListStr<const SORTED: bool = true> =
    MappedRearCodedList<str, String, Box<[u8]>, Box<[usize]>, BitFieldVec<Box<[usize]>>, SORTED>;

impl<
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> MappedRearCodedList<I, O, D, P, Q, SORTED>
{
    /// Creates a new instance from its parts.
    ///
    /// It is your responsibility to ensure that the mapping is valid,
    /// that is, that its length matches the length of the rear-coded list,
    /// and that all indices are in range.
    ///
    /// # Panics
    ///
    /// This method will panic if the length of the mapping does not match
    /// the length of the rear-coded list.
    pub fn from_parts(rcl: RearCodedList<I, O, D, P, SORTED>, map: Q) -> Self {
        assert_eq!(
            rcl.len(),
            map.len(),
            "Length mismatch between rear-coded list ({}) and mapping ({})",
            rcl.len(),
            map.len()
        );
        Self { rcl, map }
    }

    /// Returns the rear-coded list and the mapping, consuming this structure.
    pub fn into_parts(self) -> (RearCodedList<I, O, D, P, SORTED>, Q) {
        (self.rcl, self.map)
    }

    /// Returns the number of elements.
    ///
    /// This method is equivalent to [`IndexedSeq::len`], but it is provided to
    /// reduce ambiguity in method resolution.
    #[inline]
    pub const fn len(&self) -> usize {
        self.rcl.len()
    }

    /// Writes the index-th element to `result` as bytes. This is useful to avoid
    /// allocating a new vector for every query.
    #[inline]
    fn get_in_place_impl(&self, index: usize, result: &mut Vec<u8>) {
        let index = self.map.index_value(index);
        self.rcl.get_in_place_impl(index, result)
    }
}

impl<
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> MappedRearCodedList<I, O, D, P, Q, SORTED>
where
    for<'a> Lend<'a, I, O, D, P, Q, SORTED>: Lender,
{
    /// Returns a [`Lender`] over the elements of the list.
    ///
    /// Note that [`iter`] is more convenient if you need owned elements.
    ///
    /// [`iter`]: MappedRearCodedList::iter
    #[inline(always)]
    pub fn lender(&self) -> Lend<'_, I, O, D, P, Q, SORTED> {
        Lend::new(self)
    }

    /// Returns a [`Lender`] over the elements of the list
    /// starting from the given index.
    ///
    /// Note that [`iter_from`] is more convenient if you need owned
    /// elements.
    ///
    /// [`iter_from`]: MappedRearCodedList::iter_from
    #[inline(always)]
    pub fn lender_from(&self, from: usize) -> Lend<'_, I, O, D, P, Q, SORTED> {
        Lend::new_from(self, from)
    }

    /// Returns an [`Iterator`] over the elements of the list.
    ///
    /// Note that [`lender`] is more efficient if you need to iterate
    /// over many elements.
    ///
    /// [`lender`]: MappedRearCodedList::lender
    #[inline(always)]
    pub fn iter(&self) -> Iter<'_, I, O, D, P, Q, SORTED> {
        Iter(self.lender())
    }

    /// Returns an [`Iterator`] over the elements of the list
    /// starting from the given index.
    ///
    /// Note that [`lender_from`] is more efficient if you need to
    /// iterate over many elements.
    ///
    /// [`lender_from`]: MappedRearCodedList::lender_from
    #[inline(always)]
    pub fn iter_from(&self, from: usize) -> Iter<'_, I, O, D, P, Q, SORTED> {
        Iter(self.lender_from(from))
    }
}

// Dictionary traits

impl<
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> Types for MappedRearCodedList<I, O, D, P, Q, SORTED>
{
    type Output<'a> = O;
    type Input = I;
}

impl<D: AsRef<[u8]>, P: AsRef<[usize]>, Q: SliceByValue<Value = usize>, const SORTED: bool>
    IndexedSeq for MappedRearCodedList<[u8], Vec<u8>, D, P, Q, SORTED>
{
    #[inline(always)]
    unsafe fn get_unchecked(&self, index: usize) -> Self::Output<'_> {
        let index = self.map.index_value(index);
        unsafe { self.rcl.get_unchecked(index) }
    }

    #[inline(always)]
    fn len(&self) -> usize {
        self.rcl.len()
    }
}

impl<D: AsRef<[u8]>, P: AsRef<[usize]>, Q: SliceByValue<Value = usize>, const SORTED: bool>
    MappedRearCodedList<[u8], Vec<u8>, D, P, Q, SORTED>
{
    /// Returns in place the byte sequence of given index by writing
    /// its bytes into the provided vector.
    pub fn get_in_place(&self, index: usize, result: &mut Vec<u8>) {
        let index = self.map.index_value(index);
        self.rcl.get_in_place_impl(index, result);
    }
}

impl<D: AsRef<[u8]>, P: AsRef<[usize]>, Q: SliceByValue<Value = usize>, const SORTED: bool>
    IndexedSeq for MappedRearCodedList<str, String, D, P, Q, SORTED>
{
    #[inline(always)]
    unsafe fn get_unchecked(&self, index: usize) -> Self::Output<'_> {
        let index = self.map.index_value(index);
        unsafe { self.rcl.get_unchecked(index) }
    }

    #[inline(always)]
    fn len(&self) -> usize {
        self.rcl.len()
    }
}

impl<D: AsRef<[u8]>, P: AsRef<[usize]>, Q: SliceByValue<Value = usize>, const SORTED: bool>
    MappedRearCodedList<str, String, D, P, Q, SORTED>
{
    /// Returns in place the string of given index by writing
    /// its bytes into the provided string.
    pub fn get_in_place(&self, index: usize, result: &mut String) {
        let index = self.map.index_value(index);
        self.rcl.get_in_place(index, result)
    }

    /// Returns the bytes of the string of given index.
    ///
    /// This method can be used to avoid UTF-8 checks when you just need the raw
    /// bytes, or to use methods such as [`String::from_utf8_unchecked`] and
    /// [`str::from_utf8_unchecked`] to avoid the cost of UTF-8 checks. Be aware,
    /// however, that using invalid UTF-8 data may lead to undefined behavior.
    #[inline]
    pub fn get_bytes(&self, index: usize) -> Vec<u8> {
        let index = self.map.index_value(index);
        self.rcl.get_bytes(index)
    }

    /// Returns in place the string of given index by writing
    /// its bytes into the provided vector.
    ///
    /// This method can be used to avoid UTF-8 checks when you just need the raw
    /// bytes, or to use methods such as [`String::from_utf8_unchecked`] and
    /// [`str::from_utf8_unchecked`] to avoid the cost of UTF-8 checks. Be aware,
    /// however, that using invalid UTF-8 data may lead to undefined behavior.
    #[inline(always)]
    pub fn get_bytes_in_place(&self, index: usize, result: &mut Vec<u8>) {
        let index = self.map.index_value(index);
        self.rcl.get_in_place_impl(index, result);
    }
}

// Lenders

/// Sequential [`Lender`] over the contents of the list.
#[derive(Debug, Clone, MemSize, MemDbg)]
pub struct Lend<
    'a,
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> {
    prcl: &'a MappedRearCodedList<I, O, D, P, Q, SORTED>,
    buffer: Vec<u8>,
    index: usize,
}

impl<
    'a,
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> Lend<'a, I, O, D, P, Q, SORTED>
where
    Self: Lender,
{
    /// Creates a new lender over the rear-coded list.
    pub fn new(prcl: &'a MappedRearCodedList<I, O, D, P, Q, SORTED>) -> Self {
        Self {
            prcl,
            buffer: Vec::with_capacity(128),
            index: 0,
        }
    }

    /// Creates a new lender over the rear-coded list starting from the given
    /// position.
    pub fn new_from(prcl: &'a MappedRearCodedList<I, O, D, P, Q, SORTED>, from: usize) -> Self {
        Self {
            prcl,
            buffer: Vec::with_capacity(128),
            index: from,
        }
    }

    /// Internal next method that returns a reference to the inner buffer.
    fn next_impl(&mut self) -> Option<&[u8]> {
        if self.index >= self.prcl.len() {
            return None;
        }
        self.prcl.get_in_place_impl(self.index, &mut self.buffer);
        self.index += 1;
        Some(&self.buffer)
    }
}

impl<
    'a,
    'b,
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> Lending<'b> for Lend<'a, I, O, D, P, Q, SORTED>
{
    type Lend = &'b I;
}

impl<
    O: PartialEq<str> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> Lender for Lend<'_, str, O, D, P, Q, SORTED>
where
    str: PartialEq<O> + PartialEq,
{
    check_covariance!();
    fn next(&mut self) -> Option<&'_ str> {
        self.next_impl().map(|s| std::str::from_utf8(s).unwrap())
    }

    #[inline(always)]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len(), Some(self.len()))
    }
}

impl<
    O: PartialEq<[u8]> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> Lender for Lend<'_, [u8], O, D, P, Q, SORTED>
where
    [u8]: PartialEq<O> + PartialEq,
{
    check_covariance!();
    fn next(&mut self) -> Option<&[u8]> {
        self.next_impl()
    }

    #[inline(always)]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len(), Some(self.len()))
    }
}

impl<
    'a,
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> ExactSizeLender for Lend<'a, I, O, D, P, Q, SORTED>
where
    Lend<'a, I, O, D, P, Q, SORTED>: Lender,
{
    #[inline(always)]
    fn len(&self) -> usize {
        self.prcl.len() - self.index
    }
}

impl<
    'a,
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> FusedLender for Lend<'a, I, O, D, P, Q, SORTED>
where
    Lend<'a, I, O, D, P, Q, SORTED>: Lender,
{
}

// Iterators

/// Sequential [`Iterator`] over the contents of the list.
#[derive(Debug, Clone, MemSize, MemDbg)]
pub struct Iter<
    'a,
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
>(Lend<'a, I, O, D, P, Q, SORTED>);

impl<
    'a,
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> std::iter::ExactSizeIterator for Iter<'a, I, O, D, P, Q, SORTED>
where
    Iter<'a, I, O, D, P, Q, SORTED>: std::iter::Iterator,
    Lend<'a, I, O, D, P, Q, SORTED>: ExactSizeLender,
{
    #[inline(always)]
    fn len(&self) -> usize {
        self.0.len()
    }
}

impl<
    'a,
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> std::iter::FusedIterator for Iter<'a, I, O, D, P, Q, SORTED>
where
    Iter<'a, I, O, D, P, Q, SORTED>: std::iter::Iterator,
    Lend<'a, I, O, D, P, Q, SORTED>: FusedLender,
{
}

impl<'a, D: AsRef<[u8]>, P: AsRef<[usize]>, Q: SliceByValue<Value = usize>, const SORTED: bool>
    std::iter::Iterator for Iter<'a, str, String, D, P, Q, SORTED>
where
    Lend<'a, str, String, D, P, Q, SORTED>: Lender,
{
    type Item = String;

    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        // SAFETY: We encoded valid UTF-8 strings
        self.0
            .next_impl()
            .map(|v| String::from_utf8(Vec::from(v)).unwrap())
    }

    #[inline(always)]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len(), Some(self.len()))
    }
}

impl<'a, D: AsRef<[u8]>, P: AsRef<[usize]>, Q: SliceByValue<Value = usize>, const SORTED: bool>
    std::iter::Iterator for Iter<'a, [u8], Vec<u8>, D, P, Q, SORTED>
where
    Lend<'a, [u8], Vec<u8>, D, P, Q, SORTED>: ExactSizeLender,
{
    type Item = Vec<u8>;

    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next_impl().map(|v| v.into())
    }

    #[inline(always)]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len(), Some(self.len()))
    }
}

// Into... impls

impl<
    'a,
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> IntoLender for &'a MappedRearCodedList<I, O, D, P, Q, SORTED>
where
    Lend<'a, I, O, D, P, Q, SORTED>: Lender,
{
    type Lender = Lend<'a, I, O, D, P, Q, SORTED>;
    #[inline(always)]
    fn into_lender(self) -> Lend<'a, I, O, D, P, Q, SORTED> {
        Lend::new(self)
    }
}

impl<
    'a,
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> IntoIterator for &'a MappedRearCodedList<I, O, D, P, Q, SORTED>
where
    for<'b> Lend<'b, I, O, D, P, Q, SORTED>: Lender,
    Iter<'a, I, O, D, P, Q, SORTED>: std::iter::Iterator,
{
    type Item = <Iter<'a, I, O, D, P, Q, SORTED> as Iterator>::Item;
    type IntoIter = Iter<'a, I, O, D, P, Q, SORTED>;
    #[inline(always)]
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<
    'a,
    I: PartialEq<O> + PartialEq + ?Sized,
    O: PartialEq<I> + PartialEq,
    D: AsRef<[u8]>,
    P: AsRef<[usize]>,
    Q: SliceByValue<Value = usize>,
    const SORTED: bool,
> IntoIteratorFrom for &'a MappedRearCodedList<I, O, D, P, Q, SORTED>
where
    for<'b> Lend<'b, I, O, D, P, Q, SORTED>: Lender,
    Iter<'a, I, O, D, P, Q, SORTED>: std::iter::Iterator,
{
    type IntoIterFrom = Iter<'a, I, O, D, P, Q, SORTED>;
    #[inline(always)]
    fn into_iter_from(self, from: usize) -> Self::IntoIter {
        self.iter_from(from)
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Inria
3	* SPDX-FileCopyrightText: 2023 Tommaso Fontana
4	* SPDX-FileCopyrightText: 2025 Sebastiano Vigna
5	*
6	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
7	*/
8
9	//! A [`RearCodedList`] indexed through a mapping.
10	//!
11	//! The typical use case of this structure is to compress and access efficiently
12	//! list of strings that are not in sorted order. You build a sorted
13	//! [`RearCodedList`], and then you [wrap the instance together with a
14	//! mapping] that maps the original order
15	//! to the sorted order.
16	//!
17	//! There is no constraint, however, on the mapping: it can also collapse indices;
18	//! and the rear-coded list can also be unsorted.
19	//!
20	//! As in the case of [`RearCodedList`], the structure is parameterized by the
21	//! input/output type and by the storage backend, but two versions are presently
22	//! implemented, and associated with a type alias:
23	//!
24	//! - [`MappedRearCodedListStr`]: stores UTF-8 elements (`AsRef<str>`),
25	//! returning [`String`] on access;
26	//!
27	//! - [`MappedRearCodedListSliceU8`]: stores byte sequences (`AsRef<[u8]>`),
28	//! returning `Vec<u8>` on access.
29	//!
30	//! These standard types use a `Box<[usize]>` for storing the mapping.
31	//! However, it is possible to use any type implementing the
32	//! [`SliceByValue`] trait from the [`value_traits`] crate.
33	//!
34	//! Besides the standard access by means of the [`IndexedSeq`] trait, this
35	//! structure also implements the `get_in_place` method, which makes it possible
36	//! to write the element directly into a user-provided buffer (a string or a
37	//! vector of bytes), avoiding allocations. [`MappedRearCodedListStr`] has an
38	//! additional [`get_bytes_in_place`] method that writes the bytes of the
39	//! string into a user-provided `Vec<u8>`.
40	//!
41	//! Mapped rear-coded lists can be iterated upon using either an
42	//! [`Iterator`] or a [`Lender`]. In the first case there will be an
43	//! allocation at each iteration, whereas in the second case a single buffer
44	//! will be reused. You can also [iterate from a given position]. The
45	//! iteration will not be as fast as in the non-mapped case, however, as it
46	//! is not possible to build the returned strings incrementally.
47	//!
48	//! Note that, contrarily to [`RearCodedList`], this structure does not provide
49	//! implementations for the [`IndexedDict`] trait,
50	//! independently of whether the underlying [`RearCodedList`] is sorted or not.
51	//!
52	//! Finally, the `mrcl` command-line tool can be used to create
53	//! a serialized mapped rear-coded list starting from a
54	//! serialized rear-coded list and a mapping.
55	//!
56	//! # Examples
57	//!
58	//! Here we build a sorted rear-coded list, and then we wrap it in a
59	//! [`MappedRearCodedListStr`] together with a permutation:
60	//!
61	//! ```
62	//! # use sux::traits::IndexedSeq;
63	//! # use sux::dict::RearCodedListBuilder;
64	//! # use sux::dict::MappedRearCodedListStr;
65	//! # use sux::bits::BitFieldVec;
66	//!
67	//! let mut rclb = RearCodedListBuilder::<str, true>::new(4);
68	//!
69	//! rclb.push("aa");
70	//! rclb.push("aab");
71	//! rclb.push("abc");
72	//! rclb.push("abdd");
73	//! rclb.push("abde\0f");
74	//! rclb.push("abdf");
75	//!
76	//! let rcl = rclb.build();
77	//! let mut map = BitFieldVec::<Vec<usize>>::new(4, 0);
78	//! for &v in &[5, 4, 2, 0, 1, 3] { map.push(v); } // permutation
79	//! let mrcl = MappedRearCodedListStr::from_parts(rcl, map.into());
80	//! assert_eq!(mrcl.get(0), "abdf");
81	//! assert_eq!(mrcl.get(1), "abde\0f");
82	//! assert_eq!(mrcl.get(2), "abc");
83	//! assert_eq!(mrcl.get(3), "aa");
84	//! assert_eq!(mrcl.get(4), "aab");
85	//! assert_eq!(mrcl.get(5), "abdd");
86	//! ```
87	//!
88	//! [`IndexedDict`]: crate::traits::IndexedDict
89	//! [`get_bytes_in_place`]: MappedRearCodedListStr::get_bytes_in_place
90	//! [`Iterator`]: MappedRearCodedList::iter
91	//! [`Lender`]: MappedRearCodedList::lender
92	//! [iterate from a given position]: MappedRearCodedList::lender_from
93	//! [wrap the instance together with a mapping]: MappedRearCodedList::from_parts
94	use crate::bits::BitFieldVec;
95	use crate::dict::rear_coded_list::RearCodedList;
96	use crate::traits::{IndexedSeq, IntoIteratorFrom, Types};
97	use lender::FusedLender;
98	use lender::{ExactSizeLender, IntoLender, Lender, Lending, check_covariance};
99	use mem_dbg::*;
100	use value_traits::slices::SliceByValue;
101
102	/// Main structure; please use the type aliases [`MappedRearCodedListStr`] and
103	/// [`MappedRearCodedListSliceU8`].
104	#[derive(Debug, Clone, MemSize, MemDbg)]
105	#[cfg_attr(feature = "epserde", derive(epserde::Epserde))]
106	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
107	pub struct MappedRearCodedList<
108	I: ?Sized,
109	O,
110	D = Box<[u8]>,
111	P = Box<[usize]>,
112	Q = BitFieldVec,
113	const SORTED: bool = true,
114	> {
115	rcl: RearCodedList<I, O, D, P, SORTED>,
116	map: Q,
117	}
118
119	/// A mapped rear-coded list of byte sequences.
120	pub type MappedRearCodedListSliceU8<const SORTED: bool = true> =
121	MappedRearCodedList<[u8], Vec<u8>, Box<[u8]>, Box<[usize]>, BitFieldVec<Box<[usize]>>, SORTED>;
122	/// A mapped rear-coded list of strings.
123	pub type MappedRearCodedListStr<const SORTED: bool = true> =
124	MappedRearCodedList<str, String, Box<[u8]>, Box<[usize]>, BitFieldVec<Box<[usize]>>, SORTED>;
125
126	impl<
127	I: PartialEq<O> + PartialEq + ?Sized,
128	O: PartialEq<I> + PartialEq,
129	D: AsRef<[u8]>,
130	P: AsRef<[usize]>,
131	Q: SliceByValue<Value = usize>,
132	const SORTED: bool,
133	> MappedRearCodedList<I, O, D, P, Q, SORTED>
134	{
135	/// Creates a new instance from its parts.
136	///
137	/// It is your responsibility to ensure that the mapping is valid,
138	/// that is, that its length matches the length of the rear-coded list,
139	/// and that all indices are in range.
140	///
141	/// # Panics
142	///
143	/// This method will panic if the length of the mapping does not match
144	/// the length of the rear-coded list.
145	pub fn from_parts(rcl: RearCodedList<I, O, D, P, SORTED>, map: Q) -> Self {	34✔
146	assert_eq!(	34✔
147	rcl.len(),	68✔
148	map.len(),	68✔
149	"Length mismatch between rear-coded list ({}) and mapping ({})",	×
150	rcl.len(),	2✔
151	map.len()	2✔
152	);
153	Self { rcl, map }
154	}
155
156	/// Returns the rear-coded list and the mapping, consuming this structure.
157	pub fn into_parts(self) -> (RearCodedList<I, O, D, P, SORTED>, Q) {	1✔
158	(self.rcl, self.map)	1✔
159	}
160
161	/// Returns the number of elements.
162	///
163	/// This method is equivalent to [`IndexedSeq::len`], but it is provided to
164	/// reduce ambiguity in method resolution.
165	#[inline]
166	pub const fn len(&self) -> usize {	21,102✔
167	self.rcl.len()	42,204✔
168	}
169
170	/// Writes the index-th element to `result` as bytes. This is useful to avoid
171	/// allocating a new vector for every query.
172	#[inline]
173	fn get_in_place_impl(&self, index: usize, result: &mut Vec<u8>) {	20,646✔
174	let index = self.map.index_value(index);	82,584✔
175	self.rcl.get_in_place_impl(index, result)	82,584✔
176	}
177	}
178
179	impl<
180	I: PartialEq<O> + PartialEq + ?Sized,
181	O: PartialEq<I> + PartialEq,
182	D: AsRef<[u8]>,
183	P: AsRef<[usize]>,
184	Q: SliceByValue<Value = usize>,
185	const SORTED: bool,
186	> MappedRearCodedList<I, O, D, P, Q, SORTED>
187	where
188	for<'a> Lend<'a, I, O, D, P, Q, SORTED>: Lender,
189	{
190	/// Returns a [`Lender`] over the elements of the list.
191	///
192	/// Note that [`iter`] is more convenient if you need owned elements.
193	///
194	/// [`iter`]: MappedRearCodedList::iter
195	#[inline(always)]
196	pub fn lender(&self) -> Lend<'_, I, O, D, P, Q, SORTED> {	17✔
197	Lend::new(self)	34✔
198	}
199
200	/// Returns a [`Lender`] over the elements of the list
201	/// starting from the given index.
202	///
203	/// Note that [`iter_from`] is more convenient if you need owned
204	/// elements.
205	///
206	/// [`iter_from`]: MappedRearCodedList::iter_from
207	#[inline(always)]
208	pub fn lender_from(&self, from: usize) -> Lend<'_, I, O, D, P, Q, SORTED> {	407✔
209	Lend::new_from(self, from)	1,221✔
210	}
211
212	/// Returns an [`Iterator`] over the elements of the list.
213	///
214	/// Note that [`lender`] is more efficient if you need to iterate
215	/// over many elements.
216	///
217	/// [`lender`]: MappedRearCodedList::lender
218	#[inline(always)]
219	pub fn iter(&self) -> Iter<'_, I, O, D, P, Q, SORTED> {	9✔
220	Iter(self.lender())	9✔
221	}
222
223	/// Returns an [`Iterator`] over the elements of the list
224	/// starting from the given index.
225	///
226	/// Note that [`lender_from`] is more efficient if you need to
227	/// iterate over many elements.
228	///
229	/// [`lender_from`]: MappedRearCodedList::lender_from
230	#[inline(always)]
231	pub fn iter_from(&self, from: usize) -> Iter<'_, I, O, D, P, Q, SORTED> {	204✔
232	Iter(self.lender_from(from))	408✔
233	}
234	}
235
236	// Dictionary traits
237
238	impl<
239	I: PartialEq<O> + PartialEq + ?Sized,
240	O: PartialEq<I> + PartialEq,
241	D: AsRef<[u8]>,
242	P: AsRef<[usize]>,
243	Q: SliceByValue<Value = usize>,
244	const SORTED: bool,
245	> Types for MappedRearCodedList<I, O, D, P, Q, SORTED>
246	{
247	type Output<'a> = O;
248	type Input = I;
249	}
250
251	impl<D: AsRef<[u8]>, P: AsRef<[usize]>, Q: SliceByValue<Value = usize>, const SORTED: bool>
252	IndexedSeq for MappedRearCodedList<[u8], Vec<u8>, D, P, Q, SORTED>
253	{
254	#[inline(always)]
255	unsafe fn get_unchecked(&self, index: usize) -> Self::Output<'_> {	2✔
256	let index = self.map.index_value(index);	8✔
257	unsafe { self.rcl.get_unchecked(index) }	6✔
258	}
259
260	#[inline(always)]
261	fn len(&self) -> usize {	4✔
262	self.rcl.len()	8✔
263	}
264	}
265
266	impl<D: AsRef<[u8]>, P: AsRef<[usize]>, Q: SliceByValue<Value = usize>, const SORTED: bool>
267	MappedRearCodedList<[u8], Vec<u8>, D, P, Q, SORTED>
268	{
269	/// Returns in place the byte sequence of given index by writing
270	/// its bytes into the provided vector.
271	pub fn get_in_place(&self, index: usize, result: &mut Vec<u8>) {	2✔
272	let index = self.map.index_value(index);	8✔
273	self.rcl.get_in_place_impl(index, result);	8✔
274	}
275	}
276
277	impl<D: AsRef<[u8]>, P: AsRef<[usize]>, Q: SliceByValue<Value = usize>, const SORTED: bool>
278	IndexedSeq for MappedRearCodedList<str, String, D, P, Q, SORTED>
279	{
280	#[inline(always)]
281	unsafe fn get_unchecked(&self, index: usize) -> Self::Output<'_> {	402✔
282	let index = self.map.index_value(index);	1,608✔
283	unsafe { self.rcl.get_unchecked(index) }	1,206✔
284	}
285
286	#[inline(always)]
287	fn len(&self) -> usize {	414✔
288	self.rcl.len()	828✔
289	}
290	}
291
292	impl<D: AsRef<[u8]>, P: AsRef<[usize]>, Q: SliceByValue<Value = usize>, const SORTED: bool>
293	MappedRearCodedList<str, String, D, P, Q, SORTED>
294	{
295	/// Returns in place the string of given index by writing
296	/// its bytes into the provided string.
297	pub fn get_in_place(&self, index: usize, result: &mut String) {	2✔
298	let index = self.map.index_value(index);	8✔
299	self.rcl.get_in_place(index, result)	8✔
300	}
301
302	/// Returns the bytes of the string of given index.
303	///
304	/// This method can be used to avoid UTF-8 checks when you just need the raw
305	/// bytes, or to use methods such as [`String::from_utf8_unchecked`] and
306	/// [`str::from_utf8_unchecked`] to avoid the cost of UTF-8 checks. Be aware,
307	/// however, that using invalid UTF-8 data may lead to undefined behavior.
308	#[inline]
309	pub fn get_bytes(&self, index: usize) -> Vec<u8> {	2✔
310	let index = self.map.index_value(index);	8✔
311	self.rcl.get_bytes(index)	6✔
312	}
313
314	/// Returns in place the string of given index by writing
315	/// its bytes into the provided vector.
316	///
317	/// This method can be used to avoid UTF-8 checks when you just need the raw
318	/// bytes, or to use methods such as [`String::from_utf8_unchecked`] and
319	/// [`str::from_utf8_unchecked`] to avoid the cost of UTF-8 checks. Be aware,
320	/// however, that using invalid UTF-8 data may lead to undefined behavior.
321	#[inline(always)]
322	pub fn get_bytes_in_place(&self, index: usize, result: &mut Vec<u8>) {	2✔
323	let index = self.map.index_value(index);	8✔
324	self.rcl.get_in_place_impl(index, result);	8✔
325	}
326	}
327
328	// Lenders
329
330	/// Sequential [`Lender`] over the contents of the list.
331	#[derive(Debug, Clone, MemSize, MemDbg)]
332	pub struct Lend<
333	'a,
334	I: PartialEq<O> + PartialEq + ?Sized,
335	O: PartialEq<I> + PartialEq,
336	D: AsRef<[u8]>,
337	P: AsRef<[usize]>,
338	Q: SliceByValue<Value = usize>,
339	const SORTED: bool,
340	> {
341	prcl: &'a MappedRearCodedList<I, O, D, P, Q, SORTED>,
342	buffer: Vec<u8>,
343	index: usize,
344	}
345
346	impl<
347	'a,
348	I: PartialEq<O> + PartialEq + ?Sized,
349	O: PartialEq<I> + PartialEq,
350	D: AsRef<[u8]>,
351	P: AsRef<[usize]>,
352	Q: SliceByValue<Value = usize>,
353	const SORTED: bool,
354	> Lend<'a, I, O, D, P, Q, SORTED>
355	where
356	Self: Lender,
357	{
358	/// Creates a new lender over the rear-coded list.
359	pub fn new(prcl: &'a MappedRearCodedList<I, O, D, P, Q, SORTED>) -> Self {	18✔
360	Self {
361	prcl,
362	buffer: Vec::with_capacity(128),	18✔
363	index: 0,
364	}
365	}
366
367	/// Creates a new lender over the rear-coded list starting from the given
368	/// position.
369	pub fn new_from(prcl: &'a MappedRearCodedList<I, O, D, P, Q, SORTED>, from: usize) -> Self {	407✔
370	Self {
371	prcl,
372	buffer: Vec::with_capacity(128),	407✔
373	index: from,
374	}
375	}
376
377	/// Internal next method that returns a reference to the inner buffer.
378	fn next_impl(&mut self) -> Option<&[u8]> {	21,067✔
379	if self.index >= self.prcl.len() {	42,134✔
380	return None;	421✔
381	}
382	self.prcl.get_in_place_impl(self.index, &mut self.buffer);	82,584✔
383	self.index += 1;	20,646✔
384	Some(&self.buffer)	20,646✔
385	}
386	}
387
388	impl<
389	'a,
390	'b,
391	I: PartialEq<O> + PartialEq + ?Sized,
392	O: PartialEq<I> + PartialEq,
393	D: AsRef<[u8]>,
394	P: AsRef<[usize]>,
395	Q: SliceByValue<Value = usize>,
396	const SORTED: bool,
397	> Lending<'b> for Lend<'a, I, O, D, P, Q, SORTED>
398	{
399	type Lend = &'b I;
400	}
401
402	impl<
403	O: PartialEq<str> + PartialEq,
404	D: AsRef<[u8]>,
405	P: AsRef<[usize]>,
406	Q: SliceByValue<Value = usize>,
407	const SORTED: bool,
408	> Lender for Lend<'_, str, O, D, P, Q, SORTED>
409	where
410	str: PartialEq<O> + PartialEq,
411	{
412	check_covariance!();
413	fn next(&mut self) -> Option<&'_ str> {	10,525✔
414	self.next_impl().map(\|s\| std::str::from_utf8(s).unwrap())	62,523✔
415	}
416
417	#[inline(always)]
418	fn size_hint(&self) -> (usize, Option<usize>) {	1✔
419	(self.len(), Some(self.len()))	3✔
420	}
421	}
422
423	impl<
424	O: PartialEq<[u8]> + PartialEq,
425	D: AsRef<[u8]>,
426	P: AsRef<[usize]>,
427	Q: SliceByValue<Value = usize>,
428	const SORTED: bool,
429	> Lender for Lend<'_, [u8], O, D, P, Q, SORTED>
430	where
431	[u8]: PartialEq<O> + PartialEq,
432	{
433	check_covariance!();
434	fn next(&mut self) -> Option<&[u8]> {	8✔
435	self.next_impl()	16✔
436	}
437
438	#[inline(always)]
439	fn size_hint(&self) -> (usize, Option<usize>) {	×
440	(self.len(), Some(self.len()))	×
441	}
442	}
443
444	impl<
445	'a,
446	I: PartialEq<O> + PartialEq + ?Sized,
447	O: PartialEq<I> + PartialEq,
448	D: AsRef<[u8]>,
449	P: AsRef<[usize]>,
450	Q: SliceByValue<Value = usize>,
451	const SORTED: bool,
452	> ExactSizeLender for Lend<'a, I, O, D, P, Q, SORTED>
453	where
454	Lend<'a, I, O, D, P, Q, SORTED>: Lender,
455	{
456	#[inline(always)]
457	fn len(&self) -> usize {	12✔
458	self.prcl.len() - self.index	24✔
459	}
460	}
461
462	impl<
463	'a,
464	I: PartialEq<O> + PartialEq + ?Sized,
465	O: PartialEq<I> + PartialEq,
466	D: AsRef<[u8]>,
467	P: AsRef<[usize]>,
468	Q: SliceByValue<Value = usize>,
469	const SORTED: bool,
470	> FusedLender for Lend<'a, I, O, D, P, Q, SORTED>
471	where
472	Lend<'a, I, O, D, P, Q, SORTED>: Lender,
473	{
474	}
475
476	// Iterators
477
478	/// Sequential [`Iterator`] over the contents of the list.
479	#[derive(Debug, Clone, MemSize, MemDbg)]
480	pub struct Iter<
481	'a,
482	I: PartialEq<O> + PartialEq + ?Sized,
483	O: PartialEq<I> + PartialEq,
484	D: AsRef<[u8]>,
485	P: AsRef<[usize]>,
486	Q: SliceByValue<Value = usize>,
487	const SORTED: bool,
488	>(Lend<'a, I, O, D, P, Q, SORTED>);
489
490	impl<
491	'a,
492	I: PartialEq<O> + PartialEq + ?Sized,
493	O: PartialEq<I> + PartialEq,
494	D: AsRef<[u8]>,
495	P: AsRef<[usize]>,
496	Q: SliceByValue<Value = usize>,
497	const SORTED: bool,
498	> std::iter::ExactSizeIterator for Iter<'a, I, O, D, P, Q, SORTED>
499	where
500	Iter<'a, I, O, D, P, Q, SORTED>: std::iter::Iterator,
501	Lend<'a, I, O, D, P, Q, SORTED>: ExactSizeLender,
502	{
503	#[inline(always)]
504	fn len(&self) -> usize {	8✔
505	self.0.len()	16✔
506	}
507	}
508
509	impl<
510	'a,
511	I: PartialEq<O> + PartialEq + ?Sized,
512	O: PartialEq<I> + PartialEq,
513	D: AsRef<[u8]>,
514	P: AsRef<[usize]>,
515	Q: SliceByValue<Value = usize>,
516	const SORTED: bool,
517	> std::iter::FusedIterator for Iter<'a, I, O, D, P, Q, SORTED>
518	where
519	Iter<'a, I, O, D, P, Q, SORTED>: std::iter::Iterator,
520	Lend<'a, I, O, D, P, Q, SORTED>: FusedLender,
521	{
522	}
523
524	impl<'a, D: AsRef<[u8]>, P: AsRef<[usize]>, Q: SliceByValue<Value = usize>, const SORTED: bool>
525	std::iter::Iterator for Iter<'a, str, String, D, P, Q, SORTED>
526	where
527	Lend<'a, str, String, D, P, Q, SORTED>: Lender,
528	{
529	type Item = String;
530
531	#[inline(always)]
532	fn next(&mut self) -> Option<Self::Item> {	10,503✔
533	// SAFETY: We encoded valid UTF-8 strings
534	self.0	10,503✔
535	.next_impl()
536	.map(\|v\| String::from_utf8(Vec::from(v)).unwrap())	51,775✔
537	}
538
539	#[inline(always)]
540	fn size_hint(&self) -> (usize, Option<usize>) {	1✔
541	(self.len(), Some(self.len()))	3✔
542	}
543	}
544
545	impl<'a, D: AsRef<[u8]>, P: AsRef<[usize]>, Q: SliceByValue<Value = usize>, const SORTED: bool>
546	std::iter::Iterator for Iter<'a, [u8], Vec<u8>, D, P, Q, SORTED>
547	where
548	Lend<'a, [u8], Vec<u8>, D, P, Q, SORTED>: ExactSizeLender,
549	{
550	type Item = Vec<u8>;
551
552	#[inline(always)]
553	fn next(&mut self) -> Option<Self::Item> {	8✔
554	self.0.next_impl().map(\|v\| v.into())	36✔
555	}
556
557	#[inline(always)]
558	fn size_hint(&self) -> (usize, Option<usize>) {	2✔
559	(self.len(), Some(self.len()))	6✔
560	}
561	}
562
563	// Into... impls
564
565	impl<
566	'a,
567	I: PartialEq<O> + PartialEq + ?Sized,
568	O: PartialEq<I> + PartialEq,
569	D: AsRef<[u8]>,
570	P: AsRef<[usize]>,
571	Q: SliceByValue<Value = usize>,
572	const SORTED: bool,
573	> IntoLender for &'a MappedRearCodedList<I, O, D, P, Q, SORTED>
574	where
575	Lend<'a, I, O, D, P, Q, SORTED>: Lender,
576	{
577	type Lender = Lend<'a, I, O, D, P, Q, SORTED>;
578	#[inline(always)]
579	fn into_lender(self) -> Lend<'a, I, O, D, P, Q, SORTED> {	1✔
580	Lend::new(self)	2✔
581	}
582	}
583
584	impl<
585	'a,
586	I: PartialEq<O> + PartialEq + ?Sized,
587	O: PartialEq<I> + PartialEq,
588	D: AsRef<[u8]>,
589	P: AsRef<[usize]>,
590	Q: SliceByValue<Value = usize>,
591	const SORTED: bool,
592	> IntoIterator for &'a MappedRearCodedList<I, O, D, P, Q, SORTED>
593	where
594	for<'b> Lend<'b, I, O, D, P, Q, SORTED>: Lender,
595	Iter<'a, I, O, D, P, Q, SORTED>: std::iter::Iterator,
596	{
597	type Item = <Iter<'a, I, O, D, P, Q, SORTED> as Iterator>::Item;
598	type IntoIter = Iter<'a, I, O, D, P, Q, SORTED>;
599	#[inline(always)]
600	fn into_iter(self) -> Self::IntoIter {	1✔
601	self.iter()	2✔
602	}
603	}
604
605	impl<
606	'a,
607	I: PartialEq<O> + PartialEq + ?Sized,
608	O: PartialEq<I> + PartialEq,
609	D: AsRef<[u8]>,
610	P: AsRef<[usize]>,
611	Q: SliceByValue<Value = usize>,
612	const SORTED: bool,
613	> IntoIteratorFrom for &'a MappedRearCodedList<I, O, D, P, Q, SORTED>
614	where
615	for<'b> Lend<'b, I, O, D, P, Q, SORTED>: Lender,
616	Iter<'a, I, O, D, P, Q, SORTED>: std::iter::Iterator,
617	{
618	type IntoIterFrom = Iter<'a, I, O, D, P, Q, SORTED>;
619	#[inline(always)]
620	fn into_iter_from(self, from: usize) -> Self::IntoIter {	1✔
621	self.iter_from(from)	3✔
622	}
623	}

vigna / sux-rs / 24281101826

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