Skip to main content

vortex_array/arrays/runend/
ops.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use vortex_error::VortexResult;
5
6use crate::ArrayRef;
7use crate::ArrayView;
8use crate::ExecutionCtx;
9use crate::ProbeState;
10use crate::arrays::runend::RunEnd;
11use crate::match_each_unsigned_integer_ptype;
12use crate::scalar::Scalar;
13use crate::search_sorted::SearchResult;
14use crate::search_sorted::SearchSorted;
15use crate::search_sorted::SearchSortedPrimitiveArray;
16use crate::search_sorted::SearchSortedSide;
17use crate::vtable::OperationsVTable;
18
19impl OperationsVTable<RunEnd> for RunEnd {
20    type ProbeState = ();
21
22    fn probe_scalar(
23        state: &mut ProbeState<'_, RunEnd>,
24        index: usize,
25        ctx: &mut ExecutionCtx,
26    ) -> VortexResult<Scalar> {
27        super::probe::scalar_at(state, index, ctx)
28    }
29
30    fn scalar_at(
31        array: ArrayView<'_, RunEnd>,
32        index: usize,
33        ctx: &mut ExecutionCtx,
34    ) -> VortexResult<Scalar> {
35        super::probe::scalar_at(&mut ProbeState::once(array), index, ctx)
36    }
37}
38
39/// Find the physical offset for and index that would be an end of the slice i.e., one past the last element.
40///
41/// If the index exists in the array we want to take that position (as we are searching from the right)
42/// otherwise we want to take the next one
43pub fn find_slice_end_index(
44    array: &ArrayRef,
45    index: usize,
46    ctx: &mut ExecutionCtx,
47) -> VortexResult<usize> {
48    let result = match_each_unsigned_integer_ptype!(array.dtype().as_ptype(), |T| {
49        SearchSortedPrimitiveArray::<T>::new(array, ctx)
50            .search_sorted(&index, SearchSortedSide::Right)?
51    });
52    Ok(match result {
53        SearchResult::Found(i) => i,
54        SearchResult::NotFound(i) => {
55            if i == array.len() {
56                i
57            } else {
58                i + 1
59            }
60        }
61    })
62}
63
64/// Find the physical index (the run) that contains the logical `index`, given the run `ends`.
65pub fn find_physical_index(
66    array: &ArrayRef,
67    index: usize,
68    ctx: &mut ExecutionCtx,
69) -> VortexResult<usize> {
70    match_each_unsigned_integer_ptype!(array.dtype().as_ptype(), |T| {
71        Ok(SearchSortedPrimitiveArray::<T>::new(array, ctx)
72            .search_sorted(&index, SearchSortedSide::Right)?
73            .to_ends_index(array.len()))
74    })
75}
76
77#[cfg(test)]
78mod tests {
79    use std::sync::LazyLock;
80
81    use vortex_buffer::buffer;
82    use vortex_session::VortexSession;
83
84    use crate::IntoArray;
85    use crate::VortexSessionExecute;
86    use crate::aggregate_fn::fns::is_constant::is_constant;
87    use crate::arrays::PrimitiveArray;
88    use crate::arrays::runend::RunEnd;
89    use crate::assert_arrays_eq;
90    use crate::dtype::DType;
91    use crate::dtype::Nullability;
92    use crate::dtype::PType;
93
94    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
95
96    #[test]
97    fn slice_array() {
98        let mut ctx = SESSION.create_execution_ctx();
99        let arr = RunEnd::try_new(
100            buffer![2u32, 5, 10].into_array(),
101            buffer![1i32, 2, 3].into_array(),
102            &mut ctx,
103        )
104        .unwrap()
105        .slice(3..8)
106        .unwrap();
107        assert_eq!(
108            arr.dtype(),
109            &DType::Primitive(PType::I32, Nullability::NonNullable)
110        );
111        assert_eq!(arr.len(), 5);
112
113        let expected = PrimitiveArray::from_iter(vec![2i32, 2, 3, 3, 3]).into_array();
114        assert_arrays_eq!(arr, expected, &mut ctx);
115    }
116
117    #[test]
118    fn double_slice() {
119        let mut ctx = SESSION.create_execution_ctx();
120        let arr = RunEnd::try_new(
121            buffer![2u32, 5, 10].into_array(),
122            buffer![1i32, 2, 3].into_array(),
123            &mut ctx,
124        )
125        .unwrap()
126        .slice(3..8)
127        .unwrap();
128        assert_eq!(arr.len(), 5);
129
130        let doubly_sliced = arr.slice(0..3).unwrap();
131
132        let expected = PrimitiveArray::from_iter(vec![2i32, 2, 3]).into_array();
133        assert_arrays_eq!(doubly_sliced, expected, &mut ctx);
134    }
135
136    #[test]
137    fn slice_end_inclusive() {
138        let mut ctx = SESSION.create_execution_ctx();
139        let arr = RunEnd::try_new(
140            buffer![2u32, 5, 10].into_array(),
141            buffer![1i32, 2, 3].into_array(),
142            &mut ctx,
143        )
144        .unwrap()
145        .slice(4..10)
146        .unwrap();
147        assert_eq!(
148            arr.dtype(),
149            &DType::Primitive(PType::I32, Nullability::NonNullable)
150        );
151        assert_eq!(arr.len(), 6);
152
153        let expected = PrimitiveArray::from_iter(vec![2i32, 3, 3, 3, 3, 3]).into_array();
154        assert_arrays_eq!(arr, expected, &mut ctx);
155    }
156
157    #[test]
158    fn slice_at_end() {
159        let mut ctx = SESSION.create_execution_ctx();
160        let re_array = RunEnd::try_new(
161            buffer![7_u64, 10].into_array(),
162            buffer![2_u64, 3].into_array(),
163            &mut ctx,
164        )
165        .unwrap();
166
167        assert_eq!(re_array.len(), 10);
168
169        let sliced_array = re_array.slice(re_array.len()..re_array.len()).unwrap();
170        assert!(sliced_array.is_empty());
171    }
172
173    #[test]
174    fn slice_single_end() {
175        let mut ctx = SESSION.create_execution_ctx();
176        let re_array = RunEnd::try_new(
177            buffer![7_u64, 10].into_array(),
178            buffer![2_u64, 3].into_array(),
179            &mut ctx,
180        )
181        .unwrap();
182
183        assert_eq!(re_array.len(), 10);
184
185        let sliced_array = re_array.slice(2..5).unwrap();
186
187        assert!(is_constant(&sliced_array, &mut ctx).unwrap());
188        assert_arrays_eq!(
189            sliced_array,
190            PrimitiveArray::from_iter([2u64, 2, 2]),
191            &mut ctx
192        );
193    }
194
195    #[test]
196    fn ree_scalar_at_end() {
197        let mut ctx = SESSION.create_execution_ctx();
198        let scalar = RunEnd::encode(
199            buffer![1, 1, 1, 4, 4, 4, 2, 2, 5, 5, 5, 5].into_array(),
200            &mut ctx,
201        )
202        .unwrap()
203        .execute_scalar(11, &mut ctx)
204        .unwrap();
205        assert_eq!(scalar, 5.into());
206    }
207
208    #[test]
209    fn slice_along_run_boundaries() {
210        let mut ctx = SESSION.create_execution_ctx();
211        // Create a runend array with runs: [1, 1, 1] [4, 4, 4] [2, 2] [5, 5, 5, 5]
212        // Run ends at indices: 3, 6, 8, 12
213        let arr = RunEnd::try_new(
214            buffer![3u32, 6, 8, 12].into_array(),
215            buffer![1i32, 4, 2, 5].into_array(),
216            &mut ctx,
217        )
218        .unwrap();
219
220        // Slice from start of first run to end of first run (indices 0..3)
221        let slice1 = arr.slice(0..3).unwrap();
222        assert_eq!(slice1.len(), 3);
223        let expected = PrimitiveArray::from_iter(vec![1i32, 1, 1]).into_array();
224        assert_arrays_eq!(slice1, expected, &mut ctx);
225
226        // Slice from start of second run to end of second run (indices 3..6)
227        let slice2 = arr.slice(3..6).unwrap();
228        assert_eq!(slice2.len(), 3);
229        let expected = PrimitiveArray::from_iter(vec![4i32, 4, 4]).into_array();
230        assert_arrays_eq!(slice2, expected, &mut ctx);
231
232        // Slice from start of third run to end of third run (indices 6..8)
233        let slice3 = arr.slice(6..8).unwrap();
234        assert_eq!(slice3.len(), 2);
235        let expected = PrimitiveArray::from_iter(vec![2i32, 2]).into_array();
236        assert_arrays_eq!(slice3, expected, &mut ctx);
237
238        // Slice from start of last run to end of last run (indices 8..12)
239        let slice4 = arr.slice(8..12).unwrap();
240        assert_eq!(slice4.len(), 4);
241        let expected = PrimitiveArray::from_iter(vec![5i32, 5, 5, 5]).into_array();
242        assert_arrays_eq!(slice4, expected, &mut ctx);
243
244        // Slice spanning exactly two runs (indices 3..8)
245        let slice5 = arr.slice(3..8).unwrap();
246        assert_eq!(slice5.len(), 5);
247        let expected = PrimitiveArray::from_iter(vec![4i32, 4, 4, 2, 2]).into_array();
248        assert_arrays_eq!(slice5, expected, &mut ctx);
249
250        // Slice from middle of first run to end of second run (indices 1..6)
251        let slice6 = arr.slice(1..6).unwrap();
252        assert_eq!(slice6.len(), 5);
253        let expected = PrimitiveArray::from_iter(vec![1i32, 1, 4, 4, 4]).into_array();
254        assert_arrays_eq!(slice6, expected, &mut ctx);
255
256        // Slice from start of second run to middle of third run (indices 3..7)
257        let slice7 = arr.slice(3..7).unwrap();
258        assert_eq!(slice7.len(), 4);
259        let expected = PrimitiveArray::from_iter(vec![4i32, 4, 4, 2]).into_array();
260        assert_arrays_eq!(slice7, expected, &mut ctx);
261    }
262}