Skip to main content

arrow_cmp/
lib.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5//! Basic comparator factories shared by Arrow crates that need to compare
6//! arbitrary array slots without pulling in the full `arrow-ord` crate.
7//!
8//! The only public surface is [`make_comparator`] (with [`DynComparator`] as the
9//! returned function type). `arrow-ord` re-exports both from here, so its
10//! public API is unchanged.
11//!
12//! This crate exists so that crates such as `arrow-select` can use slot-wise
13//! comparison (e.g. for the run-end-encoded `take` fast path) without taking on
14//! the full ordering kernel suite — which would either create a circular
15//! dependency (`arrow-ord` already depends on `arrow-select`) or force every
16//! downstream user of `arrow-array` to compile the comparator machinery whether
17//! they need it or not.
18//!
19//! # Platform Support
20//!
21//! Only little-endian platforms are officially supported and tested in CI.
22//! Big-endian platforms are not tested in CI and may not work correctly.
23//! Fixes for big-endian platforms are welcome and handled on a best-effort basis,
24//! but compatibility is not guaranteed.
25
26#![deny(rustdoc::broken_intra_doc_links)]
27#![warn(missing_docs)]
28
29use arrow_array::cast::AsArray;
30use arrow_array::types::*;
31use arrow_array::*;
32use arrow_buffer::{ArrowNativeType, NullBuffer};
33use arrow_schema::{ArrowError, DataType, SortOptions};
34use std::{cmp::Ordering, collections::HashMap};
35
36fn compare_run_end_encoded<R: RunEndIndexType>(
37    left: &dyn Array,
38    right: &dyn Array,
39    opts: SortOptions,
40) -> Result<DynComparator, ArrowError> {
41    let left = left.as_run::<R>();
42    let right = right.as_run::<R>();
43
44    let c_opts = child_opts(opts);
45    let cmp = make_comparator(left.values().as_ref(), right.values().as_ref(), c_opts)?;
46
47    let l_run_ends = left.run_ends().clone();
48    let r_run_ends = right.run_ends().clone();
49
50    let f = compare(left, right, opts, move |i, j| {
51        let l_physical = l_run_ends.get_physical_index(i);
52        let r_physical = r_run_ends.get_physical_index(j);
53        cmp(l_physical, r_physical)
54    });
55    Ok(f)
56}
57
58/// Compare values at arbitrary indices in two arrays.
59pub type DynComparator = Box<dyn Fn(usize, usize) -> Ordering + Send + Sync>;
60
61/// If parent sort order is descending we need to invert the value of nulls_first so that
62/// when the parent is sorted based on the produced ranks, nulls are still ordered correctly
63fn child_opts(opts: SortOptions) -> SortOptions {
64    SortOptions {
65        descending: false,
66        nulls_first: opts.nulls_first != opts.descending,
67    }
68}
69
70fn compare<A, F>(l: &A, r: &A, opts: SortOptions, cmp: F) -> DynComparator
71where
72    A: Array + Clone,
73    F: Fn(usize, usize) -> Ordering + Send + Sync + 'static,
74{
75    let l = l.logical_nulls().filter(|x| x.null_count() > 0);
76    let r = r.logical_nulls().filter(|x| x.null_count() > 0);
77    match (opts.nulls_first, opts.descending) {
78        (true, true) => compare_impl::<true, true, _>(l, r, cmp),
79        (true, false) => compare_impl::<true, false, _>(l, r, cmp),
80        (false, true) => compare_impl::<false, true, _>(l, r, cmp),
81        (false, false) => compare_impl::<false, false, _>(l, r, cmp),
82    }
83}
84
85fn compare_impl<const NULLS_FIRST: bool, const DESCENDING: bool, F>(
86    l: Option<NullBuffer>,
87    r: Option<NullBuffer>,
88    cmp: F,
89) -> DynComparator
90where
91    F: Fn(usize, usize) -> Ordering + Send + Sync + 'static,
92{
93    let cmp = move |i, j| match DESCENDING {
94        true => cmp(i, j).reverse(),
95        false => cmp(i, j),
96    };
97
98    let (left_null, right_null) = match NULLS_FIRST {
99        true => (Ordering::Less, Ordering::Greater),
100        false => (Ordering::Greater, Ordering::Less),
101    };
102
103    match (l, r) {
104        (None, None) => Box::new(cmp),
105        (Some(l), None) => Box::new(move |i, j| match l.is_null(i) {
106            true => left_null,
107            false => cmp(i, j),
108        }),
109        (None, Some(r)) => Box::new(move |i, j| match r.is_null(j) {
110            true => right_null,
111            false => cmp(i, j),
112        }),
113        (Some(l), Some(r)) => Box::new(move |i, j| match (l.is_null(i), r.is_null(j)) {
114            (true, true) => Ordering::Equal,
115            (true, false) => left_null,
116            (false, true) => right_null,
117            (false, false) => cmp(i, j),
118        }),
119    }
120}
121
122fn compare_primitive<T: ArrowPrimitiveType>(
123    left: &dyn Array,
124    right: &dyn Array,
125    opts: SortOptions,
126) -> DynComparator
127where
128    T::Native: ArrowNativeTypeOp,
129{
130    let left = left.as_primitive::<T>();
131    let right = right.as_primitive::<T>();
132    let l_values = left.values().clone();
133    let r_values = right.values().clone();
134
135    compare(&left, &right, opts, move |i, j| {
136        l_values[i].compare(r_values[j])
137    })
138}
139
140fn compare_boolean(left: &dyn Array, right: &dyn Array, opts: SortOptions) -> DynComparator {
141    let left = left.as_boolean();
142    let right = right.as_boolean();
143
144    let l_values = left.values().clone();
145    let r_values = right.values().clone();
146
147    compare(left, right, opts, move |i, j| {
148        l_values.value(i).cmp(&r_values.value(j))
149    })
150}
151
152fn compare_bytes<T: ByteArrayType>(
153    left: &dyn Array,
154    right: &dyn Array,
155    opts: SortOptions,
156) -> DynComparator {
157    let left = left.as_bytes::<T>();
158    let right = right.as_bytes::<T>();
159
160    let l = left.clone();
161    let r = right.clone();
162    compare(left, right, opts, move |i, j| {
163        let l: &[u8] = l.value(i).as_ref();
164        let r: &[u8] = r.value(j).as_ref();
165        l.cmp(r)
166    })
167}
168
169fn compare_byte_view<T: ByteViewType>(
170    left: &dyn Array,
171    right: &dyn Array,
172    opts: SortOptions,
173) -> DynComparator {
174    let left = left.as_byte_view::<T>();
175    let right = right.as_byte_view::<T>();
176
177    let l = left.clone();
178    let r = right.clone();
179    compare(left, right, opts, move |i, j| {
180        compare_byte_view_values(&l, i, &r, j)
181    })
182}
183
184fn compare_byte_view_values<T: ByteViewType>(
185    left: &GenericByteViewArray<T>,
186    left_idx: usize,
187    right: &GenericByteViewArray<T>,
188    right_idx: usize,
189) -> Ordering {
190    assert!(left_idx < left.len());
191    assert!(right_idx < right.len());
192
193    if left.data_buffers().is_empty() && right.data_buffers().is_empty() {
194        let l_view = unsafe { left.views().get_unchecked(left_idx) };
195        let r_view = unsafe { right.views().get_unchecked(right_idx) };
196        return GenericByteViewArray::<T>::inline_key_fast(*l_view)
197            .cmp(&GenericByteViewArray::<T>::inline_key_fast(*r_view));
198    }
199
200    unsafe { GenericByteViewArray::compare_unchecked(left, left_idx, right, right_idx) }
201}
202
203fn compare_dict<K: ArrowDictionaryKeyType>(
204    left: &dyn Array,
205    right: &dyn Array,
206    opts: SortOptions,
207) -> Result<DynComparator, ArrowError> {
208    let left = left.as_dictionary::<K>();
209    let right = right.as_dictionary::<K>();
210    let value_dtype = left.values().data_type();
211    if value_dtype == right.values().data_type() {
212        match value_dtype {
213            DataType::Utf8 => return Ok(compare_dict_bytes::<K, Utf8Type>(left, right, opts)),
214            DataType::LargeUtf8 => {
215                return Ok(compare_dict_bytes::<K, LargeUtf8Type>(left, right, opts));
216            }
217            DataType::Binary => {
218                return Ok(compare_dict_bytes::<K, BinaryType>(left, right, opts));
219            }
220            DataType::LargeBinary => {
221                return Ok(compare_dict_bytes::<K, LargeBinaryType>(left, right, opts));
222            }
223            DataType::FixedSizeBinary(_) => {
224                return Ok(compare_dict_fixed_size_binary::<K>(left, right, opts));
225            }
226            _ => {}
227        }
228    }
229
230    let c_opts = child_opts(opts);
231    let cmp = make_comparator(left.values().as_ref(), right.values().as_ref(), c_opts)?;
232    let left_keys = left.keys().values().clone();
233    let right_keys = right.keys().values().clone();
234
235    let f = compare(left, right, opts, move |i, j| {
236        let l = left_keys[i].as_usize();
237        let r = right_keys[j].as_usize();
238        cmp(l, r)
239    });
240    Ok(f)
241}
242
243fn compare_dict_bytes<K: ArrowDictionaryKeyType, T: ByteArrayType>(
244    left: &DictionaryArray<K>,
245    right: &DictionaryArray<K>,
246    opts: SortOptions,
247) -> DynComparator {
248    let left_values = left.values().as_bytes::<T>().clone();
249    let right_values = right.values().as_bytes::<T>().clone();
250    let left_keys = left.keys().values().clone();
251    let right_keys = right.keys().values().clone();
252    compare(left, right, opts, move |left_row, right_row| {
253        let left_key = left_keys[left_row].as_usize();
254        let right_key = right_keys[right_row].as_usize();
255        debug_assert!(left_key < left_values.len() && right_key < right_values.len());
256        // SAFETY: `compare` calls this only for rows that are valid on both sides, and
257        // `DictionaryArray` guarantees that every valid key indexes into its values.
258        let (left_bytes, right_bytes): (&[u8], &[u8]) = unsafe {
259            (
260                left_values.value_unchecked(left_key).as_ref(),
261                right_values.value_unchecked(right_key).as_ref(),
262            )
263        };
264        left_bytes.cmp(right_bytes)
265    })
266}
267
268fn compare_dict_fixed_size_binary<K: ArrowDictionaryKeyType>(
269    left: &DictionaryArray<K>,
270    right: &DictionaryArray<K>,
271    opts: SortOptions,
272) -> DynComparator {
273    let left_values = left.values().as_fixed_size_binary().clone();
274    let right_values = right.values().as_fixed_size_binary().clone();
275    let left_keys = left.keys().values().clone();
276    let right_keys = right.keys().values().clone();
277    compare(left, right, opts, move |left_row, right_row| {
278        let left_key = left_keys[left_row].as_usize();
279        let right_key = right_keys[right_row].as_usize();
280        debug_assert!(left_key < left_values.len() && right_key < right_values.len());
281        // SAFETY: `compare` calls this only for rows that are valid on both sides, and
282        // `DictionaryArray` guarantees that every valid key indexes into its values.
283        let (left_bytes, right_bytes) = unsafe {
284            (
285                left_values.value_unchecked(left_key),
286                right_values.value_unchecked(right_key),
287            )
288        };
289        left_bytes.cmp(right_bytes)
290    })
291}
292
293fn compare_list<O: OffsetSizeTrait>(
294    left: &dyn Array,
295    right: &dyn Array,
296    opts: SortOptions,
297) -> Result<DynComparator, ArrowError> {
298    let left = left.as_list::<O>();
299    let right = right.as_list::<O>();
300
301    let c_opts = child_opts(opts);
302    let cmp = make_comparator(left.values().as_ref(), right.values().as_ref(), c_opts)?;
303
304    let l_o = left.offsets().clone();
305    let r_o = right.offsets().clone();
306    let f = compare(left, right, opts, move |i, j| {
307        let l_end = l_o[i + 1].as_usize();
308        let l_start = l_o[i].as_usize();
309
310        let r_end = r_o[j + 1].as_usize();
311        let r_start = r_o[j].as_usize();
312
313        for (i, j) in (l_start..l_end).zip(r_start..r_end) {
314            match cmp(i, j) {
315                Ordering::Equal => {}
316                r => return r,
317            }
318        }
319        (l_end - l_start).cmp(&(r_end - r_start))
320    });
321    Ok(f)
322}
323
324fn compare_fixed_list(
325    left: &dyn Array,
326    right: &dyn Array,
327    opts: SortOptions,
328) -> Result<DynComparator, ArrowError> {
329    let left = left.as_fixed_size_list();
330    let right = right.as_fixed_size_list();
331
332    let c_opts = child_opts(opts);
333    let cmp = make_comparator(left.values().as_ref(), right.values().as_ref(), c_opts)?;
334
335    let l_size = left.value_length().to_usize().unwrap();
336    let r_size = right.value_length().to_usize().unwrap();
337    let size_cmp = l_size.cmp(&r_size);
338
339    let f = compare(left, right, opts, move |i, j| {
340        let l_start = i * l_size;
341        let l_end = l_start + l_size;
342        let r_start = j * r_size;
343        let r_end = r_start + r_size;
344        for (i, j) in (l_start..l_end).zip(r_start..r_end) {
345            match cmp(i, j) {
346                Ordering::Equal => {}
347                r => return r,
348            }
349        }
350        size_cmp
351    });
352    Ok(f)
353}
354
355fn compare_list_view<O: OffsetSizeTrait>(
356    left: &dyn Array,
357    right: &dyn Array,
358    opts: SortOptions,
359) -> Result<DynComparator, ArrowError> {
360    let left = left.as_list_view::<O>();
361    let right = right.as_list_view::<O>();
362
363    let c_opts = child_opts(opts);
364    let cmp = make_comparator(left.values().as_ref(), right.values().as_ref(), c_opts)?;
365
366    let l_offsets = left.offsets().clone();
367    let l_sizes = left.sizes().clone();
368    let r_offsets = right.offsets().clone();
369    let r_sizes = right.sizes().clone();
370
371    let f = compare(left, right, opts, move |i, j| {
372        let l_start = l_offsets[i].as_usize();
373        let l_len = l_sizes[i].as_usize();
374        let l_end = l_start + l_len;
375
376        let r_start = r_offsets[j].as_usize();
377        let r_len = r_sizes[j].as_usize();
378        let r_end = r_start + r_len;
379
380        for (i, j) in (l_start..l_end).zip(r_start..r_end) {
381            match cmp(i, j) {
382                Ordering::Equal => {}
383                r => return r,
384            }
385        }
386        l_len.cmp(&r_len)
387    });
388    Ok(f)
389}
390
391fn compare_map(
392    left: &dyn Array,
393    right: &dyn Array,
394    opts: SortOptions,
395) -> Result<DynComparator, ArrowError> {
396    let left = left.as_map();
397    let right = right.as_map();
398
399    let c_opts = child_opts(opts);
400    let cmp = make_comparator(left.entries(), right.entries(), c_opts)?;
401
402    let l_o = left.offsets().clone();
403    let r_o = right.offsets().clone();
404    let f = compare(left, right, opts, move |i, j| {
405        let l_end = l_o[i + 1].as_usize();
406        let l_start = l_o[i].as_usize();
407
408        let r_end = r_o[j + 1].as_usize();
409        let r_start = r_o[j].as_usize();
410
411        for (i, j) in (l_start..l_end).zip(r_start..r_end) {
412            match cmp(i, j) {
413                Ordering::Equal => {}
414                r => return r,
415            }
416        }
417        (l_end - l_start).cmp(&(r_end - r_start))
418    });
419    Ok(f)
420}
421
422fn compare_struct(
423    left: &dyn Array,
424    right: &dyn Array,
425    opts: SortOptions,
426) -> Result<DynComparator, ArrowError> {
427    let left = left.as_struct();
428    let right = right.as_struct();
429
430    if left.columns().len() != right.columns().len() {
431        return Err(ArrowError::InvalidArgumentError(
432            "Cannot compare StructArray with different number of columns".to_string(),
433        ));
434    }
435
436    let c_opts = child_opts(opts);
437    let columns = left.columns().iter().zip(right.columns());
438    let comparators = columns
439        .map(|(l, r)| make_comparator(l, r, c_opts))
440        .collect::<Result<Vec<_>, _>>()?;
441
442    let f = compare(left, right, opts, move |i, j| {
443        for cmp in &comparators {
444            match cmp(i, j) {
445                Ordering::Equal => {}
446                r => return r,
447            }
448        }
449        Ordering::Equal
450    });
451    Ok(f)
452}
453
454fn compare_union(
455    left: &dyn Array,
456    right: &dyn Array,
457    opts: SortOptions,
458) -> Result<DynComparator, ArrowError> {
459    let left = left.as_union();
460    let right = right.as_union();
461
462    let DataType::Union(left_fields, left_mode) = left.data_type() else {
463        unreachable!()
464    };
465    let DataType::Union(right_fields, right_mode) = right.data_type() else {
466        unreachable!()
467    };
468
469    if left_fields != right_fields {
470        return Err(ArrowError::InvalidArgumentError(format!(
471            "Cannot compare UnionArrays with different fields: left={left_fields:?}, right={right_fields:?}"
472        )));
473    }
474
475    if left_mode != right_mode {
476        return Err(ArrowError::InvalidArgumentError(format!(
477            "Cannot compare UnionArrays with different modes: left={left_mode:?}, right={right_mode:?}"
478        )));
479    }
480
481    let c_opts = child_opts(opts);
482
483    let mut field_comparators = HashMap::with_capacity(left_fields.len());
484
485    for (type_id, _field) in left_fields.iter() {
486        let left_child = left.child(type_id);
487        let right_child = right.child(type_id);
488        let cmp = make_comparator(left_child.as_ref(), right_child.as_ref(), c_opts)?;
489
490        field_comparators.insert(type_id, cmp);
491    }
492
493    let left_type_ids = left.type_ids().clone();
494    let right_type_ids = right.type_ids().clone();
495
496    let left_offsets = left.offsets().cloned();
497    let right_offsets = right.offsets().cloned();
498
499    let f = compare(left, right, opts, move |i, j| {
500        let left_type_id = left_type_ids[i];
501        let right_type_id = right_type_ids[j];
502
503        match left_type_id.cmp(&right_type_id) {
504            Ordering::Equal => {
505                let left_offset = left_offsets.as_ref().map(|o| o[i] as usize).unwrap_or(i);
506                let right_offset = right_offsets.as_ref().map(|o| o[j] as usize).unwrap_or(j);
507
508                let cmp = field_comparators
509                    .get(&left_type_id)
510                    .expect("type id not found in field_comparators");
511
512                cmp(left_offset, right_offset)
513            }
514            other => other,
515        }
516    });
517    Ok(f)
518}
519
520/// Returns a comparison function that compares two values at two arbitrary indices.
521///
522/// If `nulls_first` is true, null values are considered less than any non-null
523/// value; otherwise they are considered greater. This is primarily shared by
524/// crates that need repeated slot comparisons without constructing sliced arrays.
525///
526/// Returns an error for arrays whose types are not comparable.
527pub fn make_comparator(
528    left: &dyn Array,
529    right: &dyn Array,
530    opts: SortOptions,
531) -> Result<DynComparator, ArrowError> {
532    use arrow_schema::DataType::*;
533
534    // Decimal arrays of the same width are compared as raw unscaled values
535    // below; that is only correct when the scales match.
536    match (left.data_type(), right.data_type()) {
537        (Decimal32(_, s1), Decimal32(_, s2))
538        | (Decimal64(_, s1), Decimal64(_, s2))
539        | (Decimal128(_, s1), Decimal128(_, s2))
540        | (Decimal256(_, s1), Decimal256(_, s2))
541            if s1 != s2 =>
542        {
543            return Err(ArrowError::InvalidArgumentError(format!(
544                "Can't compare decimal arrays with different scales: {:?}, {:?}",
545                left.data_type(),
546                right.data_type()
547            )));
548        }
549        _ => {}
550    }
551
552    macro_rules! primitive_helper {
553        ($t:ty, $left:expr, $right:expr, $nulls_first:expr) => {
554            Ok(compare_primitive::<$t>($left, $right, $nulls_first))
555        };
556    }
557    downcast_primitive! {
558        left.data_type(), right.data_type() => (primitive_helper, left, right, opts),
559        (Boolean, Boolean) => Ok(compare_boolean(left, right, opts)),
560        (Utf8, Utf8) => Ok(compare_bytes::<Utf8Type>(left, right, opts)),
561        (LargeUtf8, LargeUtf8) => Ok(compare_bytes::<LargeUtf8Type>(left, right, opts)),
562        (Utf8View, Utf8View) => Ok(compare_byte_view::<StringViewType>(left, right, opts)),
563        (Binary, Binary) => Ok(compare_bytes::<BinaryType>(left, right, opts)),
564        (LargeBinary, LargeBinary) => Ok(compare_bytes::<LargeBinaryType>(left, right, opts)),
565        (BinaryView, BinaryView) => Ok(compare_byte_view::<BinaryViewType>(left, right, opts)),
566        (FixedSizeBinary(_), FixedSizeBinary(_)) => {
567            let left = left.as_fixed_size_binary();
568            let right = right.as_fixed_size_binary();
569
570            let l = left.clone();
571            let r = right.clone();
572            Ok(compare(left, right, opts, move |i, j| {
573                l.value(i).cmp(r.value(j))
574            }))
575        },
576        (List(_), List(_)) => compare_list::<i32>(left, right, opts),
577        (LargeList(_), LargeList(_)) => compare_list::<i64>(left, right, opts),
578        (ListView(_), ListView(_)) => compare_list_view::<i32>(left, right, opts),
579        (LargeListView(_), LargeListView(_)) => compare_list_view::<i64>(left, right, opts),
580        (FixedSizeList(_, _), FixedSizeList(_, _)) => compare_fixed_list(left, right, opts),
581        (Struct(_), Struct(_)) => compare_struct(left, right, opts),
582        (Dictionary(l_key, _), Dictionary(r_key, _)) => {
583             macro_rules! dict_helper {
584                ($t:ty, $left:expr, $right:expr, $opts: expr) => {
585                     compare_dict::<$t>($left, $right, $opts)
586                 };
587             }
588            downcast_integer! {
589                 l_key.as_ref(), r_key.as_ref() => (dict_helper, left, right, opts),
590                 _ => unreachable!()
591             }
592        },
593        (RunEndEncoded(l_run_ends, _), RunEndEncoded(r_run_ends, _)) => {
594            macro_rules! run_end_helper {
595                ($t:ty, $left:expr, $right:expr, $opts:expr) => {
596                    compare_run_end_encoded::<$t>($left, $right, $opts)
597                };
598            }
599            downcast_run_end_index! {
600                l_run_ends.data_type(), r_run_ends.data_type() => (run_end_helper, left, right, opts),
601                _ => Err(ArrowError::InvalidArgumentError(format!(
602                    "Cannot compare RunEndEncoded arrays with different run ends types: left={:?}, right={:?}",
603                    l_run_ends.data_type(),
604                    r_run_ends.data_type()
605                )))
606            }
607        },
608        (Map(_, _), Map(_, _)) => compare_map(left, right, opts),
609        (Null, Null) => Ok(Box::new(|_, _| Ordering::Equal)),
610        (Union(_, _), Union(_, _)) => compare_union(left, right, opts),
611        (lhs, rhs) => Err(ArrowError::InvalidArgumentError(match lhs == rhs {
612            true => format!("The data type type {lhs:?} has no natural order"),
613            false => "Can't compare arrays of different types".to_string(),
614        }))
615    }
616}
617
618#[cfg(test)]
619mod tests {
620    use super::*;
621    use arrow_array::builder::{Int32Builder, ListBuilder, MapBuilder, StringBuilder};
622    use arrow_buffer::{IntervalDayTime, NullBuffer, OffsetBuffer, ScalarBuffer, i256};
623    use arrow_schema::{ArrowError, DataType, Field, Fields, UnionFields};
624    use half::f16;
625    use std::cmp::Ordering;
626    use std::sync::Arc;
627
628    #[test]
629    fn test_fixed_size_binary() {
630        let items = vec![vec![1u8], vec![2u8]];
631        let array = FixedSizeBinaryArray::try_from_iter(items.into_iter()).unwrap();
632
633        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
634
635        assert_eq!(Ordering::Less, cmp(0, 1));
636    }
637
638    #[test]
639    fn test_fixed_size_binary_fixed_size_binary() {
640        let items = vec![vec![1u8]];
641        let array1 = FixedSizeBinaryArray::try_from_iter(items.into_iter()).unwrap();
642        let items = vec![vec![2u8]];
643        let array2 = FixedSizeBinaryArray::try_from_iter(items.into_iter()).unwrap();
644
645        let cmp = make_comparator(&array1, &array2, SortOptions::default()).unwrap();
646
647        assert_eq!(Ordering::Less, cmp(0, 0));
648    }
649
650    #[test]
651    fn test_i32() {
652        let array = Int32Array::from(vec![1, 2]);
653
654        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
655
656        assert_eq!(Ordering::Less, (cmp)(0, 1));
657    }
658
659    #[test]
660    fn test_i32_i32() {
661        let array1 = Int32Array::from(vec![1]);
662        let array2 = Int32Array::from(vec![2]);
663
664        let cmp = make_comparator(&array1, &array2, SortOptions::default()).unwrap();
665
666        assert_eq!(Ordering::Less, cmp(0, 0));
667    }
668
669    #[cfg_attr(miri, ignore)] // Unsupported inline assembly
670    #[test]
671    fn test_f16() {
672        let array = Float16Array::from(vec![f16::from_f32(1.0), f16::from_f32(2.0)]);
673
674        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
675
676        assert_eq!(Ordering::Less, cmp(0, 1));
677    }
678
679    #[test]
680    fn test_f64() {
681        let array = Float64Array::from(vec![1.0, 2.0]);
682
683        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
684
685        assert_eq!(Ordering::Less, cmp(0, 1));
686    }
687
688    #[test]
689    fn test_f64_nan() {
690        let array = Float64Array::from(vec![1.0, f64::NAN]);
691
692        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
693
694        assert_eq!(Ordering::Less, cmp(0, 1));
695        assert_eq!(Ordering::Equal, cmp(1, 1));
696    }
697
698    #[test]
699    fn test_f64_zeros() {
700        let array = Float64Array::from(vec![-0.0, 0.0]);
701
702        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
703
704        assert_eq!(Ordering::Less, cmp(0, 1));
705        assert_eq!(Ordering::Greater, cmp(1, 0));
706    }
707
708    #[test]
709    fn test_interval_day_time() {
710        let array = IntervalDayTimeArray::from(vec![
711            // 0 days, 1 second
712            IntervalDayTimeType::make_value(0, 1000),
713            // 1 day, 2 milliseconds
714            IntervalDayTimeType::make_value(1, 2),
715            // 90M milliseconds (which is more than is in 1 day)
716            IntervalDayTimeType::make_value(0, 90_000_000),
717        ]);
718
719        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
720
721        assert_eq!(Ordering::Less, cmp(0, 1));
722        assert_eq!(Ordering::Greater, cmp(1, 0));
723
724        // somewhat confusingly, while 90M milliseconds is more than 1 day,
725        // it will compare less as the comparison is done on the underlying
726        // values not field by field
727        assert_eq!(Ordering::Greater, cmp(1, 2));
728        assert_eq!(Ordering::Less, cmp(2, 1));
729    }
730
731    #[test]
732    fn test_interval_year_month() {
733        let array = IntervalYearMonthArray::from(vec![
734            // 1 year, 0 months
735            IntervalYearMonthType::make_value(1, 0),
736            // 0 years, 13 months
737            IntervalYearMonthType::make_value(0, 13),
738            // 1 year, 1 month
739            IntervalYearMonthType::make_value(1, 1),
740        ]);
741
742        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
743
744        assert_eq!(Ordering::Less, cmp(0, 1));
745        assert_eq!(Ordering::Greater, cmp(1, 0));
746
747        // the underlying representation is months, so both quantities are the same
748        assert_eq!(Ordering::Equal, cmp(1, 2));
749        assert_eq!(Ordering::Equal, cmp(2, 1));
750    }
751
752    #[test]
753    fn test_interval_month_day_nano() {
754        let array = IntervalMonthDayNanoArray::from(vec![
755            // 100 days
756            IntervalMonthDayNanoType::make_value(0, 100, 0),
757            // 1 month
758            IntervalMonthDayNanoType::make_value(1, 0, 0),
759            // 100 day, 1 nanoseconds
760            IntervalMonthDayNanoType::make_value(0, 100, 2),
761        ]);
762
763        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
764
765        assert_eq!(Ordering::Less, cmp(0, 1));
766        assert_eq!(Ordering::Greater, cmp(1, 0));
767
768        // somewhat confusingly, while 100 days is more than 1 month in all cases
769        // it will compare less as the comparison is done on the underlying
770        // values not field by field
771        assert_eq!(Ordering::Greater, cmp(1, 2));
772        assert_eq!(Ordering::Less, cmp(2, 1));
773    }
774
775    #[test]
776    fn test_decimali32() {
777        let array = vec![Some(5_i32), Some(2_i32), Some(3_i32)]
778            .into_iter()
779            .collect::<Decimal32Array>()
780            .with_precision_and_scale(8, 6)
781            .unwrap();
782
783        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
784        assert_eq!(Ordering::Less, cmp(1, 0));
785        assert_eq!(Ordering::Greater, cmp(0, 2));
786    }
787
788    #[test]
789    fn test_decimali64() {
790        let array = vec![Some(5_i64), Some(2_i64), Some(3_i64)]
791            .into_iter()
792            .collect::<Decimal64Array>()
793            .with_precision_and_scale(16, 6)
794            .unwrap();
795
796        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
797        assert_eq!(Ordering::Less, cmp(1, 0));
798        assert_eq!(Ordering::Greater, cmp(0, 2));
799    }
800
801    #[test]
802    fn test_decimali128() {
803        let array = vec![Some(5_i128), Some(2_i128), Some(3_i128)]
804            .into_iter()
805            .collect::<Decimal128Array>()
806            .with_precision_and_scale(23, 6)
807            .unwrap();
808
809        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
810        assert_eq!(Ordering::Less, cmp(1, 0));
811        assert_eq!(Ordering::Greater, cmp(0, 2));
812    }
813
814    #[test]
815    fn test_decimali256() {
816        let array = vec![
817            Some(i256::from_i128(5_i128)),
818            Some(i256::from_i128(2_i128)),
819            Some(i256::from_i128(3_i128)),
820        ]
821        .into_iter()
822        .collect::<Decimal256Array>()
823        .with_precision_and_scale(53, 6)
824        .unwrap();
825
826        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
827        assert_eq!(Ordering::Less, cmp(1, 0));
828        assert_eq!(Ordering::Greater, cmp(0, 2));
829    }
830
831    #[test]
832    fn test_dict() {
833        let data = vec!["a", "b", "c", "a", "a", "c", "c"];
834        let array = data.into_iter().collect::<DictionaryArray<Int16Type>>();
835
836        let cmp = make_comparator(&array, &array, SortOptions::default()).unwrap();
837
838        assert_eq!(Ordering::Less, cmp(0, 1));
839        assert_eq!(Ordering::Equal, cmp(3, 4));
840        assert_eq!(Ordering::Greater, cmp(2, 3));
841    }
842
843    #[test]
844    fn test_multiple_dict() {
845        let d1 = vec!["a", "b", "c", "d"];
846        let a1 = d1.into_iter().collect::<DictionaryArray<Int16Type>>();
847        let d2 = vec!["e", "f", "g", "a"];
848        let a2 = d2.into_iter().collect::<DictionaryArray<Int16Type>>();
849
850        let cmp = make_comparator(&a1, &a2, SortOptions::default()).unwrap();
851
852        assert_eq!(Ordering::Less, cmp(0, 0));
853        assert_eq!(Ordering::Equal, cmp(0, 3));
854        assert_eq!(Ordering::Greater, cmp(1, 3));
855    }
856
857    #[test]
858    fn dict_fixed_size_binary_fast_path_derefs_values_both_directions() {
859        let shared_keys = || Int32Array::from(vec![0_i32, 1]);
860        let left_values =
861            FixedSizeBinaryArray::try_from_iter([b"zz".as_ref(), b"aa".as_ref()].into_iter())
862                .unwrap();
863        let right_values =
864            FixedSizeBinaryArray::try_from_iter([b"aa".as_ref(), b"zz".as_ref()].into_iter())
865                .unwrap();
866        let left = DictionaryArray::<Int32Type>::new(shared_keys(), Arc::new(left_values));
867        let right = DictionaryArray::<Int32Type>::new(shared_keys(), Arc::new(right_values));
868
869        let ascending = make_comparator(&left, &right, SortOptions::default()).unwrap();
870        assert_eq!(ascending(0, 0), Ordering::Greater);
871        assert_eq!(ascending(1, 1), Ordering::Less);
872
873        let descending = make_comparator(
874            &left,
875            &right,
876            SortOptions {
877                descending: true,
878                nulls_first: true,
879            },
880        )
881        .unwrap();
882        assert_eq!(descending(0, 0), Ordering::Less);
883        assert_eq!(descending(1, 1), Ordering::Greater);
884    }
885
886    fn dict_bytes_fast_path_derefs_values_both_directions_impl<T: ByteArrayType>() {
887        let shared_keys = || Int32Array::from(vec![0_i32, 1]);
888        let left_values =
889            GenericByteArray::<T>::new(OffsetBuffer::from_lengths([1, 1]), b"za".into(), None);
890        let right_values =
891            GenericByteArray::<T>::new(OffsetBuffer::from_lengths([1, 1]), b"az".into(), None);
892        let left = DictionaryArray::<Int32Type>::new(shared_keys(), Arc::new(left_values));
893        let right = DictionaryArray::<Int32Type>::new(shared_keys(), Arc::new(right_values));
894
895        let ascending = make_comparator(&left, &right, SortOptions::default()).unwrap();
896        assert_eq!(ascending(0, 0), Ordering::Greater);
897        assert_eq!(ascending(1, 1), Ordering::Less);
898
899        let descending = make_comparator(
900            &left,
901            &right,
902            SortOptions {
903                descending: true,
904                nulls_first: true,
905            },
906        )
907        .unwrap();
908        assert_eq!(descending(0, 0), Ordering::Less);
909        assert_eq!(descending(1, 1), Ordering::Greater);
910    }
911
912    #[test]
913    fn dict_bytes_fast_path_derefs_values_both_directions() {
914        dict_bytes_fast_path_derefs_values_both_directions_impl::<Utf8Type>();
915        dict_bytes_fast_path_derefs_values_both_directions_impl::<LargeUtf8Type>();
916        dict_bytes_fast_path_derefs_values_both_directions_impl::<BinaryType>();
917        dict_bytes_fast_path_derefs_values_both_directions_impl::<LargeBinaryType>();
918    }
919
920    fn dict_bytes_handles_key_and_value_nulls_impl<T: ByteArrayType>() {
921        // Left carries a logical null via a null KEY at row 1.
922        let left_keys = Int32Array::from(vec![Some(0_i32), None, Some(1)]);
923        let left_values = GenericByteArray::<T>::new(
924            OffsetBuffer::from_lengths([5, 6]),
925            b"applebanana".into(),
926            None,
927        );
928        let left = DictionaryArray::<Int32Type>::new(left_keys, Arc::new(left_values));
929
930        // Right carries a logical null via a null VALUE referenced at row 1.
931        let right_keys = Int32Array::from(vec![Some(0_i32), Some(1), Some(0)]);
932        let right_values = GenericByteArray::<T>::new(
933            OffsetBuffer::from_lengths([5, 0]),
934            b"apple".into(),
935            Some(NullBuffer::from(vec![true, false])),
936        );
937        let right = DictionaryArray::<Int32Type>::new(right_keys, Arc::new(right_values));
938
939        let cmp = make_comparator(&left, &right, SortOptions::default()).unwrap();
940        assert_eq!(cmp(0, 0), Ordering::Equal); // apple vs apple
941        assert_eq!(cmp(1, 0), Ordering::Less); // null-key < apple (nulls_first)
942        assert_eq!(cmp(0, 1), Ordering::Greater); // apple > null-value (nulls_first)
943        assert_eq!(cmp(1, 1), Ordering::Equal); // null-key vs null-value
944    }
945
946    #[test]
947    fn dict_bytes_handles_key_and_value_nulls() {
948        dict_bytes_handles_key_and_value_nulls_impl::<Utf8Type>();
949        dict_bytes_handles_key_and_value_nulls_impl::<LargeUtf8Type>();
950        dict_bytes_handles_key_and_value_nulls_impl::<BinaryType>();
951        dict_bytes_handles_key_and_value_nulls_impl::<LargeBinaryType>();
952    }
953
954    fn dict_bytes_sort_options_with_nulls_impl<T: ByteArrayType>() {
955        // row 1 is null on both sides (null key on left, null value on right)
956        let null_row_on_left = Int32Array::from(vec![Some(0_i32), None, Some(1)]);
957        let left_values = GenericByteArray::<T>::new(
958            OffsetBuffer::from_lengths([5, 6]),
959            b"applebanana".into(),
960            None,
961        );
962        let left = DictionaryArray::<Int32Type>::new(null_row_on_left, Arc::new(left_values));
963
964        let keys_pointing_at_null = Int32Array::from(vec![Some(0_i32), Some(1), Some(0)]);
965        let right_values = GenericByteArray::<T>::new(
966            OffsetBuffer::from_lengths([6, 0]),
967            b"cherry".into(),
968            Some(NullBuffer::from(vec![true, false])),
969        );
970        let right =
971            DictionaryArray::<Int32Type>::new(keys_pointing_at_null, Arc::new(right_values));
972
973        let asc_nulls_last = SortOptions {
974            descending: false,
975            nulls_first: false,
976        };
977        let desc_nulls_first = SortOptions {
978            descending: true,
979            nulls_first: true,
980        };
981        let desc_nulls_last = SortOptions {
982            descending: true,
983            nulls_first: false,
984        };
985
986        let cmp = make_comparator(&left, &right, asc_nulls_last).unwrap();
987        assert_eq!(cmp(0, 0), Ordering::Less); // apple < cherry
988        assert_eq!(cmp(1, 0), Ordering::Greater); // null > cherry (nulls last)
989        assert_eq!(cmp(0, 1), Ordering::Less); // apple < null (nulls last)
990        assert_eq!(cmp(1, 1), Ordering::Equal);
991
992        let cmp = make_comparator(&left, &right, desc_nulls_first).unwrap();
993        assert_eq!(cmp(0, 0), Ordering::Greater); // apple vs cherry reversed
994        assert_eq!(cmp(1, 0), Ordering::Less); // null < cherry (nulls first, unaffected by desc)
995        assert_eq!(cmp(0, 1), Ordering::Greater); // apple > null (nulls first)
996        assert_eq!(cmp(1, 1), Ordering::Equal);
997
998        let cmp = make_comparator(&left, &right, desc_nulls_last).unwrap();
999        assert_eq!(cmp(0, 0), Ordering::Greater); // apple vs cherry reversed
1000        assert_eq!(cmp(1, 0), Ordering::Greater); // null > cherry (nulls last)
1001        assert_eq!(cmp(0, 1), Ordering::Less); // apple < null (nulls last)
1002        assert_eq!(cmp(1, 1), Ordering::Equal);
1003    }
1004
1005    #[test]
1006    fn dict_bytes_sort_options_with_nulls() {
1007        dict_bytes_sort_options_with_nulls_impl::<Utf8Type>();
1008        dict_bytes_sort_options_with_nulls_impl::<LargeUtf8Type>();
1009        dict_bytes_sort_options_with_nulls_impl::<BinaryType>();
1010        dict_bytes_sort_options_with_nulls_impl::<LargeBinaryType>();
1011    }
1012
1013    fn dict_bytes_fast_path_panics_on_out_of_bounds_row_impl<T: ByteArrayType>() {
1014        let two_row_keys = Int32Array::from(vec![0_i32, 1]);
1015        let values =
1016            GenericByteArray::<T>::new(OffsetBuffer::from_lengths([1, 1]), b"ab".into(), None);
1017        let dict = DictionaryArray::<Int32Type>::new(two_row_keys, Arc::new(values));
1018
1019        let cmp = make_comparator(&dict, &dict, SortOptions::default()).unwrap();
1020        cmp(2, 0);
1021    }
1022
1023    #[test]
1024    #[should_panic(expected = "index out of bounds")]
1025    fn dict_utf8_fast_path_panics_on_out_of_bounds_row() {
1026        dict_bytes_fast_path_panics_on_out_of_bounds_row_impl::<Utf8Type>();
1027    }
1028
1029    #[test]
1030    #[should_panic(expected = "index out of bounds")]
1031    fn dict_large_utf8_fast_path_panics_on_out_of_bounds_row() {
1032        dict_bytes_fast_path_panics_on_out_of_bounds_row_impl::<LargeUtf8Type>();
1033    }
1034
1035    #[test]
1036    #[should_panic(expected = "index out of bounds")]
1037    fn dict_binary_fast_path_panics_on_out_of_bounds_row() {
1038        dict_bytes_fast_path_panics_on_out_of_bounds_row_impl::<BinaryType>();
1039    }
1040
1041    #[test]
1042    #[should_panic(expected = "index out of bounds")]
1043    fn dict_large_binary_fast_path_panics_on_out_of_bounds_row() {
1044        dict_bytes_fast_path_panics_on_out_of_bounds_row_impl::<LargeBinaryType>();
1045    }
1046
1047    #[test]
1048    #[should_panic(expected = "index out of bounds")]
1049    fn dict_fixed_size_binary_fast_path_panics_on_out_of_bounds_row() {
1050        let two_row_keys = Int32Array::from(vec![0_i32, 1]);
1051        let values = Arc::new(
1052            FixedSizeBinaryArray::try_from_iter([b"aa".as_ref(), b"bb".as_ref()].into_iter())
1053                .unwrap(),
1054        );
1055        let dict = DictionaryArray::<Int32Type>::new(two_row_keys, values);
1056
1057        let cmp = make_comparator(&dict, &dict, SortOptions::default()).unwrap();
1058        cmp(2, 0);
1059    }
1060
1061    #[test]
1062    fn dict_fixed_size_binary_sort_options_with_nulls() {
1063        let null_row_on_left = Int32Array::from(vec![Some(0_i32), None, Some(1)]);
1064        let left_values =
1065            FixedSizeBinaryArray::try_from_iter([b"aa".as_ref(), b"bb".as_ref()].into_iter())
1066                .unwrap();
1067        let left = DictionaryArray::<Int32Type>::new(null_row_on_left, Arc::new(left_values));
1068
1069        let keys_pointing_at_null = Int32Array::from(vec![Some(0_i32), Some(1), Some(0)]);
1070        let right_values = FixedSizeBinaryArray::try_from_sparse_iter_with_size(
1071            [Some(b"cc".as_ref()), None].into_iter(),
1072            2,
1073        )
1074        .unwrap();
1075        let right =
1076            DictionaryArray::<Int32Type>::new(keys_pointing_at_null, Arc::new(right_values));
1077
1078        let asc_nulls_last = SortOptions {
1079            descending: false,
1080            nulls_first: false,
1081        };
1082        let desc_nulls_first = SortOptions {
1083            descending: true,
1084            nulls_first: true,
1085        };
1086        let desc_nulls_last = SortOptions {
1087            descending: true,
1088            nulls_first: false,
1089        };
1090
1091        let cmp = make_comparator(&left, &right, asc_nulls_last).unwrap();
1092        assert_eq!(cmp(0, 0), Ordering::Less); // "aa" < "cc"
1093        assert_eq!(cmp(1, 0), Ordering::Greater); // null > "cc" (nulls last)
1094        assert_eq!(cmp(0, 1), Ordering::Less); // "aa" < null (nulls last)
1095        assert_eq!(cmp(1, 1), Ordering::Equal);
1096
1097        let cmp = make_comparator(&left, &right, desc_nulls_first).unwrap();
1098        assert_eq!(cmp(0, 0), Ordering::Greater); // "aa" vs "cc" reversed
1099        assert_eq!(cmp(1, 0), Ordering::Less); // null < "cc" (nulls first)
1100        assert_eq!(cmp(0, 1), Ordering::Greater); // "aa" > null (nulls first)
1101        assert_eq!(cmp(1, 1), Ordering::Equal);
1102
1103        let cmp = make_comparator(&left, &right, desc_nulls_last).unwrap();
1104        assert_eq!(cmp(0, 0), Ordering::Greater); // "aa" vs "cc" reversed
1105        assert_eq!(cmp(1, 0), Ordering::Greater); // null > "cc" (nulls last)
1106        assert_eq!(cmp(0, 1), Ordering::Less); // "aa" < null (nulls last)
1107        assert_eq!(cmp(1, 1), Ordering::Equal);
1108    }
1109
1110    #[test]
1111    fn test_primitive_dict() {
1112        let values = Int32Array::from(vec![1_i32, 0, 2, 5]);
1113        let keys = Int8Array::from_iter_values([0, 0, 1, 3]);
1114        let array1 = DictionaryArray::new(keys, Arc::new(values));
1115
1116        let values = Int32Array::from(vec![2_i32, 3, 4, 5]);
1117        let keys = Int8Array::from_iter_values([0, 1, 1, 3]);
1118        let array2 = DictionaryArray::new(keys, Arc::new(values));
1119
1120        let cmp = make_comparator(&array1, &array2, SortOptions::default()).unwrap();
1121
1122        assert_eq!(Ordering::Less, cmp(0, 0));
1123        assert_eq!(Ordering::Less, cmp(0, 3));
1124        assert_eq!(Ordering::Equal, cmp(3, 3));
1125        assert_eq!(Ordering::Greater, cmp(3, 1));
1126        assert_eq!(Ordering::Greater, cmp(3, 2));
1127    }
1128
1129    #[test]
1130    fn test_float_dict() {
1131        let values = Float32Array::from(vec![1.0, 0.5, 2.1, 5.5]);
1132        let keys = Int8Array::from_iter_values([0, 0, 1, 3]);
1133        let array1 = DictionaryArray::try_new(keys, Arc::new(values)).unwrap();
1134
1135        let values = Float32Array::from(vec![1.2, 3.2, 4.0, 5.5]);
1136        let keys = Int8Array::from_iter_values([0, 1, 1, 3]);
1137        let array2 = DictionaryArray::new(keys, Arc::new(values));
1138
1139        let cmp = make_comparator(&array1, &array2, SortOptions::default()).unwrap();
1140
1141        assert_eq!(Ordering::Less, cmp(0, 0));
1142        assert_eq!(Ordering::Less, cmp(0, 3));
1143        assert_eq!(Ordering::Equal, cmp(3, 3));
1144        assert_eq!(Ordering::Greater, cmp(3, 1));
1145        assert_eq!(Ordering::Greater, cmp(3, 2));
1146    }
1147
1148    #[test]
1149    fn test_timestamp_dict() {
1150        let values = TimestampSecondArray::from(vec![1, 0, 2, 5]);
1151        let keys = Int8Array::from_iter_values([0, 0, 1, 3]);
1152        let array1 = DictionaryArray::new(keys, Arc::new(values));
1153
1154        let values = TimestampSecondArray::from(vec![2, 3, 4, 5]);
1155        let keys = Int8Array::from_iter_values([0, 1, 1, 3]);
1156        let array2 = DictionaryArray::new(keys, Arc::new(values));
1157
1158        let cmp = make_comparator(&array1, &array2, SortOptions::default()).unwrap();
1159
1160        assert_eq!(Ordering::Less, cmp(0, 0));
1161        assert_eq!(Ordering::Less, cmp(0, 3));
1162        assert_eq!(Ordering::Equal, cmp(3, 3));
1163        assert_eq!(Ordering::Greater, cmp(3, 1));
1164        assert_eq!(Ordering::Greater, cmp(3, 2));
1165    }
1166
1167    #[test]
1168    fn test_interval_dict() {
1169        let v1 = IntervalDayTime::new(0, 1);
1170        let v2 = IntervalDayTime::new(0, 2);
1171        let v3 = IntervalDayTime::new(12, 2);
1172
1173        let values = IntervalDayTimeArray::from(vec![Some(v1), Some(v2), None, Some(v3)]);
1174        let keys = Int8Array::from_iter_values([0, 0, 1, 3]);
1175        let array1 = DictionaryArray::new(keys, Arc::new(values));
1176
1177        let values = IntervalDayTimeArray::from(vec![Some(v3), Some(v2), None, Some(v1)]);
1178        let keys = Int8Array::from_iter_values([0, 1, 1, 3]);
1179        let array2 = DictionaryArray::new(keys, Arc::new(values));
1180
1181        let cmp = make_comparator(&array1, &array2, SortOptions::default()).unwrap();
1182
1183        assert_eq!(Ordering::Less, cmp(0, 0)); // v1 vs v3
1184        assert_eq!(Ordering::Equal, cmp(0, 3)); // v1 vs v1
1185        assert_eq!(Ordering::Greater, cmp(3, 3)); // v3 vs v1
1186        assert_eq!(Ordering::Greater, cmp(3, 1)); // v3 vs v2
1187        assert_eq!(Ordering::Greater, cmp(3, 2)); // v3 vs v2
1188    }
1189
1190    #[test]
1191    fn test_duration_dict() {
1192        let values = DurationSecondArray::from(vec![1, 0, 2, 5]);
1193        let keys = Int8Array::from_iter_values([0, 0, 1, 3]);
1194        let array1 = DictionaryArray::new(keys, Arc::new(values));
1195
1196        let values = DurationSecondArray::from(vec![2, 3, 4, 5]);
1197        let keys = Int8Array::from_iter_values([0, 1, 1, 3]);
1198        let array2 = DictionaryArray::new(keys, Arc::new(values));
1199
1200        let cmp = make_comparator(&array1, &array2, SortOptions::default()).unwrap();
1201
1202        assert_eq!(Ordering::Less, cmp(0, 0));
1203        assert_eq!(Ordering::Less, cmp(0, 3));
1204        assert_eq!(Ordering::Equal, cmp(3, 3));
1205        assert_eq!(Ordering::Greater, cmp(3, 1));
1206        assert_eq!(Ordering::Greater, cmp(3, 2));
1207    }
1208
1209    #[test]
1210    fn test_decimal_dict() {
1211        let values = Decimal128Array::from(vec![1, 0, 2, 5]);
1212        let keys = Int8Array::from_iter_values([0, 0, 1, 3]);
1213        let array1 = DictionaryArray::new(keys, Arc::new(values));
1214
1215        let values = Decimal128Array::from(vec![2, 3, 4, 5]);
1216        let keys = Int8Array::from_iter_values([0, 1, 1, 3]);
1217        let array2 = DictionaryArray::new(keys, Arc::new(values));
1218
1219        let cmp = make_comparator(&array1, &array2, SortOptions::default()).unwrap();
1220
1221        assert_eq!(Ordering::Less, cmp(0, 0));
1222        assert_eq!(Ordering::Less, cmp(0, 3));
1223        assert_eq!(Ordering::Equal, cmp(3, 3));
1224        assert_eq!(Ordering::Greater, cmp(3, 1));
1225        assert_eq!(Ordering::Greater, cmp(3, 2));
1226    }
1227
1228    #[test]
1229    fn test_decimal256_dict() {
1230        let values = Decimal256Array::from(vec![
1231            i256::from_i128(1),
1232            i256::from_i128(0),
1233            i256::from_i128(2),
1234            i256::from_i128(5),
1235        ]);
1236        let keys = Int8Array::from_iter_values([0, 0, 1, 3]);
1237        let array1 = DictionaryArray::new(keys, Arc::new(values));
1238
1239        let values = Decimal256Array::from(vec![
1240            i256::from_i128(2),
1241            i256::from_i128(3),
1242            i256::from_i128(4),
1243            i256::from_i128(5),
1244        ]);
1245        let keys = Int8Array::from_iter_values([0, 1, 1, 3]);
1246        let array2 = DictionaryArray::new(keys, Arc::new(values));
1247
1248        let cmp = make_comparator(&array1, &array2, SortOptions::default()).unwrap();
1249
1250        assert_eq!(Ordering::Less, cmp(0, 0));
1251        assert_eq!(Ordering::Less, cmp(0, 3));
1252        assert_eq!(Ordering::Equal, cmp(3, 3));
1253        assert_eq!(Ordering::Greater, cmp(3, 1));
1254        assert_eq!(Ordering::Greater, cmp(3, 2));
1255    }
1256
1257    #[test]
1258    fn test_decimal_different_scale_errors() {
1259        // https://github.com/apache/arrow-rs/issues/10863
1260        let a = Decimal128Array::from(vec![100])
1261            .with_precision_and_scale(10, 2)
1262            .unwrap();
1263        let b = Decimal128Array::from(vec![500])
1264            .with_precision_and_scale(10, 3)
1265            .unwrap();
1266        let err = make_comparator(&a, &b, SortOptions::default())
1267            .err()
1268            .unwrap();
1269        assert_eq!(
1270            err.to_string(),
1271            "Invalid argument error: Can't compare decimal arrays with different scales: \
1272             Decimal128(10, 2), Decimal128(10, 3)"
1273        );
1274
1275        // the same check applies behind nested types
1276        let keys = Int8Array::from_iter_values([0]);
1277        let dict_a = DictionaryArray::new(keys.clone(), Arc::new(a.clone()));
1278        let dict_b = DictionaryArray::new(keys, Arc::new(b));
1279        assert!(make_comparator(&dict_a, &dict_b, SortOptions::default()).is_err());
1280
1281        // precision does not affect the ordering, so it need not match
1282        let c = Decimal128Array::from(vec![100])
1283            .with_precision_and_scale(12, 2)
1284            .unwrap();
1285        let cmp = make_comparator(&a, &c, SortOptions::default()).unwrap();
1286        assert_eq!(Ordering::Equal, cmp(0, 0));
1287
1288        // every decimal width is checked
1289        let a = Decimal32Array::from(vec![1])
1290            .with_precision_and_scale(5, 1)
1291            .unwrap();
1292        let b = Decimal32Array::from(vec![1])
1293            .with_precision_and_scale(5, 2)
1294            .unwrap();
1295        assert!(make_comparator(&a, &b, SortOptions::default()).is_err());
1296
1297        let a = Decimal64Array::from(vec![1])
1298            .with_precision_and_scale(10, 1)
1299            .unwrap();
1300        let b = Decimal64Array::from(vec![1])
1301            .with_precision_and_scale(10, 2)
1302            .unwrap();
1303        assert!(make_comparator(&a, &b, SortOptions::default()).is_err());
1304
1305        let a = Decimal256Array::from(vec![i256::from_i128(1)])
1306            .with_precision_and_scale(40, 1)
1307            .unwrap();
1308        let b = Decimal256Array::from(vec![i256::from_i128(1)])
1309            .with_precision_and_scale(40, 2)
1310            .unwrap();
1311        assert!(make_comparator(&a, &b, SortOptions::default()).is_err());
1312    }
1313
1314    fn test_bytes_impl<T: ByteArrayType>() {
1315        let offsets = OffsetBuffer::from_lengths([3, 3, 1]);
1316        let a = GenericByteArray::<T>::new(offsets, b"abcdefa".into(), None);
1317        let cmp = make_comparator(&a, &a, SortOptions::default()).unwrap();
1318
1319        assert_eq!(Ordering::Less, cmp(0, 1));
1320        assert_eq!(Ordering::Greater, cmp(0, 2));
1321        assert_eq!(Ordering::Equal, cmp(1, 1));
1322    }
1323
1324    #[test]
1325    fn test_bytes() {
1326        test_bytes_impl::<Utf8Type>();
1327        test_bytes_impl::<LargeUtf8Type>();
1328        test_bytes_impl::<BinaryType>();
1329        test_bytes_impl::<LargeBinaryType>();
1330    }
1331
1332    fn assert_cmp_cases<A: Array>(
1333        array1: &A,
1334        array2: &A,
1335        opts: SortOptions,
1336        cases: &[(usize, usize, Ordering)],
1337    ) {
1338        let cmp = make_comparator(array1, array2, opts).unwrap();
1339        for (left, right, expected) in cases {
1340            assert_eq!(cmp(*left, *right), *expected);
1341        }
1342    }
1343
1344    #[test]
1345    fn test_lists() {
1346        let mut a = ListBuilder::new(ListBuilder::new(Int32Builder::new()));
1347        a.extend([
1348            Some(vec![Some(vec![Some(1), Some(2), None]), Some(vec![None])]),
1349            Some(vec![
1350                Some(vec![Some(1), Some(2), Some(3)]),
1351                Some(vec![Some(1)]),
1352            ]),
1353            Some(vec![]),
1354        ]);
1355        let a = a.finish();
1356        let mut b = ListBuilder::new(ListBuilder::new(Int32Builder::new()));
1357        b.extend([
1358            Some(vec![Some(vec![Some(1), Some(2), None]), Some(vec![None])]),
1359            Some(vec![
1360                Some(vec![Some(1), Some(2), None]),
1361                Some(vec![Some(1)]),
1362            ]),
1363            Some(vec![
1364                Some(vec![Some(1), Some(2), Some(3), Some(4)]),
1365                Some(vec![Some(1)]),
1366            ]),
1367            None,
1368        ]);
1369        let b = b.finish();
1370
1371        // Ascending with nulls first.
1372        assert_cmp_cases(
1373            &a,
1374            &b,
1375            SortOptions {
1376                descending: false,
1377                nulls_first: true,
1378            },
1379            &[
1380                (0, 0, Ordering::Equal),
1381                (0, 1, Ordering::Less),
1382                (0, 2, Ordering::Less),
1383                (1, 2, Ordering::Less),
1384                (1, 3, Ordering::Greater),
1385                (2, 0, Ordering::Less),
1386            ],
1387        );
1388
1389        // Descending with nulls first.
1390        assert_cmp_cases(
1391            &a,
1392            &b,
1393            SortOptions {
1394                descending: true,
1395                nulls_first: true,
1396            },
1397            &[
1398                (0, 0, Ordering::Equal),
1399                (0, 1, Ordering::Less),
1400                (0, 2, Ordering::Less),
1401                (1, 2, Ordering::Greater),
1402                (1, 3, Ordering::Greater),
1403                (2, 0, Ordering::Greater),
1404            ],
1405        );
1406
1407        // Descending with nulls last.
1408        assert_cmp_cases(
1409            &a,
1410            &b,
1411            SortOptions {
1412                descending: true,
1413                nulls_first: false,
1414            },
1415            &[
1416                (0, 0, Ordering::Equal),
1417                (0, 1, Ordering::Greater),
1418                (0, 2, Ordering::Greater),
1419                (1, 2, Ordering::Greater),
1420                (1, 3, Ordering::Less),
1421                (2, 0, Ordering::Greater),
1422            ],
1423        );
1424
1425        // Ascending with nulls last.
1426        assert_cmp_cases(
1427            &a,
1428            &b,
1429            SortOptions {
1430                descending: false,
1431                nulls_first: false,
1432            },
1433            &[
1434                (0, 0, Ordering::Equal),
1435                (0, 1, Ordering::Greater),
1436                (0, 2, Ordering::Greater),
1437                (1, 2, Ordering::Less),
1438                (1, 3, Ordering::Less),
1439                (2, 0, Ordering::Less),
1440            ],
1441        );
1442    }
1443
1444    fn list_view_array<O: OffsetSizeTrait>(
1445        values: Vec<i32>,
1446        offsets: &[usize],
1447        sizes: &[usize],
1448        valid: Option<&[bool]>,
1449    ) -> GenericListViewArray<O> {
1450        let offsets = offsets
1451            .iter()
1452            .map(|v| O::from_usize(*v).unwrap())
1453            .collect::<ScalarBuffer<O>>();
1454        let sizes = sizes
1455            .iter()
1456            .map(|v| O::from_usize(*v).unwrap())
1457            .collect::<ScalarBuffer<O>>();
1458        let field = Arc::new(Field::new_list_field(DataType::Int32, true));
1459        let values = Int32Array::from(values);
1460        let nulls = valid.map(NullBuffer::from);
1461        GenericListViewArray::new(field, offsets, sizes, Arc::new(values), nulls)
1462    }
1463
1464    fn test_list_view_comparisons<O: OffsetSizeTrait>() {
1465        let array = list_view_array::<O>(
1466            vec![1, 2, 3, 4, 5],
1467            &[0, 2, 1, 0, 3],
1468            &[2, 2, 2, 0, 2],
1469            Some(&[true, true, true, true, false]),
1470        );
1471
1472        // Ascending with nulls first (non-monotonic offsets and empty list).
1473        assert_cmp_cases(
1474            &array,
1475            &array,
1476            SortOptions {
1477                descending: false,
1478                nulls_first: true,
1479            },
1480            &[
1481                (0, 2, Ordering::Less),    // [1,2] < [2,3]
1482                (1, 2, Ordering::Greater), // [3,4] > [2,3]
1483                (3, 0, Ordering::Less),    // [] < [1,2]
1484                (4, 0, Ordering::Less),    // null < [1,2]
1485            ],
1486        );
1487
1488        // Ascending with nulls last.
1489        assert_cmp_cases(
1490            &array,
1491            &array,
1492            SortOptions {
1493                descending: false,
1494                nulls_first: false,
1495            },
1496            &[
1497                (0, 2, Ordering::Less),
1498                (1, 2, Ordering::Greater),
1499                (3, 0, Ordering::Less),
1500                (4, 0, Ordering::Greater), // null last
1501            ],
1502        );
1503
1504        // Descending with nulls first.
1505        assert_cmp_cases(
1506            &array,
1507            &array,
1508            SortOptions {
1509                descending: true,
1510                nulls_first: true,
1511            },
1512            &[
1513                (0, 2, Ordering::Greater),
1514                (1, 2, Ordering::Less),
1515                (3, 0, Ordering::Greater),
1516                (4, 0, Ordering::Less),
1517            ],
1518        );
1519
1520        // Descending with nulls last.
1521        assert_cmp_cases(
1522            &array,
1523            &array,
1524            SortOptions {
1525                descending: true,
1526                nulls_first: false,
1527            },
1528            &[
1529                (0, 2, Ordering::Greater),
1530                (1, 2, Ordering::Less),
1531                (3, 0, Ordering::Greater),
1532                (4, 0, Ordering::Greater),
1533            ],
1534        );
1535    }
1536
1537    #[test]
1538    fn test_list_view() {
1539        test_list_view_comparisons::<i32>();
1540    }
1541
1542    #[test]
1543    fn test_large_list_view() {
1544        test_list_view_comparisons::<i64>();
1545    }
1546
1547    #[test]
1548    fn test_struct() {
1549        let fields = Fields::from(vec![
1550            Field::new("a", DataType::Int32, true),
1551            Field::new_list("b", Field::new_list_field(DataType::Int32, true), true),
1552        ]);
1553
1554        let a = Int32Array::from(vec![Some(1), Some(2), None, None]);
1555        let mut b = ListBuilder::new(Int32Builder::new());
1556        b.extend([Some(vec![Some(1), Some(2)]), Some(vec![None]), None, None]);
1557        let b = b.finish();
1558
1559        let nulls = Some(NullBuffer::from_iter([true, true, true, false]));
1560        let values = vec![Arc::new(a) as _, Arc::new(b) as _];
1561        let s1 = StructArray::new(fields.clone(), values, nulls);
1562
1563        let a = Int32Array::from(vec![None, Some(2), None]);
1564        let mut b = ListBuilder::new(Int32Builder::new());
1565        b.extend([None, None, Some(vec![])]);
1566        let b = b.finish();
1567
1568        let values = vec![Arc::new(a) as _, Arc::new(b) as _];
1569        let s2 = StructArray::new(fields.clone(), values, None);
1570
1571        let opts = SortOptions {
1572            descending: false,
1573            nulls_first: true,
1574        };
1575        let cmp = make_comparator(&s1, &s2, opts).unwrap();
1576        assert_eq!(cmp(0, 1), Ordering::Less); // (1, [1, 2]) cmp (2, None)
1577        assert_eq!(cmp(0, 0), Ordering::Greater); // (1, [1, 2]) cmp (None, None)
1578        assert_eq!(cmp(1, 1), Ordering::Greater); // (2, [None]) cmp (2, None)
1579        assert_eq!(cmp(2, 2), Ordering::Less); // (None, None) cmp (None, [])
1580        assert_eq!(cmp(3, 0), Ordering::Less); // None cmp (None, [])
1581        assert_eq!(cmp(2, 0), Ordering::Equal); // (None, None) cmp (None, None)
1582        assert_eq!(cmp(3, 0), Ordering::Less); // None cmp (None, None)
1583
1584        let opts = SortOptions {
1585            descending: true,
1586            nulls_first: true,
1587        };
1588        let cmp = make_comparator(&s1, &s2, opts).unwrap();
1589        assert_eq!(cmp(0, 1), Ordering::Greater); // (1, [1, 2]) cmp (2, None)
1590        assert_eq!(cmp(0, 0), Ordering::Greater); // (1, [1, 2]) cmp (None, None)
1591        assert_eq!(cmp(1, 1), Ordering::Greater); // (2, [None]) cmp (2, None)
1592        assert_eq!(cmp(2, 2), Ordering::Less); // (None, None) cmp (None, [])
1593        assert_eq!(cmp(3, 0), Ordering::Less); // None cmp (None, [])
1594        assert_eq!(cmp(2, 0), Ordering::Equal); // (None, None) cmp (None, None)
1595        assert_eq!(cmp(3, 0), Ordering::Less); // None cmp (None, None)
1596
1597        let opts = SortOptions {
1598            descending: true,
1599            nulls_first: false,
1600        };
1601        let cmp = make_comparator(&s1, &s2, opts).unwrap();
1602        assert_eq!(cmp(0, 1), Ordering::Greater); // (1, [1, 2]) cmp (2, None)
1603        assert_eq!(cmp(0, 0), Ordering::Less); // (1, [1, 2]) cmp (None, None)
1604        assert_eq!(cmp(1, 1), Ordering::Less); // (2, [None]) cmp (2, None)
1605        assert_eq!(cmp(2, 2), Ordering::Greater); // (None, None) cmp (None, [])
1606        assert_eq!(cmp(3, 0), Ordering::Greater); // None cmp (None, [])
1607        assert_eq!(cmp(2, 0), Ordering::Equal); // (None, None) cmp (None, None)
1608        assert_eq!(cmp(3, 0), Ordering::Greater); // None cmp (None, None)
1609
1610        let opts = SortOptions {
1611            descending: false,
1612            nulls_first: false,
1613        };
1614        let cmp = make_comparator(&s1, &s2, opts).unwrap();
1615        assert_eq!(cmp(0, 1), Ordering::Less); // (1, [1, 2]) cmp (2, None)
1616        assert_eq!(cmp(0, 0), Ordering::Less); // (1, [1, 2]) cmp (None, None)
1617        assert_eq!(cmp(1, 1), Ordering::Less); // (2, [None]) cmp (2, None)
1618        assert_eq!(cmp(2, 2), Ordering::Greater); // (None, None) cmp (None, [])
1619        assert_eq!(cmp(3, 0), Ordering::Greater); // None cmp (None, [])
1620        assert_eq!(cmp(2, 0), Ordering::Equal); // (None, None) cmp (None, None)
1621        assert_eq!(cmp(3, 0), Ordering::Greater); // None cmp (None, None)
1622    }
1623
1624    #[test]
1625    fn test_map() {
1626        // Create first map array demonstrating key priority over values:
1627        // [{"a": 100, "b": 1}, {"b": 999, "c": 1}, {}, {"x": 1}]
1628        let string_builder = StringBuilder::new();
1629        let int_builder = Int32Builder::new();
1630        let mut map1_builder = MapBuilder::new(None, string_builder, int_builder);
1631
1632        // {"a": 100, "b": 1} - high value for "a", low value for "b"
1633        map1_builder.keys().append_value("a");
1634        map1_builder.values().append_value(100);
1635        map1_builder.keys().append_value("b");
1636        map1_builder.values().append_value(1);
1637        map1_builder.append(true).unwrap();
1638
1639        // {"b": 999, "c": 1} - very high value for "b", low value for "c"
1640        map1_builder.keys().append_value("b");
1641        map1_builder.values().append_value(999);
1642        map1_builder.keys().append_value("c");
1643        map1_builder.values().append_value(1);
1644        map1_builder.append(true).unwrap();
1645
1646        // {}
1647        map1_builder.append(true).unwrap();
1648
1649        // {"x": 1}
1650        map1_builder.keys().append_value("x");
1651        map1_builder.values().append_value(1);
1652        map1_builder.append(true).unwrap();
1653
1654        let map1 = map1_builder.finish();
1655
1656        // Create second map array:
1657        // [{"a": 1, "c": 999}, {"b": 1, "d": 999}, {"a": 1}, None]
1658        let string_builder = StringBuilder::new();
1659        let int_builder = Int32Builder::new();
1660        let mut map2_builder = MapBuilder::new(None, string_builder, int_builder);
1661
1662        // {"a": 1, "c": 999} - low value for "a", high value for "c"
1663        map2_builder.keys().append_value("a");
1664        map2_builder.values().append_value(1);
1665        map2_builder.keys().append_value("c");
1666        map2_builder.values().append_value(999);
1667        map2_builder.append(true).unwrap();
1668
1669        // {"b": 1, "d": 999} - low value for "b", high value for "d"
1670        map2_builder.keys().append_value("b");
1671        map2_builder.values().append_value(1);
1672        map2_builder.keys().append_value("d");
1673        map2_builder.values().append_value(999);
1674        map2_builder.append(true).unwrap();
1675
1676        // {"a": 1}
1677        map2_builder.keys().append_value("a");
1678        map2_builder.values().append_value(1);
1679        map2_builder.append(true).unwrap();
1680
1681        // None
1682        map2_builder.append(false).unwrap();
1683
1684        let map2 = map2_builder.finish();
1685
1686        let opts = SortOptions {
1687            descending: false,
1688            nulls_first: true,
1689        };
1690        let cmp = make_comparator(&map1, &map2, opts).unwrap();
1691
1692        // Test that keys have priority over values:
1693        // {"a": 100, "b": 1} vs {"a": 1, "c": 999}
1694        // First entries match (a:100 vs a:1), but 100 > 1, so Greater
1695        assert_eq!(cmp(0, 0), Ordering::Greater);
1696
1697        // {"b": 999, "c": 1} vs {"b": 1, "d": 999}
1698        // First entries match (b:999 vs b:1), but 999 > 1, so Greater
1699        assert_eq!(cmp(1, 1), Ordering::Greater);
1700
1701        // Key comparison: "a" < "b", so {"a": 100, "b": 1} < {"b": 999, "c": 1}
1702        assert_eq!(cmp(0, 1), Ordering::Less);
1703
1704        // Empty map vs non-empty
1705        assert_eq!(cmp(2, 2), Ordering::Less); // {} < {"a": 1}
1706
1707        // Non-null vs null
1708        assert_eq!(cmp(3, 3), Ordering::Greater); // {"x": 1} > None
1709
1710        // Key priority test: "x" > "a", regardless of values
1711        assert_eq!(cmp(3, 0), Ordering::Greater); // {"x": 1} > {"a": 1, "c": 999}
1712
1713        // Empty vs non-empty
1714        assert_eq!(cmp(2, 0), Ordering::Less); // {} < {"a": 1, "c": 999}
1715
1716        let opts = SortOptions {
1717            descending: true,
1718            nulls_first: true,
1719        };
1720        let cmp = make_comparator(&map1, &map2, opts).unwrap();
1721
1722        // With descending=true, value comparison is reversed
1723        assert_eq!(cmp(0, 0), Ordering::Less); // {"a": 100, "b": 1} vs {"a": 1, "c": 999} (reversed)
1724        assert_eq!(cmp(1, 1), Ordering::Less); // {"b": 999, "c": 1} vs {"b": 1, "d": 999} (reversed)
1725        assert_eq!(cmp(0, 1), Ordering::Greater); // {"a": 100, "b": 1} vs {"b": 999, "c": 1} (key order reversed)
1726        assert_eq!(cmp(3, 3), Ordering::Greater); // {"x": 1} > None
1727        assert_eq!(cmp(2, 2), Ordering::Greater); // {} > {"a": 1} (reversed)
1728
1729        let opts = SortOptions {
1730            descending: false,
1731            nulls_first: false,
1732        };
1733        let cmp = make_comparator(&map1, &map2, opts).unwrap();
1734
1735        // Same key priority behavior with nulls_first=false
1736        assert_eq!(cmp(0, 0), Ordering::Greater); // {"a": 100, "b": 1} vs {"a": 1, "c": 999}
1737        assert_eq!(cmp(1, 1), Ordering::Greater); // {"b": 999, "c": 1} vs {"b": 1, "d": 999}
1738        assert_eq!(cmp(3, 3), Ordering::Less); // {"x": 1} < None (nulls last)
1739        assert_eq!(cmp(2, 2), Ordering::Less); // {} < {"a": 1}
1740    }
1741
1742    #[test]
1743    fn test_map_vs_list_consistency() {
1744        // Create map arrays and convert them to list arrays to verify comparison consistency
1745        // Map arrays: [{"a": 1, "b": 2}, {"x": 10}, {}, {"c": 3}]
1746        let string_builder = StringBuilder::new();
1747        let int_builder = Int32Builder::new();
1748        let mut map1_builder = MapBuilder::new(None, string_builder, int_builder);
1749
1750        // {"a": 1, "b": 2}
1751        map1_builder.keys().append_value("a");
1752        map1_builder.values().append_value(1);
1753        map1_builder.keys().append_value("b");
1754        map1_builder.values().append_value(2);
1755        map1_builder.append(true).unwrap();
1756
1757        // {"x": 10}
1758        map1_builder.keys().append_value("x");
1759        map1_builder.values().append_value(10);
1760        map1_builder.append(true).unwrap();
1761
1762        // {}
1763        map1_builder.append(true).unwrap();
1764
1765        // {"c": 3}
1766        map1_builder.keys().append_value("c");
1767        map1_builder.values().append_value(3);
1768        map1_builder.append(true).unwrap();
1769
1770        let map1 = map1_builder.finish();
1771
1772        // Second map array: [{"a": 1, "b": 2}, {"y": 20}, {"d": 4}, None]
1773        let string_builder = StringBuilder::new();
1774        let int_builder = Int32Builder::new();
1775        let mut map2_builder = MapBuilder::new(None, string_builder, int_builder);
1776
1777        // {"a": 1, "b": 2}
1778        map2_builder.keys().append_value("a");
1779        map2_builder.values().append_value(1);
1780        map2_builder.keys().append_value("b");
1781        map2_builder.values().append_value(2);
1782        map2_builder.append(true).unwrap();
1783
1784        // {"y": 20}
1785        map2_builder.keys().append_value("y");
1786        map2_builder.values().append_value(20);
1787        map2_builder.append(true).unwrap();
1788
1789        // {"d": 4}
1790        map2_builder.keys().append_value("d");
1791        map2_builder.values().append_value(4);
1792        map2_builder.append(true).unwrap();
1793
1794        // None
1795        map2_builder.append(false).unwrap();
1796
1797        let map2 = map2_builder.finish();
1798
1799        // Convert map arrays to list arrays (Map entries are struct arrays with key-value pairs)
1800        let list1: ListArray = map1.clone().into();
1801        let list2: ListArray = map2.clone().into();
1802
1803        let test_cases = [
1804            SortOptions {
1805                descending: false,
1806                nulls_first: true,
1807            },
1808            SortOptions {
1809                descending: true,
1810                nulls_first: true,
1811            },
1812            SortOptions {
1813                descending: false,
1814                nulls_first: false,
1815            },
1816            SortOptions {
1817                descending: true,
1818                nulls_first: false,
1819            },
1820        ];
1821
1822        for opts in test_cases {
1823            let map_cmp = make_comparator(&map1, &map2, opts).unwrap();
1824            let list_cmp = make_comparator(&list1, &list2, opts).unwrap();
1825
1826            // Test all possible index combinations
1827            for i in 0..map1.len() {
1828                for j in 0..map2.len() {
1829                    let map_result = map_cmp(i, j);
1830                    let list_result = list_cmp(i, j);
1831                    assert_eq!(
1832                        map_result, list_result,
1833                        "Map comparison and List comparison should be equal for indices ({i}, {j}) with opts {opts:?}. Map: {map_result:?}, List: {list_result:?}"
1834                    );
1835                }
1836            }
1837        }
1838    }
1839
1840    #[test]
1841    fn test_dense_union() {
1842        // create a dense union array with Int32 (type_id = 0) and Utf8 (type_id=1)
1843        // the values are: [1, "b", 2, "a", 3]
1844        //  type_ids are: [0,  1,  0,  1,  0]
1845        //   offsets are: [0, 0, 1, 1, 2] from [1, 2, 3] and ["b", "a"]
1846        let int_array = Int32Array::from(vec![1, 2, 3]);
1847        let str_array = StringArray::from(vec!["b", "a"]);
1848
1849        let type_ids = [0, 1, 0, 1, 0].into_iter().collect::<ScalarBuffer<i8>>();
1850        let offsets = [0, 0, 1, 1, 2].into_iter().collect::<ScalarBuffer<i32>>();
1851
1852        let union_fields = [
1853            (0, Arc::new(Field::new("A", DataType::Int32, false))),
1854            (1, Arc::new(Field::new("B", DataType::Utf8, false))),
1855        ]
1856        .into_iter()
1857        .collect::<UnionFields>();
1858
1859        let children = vec![Arc::new(int_array) as ArrayRef, Arc::new(str_array)];
1860
1861        let array1 =
1862            UnionArray::try_new(union_fields.clone(), type_ids, Some(offsets), children).unwrap();
1863
1864        // create a second array: [2, "a", 1, "c"]
1865        //          type ids are: [0,  1,  0,  1]
1866        //           offsets are: [0, 0, 1, 1] from [2, 1] and ["a", "c"]
1867        let int_array2 = Int32Array::from(vec![2, 1]);
1868        let str_array2 = StringArray::from(vec!["a", "c"]);
1869        let type_ids2 = [0, 1, 0, 1].into_iter().collect::<ScalarBuffer<i8>>();
1870        let offsets2 = [0, 0, 1, 1].into_iter().collect::<ScalarBuffer<i32>>();
1871
1872        let children2 = vec![Arc::new(int_array2) as ArrayRef, Arc::new(str_array2)];
1873
1874        let array2 =
1875            UnionArray::try_new(union_fields, type_ids2, Some(offsets2), children2).unwrap();
1876
1877        let opts = SortOptions {
1878            descending: false,
1879            nulls_first: true,
1880        };
1881
1882        // comparing
1883        // [1, "b", 2, "a", 3]
1884        // [2, "a", 1, "c"]
1885        let cmp = make_comparator(&array1, &array2, opts).unwrap();
1886
1887        // array1[0] = (type_id=0, value=1)
1888        // array2[0] = (type_id=0, value=2)
1889        assert_eq!(cmp(0, 0), Ordering::Less); // 1 < 2
1890
1891        // array1[0] = (type_id=0, value=1)
1892        // array2[1] = (type_id=1, value="a")
1893        assert_eq!(cmp(0, 1), Ordering::Less); // type_id 0 < 1
1894
1895        // array1[1] = (type_id=1, value="b")
1896        // array2[1] = (type_id=1, value="a")
1897        assert_eq!(cmp(1, 1), Ordering::Greater); // "b" > "a"
1898
1899        // array1[2] = (type_id=0, value=2)
1900        // array2[0] = (type_id=0, value=2)
1901        assert_eq!(cmp(2, 0), Ordering::Equal); // 2 == 2
1902
1903        // array1[3] = (type_id=1, value="a")
1904        // array2[1] = (type_id=1, value="a")
1905        assert_eq!(cmp(3, 1), Ordering::Equal); // "a" == "a"
1906
1907        // array1[1] = (type_id=1, value="b")
1908        // array2[3] = (type_id=1, value="c")
1909        assert_eq!(cmp(1, 3), Ordering::Less); // "b" < "c"
1910
1911        let opts_desc = SortOptions {
1912            descending: true,
1913            nulls_first: true,
1914        };
1915        let cmp_desc = make_comparator(&array1, &array2, opts_desc).unwrap();
1916
1917        assert_eq!(cmp_desc(0, 0), Ordering::Greater); // 1 > 2 (reversed)
1918        assert_eq!(cmp_desc(0, 1), Ordering::Greater); // type_id 0 < 1, reversed to Greater
1919        assert_eq!(cmp_desc(1, 1), Ordering::Less); // "b" < "a" (reversed)
1920    }
1921
1922    #[test]
1923    fn test_sparse_union() {
1924        // create a sparse union array with Int32 (type_id=0) and Utf8 (type_id=1)
1925        // values: [1, "b", 3]
1926        // note, in sparse unions, child arrays have the same length as the union
1927        let int_array = Int32Array::from(vec![Some(1), None, Some(3)]);
1928        let str_array = StringArray::from(vec![None, Some("b"), None]);
1929        let type_ids = [0, 1, 0].into_iter().collect::<ScalarBuffer<i8>>();
1930
1931        let union_fields = [
1932            (0, Arc::new(Field::new("a", DataType::Int32, false))),
1933            (1, Arc::new(Field::new("b", DataType::Utf8, false))),
1934        ]
1935        .into_iter()
1936        .collect::<UnionFields>();
1937
1938        let children = vec![Arc::new(int_array) as ArrayRef, Arc::new(str_array)];
1939
1940        let array = UnionArray::try_new(union_fields, type_ids, None, children).unwrap();
1941
1942        let opts = SortOptions::default();
1943        let cmp = make_comparator(&array, &array, opts).unwrap();
1944
1945        // array[0] = (type_id=0, value=1), array[2] = (type_id=0, value=3)
1946        assert_eq!(cmp(0, 2), Ordering::Less); // 1 < 3
1947        // array[0] = (type_id=0, value=1), array[1] = (type_id=1, value="b")
1948        assert_eq!(cmp(0, 1), Ordering::Less); // type_id 0 < 1
1949    }
1950
1951    #[test]
1952    #[should_panic(expected = "index out of bounds")]
1953    fn test_union_out_of_bounds() {
1954        // create a dense union array with 3 elements
1955        let int_array = Int32Array::from(vec![1, 2]);
1956        let str_array = StringArray::from(vec!["a"]);
1957
1958        let type_ids = [0, 1, 0].into_iter().collect::<ScalarBuffer<i8>>();
1959        let offsets = [0, 0, 1].into_iter().collect::<ScalarBuffer<i32>>();
1960
1961        let union_fields = [
1962            (0, Arc::new(Field::new("A", DataType::Int32, false))),
1963            (1, Arc::new(Field::new("B", DataType::Utf8, false))),
1964        ]
1965        .into_iter()
1966        .collect::<UnionFields>();
1967
1968        let children = vec![Arc::new(int_array) as ArrayRef, Arc::new(str_array)];
1969
1970        let array = UnionArray::try_new(union_fields, type_ids, Some(offsets), children).unwrap();
1971
1972        let opts = SortOptions::default();
1973        let cmp = make_comparator(&array, &array, opts).unwrap();
1974
1975        // oob
1976        cmp(0, 3);
1977    }
1978
1979    #[test]
1980    fn test_union_incompatible_fields() {
1981        // create first union with Int32 and Utf8
1982        let int_array1 = Int32Array::from(vec![1, 2]);
1983        let str_array1 = StringArray::from(vec!["a", "b"]);
1984
1985        let type_ids1 = [0, 1].into_iter().collect::<ScalarBuffer<i8>>();
1986        let offsets1 = [0, 0].into_iter().collect::<ScalarBuffer<i32>>();
1987
1988        let union_fields1 = [
1989            (0, Arc::new(Field::new("A", DataType::Int32, false))),
1990            (1, Arc::new(Field::new("B", DataType::Utf8, false))),
1991        ]
1992        .into_iter()
1993        .collect::<UnionFields>();
1994
1995        let children1 = vec![Arc::new(int_array1) as ArrayRef, Arc::new(str_array1)];
1996
1997        let array1 =
1998            UnionArray::try_new(union_fields1, type_ids1, Some(offsets1), children1).unwrap();
1999
2000        // create second union with Int32 and Float64 (incompatible with first)
2001        let int_array2 = Int32Array::from(vec![3, 4]);
2002        let float_array2 = Float64Array::from(vec![1.0, 2.0]);
2003
2004        let type_ids2 = [0, 1].into_iter().collect::<ScalarBuffer<i8>>();
2005        let offsets2 = [0, 0].into_iter().collect::<ScalarBuffer<i32>>();
2006
2007        let union_fields2 = [
2008            (0, Arc::new(Field::new("A", DataType::Int32, false))),
2009            (1, Arc::new(Field::new("C", DataType::Float64, false))),
2010        ]
2011        .into_iter()
2012        .collect::<UnionFields>();
2013
2014        let children2 = vec![Arc::new(int_array2) as ArrayRef, Arc::new(float_array2)];
2015
2016        let array2 =
2017            UnionArray::try_new(union_fields2, type_ids2, Some(offsets2), children2).unwrap();
2018
2019        let opts = SortOptions::default();
2020
2021        let Result::Err(ArrowError::InvalidArgumentError(out)) =
2022            make_comparator(&array1, &array2, opts)
2023        else {
2024            panic!("expected error when making comparator of incompatible union arrays");
2025        };
2026
2027        assert_eq!(
2028            &out,
2029            "Cannot compare UnionArrays with different fields: left=[(0, Field { name: \"A\", data_type: Int32 }), (1, Field { name: \"B\", data_type: Utf8 })], right=[(0, Field { name: \"A\", data_type: Int32 }), (1, Field { name: \"C\", data_type: Float64 })]"
2030        );
2031    }
2032
2033    #[test]
2034    fn test_union_incompatible_modes() {
2035        // create first union as Dense with Int32 and Utf8
2036        let int_array1 = Int32Array::from(vec![1, 2]);
2037        let str_array1 = StringArray::from(vec!["a", "b"]);
2038
2039        let type_ids1 = [0, 1].into_iter().collect::<ScalarBuffer<i8>>();
2040        let offsets1 = [0, 0].into_iter().collect::<ScalarBuffer<i32>>();
2041
2042        let union_fields1 = [
2043            (0, Arc::new(Field::new("A", DataType::Int32, false))),
2044            (1, Arc::new(Field::new("B", DataType::Utf8, false))),
2045        ]
2046        .into_iter()
2047        .collect::<UnionFields>();
2048
2049        let children1 = vec![Arc::new(int_array1) as ArrayRef, Arc::new(str_array1)];
2050
2051        let array1 =
2052            UnionArray::try_new(union_fields1.clone(), type_ids1, Some(offsets1), children1)
2053                .unwrap();
2054
2055        // create second union as Sparse with same fields (Int32 and Utf8)
2056        let int_array2 = Int32Array::from(vec![Some(3), None]);
2057        let str_array2 = StringArray::from(vec![None, Some("c")]);
2058
2059        let type_ids2 = [0, 1].into_iter().collect::<ScalarBuffer<i8>>();
2060
2061        let children2 = vec![Arc::new(int_array2) as ArrayRef, Arc::new(str_array2)];
2062
2063        let array2 = UnionArray::try_new(union_fields1, type_ids2, None, children2).unwrap();
2064
2065        let opts = SortOptions::default();
2066
2067        let Result::Err(ArrowError::InvalidArgumentError(out)) =
2068            make_comparator(&array1, &array2, opts)
2069        else {
2070            panic!("expected error when making comparator of union arrays with different modes");
2071        };
2072
2073        assert_eq!(
2074            &out,
2075            "Cannot compare UnionArrays with different modes: left=Dense, right=Sparse"
2076        );
2077    }
2078
2079    #[test]
2080    fn test_null_array_cmp() {
2081        let a = NullArray::new(3);
2082        let b = NullArray::new(3);
2083        let cmp = make_comparator(&a, &b, SortOptions::default()).unwrap();
2084
2085        assert_eq!(cmp(0, 0), Ordering::Equal);
2086        assert_eq!(cmp(0, 1), Ordering::Equal);
2087        assert_eq!(cmp(2, 0), Ordering::Equal);
2088    }
2089
2090    #[test]
2091    fn test_run_end_encoded_int32() {
2092        // Create RunEndEncoded arrays:
2093        // array1: [1, 1, 2, 2, 2, 3]
2094        // run_ends1: [2, 5, 6], values1: [1, 2, 3]
2095        let run_ends1 = Int32Array::from(vec![2, 5, 6]);
2096        let values1 = Int32Array::from(vec![1, 2, 3]);
2097        let array1 = RunArray::<Int32Type>::try_new(&run_ends1, &values1).unwrap();
2098
2099        // array2: [1, 2, 2, 3, 3, 3]
2100        // run_ends2: [1, 3, 6], values2: [1, 2, 3]
2101        let run_ends2 = Int32Array::from(vec![1, 3, 6]);
2102        let values2 = Int32Array::from(vec![1, 2, 3]);
2103        let array2 = RunArray::<Int32Type>::try_new(&run_ends2, &values2).unwrap();
2104
2105        let cmp = make_comparator(&array1, &array2, SortOptions::default()).unwrap();
2106
2107        // array1[0] = 1, array2[0] = 1
2108        assert_eq!(cmp(0, 0), Ordering::Equal);
2109        // array1[0] = 1, array2[1] = 2
2110        assert_eq!(cmp(0, 1), Ordering::Less);
2111        // array1[2] = 2, array2[1] = 2
2112        assert_eq!(cmp(2, 1), Ordering::Equal);
2113        // array1[5] = 3, array2[5] = 3
2114        assert_eq!(cmp(5, 5), Ordering::Equal);
2115        // array1[1] = 1, array2[2] = 2
2116        assert_eq!(cmp(1, 2), Ordering::Less);
2117        // array1[4] = 2, array2[4] = 3
2118        assert_eq!(cmp(4, 4), Ordering::Less);
2119    }
2120
2121    #[test]
2122    fn test_run_end_encoded_with_nulls() {
2123        // Create RunEndEncoded arrays with nulls:
2124        // array1: [1, 1, null, null, 2]
2125        // run_ends1: [2, 4, 5], values1: [1, null, 2]
2126        let run_ends1 = Int32Array::from(vec![2, 4, 5]);
2127        let values1 = Int32Array::from(vec![Some(1), None, Some(2)]);
2128        let array1 = RunArray::<Int32Type>::try_new(&run_ends1, &values1).unwrap();
2129
2130        // array2: [null, 1, 1, 2, null]
2131        // run_ends2: [1, 3, 4, 5], values2: [null, 1, 2, null]
2132        let run_ends2 = Int32Array::from(vec![1, 3, 4, 5]);
2133        let values2 = Int32Array::from(vec![None, Some(1), Some(2), None]);
2134        let array2 = RunArray::<Int32Type>::try_new(&run_ends2, &values2).unwrap();
2135
2136        let opts = SortOptions::default();
2137        let cmp = make_comparator(&array1, &array2, opts).unwrap();
2138
2139        // array1[0] = 1, array2[1] = 1
2140        assert_eq!(cmp(0, 1), Ordering::Equal);
2141        // array1[2] = null, array2[0] = null
2142        assert_eq!(cmp(2, 0), Ordering::Equal);
2143        // array1[0] = 1, array2[0] = null (nulls first by default)
2144        assert_eq!(cmp(0, 0), Ordering::Greater);
2145        // array1[2] = null, array2[1] = 1
2146        assert_eq!(cmp(2, 1), Ordering::Less);
2147    }
2148
2149    #[test]
2150    fn test_run_end_encoded_int16() {
2151        // Test with Int16 run ends
2152        let run_ends1 = Int16Array::from(vec![3_i16, 5, 6]);
2153        let values1 = StringArray::from(vec!["a", "b", "c"]);
2154        let array1 = RunArray::<Int16Type>::try_new(&run_ends1, &values1).unwrap();
2155
2156        let run_ends2 = Int16Array::from(vec![2_i16, 4, 6]);
2157        let values2 = StringArray::from(vec!["a", "b", "c"]);
2158        let array2 = RunArray::<Int16Type>::try_new(&run_ends2, &values2).unwrap();
2159
2160        let cmp = make_comparator(&array1, &array2, SortOptions::default()).unwrap();
2161
2162        // array1: [a, a, a, b, b, c]
2163        // array2: [a, a, b, b, c, c]
2164        assert_eq!(cmp(0, 0), Ordering::Equal); // a vs a
2165        assert_eq!(cmp(2, 2), Ordering::Less); // a vs b
2166        assert_eq!(cmp(3, 2), Ordering::Equal); // b vs b
2167        assert_eq!(cmp(5, 4), Ordering::Equal); // c vs c
2168    }
2169
2170    #[test]
2171    fn test_run_end_encoded_int64() {
2172        // Test with Int64 run ends
2173        let run_ends1 = Int64Array::from(vec![2_i64, 4, 6]);
2174        let values1 = Int64Array::from(vec![10_i64, 20, 30]);
2175        let array1 = RunArray::<Int64Type>::try_new(&run_ends1, &values1).unwrap();
2176
2177        let run_ends2 = Int64Array::from(vec![3_i64, 5, 6]);
2178        let values2 = Int64Array::from(vec![10_i64, 20, 30]);
2179        let array2 = RunArray::<Int64Type>::try_new(&run_ends2, &values2).unwrap();
2180
2181        let cmp = make_comparator(&array1, &array2, SortOptions::default()).unwrap();
2182
2183        // array1: [10, 10, 20, 20, 30, 30]
2184        // array2: [10, 10, 10, 20, 20, 30]
2185        assert_eq!(cmp(0, 0), Ordering::Equal); // 10 vs 10
2186        assert_eq!(cmp(1, 2), Ordering::Equal); // 10 vs 10
2187        assert_eq!(cmp(2, 3), Ordering::Equal); // 20 vs 20
2188        assert_eq!(cmp(4, 4), Ordering::Greater); // 30 vs 20
2189    }
2190
2191    #[test]
2192    fn test_run_end_encoded_sliced() {
2193        // Create a RunEndEncoded array and slice it:
2194        // original: [1, 1, 2, 2, 2, 3, 3, 4]
2195        // run_ends: [2, 5, 7, 8], values: [1, 2, 3, 4]
2196        let run_ends = Int32Array::from(vec![2, 5, 7, 8]);
2197        let values = Int32Array::from(vec![1, 2, 3, 4]);
2198        let array = RunArray::<Int32Type>::try_new(&run_ends, &values).unwrap();
2199
2200        // slice1 = array[1..5] => [1, 2, 2, 2]
2201        let slice1 = array.slice(1, 4);
2202        // slice2 = array[3..7] => [2, 2, 3, 3]
2203        let slice2 = array.slice(3, 4);
2204
2205        let cmp = make_comparator(&slice1, &slice2, SortOptions::default()).unwrap();
2206
2207        // slice1[0]=1, slice2[0]=2
2208        assert_eq!(cmp(0, 0), Ordering::Less);
2209        // slice1[1]=2, slice2[0]=2
2210        assert_eq!(cmp(1, 0), Ordering::Equal);
2211        // slice1[3]=2, slice2[2]=3
2212        assert_eq!(cmp(3, 2), Ordering::Less);
2213        // slice1[1]=2, slice2[3]=3
2214        assert_eq!(cmp(1, 3), Ordering::Less);
2215
2216        // Compare a sliced array with an unsliced array
2217        let run_ends2 = Int32Array::from(vec![2, 4]);
2218        let values2 = Int32Array::from(vec![1, 2]);
2219        let array2 = RunArray::<Int32Type>::try_new(&run_ends2, &values2).unwrap();
2220
2221        let cmp = make_comparator(&slice1, &array2, SortOptions::default()).unwrap();
2222
2223        // slice1[0]=1, array2[0]=1
2224        assert_eq!(cmp(0, 0), Ordering::Equal);
2225        // slice1[1]=2, array2[1]=1
2226        assert_eq!(cmp(1, 1), Ordering::Greater);
2227        // slice1[3]=2, array2[3]=2
2228        assert_eq!(cmp(3, 3), Ordering::Equal);
2229    }
2230
2231    #[test]
2232    fn test_run_end_encoded_sliced_with_nulls() {
2233        // Create a RunEndEncoded array with nulls:
2234        // original: [1, 1, null, null, 2, 2, null, 3]
2235        // run_ends: [2, 4, 6, 7, 8], values: [1, null, 2, null, 3]
2236        let run_ends = Int32Array::from(vec![2, 4, 6, 7, 8]);
2237        let values = Int32Array::from(vec![Some(1), None, Some(2), None, Some(3)]);
2238        let array = RunArray::<Int32Type>::try_new(&run_ends, &values).unwrap();
2239
2240        // slice1 = array[1..6] => [1, null, null, 2, 2]
2241        let slice1 = array.slice(1, 5);
2242        // slice2 = array[3..8] => [null, 2, 2, null, 3]
2243        let slice2 = array.slice(3, 5);
2244
2245        let opts = SortOptions::default(); // nulls_first=true, descending=false
2246        let cmp = make_comparator(&slice1, &slice2, opts).unwrap();
2247
2248        // slice1[0]=1, slice2[0]=null
2249        assert_eq!(cmp(0, 0), Ordering::Greater);
2250        // slice1[1]=null, slice2[0]=null
2251        assert_eq!(cmp(1, 0), Ordering::Equal);
2252        // slice1[1]=null, slice2[1]=2
2253        assert_eq!(cmp(1, 1), Ordering::Less);
2254        // slice1[3]=2, slice2[1]=2
2255        assert_eq!(cmp(3, 1), Ordering::Equal);
2256        // slice1[4]=2, slice2[4]=3
2257        assert_eq!(cmp(4, 4), Ordering::Less);
2258        // slice1[3]=2, slice2[3]=null
2259        assert_eq!(cmp(3, 3), Ordering::Greater);
2260    }
2261
2262    #[test]
2263    fn test_run_end_encoded_different_types() {
2264        // Test with different run end types - should fail
2265        let run_ends1 = Int32Array::from(vec![2, 4, 6]);
2266        let values1 = Int32Array::from(vec![1, 2, 3]);
2267        let array1 = RunArray::<Int32Type>::try_new(&run_ends1, &values1).unwrap();
2268
2269        let run_ends2 = Int64Array::from(vec![2_i64, 4, 6]);
2270        let values2 = Int64Array::from(vec![1_i64, 2, 3]);
2271        let array2 = RunArray::<Int64Type>::try_new(&run_ends2, &values2).unwrap();
2272
2273        let result = make_comparator(&array1, &array2, SortOptions::default());
2274        assert!(result.is_err());
2275        let err = match result {
2276            Err(e) => e.to_string(),
2277            Ok(_) => panic!("Expected error"),
2278        };
2279        assert!(err.contains("Cannot compare RunEndEncoded arrays"));
2280    }
2281}