1#![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
58pub type DynComparator = Box<dyn Fn(usize, usize) -> Ordering + Send + Sync>;
60
61fn 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 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 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
520pub 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 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)] #[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 IntervalDayTimeType::make_value(0, 1000),
713 IntervalDayTimeType::make_value(1, 2),
715 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 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 IntervalYearMonthType::make_value(1, 0),
736 IntervalYearMonthType::make_value(0, 13),
738 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 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 IntervalMonthDayNanoType::make_value(0, 100, 0),
757 IntervalMonthDayNanoType::make_value(1, 0, 0),
759 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 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 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 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); assert_eq!(cmp(1, 0), Ordering::Less); assert_eq!(cmp(0, 1), Ordering::Greater); assert_eq!(cmp(1, 1), Ordering::Equal); }
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 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); assert_eq!(cmp(1, 0), Ordering::Greater); assert_eq!(cmp(0, 1), Ordering::Less); 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); assert_eq!(cmp(1, 0), Ordering::Less); assert_eq!(cmp(0, 1), Ordering::Greater); 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); assert_eq!(cmp(1, 0), Ordering::Greater); assert_eq!(cmp(0, 1), Ordering::Less); 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); assert_eq!(cmp(1, 0), Ordering::Greater); assert_eq!(cmp(0, 1), Ordering::Less); 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); assert_eq!(cmp(1, 0), Ordering::Less); assert_eq!(cmp(0, 1), Ordering::Greater); 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); assert_eq!(cmp(1, 0), Ordering::Greater); assert_eq!(cmp(0, 1), Ordering::Less); 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)); assert_eq!(Ordering::Equal, cmp(0, 3)); assert_eq!(Ordering::Greater, cmp(3, 3)); assert_eq!(Ordering::Greater, cmp(3, 1)); assert_eq!(Ordering::Greater, cmp(3, 2)); }
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 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 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 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 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 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 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 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 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 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, Ordering::Greater), (3, 0, Ordering::Less), (4, 0, Ordering::Less), ],
1486 );
1487
1488 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), ],
1502 );
1503
1504 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 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); assert_eq!(cmp(0, 0), Ordering::Greater); assert_eq!(cmp(1, 1), Ordering::Greater); assert_eq!(cmp(2, 2), Ordering::Less); assert_eq!(cmp(3, 0), Ordering::Less); assert_eq!(cmp(2, 0), Ordering::Equal); assert_eq!(cmp(3, 0), Ordering::Less); 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); assert_eq!(cmp(0, 0), Ordering::Greater); assert_eq!(cmp(1, 1), Ordering::Greater); assert_eq!(cmp(2, 2), Ordering::Less); assert_eq!(cmp(3, 0), Ordering::Less); assert_eq!(cmp(2, 0), Ordering::Equal); assert_eq!(cmp(3, 0), Ordering::Less); 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); assert_eq!(cmp(0, 0), Ordering::Less); assert_eq!(cmp(1, 1), Ordering::Less); assert_eq!(cmp(2, 2), Ordering::Greater); assert_eq!(cmp(3, 0), Ordering::Greater); assert_eq!(cmp(2, 0), Ordering::Equal); assert_eq!(cmp(3, 0), Ordering::Greater); 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); assert_eq!(cmp(0, 0), Ordering::Less); assert_eq!(cmp(1, 1), Ordering::Less); assert_eq!(cmp(2, 2), Ordering::Greater); assert_eq!(cmp(3, 0), Ordering::Greater); assert_eq!(cmp(2, 0), Ordering::Equal); assert_eq!(cmp(3, 0), Ordering::Greater); }
1623
1624 #[test]
1625 fn test_map() {
1626 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 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 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 map1_builder.append(true).unwrap();
1648
1649 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 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 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 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 map2_builder.keys().append_value("a");
1678 map2_builder.values().append_value(1);
1679 map2_builder.append(true).unwrap();
1680
1681 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 assert_eq!(cmp(0, 0), Ordering::Greater);
1696
1697 assert_eq!(cmp(1, 1), Ordering::Greater);
1700
1701 assert_eq!(cmp(0, 1), Ordering::Less);
1703
1704 assert_eq!(cmp(2, 2), Ordering::Less); assert_eq!(cmp(3, 3), Ordering::Greater); assert_eq!(cmp(3, 0), Ordering::Greater); assert_eq!(cmp(2, 0), Ordering::Less); let opts = SortOptions {
1717 descending: true,
1718 nulls_first: true,
1719 };
1720 let cmp = make_comparator(&map1, &map2, opts).unwrap();
1721
1722 assert_eq!(cmp(0, 0), Ordering::Less); assert_eq!(cmp(1, 1), Ordering::Less); assert_eq!(cmp(0, 1), Ordering::Greater); assert_eq!(cmp(3, 3), Ordering::Greater); assert_eq!(cmp(2, 2), Ordering::Greater); let opts = SortOptions {
1730 descending: false,
1731 nulls_first: false,
1732 };
1733 let cmp = make_comparator(&map1, &map2, opts).unwrap();
1734
1735 assert_eq!(cmp(0, 0), Ordering::Greater); assert_eq!(cmp(1, 1), Ordering::Greater); assert_eq!(cmp(3, 3), Ordering::Less); assert_eq!(cmp(2, 2), Ordering::Less); }
1741
1742 #[test]
1743 fn test_map_vs_list_consistency() {
1744 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 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 map1_builder.keys().append_value("x");
1759 map1_builder.values().append_value(10);
1760 map1_builder.append(true).unwrap();
1761
1762 map1_builder.append(true).unwrap();
1764
1765 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 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 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 map2_builder.keys().append_value("y");
1786 map2_builder.values().append_value(20);
1787 map2_builder.append(true).unwrap();
1788
1789 map2_builder.keys().append_value("d");
1791 map2_builder.values().append_value(4);
1792 map2_builder.append(true).unwrap();
1793
1794 map2_builder.append(false).unwrap();
1796
1797 let map2 = map2_builder.finish();
1798
1799 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 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 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 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 let cmp = make_comparator(&array1, &array2, opts).unwrap();
1886
1887 assert_eq!(cmp(0, 0), Ordering::Less); assert_eq!(cmp(0, 1), Ordering::Less); assert_eq!(cmp(1, 1), Ordering::Greater); assert_eq!(cmp(2, 0), Ordering::Equal); assert_eq!(cmp(3, 1), Ordering::Equal); assert_eq!(cmp(1, 3), Ordering::Less); 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); assert_eq!(cmp_desc(0, 1), Ordering::Greater); assert_eq!(cmp_desc(1, 1), Ordering::Less); }
1921
1922 #[test]
1923 fn test_sparse_union() {
1924 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 assert_eq!(cmp(0, 2), Ordering::Less); assert_eq!(cmp(0, 1), Ordering::Less); }
1950
1951 #[test]
1952 #[should_panic(expected = "index out of bounds")]
1953 fn test_union_out_of_bounds() {
1954 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 cmp(0, 3);
1977 }
1978
1979 #[test]
1980 fn test_union_incompatible_fields() {
1981 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 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 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 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 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 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 assert_eq!(cmp(0, 0), Ordering::Equal);
2109 assert_eq!(cmp(0, 1), Ordering::Less);
2111 assert_eq!(cmp(2, 1), Ordering::Equal);
2113 assert_eq!(cmp(5, 5), Ordering::Equal);
2115 assert_eq!(cmp(1, 2), Ordering::Less);
2117 assert_eq!(cmp(4, 4), Ordering::Less);
2119 }
2120
2121 #[test]
2122 fn test_run_end_encoded_with_nulls() {
2123 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 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 assert_eq!(cmp(0, 1), Ordering::Equal);
2141 assert_eq!(cmp(2, 0), Ordering::Equal);
2143 assert_eq!(cmp(0, 0), Ordering::Greater);
2145 assert_eq!(cmp(2, 1), Ordering::Less);
2147 }
2148
2149 #[test]
2150 fn test_run_end_encoded_int16() {
2151 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 assert_eq!(cmp(0, 0), Ordering::Equal); assert_eq!(cmp(2, 2), Ordering::Less); assert_eq!(cmp(3, 2), Ordering::Equal); assert_eq!(cmp(5, 4), Ordering::Equal); }
2169
2170 #[test]
2171 fn test_run_end_encoded_int64() {
2172 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 assert_eq!(cmp(0, 0), Ordering::Equal); assert_eq!(cmp(1, 2), Ordering::Equal); assert_eq!(cmp(2, 3), Ordering::Equal); assert_eq!(cmp(4, 4), Ordering::Greater); }
2190
2191 #[test]
2192 fn test_run_end_encoded_sliced() {
2193 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 let slice1 = array.slice(1, 4);
2202 let slice2 = array.slice(3, 4);
2204
2205 let cmp = make_comparator(&slice1, &slice2, SortOptions::default()).unwrap();
2206
2207 assert_eq!(cmp(0, 0), Ordering::Less);
2209 assert_eq!(cmp(1, 0), Ordering::Equal);
2211 assert_eq!(cmp(3, 2), Ordering::Less);
2213 assert_eq!(cmp(1, 3), Ordering::Less);
2215
2216 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 assert_eq!(cmp(0, 0), Ordering::Equal);
2225 assert_eq!(cmp(1, 1), Ordering::Greater);
2227 assert_eq!(cmp(3, 3), Ordering::Equal);
2229 }
2230
2231 #[test]
2232 fn test_run_end_encoded_sliced_with_nulls() {
2233 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 let slice1 = array.slice(1, 5);
2242 let slice2 = array.slice(3, 5);
2244
2245 let opts = SortOptions::default(); let cmp = make_comparator(&slice1, &slice2, opts).unwrap();
2247
2248 assert_eq!(cmp(0, 0), Ordering::Greater);
2250 assert_eq!(cmp(1, 0), Ordering::Equal);
2252 assert_eq!(cmp(1, 1), Ordering::Less);
2254 assert_eq!(cmp(3, 1), Ordering::Equal);
2256 assert_eq!(cmp(4, 4), Ordering::Less);
2258 assert_eq!(cmp(3, 3), Ordering::Greater);
2260 }
2261
2262 #[test]
2263 fn test_run_end_encoded_different_types() {
2264 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}