@@ -42,8 +42,8 @@ pub use crate::joins::{JoinOn, JoinOnRef};
4242
4343use arrow:: array:: {
4444 Array , ArrowPrimitiveType , BooleanBufferBuilder , NativeAdapter , PrimitiveArray ,
45- RecordBatch , RecordBatchOptions , UInt32Array , UInt32Builder , UInt64Array ,
46- builder:: UInt64Builder , downcast_array, new_null_array,
45+ PrimitiveBuilder , RecordBatch , RecordBatchOptions , UInt32Array , UInt32Builder ,
46+ UInt64Array , builder:: UInt64Builder , downcast_array, new_null_array,
4747} ;
4848use arrow:: array:: {
4949 ArrayRef , BinaryArray , BinaryViewArray , BooleanArray , Date32Array , Date64Array ,
@@ -1555,39 +1555,78 @@ pub(crate) fn append_right_indices(
15551555 }
15561556}
15571557
1558- /// Returns `range` indices which are not present in `input_indices`
1558+ /// Returns `range` indices which are not present in `input_indices`.
1559+ ///
1560+ /// `input_indices` must be sorted ascending.
15591561pub ( crate ) fn get_anti_indices < T : ArrowPrimitiveType > (
15601562 range : Range < usize > ,
15611563 input_indices : & PrimitiveArray < T > ,
15621564) -> PrimitiveArray < T >
15631565where
15641566 NativeAdapter < T > : From < <T as ArrowPrimitiveType >:: Native > ,
15651567{
1566- let bitmap = build_range_bitmap ( & range, input_indices) ;
1567- let offset = range. start ;
1568+ debug_assert ! (
1569+ input_indices
1570+ . values( )
1571+ . windows( 2 )
1572+ . all( |w| w[ 0 ] . as_usize( ) <= w[ 1 ] . as_usize( ) ) ,
1573+ "get_anti_indices requires ascending input_indices"
1574+ ) ;
15681575
1569- // get the anti index
1570- ( range)
1571- . filter_map ( |idx| {
1572- ( !bitmap. get_bit ( idx - offset) ) . then_some ( T :: Native :: from_usize ( idx) )
1573- } )
1574- . collect ( )
1576+ let mut next_unmatched_idx = range. start ;
1577+ let mut output = PrimitiveBuilder :: < T > :: new ( ) ;
1578+
1579+ for v in input_indices. iter ( ) . flatten ( ) {
1580+ let idx = v. as_usize ( ) ;
1581+
1582+ if idx < range. start {
1583+ continue ;
1584+ }
1585+ if idx >= range. end {
1586+ break ;
1587+ }
1588+
1589+ if next_unmatched_idx < idx {
1590+ for value in next_unmatched_idx..idx {
1591+ output. append_option ( T :: Native :: from_usize ( value) ) ;
1592+ }
1593+ }
1594+ next_unmatched_idx = idx + 1 ;
1595+ }
1596+
1597+ if next_unmatched_idx < range. end {
1598+ for value in next_unmatched_idx..range. end {
1599+ output. append_option ( T :: Native :: from_usize ( value) ) ;
1600+ }
1601+ }
1602+ output. finish ( )
15751603}
15761604
1577- /// Returns intersection of `range` and `input_indices` omitting duplicates
1605+ /// Returns the intersection of `range` and `input_indices`, omitting duplicates.
1606+ ///
1607+ /// `input_indices` must be sorted ascending.
15781608pub ( crate ) fn get_semi_indices < T : ArrowPrimitiveType > (
15791609 range : Range < usize > ,
15801610 input_indices : & PrimitiveArray < T > ,
15811611) -> PrimitiveArray < T >
15821612where
15831613 NativeAdapter < T > : From < <T as ArrowPrimitiveType >:: Native > ,
15841614{
1585- let bitmap = build_range_bitmap ( & range, input_indices) ;
1586- let offset = range. start ;
1587- // get the semi index
1588- ( range)
1589- . filter_map ( |idx| {
1590- ( bitmap. get_bit ( idx - offset) ) . then_some ( T :: Native :: from_usize ( idx) )
1615+ debug_assert ! (
1616+ input_indices
1617+ . values( )
1618+ . windows( 2 )
1619+ . all( |w| w[ 0 ] . as_usize( ) <= w[ 1 ] . as_usize( ) ) ,
1620+ "get_semi_indices requires ascending input_indices"
1621+ ) ;
1622+
1623+ let mut prev_idx: Option < usize > = None ;
1624+ input_indices
1625+ . iter ( )
1626+ . flatten ( )
1627+ . filter_map ( |v| {
1628+ let idx = v. as_usize ( ) ;
1629+ ( range. contains ( & idx) && prev_idx. replace ( idx) != Some ( idx) ) . then_some ( v)
15911630 } )
15921631 . collect ( )
15931632}
@@ -2353,6 +2392,82 @@ mod tests {
23532392
23542393 use rstest:: rstest;
23552394
2395+ fn assert_u32_values ( array : & UInt32Array , expected : & [ u32 ] ) {
2396+ assert_eq ! ( array. values( ) . as_ref( ) , expected) ;
2397+ }
2398+
2399+ #[ test]
2400+ fn get_anti_indices_returns_unmatched_range_indices ( ) {
2401+ let input = UInt32Array :: from ( vec ! [ 3 , 5 , 5 ] ) ;
2402+
2403+ let result = get_anti_indices ( 2 ..8 , & input) ;
2404+
2405+ assert_u32_values ( & result, & [ 2 , 4 , 6 , 7 ] ) ;
2406+ }
2407+
2408+ #[ test]
2409+ fn get_anti_indices_ignores_out_of_range_indices ( ) {
2410+ let input = UInt32Array :: from ( vec ! [ 0 , 1 , 3 , 5 , 8 , 12 ] ) ;
2411+
2412+ let result = get_anti_indices ( 2 ..8 , & input) ;
2413+
2414+ assert_u32_values ( & result, & [ 2 , 4 , 6 , 7 ] ) ;
2415+ }
2416+
2417+ #[ test]
2418+ fn get_anti_indices_handles_dense_matches ( ) {
2419+ let input = UInt32Array :: from ( vec ! [ 2 , 3 , 4 , 5 ] ) ;
2420+
2421+ let result = get_anti_indices ( 2 ..6 , & input) ;
2422+
2423+ assert ! ( result. is_empty( ) ) ;
2424+ }
2425+
2426+ #[ test]
2427+ fn get_anti_indices_handles_sparse_matches ( ) {
2428+ let input = UInt32Array :: from ( vec ! [ 0 , 8 ] ) ;
2429+
2430+ let result = get_anti_indices ( 2 ..6 , & input) ;
2431+
2432+ assert_u32_values ( & result, & [ 2 , 3 , 4 , 5 ] ) ;
2433+ }
2434+
2435+ #[ test]
2436+ fn get_semi_indices_returns_distinct_matches_in_range ( ) {
2437+ let input = UInt32Array :: from ( vec ! [ 1 , 3 , 3 , 3 , 5 , 8 ] ) ;
2438+
2439+ let result = get_semi_indices ( 2 ..7 , & input) ;
2440+
2441+ assert_u32_values ( & result, & [ 3 , 5 ] ) ;
2442+ }
2443+
2444+ #[ test]
2445+ fn get_semi_indices_ignores_out_of_range_indices ( ) {
2446+ let input = UInt32Array :: from ( vec ! [ 0 , 1 , 3 , 5 , 8 , 12 ] ) ;
2447+
2448+ let result = get_semi_indices ( 2 ..8 , & input) ;
2449+
2450+ assert_u32_values ( & result, & [ 3 , 5 ] ) ;
2451+ }
2452+
2453+ #[ test]
2454+ fn get_semi_indices_handles_dense_matches ( ) {
2455+ let input = UInt32Array :: from ( vec ! [ 2 , 3 , 4 , 5 ] ) ;
2456+
2457+ let result = get_semi_indices ( 2 ..6 , & input) ;
2458+
2459+ assert_u32_values ( & result, & [ 2 , 3 , 4 , 5 ] ) ;
2460+ }
2461+
2462+ #[ test]
2463+ fn get_semi_indices_handles_empty_input ( ) {
2464+ let input = UInt32Array :: from ( Vec :: < u32 > :: new ( ) ) ;
2465+
2466+ let result = get_semi_indices ( 2 ..6 , & input) ;
2467+
2468+ assert ! ( result. is_empty( ) ) ;
2469+ }
2470+
23562471 fn check (
23572472 left : & [ Column ] ,
23582473 right : & [ Column ] ,
0 commit comments