Skip to content

Commit edf6849

Browse files
authored
fix: Correctly handle slicing RunEnd arrays where slice end aligns with run end (#4542)
Signed-off-by: Robert Kruszewski <[email protected]> Signed-off-by: Robert Kruszewski <[email protected]>
1 parent 95a1479 commit edf6849

2 files changed

Lines changed: 71 additions & 7 deletions

File tree

‎encodings/runend/src/arrow.rs‎

Lines changed: 2 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@ use vortex_dtype::NativePType;
1313
use vortex_scalar::PValue;
1414

1515
use crate::RunEndArray;
16+
use crate::ops::find_slice_end_index;
1617

1718
impl<R: RunEndIndexType> FromArrowArray<&RunArray<R>> for RunEndArray
1819
where
@@ -34,11 +35,7 @@ where
3435
.as_primitive_typed()
3536
.search_sorted(&PValue::from(offset), SearchSortedSide::Right)
3637
.to_ends_index(ends.len());
37-
let slice_end = ends
38-
.as_primitive_typed()
39-
.search_sorted(&PValue::from(offset + len), SearchSortedSide::Right)
40-
.to_ends_index(ends.len())
41-
+ 1;
38+
let slice_end = find_slice_end_index(ends.as_ref(), offset + len);
4239

4340
(
4441
ends.slice(slice_begin..slice_end),

‎encodings/runend/src/ops.rs‎

Lines changed: 69 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4,9 +4,10 @@
44
use std::ops::Range;
55

66
use vortex_array::arrays::ConstantArray;
7+
use vortex_array::search_sorted::{SearchResult, SearchSorted, SearchSortedSide};
78
use vortex_array::vtable::OperationsVTable;
89
use vortex_array::{Array, ArrayRef, IntoArray};
9-
use vortex_scalar::Scalar;
10+
use vortex_scalar::{PValue, Scalar};
1011

1112
use crate::{RunEndArray, RunEndVTable};
1213

@@ -15,7 +16,7 @@ impl OperationsVTable<RunEndVTable> for RunEndVTable {
1516
let new_length = range.len();
1617

1718
let slice_begin = array.find_physical_index(range.start);
18-
let slice_end = array.find_physical_index(range.end) + 1;
19+
let slice_end = find_slice_end_index(array.ends(), range.end + array.offset());
1920

2021
// If the sliced range contains only a single run, opt to return a ConstantArray.
2122
if slice_begin + 1 == slice_end {
@@ -40,6 +41,26 @@ impl OperationsVTable<RunEndVTable> for RunEndVTable {
4041
}
4142
}
4243

44+
/// Find the physical offset for and index that would be an end of the slice i.e., one past the last element.
45+
///
46+
/// If the index exists in the array we want to take that position (as we are searching from the right)
47+
/// otherwise we want to take the next one
48+
pub(crate) fn find_slice_end_index(array: &dyn Array, index: usize) -> usize {
49+
let result = array
50+
.as_primitive_typed()
51+
.search_sorted(&PValue::from(index), SearchSortedSide::Right);
52+
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+
4364
#[cfg(test)]
4465
mod tests {
4566
use vortex_array::arrays::PrimitiveArray;
@@ -139,4 +160,50 @@ mod tests {
139160
.scalar_at(11);
140161
assert_eq!(scalar, 5.into());
141162
}
163+
164+
#[test]
165+
fn slice_along_run_boundaries() {
166+
// Create a runend array with runs: [1, 1, 1] [4, 4, 4] [2, 2] [5, 5, 5, 5]
167+
// Run ends at indices: 3, 6, 8, 12
168+
let arr = RunEndArray::try_new(
169+
buffer![3u32, 6, 8, 12].into_array(),
170+
buffer![1i32, 4, 2, 5].into_array(),
171+
)
172+
.unwrap();
173+
174+
// Slice from start of first run to end of first run (indices 0..3)
175+
let slice1 = arr.slice(0..3);
176+
assert_eq!(slice1.len(), 3);
177+
assert_eq!(slice1.to_primitive().as_slice::<i32>(), vec![1, 1, 1]);
178+
179+
// Slice from start of second run to end of second run (indices 3..6)
180+
let slice2 = arr.slice(3..6);
181+
assert_eq!(slice2.len(), 3);
182+
assert_eq!(slice2.to_primitive().as_slice::<i32>(), vec![4, 4, 4]);
183+
184+
// Slice from start of third run to end of third run (indices 6..8)
185+
let slice3 = arr.slice(6..8);
186+
assert_eq!(slice3.len(), 2);
187+
assert_eq!(slice3.to_primitive().as_slice::<i32>(), vec![2, 2]);
188+
189+
// Slice from start of last run to end of last run (indices 8..12)
190+
let slice4 = arr.slice(8..12);
191+
assert_eq!(slice4.len(), 4);
192+
assert_eq!(slice4.to_primitive().as_slice::<i32>(), vec![5, 5, 5, 5]);
193+
194+
// Slice spanning exactly two runs (indices 3..8)
195+
let slice5 = arr.slice(3..8);
196+
assert_eq!(slice5.len(), 5);
197+
assert_eq!(slice5.to_primitive().as_slice::<i32>(), vec![4, 4, 4, 2, 2]);
198+
199+
// Slice from middle of first run to end of second run (indices 1..6)
200+
let slice6 = arr.slice(1..6);
201+
assert_eq!(slice6.len(), 5);
202+
assert_eq!(slice6.to_primitive().as_slice::<i32>(), vec![1, 1, 4, 4, 4]);
203+
204+
// Slice from start of second run to middle of third run (indices 3..7)
205+
let slice7 = arr.slice(3..7);
206+
assert_eq!(slice7.len(), 4);
207+
assert_eq!(slice7.to_primitive().as_slice::<i32>(), vec![4, 4, 4, 2]);
208+
}
142209
}

0 commit comments

Comments
 (0)