compressed_intvec/variable/
slice.rs

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