Skip to main content

vortex_array/
patches.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::fmt::Debug;
5use std::hash::Hash;
6use std::ops::Range;
7
8use num_traits::NumCast;
9use vortex_buffer::BitBuffer;
10use vortex_buffer::BitBufferMut;
11use vortex_buffer::BufferAllocatorRef;
12use vortex_buffer::BufferMut;
13use vortex_error::VortexError;
14use vortex_error::VortexExpect as _;
15use vortex_error::VortexResult;
16use vortex_error::vortex_bail;
17use vortex_error::vortex_ensure;
18use vortex_error::vortex_ensure_eq;
19use vortex_error::vortex_err;
20use vortex_mask::AllOr;
21use vortex_mask::Mask;
22use vortex_mask::MaskValues;
23use vortex_utils::aliases::hash_map::HashMap;
24
25use crate::ArrayRef;
26use crate::ArraySlots;
27use crate::ExecutionCtx;
28use crate::IntoArray;
29use crate::arrays::Primitive;
30use crate::arrays::PrimitiveArray;
31use crate::arrays::primitive::PrimitiveArrayExt;
32use crate::builtins::ArrayBuiltins;
33use crate::dtype::DType;
34use crate::dtype::IntegerPType;
35use crate::dtype::NativePType;
36use crate::dtype::Nullability;
37use crate::dtype::Nullability::NonNullable;
38use crate::dtype::PType;
39use crate::dtype::UnsignedPType;
40use crate::match_each_unsigned_integer_ptype;
41use crate::scalar::Scalar;
42use crate::search_sorted::SearchResult;
43use crate::search_sorted::SearchSorted;
44use crate::search_sorted::SearchSortedPrimitiveArray;
45use crate::search_sorted::SearchSortedSide;
46use crate::validity::Validity;
47
48/// One patch index offset is stored for each chunk.
49/// This allows for constant time patch index lookups.
50pub const PATCH_CHUNK_SIZE: usize = 1024;
51
52#[derive(Copy, Clone, prost::Message)]
53pub struct PatchesMetadata {
54    #[prost(uint64, tag = "1")]
55    len: u64,
56    #[prost(uint64, tag = "2")]
57    offset: u64,
58    #[prost(enumeration = "PType", tag = "3")]
59    indices_ptype: i32,
60    #[prost(uint64, optional, tag = "4")]
61    chunk_offsets_len: Option<u64>,
62    #[prost(enumeration = "PType", optional, tag = "5")]
63    chunk_offsets_ptype: Option<i32>,
64    #[prost(uint64, optional, tag = "6")]
65    offset_within_chunk: Option<u64>,
66}
67
68impl PatchesMetadata {
69    #[inline]
70    pub fn new(
71        len: usize,
72        offset: usize,
73        indices_ptype: PType,
74        chunk_offsets_len: Option<usize>,
75        chunk_offsets_ptype: Option<PType>,
76        offset_within_chunk: Option<usize>,
77    ) -> Self {
78        Self {
79            len: len as u64,
80            offset: offset as u64,
81            indices_ptype: indices_ptype as i32,
82            chunk_offsets_len: chunk_offsets_len.map(|len| len as u64),
83            chunk_offsets_ptype: chunk_offsets_ptype.map(|pt| pt as i32),
84            offset_within_chunk: offset_within_chunk.map(|len| len as u64),
85        }
86    }
87
88    #[inline]
89    pub fn len(&self) -> VortexResult<usize> {
90        usize::try_from(self.len).map_err(|_| vortex_err!("len does not fit in usize"))
91    }
92
93    #[inline]
94    pub fn is_empty(&self) -> bool {
95        self.len == 0
96    }
97
98    #[inline]
99    pub fn offset(&self) -> VortexResult<usize> {
100        usize::try_from(self.offset).map_err(|_| vortex_err!("offset does not fit in usize"))
101    }
102
103    #[inline]
104    pub fn chunk_offsets_dtype(&self) -> VortexResult<Option<DType>> {
105        self.chunk_offsets_ptype
106            .map(|t| {
107                PType::try_from(t)
108                    .map_err(|e| vortex_err!("invalid i32 value {t} for PType: {}", e))
109                    .map(|ptype| DType::Primitive(ptype, NonNullable))
110            })
111            .transpose()
112    }
113
114    #[inline]
115    pub fn indices_dtype(&self) -> VortexResult<DType> {
116        let ptype = PType::try_from(self.indices_ptype).map_err(|e| {
117            vortex_err!("invalid i32 value {} for PType: {}", self.indices_ptype, e)
118        })?;
119        vortex_ensure!(
120            ptype.is_unsigned_int(),
121            "Patch indices must be unsigned integers"
122        );
123        Ok(DType::Primitive(ptype, NonNullable))
124    }
125}
126
127/// Metadata stored in an array's data struct for reconstructing [`Patches`] from slots.
128///
129/// The actual patch arrays (indices, values, chunk_offsets) live in the array's
130/// slots. This struct stores only the scalar metadata needed to reassemble them.
131#[derive(Clone, Debug, Hash, PartialEq, Eq)]
132pub struct PatchesData {
133    offset: usize,
134    offset_within_chunk: Option<usize>,
135}
136
137/// Slot indices for the three patch components within a slot array.
138#[derive(Copy, Clone, Debug)]
139pub struct PatchSlotIndices {
140    pub indices: usize,
141    pub values: usize,
142    pub chunk_offsets: usize,
143}
144
145impl PatchesData {
146    /// Extract patch metadata from an existing [`Patches`].
147    pub fn from_patches(patches: &Patches) -> Self {
148        Self {
149            offset: patches.offset(),
150            offset_within_chunk: patches.offset_within_chunk(),
151        }
152    }
153
154    /// Reconstruct patches from the given slot positions.
155    ///
156    /// Returns `None` if `patches_data` is `None`.
157    /// Panics if `patches_data` is `Some` but the indices or values slots are missing.
158    pub fn patches_from_slots(
159        patches_data: Option<&Self>,
160        len: usize,
161        slots: &[Option<ArrayRef>],
162        slot_idx: PatchSlotIndices,
163    ) -> Option<Patches> {
164        let data = patches_data?;
165        let indices = slots[slot_idx.indices]
166            .as_ref()
167            .vortex_expect("patches_data is set but patch_indices slot is missing");
168        let values = slots[slot_idx.values]
169            .as_ref()
170            .vortex_expect("patches_data is set but patch_values slot is missing");
171        Some(unsafe {
172            Patches::new_unchecked(
173                len,
174                data.offset,
175                indices.clone(),
176                values.clone(),
177                slots[slot_idx.chunk_offsets].clone(),
178                data.offset_within_chunk,
179            )
180        })
181    }
182
183    /// Push 3 patch slots (indices, values, chunk_offsets) onto a slot vector.
184    ///
185    /// If `patches` is `None`, pushes three `None` entries.
186    pub fn push_slots(slots: &mut ArraySlots, patches: Option<&Patches>) {
187        match patches {
188            Some(p) => {
189                slots.push(Some(p.indices().clone()));
190                slots.push(Some(p.values().clone()));
191                slots.push(p.chunk_offsets().clone());
192            }
193            None => {
194                slots.push(None);
195                slots.push(None);
196                slots.push(None);
197            }
198        }
199    }
200
201    /// Returns the patch offset.
202    #[inline]
203    pub fn offset(&self) -> usize {
204        self.offset
205    }
206
207    /// Returns the offset within the first chunk, if chunk offsets are present.
208    #[inline]
209    pub fn offset_within_chunk(&self) -> Option<usize> {
210        self.offset_within_chunk
211    }
212}
213
214/// A helper for working with patched arrays.
215#[derive(Debug, Clone)]
216pub struct Patches {
217    array_len: usize,
218    offset: usize,
219    indices: ArrayRef,
220    values: ArrayRef,
221    /// Stores the patch index offset for each chunk.
222    ///
223    /// This allows us to lookup the patches for a given chunk in constant time via
224    /// `patch_indices[chunk_offsets[i]..chunk_offsets[i+1]]`.
225    ///
226    /// This is optional for compatibility reasons.
227    chunk_offsets: Option<ArrayRef>,
228    /// Chunk offsets are only sliced off in case the slice is fully
229    /// outside of the chunk range.
230    ///
231    /// Though the range for indices and values is sliced in terms of
232    /// individual elements, not chunks. To account for that we do a
233    /// saturating sub when adjusting the indices based on the chunk offset.
234    ///
235    /// `offset_within_chunk` is necessary in order to keep track of how many
236    /// elements were sliced off within the chunk.
237    offset_within_chunk: Option<usize>,
238}
239
240impl Patches {
241    pub fn new(
242        array_len: usize,
243        offset: usize,
244        indices: ArrayRef,
245        values: ArrayRef,
246        chunk_offsets: Option<ArrayRef>,
247        ctx: &mut ExecutionCtx,
248    ) -> VortexResult<Self> {
249        vortex_ensure_eq!(indices.len(), values.len());
250        vortex_ensure!(
251            indices.dtype().is_unsigned_int() && !indices.dtype().is_nullable(),
252            "Patch indices must be non-nullable unsigned integers, got {:?}",
253            indices.dtype()
254        );
255
256        vortex_ensure!(
257            indices.len() <= array_len,
258            "Patch indices must be shorter than the array length"
259        );
260        vortex_ensure!(!indices.is_empty(), "Patch indices must not be empty");
261
262        // Perform validation of components when they are host-resident.
263        // This is not possible to do eagerly when the data is on GPU memory.
264        if indices.is_host() && values.is_host() {
265            let max = usize::try_from(&indices.execute_scalar(indices.len() - 1, ctx)?)
266                .map_err(|_| vortex_err!("indices must be a number"))?;
267            vortex_ensure!(
268                max - offset < array_len,
269                "Patch indices {max:?}, offset {offset} are longer than the array length {array_len}"
270            );
271
272            #[cfg(debug_assertions)]
273            {
274                use crate::aggregate_fn::fns::is_sorted::is_strict_sorted;
275                assert!(
276                    is_strict_sorted(&indices, ctx).unwrap_or(false),
277                    "Patch indices must be strictly increasing"
278                );
279            }
280        }
281
282        Ok(Self {
283            array_len,
284            offset,
285            indices,
286            values,
287            chunk_offsets: chunk_offsets.clone(),
288            // Initialize with `Some(0)` only if `chunk_offsets` are set.
289            offset_within_chunk: chunk_offsets.map(|_| 0),
290        })
291    }
292
293    /// Reconstruct patches from serialized metadata and their child arrays.
294    ///
295    /// Preserves the number of patches sliced off within the first chunk. Metadata without this
296    /// field defaults to zero for compatibility with older arrays.
297    pub fn from_metadata(
298        array_len: usize,
299        metadata: &PatchesMetadata,
300        indices: ArrayRef,
301        values: ArrayRef,
302        chunk_offsets: Option<ArrayRef>,
303        ctx: &mut ExecutionCtx,
304    ) -> VortexResult<Self> {
305        let mut patches = Self::new(
306            array_len,
307            metadata.offset()?,
308            indices,
309            values,
310            chunk_offsets,
311            ctx,
312        )?;
313        if let Some(chunk_offsets) = &patches.chunk_offsets {
314            let offset_within_chunk = usize::try_from(metadata.offset_within_chunk())?;
315            let sliced_rows = patches.offset % PATCH_CHUNK_SIZE;
316            vortex_ensure!(
317                offset_within_chunk <= sliced_rows,
318                "Patch offset within chunk exceeds the sliced row count"
319            );
320
321            // A wrong offset can assign first-chunk patches to a later chunk during decoding.
322            // Check the boundary against the indices, not just the original chunk's patch count.
323            if chunk_offsets.len() > 1 && chunk_offsets.is_host() && patches.indices.is_host() {
324                let first_chunk_end = patches
325                    .offset
326                    .checked_add(PATCH_CHUNK_SIZE - sliced_rows)
327                    .ok_or_else(|| vortex_err!("Patch chunk boundary overflows usize"))?;
328                let retained =
329                    search_index_binary_search(&patches.indices, first_chunk_end, ctx)?.to_index();
330                let expected_offset = patches
331                    .chunk_offset_at(1, ctx)?
332                    .checked_sub(patches.chunk_offset_at(0, ctx)?)
333                    .and_then(|count| count.checked_sub(retained))
334                    .ok_or_else(|| vortex_err!("Invalid patch chunk offsets"))?;
335                vortex_ensure_eq!(
336                    offset_within_chunk,
337                    expected_offset,
338                    "Patch offset within chunk disagrees with the patch indices"
339                );
340            }
341            patches.offset_within_chunk = Some(offset_within_chunk);
342        }
343        Ok(patches)
344    }
345
346    /// Construct new patches without validating any of the arguments
347    ///
348    /// # Safety
349    ///
350    /// Users have to assert that
351    /// * Indices and values have the same length
352    /// * Indices is an unsigned integer type
353    /// * Indices must be strictly increasing
354    /// * Last value in indices is smaller than array_len
355    pub unsafe fn new_unchecked(
356        array_len: usize,
357        offset: usize,
358        indices: ArrayRef,
359        values: ArrayRef,
360        chunk_offsets: Option<ArrayRef>,
361        offset_within_chunk: Option<usize>,
362    ) -> Self {
363        Self {
364            array_len,
365            offset,
366            indices,
367            values,
368            chunk_offsets,
369            offset_within_chunk,
370        }
371    }
372
373    #[inline]
374    pub fn array_len(&self) -> usize {
375        self.array_len
376    }
377
378    #[inline]
379    pub fn num_patches(&self) -> usize {
380        self.indices.len()
381    }
382
383    #[inline]
384    pub fn dtype(&self) -> &DType {
385        self.values.dtype()
386    }
387
388    #[inline]
389    pub fn indices(&self) -> &ArrayRef {
390        &self.indices
391    }
392
393    #[inline]
394    pub fn into_indices(self) -> ArrayRef {
395        self.indices
396    }
397
398    #[inline]
399    pub fn indices_mut(&mut self) -> &mut ArrayRef {
400        &mut self.indices
401    }
402
403    #[inline]
404    pub fn values(&self) -> &ArrayRef {
405        &self.values
406    }
407
408    #[inline]
409    pub fn into_values(self) -> ArrayRef {
410        self.values
411    }
412
413    #[inline]
414    pub fn values_mut(&mut self) -> &mut ArrayRef {
415        &mut self.values
416    }
417
418    #[inline]
419    // Absolute offset: 0 if the array is unsliced.
420    pub fn offset(&self) -> usize {
421        self.offset
422    }
423
424    #[inline]
425    pub fn chunk_offsets(&self) -> &Option<ArrayRef> {
426        &self.chunk_offsets
427    }
428
429    #[inline]
430    pub fn chunk_offset_at(&self, idx: usize, ctx: &mut ExecutionCtx) -> VortexResult<usize> {
431        let Some(chunk_offsets) = &self.chunk_offsets else {
432            vortex_bail!("chunk_offsets must be set to retrieve offset at index")
433        };
434
435        chunk_offsets
436            .execute_scalar(idx, ctx)?
437            .as_primitive()
438            .as_::<usize>()
439            .ok_or_else(|| vortex_err!("chunk offset does not fit in usize"))
440    }
441
442    /// Returns the number of patches sliced off from the current first chunk.
443    ///
444    /// When patches are sliced, the chunk offsets array is also sliced to only include
445    /// chunks that overlap with the slice range. However, the slice boundary may fall
446    /// in the middle of a chunk's patch range. This offset indicates how many patches
447    /// at the start of the first chunk should be skipped.
448    ///
449    /// Returns `None` if chunk offsets are not set.
450    #[inline]
451    pub fn offset_within_chunk(&self) -> Option<usize> {
452        self.offset_within_chunk
453    }
454
455    #[inline]
456    pub fn indices_ptype(&self) -> VortexResult<PType> {
457        PType::try_from(self.indices.dtype())
458            .map_err(|_| vortex_err!("indices dtype is not primitive"))
459    }
460
461    pub fn to_metadata(&self, len: usize, dtype: &DType) -> VortexResult<PatchesMetadata> {
462        if self.indices.len() > len {
463            vortex_bail!(
464                "Patch indices {} are longer than the array length {}",
465                self.indices.len(),
466                len
467            );
468        }
469        if self.values.dtype() != dtype {
470            vortex_bail!(
471                "Patch values dtype {} does not match array dtype {}",
472                self.values.dtype(),
473                dtype
474            );
475        }
476        let chunk_offsets_len = self.chunk_offsets.as_ref().map(|co| co.len());
477        let chunk_offsets_ptype = self.chunk_offsets.as_ref().map(|co| co.dtype().as_ptype());
478
479        Ok(PatchesMetadata::new(
480            self.indices.len(),
481            self.offset,
482            self.indices.dtype().as_ptype(),
483            chunk_offsets_len,
484            chunk_offsets_ptype,
485            self.offset_within_chunk,
486        ))
487    }
488
489    /// Get the patched value at a given index if it exists.
490    pub fn get_patched(
491        &self,
492        index: usize,
493        ctx: &mut ExecutionCtx,
494    ) -> VortexResult<Option<Scalar>> {
495        self.search_index(index, ctx)?
496            .to_found()
497            .map(|patch_idx| self.values().execute_scalar(patch_idx, ctx))
498            .transpose()
499    }
500
501    /// Searches for `index` in the indices array.
502    ///
503    /// Chooses between chunked search when [`Self::chunk_offsets`] is
504    /// available, and binary search otherwise. The `index` parameter is
505    /// adjusted by [`Self::offset`] for both.
506    ///
507    /// # Arguments
508    /// * `index` - The index to search for
509    ///
510    /// # Returns
511    /// * [`SearchResult::Found(patch_idx)`] - If a patch exists at this index, returns the
512    ///   position in the patches array
513    /// * [`SearchResult::NotFound(insertion_point)`] - If no patch exists, returns where
514    ///   a patch at this index would be inserted to maintain sorted order
515    ///
516    /// [`SearchResult::Found(patch_idx)`]: SearchResult::Found
517    /// [`SearchResult::NotFound(insertion_point)`]: SearchResult::NotFound
518    pub fn search_index(&self, index: usize, ctx: &mut ExecutionCtx) -> VortexResult<SearchResult> {
519        if self.chunk_offsets.is_some() {
520            return self.search_index_chunked(index, ctx);
521        }
522
523        search_index_binary_search(&self.indices, index + self.offset, ctx)
524    }
525
526    /// Constant time searches for `index` in the indices array.
527    ///
528    /// First determines which chunk the target index falls into, then performs
529    /// a binary search within that chunk's range.
530    ///
531    /// Returns a [`SearchResult`] indicating either the exact patch index if found,
532    /// or the insertion point if not found.
533    ///
534    /// Returns an error if `chunk_offsets` or `offset_within_chunk` are not set.
535    fn search_index_chunked(
536        &self,
537        index: usize,
538        ctx: &mut ExecutionCtx,
539    ) -> VortexResult<SearchResult> {
540        let Some(chunk_offsets) = &self.chunk_offsets else {
541            vortex_bail!("chunk_offsets is required to be set")
542        };
543
544        let Some(offset_within_chunk) = self.offset_within_chunk else {
545            vortex_bail!("offset_within_chunk is required to be set")
546        };
547
548        if index >= self.array_len() {
549            return Ok(SearchResult::NotFound(self.indices().len()));
550        }
551
552        let chunk_idx = (index + self.offset % PATCH_CHUNK_SIZE) / PATCH_CHUNK_SIZE;
553
554        // The three reads below are of the same array, so they share one probe rather than
555        // building one per read as `Self::chunk_offset_at` does.
556        let mut probe = chunk_offsets.repeated_probe();
557        let mut chunk_offset_at = |idx: usize| -> VortexResult<usize> {
558            probe
559                .execute_scalar(idx, ctx)?
560                .as_primitive()
561                .as_::<usize>()
562                .ok_or_else(|| vortex_err!("chunk offset does not fit in usize"))
563        };
564
565        // Patch index offsets are absolute and need to be offset by the first chunk of the current slice.
566        let base_offset = chunk_offset_at(0)?;
567
568        let patches_start_idx = (chunk_offset_at(chunk_idx)? - base_offset)
569            // Chunk offsets are only sliced off in case the slice is fully
570            // outside of the chunk range.
571            //
572            // Though the range for indices and values is sliced in terms of
573            // individual elements, not chunks. To account for that we do a
574            // saturating sub when adjusting the indices based on the chunk offset.
575            .saturating_sub(offset_within_chunk);
576
577        let patches_end_idx = if chunk_idx < chunk_offsets.len() - 1 {
578            (chunk_offset_at(chunk_idx + 1)? - base_offset)
579                .saturating_sub(offset_within_chunk)
580                .min(self.indices.len())
581        } else {
582            self.indices.len()
583        };
584
585        let chunk_indices = self.indices.slice(patches_start_idx..patches_end_idx)?;
586        let result = search_index_binary_search(&chunk_indices, index + self.offset, ctx)?;
587
588        Ok(match result {
589            SearchResult::Found(idx) => SearchResult::Found(patches_start_idx + idx),
590            SearchResult::NotFound(idx) => SearchResult::NotFound(patches_start_idx + idx),
591        })
592    }
593
594    /// Batch version of `search_index`.
595    ///
596    /// In contrast to `search_index`, this function requires `indices` as
597    /// well as `chunk_offsets` to be passed as slices. This is to avoid
598    /// redundant canonicalization and `scalar_at` lookups across calls.
599    fn search_index_chunked_batch<T, O>(
600        &self,
601        indices: &[T],
602        chunk_offsets: &[O],
603        index: T,
604    ) -> VortexResult<SearchResult>
605    where
606        T: UnsignedPType,
607        O: UnsignedPType,
608        usize: TryFrom<T>,
609        usize: TryFrom<O>,
610    {
611        let Some(offset_within_chunk) = self.offset_within_chunk else {
612            vortex_bail!("offset_within_chunk is required to be set")
613        };
614
615        let chunk_idx = {
616            let Ok(index) = usize::try_from(index) else {
617                // If the needle cannot be converted to usize, it's larger than all values in this array.
618                return Ok(SearchResult::NotFound(indices.len()));
619            };
620
621            if index >= self.array_len() {
622                return Ok(SearchResult::NotFound(self.indices().len()));
623            }
624
625            (index + self.offset % PATCH_CHUNK_SIZE) / PATCH_CHUNK_SIZE
626        };
627
628        // Patch index offsets are absolute and need to be offset by the first chunk of the current slice.
629        let chunk_offset = usize::try_from(chunk_offsets[chunk_idx] - chunk_offsets[0])
630            .map_err(|_| vortex_err!("chunk_offset failed to convert to usize"))?;
631
632        let patches_start_idx = chunk_offset
633            // Chunk offsets are only sliced off in case the slice is fully
634            // outside of the chunk range.
635            //
636            // Though the range for indices and values is sliced in terms of
637            // individual elements, not chunks. To account for that we do a
638            // saturating sub when adjusting the indices based on the chunk offset.
639            .saturating_sub(offset_within_chunk);
640
641        let patches_end_idx = if chunk_idx < chunk_offsets.len() - 1 {
642            usize::try_from(chunk_offsets[chunk_idx + 1] - chunk_offsets[0])
643                .map_err(|_| vortex_err!("patches_end_idx failed to convert to usize"))?
644                .saturating_sub(offset_within_chunk)
645                .min(indices.len())
646        } else {
647            self.indices.len()
648        };
649
650        let Some(offset) = T::from(self.offset) else {
651            // If the offset cannot be converted to T, it's larger than all values in this array.
652            return Ok(SearchResult::NotFound(indices.len()));
653        };
654
655        let chunk_indices = &indices[patches_start_idx..patches_end_idx];
656        let result = chunk_indices.search_sorted(&(index + offset), SearchSortedSide::Left)?;
657
658        Ok(match result {
659            SearchResult::Found(idx) => SearchResult::Found(patches_start_idx + idx),
660            SearchResult::NotFound(idx) => SearchResult::NotFound(patches_start_idx + idx),
661        })
662    }
663
664    /// Returns the minimum patch index
665    pub fn min_index(&self, ctx: &mut ExecutionCtx) -> VortexResult<usize> {
666        let first = self
667            .indices
668            .execute_scalar(0, ctx)?
669            .as_primitive()
670            .as_::<usize>()
671            .ok_or_else(|| vortex_err!("index does not fit in usize"))?;
672        Ok(first - self.offset)
673    }
674
675    /// Returns the maximum patch index
676    pub fn max_index(&self, ctx: &mut ExecutionCtx) -> VortexResult<usize> {
677        let last = self
678            .indices
679            .execute_scalar(self.indices.len() - 1, ctx)?
680            .as_primitive()
681            .as_::<usize>()
682            .ok_or_else(|| vortex_err!("index does not fit in usize"))?;
683        Ok(last - self.offset)
684    }
685
686    /// Filter the patches by a mask, resulting in new patches for the filtered array.
687    pub fn filter(&self, mask: &Mask, ctx: &mut ExecutionCtx) -> VortexResult<Option<Self>> {
688        if mask.len() != self.array_len {
689            vortex_bail!(
690                "Filter mask length {} does not match array length {}",
691                mask.len(),
692                self.array_len
693            );
694        }
695
696        match mask {
697            Mask::AllTrue(_) => Ok(Some(self.clone())),
698            Mask::AllFalse(_) => Ok(None),
699            Mask::Values(mask_values) => {
700                let flat_indices = self.indices().clone().execute::<PrimitiveArray>(ctx)?;
701                match_each_unsigned_integer_ptype!(flat_indices.ptype(), |I| {
702                    filter_patches_with_mask(
703                        flat_indices.as_slice::<I>(),
704                        self.offset(),
705                        self.values(),
706                        mask_values,
707                        ctx.allocator(),
708                    )
709                })
710            }
711        }
712    }
713
714    /// Mask the patches, REMOVING the patches where the mask is true.
715    /// Unlike filter, this preserves the patch indices.
716    /// Unlike mask on a single array, this does not set masked values to null.
717    ///
718    /// Masking an array always yields a nullable result (see [`crate::scalar_fn::fns::mask`]),
719    /// so the surviving patch values are widened to nullable to match the masked parent. Callers
720    /// therefore receive patches with the correct dtype and do not need to re-cast them.
721    // TODO(joe): make this lazy and remove the ctx.
722    pub fn mask(&self, mask: &Mask, ctx: &mut ExecutionCtx) -> VortexResult<Option<Self>> {
723        if mask.len() != self.array_len {
724            vortex_bail!(
725                "Filter mask length {} does not match array length {}",
726                mask.len(),
727                self.array_len
728            );
729        }
730
731        let filter_mask = match mask.bit_buffer() {
732            AllOr::All => return Ok(None),
733            AllOr::None => return self.clone().into_nullable_values().map(Some),
734            AllOr::Some(masked) => {
735                let patch_indices = self.indices().clone().execute::<PrimitiveArray>(ctx)?;
736                match_each_unsigned_integer_ptype!(patch_indices.ptype(), |P| {
737                    let patch_indices = patch_indices.as_slice::<P>();
738                    Mask::from_buffer(BitBuffer::collect_bool_in(
739                        patch_indices.len(),
740                        |i| {
741                            #[allow(clippy::cast_possible_truncation)]
742                            let idx = (patch_indices[i] as usize) - self.offset;
743                            !masked.value(idx)
744                        },
745                        ctx.allocator().clone(),
746                    ))
747                })
748            }
749        };
750
751        if filter_mask.all_false() {
752            return Ok(None);
753        }
754
755        // SAFETY: filtering indices/values with same mask maintains their 1:1 relationship
756        let filtered_indices = self.indices.filter(filter_mask.clone())?;
757        let filtered_values = self.values.filter(filter_mask)?;
758
759        Self {
760            array_len: self.array_len,
761            offset: self.offset,
762            indices: filtered_indices,
763            values: filtered_values,
764            // TODO(0ax1): Chunk offsets are invalid after a filter is applied.
765            chunk_offsets: None,
766            offset_within_chunk: self.offset_within_chunk,
767        }
768        .into_nullable_values()
769        .map(Some)
770    }
771
772    /// Widen the patch values to their nullable dtype, leaving indices and offsets untouched.
773    ///
774    /// The values stay logically unchanged (all currently-valid entries remain valid); only the
775    /// dtype's nullability flag is set. Used by [`Self::mask`], whose result must be nullable.
776    fn into_nullable_values(self) -> VortexResult<Self> {
777        if self.values.dtype().is_nullable() {
778            return Ok(self);
779        }
780        let nullable = self.values.dtype().as_nullable();
781        self.map_values(|values| values.cast(nullable))
782    }
783
784    /// Slice the patches by a range of the patched array.
785    pub fn slice(&self, range: Range<usize>, ctx: &mut ExecutionCtx) -> VortexResult<Option<Self>> {
786        let slice_start_idx = self.search_index(range.start, ctx)?.to_index();
787        let slice_end_idx = self.search_index(range.end, ctx)?.to_index();
788
789        if slice_start_idx == slice_end_idx {
790            return Ok(None);
791        }
792
793        let values = self.values().slice(slice_start_idx..slice_end_idx)?;
794        let indices = self.indices().slice(slice_start_idx..slice_end_idx)?;
795
796        let new_chunk_offsets = self
797            .chunk_offsets
798            .as_ref()
799            .map(|chunk_offsets| -> VortexResult<ArrayRef> {
800                let chunk_relative_offset = self.offset % PATCH_CHUNK_SIZE;
801                let chunk_start_idx = (chunk_relative_offset + range.start) / PATCH_CHUNK_SIZE;
802                let chunk_end_idx = (chunk_relative_offset + range.end).div_ceil(PATCH_CHUNK_SIZE);
803                chunk_offsets.slice(chunk_start_idx..chunk_end_idx)
804            })
805            .transpose()?;
806
807        let offset_within_chunk = new_chunk_offsets
808            .as_ref()
809            .map(|new_chunk_offsets| -> VortexResult<usize> {
810                let new_chunk_base = new_chunk_offsets
811                    .execute_scalar(0, ctx)?
812                    .as_primitive()
813                    .as_::<usize>()
814                    .ok_or_else(|| vortex_err!("chunk offset does not fit in usize"))?;
815                let parent_chunk_base = self.chunk_offset_at(0, ctx)?;
816                let parent_within = self.offset_within_chunk.unwrap_or(0);
817                Ok(parent_chunk_base + parent_within + slice_start_idx - new_chunk_base)
818            })
819            .transpose()?;
820
821        Ok(Some(Self {
822            array_len: range.len(),
823            offset: range.start + self.offset(),
824            indices,
825            values,
826            chunk_offsets: new_chunk_offsets,
827            offset_within_chunk,
828        }))
829    }
830
831    // https://docs.google.com/spreadsheets/d/1D9vBZ1QJ6mwcIvV5wIL0hjGgVchcEnAyhvitqWu2ugU
832    const PREFER_MAP_WHEN_PATCHES_OVER_INDICES_LESS_THAN: f64 = 5.0;
833
834    fn is_map_faster_than_search(&self, take_indices: &PrimitiveArray) -> bool {
835        (self.num_patches() as f64 / take_indices.len() as f64)
836            < Self::PREFER_MAP_WHEN_PATCHES_OVER_INDICES_LESS_THAN
837    }
838
839    /// Take the indices from the patches
840    ///
841    /// Any nulls in take_indices are added to the resulting patches.
842    pub fn take_with_nulls(
843        &self,
844        take_indices: &ArrayRef,
845        ctx: &mut ExecutionCtx,
846    ) -> VortexResult<Option<Self>> {
847        if take_indices.is_empty() {
848            return Ok(None);
849        }
850
851        let take_indices = take_indices.clone().execute::<PrimitiveArray>(ctx)?;
852        if self.is_map_faster_than_search(&take_indices) {
853            self.take_map(take_indices, true, ctx)
854        } else {
855            self.take_search(take_indices, true, ctx)
856        }
857    }
858
859    /// Take the indices from the patches.
860    ///
861    /// Any nulls in take_indices are ignored.
862    pub fn take(
863        &self,
864        take_indices: &ArrayRef,
865        ctx: &mut ExecutionCtx,
866    ) -> VortexResult<Option<Self>> {
867        if take_indices.is_empty() {
868            return Ok(None);
869        }
870
871        let take_indices = take_indices.clone().execute::<PrimitiveArray>(ctx)?;
872        if self.is_map_faster_than_search(&take_indices) {
873            self.take_map(take_indices, false, ctx)
874        } else {
875            self.take_search(take_indices, false, ctx)
876        }
877    }
878
879    #[expect(
880        clippy::cognitive_complexity,
881        reason = "complexity is from nested match_each_* macros"
882    )]
883    pub fn take_search(
884        &self,
885        take_indices: PrimitiveArray,
886        include_nulls: bool,
887        ctx: &mut ExecutionCtx,
888    ) -> VortexResult<Option<Self>> {
889        let take_indices_validity = take_indices.validity()?;
890        // Take indices are non-negative; reinterpret to unsigned so the `TakeT` dimension
891        // dispatches over 4 widths instead of 8.
892        let take_indices_unsigned =
893            take_indices.reinterpret_cast(take_indices.ptype().to_unsigned());
894        let patch_indices = self.indices.clone().execute::<PrimitiveArray>(ctx)?;
895        let chunk_offsets = self
896            .chunk_offsets()
897            .as_ref()
898            .map(|co| co.clone().execute::<PrimitiveArray>(ctx))
899            .transpose()?;
900
901        let (values_indices, new_indices): (BufferMut<u64>, BufferMut<u64>) =
902            match_each_unsigned_integer_ptype!(patch_indices.ptype(), |PatchT| {
903                let patch_indices_slice = patch_indices.as_slice::<PatchT>();
904                match_each_unsigned_integer_ptype!(take_indices_unsigned.ptype(), |TakeT| {
905                    let take_slice = take_indices_unsigned.as_slice::<TakeT>();
906
907                    if let Some(chunk_offsets) = chunk_offsets {
908                        match_each_unsigned_integer_ptype!(chunk_offsets.ptype(), |OffsetT| {
909                            let chunk_offsets = chunk_offsets.as_slice::<OffsetT>();
910                            take_indices_with_search_fn(
911                                patch_indices_slice,
912                                take_slice,
913                                take_indices
914                                    .as_ref()
915                                    .validity()?
916                                    .execute_mask(take_indices.as_ref().len(), ctx)?,
917                                include_nulls,
918                                ctx.allocator(),
919                                |take_idx| {
920                                    self.search_index_chunked_batch(
921                                        patch_indices_slice,
922                                        chunk_offsets,
923                                        take_idx,
924                                    )
925                                },
926                            )?
927                        })
928                    } else {
929                        take_indices_with_search_fn(
930                            patch_indices_slice,
931                            take_slice,
932                            take_indices
933                                .as_ref()
934                                .validity()?
935                                .execute_mask(take_indices.as_ref().len(), ctx)?,
936                            include_nulls,
937                            ctx.allocator(),
938                            |take_idx| {
939                                let Some(offset) = <PatchT as NumCast>::from(self.offset) else {
940                                    // If the offset cannot be converted to T, it's larger than all values in this array.
941                                    return Ok(SearchResult::NotFound(patch_indices_slice.len()));
942                                };
943
944                                patch_indices_slice
945                                    .search_sorted(&(take_idx + offset), SearchSortedSide::Left)
946                            },
947                        )?
948                    }
949                })
950            });
951
952        if new_indices.is_empty() {
953            return Ok(None);
954        }
955
956        let new_indices = new_indices.into_array();
957        let new_array_len = take_indices.len();
958        let values_validity = take_indices_validity.take(&new_indices)?;
959
960        Ok(Some(Self {
961            array_len: new_array_len,
962            offset: 0,
963            indices: new_indices,
964            values: self
965                .values()
966                .take(PrimitiveArray::new(values_indices, values_validity).into_array())?,
967            chunk_offsets: None,
968            offset_within_chunk: Some(0), // Reset when creating new Patches.
969        }))
970    }
971
972    pub fn take_map(
973        &self,
974        take_indices: PrimitiveArray,
975        include_nulls: bool,
976        ctx: &mut ExecutionCtx,
977    ) -> VortexResult<Option<Self>> {
978        let indices = self.indices.clone().execute::<PrimitiveArray>(ctx)?;
979        let new_length = take_indices.len();
980        // Take indices are non-negative; reinterpret to unsigned (4 widths instead of 8).
981        let take_indices_unsigned =
982            take_indices.reinterpret_cast(take_indices.ptype().to_unsigned());
983
984        let min_index = self.min_index(ctx)?;
985        let max_index = self.max_index(ctx)?;
986
987        let Some((new_sparse_indices, value_indices)) =
988            match_each_unsigned_integer_ptype!(indices.ptype(), |Indices| {
989                match_each_unsigned_integer_ptype!(take_indices_unsigned.ptype(), |TakeIndices| {
990                    let take_validity = take_indices
991                        .validity()?
992                        .execute_mask(take_indices.len(), ctx)?;
993                    let take_nullability = take_indices.validity()?.nullability();
994                    let take_slice = take_indices_unsigned.as_slice::<TakeIndices>();
995                    take_map::<_, TakeIndices>(
996                        indices.as_slice::<Indices>(),
997                        take_slice,
998                        take_validity,
999                        take_nullability,
1000                        self.offset(),
1001                        min_index,
1002                        max_index,
1003                        include_nulls,
1004                        ctx.allocator(),
1005                    )?
1006                })
1007            })
1008        else {
1009            return Ok(None);
1010        };
1011
1012        let taken_values = self.values().take(value_indices)?;
1013
1014        Ok(Some(Patches {
1015            array_len: new_length,
1016            offset: 0,
1017            indices: new_sparse_indices,
1018            values: taken_values,
1019            // TODO(0ax1): Chunk offsets are invalid after take is applied.
1020            chunk_offsets: None,
1021            offset_within_chunk: self.offset_within_chunk,
1022        }))
1023    }
1024
1025    pub fn map_values<F>(self, f: F) -> VortexResult<Self>
1026    where
1027        F: FnOnce(ArrayRef) -> VortexResult<ArrayRef>,
1028    {
1029        let values = f(self.values)?;
1030        if self.indices.len() != values.len() {
1031            vortex_bail!(
1032                "map_values must preserve length: expected {} received {}",
1033                self.indices.len(),
1034                values.len()
1035            )
1036        }
1037
1038        Ok(Self {
1039            array_len: self.array_len,
1040            offset: self.offset,
1041            indices: self.indices,
1042            values,
1043            chunk_offsets: self.chunk_offsets,
1044            offset_within_chunk: self.offset_within_chunk,
1045        })
1046    }
1047}
1048
1049/// Binary searches for `needle` in the indices array.
1050///
1051/// # Returns
1052/// [`SearchResult::Found`] with the position if needle exists, or [`SearchResult::NotFound`]
1053/// with the insertion point if not found.
1054fn search_index_binary_search(
1055    indices: &ArrayRef,
1056    needle: usize,
1057    ctx: &mut ExecutionCtx,
1058) -> VortexResult<SearchResult> {
1059    if let Some(primitive) = indices.as_opt::<Primitive>() {
1060        match_each_unsigned_integer_ptype!(primitive.ptype(), |T| {
1061            let Ok(needle) = T::try_from(needle) else {
1062                // If the needle is not of type T, then it cannot possibly be in this array.
1063                //
1064                // The needle is a non-negative integer (a usize); therefore, it must be larger
1065                // than all values in this array.
1066                return Ok(SearchResult::NotFound(primitive.len()));
1067            };
1068            return primitive
1069                .as_slice::<T>()
1070                .search_sorted(&needle, SearchSortedSide::Left);
1071        });
1072    }
1073
1074    search_index_binary_search_scalar(indices, needle, ctx)
1075}
1076
1077fn search_index_binary_search_scalar(
1078    indices: &ArrayRef,
1079    needle: usize,
1080    ctx: &mut ExecutionCtx,
1081) -> VortexResult<SearchResult> {
1082    match_each_unsigned_integer_ptype!(indices.dtype().as_ptype(), |T| {
1083        SearchSortedPrimitiveArray::<T>::new(indices, ctx)
1084            .search_sorted(&needle, SearchSortedSide::Left)
1085    })
1086}
1087
1088#[expect(clippy::too_many_arguments)] // private function, can clean up one day
1089fn take_map<I: NativePType + Hash + Eq + TryFrom<usize>, T: NativePType>(
1090    indices: &[I],
1091    take_indices: &[T],
1092    take_validity: Mask,
1093    take_nullability: Nullability,
1094    indices_offset: usize,
1095    min_index: usize,
1096    max_index: usize,
1097    include_nulls: bool,
1098    allocator: &BufferAllocatorRef,
1099) -> VortexResult<Option<(ArrayRef, ArrayRef)>>
1100where
1101    usize: TryFrom<T>,
1102    VortexError: From<<I as TryFrom<usize>>::Error>,
1103{
1104    let offset_i = I::try_from(indices_offset)?;
1105
1106    let sparse_index_to_value_index: HashMap<I, usize> = indices
1107        .iter()
1108        .copied()
1109        .map(|idx| idx - offset_i)
1110        .enumerate()
1111        .map(|(value_index, sparse_index)| (sparse_index, value_index))
1112        .collect();
1113
1114    let mut new_sparse_indices =
1115        BufferMut::<u64>::with_capacity_in(take_indices.len(), allocator.clone());
1116    let mut value_indices =
1117        BufferMut::<u64>::with_capacity_in(take_indices.len(), allocator.clone());
1118
1119    for (idx_in_take, &take_idx) in take_indices.iter().enumerate() {
1120        let ti = usize::try_from(take_idx)
1121            .map_err(|_| vortex_err!("Failed to convert index to usize"))?;
1122
1123        // If we have to take nulls the take index doesn't matter, make it 0 for consistency
1124        let is_null = match take_validity.bit_buffer() {
1125            AllOr::All => false,
1126            AllOr::None => true,
1127            AllOr::Some(buf) => !buf.value(idx_in_take),
1128        };
1129        if is_null {
1130            if include_nulls {
1131                new_sparse_indices.push(idx_in_take as u64);
1132                value_indices.push(0);
1133            }
1134        } else if ti >= min_index && ti <= max_index {
1135            let ti_as_i = I::try_from(ti)
1136                .map_err(|_| vortex_err!("take index does not fit in index type"))?;
1137            if let Some(&value_index) = sparse_index_to_value_index.get(&ti_as_i) {
1138                new_sparse_indices.push(idx_in_take as u64);
1139                value_indices.push(value_index as u64);
1140            }
1141        }
1142    }
1143
1144    if new_sparse_indices.is_empty() {
1145        return Ok(None);
1146    }
1147
1148    let new_sparse_indices = new_sparse_indices.into_array();
1149    let values_validity =
1150        Validity::from_mask(take_validity, take_nullability).take(&new_sparse_indices)?;
1151    Ok(Some((
1152        new_sparse_indices,
1153        PrimitiveArray::new(value_indices, values_validity).into_array(),
1154    )))
1155}
1156
1157/// Filter patches with the provided mask (in flattened space).
1158///
1159/// The filter mask may contain indices that are non-patched. The return value of this function
1160/// is a new set of `Patches` with the indices relative to the provided `mask` rank, and the
1161/// patch values.
1162///
1163/// We search the larger side for each element of the smaller side, without building the mask
1164/// indices:
1165///
1166/// * More patches than mask indices: gallop through the patches.
1167/// * Cached mask indices: gallop through the mask indices.
1168/// * Otherwise: rank each patch in the mask bitmap.
1169fn filter_patches_with_mask<T: IntegerPType>(
1170    patch_indices: &[T],
1171    offset: usize,
1172    patch_values: &ArrayRef,
1173    mask: &MaskValues,
1174    allocator: &BufferAllocatorRef,
1175) -> VortexResult<Option<Patches>> {
1176    let true_count = mask.true_count();
1177    let patch_count = patch_indices.len();
1178    let expected_matches = true_count.min(patch_count);
1179
1180    // The mask rank of each kept patch, and a bitmap over the original patches marking them.
1181    let mut new_patch_indices =
1182        BufferMut::<u64>::with_capacity_in(expected_matches, allocator.clone());
1183    let mut kept_patches = BitBufferMut::from_buffer(
1184        BufferMut::zeroed_in(patch_count.div_ceil(8), allocator.clone()),
1185        0,
1186        patch_count,
1187    );
1188
1189    if patch_count > true_count {
1190        gallop_patches_for_mask_indices(
1191            patch_indices,
1192            offset,
1193            mask,
1194            &mut new_patch_indices,
1195            &mut kept_patches,
1196        )?;
1197    } else {
1198        match mask.cached_indices() {
1199            Some(mask_indices) => gallop_mask_indices_for_patches(
1200                patch_indices,
1201                offset,
1202                mask_indices,
1203                &mut new_patch_indices,
1204                &mut kept_patches,
1205            )?,
1206            None => rank_patches_in_mask_bitmap(
1207                patch_indices,
1208                offset,
1209                mask.bit_buffer(),
1210                &mut new_patch_indices,
1211                &mut kept_patches,
1212            )?,
1213        }
1214    }
1215
1216    let new_patch_values = match new_patch_indices.len() {
1217        0 => return Ok(None),
1218        kept if kept == patch_count => patch_values.clone(),
1219        _ => patch_values.filter(Mask::from_buffer(kept_patches.freeze()))?,
1220    };
1221    let new_patch_indices = new_patch_indices.into_array();
1222
1223    // SAFETY: there is one index and one value per kept patch. The indices are strictly
1224    // increasing non-nullable `u64` mask ranks below `true_count`.
1225    Ok(Some(unsafe {
1226        Patches::new_unchecked(
1227            true_count,
1228            0,
1229            new_patch_indices,
1230            new_patch_values,
1231            // TODO(0ax1): Chunk offsets are invalid after a filter is applied.
1232            None,
1233            None,
1234        )
1235    }))
1236}
1237
1238/// Returns the first position at or after `start` whose value is not less than `needle`.
1239///
1240/// The cost is logarithmic in the distance from `start` to the result.
1241fn gallop_lower_bound<T: Ord>(values: &[T], start: usize, needle: &T) -> usize {
1242    let mut low = start;
1243    let mut high = start;
1244    let mut step = 1;
1245
1246    while high < values.len() && values[high] < *needle {
1247        low = high + 1;
1248        high += step;
1249        step *= 2;
1250    }
1251
1252    let high = high.min(values.len());
1253    low + values[low..high].partition_point(|value| value < needle)
1254}
1255
1256/// Finds the patch of each mask index, for masks that are sparser than the patches.
1257///
1258/// Mask indices after the last patch cannot match, so we skip them.
1259fn gallop_patches_for_mask_indices<T: IntegerPType>(
1260    patch_indices: &[T],
1261    offset: usize,
1262    mask: &MaskValues,
1263    new_patch_indices: &mut BufferMut<u64>,
1264    kept_patches: &mut BitBufferMut,
1265) -> VortexResult<()> {
1266    let Some(&last_patch_index) = patch_indices.last() else {
1267        return Ok(());
1268    };
1269    let last_mask_index = patch_index_to_usize(last_patch_index, offset)?;
1270
1271    let mut patch_position = 0;
1272    let mut mask_position = 0;
1273
1274    let mut visit = |mask_index: usize| {
1275        // At most the last patch index, so it fits in `T` and the search stays in bounds.
1276        let needle = <T as NumCast>::from(mask_index + offset)
1277            .vortex_expect("mask index is at most the last patch index");
1278
1279        patch_position = gallop_lower_bound(patch_indices, patch_position, &needle);
1280        if patch_indices[patch_position] == needle {
1281            new_patch_indices.push(mask_position as u64);
1282            kept_patches.set(patch_position);
1283            patch_position += 1;
1284        }
1285
1286        mask_position += 1;
1287    };
1288
1289    match mask.cached_indices() {
1290        Some(mask_indices) => {
1291            let end = mask_indices.partition_point(|&mask_index| mask_index <= last_mask_index);
1292            mask_indices[..end]
1293                .iter()
1294                .for_each(|&mask_index| visit(mask_index));
1295        }
1296        None => mask
1297            .bit_buffer()
1298            .slice(..=last_mask_index)
1299            .for_each_set_index(visit),
1300    }
1301
1302    Ok(())
1303}
1304
1305/// Finds the mask position of each patch, for patches that are not sparser than the mask.
1306fn gallop_mask_indices_for_patches<T: IntegerPType>(
1307    patch_indices: &[T],
1308    offset: usize,
1309    mask_indices: &[usize],
1310    new_patch_indices: &mut BufferMut<u64>,
1311    kept_patches: &mut BitBufferMut,
1312) -> VortexResult<()> {
1313    let mut mask_position = 0;
1314
1315    for (patch_position, patch_index) in patch_indices.iter().enumerate() {
1316        let index = patch_index_to_usize(*patch_index, offset)?;
1317
1318        mask_position = gallop_lower_bound(mask_indices, mask_position, &index);
1319        if mask_position == mask_indices.len() {
1320            break;
1321        }
1322
1323        if mask_indices[mask_position] == index {
1324            new_patch_indices.push(mask_position as u64);
1325            kept_patches.set(patch_position);
1326            mask_position += 1;
1327        }
1328    }
1329
1330    Ok(())
1331}
1332
1333/// Finds the mask position of each patch from the mask bitmap, without building the mask indices.
1334///
1335/// The mask position is the number of set bits before the patch, counted between adjacent patches.
1336fn rank_patches_in_mask_bitmap<T: IntegerPType>(
1337    patch_indices: &[T],
1338    offset: usize,
1339    mask: &BitBuffer,
1340    new_patch_indices: &mut BufferMut<u64>,
1341    kept_patches: &mut BitBufferMut,
1342) -> VortexResult<()> {
1343    let mut rank = 0;
1344    let mut previous_index = 0;
1345
1346    for (patch_position, patch_index) in patch_indices.iter().enumerate() {
1347        let index = patch_index_to_usize(*patch_index, offset)?;
1348
1349        rank += mask.count_range(previous_index, index);
1350        previous_index = index;
1351
1352        if mask.value(index) {
1353            new_patch_indices.push(rank as u64);
1354            kept_patches.set(patch_position);
1355        }
1356    }
1357
1358    Ok(())
1359}
1360
1361#[inline]
1362fn patch_index_to_usize<T: IntegerPType>(patch_index: T, offset: usize) -> VortexResult<usize> {
1363    Ok(patch_index
1364        .to_usize()
1365        .ok_or_else(|| vortex_err!("patch index does not fit in usize"))?
1366        - offset)
1367}
1368
1369fn take_indices_with_search_fn<
1370    I: UnsignedPType,
1371    T: IntegerPType,
1372    F: Fn(I) -> VortexResult<SearchResult>,
1373>(
1374    indices: &[I],
1375    take_indices: &[T],
1376    take_validity: Mask,
1377    include_nulls: bool,
1378    allocator: &BufferAllocatorRef,
1379    search_fn: F,
1380) -> VortexResult<(BufferMut<u64>, BufferMut<u64>)> {
1381    let mut values_indices = BufferMut::with_capacity_in(take_indices.len(), allocator.clone());
1382    let mut new_indices = BufferMut::with_capacity_in(take_indices.len(), allocator.clone());
1383
1384    for (new_patch_idx, &take_idx) in take_indices.iter().enumerate() {
1385        if !take_validity.value(new_patch_idx) {
1386            if include_nulls {
1387                // For nulls, patch index doesn't matter - use 0 for consistency
1388                values_indices.push(0u64);
1389                new_indices.push(new_patch_idx as u64);
1390            }
1391            continue;
1392        } else {
1393            let search_result = match I::from(take_idx) {
1394                Some(idx) => search_fn(idx)?,
1395                None => SearchResult::NotFound(indices.len()),
1396            };
1397
1398            if let Some(patch_idx) = search_result.to_found() {
1399                values_indices.push(patch_idx as u64);
1400                new_indices.push(new_patch_idx as u64);
1401            }
1402        }
1403    }
1404
1405    Ok((values_indices, new_indices))
1406}
1407
1408#[cfg(test)]
1409mod test {
1410    use std::ops::Range;
1411    use std::sync::LazyLock;
1412
1413    use rstest::rstest;
1414    use vortex_buffer::BitBuffer;
1415    use vortex_buffer::Buffer;
1416    use vortex_buffer::BufferMut;
1417    use vortex_buffer::buffer;
1418    use vortex_error::VortexExpect;
1419    use vortex_error::VortexResult;
1420    use vortex_mask::Mask;
1421    use vortex_session::VortexSession;
1422
1423    use crate::IntoArray;
1424    use crate::VortexSessionExecute;
1425    use crate::assert_arrays_eq;
1426    use crate::dtype::PType;
1427    use crate::patches::Patches;
1428    use crate::patches::PatchesMetadata;
1429    use crate::patches::PrimitiveArray;
1430    use crate::search_sorted::SearchResult;
1431    use crate::validity::Validity;
1432
1433    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
1434
1435    #[rstest]
1436    #[case::unchunked(false)]
1437    #[case::chunked(true)]
1438    fn test_from_metadata_without_offset_within_chunk(#[case] chunked: bool) -> VortexResult<()> {
1439        let mut ctx = SESSION.create_execution_ctx();
1440        let metadata = PatchesMetadata::new(
1441            3,
1442            0,
1443            PType::U32,
1444            chunked.then_some(3),
1445            chunked.then_some(PType::U32),
1446            None,
1447        );
1448        let patches = Patches::from_metadata(
1449            3072,
1450            &metadata,
1451            buffer![7u32, 1029, 2051].into_array(),
1452            buffer![11i32, 22, 33].into_array(),
1453            chunked.then(|| buffer![0u32, 1, 2].into_array()),
1454            &mut ctx,
1455        )?;
1456
1457        assert_eq!(patches.offset_within_chunk(), chunked.then_some(0));
1458        assert_eq!(
1459            patches.search_index(1029, &mut ctx)?,
1460            SearchResult::Found(1)
1461        );
1462        Ok(())
1463    }
1464
1465    #[rstest]
1466    fn test_from_metadata_rejects_inconsistent_chunk_offset(
1467        #[values(0, 2, 3, 501, usize::MAX)] offset_within_chunk: usize,
1468    ) {
1469        let mut ctx = SESSION.create_execution_ctx();
1470        // The original first chunk had patches at 100 and 500; slicing at 500 removed one.
1471        let metadata = PatchesMetadata::new(
1472            2,
1473            500,
1474            PType::U32,
1475            Some(2),
1476            Some(PType::U32),
1477            Some(offset_within_chunk),
1478        );
1479        let error = Patches::from_metadata(
1480            1000,
1481            &metadata,
1482            buffer![500u32, 1200].into_array(),
1483            buffer![11i32, 22].into_array(),
1484            Some(buffer![0u32, 2].into_array()),
1485            &mut ctx,
1486        )
1487        .expect_err("inconsistent patch offset must be rejected");
1488        assert!(error.to_string().contains("Patch offset within chunk"));
1489    }
1490
1491    #[rstest]
1492    #[case::single_chunk(900..901)]
1493    #[case::later_single_chunk(1500..1501)]
1494    #[case::multiple_chunks(900..2050)]
1495    fn test_from_metadata_short_slice(#[case] range: Range<usize>) -> VortexResult<()> {
1496        let mut ctx = SESSION.create_execution_ctx();
1497        let indices = PrimitiveArray::from_iter(0u32..3072).into_array();
1498        let patches = Patches::new(
1499            3072,
1500            0,
1501            indices.clone(),
1502            indices,
1503            Some(buffer![0u32, 1024, 2048].into_array()),
1504            &mut ctx,
1505        )?;
1506        let sliced = patches.slice(range, &mut ctx)?.expect("slice has patches");
1507        let metadata = sliced.to_metadata(sliced.array_len(), sliced.dtype())?;
1508        let read = Patches::from_metadata(
1509            sliced.array_len(),
1510            &metadata,
1511            sliced.indices().clone(),
1512            sliced.values().clone(),
1513            sliced.chunk_offsets().clone(),
1514            &mut ctx,
1515        )?;
1516
1517        assert_eq!(read.offset_within_chunk(), sliced.offset_within_chunk());
1518        assert_eq!(read.search_index(0, &mut ctx)?, SearchResult::Found(0));
1519        assert_arrays_eq!(read.values(), sliced.values(), &mut ctx);
1520        Ok(())
1521    }
1522
1523    #[cfg(debug_assertions)]
1524    #[test]
1525    #[should_panic(expected = "Patch indices must be strictly increasing")]
1526    fn test_new_rejects_repeated_indices() {
1527        let mut ctx = SESSION.create_execution_ctx();
1528        Patches::new(
1529            5,
1530            0,
1531            buffer![1u32, 1].into_array(),
1532            buffer![10i32, 20].into_array(),
1533            None,
1534            &mut ctx,
1535        )
1536        .unwrap();
1537    }
1538
1539    #[test]
1540    fn test_filter() {
1541        let mut ctx = SESSION.create_execution_ctx();
1542        let patches = Patches::new(
1543            100,
1544            0,
1545            buffer![10u32, 11, 20].into_array(),
1546            buffer![100, 110, 200].into_array(),
1547            None,
1548            &mut ctx,
1549        )
1550        .unwrap();
1551
1552        let filtered = patches
1553            .filter(&Mask::from_indices(100, vec![10, 20, 30]), &mut ctx)
1554            .unwrap()
1555            .unwrap();
1556
1557        assert_arrays_eq!(
1558            filtered.indices(),
1559            PrimitiveArray::from_iter([0u64, 1]),
1560            &mut ctx
1561        );
1562        assert_arrays_eq!(
1563            filtered.values(),
1564            PrimitiveArray::from_iter([100i32, 200]),
1565            &mut ctx
1566        );
1567    }
1568
1569    #[test]
1570    fn take_with_nulls() {
1571        let mut ctx = SESSION.create_execution_ctx();
1572        let patches = Patches::new(
1573            20,
1574            0,
1575            buffer![2u64, 9, 15].into_array(),
1576            PrimitiveArray::new(buffer![33_i32, 44, 55], Validity::AllValid).into_array(),
1577            None,
1578            &mut ctx,
1579        )
1580        .unwrap();
1581
1582        let taken = patches
1583            .take(
1584                &PrimitiveArray::new(buffer![9, 0], Validity::from_iter(vec![true, false]))
1585                    .into_array(),
1586                &mut ctx,
1587            )
1588            .unwrap()
1589            .unwrap();
1590        let values = taken.values();
1591        let primitive_indices = taken.indices();
1592        assert_eq!(taken.array_len(), 2);
1593        assert_arrays_eq!(
1594            values,
1595            PrimitiveArray::from_option_iter([Some(44i32)]),
1596            &mut ctx
1597        );
1598        assert_arrays_eq!(
1599            primitive_indices,
1600            PrimitiveArray::from_iter([0u64]),
1601            &mut ctx
1602        );
1603        assert_eq!(
1604            values
1605                .validity()
1606                .unwrap()
1607                .execute_mask(values.len(), &mut ctx)
1608                .unwrap(),
1609            Mask::from_iter(vec![true])
1610        );
1611    }
1612
1613    #[test]
1614    fn take_search_with_nulls_chunked() {
1615        let mut ctx = SESSION.create_execution_ctx();
1616        let patches = Patches::new(
1617            20,
1618            0,
1619            buffer![2u64, 9, 15].into_array(),
1620            buffer![33_i32, 44, 55].into_array(),
1621            Some(buffer![0u64].into_array()),
1622            &mut ctx,
1623        )
1624        .unwrap();
1625
1626        let taken = patches
1627            .take_search(
1628                PrimitiveArray::new(buffer![9, 0], Validity::from_iter([true, false])),
1629                true,
1630                &mut ctx,
1631            )
1632            .unwrap()
1633            .unwrap();
1634
1635        let values = taken.values();
1636        assert_eq!(taken.array_len(), 2);
1637        assert_arrays_eq!(
1638            values,
1639            PrimitiveArray::from_option_iter([Some(44i32), None]),
1640            &mut ctx
1641        );
1642        assert_arrays_eq!(
1643            taken.indices(),
1644            PrimitiveArray::from_iter([0u64, 1]),
1645            &mut ctx
1646        );
1647
1648        assert_eq!(
1649            values
1650                .validity()
1651                .unwrap()
1652                .execute_mask(values.len(), &mut ctx)
1653                .unwrap(),
1654            Mask::from_iter([true, false])
1655        );
1656    }
1657
1658    #[test]
1659    fn take_search_chunked_multiple_chunks() {
1660        let mut ctx = SESSION.create_execution_ctx();
1661        let patches = Patches::new(
1662            2048,
1663            0,
1664            buffer![100u64, 500, 1200, 1800].into_array(),
1665            buffer![10_i32, 20, 30, 40].into_array(),
1666            Some(buffer![0u64, 2].into_array()),
1667            &mut ctx,
1668        )
1669        .unwrap();
1670
1671        let taken = patches
1672            .take_search(
1673                PrimitiveArray::new(buffer![500, 1200, 999], Validity::AllValid),
1674                true,
1675                &mut ctx,
1676            )
1677            .unwrap()
1678            .unwrap();
1679
1680        assert_eq!(taken.array_len(), 3);
1681        assert_arrays_eq!(
1682            taken.values(),
1683            PrimitiveArray::from_option_iter([Some(20i32), Some(30)]),
1684            &mut ctx
1685        );
1686        assert_arrays_eq!(
1687            taken.indices(),
1688            PrimitiveArray::from_iter([0u64, 1]),
1689            &mut ctx
1690        );
1691    }
1692
1693    #[test]
1694    fn take_search_chunked_indices_with_no_patches() {
1695        let mut ctx = SESSION.create_execution_ctx();
1696        let patches = Patches::new(
1697            20,
1698            0,
1699            buffer![2u64, 9, 15].into_array(),
1700            buffer![33_i32, 44, 55].into_array(),
1701            Some(buffer![0u64].into_array()),
1702            &mut ctx,
1703        )
1704        .unwrap();
1705
1706        let taken = patches
1707            .take_search(
1708                PrimitiveArray::new(buffer![3, 4, 5], Validity::AllValid),
1709                true,
1710                &mut ctx,
1711            )
1712            .unwrap();
1713
1714        assert!(taken.is_none());
1715    }
1716
1717    #[test]
1718    fn take_search_chunked_interleaved() {
1719        let mut ctx = SESSION.create_execution_ctx();
1720        let patches = Patches::new(
1721            30,
1722            0,
1723            buffer![5u64, 10, 20, 25].into_array(),
1724            buffer![100_i32, 200, 300, 400].into_array(),
1725            Some(buffer![0u64].into_array()),
1726            &mut ctx,
1727        )
1728        .unwrap();
1729
1730        let taken = patches
1731            .take_search(
1732                PrimitiveArray::new(buffer![10, 15, 20, 99], Validity::AllValid),
1733                true,
1734                &mut ctx,
1735            )
1736            .unwrap()
1737            .unwrap();
1738
1739        assert_eq!(taken.array_len(), 4);
1740        assert_arrays_eq!(
1741            taken.values(),
1742            PrimitiveArray::from_option_iter([Some(200i32), Some(300)]),
1743            &mut ctx
1744        );
1745        assert_arrays_eq!(
1746            taken.indices(),
1747            PrimitiveArray::from_iter([0u64, 2]),
1748            &mut ctx
1749        );
1750    }
1751
1752    #[test]
1753    fn test_take_search_multiple_chunk_offsets() {
1754        let mut ctx = SESSION.create_execution_ctx();
1755        let patches = Patches::new(
1756            1500,
1757            0,
1758            BufferMut::from_iter(0..1500u64).into_array(),
1759            BufferMut::from_iter(0..1500i32).into_array(),
1760            Some(buffer![0u64, 1024u64].into_array()),
1761            &mut ctx,
1762        )
1763        .unwrap();
1764
1765        let taken = patches
1766            .take_search(
1767                PrimitiveArray::new(BufferMut::from_iter(0..1500u64), Validity::AllValid),
1768                false,
1769                &mut ctx,
1770            )
1771            .unwrap()
1772            .unwrap();
1773
1774        assert_eq!(taken.array_len(), 1500);
1775        assert_arrays_eq!(
1776            taken.indices(),
1777            PrimitiveArray::from_iter(0..1500u64),
1778            &mut ctx
1779        );
1780        assert_arrays_eq!(
1781            taken.values(),
1782            PrimitiveArray::from_option_iter((0..1500i32).map(Some)),
1783            &mut ctx
1784        );
1785    }
1786
1787    #[test]
1788    fn doubly_sliced() {
1789        let mut ctx = SESSION.create_execution_ctx();
1790        let values = buffer![15_u32, 135, 13531, 42].into_array();
1791        let indices = buffer![10_u64, 11, 50, 100].into_array();
1792
1793        let patches = Patches::new(101, 0, indices, values, None, &mut ctx).unwrap();
1794
1795        let sliced = patches.slice(15..100, &mut ctx).unwrap().unwrap();
1796        assert_eq!(sliced.array_len(), 100 - 15);
1797        assert_arrays_eq!(
1798            sliced.values(),
1799            PrimitiveArray::from_iter([13531u32]),
1800            &mut ctx
1801        );
1802
1803        assert_eq!(sliced.offset(), 15);
1804        assert_arrays_eq!(
1805            sliced.indices(),
1806            PrimitiveArray::from_iter([50u64]),
1807            &mut ctx
1808        );
1809        let doubly_sliced = sliced.slice(35..36, &mut ctx).unwrap().unwrap();
1810        assert_eq!(doubly_sliced.array_len(), 1);
1811        assert_eq!(doubly_sliced.offset(), 50);
1812        assert_eq!(
1813            doubly_sliced.search_index(0, &mut ctx).unwrap(),
1814            SearchResult::Found(0)
1815        );
1816        assert_arrays_eq!(
1817            doubly_sliced.values(),
1818            PrimitiveArray::from_iter([13531u32]),
1819            &mut ctx
1820        );
1821    }
1822
1823    #[test]
1824    fn test_mask_all_true() {
1825        let mut ctx = SESSION.create_execution_ctx();
1826        let patches = Patches::new(
1827            10,
1828            0,
1829            buffer![2u64, 5, 8].into_array(),
1830            buffer![100i32, 200, 300].into_array(),
1831            None,
1832            &mut ctx,
1833        )
1834        .unwrap();
1835
1836        let mask = Mask::new_true(10);
1837        let masked = patches.mask(&mask, &mut ctx).unwrap();
1838        assert!(masked.is_none());
1839    }
1840
1841    #[test]
1842    fn test_mask_all_false() {
1843        let mut ctx = SESSION.create_execution_ctx();
1844        let patches = Patches::new(
1845            10,
1846            0,
1847            buffer![2u64, 5, 8].into_array(),
1848            buffer![100i32, 200, 300].into_array(),
1849            None,
1850            &mut ctx,
1851        )
1852        .unwrap();
1853
1854        let mask = Mask::new_false(10);
1855        let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
1856
1857        // Masking widens the surviving (still valid) values to nullable.
1858        assert!(masked.values().dtype().is_nullable());
1859        assert_arrays_eq!(
1860            masked.values(),
1861            PrimitiveArray::from_option_iter([Some(100i32), Some(200), Some(300)]),
1862            &mut ctx
1863        );
1864        assert!(masked.values().is_valid(0, &mut ctx).unwrap());
1865        assert!(masked.values().is_valid(1, &mut ctx).unwrap());
1866        assert!(masked.values().is_valid(2, &mut ctx).unwrap());
1867
1868        // Indices should remain unchanged
1869        assert_arrays_eq!(
1870            masked.indices(),
1871            PrimitiveArray::from_iter([2u64, 5, 8]),
1872            &mut ctx
1873        );
1874    }
1875
1876    #[test]
1877    fn test_mask_partial() {
1878        let mut ctx = SESSION.create_execution_ctx();
1879        let patches = Patches::new(
1880            10,
1881            0,
1882            buffer![2u64, 5, 8].into_array(),
1883            buffer![100i32, 200, 300].into_array(),
1884            None,
1885            &mut ctx,
1886        )
1887        .unwrap();
1888
1889        // Mask that removes patches at indices 2 and 8 (but not 5)
1890        let mask = Mask::from_iter([
1891            false, false, true, false, false, false, false, false, true, false,
1892        ]);
1893        let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
1894
1895        // Only the patch at index 5 should remain
1896        assert_eq!(masked.values().len(), 1);
1897        assert_arrays_eq!(
1898            masked.values(),
1899            PrimitiveArray::from_option_iter([Some(200i32)]),
1900            &mut ctx
1901        );
1902
1903        // Only index 5 should remain
1904        assert_arrays_eq!(
1905            masked.indices(),
1906            PrimitiveArray::from_iter([5u64]),
1907            &mut ctx
1908        );
1909    }
1910
1911    #[test]
1912    fn test_mask_with_offset() {
1913        let mut ctx = SESSION.create_execution_ctx();
1914        let patches = Patches::new(
1915            10,
1916            5,                                  // offset
1917            buffer![7u64, 10, 13].into_array(), // actual indices are 2, 5, 8
1918            buffer![100i32, 200, 300].into_array(),
1919            None,
1920            &mut ctx,
1921        )
1922        .unwrap();
1923
1924        // Mask that sets actual index 2 to null
1925        let mask = Mask::from_iter([
1926            false, false, true, false, false, false, false, false, false, false,
1927        ]);
1928
1929        let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
1930        assert_eq!(masked.array_len(), 10);
1931        assert_eq!(masked.offset(), 5);
1932        assert_arrays_eq!(
1933            masked.indices(),
1934            PrimitiveArray::from_iter([10u64, 13]),
1935            &mut ctx
1936        );
1937        assert_arrays_eq!(
1938            masked.values(),
1939            PrimitiveArray::from_option_iter([Some(200i32), Some(300)]),
1940            &mut ctx
1941        );
1942    }
1943
1944    #[test]
1945    fn test_mask_nullable_values() {
1946        let mut ctx = SESSION.create_execution_ctx();
1947        let patches = Patches::new(
1948            10,
1949            0,
1950            buffer![2u64, 5, 8].into_array(),
1951            PrimitiveArray::from_option_iter([Some(100i32), None, Some(300)]).into_array(),
1952            None,
1953            &mut ctx,
1954        )
1955        .unwrap();
1956
1957        // Test masking removes patch at index 2
1958        let mask = Mask::from_iter([
1959            false, false, true, false, false, false, false, false, false, false,
1960        ]);
1961        let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
1962
1963        // Patches at indices 5 and 8 should remain
1964        assert_arrays_eq!(
1965            masked.indices(),
1966            PrimitiveArray::from_iter([5u64, 8]),
1967            &mut ctx
1968        );
1969
1970        // Values should be the null and 300
1971        let masked_values = masked
1972            .values()
1973            .clone()
1974            .execute::<PrimitiveArray>(&mut ctx)
1975            .unwrap();
1976        assert_eq!(masked_values.len(), 2);
1977        assert!(!masked_values.is_valid(0, &mut ctx).unwrap()); // the null value at index 5
1978        assert!(masked_values.is_valid(1, &mut ctx).unwrap()); // the 300 value at index 8
1979        assert_eq!(
1980            i32::try_from(&masked_values.execute_scalar(1, &mut ctx).unwrap()).unwrap(),
1981            300i32
1982        );
1983    }
1984
1985    /// Covers each filter algorithm.
1986    #[rstest]
1987    #[case::sparse_mask((0..1000).step_by(2).collect(), (0..1000).step_by(97).collect())]
1988    #[case::sparse_patches((0..1000).step_by(97).collect(), (0..1000).step_by(2).collect())]
1989    #[case::similar_sizes((0..1000).step_by(3).collect(), (0..1000).step_by(2).collect())]
1990    #[case::no_overlap((0..500).collect(), (500..1000).step_by(50).collect())]
1991    #[case::no_overlap_sparse_patches((500..1000).step_by(100).collect(), (0..500).collect())]
1992    #[case::edges(vec![0, 1, 998, 999], vec![0, 999])]
1993    #[case::all_patches_kept((0..1000).step_by(100).collect(), (0..1000).step_by(2).collect())]
1994    fn test_filter_matches_naive(
1995        #[case] patch_indices: Vec<usize>,
1996        #[case] mask_indices: Vec<usize>,
1997        #[values(0, 5)] offset: usize,
1998        #[values(true, false)] cache_mask_indices: bool,
1999    ) -> VortexResult<()> {
2000        const LEN: usize = 1000;
2001        let mut ctx = SESSION.create_execution_ctx();
2002
2003        let patches = Patches::new(
2004            LEN,
2005            offset,
2006            patch_indices
2007                .iter()
2008                .map(|&index| u32::try_from(index + offset).vortex_expect("index fits in u32"))
2009                .collect::<Buffer<u32>>()
2010                .into_array(),
2011            (0i32..)
2012                .take(patch_indices.len())
2013                .collect::<Buffer<i32>>()
2014                .into_array(),
2015            None,
2016            &mut ctx,
2017        )?;
2018
2019        let mask = if cache_mask_indices {
2020            Mask::from_indices(LEN, mask_indices.iter().copied())
2021        } else {
2022            Mask::from_buffer(BitBuffer::from_iter(
2023                (0..LEN).map(|index| mask_indices.binary_search(&index).is_ok()),
2024            ))
2025        };
2026
2027        let (expected_indices, expected_values): (Vec<u64>, Vec<i32>) = mask_indices
2028            .iter()
2029            .enumerate()
2030            .filter_map(|(mask_position, index)| {
2031                patch_indices
2032                    .binary_search(index)
2033                    .ok()
2034                    .map(|patch_position| {
2035                        (
2036                            mask_position as u64,
2037                            i32::try_from(patch_position).vortex_expect("position fits in i32"),
2038                        )
2039                    })
2040            })
2041            .unzip();
2042
2043        let filtered = patches.filter(&mask, &mut ctx)?;
2044
2045        let Some(filtered) = filtered else {
2046            assert!(expected_indices.is_empty());
2047            return Ok(());
2048        };
2049
2050        assert_eq!(filtered.array_len(), mask_indices.len());
2051        assert_arrays_eq!(
2052            filtered.indices(),
2053            PrimitiveArray::from_iter(expected_indices),
2054            &mut ctx
2055        );
2056        assert_arrays_eq!(
2057            filtered.values(),
2058            PrimitiveArray::from_iter(expected_values),
2059            &mut ctx
2060        );
2061
2062        Ok(())
2063    }
2064
2065    /// Mask indices past the maximum of the patch index type cannot match a patch.
2066    #[test]
2067    fn test_filter_sparse_mask_past_index_type_max() -> VortexResult<()> {
2068        let mut ctx = SESSION.create_execution_ctx();
2069        let patches = Patches::new(
2070            1000,
2071            0,
2072            (0..=u8::MAX).collect::<Buffer<u8>>().into_array(),
2073            (0..256i32).collect::<Buffer<i32>>().into_array(),
2074            None,
2075            &mut ctx,
2076        )?;
2077
2078        let mask = Mask::from_indices(1000, [3, 255, 256, 900]);
2079        let filtered = patches
2080            .filter(&mask, &mut ctx)?
2081            .expect("patches at 3 and 255 are kept");
2082
2083        assert_arrays_eq!(
2084            filtered.indices(),
2085            PrimitiveArray::from_iter([0u64, 1]),
2086            &mut ctx
2087        );
2088        assert_arrays_eq!(
2089            filtered.values(),
2090            PrimitiveArray::from_iter([3i32, 255]),
2091            &mut ctx
2092        );
2093
2094        Ok(())
2095    }
2096
2097    #[test]
2098    fn test_filter_keep_all() {
2099        let mut ctx = SESSION.create_execution_ctx();
2100        let patches = Patches::new(
2101            10,
2102            0,
2103            buffer![2u64, 5, 8].into_array(),
2104            buffer![100i32, 200, 300].into_array(),
2105            None,
2106            &mut ctx,
2107        )
2108        .unwrap();
2109
2110        // Keep all indices (mask with indices 0-9)
2111        let mask = Mask::from_indices(10, 0..10);
2112        let filtered = patches.filter(&mask, &mut ctx).unwrap().unwrap();
2113
2114        assert_arrays_eq!(
2115            filtered.indices(),
2116            PrimitiveArray::from_iter([2u64, 5, 8]),
2117            &mut ctx
2118        );
2119        assert_arrays_eq!(
2120            filtered.values(),
2121            PrimitiveArray::from_iter([100i32, 200, 300]),
2122            &mut ctx
2123        );
2124    }
2125
2126    #[test]
2127    fn test_filter_none() {
2128        let mut ctx = SESSION.create_execution_ctx();
2129        let patches = Patches::new(
2130            10,
2131            0,
2132            buffer![2u64, 5, 8].into_array(),
2133            buffer![100i32, 200, 300].into_array(),
2134            None,
2135            &mut ctx,
2136        )
2137        .unwrap();
2138
2139        // Filter out all (empty mask means keep nothing)
2140        let mask = Mask::from_indices(10, vec![]);
2141        let filtered = patches.filter(&mask, &mut ctx).unwrap();
2142        assert!(filtered.is_none());
2143    }
2144
2145    #[test]
2146    fn test_filter_with_indices() {
2147        let mut ctx = SESSION.create_execution_ctx();
2148        let patches = Patches::new(
2149            10,
2150            0,
2151            buffer![2u64, 5, 8].into_array(),
2152            buffer![100i32, 200, 300].into_array(),
2153            None,
2154            &mut ctx,
2155        )
2156        .unwrap();
2157
2158        // Keep indices 2, 5, 9 (so patches at 2 and 5 remain)
2159        let mask = Mask::from_indices(10, vec![2, 5, 9]);
2160        let filtered = patches.filter(&mask, &mut ctx).unwrap().unwrap();
2161
2162        assert_arrays_eq!(
2163            filtered.indices(),
2164            PrimitiveArray::from_iter([0u64, 1]),
2165            &mut ctx
2166        ); // Adjusted indices
2167        assert_arrays_eq!(
2168            filtered.values(),
2169            PrimitiveArray::from_iter([100i32, 200]),
2170            &mut ctx
2171        );
2172    }
2173
2174    #[test]
2175    fn test_slice_full_range() {
2176        let mut ctx = SESSION.create_execution_ctx();
2177        let patches = Patches::new(
2178            10,
2179            0,
2180            buffer![2u64, 5, 8].into_array(),
2181            buffer![100i32, 200, 300].into_array(),
2182            None,
2183            &mut ctx,
2184        )
2185        .unwrap();
2186
2187        let sliced = patches.slice(0..10, &mut ctx).unwrap().unwrap();
2188
2189        assert_arrays_eq!(
2190            sliced.indices(),
2191            PrimitiveArray::from_iter([2u64, 5, 8]),
2192            &mut ctx
2193        );
2194        assert_arrays_eq!(
2195            sliced.values(),
2196            PrimitiveArray::from_iter([100i32, 200, 300]),
2197            &mut ctx
2198        );
2199    }
2200
2201    #[test]
2202    fn test_slice_partial() {
2203        let mut ctx = SESSION.create_execution_ctx();
2204        let patches = Patches::new(
2205            10,
2206            0,
2207            buffer![2u64, 5, 8].into_array(),
2208            buffer![100i32, 200, 300].into_array(),
2209            None,
2210            &mut ctx,
2211        )
2212        .unwrap();
2213
2214        // Slice from 3 to 8 (includes patch at 5)
2215        let sliced = patches.slice(3..8, &mut ctx).unwrap().unwrap();
2216
2217        assert_arrays_eq!(
2218            sliced.indices(),
2219            PrimitiveArray::from_iter([5u64]),
2220            &mut ctx
2221        ); // Index stays the same
2222        assert_arrays_eq!(
2223            sliced.values(),
2224            PrimitiveArray::from_iter([200i32]),
2225            &mut ctx
2226        );
2227        assert_eq!(sliced.array_len(), 5); // 8 - 3 = 5
2228        assert_eq!(sliced.offset(), 3); // New offset
2229    }
2230
2231    #[test]
2232    fn test_slice_no_patches() {
2233        let mut ctx = SESSION.create_execution_ctx();
2234        let patches = Patches::new(
2235            10,
2236            0,
2237            buffer![2u64, 5, 8].into_array(),
2238            buffer![100i32, 200, 300].into_array(),
2239            None,
2240            &mut ctx,
2241        )
2242        .unwrap();
2243
2244        // Slice from 6 to 7 (no patches in this range)
2245        let sliced = patches.slice(6..7, &mut ctx).unwrap();
2246        assert!(sliced.is_none());
2247    }
2248
2249    #[test]
2250    fn test_slice_with_offset() {
2251        let mut ctx = SESSION.create_execution_ctx();
2252        let patches = Patches::new(
2253            10,
2254            5,                                  // offset
2255            buffer![7u64, 10, 13].into_array(), // actual indices are 2, 5, 8
2256            buffer![100i32, 200, 300].into_array(),
2257            None,
2258            &mut ctx,
2259        )
2260        .unwrap();
2261
2262        // Slice from 3 to 8 (includes patch at actual index 5)
2263        let sliced = patches.slice(3..8, &mut ctx).unwrap().unwrap();
2264
2265        assert_arrays_eq!(
2266            sliced.indices(),
2267            PrimitiveArray::from_iter([10u64]),
2268            &mut ctx
2269        ); // Index stays the same (offset + 5 = 10)
2270        assert_arrays_eq!(
2271            sliced.values(),
2272            PrimitiveArray::from_iter([200i32]),
2273            &mut ctx
2274        );
2275        assert_eq!(sliced.offset(), 8); // New offset = 5 + 3
2276    }
2277
2278    #[test]
2279    fn test_indices_range() {
2280        let mut ctx = SESSION.create_execution_ctx();
2281        let patches = Patches::new(
2282            10,
2283            0,
2284            buffer![2u64, 5, 8].into_array(),
2285            buffer![100i32, 200, 300].into_array(),
2286            None,
2287            &mut ctx,
2288        )
2289        .unwrap();
2290
2291        assert_eq!(patches.min_index(&mut ctx).unwrap(), 2);
2292        assert_eq!(patches.max_index(&mut ctx).unwrap(), 8);
2293    }
2294
2295    #[test]
2296    fn test_search_index() {
2297        let mut ctx = SESSION.create_execution_ctx();
2298        let patches = Patches::new(
2299            10,
2300            0,
2301            buffer![2u64, 5, 8].into_array(),
2302            buffer![100i32, 200, 300].into_array(),
2303            None,
2304            &mut ctx,
2305        )
2306        .unwrap();
2307
2308        // Search for exact indices
2309        assert_eq!(
2310            patches.search_index(2, &mut ctx).unwrap(),
2311            SearchResult::Found(0)
2312        );
2313        assert_eq!(
2314            patches.search_index(5, &mut ctx).unwrap(),
2315            SearchResult::Found(1)
2316        );
2317        assert_eq!(
2318            patches.search_index(8, &mut ctx).unwrap(),
2319            SearchResult::Found(2)
2320        );
2321
2322        // Search for non-patch indices
2323        assert_eq!(
2324            patches.search_index(0, &mut ctx).unwrap(),
2325            SearchResult::NotFound(0)
2326        );
2327        assert_eq!(
2328            patches.search_index(3, &mut ctx).unwrap(),
2329            SearchResult::NotFound(1)
2330        );
2331        assert_eq!(
2332            patches.search_index(6, &mut ctx).unwrap(),
2333            SearchResult::NotFound(2)
2334        );
2335        assert_eq!(
2336            patches.search_index(9, &mut ctx).unwrap(),
2337            SearchResult::NotFound(3)
2338        );
2339    }
2340
2341    #[test]
2342    fn test_mask_boundary_patches() {
2343        let mut ctx = SESSION.create_execution_ctx();
2344        // Test masking patches at array boundaries
2345        let patches = Patches::new(
2346            10,
2347            0,
2348            buffer![0u64, 9].into_array(),
2349            buffer![100i32, 200].into_array(),
2350            None,
2351            &mut ctx,
2352        )
2353        .unwrap();
2354
2355        let mask = Mask::from_iter([
2356            true, false, false, false, false, false, false, false, false, false,
2357        ]);
2358        let masked = patches.mask(&mask, &mut ctx).unwrap();
2359        assert!(masked.is_some());
2360        let masked = masked.unwrap();
2361        assert_arrays_eq!(
2362            masked.indices(),
2363            PrimitiveArray::from_iter([9u64]),
2364            &mut ctx
2365        );
2366        assert_arrays_eq!(
2367            masked.values(),
2368            PrimitiveArray::from_option_iter([Some(200i32)]),
2369            &mut ctx
2370        );
2371    }
2372
2373    #[test]
2374    fn test_mask_all_patches_removed() {
2375        let mut ctx = SESSION.create_execution_ctx();
2376        // Test when all patches are masked out
2377        let patches = Patches::new(
2378            10,
2379            0,
2380            buffer![2u64, 5, 8].into_array(),
2381            buffer![100i32, 200, 300].into_array(),
2382            None,
2383            &mut ctx,
2384        )
2385        .unwrap();
2386
2387        // Mask that removes all patches
2388        let mask = Mask::from_iter([
2389            false, false, true, false, false, true, false, false, true, false,
2390        ]);
2391        let masked = patches.mask(&mask, &mut ctx).unwrap();
2392        assert!(masked.is_none());
2393    }
2394
2395    #[test]
2396    fn test_mask_no_patches_removed() {
2397        let mut ctx = SESSION.create_execution_ctx();
2398        // Test when no patches are masked
2399        let patches = Patches::new(
2400            10,
2401            0,
2402            buffer![2u64, 5, 8].into_array(),
2403            buffer![100i32, 200, 300].into_array(),
2404            None,
2405            &mut ctx,
2406        )
2407        .unwrap();
2408
2409        // Mask that doesn't affect any patches
2410        let mask = Mask::from_iter([
2411            true, false, false, true, false, false, true, false, false, true,
2412        ]);
2413        let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
2414
2415        assert_arrays_eq!(
2416            masked.indices(),
2417            PrimitiveArray::from_iter([2u64, 5, 8]),
2418            &mut ctx
2419        );
2420        assert_arrays_eq!(
2421            masked.values(),
2422            PrimitiveArray::from_option_iter([Some(100i32), Some(200), Some(300)]),
2423            &mut ctx
2424        );
2425    }
2426
2427    #[test]
2428    fn test_mask_single_patch() {
2429        let mut ctx = SESSION.create_execution_ctx();
2430        // Test with a single patch
2431        let patches = Patches::new(
2432            5,
2433            0,
2434            buffer![2u64].into_array(),
2435            buffer![42i32].into_array(),
2436            None,
2437            &mut ctx,
2438        )
2439        .unwrap();
2440
2441        // Mask that removes the single patch
2442        let mask = Mask::from_iter([false, false, true, false, false]);
2443        let masked = patches.mask(&mask, &mut ctx).unwrap();
2444        assert!(masked.is_none());
2445
2446        // Mask that keeps the single patch
2447        let mask = Mask::from_iter([true, false, false, true, false]);
2448        let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
2449        assert_arrays_eq!(
2450            masked.indices(),
2451            PrimitiveArray::from_iter([2u64]),
2452            &mut ctx
2453        );
2454        assert_arrays_eq!(
2455            masked.values(),
2456            PrimitiveArray::from_option_iter([Some(42i32)]),
2457            &mut ctx
2458        );
2459    }
2460
2461    #[test]
2462    fn test_mask_contiguous_patches() {
2463        let mut ctx = SESSION.create_execution_ctx();
2464        // Test with contiguous patches
2465        let patches = Patches::new(
2466            10,
2467            0,
2468            buffer![3u64, 4, 5, 6].into_array(),
2469            buffer![100i32, 200, 300, 400].into_array(),
2470            None,
2471            &mut ctx,
2472        )
2473        .unwrap();
2474
2475        // Mask that removes middle patches
2476        let mask = Mask::from_iter([
2477            false, false, false, false, true, true, false, false, false, false,
2478        ]);
2479        let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
2480
2481        assert_arrays_eq!(
2482            masked.indices(),
2483            PrimitiveArray::from_iter([3u64, 6]),
2484            &mut ctx
2485        );
2486        assert_arrays_eq!(
2487            masked.values(),
2488            PrimitiveArray::from_option_iter([Some(100i32), Some(400)]),
2489            &mut ctx
2490        );
2491    }
2492
2493    #[test]
2494    fn test_mask_with_large_offset() {
2495        let mut ctx = SESSION.create_execution_ctx();
2496        // Test with a large offset that shifts all indices
2497        let patches = Patches::new(
2498            20,
2499            15,
2500            buffer![16u64, 17, 19].into_array(), // actual indices are 1, 2, 4
2501            buffer![100i32, 200, 300].into_array(),
2502            None,
2503            &mut ctx,
2504        )
2505        .unwrap();
2506
2507        // Mask that removes the patch at actual index 2
2508        let mask = Mask::from_iter([
2509            false, false, true, false, false, false, false, false, false, false, false, false,
2510            false, false, false, false, false, false, false, false,
2511        ]);
2512        let masked = patches.mask(&mask, &mut ctx).unwrap().unwrap();
2513
2514        assert_arrays_eq!(
2515            masked.indices(),
2516            PrimitiveArray::from_iter([16u64, 19]),
2517            &mut ctx
2518        );
2519        assert_arrays_eq!(
2520            masked.values(),
2521            PrimitiveArray::from_option_iter([Some(100i32), Some(300)]),
2522            &mut ctx
2523        );
2524    }
2525
2526    #[test]
2527    #[should_panic(expected = "Filter mask length 5 does not match array length 10")]
2528    fn test_mask_wrong_length() {
2529        let mut ctx = SESSION.create_execution_ctx();
2530        let patches = Patches::new(
2531            10,
2532            0,
2533            buffer![2u64, 5, 8].into_array(),
2534            buffer![100i32, 200, 300].into_array(),
2535            None,
2536            &mut ctx,
2537        )
2538        .unwrap();
2539
2540        // Mask with wrong length
2541        let mask = Mask::from_iter([false, false, true, false, false]);
2542        patches.mask(&mask, &mut ctx).unwrap();
2543    }
2544
2545    #[test]
2546    fn test_chunk_offsets_search() {
2547        let mut ctx = SESSION.create_execution_ctx();
2548        let indices = buffer![100u64, 200, 3000, 3100].into_array();
2549        let values = buffer![10i32, 20, 30, 40].into_array();
2550        let chunk_offsets = buffer![0u64, 2, 2, 3].into_array();
2551        let patches =
2552            Patches::new(4096, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2553
2554        assert!(patches.chunk_offsets.is_some());
2555
2556        // chunk 0: patches at 100, 200
2557        assert_eq!(
2558            patches.search_index(100, &mut ctx).unwrap(),
2559            SearchResult::Found(0)
2560        );
2561        assert_eq!(
2562            patches.search_index(200, &mut ctx).unwrap(),
2563            SearchResult::Found(1)
2564        );
2565
2566        // Chunk 1 has no patches; 2000 is before the first patch in chunk 2.
2567        assert_eq!(
2568            patches.search_index(1500, &mut ctx).unwrap(),
2569            SearchResult::NotFound(2)
2570        );
2571        assert_eq!(
2572            patches.search_index(2000, &mut ctx).unwrap(),
2573            SearchResult::NotFound(2)
2574        );
2575
2576        // The patches at 3000 and 3100 straddle chunks 2 and 3.
2577        assert_eq!(
2578            patches.search_index(3000, &mut ctx).unwrap(),
2579            SearchResult::Found(2)
2580        );
2581        assert_eq!(
2582            patches.search_index(3100, &mut ctx).unwrap(),
2583            SearchResult::Found(3)
2584        );
2585
2586        assert_eq!(
2587            patches.search_index(1024, &mut ctx).unwrap(),
2588            SearchResult::NotFound(2)
2589        );
2590    }
2591
2592    #[test]
2593    fn test_chunk_offsets_with_slice() {
2594        let mut ctx = SESSION.create_execution_ctx();
2595        let indices = buffer![100u64, 500, 1200, 1300, 1500, 1800, 2100, 2500].into_array();
2596        let values = buffer![10i32, 20, 30, 35, 40, 45, 50, 60].into_array();
2597        let chunk_offsets = buffer![0u64, 2, 6].into_array();
2598        let patches =
2599            Patches::new(3000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2600
2601        let sliced = patches.slice(1000..2200, &mut ctx).unwrap().unwrap();
2602
2603        assert!(sliced.chunk_offsets.is_some());
2604        assert_eq!(sliced.offset(), 1000);
2605
2606        assert_eq!(
2607            sliced.search_index(200, &mut ctx).unwrap(),
2608            SearchResult::Found(0)
2609        );
2610        assert_eq!(
2611            sliced.search_index(500, &mut ctx).unwrap(),
2612            SearchResult::Found(2)
2613        );
2614        assert_eq!(
2615            sliced.search_index(1100, &mut ctx).unwrap(),
2616            SearchResult::Found(4)
2617        );
2618
2619        assert_eq!(
2620            sliced.search_index(250, &mut ctx).unwrap(),
2621            SearchResult::NotFound(1)
2622        );
2623        assert_arrays_eq!(
2624            sliced.values(),
2625            PrimitiveArray::from_iter([30i32, 35, 40, 45, 50]),
2626            &mut ctx
2627        );
2628    }
2629
2630    #[test]
2631    fn test_chunk_offsets_with_slice_after_first_chunk() {
2632        let mut ctx = SESSION.create_execution_ctx();
2633        let indices = buffer![100u64, 500, 1200, 1300, 1500, 1800, 2100, 2500].into_array();
2634        let values = buffer![10i32, 20, 30, 35, 40, 45, 50, 60].into_array();
2635        let chunk_offsets = buffer![0u64, 2, 6].into_array();
2636        let patches =
2637            Patches::new(3000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2638
2639        let sliced = patches.slice(1300..2200, &mut ctx).unwrap().unwrap();
2640
2641        assert!(sliced.chunk_offsets.is_some());
2642        assert_eq!(sliced.offset(), 1300);
2643
2644        assert_eq!(
2645            sliced.search_index(0, &mut ctx).unwrap(),
2646            SearchResult::Found(0)
2647        );
2648        assert_eq!(
2649            sliced.search_index(200, &mut ctx).unwrap(),
2650            SearchResult::Found(1)
2651        );
2652        assert_eq!(
2653            sliced.search_index(500, &mut ctx).unwrap(),
2654            SearchResult::Found(2)
2655        );
2656        assert_eq!(
2657            sliced.search_index(250, &mut ctx).unwrap(),
2658            SearchResult::NotFound(2)
2659        );
2660        assert_eq!(
2661            sliced.search_index(900, &mut ctx).unwrap(),
2662            SearchResult::NotFound(4)
2663        );
2664        assert_arrays_eq!(
2665            sliced.values(),
2666            PrimitiveArray::from_iter([35i32, 40, 45, 50]),
2667            &mut ctx
2668        );
2669    }
2670
2671    #[test]
2672    fn test_chunk_offsets_slice_empty_result() {
2673        let mut ctx = SESSION.create_execution_ctx();
2674        let indices = buffer![100u64, 200, 3000, 3100].into_array();
2675        let values = buffer![10i32, 20, 30, 40].into_array();
2676        let chunk_offsets = buffer![0u64, 2, 2, 3].into_array();
2677        let patches =
2678            Patches::new(4000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2679
2680        let sliced = patches.slice(1000..2000, &mut ctx).unwrap();
2681        assert!(sliced.is_none());
2682    }
2683
2684    #[test]
2685    fn test_chunk_offsets_slice_single_patch() {
2686        let mut ctx = SESSION.create_execution_ctx();
2687        let indices = buffer![100u64, 1200, 1300, 2500].into_array();
2688        let values = buffer![10i32, 20, 30, 40].into_array();
2689        let chunk_offsets = buffer![0u64, 1, 3].into_array();
2690        let patches =
2691            Patches::new(3000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2692
2693        let sliced = patches.slice(1100..1250, &mut ctx).unwrap().unwrap();
2694
2695        assert_eq!(sliced.num_patches(), 1);
2696        assert_eq!(sliced.offset(), 1100);
2697        assert_eq!(
2698            sliced.search_index(100, &mut ctx).unwrap(),
2699            SearchResult::Found(0)
2700        ); // 1200 - 1100 = 100
2701        assert_eq!(
2702            sliced.search_index(50, &mut ctx).unwrap(),
2703            SearchResult::NotFound(0)
2704        );
2705        assert_eq!(
2706            sliced.search_index(150, &mut ctx).unwrap(),
2707            SearchResult::NotFound(1)
2708        );
2709        assert_arrays_eq!(
2710            sliced.values(),
2711            PrimitiveArray::from_iter([20i32]),
2712            &mut ctx
2713        );
2714    }
2715
2716    #[test]
2717    fn test_chunk_offsets_slice_across_chunks() {
2718        let mut ctx = SESSION.create_execution_ctx();
2719        let indices = buffer![100u64, 200, 1100, 1200, 2100, 2200].into_array();
2720        let values = buffer![10i32, 20, 30, 40, 50, 60].into_array();
2721        let chunk_offsets = buffer![0u64, 2, 4].into_array();
2722        let patches =
2723            Patches::new(3000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2724
2725        let sliced = patches.slice(150..2150, &mut ctx).unwrap().unwrap();
2726
2727        assert_eq!(sliced.num_patches(), 4);
2728        assert_eq!(sliced.offset(), 150);
2729
2730        assert_eq!(
2731            sliced.search_index(50, &mut ctx).unwrap(),
2732            SearchResult::Found(0)
2733        ); // 200 - 150 = 50
2734        assert_eq!(
2735            sliced.search_index(950, &mut ctx).unwrap(),
2736            SearchResult::Found(1)
2737        ); // 1100 - 150 = 950
2738        assert_eq!(
2739            sliced.search_index(1050, &mut ctx).unwrap(),
2740            SearchResult::Found(2)
2741        ); // 1200 - 150 = 1050
2742        assert_eq!(
2743            sliced.search_index(1950, &mut ctx).unwrap(),
2744            SearchResult::Found(3)
2745        ); // 2100 - 150 = 1950
2746        assert_arrays_eq!(
2747            sliced.values(),
2748            PrimitiveArray::from_iter([20i32, 30, 40, 50]),
2749            &mut ctx
2750        );
2751    }
2752
2753    #[test]
2754    fn test_chunk_offsets_boundary_searches() {
2755        let mut ctx = SESSION.create_execution_ctx();
2756        let indices = buffer![1023u64, 1024, 1025, 2047, 2048].into_array();
2757        let values = buffer![10i32, 20, 30, 40, 50].into_array();
2758        let chunk_offsets = buffer![0u64, 1, 4].into_array();
2759        let patches =
2760            Patches::new(3000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2761
2762        assert_eq!(
2763            patches.search_index(1023, &mut ctx).unwrap(),
2764            SearchResult::Found(0)
2765        );
2766        assert_eq!(
2767            patches.search_index(1024, &mut ctx).unwrap(),
2768            SearchResult::Found(1)
2769        );
2770        assert_eq!(
2771            patches.search_index(1025, &mut ctx).unwrap(),
2772            SearchResult::Found(2)
2773        );
2774        assert_eq!(
2775            patches.search_index(2047, &mut ctx).unwrap(),
2776            SearchResult::Found(3)
2777        );
2778        assert_eq!(
2779            patches.search_index(2048, &mut ctx).unwrap(),
2780            SearchResult::Found(4)
2781        );
2782
2783        assert_eq!(
2784            patches.search_index(1022, &mut ctx).unwrap(),
2785            SearchResult::NotFound(0)
2786        );
2787        assert_eq!(
2788            patches.search_index(2046, &mut ctx).unwrap(),
2789            SearchResult::NotFound(3)
2790        );
2791    }
2792
2793    #[test]
2794    fn test_chunk_offsets_slice_edge_cases() {
2795        let mut ctx = SESSION.create_execution_ctx();
2796        let indices = buffer![0u64, 1, 1023, 1024, 2047, 2048].into_array();
2797        let values = buffer![10i32, 20, 30, 40, 50, 60].into_array();
2798        let chunk_offsets = buffer![0u64, 3, 5].into_array();
2799        let patches =
2800            Patches::new(3000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2801
2802        // Slice at the very beginning
2803        let sliced = patches.slice(0..10, &mut ctx).unwrap().unwrap();
2804        assert_eq!(sliced.num_patches(), 2);
2805        assert_eq!(
2806            sliced.search_index(0, &mut ctx).unwrap(),
2807            SearchResult::Found(0)
2808        );
2809        assert_eq!(
2810            sliced.search_index(1, &mut ctx).unwrap(),
2811            SearchResult::Found(1)
2812        );
2813
2814        assert_arrays_eq!(
2815            sliced.values(),
2816            PrimitiveArray::from_iter([10i32, 20]),
2817            &mut ctx
2818        );
2819
2820        // Slice at the very end
2821        let sliced = patches.slice(2040..3000, &mut ctx).unwrap().unwrap();
2822        assert_eq!(sliced.num_patches(), 2); // patches at 2047 and 2048
2823        assert_eq!(
2824            sliced.search_index(7, &mut ctx).unwrap(),
2825            SearchResult::Found(0)
2826        ); // 2047 - 2040
2827        assert_eq!(
2828            sliced.search_index(8, &mut ctx).unwrap(),
2829            SearchResult::Found(1)
2830        ); // 2048 - 2040
2831        assert_arrays_eq!(
2832            sliced.values(),
2833            PrimitiveArray::from_iter([50i32, 60]),
2834            &mut ctx
2835        );
2836    }
2837
2838    #[test]
2839    fn test_chunk_offsets_slice_nested() {
2840        let mut ctx = SESSION.create_execution_ctx();
2841        let indices = buffer![100u64, 200, 300, 400, 500, 600].into_array();
2842        let values = buffer![10i32, 20, 30, 40, 50, 60].into_array();
2843        let chunk_offsets = buffer![0u64].into_array();
2844        let patches =
2845            Patches::new(1000, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2846
2847        let sliced1 = patches.slice(150..550, &mut ctx).unwrap().unwrap();
2848        assert_eq!(sliced1.num_patches(), 4); // 200, 300, 400, 500
2849
2850        let sliced2 = sliced1.slice(100..250, &mut ctx).unwrap().unwrap();
2851        assert_eq!(sliced2.num_patches(), 1); // 300
2852        assert_eq!(sliced2.offset(), 250);
2853
2854        assert_eq!(
2855            sliced2.search_index(50, &mut ctx).unwrap(),
2856            SearchResult::Found(0)
2857        ); // 300 - 250
2858        assert_eq!(
2859            sliced2.search_index(150, &mut ctx).unwrap(),
2860            SearchResult::NotFound(1)
2861        );
2862        assert_arrays_eq!(
2863            sliced1.values(),
2864            PrimitiveArray::from_iter([20i32, 30, 40, 50]),
2865            &mut ctx
2866        );
2867        assert_arrays_eq!(
2868            sliced2.values(),
2869            PrimitiveArray::from_iter([30i32]),
2870            &mut ctx
2871        );
2872    }
2873
2874    #[test]
2875    fn test_nested_slice_with_dropped_first_chunk() {
2876        let mut ctx = SESSION.create_execution_ctx();
2877        // PATCH_CHUNK_SIZE = 1024, so the two patches land in different chunks.
2878        let indices = buffer![0u64, 1024].into_array();
2879        let values = buffer![1i32, 2].into_array();
2880        let chunk_offsets = buffer![0u64, 1].into_array();
2881        let patches =
2882            Patches::new(2048, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2883
2884        // Drop chunk 0, then re-slice the result.
2885        let dropped_first = patches.slice(1024..2048, &mut ctx).unwrap().unwrap();
2886        let resliced = dropped_first.slice(0..1024, &mut ctx).unwrap().unwrap();
2887        assert_eq!(resliced.num_patches(), 1);
2888        assert_eq!(resliced.array_len(), 1024);
2889        assert_eq!(resliced.offset(), 1024);
2890        assert_eq!(
2891            resliced.search_index(0, &mut ctx).unwrap(),
2892            SearchResult::Found(0)
2893        );
2894        assert_arrays_eq!(
2895            resliced.values(),
2896            PrimitiveArray::from_iter([2i32]),
2897            &mut ctx
2898        );
2899    }
2900
2901    #[test]
2902    fn test_index_larger_than_length() {
2903        let mut ctx = SESSION.create_execution_ctx();
2904        let chunk_offsets = buffer![0u64].into_array();
2905        let indices = buffer![1023u64].into_array();
2906        let values = buffer![42i32].into_array();
2907        let patches =
2908            Patches::new(1024, 0, indices, values, Some(chunk_offsets), &mut ctx).unwrap();
2909        assert_eq!(
2910            patches.search_index(2048, &mut ctx).unwrap(),
2911            SearchResult::NotFound(1)
2912        );
2913    }
2914}