compressed_intvec/variable/
slice.rs1use super::{traits::Storable, IntVec, IntVecBitReader};
10use dsi_bitstream::prelude::{BitRead, BitSeek, CodesRead, Endianness};
11use std::cmp::Ordering;
12use std::ops::Range;
13
14#[derive(Debug, Clone)]
49pub struct IntVecSlice<'a, T: Storable, E: Endianness, B: AsRef<[u64]>> {
50 vec: &'a IntVec<T, E, B>,
52 start: usize,
54 len: usize,
56}
57
58impl<'a, T: Storable, E: Endianness, B: AsRef<[u64]>> IntVecSlice<'a, T, E, B> {
59 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 #[inline]
70 pub fn len(&self) -> usize {
71 self.len
72 }
73
74 #[inline]
76 pub fn is_empty(&self) -> bool {
77 self.len == 0
78 }
79
80 #[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 self.vec.get(self.start + index)
96 }
97
98 #[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 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 pub fn binary_search(&self, value: &T) -> Result<usize, usize> {
143 self.binary_search_by(|probe| probe.cmp(value))
144 }
145
146 #[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 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 #[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
181pub 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 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 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}