compressed_intvec/variable/
slice.rs

1//! An immutable, zero-copy slice of an [`VarVec`].
2//!
3//! This module provides [`VarVecSlice`], a view into a contiguous portion of an
4//! [`VarVec`]. Slices are immutable and do not own their data; they borrow it
5//! from the parent [`VarVec`].
6//!
7//! [`VarVec`]: crate::variable::VarVec
8
9use super::{traits::Storable, VarVec, VarVecBitReader};
10use dsi_bitstream::prelude::{BitRead, BitSeek, CodesRead, Endianness};
11use std::cmp::Ordering;
12use std::fmt;
13use std::iter::FusedIterator;
14use std::ops::Range;
15
16/// An immutable, zero-copy slice of an [`VarVec`].
17///
18/// This struct provides a view into a contiguous portion of an [`VarVec`]
19/// without copying the underlying compressed data. It is created by the
20/// [`slice`](super::VarVec::slice) or [`split_at`](super::VarVec::split_at)
21/// methods on an [`VarVec`].
22///
23/// All operations on an [`VarVecSlice`] are relative to the start of the slice,
24/// not the parent vector.
25///
26/// # Examples
27///
28/// ```
29/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
30/// use compressed_intvec::variable::{VarVec, UVarVec};
31///
32/// let data: Vec<u32> = (0..100).collect();
33/// let vec: UVarVec<u32> = VarVec::from_slice(&data)?;
34///
35/// // Create a slice of the elements from index 20 to 49
36/// let slice = vec.slice(20, 30).expect("valid slice range");
37///
38/// assert_eq!(slice.len(), 30);
39///
40/// // Accessing an element of the slice
41/// // Index 5 of the slice corresponds to index 25 of the original vector
42/// assert_eq!(slice.get(5), Some(25));
43///
44/// // Iterating over the slice
45/// let mut slice_sum = 0;
46/// for value in slice.iter() {
47///     slice_sum += value;
48/// }
49/// assert_eq!(slice_sum, (20..50).sum());
50/// # Ok(())
51/// # }
52/// ```
53#[derive(Debug, Clone)]
54pub struct VarVecSlice<'a, T: Storable, E: Endianness, B: AsRef<[u64]>> {
55    /// A reference to the parent vector.
56    vec: &'a VarVec<T, E, B>,
57    /// The starting index of the slice within the parent vector.
58    start: usize,
59    /// The number of elements in the slice.
60    len: usize,
61}
62
63impl<'a, T: Storable, E: Endianness, B: AsRef<[u64]>> VarVecSlice<'a, T, E, B> {
64    /// Creates a new `VarVecSlice`.
65    pub(super) fn new(vec: &'a VarVec<T, E, B>, range: Range<usize>) -> Self {
66        Self {
67            vec,
68            start: range.start,
69            len: range.len(),
70        }
71    }
72
73    /// Returns the number of elements in the slice.
74    #[inline]
75    pub fn len(&self) -> usize {
76        self.len
77    }
78
79    /// Returns `true` if the slice contains no elements.
80    #[inline]
81    pub fn is_empty(&self) -> bool {
82        self.len == 0
83    }
84
85    /// Returns the element at the specified index within the slice, or `None` if
86    /// the index is out of bounds.
87    ///
88    /// The index is relative to the start of the slice.
89    #[inline]
90    pub fn get(&self, index: usize) -> Option<T>
91    where
92        for<'b> VarVecBitReader<'b, E>: BitRead<E, Error = core::convert::Infallible>
93            + CodesRead<E>
94            + BitSeek<Error = core::convert::Infallible>,
95    {
96        if index >= self.len {
97            return None;
98        }
99        // The actual index into the parent vector is `self.start + index`.
100        self.vec.get(self.start + index)
101    }
102
103    /// Returns the element at `index` within the slice without bounds checking.
104    ///
105    /// The index is relative to the start of the slice.
106    ///
107    /// # Safety
108    ///
109    /// Calling this method with an out-of-bounds index is undefined behavior.
110    /// The caller must ensure that `index < self.len()`.
111    #[inline(always)]
112    pub unsafe fn get_unchecked(&self, index: usize) -> T
113    where
114        for<'b> VarVecBitReader<'b, E>: BitRead<E, Error = core::convert::Infallible>
115            + CodesRead<E>
116            + BitSeek<Error = core::convert::Infallible>,
117    {
118        debug_assert!(index < self.len, "Index out of bounds");
119        unsafe { self.vec.get_unchecked(self.start + index) }
120    }
121
122    /// Returns an iterator over the values in the slice.
123    pub fn iter(&self) -> VarVecSliceIter<'_, T, E, B>
124    where
125        for<'b> VarVecBitReader<'b, E>: BitRead<E, Error = core::convert::Infallible>
126            + CodesRead<E>
127            + BitSeek<Error = core::convert::Infallible>,
128    {
129        VarVecSliceIter::new(self)
130    }
131}
132
133impl<T, E, B> VarVecSlice<'_, T, E, B>
134where
135    T: Storable + Ord,
136    E: Endianness,
137    B: AsRef<[u64]>,
138    for<'b> VarVecBitReader<'b, E>: BitRead<E, Error = core::convert::Infallible>
139        + CodesRead<E>
140        + BitSeek<Error = core::convert::Infallible>,
141{
142    /// Binary searches this slice for a given element.
143    ///
144    /// If the value is found, returns `Ok(usize)` with the index of the
145    /// matching element within the slice. If not found, returns `Err(usize)`
146    /// with the insertion point to maintain order.
147    pub fn binary_search(&self, value: &T) -> Result<usize, usize> {
148        self.binary_search_by(|probe| probe.cmp(value))
149    }
150
151    /// Binary searches this slice with a custom comparison function.
152    #[inline]
153    pub fn binary_search_by<F>(&self, mut f: F) -> Result<usize, usize>
154    where
155        F: FnMut(T) -> Ordering,
156    {
157        let mut low = 0;
158        let mut high = self.len();
159        let mut reader = self.vec.reader();
160
161        while low < high {
162            let mid = low + (high - low) / 2;
163            // SAFETY: Bounds are checked by the loop invariants and the slice's
164            // construction, so the index into the parent vector is always valid.
165            let cmp = f(unsafe { reader.get_unchecked(self.start + mid) });
166            match cmp {
167                Ordering::Less => low = mid + 1,
168                Ordering::Equal => return Ok(mid),
169                Ordering::Greater => high = mid,
170            }
171        }
172        Err(low)
173    }
174
175    /// Binary searches this slice with a key extraction function.
176    #[inline]
177    pub fn binary_search_by_key<K, F>(&self, b: &K, mut f: F) -> Result<usize, usize>
178    where
179        F: FnMut(T) -> K,
180        K: Ord,
181    {
182        self.binary_search_by(|k| f(k).cmp(b))
183    }
184}
185
186/// An iterator over the decompressed values of an [`VarVecSlice`].
187///
188/// This struct is created by the [`iter`](VarVecSlice::iter) method.
189pub struct VarVecSliceIter<'a, T: Storable, E: Endianness, B: AsRef<[u64]>> {
190    slice: &'a VarVecSlice<'a, T, E, B>,
191    current_index: usize,
192}
193
194impl<'a, T: Storable, E: Endianness, B: AsRef<[u64]>> VarVecSliceIter<'a, T, E, B> {
195    /// Creates a new iterator for a given `VarVecSlice`.
196    fn new(slice: &'a VarVecSlice<'a, T, E, B>) -> Self {
197        Self {
198            slice,
199            current_index: 0,
200        }
201    }
202}
203
204impl<T, E, B> Iterator for VarVecSliceIter<'_, T, E, B>
205where
206    T: Storable,
207    E: Endianness,
208    B: AsRef<[u64]>,
209    for<'b> VarVecBitReader<'b, E>: BitRead<E, Error = core::convert::Infallible>
210        + CodesRead<E>
211        + BitSeek<Error = core::convert::Infallible>,
212{
213    type Item = T;
214
215    #[inline]
216    fn next(&mut self) -> Option<Self::Item> {
217        if self.current_index >= self.slice.len() {
218            return None;
219        }
220        // SAFETY: The iterator's logic guarantees the index is in bounds.
221        let value = unsafe { self.slice.get_unchecked(self.current_index) };
222        self.current_index += 1;
223        Some(value)
224    }
225
226    fn size_hint(&self) -> (usize, Option<usize>) {
227        let remaining = self.slice.len().saturating_sub(self.current_index);
228        (remaining, Some(remaining))
229    }
230}
231
232impl<T, E, B> ExactSizeIterator for VarVecSliceIter<'_, T, E, B>
233where
234    T: Storable,
235    E: Endianness,
236    B: AsRef<[u64]>,
237    for<'b> VarVecBitReader<'b, E>: BitRead<E, Error = core::convert::Infallible>
238        + CodesRead<E>
239        + BitSeek<Error = core::convert::Infallible>,
240{
241    fn len(&self) -> usize {
242        self.slice.len().saturating_sub(self.current_index)
243    }
244}
245
246impl<T, E, B> FusedIterator for VarVecSliceIter<'_, T, E, B>
247where
248    T: Storable,
249    E: Endianness,
250    B: AsRef<[u64]>,
251    for<'b> VarVecBitReader<'b, E>: BitRead<E, Error = core::convert::Infallible>
252        + CodesRead<E>
253        + BitSeek<Error = core::convert::Infallible>,
254{
255}
256
257impl<T: Storable, E: Endianness, B: AsRef<[u64]>> fmt::Debug for VarVecSliceIter<'_, T, E, B> {
258    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
259        f.debug_struct("VarVecSliceIter")
260            .field("remaining", &self.slice.len().saturating_sub(self.current_index))
261            .finish()
262    }
263}
compressed_intvec/variable/slice.rs

compressed_intvec/variable/
slice.rs
