Skip to main content

arrow_arith/
aggregate.rs

1// Licensed to the Apache Software Foundation (ASF) under one
2// or more contributor license agreements.  See the NOTICE file
3// distributed with this work for additional information
4// regarding copyright ownership.  The ASF licenses this file
5// to you under the Apache License, Version 2.0 (the
6// "License"); you may not use this file except in compliance
7// with the License.  You may obtain a copy of the License at
8//
9//   http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing,
12// software distributed under the License is distributed on an
13// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14// KIND, either express or implied.  See the License for the
15// specific language governing permissions and limitations
16// under the License.
17
18//! Defines aggregations over Arrow arrays.
19
20use arrow_array::cast::*;
21use arrow_array::iterator::ArrayIter;
22use arrow_array::*;
23use arrow_buffer::NullBuffer;
24use arrow_data::bit_iterator::try_for_each_valid_idx;
25use arrow_schema::*;
26use std::cmp::{self, Ordering};
27use std::ops::{BitAnd, BitOr, BitXor};
28use types::ByteViewType;
29
30/// An accumulator for primitive numeric values.
31trait NumericAccumulator<T: ArrowNativeTypeOp>: Copy + Default {
32    /// Accumulate a non-null value.
33    fn accumulate(&mut self, value: T);
34    /// Accumulate a nullable values.
35    /// If `valid` is false the `value` should not affect the accumulator state.
36    fn accumulate_nullable(&mut self, value: T, valid: bool);
37    /// Merge another accumulator into this accumulator
38    fn merge(&mut self, other: Self);
39    /// Return the aggregated value.
40    fn finish(&mut self) -> T;
41}
42
43/// Helper for branchlessly selecting either `a` or `b` based on the boolean `m`.
44/// After verifying the generated assembly this can be a simple `if`.
45#[inline(always)]
46fn select<T: Copy>(m: bool, a: T, b: T) -> T {
47    if m { a } else { b }
48}
49
50#[derive(Clone, Copy)]
51struct SumAccumulator<T: ArrowNativeTypeOp> {
52    sum: T,
53}
54
55impl<T: ArrowNativeTypeOp> Default for SumAccumulator<T> {
56    fn default() -> Self {
57        Self { sum: T::ZERO }
58    }
59}
60
61impl<T: ArrowNativeTypeOp> NumericAccumulator<T> for SumAccumulator<T> {
62    fn accumulate(&mut self, value: T) {
63        self.sum = self.sum.add_wrapping(value);
64    }
65
66    fn accumulate_nullable(&mut self, value: T, valid: bool) {
67        let sum = self.sum;
68        self.sum = select(valid, sum.add_wrapping(value), sum)
69    }
70
71    fn merge(&mut self, other: Self) {
72        self.sum = self.sum.add_wrapping(other.sum);
73    }
74
75    fn finish(&mut self) -> T {
76        self.sum
77    }
78}
79
80#[derive(Clone, Copy)]
81struct ProductAccumulator<T: ArrowNativeTypeOp> {
82    product: T,
83}
84
85impl<T: ArrowNativeTypeOp> Default for ProductAccumulator<T> {
86    fn default() -> Self {
87        Self { product: T::ONE }
88    }
89}
90
91impl<T: ArrowNativeTypeOp> NumericAccumulator<T> for ProductAccumulator<T> {
92    fn accumulate(&mut self, value: T) {
93        self.product = self.product.mul_wrapping(value);
94    }
95
96    fn accumulate_nullable(&mut self, value: T, valid: bool) {
97        let product = self.product;
98        self.product = select(valid, product.mul_wrapping(value), product)
99    }
100
101    fn merge(&mut self, other: Self) {
102        self.product = self.product.mul_wrapping(other.product);
103    }
104
105    fn finish(&mut self) -> T {
106        self.product
107    }
108}
109
110#[derive(Clone, Copy)]
111struct MinAccumulator<T: ArrowNativeTypeOp> {
112    min: T,
113}
114
115impl<T: ArrowNativeTypeOp> Default for MinAccumulator<T> {
116    fn default() -> Self {
117        Self {
118            min: T::MAX_TOTAL_ORDER,
119        }
120    }
121}
122
123impl<T: ArrowNativeTypeOp> NumericAccumulator<T> for MinAccumulator<T> {
124    fn accumulate(&mut self, value: T) {
125        let min = self.min;
126        self.min = select(value.is_lt(min), value, min);
127    }
128
129    fn accumulate_nullable(&mut self, value: T, valid: bool) {
130        let min = self.min;
131        let is_lt = valid & value.is_lt(min);
132        self.min = select(is_lt, value, min);
133    }
134
135    fn merge(&mut self, other: Self) {
136        self.accumulate(other.min)
137    }
138
139    fn finish(&mut self) -> T {
140        self.min
141    }
142}
143
144#[derive(Clone, Copy)]
145struct MaxAccumulator<T: ArrowNativeTypeOp> {
146    max: T,
147}
148
149impl<T: ArrowNativeTypeOp> Default for MaxAccumulator<T> {
150    fn default() -> Self {
151        Self {
152            max: T::MIN_TOTAL_ORDER,
153        }
154    }
155}
156
157impl<T: ArrowNativeTypeOp> NumericAccumulator<T> for MaxAccumulator<T> {
158    fn accumulate(&mut self, value: T) {
159        let max = self.max;
160        self.max = select(value.is_gt(max), value, max);
161    }
162
163    fn accumulate_nullable(&mut self, value: T, valid: bool) {
164        let max = self.max;
165        let is_gt = value.is_gt(max) & valid;
166        self.max = select(is_gt, value, max);
167    }
168
169    fn merge(&mut self, other: Self) {
170        self.accumulate(other.max)
171    }
172
173    fn finish(&mut self) -> T {
174        self.max
175    }
176}
177
178fn reduce_accumulators<T: ArrowNativeTypeOp, A: NumericAccumulator<T>, const LANES: usize>(
179    mut acc: [A; LANES],
180) -> A {
181    assert!(LANES > 0 && LANES.is_power_of_two());
182    let mut len = LANES;
183
184    // attempt at tree reduction, unfortunately llvm does not fully recognize this pattern,
185    // but the generated code is still a little faster than purely sequential reduction for floats.
186    while len >= 2 {
187        let mid = len / 2;
188        let (h, t) = acc[..len].split_at_mut(mid);
189
190        for i in 0..mid {
191            h[i].merge(t[i]);
192        }
193        len /= 2;
194    }
195    acc[0]
196}
197
198#[inline(always)]
199fn aggregate_nonnull_chunk<T: ArrowNativeTypeOp, A: NumericAccumulator<T>, const LANES: usize>(
200    acc: &mut [A; LANES],
201    values: &[T; LANES],
202) {
203    for i in 0..LANES {
204        acc[i].accumulate(values[i]);
205    }
206}
207
208#[inline(always)]
209fn aggregate_nullable_chunk<T: ArrowNativeTypeOp, A: NumericAccumulator<T>, const LANES: usize>(
210    acc: &mut [A; LANES],
211    values: &[T; LANES],
212    validity: u64,
213) {
214    let mut bit = 1;
215    for i in 0..LANES {
216        acc[i].accumulate_nullable(values[i], (validity & bit) != 0);
217        bit <<= 1;
218    }
219}
220
221fn aggregate_nonnull_simple<T: ArrowNativeTypeOp, A: NumericAccumulator<T>>(values: &[T]) -> T {
222    values
223        .iter()
224        .copied()
225        .fold(A::default(), |mut a, b| {
226            a.accumulate(b);
227            a
228        })
229        .finish()
230}
231
232#[inline(never)]
233fn aggregate_nonnull_lanes<T: ArrowNativeTypeOp, A: NumericAccumulator<T>, const LANES: usize>(
234    values: &[T],
235) -> T {
236    // aggregating into multiple independent accumulators allows the compiler to use vector registers
237    // with a single accumulator the compiler would not be allowed to reorder floating point addition
238    let mut acc = [A::default(); LANES];
239    let (chunks, remainder) = values.as_chunks::<LANES>();
240    chunks.iter().for_each(|chunk| {
241        aggregate_nonnull_chunk(&mut acc, chunk);
242    });
243
244    for i in 0..remainder.len() {
245        acc[i].accumulate(remainder[i]);
246    }
247
248    reduce_accumulators(acc).finish()
249}
250
251#[inline(never)]
252fn aggregate_nullable_lanes<T: ArrowNativeTypeOp, A: NumericAccumulator<T>, const LANES: usize>(
253    values: &[T],
254    validity: &NullBuffer,
255) -> T {
256    assert!(LANES > 0 && 64 % LANES == 0);
257    assert_eq!(values.len(), validity.len());
258
259    // aggregating into multiple independent accumulators allows the compiler to use vector registers
260    let mut acc = [A::default(); LANES];
261    // we process 64 bits of validity at a time
262    let (values_chunks, remainder) = values.as_chunks::<64>();
263    let validity_chunks = validity.inner().bit_chunks();
264    let mut validity_chunks_iter = validity_chunks.iter();
265
266    values_chunks.iter().for_each(|chunk| {
267        // Safety: we asserted that values and validity have the same length and trust the iterator impl
268        let mut validity = unsafe { validity_chunks_iter.next().unwrap_unchecked() };
269        // chunk further based on the number of vector lanes
270        chunk.as_chunks::<LANES>().0.iter().for_each(|chunk| {
271            aggregate_nullable_chunk(&mut acc, chunk, validity);
272            validity >>= LANES;
273        });
274    });
275
276    if !remainder.is_empty() {
277        let mut validity = validity_chunks.remainder_bits();
278
279        let (remainder_chunks, remainder) = remainder.as_chunks::<LANES>();
280        remainder_chunks.iter().for_each(|chunk| {
281            aggregate_nullable_chunk(&mut acc, chunk, validity);
282            validity >>= LANES;
283        });
284
285        if !remainder.is_empty() {
286            let mut bit = 1;
287            for i in 0..remainder.len() {
288                acc[i].accumulate_nullable(remainder[i], (validity & bit) != 0);
289                bit <<= 1;
290            }
291        }
292    }
293
294    reduce_accumulators(acc).finish()
295}
296
297/// The preferred vector size in bytes for the target platform.
298/// Note that the avx512 target feature is still unstable and this also means it is not detected on stable rust.
299const PREFERRED_VECTOR_SIZE: usize =
300    if cfg!(all(target_arch = "x86_64", target_feature = "avx512f")) {
301        64
302    } else if cfg!(all(target_arch = "x86_64", target_feature = "avx")) {
303        32
304    } else {
305        16
306    };
307
308/// non-nullable aggregation requires fewer temporary registers so we can use more of them for accumulators
309const PREFERRED_VECTOR_SIZE_NON_NULL: usize = PREFERRED_VECTOR_SIZE * 2;
310
311/// Generic aggregation for any primitive type.
312/// Returns None if there are no non-null values in `array`.
313fn aggregate<T: ArrowNativeTypeOp, P: ArrowPrimitiveType<Native = T>, A: NumericAccumulator<T>>(
314    array: &PrimitiveArray<P>,
315) -> Option<T> {
316    let null_count = array.null_count();
317    if null_count == array.len() {
318        return None;
319    }
320    let values = array.values().as_ref();
321    match array.nulls() {
322        Some(nulls) if null_count > 0 => {
323            // const generics depending on a generic type parameter are not supported
324            // so we have to match and call aggregate with the corresponding constant
325            match PREFERRED_VECTOR_SIZE / std::mem::size_of::<T>() {
326                64 => Some(aggregate_nullable_lanes::<T, A, 64>(values, nulls)),
327                32 => Some(aggregate_nullable_lanes::<T, A, 32>(values, nulls)),
328                16 => Some(aggregate_nullable_lanes::<T, A, 16>(values, nulls)),
329                8 => Some(aggregate_nullable_lanes::<T, A, 8>(values, nulls)),
330                4 => Some(aggregate_nullable_lanes::<T, A, 4>(values, nulls)),
331                2 => Some(aggregate_nullable_lanes::<T, A, 2>(values, nulls)),
332                _ => Some(aggregate_nullable_lanes::<T, A, 1>(values, nulls)),
333            }
334        }
335        _ => {
336            let is_float = matches!(
337                array.data_type(),
338                DataType::Float16 | DataType::Float32 | DataType::Float64
339            );
340            if is_float {
341                match PREFERRED_VECTOR_SIZE_NON_NULL / std::mem::size_of::<T>() {
342                    64 => Some(aggregate_nonnull_lanes::<T, A, 64>(values)),
343                    32 => Some(aggregate_nonnull_lanes::<T, A, 32>(values)),
344                    16 => Some(aggregate_nonnull_lanes::<T, A, 16>(values)),
345                    8 => Some(aggregate_nonnull_lanes::<T, A, 8>(values)),
346                    4 => Some(aggregate_nonnull_lanes::<T, A, 4>(values)),
347                    2 => Some(aggregate_nonnull_lanes::<T, A, 2>(values)),
348                    _ => Some(aggregate_nonnull_simple::<T, A>(values)),
349                }
350            } else {
351                // for non-null integers its better to not chunk ourselves and instead
352                // let llvm fully handle loop unrolling and vectorization
353                Some(aggregate_nonnull_simple::<T, A>(values))
354            }
355        }
356    }
357}
358
359/// Returns the minimum value in the boolean array.
360///
361/// # Example
362/// ```
363/// # use arrow_array::BooleanArray;
364/// # use arrow_arith::aggregate::min_boolean;
365/// let a = BooleanArray::from(vec![Some(true), None, Some(false)]);
366/// assert_eq!(min_boolean(&a), Some(false))
367/// ```
368pub fn min_boolean(array: &BooleanArray) -> Option<bool> {
369    // short circuit if all nulls / zero length array
370    if array.null_count() == array.len() {
371        return None;
372    }
373
374    // Note the min bool is false (0), so short circuit as soon as we see it
375    match array.nulls() {
376        None => {
377            let bit_chunks = array.values().bit_chunks();
378            if bit_chunks.iter().any(|x| {
379                // u64::MAX has all bits set, so if the value is not that, then there is a false
380                x != u64::MAX
381            }) {
382                return Some(false);
383            }
384            // If the remainder bits are not all set, then there is a false
385            if bit_chunks.remainder_bits().count_ones() as usize != bit_chunks.remainder_len() {
386                Some(false)
387            } else {
388                Some(true)
389            }
390        }
391        Some(nulls) => {
392            let validity_chunks = nulls.inner().bit_chunks();
393            let value_chunks = array.values().bit_chunks();
394
395            if value_chunks
396                .iter()
397                .zip(validity_chunks.iter())
398                .any(|(value, validity)| {
399                    // We are looking for a false value, but because applying the validity mask
400                    // can create a false for a true value (e.g. value: true, validity: false), we instead invert the value, so that we have to look for a true.
401                    (!value & validity) != 0
402                })
403            {
404                return Some(false);
405            }
406
407            // Same trick as above: Instead of looking for a false, we invert the value bits and look for a true
408            if (!value_chunks.remainder_bits() & validity_chunks.remainder_bits()) != 0 {
409                Some(false)
410            } else {
411                Some(true)
412            }
413        }
414    }
415}
416
417/// Returns the maximum value in the boolean array
418///
419/// # Example
420/// ```
421/// # use arrow_array::BooleanArray;
422/// # use arrow_arith::aggregate::max_boolean;
423/// let a = BooleanArray::from(vec![Some(true), None, Some(false)]);
424/// assert_eq!(max_boolean(&a), Some(true))
425/// ```
426pub fn max_boolean(array: &BooleanArray) -> Option<bool> {
427    // short circuit if all nulls / zero length array
428    if array.null_count() == array.len() {
429        return None;
430    }
431
432    // Note the max bool is true (1), so short circuit as soon as we see it
433    match array.nulls() {
434        None => array
435            .values()
436            .bit_chunks()
437            .iter_padded()
438            // We found a true if any bit is set
439            .map(|x| x != 0)
440            .find(|b| *b)
441            .or(Some(false)),
442        Some(nulls) => {
443            let validity_chunks = nulls.inner().bit_chunks().iter_padded();
444            let value_chunks = array.values().bit_chunks().iter_padded();
445            value_chunks
446                .zip(validity_chunks)
447                // We found a true if the value bit is 1, AND the validity bit is 1 for any bits in the chunk
448                .map(|(value_bits, validity_bits)| (value_bits & validity_bits) != 0)
449                .find(|b| *b)
450                .or(Some(false))
451        }
452    }
453}
454
455/// Helper to compute min/max of [`ArrayAccessor`].
456fn min_max_helper<T, A: ArrayAccessor<Item = T>, F>(array: A, cmp: F) -> Option<T>
457where
458    F: Fn(&T, &T) -> bool,
459{
460    let nulls = array.logical_nulls();
461    let null_count = nulls.as_ref().map_or(0, NullBuffer::null_count);
462    if null_count == array.len() {
463        None
464    } else if null_count == 0 {
465        // JUSTIFICATION
466        //  Benefit:  ~8% speedup
467        //  Soundness: `i` is always within the array bounds
468        (0..array.len())
469            .map(|i| unsafe { array.value_unchecked(i) })
470            .reduce(|acc, item| if cmp(&acc, &item) { item } else { acc })
471    } else {
472        let nulls = nulls.unwrap();
473        unsafe {
474            let idx = nulls.valid_indices().reduce(|acc_idx, idx| {
475                let acc = array.value_unchecked(acc_idx);
476                let item = array.value_unchecked(idx);
477                if cmp(&acc, &item) { idx } else { acc_idx }
478            });
479            idx.map(|idx| array.value_unchecked(idx))
480        }
481    }
482}
483
484/// Helper to compute min/max of [`GenericByteViewArray<T>`].
485/// The specialized min/max leverages the inlined values to compare the byte views.
486/// `swap_cond` is the condition to swap current min/max with the new value.
487/// For example, `Ordering::Greater` for max and `Ordering::Less` for min.
488fn min_max_view_helper<T: ByteViewType>(
489    array: &GenericByteViewArray<T>,
490    swap_cond: cmp::Ordering,
491) -> Option<&T::Native> {
492    let null_count = array.null_count();
493    if null_count == array.len() {
494        None
495    } else if null_count == 0 {
496        let target_idx = (0..array.len()).reduce(|acc, item| {
497            // SAFETY:  array's length is correct so item is within bounds
498            let cmp = unsafe { GenericByteViewArray::compare_unchecked(array, item, array, acc) };
499            if cmp == swap_cond { item } else { acc }
500        });
501        // SAFETY: idx came from valid range `0..array.len()`
502        unsafe { target_idx.map(|idx| array.value_unchecked(idx)) }
503    } else {
504        let nulls = array.nulls().unwrap();
505
506        let target_idx = nulls.valid_indices().reduce(|acc_idx, idx| {
507            let cmp =
508                unsafe { GenericByteViewArray::compare_unchecked(array, idx, array, acc_idx) };
509            if cmp == swap_cond { idx } else { acc_idx }
510        });
511
512        // SAFETY: idx came from valid range `0..array.len()`
513        unsafe { target_idx.map(|idx| array.value_unchecked(idx)) }
514    }
515}
516
517/// Returns the maximum value in the binary array, according to the natural order.
518pub fn max_binary<T: OffsetSizeTrait>(array: &GenericBinaryArray<T>) -> Option<&[u8]> {
519    min_max_helper::<&[u8], _, _>(array, |a, b| *a < *b)
520}
521
522/// Returns the maximum value in the binary view array, according to the natural order.
523pub fn max_binary_view(array: &BinaryViewArray) -> Option<&[u8]> {
524    min_max_view_helper(array, Ordering::Greater)
525}
526
527/// Returns the maximum value in the fixed size binary array, according to the natural order.
528pub fn max_fixed_size_binary(array: &FixedSizeBinaryArray) -> Option<&[u8]> {
529    min_max_helper::<&[u8], _, _>(array, |a, b| *a < *b)
530}
531
532/// Returns the minimum value in the binary array, according to the natural order.
533pub fn min_binary<T: OffsetSizeTrait>(array: &GenericBinaryArray<T>) -> Option<&[u8]> {
534    min_max_helper::<&[u8], _, _>(array, |a, b| *a > *b)
535}
536
537/// Returns the minimum value in the binary view array, according to the natural order.
538pub fn min_binary_view(array: &BinaryViewArray) -> Option<&[u8]> {
539    min_max_view_helper(array, Ordering::Less)
540}
541
542/// Returns the minimum value in the fixed size binary array, according to the natural order.
543pub fn min_fixed_size_binary(array: &FixedSizeBinaryArray) -> Option<&[u8]> {
544    min_max_helper::<&[u8], _, _>(array, |a, b| *a > *b)
545}
546
547/// Returns the maximum value in the string array, according to the natural order.
548pub fn max_string<T: OffsetSizeTrait>(array: &GenericStringArray<T>) -> Option<&str> {
549    min_max_helper::<&str, _, _>(array, |a, b| *a < *b)
550}
551
552/// Returns the maximum value in the string view array, according to the natural order.
553pub fn max_string_view(array: &StringViewArray) -> Option<&str> {
554    min_max_view_helper(array, Ordering::Greater)
555}
556
557/// Returns the minimum value in the string array, according to the natural order.
558pub fn min_string<T: OffsetSizeTrait>(array: &GenericStringArray<T>) -> Option<&str> {
559    min_max_helper::<&str, _, _>(array, |a, b| *a > *b)
560}
561
562/// Returns the minimum value in the string view array, according to the natural order.
563pub fn min_string_view(array: &StringViewArray) -> Option<&str> {
564    min_max_view_helper(array, Ordering::Less)
565}
566
567/// Returns the sum of values in the array.
568///
569/// This doesn't detect overflow. Once overflowing, the result will wrap around.
570/// For an overflow-checking variant, use [`sum_array_checked`] instead.
571pub fn sum_array<T: ArrowNumericType, A: ArrayAccessor<Item = T::Native>>(
572    array: A,
573) -> Option<T::Native> {
574    match array.data_type() {
575        DataType::Dictionary(_, _) => {
576            let logical_null_count = array.logical_null_count();
577
578            if logical_null_count == array.len() {
579                return None;
580            }
581
582            let iter = ArrayIter::new(array);
583            let sum = iter
584                .into_iter()
585                .fold(T::default_value(), |accumulator, value| {
586                    if let Some(value) = value {
587                        accumulator.add_wrapping(value)
588                    } else {
589                        accumulator
590                    }
591                });
592
593            Some(sum)
594        }
595        DataType::RunEndEncoded(run_ends, _) => match run_ends.data_type() {
596            DataType::Int16 => ree::sum_wrapping::<types::Int16Type, T>(&array),
597            DataType::Int32 => ree::sum_wrapping::<types::Int32Type, T>(&array),
598            DataType::Int64 => ree::sum_wrapping::<types::Int64Type, T>(&array),
599            _ => unreachable!(),
600        },
601        _ => sum::<T>(as_primitive_array(&array)),
602    }
603}
604
605/// Returns the sum of values in the array.
606///
607/// This detects overflow and returns an `Err` for that. For an non-overflow-checking variant,
608/// use [`sum_array`] instead.
609/// Additionally returns an `Err` on run-end-encoded arrays with a provided
610/// values type parameter that is incorrect.
611pub fn sum_array_checked<T: ArrowNumericType, A: ArrayAccessor<Item = T::Native>>(
612    array: A,
613) -> Result<Option<T::Native>, ArrowError> {
614    match array.data_type() {
615        DataType::Dictionary(_, _) => {
616            let logical_null_count = array.logical_null_count();
617
618            if logical_null_count == array.len() {
619                return Ok(None);
620            }
621
622            let iter = ArrayIter::new(array);
623            let sum = iter
624                .into_iter()
625                .try_fold(T::default_value(), |accumulator, value| {
626                    if let Some(value) = value {
627                        accumulator.add_checked(value)
628                    } else {
629                        Ok(accumulator)
630                    }
631                })?;
632
633            Ok(Some(sum))
634        }
635        DataType::RunEndEncoded(run_ends, _) => match run_ends.data_type() {
636            DataType::Int16 => ree::sum_checked::<types::Int16Type, T>(&array),
637            DataType::Int32 => ree::sum_checked::<types::Int32Type, T>(&array),
638            DataType::Int64 => ree::sum_checked::<types::Int64Type, T>(&array),
639            _ => unreachable!(),
640        },
641        _ => sum_checked::<T>(as_primitive_array(&array)),
642    }
643}
644
645// Logic for summing run-end-encoded arrays.
646mod ree {
647    use std::convert::Infallible;
648
649    use arrow_array::cast::AsArray;
650    use arrow_array::types::RunEndIndexType;
651    use arrow_array::{Array, ArrowNativeTypeOp, ArrowNumericType, PrimitiveArray, TypedRunArray};
652    use arrow_buffer::ArrowNativeType;
653    use arrow_schema::ArrowError;
654
655    /// Downcasts an array to a TypedRunArray.
656    fn downcast<I: RunEndIndexType, V: ArrowNumericType>(
657        array: &dyn Array,
658    ) -> Option<TypedRunArray<'_, I, PrimitiveArray<V>>> {
659        let array = array.as_run_opt::<I>()?;
660        // We only support RunArray wrapping primitive types.
661        array.downcast::<PrimitiveArray<V>>()
662    }
663
664    /// Computes the sum (wrapping) of the array values.
665    pub(super) fn sum_wrapping<I: RunEndIndexType, V: ArrowNumericType>(
666        array: &dyn Array,
667    ) -> Option<V::Native> {
668        let ree = downcast::<I, V>(array)?;
669        let Ok(sum) = fold(ree, |acc, val, len| -> Result<V::Native, Infallible> {
670            Ok(acc.add_wrapping(val.mul_wrapping(V::Native::usize_as(len))))
671        });
672        sum
673    }
674
675    /// Computes the sum (erroring on overflow) of the array values.
676    pub(super) fn sum_checked<I: RunEndIndexType, V: ArrowNumericType>(
677        array: &dyn Array,
678    ) -> Result<Option<V::Native>, ArrowError> {
679        let Some(ree) = downcast::<I, V>(array) else {
680            return Err(ArrowError::InvalidArgumentError(
681                "Input run array values are not a PrimitiveArray".to_string(),
682            ));
683        };
684        fold(ree, |acc, val, len| -> Result<V::Native, ArrowError> {
685            let Some(len) = V::Native::from_usize(len) else {
686                return Err(ArrowError::ArithmeticOverflow(format!(
687                    "Cannot convert a run-end index ({:?}) to the value type ({})",
688                    len,
689                    std::any::type_name::<V::Native>()
690                )));
691            };
692            acc.add_checked(val.mul_checked(len)?)
693        })
694    }
695
696    /// Folds over the values in a run-end-encoded array.
697    fn fold<I: RunEndIndexType, V: ArrowNumericType, F, E>(
698        array: TypedRunArray<'_, I, PrimitiveArray<V>>,
699        mut f: F,
700    ) -> Result<Option<V::Native>, E>
701    where
702        F: FnMut(V::Native, V::Native, usize) -> Result<V::Native, E>,
703    {
704        let run_ends = array.run_ends().sliced_values();
705
706        let values_slice = array.run_array().values_slice();
707        let values = values_slice
708            .as_any()
709            .downcast_ref::<PrimitiveArray<V>>()
710            // Safety: we know the values array is PrimitiveArray<V>.
711            .unwrap();
712
713        let mut prev_end = 0;
714        let mut acc = V::Native::ZERO;
715        let mut has_non_null_value = false;
716
717        for (run_end, value) in run_ends.zip(values) {
718            let current_run_end = run_end.as_usize();
719            let run_length = current_run_end - prev_end;
720
721            if let Some(value) = value {
722                has_non_null_value = true;
723                acc = f(acc, value, run_length)?;
724            }
725
726            prev_end = current_run_end;
727        }
728
729        Ok(if has_non_null_value { Some(acc) } else { None })
730    }
731}
732
733/// Returns the min of values in the array of `ArrowNumericType` type, or dictionary
734/// array with value of `ArrowNumericType` type.
735pub fn min_array<T: ArrowNumericType, A: ArrayAccessor<Item = T::Native>>(
736    array: A,
737) -> Option<T::Native> {
738    min_max_array_helper::<T, A, _, _>(array, |a, b| a.is_gt(*b), min)
739}
740
741/// Returns the max of values in the array of `ArrowNumericType` type, or dictionary
742/// array with value of `ArrowNumericType` type.
743pub fn max_array<T: ArrowNumericType, A: ArrayAccessor<Item = T::Native>>(
744    array: A,
745) -> Option<T::Native> {
746    min_max_array_helper::<T, A, _, _>(array, |a, b| a.is_lt(*b), max)
747}
748
749fn min_max_array_helper<T, A: ArrayAccessor<Item = T::Native>, F, M>(
750    array: A,
751    cmp: F,
752    m: M,
753) -> Option<T::Native>
754where
755    T: ArrowNumericType,
756    F: Fn(&T::Native, &T::Native) -> bool,
757    M: Fn(&PrimitiveArray<T>) -> Option<T::Native>,
758{
759    match array.data_type() {
760        DataType::Dictionary(_, _) => min_max_helper::<T::Native, _, _>(array, cmp),
761        DataType::RunEndEncoded(run_ends, _) => {
762            // We can directly perform min/max on the values child array, as any
763            // run must have non-zero length.
764            let array: &dyn Array = &array;
765            let values = match run_ends.data_type() {
766                DataType::Int16 => array.as_run_opt::<types::Int16Type>()?.values_slice(),
767                DataType::Int32 => array.as_run_opt::<types::Int32Type>()?.values_slice(),
768                DataType::Int64 => array.as_run_opt::<types::Int64Type>()?.values_slice(),
769                _ => return None,
770            };
771            // We only support RunArray wrapping primitive types.
772            let values = values.as_any().downcast_ref::<PrimitiveArray<T>>()?;
773            m(values)
774        }
775        _ => m(as_primitive_array(&array)),
776    }
777}
778
779macro_rules! bit_operation {
780    ($NAME:ident, $OP:ident, $NATIVE:ident, $DEFAULT:expr, $DOC:expr) => {
781        #[doc = $DOC]
782        ///
783        /// Returns `None` if the array is empty or only contains null values.
784        pub fn $NAME<T>(array: &PrimitiveArray<T>) -> Option<T::Native>
785        where
786            T: ArrowNumericType,
787            T::Native: $NATIVE<Output = T::Native> + ArrowNativeTypeOp,
788        {
789            let default;
790            if $DEFAULT == -1 {
791                default = T::Native::ONE.neg_wrapping();
792            } else {
793                default = T::default_value();
794            }
795
796            let null_count = array.null_count();
797
798            if null_count == array.len() {
799                return None;
800            }
801
802            let data: &[T::Native] = array.values();
803
804            match array.nulls() {
805                None => {
806                    let result = data
807                        .iter()
808                        .fold(default, |accumulator, value| accumulator.$OP(*value));
809
810                    Some(result)
811                }
812                Some(nulls) => {
813                    let mut result = default;
814                    let data_chunks = data.chunks_exact(64);
815                    let remainder = data_chunks.remainder();
816
817                    let bit_chunks = nulls.inner().bit_chunks();
818                    data_chunks
819                        .zip(bit_chunks.iter())
820                        .for_each(|(chunk, mask)| {
821                            // index_mask has value 1 << i in the loop
822                            let mut index_mask = 1;
823                            chunk.iter().for_each(|value| {
824                                if (mask & index_mask) != 0 {
825                                    result = result.$OP(*value);
826                                }
827                                index_mask <<= 1;
828                            });
829                        });
830
831                    let remainder_bits = bit_chunks.remainder_bits();
832
833                    remainder.iter().enumerate().for_each(|(i, value)| {
834                        if remainder_bits & (1 << i) != 0 {
835                            result = result.$OP(*value);
836                        }
837                    });
838
839                    Some(result)
840                }
841            }
842        }
843    };
844}
845
846bit_operation!(
847    bit_and,
848    bitand,
849    BitAnd,
850    -1,
851    "Returns the bitwise and of all non-null input values."
852);
853bit_operation!(
854    bit_or,
855    bitor,
856    BitOr,
857    0,
858    "Returns the bitwise or of all non-null input values."
859);
860bit_operation!(
861    bit_xor,
862    bitxor,
863    BitXor,
864    0,
865    "Returns the bitwise xor of all non-null input values."
866);
867
868/// Returns true if all non-null input values are true, otherwise false.
869///
870/// Returns `None` if the array is empty or only contains null values.
871pub fn bool_and(array: &BooleanArray) -> Option<bool> {
872    min_boolean(array)
873}
874
875/// Returns true if any non-null input value is true, otherwise false.
876///
877/// Returns `None` if the array is empty or only contains null values.
878pub fn bool_or(array: &BooleanArray) -> Option<bool> {
879    max_boolean(array)
880}
881
882/// Returns the sum of values in the primitive array.
883///
884/// Returns `Ok(None)` if the array is empty or only contains null values.
885///
886/// This detects overflow and returns an `Err` for that. For an non-overflow-checking variant,
887/// use [`sum`] instead.
888pub fn sum_checked<T: ArrowNumericType>(
889    array: &PrimitiveArray<T>,
890) -> Result<Option<T::Native>, ArrowError> {
891    let null_count = array.null_count();
892
893    if null_count == array.len() {
894        return Ok(None);
895    }
896
897    let data: &[T::Native] = array.values();
898
899    match array.nulls() {
900        None => {
901            let sum = data
902                .iter()
903                .try_fold(T::default_value(), |accumulator, value| {
904                    accumulator.add_checked(*value)
905                })?;
906
907            Ok(Some(sum))
908        }
909        Some(nulls) => {
910            let mut sum = T::default_value();
911
912            try_for_each_valid_idx(
913                nulls.len(),
914                nulls.offset(),
915                nulls.null_count(),
916                Some(nulls.validity()),
917                |idx| {
918                    unsafe { sum = sum.add_checked(array.value_unchecked(idx))? };
919                    Ok::<_, ArrowError>(())
920                },
921            )?;
922
923            Ok(Some(sum))
924        }
925    }
926}
927
928/// Returns the sum of values in the primitive array.
929///
930/// Returns `None` if the array is empty or only contains null values.
931///
932/// This doesn't detect overflow in release mode by default. Once overflowing, the result will
933/// wrap around. For an overflow-checking variant, use [`sum_checked`] instead.
934pub fn sum<T: ArrowNumericType>(array: &PrimitiveArray<T>) -> Option<T::Native> {
935    aggregate::<T::Native, T, SumAccumulator<T::Native>>(array)
936}
937
938/// Returns the product of values in the primitive array.
939///
940/// Returns `None` if the array is empty or only contains null values.
941///
942/// This doesn't detect overflow in release mode by default. Once overflowing, the result will
943/// wrap around. For an overflow-checking variant, use [`product_checked`] instead.
944pub fn product<T: ArrowNumericType>(array: &PrimitiveArray<T>) -> Option<T::Native> {
945    aggregate::<T::Native, T, ProductAccumulator<T::Native>>(array)
946}
947
948/// Returns the product of values in the primitive array.
949///
950/// Returns `Ok(None)` if the array is empty or only contains null values.
951///
952/// This detects overflow and returns an `Err` for that. For an non-overflow-checking variant,
953/// use [`product`] instead.
954pub fn product_checked<T: ArrowNumericType>(
955    array: &PrimitiveArray<T>,
956) -> Result<Option<T::Native>, ArrowError> {
957    let null_count = array.null_count();
958
959    if null_count == array.len() {
960        return Ok(None);
961    }
962
963    let data: &[T::Native] = array.values();
964
965    match array.nulls() {
966        None => {
967            let product = data.iter().try_fold(T::Native::ONE, |accumulator, value| {
968                accumulator.mul_checked(*value)
969            })?;
970
971            Ok(Some(product))
972        }
973        Some(nulls) => {
974            let mut product = T::Native::ONE;
975
976            try_for_each_valid_idx(
977                nulls.len(),
978                nulls.offset(),
979                nulls.null_count(),
980                Some(nulls.validity()),
981                |idx| {
982                    unsafe { product = product.mul_checked(array.value_unchecked(idx))? };
983                    Ok::<_, ArrowError>(())
984                },
985            )?;
986
987            Ok(Some(product))
988        }
989    }
990}
991
992/// Returns the minimum value in the array, according to the natural order.
993/// For floating point arrays any NaN values are considered to be greater than any other non-null value
994///
995/// # Example
996/// ```rust
997/// # use arrow_array::Int32Array;
998/// # use arrow_arith::aggregate::min;
999/// let array = Int32Array::from(vec![8, 2, 4]);
1000/// let result = min(&array);
1001/// assert_eq!(result, Some(2));
1002/// ```
1003pub fn min<T: ArrowNumericType>(array: &PrimitiveArray<T>) -> Option<T::Native> {
1004    aggregate::<T::Native, T, MinAccumulator<T::Native>>(array)
1005}
1006
1007/// Returns the maximum value in the array, according to the natural order.
1008/// For floating point arrays any NaN values are considered to be greater than any other non-null value
1009///
1010/// # Example
1011/// ```rust
1012/// # use arrow_array::Int32Array;
1013/// # use arrow_arith::aggregate::max;
1014/// let array = Int32Array::from(vec![4, 8, 2]);
1015/// let result = max(&array);
1016/// assert_eq!(result, Some(8));
1017/// ```
1018pub fn max<T: ArrowNumericType>(array: &PrimitiveArray<T>) -> Option<T::Native> {
1019    aggregate::<T::Native, T, MaxAccumulator<T::Native>>(array)
1020}
1021
1022#[cfg(test)]
1023mod tests {
1024    use super::*;
1025    use arrow_array::types::*;
1026    use builder::BooleanBuilder;
1027    use std::sync::Arc;
1028
1029    #[test]
1030    fn test_primitive_array_sum() {
1031        let a = Int32Array::from(vec![1, 2, 3, 4, 5]);
1032        assert_eq!(15, sum(&a).unwrap());
1033    }
1034
1035    #[test]
1036    fn test_primitive_array_float_sum() {
1037        let a = Float64Array::from(vec![1.1, 2.2, 3.3, 4.4, 5.5]);
1038        assert_eq!(16.5, sum(&a).unwrap());
1039    }
1040
1041    #[test]
1042    fn test_primitive_array_product() {
1043        let a = Int32Array::from(vec![1, 2, 3, 4, 5]);
1044        assert_eq!(120, product(&a).unwrap());
1045    }
1046
1047    #[test]
1048    fn test_primitive_array_float_product() {
1049        let a = Float64Array::from(vec![1.0, 2.0, 3.0, 4.0, 5.0]);
1050        assert_eq!(120.0, product(&a).unwrap());
1051    }
1052
1053    #[test]
1054    fn test_primitive_array_product_with_nulls() {
1055        let a = Int32Array::from(vec![None, Some(2), Some(3), None, Some(5)]);
1056        assert_eq!(30, product(&a).unwrap());
1057    }
1058
1059    #[test]
1060    fn test_primitive_array_product_all_nulls() {
1061        let a = Int32Array::from(vec![None, None, None]);
1062        assert_eq!(None, product(&a));
1063    }
1064
1065    #[test]
1066    fn test_primitive_array_product_empty() {
1067        let a = Int32Array::from(Vec::<i32>::new());
1068        assert_eq!(None, product(&a));
1069    }
1070
1071    #[test]
1072    fn test_primitive_array_product_checked() {
1073        let a = Int32Array::from(vec![1, 2, 3, 4, 5]);
1074        assert_eq!(120, product_checked(&a).unwrap().unwrap());
1075    }
1076
1077    #[test]
1078    fn test_primitive_array_product_checked_with_nulls() {
1079        let a = Int32Array::from(vec![None, Some(2), Some(3), None, Some(5)]);
1080        assert_eq!(30, product_checked(&a).unwrap().unwrap());
1081    }
1082
1083    #[test]
1084    fn test_primitive_array_product_checked_all_nulls() {
1085        let a = Int32Array::from(vec![None, None, None]);
1086        assert_eq!(None, product_checked(&a).unwrap());
1087    }
1088
1089    #[test]
1090    fn test_product_overflow() {
1091        let a = Int32Array::from(vec![i32::MAX, 2]);
1092        // wrapping variant silently overflows
1093        assert_eq!(product(&a).unwrap(), -2);
1094    }
1095
1096    #[test]
1097    fn test_product_checked_overflow() {
1098        let a = Int32Array::from(vec![i32::MAX, 2]);
1099        product_checked(&a).expect_err("overflow should be detected");
1100    }
1101
1102    #[test]
1103    fn test_primitive_array_sum_with_nulls() {
1104        let a = Int32Array::from(vec![None, Some(2), Some(3), None, Some(5)]);
1105        assert_eq!(10, sum(&a).unwrap());
1106    }
1107
1108    #[test]
1109    fn test_primitive_array_sum_all_nulls() {
1110        let a = Int32Array::from(vec![None, None, None]);
1111        assert_eq!(None, sum(&a));
1112    }
1113
1114    #[test]
1115    fn test_primitive_array_sum_large_float_64() {
1116        let c = Float64Array::new((1..=100).map(|x| x as f64).collect(), None);
1117        assert_eq!(Some((1..=100).sum::<i64>() as f64), sum(&c));
1118
1119        // create an array that actually has non-zero values at the invalid indices
1120        let validity = NullBuffer::new((1..=100).map(|x| x % 3 == 0).collect());
1121        let c = Float64Array::new((1..=100).map(|x| x as f64).collect(), Some(validity));
1122
1123        assert_eq!(
1124            Some((1..=100).filter(|i| i % 3 == 0).sum::<i64>() as f64),
1125            sum(&c)
1126        );
1127    }
1128
1129    #[test]
1130    fn test_primitive_array_sum_large_float_32() {
1131        let c = Float32Array::new((1..=100).map(|x| x as f32).collect(), None);
1132        assert_eq!(Some((1..=100).sum::<i64>() as f32), sum(&c));
1133
1134        // create an array that actually has non-zero values at the invalid indices
1135        let validity = NullBuffer::new((1..=100).map(|x| x % 3 == 0).collect());
1136        let c = Float32Array::new((1..=100).map(|x| x as f32).collect(), Some(validity));
1137
1138        assert_eq!(
1139            Some((1..=100).filter(|i| i % 3 == 0).sum::<i64>() as f32),
1140            sum(&c)
1141        );
1142    }
1143
1144    #[test]
1145    fn test_primitive_array_sum_large_64() {
1146        let c = Int64Array::new((1..=100).collect(), None);
1147        assert_eq!(Some((1..=100).sum()), sum(&c));
1148
1149        // create an array that actually has non-zero values at the invalid indices
1150        let validity = NullBuffer::new((1..=100).map(|x| x % 3 == 0).collect());
1151        let c = Int64Array::new((1..=100).collect(), Some(validity));
1152
1153        assert_eq!(Some((1..=100).filter(|i| i % 3 == 0).sum()), sum(&c));
1154    }
1155
1156    #[test]
1157    fn test_primitive_array_sum_large_32() {
1158        let c = Int32Array::new((1..=100).collect(), None);
1159        assert_eq!(Some((1..=100).sum()), sum(&c));
1160
1161        // create an array that actually has non-zero values at the invalid indices
1162        let validity = NullBuffer::new((1..=100).map(|x| x % 3 == 0).collect());
1163        let c = Int32Array::new((1..=100).collect(), Some(validity));
1164        assert_eq!(Some((1..=100).filter(|i| i % 3 == 0).sum()), sum(&c));
1165    }
1166
1167    #[test]
1168    fn test_primitive_array_sum_large_16() {
1169        let c = Int16Array::new((1..=100).collect(), None);
1170        assert_eq!(Some((1..=100).sum()), sum(&c));
1171
1172        // create an array that actually has non-zero values at the invalid indices
1173        let validity = NullBuffer::new((1..=100).map(|x| x % 3 == 0).collect());
1174        let c = Int16Array::new((1..=100).collect(), Some(validity));
1175        assert_eq!(Some((1..=100).filter(|i| i % 3 == 0).sum()), sum(&c));
1176    }
1177
1178    #[test]
1179    fn test_primitive_array_sum_large_8() {
1180        let c = UInt8Array::new((1..=100).collect(), None);
1181        assert_eq!(
1182            Some((1..=100).fold(0_u8, |a, x| a.wrapping_add(x))),
1183            sum(&c)
1184        );
1185
1186        // create an array that actually has non-zero values at the invalid indices
1187        let validity = NullBuffer::new((1..=100).map(|x| x % 3 == 0).collect());
1188        let c = UInt8Array::new((1..=100).collect(), Some(validity));
1189        assert_eq!(
1190            Some(
1191                (1..=100)
1192                    .filter(|i| i % 3 == 0)
1193                    .fold(0_u8, |a, x| a.wrapping_add(x))
1194            ),
1195            sum(&c)
1196        );
1197    }
1198
1199    #[test]
1200    fn test_primitive_array_bit_and() {
1201        let a = Int32Array::from(vec![1, 2, 3, 4, 5]);
1202        assert_eq!(0, bit_and(&a).unwrap());
1203    }
1204
1205    #[test]
1206    fn test_primitive_array_bit_and_with_nulls() {
1207        let a = Int32Array::from(vec![None, Some(2), Some(3), None, None]);
1208        assert_eq!(2, bit_and(&a).unwrap());
1209    }
1210
1211    #[test]
1212    fn test_primitive_array_bit_and_all_nulls() {
1213        let a = Int32Array::from(vec![None, None, None]);
1214        assert_eq!(None, bit_and(&a));
1215    }
1216
1217    #[test]
1218    fn test_primitive_array_bit_or() {
1219        let a = Int32Array::from(vec![1, 2, 3, 4, 5]);
1220        assert_eq!(7, bit_or(&a).unwrap());
1221    }
1222
1223    #[test]
1224    fn test_primitive_array_bit_or_with_nulls() {
1225        let a = Int32Array::from(vec![None, Some(2), Some(3), None, Some(5)]);
1226        assert_eq!(7, bit_or(&a).unwrap());
1227    }
1228
1229    #[test]
1230    fn test_primitive_array_bit_or_all_nulls() {
1231        let a = Int32Array::from(vec![None, None, None]);
1232        assert_eq!(None, bit_or(&a));
1233    }
1234
1235    #[test]
1236    fn test_primitive_array_bit_xor() {
1237        let a = Int32Array::from(vec![1, 2, 3, 4, 5]);
1238        assert_eq!(1, bit_xor(&a).unwrap());
1239    }
1240
1241    #[test]
1242    fn test_primitive_array_bit_xor_with_nulls() {
1243        let a = Int32Array::from(vec![None, Some(2), Some(3), None, Some(5)]);
1244        assert_eq!(4, bit_xor(&a).unwrap());
1245    }
1246
1247    #[test]
1248    fn test_primitive_array_bit_xor_all_nulls() {
1249        let a = Int32Array::from(vec![None, None, None]);
1250        assert_eq!(None, bit_xor(&a));
1251    }
1252
1253    #[test]
1254    fn test_primitive_array_bool_and() {
1255        let a = BooleanArray::from(vec![true, false, true, false, true]);
1256        assert!(!bool_and(&a).unwrap());
1257    }
1258
1259    #[test]
1260    fn test_primitive_array_bool_and_with_nulls() {
1261        let a = BooleanArray::from(vec![None, Some(true), Some(true), None, Some(true)]);
1262        assert!(bool_and(&a).unwrap());
1263    }
1264
1265    #[test]
1266    fn test_primitive_array_bool_and_all_nulls() {
1267        let a = BooleanArray::from(vec![None, None, None]);
1268        assert_eq!(None, bool_and(&a));
1269    }
1270
1271    #[test]
1272    fn test_primitive_array_bool_or() {
1273        let a = BooleanArray::from(vec![true, false, true, false, true]);
1274        assert!(bool_or(&a).unwrap());
1275    }
1276
1277    #[test]
1278    fn test_primitive_array_bool_or_with_nulls() {
1279        let a = BooleanArray::from(vec![None, Some(false), Some(false), None, Some(false)]);
1280        assert!(!bool_or(&a).unwrap());
1281    }
1282
1283    #[test]
1284    fn test_primitive_array_bool_or_all_nulls() {
1285        let a = BooleanArray::from(vec![None, None, None]);
1286        assert_eq!(None, bool_or(&a));
1287    }
1288
1289    #[test]
1290    fn test_primitive_array_min_max() {
1291        let a = Int32Array::from(vec![5, 6, 7, 8, 9]);
1292        assert_eq!(5, min(&a).unwrap());
1293        assert_eq!(9, max(&a).unwrap());
1294    }
1295
1296    #[test]
1297    fn test_primitive_array_min_max_with_nulls() {
1298        let a = Int32Array::from(vec![Some(5), None, None, Some(8), Some(9)]);
1299        assert_eq!(5, min(&a).unwrap());
1300        assert_eq!(9, max(&a).unwrap());
1301    }
1302
1303    #[test]
1304    fn test_primitive_min_max_1() {
1305        let a = Int32Array::from(vec![None, None, Some(5), Some(2)]);
1306        assert_eq!(Some(2), min(&a));
1307        assert_eq!(Some(5), max(&a));
1308    }
1309
1310    #[test]
1311    fn test_primitive_min_max_float_large_nonnull_array() {
1312        let a: Float64Array = (0..256).map(|i| Some((i + 1) as f64)).collect();
1313        // min/max are on boundaries of chunked data
1314        assert_eq!(Some(1.0), min(&a));
1315        assert_eq!(Some(256.0), max(&a));
1316
1317        // max is last value in remainder after chunking
1318        let a: Float64Array = (0..255).map(|i| Some((i + 1) as f64)).collect();
1319        assert_eq!(Some(255.0), max(&a));
1320
1321        // max is first value in remainder after chunking
1322        let a: Float64Array = (0..257).map(|i| Some((i + 1) as f64)).collect();
1323        assert_eq!(Some(257.0), max(&a));
1324    }
1325
1326    #[test]
1327    fn test_primitive_min_max_float_large_nullable_array() {
1328        let a: Float64Array = (0..256)
1329            .map(|i| {
1330                if (i + 1) % 3 == 0 {
1331                    None
1332                } else {
1333                    Some((i + 1) as f64)
1334                }
1335            })
1336            .collect();
1337        // min/max are on boundaries of chunked data
1338        assert_eq!(Some(1.0), min(&a));
1339        assert_eq!(Some(256.0), max(&a));
1340
1341        let a: Float64Array = (0..256)
1342            .map(|i| {
1343                if i == 0 || i == 255 {
1344                    None
1345                } else {
1346                    Some((i + 1) as f64)
1347                }
1348            })
1349            .collect();
1350        // boundaries of chunked data are null
1351        assert_eq!(Some(2.0), min(&a));
1352        assert_eq!(Some(255.0), max(&a));
1353
1354        let a: Float64Array = (0..256)
1355            .map(|i| if i != 100 { None } else { Some((i) as f64) })
1356            .collect();
1357        // a single non-null value somewhere in the middle
1358        assert_eq!(Some(100.0), min(&a));
1359        assert_eq!(Some(100.0), max(&a));
1360
1361        // max is last value in remainder after chunking
1362        let a: Float64Array = (0..255).map(|i| Some((i + 1) as f64)).collect();
1363        assert_eq!(Some(255.0), max(&a));
1364
1365        // max is first value in remainder after chunking
1366        let a: Float64Array = (0..257).map(|i| Some((i + 1) as f64)).collect();
1367        assert_eq!(Some(257.0), max(&a));
1368    }
1369
1370    #[test]
1371    fn test_primitive_min_max_float_edge_cases() {
1372        let a: Float64Array = (0..100).map(|_| Some(f64::NEG_INFINITY)).collect();
1373        assert_eq!(Some(f64::NEG_INFINITY), min(&a));
1374        assert_eq!(Some(f64::NEG_INFINITY), max(&a));
1375
1376        let a: Float64Array = (0..100).map(|_| Some(f64::MIN)).collect();
1377        assert_eq!(Some(f64::MIN), min(&a));
1378        assert_eq!(Some(f64::MIN), max(&a));
1379
1380        let a: Float64Array = (0..100).map(|_| Some(f64::MAX)).collect();
1381        assert_eq!(Some(f64::MAX), min(&a));
1382        assert_eq!(Some(f64::MAX), max(&a));
1383
1384        let a: Float64Array = (0..100).map(|_| Some(f64::INFINITY)).collect();
1385        assert_eq!(Some(f64::INFINITY), min(&a));
1386        assert_eq!(Some(f64::INFINITY), max(&a));
1387    }
1388
1389    #[test]
1390    fn test_primitive_min_max_float_all_nans_non_null() {
1391        let a: Float64Array = (0..100).map(|_| Some(f64::NAN)).collect();
1392        assert!(max(&a).unwrap().is_nan());
1393        assert!(min(&a).unwrap().is_nan());
1394    }
1395
1396    #[test]
1397    fn test_primitive_min_max_float_negative_nan() {
1398        let a: Float64Array =
1399            Float64Array::from(vec![f64::NEG_INFINITY, f64::NAN, f64::INFINITY, -f64::NAN]);
1400        let max = max(&a).unwrap();
1401        let min = min(&a).unwrap();
1402        assert!(max.is_nan());
1403        assert!(max.is_sign_positive());
1404
1405        assert!(min.is_nan());
1406        assert!(min.is_sign_negative());
1407    }
1408
1409    #[test]
1410    fn test_primitive_min_max_float_first_nan_nonnull() {
1411        let a: Float64Array = (0..100)
1412            .map(|i| {
1413                if i == 0 {
1414                    Some(f64::NAN)
1415                } else {
1416                    Some(i as f64)
1417                }
1418            })
1419            .collect();
1420        assert_eq!(Some(1.0), min(&a));
1421        assert!(max(&a).unwrap().is_nan());
1422    }
1423
1424    #[test]
1425    fn test_primitive_min_max_float_last_nan_nonnull() {
1426        let a: Float64Array = (0..100)
1427            .map(|i| {
1428                if i == 99 {
1429                    Some(f64::NAN)
1430                } else {
1431                    Some((i + 1) as f64)
1432                }
1433            })
1434            .collect();
1435        assert_eq!(Some(1.0), min(&a));
1436        assert!(max(&a).unwrap().is_nan());
1437    }
1438
1439    #[test]
1440    fn test_primitive_min_max_float_first_nan_nullable() {
1441        let a: Float64Array = (0..100)
1442            .map(|i| {
1443                if i == 0 {
1444                    Some(f64::NAN)
1445                } else if i % 2 == 0 {
1446                    None
1447                } else {
1448                    Some(i as f64)
1449                }
1450            })
1451            .collect();
1452        assert_eq!(Some(1.0), min(&a));
1453        assert!(max(&a).unwrap().is_nan());
1454    }
1455
1456    #[test]
1457    fn test_primitive_min_max_float_last_nan_nullable() {
1458        let a: Float64Array = (0..100)
1459            .map(|i| {
1460                if i == 99 {
1461                    Some(f64::NAN)
1462                } else if i % 2 == 0 {
1463                    None
1464                } else {
1465                    Some(i as f64)
1466                }
1467            })
1468            .collect();
1469        assert_eq!(Some(1.0), min(&a));
1470        assert!(max(&a).unwrap().is_nan());
1471    }
1472
1473    #[test]
1474    fn test_primitive_min_max_float_inf_and_nans() {
1475        let a: Float64Array = (0..100)
1476            .map(|i| {
1477                let x = match i % 10 {
1478                    0 => f64::NEG_INFINITY,
1479                    1 => f64::MIN,
1480                    2 => f64::MAX,
1481                    4 => f64::INFINITY,
1482                    5 => f64::NAN,
1483                    _ => i as f64,
1484                };
1485                Some(x)
1486            })
1487            .collect();
1488        assert_eq!(Some(f64::NEG_INFINITY), min(&a));
1489        assert!(max(&a).unwrap().is_nan());
1490    }
1491
1492    fn pad_inputs_and_test_fixed_size_binary(
1493        input: Vec<Option<&[u8]>>,
1494        expected_min: Option<&[u8]>,
1495        expected_max: Option<&[u8]>,
1496    ) {
1497        fn pad_slice(slice: &[u8], len: usize) -> Vec<u8> {
1498            let mut padded = vec![0; len];
1499            padded[..slice.len()].copy_from_slice(slice);
1500            padded
1501        }
1502
1503        let max_len = input
1504            .iter()
1505            .filter_map(|x| x.as_ref().map(|b| b.len()))
1506            .max()
1507            .unwrap_or(0);
1508        let padded_input = input
1509            .iter()
1510            .map(|x| x.as_ref().map(|b| pad_slice(b, max_len)));
1511        let input_arr =
1512            FixedSizeBinaryArray::try_from_sparse_iter_with_size(padded_input, max_len as i32)
1513                .unwrap();
1514        let padded_expected_min = expected_min.map(|b| pad_slice(b, max_len));
1515        let padded_expected_max = expected_max.map(|b| pad_slice(b, max_len));
1516
1517        assert_eq!(
1518            padded_expected_min.as_deref(),
1519            min_fixed_size_binary(&input_arr)
1520        );
1521        assert_eq!(
1522            padded_expected_max.as_deref(),
1523            max_fixed_size_binary(&input_arr)
1524        );
1525    }
1526
1527    macro_rules! test_binary {
1528        ($NAME:ident, $ARRAY:expr, $EXPECTED_MIN:expr, $EXPECTED_MAX: expr) => {
1529            #[test]
1530            fn $NAME() {
1531                let binary = BinaryArray::from($ARRAY);
1532                assert_eq!($EXPECTED_MIN, min_binary(&binary));
1533                assert_eq!($EXPECTED_MAX, max_binary(&binary));
1534
1535                let large_binary = LargeBinaryArray::from($ARRAY);
1536                assert_eq!($EXPECTED_MIN, min_binary(&large_binary));
1537                assert_eq!($EXPECTED_MAX, max_binary(&large_binary));
1538
1539                let binary_view = BinaryViewArray::from($ARRAY);
1540                assert_eq!($EXPECTED_MIN, min_binary_view(&binary_view));
1541                assert_eq!($EXPECTED_MAX, max_binary_view(&binary_view));
1542
1543                pad_inputs_and_test_fixed_size_binary($ARRAY, $EXPECTED_MIN, $EXPECTED_MAX);
1544            }
1545        };
1546    }
1547
1548    test_binary!(
1549        test_binary_min_max_with_nulls,
1550        vec![
1551            Some(b"b01234567890123".as_slice()), // long bytes
1552            None,
1553            None,
1554            Some(b"a"),
1555            Some(b"c"),
1556            Some(b"abcdedfg0123456"),
1557        ],
1558        Some(b"a".as_slice()),
1559        Some(b"c".as_slice())
1560    );
1561
1562    test_binary!(
1563        test_binary_min_max_no_null,
1564        vec![
1565            Some(b"b".as_slice()),
1566            Some(b"abcdefghijklmnopqrst"), // long bytes
1567            Some(b"c"),
1568            Some(b"b01234567890123"), // long bytes for view types
1569        ],
1570        Some(b"abcdefghijklmnopqrst".as_slice()),
1571        Some(b"c".as_slice())
1572    );
1573
1574    test_binary!(test_binary_min_max_all_nulls, vec![None, None], None, None);
1575
1576    test_binary!(
1577        test_binary_min_max_1,
1578        vec![
1579            None,
1580            Some(b"b01234567890123435".as_slice()), // long bytes for view types
1581            None,
1582            Some(b"b0123xxxxxxxxxxx"),
1583            Some(b"a")
1584        ],
1585        Some(b"a".as_slice()),
1586        Some(b"b0123xxxxxxxxxxx".as_slice())
1587    );
1588
1589    macro_rules! test_string {
1590        ($NAME:ident, $ARRAY:expr, $EXPECTED_MIN:expr, $EXPECTED_MAX: expr) => {
1591            #[test]
1592            fn $NAME() {
1593                let string = StringArray::from($ARRAY);
1594                assert_eq!($EXPECTED_MIN, min_string(&string));
1595                assert_eq!($EXPECTED_MAX, max_string(&string));
1596
1597                let large_string = LargeStringArray::from($ARRAY);
1598                assert_eq!($EXPECTED_MIN, min_string(&large_string));
1599                assert_eq!($EXPECTED_MAX, max_string(&large_string));
1600
1601                let string_view = StringViewArray::from($ARRAY);
1602                assert_eq!($EXPECTED_MIN, min_string_view(&string_view));
1603                assert_eq!($EXPECTED_MAX, max_string_view(&string_view));
1604            }
1605        };
1606    }
1607
1608    test_string!(
1609        test_string_min_max_with_nulls,
1610        vec![
1611            Some("b012345678901234"), // long bytes for view types
1612            None,
1613            None,
1614            Some("a"),
1615            Some("c"),
1616            Some("b0123xxxxxxxxxxx")
1617        ],
1618        Some("a"),
1619        Some("c")
1620    );
1621
1622    test_string!(
1623        test_string_min_max_no_null,
1624        vec![
1625            Some("b"),
1626            Some("b012345678901234"), // long bytes for view types
1627            Some("a"),
1628            Some("b012xxxxxxxxxxxx")
1629        ],
1630        Some("a"),
1631        Some("b012xxxxxxxxxxxx")
1632    );
1633
1634    test_string!(
1635        test_string_min_max_all_nulls,
1636        Vec::<Option<&str>>::from_iter([None, None]),
1637        None,
1638        None
1639    );
1640
1641    test_string!(
1642        test_string_min_max_1,
1643        vec![
1644            None,
1645            Some("c12345678901234"), // long bytes for view types
1646            None,
1647            Some("b"),
1648            Some("c1234xxxxxxxxxx")
1649        ],
1650        Some("b"),
1651        Some("c1234xxxxxxxxxx")
1652    );
1653
1654    test_string!(
1655        test_string_min_max_empty,
1656        Vec::<Option<&str>>::new(),
1657        None,
1658        None
1659    );
1660
1661    #[test]
1662    fn test_boolean_min_max_empty() {
1663        let a = BooleanArray::from(vec![] as Vec<Option<bool>>);
1664        assert_eq!(None, min_boolean(&a));
1665        assert_eq!(None, max_boolean(&a));
1666    }
1667
1668    #[test]
1669    fn test_boolean_min_max_all_null() {
1670        let a = BooleanArray::from(vec![None, None]);
1671        assert_eq!(None, min_boolean(&a));
1672        assert_eq!(None, max_boolean(&a));
1673    }
1674
1675    #[test]
1676    fn test_boolean_min_max_no_null() {
1677        let a = BooleanArray::from(vec![Some(true), Some(false), Some(true)]);
1678        assert_eq!(Some(false), min_boolean(&a));
1679        assert_eq!(Some(true), max_boolean(&a));
1680    }
1681
1682    #[test]
1683    fn test_boolean_min_max() {
1684        let a = BooleanArray::from(vec![Some(true), Some(true), None, Some(false), None]);
1685        assert_eq!(Some(false), min_boolean(&a));
1686        assert_eq!(Some(true), max_boolean(&a));
1687
1688        let a = BooleanArray::from(vec![None, Some(true), None, Some(false), None]);
1689        assert_eq!(Some(false), min_boolean(&a));
1690        assert_eq!(Some(true), max_boolean(&a));
1691
1692        let a = BooleanArray::from(vec![Some(false), Some(true), None, Some(false), None]);
1693        assert_eq!(Some(false), min_boolean(&a));
1694        assert_eq!(Some(true), max_boolean(&a));
1695
1696        let a = BooleanArray::from(vec![Some(true), None]);
1697        assert_eq!(Some(true), min_boolean(&a));
1698        assert_eq!(Some(true), max_boolean(&a));
1699
1700        let a = BooleanArray::from(vec![Some(false), None]);
1701        assert_eq!(Some(false), min_boolean(&a));
1702        assert_eq!(Some(false), max_boolean(&a));
1703
1704        let a = BooleanArray::from(vec![Some(true)]);
1705        assert_eq!(Some(true), min_boolean(&a));
1706        assert_eq!(Some(true), max_boolean(&a));
1707
1708        let a = BooleanArray::from(vec![Some(false)]);
1709        assert_eq!(Some(false), min_boolean(&a));
1710        assert_eq!(Some(false), max_boolean(&a));
1711    }
1712
1713    #[test]
1714    fn test_boolean_min_max_smaller() {
1715        let a = BooleanArray::from(vec![Some(false)]);
1716        assert_eq!(Some(false), min_boolean(&a));
1717        assert_eq!(Some(false), max_boolean(&a));
1718
1719        let a = BooleanArray::from(vec![None, Some(false)]);
1720        assert_eq!(Some(false), min_boolean(&a));
1721        assert_eq!(Some(false), max_boolean(&a));
1722
1723        let a = BooleanArray::from(vec![None, Some(true)]);
1724        assert_eq!(Some(true), min_boolean(&a));
1725        assert_eq!(Some(true), max_boolean(&a));
1726
1727        let a = BooleanArray::from(vec![Some(true)]);
1728        assert_eq!(Some(true), min_boolean(&a));
1729        assert_eq!(Some(true), max_boolean(&a));
1730    }
1731
1732    #[test]
1733    fn test_boolean_min_max_64_true_64_false() {
1734        let mut no_nulls = BooleanBuilder::new();
1735        no_nulls.append_slice(&[true; 64]);
1736        no_nulls.append_slice(&[false; 64]);
1737        let no_nulls = no_nulls.finish();
1738
1739        assert_eq!(Some(false), min_boolean(&no_nulls));
1740        assert_eq!(Some(true), max_boolean(&no_nulls));
1741
1742        let mut with_nulls = BooleanBuilder::new();
1743        with_nulls.append_slice(&[true; 31]);
1744        with_nulls.append_null();
1745        with_nulls.append_slice(&[true; 32]);
1746        with_nulls.append_slice(&[false; 1]);
1747        with_nulls.append_nulls(63);
1748        let with_nulls = with_nulls.finish();
1749
1750        assert_eq!(Some(false), min_boolean(&with_nulls));
1751        assert_eq!(Some(true), max_boolean(&with_nulls));
1752    }
1753
1754    #[test]
1755    fn test_boolean_min_max_64_false_64_true() {
1756        let mut no_nulls = BooleanBuilder::new();
1757        no_nulls.append_slice(&[false; 64]);
1758        no_nulls.append_slice(&[true; 64]);
1759        let no_nulls = no_nulls.finish();
1760
1761        assert_eq!(Some(false), min_boolean(&no_nulls));
1762        assert_eq!(Some(true), max_boolean(&no_nulls));
1763
1764        let mut with_nulls = BooleanBuilder::new();
1765        with_nulls.append_slice(&[false; 31]);
1766        with_nulls.append_null();
1767        with_nulls.append_slice(&[false; 32]);
1768        with_nulls.append_slice(&[true; 1]);
1769        with_nulls.append_nulls(63);
1770        let with_nulls = with_nulls.finish();
1771
1772        assert_eq!(Some(false), min_boolean(&with_nulls));
1773        assert_eq!(Some(true), max_boolean(&with_nulls));
1774    }
1775
1776    #[test]
1777    fn test_boolean_min_max_96_true() {
1778        let mut no_nulls = BooleanBuilder::new();
1779        no_nulls.append_slice(&[true; 96]);
1780        let no_nulls = no_nulls.finish();
1781
1782        assert_eq!(Some(true), min_boolean(&no_nulls));
1783        assert_eq!(Some(true), max_boolean(&no_nulls));
1784
1785        let mut with_nulls = BooleanBuilder::new();
1786        with_nulls.append_slice(&[true; 31]);
1787        with_nulls.append_null();
1788        with_nulls.append_slice(&[true; 32]);
1789        with_nulls.append_slice(&[true; 31]);
1790        with_nulls.append_null();
1791        let with_nulls = with_nulls.finish();
1792
1793        assert_eq!(Some(true), min_boolean(&with_nulls));
1794        assert_eq!(Some(true), max_boolean(&with_nulls));
1795    }
1796
1797    #[test]
1798    fn test_boolean_min_max_96_false() {
1799        let mut no_nulls = BooleanBuilder::new();
1800        no_nulls.append_slice(&[false; 96]);
1801        let no_nulls = no_nulls.finish();
1802
1803        assert_eq!(Some(false), min_boolean(&no_nulls));
1804        assert_eq!(Some(false), max_boolean(&no_nulls));
1805
1806        let mut with_nulls = BooleanBuilder::new();
1807        with_nulls.append_slice(&[false; 31]);
1808        with_nulls.append_null();
1809        with_nulls.append_slice(&[false; 32]);
1810        with_nulls.append_slice(&[false; 31]);
1811        with_nulls.append_null();
1812        let with_nulls = with_nulls.finish();
1813
1814        assert_eq!(Some(false), min_boolean(&with_nulls));
1815        assert_eq!(Some(false), max_boolean(&with_nulls));
1816    }
1817
1818    #[test]
1819    fn test_dictionary_aggregates_with_null_values() {
1820        let values = Arc::new(Int32Array::new(
1821            vec![5, -100, 100].into(),
1822            Some(vec![true, false, false].into()),
1823        ));
1824        for (keys, expected) in [
1825            (
1826                vec![Some(0_i8), Some(1), Some(0)],
1827                vec![Some(5), None, Some(5)],
1828            ),
1829            (vec![Some(1), Some(2)], vec![None, None]),
1830            (vec![None, Some(1), Some(0)], vec![None, None, Some(5)]),
1831            (vec![Some(0), Some(0)], vec![Some(5), Some(5)]),
1832            (vec![None, None], vec![None, None]),
1833            (vec![], vec![]),
1834        ] {
1835            let dictionary =
1836                DictionaryArray::<Int8Type>::try_new(Int8Array::from(keys), values.clone())
1837                    .unwrap();
1838            let array = dictionary.downcast_dict::<Int32Array>().unwrap();
1839            let expected = Int32Array::from(expected);
1840            assert_eq!(min_array::<Int32Type, _>(array), min(&expected));
1841            assert_eq!(max_array::<Int32Type, _>(array), max(&expected));
1842            assert_eq!(sum_array::<Int32Type, _>(array), sum(&expected));
1843            assert_eq!(
1844                sum_array_checked::<Int32Type, _>(array).unwrap(),
1845                sum_checked(&expected).unwrap()
1846            );
1847        }
1848    }
1849
1850    #[test]
1851    fn test_sum_dyn() {
1852        let values = Int8Array::from_iter_values([10_i8, 11, 12, 13, 14, 15, 16, 17]);
1853        let values = Arc::new(values) as ArrayRef;
1854        let keys = Int8Array::from_iter_values([2_i8, 3, 4]);
1855
1856        let dict_array = DictionaryArray::new(keys, values.clone());
1857        let array = dict_array.downcast_dict::<Int8Array>().unwrap();
1858        assert_eq!(39, sum_array::<Int8Type, _>(array).unwrap());
1859
1860        let a = Int32Array::from(vec![1, 2, 3, 4, 5]);
1861        assert_eq!(15, sum_array::<Int32Type, _>(&a).unwrap());
1862
1863        let keys = Int8Array::from(vec![Some(2_i8), None, Some(4)]);
1864        let dict_array = DictionaryArray::new(keys, values.clone());
1865        let array = dict_array.downcast_dict::<Int8Array>().unwrap();
1866        assert_eq!(26, sum_array::<Int8Type, _>(array).unwrap());
1867
1868        let keys = Int8Array::from(vec![None, None, None]);
1869        let dict_array = DictionaryArray::new(keys, values.clone());
1870        let array = dict_array.downcast_dict::<Int8Array>().unwrap();
1871        assert!(sum_array::<Int8Type, _>(array).is_none());
1872    }
1873
1874    #[test]
1875    fn test_max_min_dyn() {
1876        let values = Int8Array::from_iter_values([10_i8, 11, 12, 13, 14, 15, 16, 17]);
1877        let keys = Int8Array::from_iter_values([2_i8, 3, 4]);
1878        let values = Arc::new(values) as ArrayRef;
1879
1880        let dict_array = DictionaryArray::new(keys, values.clone());
1881        let array = dict_array.downcast_dict::<Int8Array>().unwrap();
1882        assert_eq!(14, max_array::<Int8Type, _>(array).unwrap());
1883
1884        let array = dict_array.downcast_dict::<Int8Array>().unwrap();
1885        assert_eq!(12, min_array::<Int8Type, _>(array).unwrap());
1886
1887        let a = Int32Array::from(vec![1, 2, 3, 4, 5]);
1888        assert_eq!(5, max_array::<Int32Type, _>(&a).unwrap());
1889        assert_eq!(1, min_array::<Int32Type, _>(&a).unwrap());
1890
1891        let keys = Int8Array::from(vec![Some(2_i8), None, Some(7)]);
1892        let dict_array = DictionaryArray::new(keys, values.clone());
1893        let array = dict_array.downcast_dict::<Int8Array>().unwrap();
1894        assert_eq!(17, max_array::<Int8Type, _>(array).unwrap());
1895        let array = dict_array.downcast_dict::<Int8Array>().unwrap();
1896        assert_eq!(12, min_array::<Int8Type, _>(array).unwrap());
1897
1898        let keys = Int8Array::from(vec![None, None, None]);
1899        let dict_array = DictionaryArray::new(keys, values.clone());
1900        let array = dict_array.downcast_dict::<Int8Array>().unwrap();
1901        assert!(max_array::<Int8Type, _>(array).is_none());
1902        let array = dict_array.downcast_dict::<Int8Array>().unwrap();
1903        assert!(min_array::<Int8Type, _>(array).is_none());
1904    }
1905
1906    #[test]
1907    fn test_max_min_dyn_nan() {
1908        let values = Float32Array::from(vec![5.0_f32, 2.0_f32, f32::NAN]);
1909        let keys = Int8Array::from_iter_values([0_i8, 1, 2]);
1910
1911        let dict_array = DictionaryArray::new(keys, Arc::new(values));
1912        let array = dict_array.downcast_dict::<Float32Array>().unwrap();
1913        assert!(max_array::<Float32Type, _>(array).unwrap().is_nan());
1914
1915        let array = dict_array.downcast_dict::<Float32Array>().unwrap();
1916        assert_eq!(2.0_f32, min_array::<Float32Type, _>(array).unwrap());
1917    }
1918
1919    #[test]
1920    fn test_min_max_sliced_primitive() {
1921        let expected = Some(4.0);
1922        let input: Float64Array = vec![None, Some(4.0)].into_iter().collect();
1923        let actual = min(&input);
1924        assert_eq!(actual, expected);
1925        let actual = max(&input);
1926        assert_eq!(actual, expected);
1927
1928        let sliced_input: Float64Array = vec![None, None, None, None, None, Some(4.0)]
1929            .into_iter()
1930            .collect();
1931        let sliced_input = sliced_input.slice(4, 2);
1932
1933        assert_eq!(&sliced_input, &input);
1934
1935        let actual = min(&sliced_input);
1936        assert_eq!(actual, expected);
1937        let actual = max(&sliced_input);
1938        assert_eq!(actual, expected);
1939    }
1940
1941    #[test]
1942    fn test_min_max_sliced_boolean() {
1943        let expected = Some(true);
1944        let input: BooleanArray = vec![None, Some(true)].into_iter().collect();
1945        let actual = min_boolean(&input);
1946        assert_eq!(actual, expected);
1947        let actual = max_boolean(&input);
1948        assert_eq!(actual, expected);
1949
1950        let sliced_input: BooleanArray = vec![None, None, None, None, None, Some(true)]
1951            .into_iter()
1952            .collect();
1953        let sliced_input = sliced_input.slice(4, 2);
1954
1955        assert_eq!(sliced_input, input);
1956
1957        let actual = min_boolean(&sliced_input);
1958        assert_eq!(actual, expected);
1959        let actual = max_boolean(&sliced_input);
1960        assert_eq!(actual, expected);
1961    }
1962
1963    #[test]
1964    fn test_min_max_sliced_string() {
1965        let expected = Some("foo");
1966        let input: StringArray = vec![None, Some("foo")].into_iter().collect();
1967        let actual = min_string(&input);
1968        assert_eq!(actual, expected);
1969        let actual = max_string(&input);
1970        assert_eq!(actual, expected);
1971
1972        let sliced_input: StringArray = vec![None, None, None, None, None, Some("foo")]
1973            .into_iter()
1974            .collect();
1975        let sliced_input = sliced_input.slice(4, 2);
1976
1977        assert_eq!(&sliced_input, &input);
1978
1979        let actual = min_string(&sliced_input);
1980        assert_eq!(actual, expected);
1981        let actual = max_string(&sliced_input);
1982        assert_eq!(actual, expected);
1983    }
1984
1985    #[test]
1986    fn test_min_max_sliced_binary() {
1987        let expected: Option<&[u8]> = Some(&[5]);
1988        let input: BinaryArray = vec![None, Some(&[5])].into_iter().collect();
1989        let actual = min_binary(&input);
1990        assert_eq!(actual, expected);
1991        let actual = max_binary(&input);
1992        assert_eq!(actual, expected);
1993
1994        let sliced_input: BinaryArray = vec![None, None, None, None, None, Some(&[5])]
1995            .into_iter()
1996            .collect();
1997        let sliced_input = sliced_input.slice(4, 2);
1998
1999        assert_eq!(&sliced_input, &input);
2000
2001        let actual = min_binary(&sliced_input);
2002        assert_eq!(actual, expected);
2003        let actual = max_binary(&sliced_input);
2004        assert_eq!(actual, expected);
2005    }
2006
2007    #[test]
2008    fn test_sum_overflow() {
2009        let a = Int32Array::from(vec![i32::MAX, 1]);
2010
2011        assert_eq!(sum(&a).unwrap(), -2147483648);
2012        assert_eq!(sum_array::<Int32Type, _>(&a).unwrap(), -2147483648);
2013    }
2014
2015    #[test]
2016    fn test_sum_checked_overflow() {
2017        let a = Int32Array::from(vec![i32::MAX, 1]);
2018
2019        sum_checked(&a).expect_err("overflow should be detected");
2020        sum_array_checked::<Int32Type, _>(&a).expect_err("overflow should be detected");
2021    }
2022
2023    /// Helper for building a RunArray.
2024    fn make_run_array<'a, I: RunEndIndexType, V: ArrowNumericType, ItemType>(
2025        values: impl IntoIterator<Item = &'a ItemType>,
2026    ) -> RunArray<I>
2027    where
2028        ItemType: Clone + Into<Option<V::Native>> + 'static,
2029    {
2030        let mut builder = arrow_array::builder::PrimitiveRunBuilder::<I, V>::new();
2031        for v in values {
2032            builder.append_option((*v).clone().into());
2033        }
2034        builder.finish()
2035    }
2036
2037    #[test]
2038    fn test_ree_sum_array_basic() {
2039        let run_array = make_run_array::<Int16Type, Int32Type, _>(&[10, 10, 20, 30, 30, 30]);
2040        let typed_array = run_array.downcast::<Int32Array>().unwrap();
2041
2042        let result = sum_array::<Int32Type, _>(typed_array);
2043        assert_eq!(result, Some(130));
2044
2045        let result = sum_array_checked::<Int32Type, _>(typed_array).unwrap();
2046        assert_eq!(result, Some(130));
2047    }
2048
2049    #[test]
2050    fn test_ree_sum_array_empty() {
2051        let run_array = make_run_array::<Int16Type, Int32Type, i32>(&[]);
2052        let typed_array = run_array.downcast::<Int32Array>().unwrap();
2053
2054        let result = sum_array::<Int32Type, _>(typed_array);
2055        assert_eq!(result, None);
2056
2057        let result = sum_array_checked::<Int32Type, _>(typed_array).unwrap();
2058        assert_eq!(result, None);
2059    }
2060
2061    #[test]
2062    fn test_ree_sum_array_with_nulls() {
2063        let run_array =
2064            make_run_array::<Int16Type, Int32Type, _>(&[Some(10), None, Some(20), None, Some(30)]);
2065        let typed_array = run_array.downcast::<Int32Array>().unwrap();
2066
2067        let result = sum_array::<Int32Type, _>(typed_array);
2068        assert_eq!(result, Some(60));
2069
2070        let result = sum_array_checked::<Int32Type, _>(typed_array).unwrap();
2071        assert_eq!(result, Some(60));
2072    }
2073
2074    #[test]
2075    fn test_ree_sum_array_with_only_nulls() {
2076        let run_array = make_run_array::<Int16Type, Int16Type, _>(&[None, None, None, None, None]);
2077        let typed_array = run_array.downcast::<Int16Array>().unwrap();
2078
2079        let result = sum_array::<Int16Type, _>(typed_array);
2080        assert_eq!(result, None);
2081
2082        let result = sum_array_checked::<Int16Type, _>(typed_array).unwrap();
2083        assert_eq!(result, None);
2084    }
2085
2086    #[test]
2087    fn test_ree_sum_array_overflow() {
2088        let run_array = make_run_array::<Int16Type, Int8Type, _>(&[126, 2]);
2089        let typed_array = run_array.downcast::<Int8Array>().unwrap();
2090
2091        // i8 range is -128..=127. 126+2 overflows to -128.
2092        let result = sum_array::<Int8Type, _>(typed_array);
2093        assert_eq!(result, Some(-128));
2094
2095        let result = sum_array_checked::<Int8Type, _>(typed_array);
2096        assert!(result.is_err());
2097    }
2098
2099    #[test]
2100    fn test_ree_sum_array_sliced() {
2101        let run_array = make_run_array::<Int16Type, UInt8Type, _>(&[0, 10, 10, 10, 20, 30, 30, 30]);
2102        // Skip 2 values at the start and 1 at the end.
2103        let sliced = run_array.slice(2, 5);
2104        let typed_array = sliced.downcast::<UInt8Array>().unwrap();
2105
2106        let result = sum_array::<UInt8Type, _>(typed_array);
2107        assert_eq!(result, Some(100));
2108
2109        let result = sum_array_checked::<UInt8Type, _>(typed_array).unwrap();
2110        assert_eq!(result, Some(100));
2111    }
2112
2113    #[test]
2114    fn test_ree_sum_array_sliced_across_runs() {
2115        let run_ends = Int16Array::from(vec![4, 8]);
2116        let values = Int32Array::from(vec![10, 100]);
2117        let array = RunArray::<Int16Type>::try_new(&run_ends, &values).unwrap();
2118        let sliced = array.slice(3, 4);
2119        let typed_array = sliced.downcast::<Int32Array>().unwrap();
2120
2121        assert_eq!(sum_array::<Int32Type, _>(typed_array), Some(310));
2122    }
2123
2124    #[test]
2125    fn test_ree_sum_array_all_slices() {
2126        fn check<I: RunEndIndexType>() {
2127            let values = [
2128                Some(2),
2129                Some(2),
2130                None,
2131                None,
2132                Some(-3),
2133                Some(-3),
2134                Some(-3),
2135                Some(4),
2136            ];
2137            let run_array = make_run_array::<I, Int32Type, _>(&values);
2138            let plain_array = Int32Array::from(values.to_vec());
2139
2140            for offset in 0..=values.len() {
2141                for len in 0..=values.len() - offset {
2142                    let sliced = run_array.slice(offset, len);
2143                    let typed = sliced.downcast::<Int32Array>().unwrap();
2144                    let expected = plain_array.slice(offset, len);
2145
2146                    assert_eq!(
2147                        sum_array::<Int32Type, _>(typed),
2148                        sum_array::<Int32Type, _>(&expected),
2149                        "offset={offset}, len={len}"
2150                    );
2151                    assert_eq!(
2152                        sum_array_checked::<Int32Type, _>(typed).unwrap(),
2153                        sum_array_checked::<Int32Type, _>(&expected).unwrap(),
2154                        "offset={offset}, len={len}"
2155                    );
2156                }
2157            }
2158
2159            let nested = run_array.slice(1, 7).slice(2, 4);
2160            let typed = nested.downcast::<Int32Array>().unwrap();
2161            let expected = plain_array.slice(1, 7).slice(2, 4);
2162            assert_eq!(
2163                sum_array::<Int32Type, _>(typed),
2164                sum_array::<Int32Type, _>(&expected)
2165            );
2166            assert_eq!(
2167                sum_array_checked::<Int32Type, _>(typed).unwrap(),
2168                sum_array_checked::<Int32Type, _>(&expected).unwrap()
2169            );
2170        }
2171
2172        check::<Int16Type>();
2173        check::<Int32Type>();
2174        check::<Int64Type>();
2175    }
2176
2177    #[test]
2178    fn test_ree_sum_array_checked_sliced_overflow() {
2179        let values = [50, 50, 50, 50, 1, 1, 1, 1];
2180        let run_array = make_run_array::<Int16Type, Int8Type, _>(&values);
2181        let sliced = run_array.slice(3, 4);
2182        let typed = sliced.downcast::<Int8Array>().unwrap();
2183        assert_eq!(sum_array_checked::<Int8Type, _>(typed).unwrap(), Some(53));
2184
2185        let values = [1, 1, 1, 1, 50, 50, 50, 50];
2186        let run_array = make_run_array::<Int16Type, Int8Type, _>(&values);
2187        let sliced = run_array.slice(3, 4);
2188        let typed = sliced.downcast::<Int8Array>().unwrap();
2189        assert!(sum_array_checked::<Int8Type, _>(typed).is_err());
2190    }
2191
2192    #[test]
2193    fn test_ree_sum_array_sliced_infinity() {
2194        let values = [
2195            1.0,
2196            1.0,
2197            1.0,
2198            1.0,
2199            2.0,
2200            2.0,
2201            2.0,
2202            2.0,
2203            f64::INFINITY,
2204            f64::INFINITY,
2205            f64::INFINITY,
2206            f64::INFINITY,
2207        ];
2208        let run_array = make_run_array::<Int16Type, Float64Type, _>(&values);
2209        let sliced = run_array.slice(5, 4);
2210        let typed = sliced.downcast::<Float64Array>().unwrap();
2211
2212        assert_eq!(sum_array::<Float64Type, _>(typed), Some(f64::INFINITY));
2213    }
2214
2215    #[test]
2216    fn test_ree_min_max_array_basic() {
2217        let run_array = make_run_array::<Int16Type, Int32Type, _>(&[30, 30, 10, 20, 20]);
2218        let typed_array = run_array.downcast::<Int32Array>().unwrap();
2219
2220        let result = min_array::<Int32Type, _>(typed_array);
2221        assert_eq!(result, Some(10));
2222
2223        let result = max_array::<Int32Type, _>(typed_array);
2224        assert_eq!(result, Some(30));
2225    }
2226
2227    #[test]
2228    fn test_ree_min_max_array_empty() {
2229        let run_array = make_run_array::<Int16Type, Int32Type, i32>(&[]);
2230        let typed_array = run_array.downcast::<Int32Array>().unwrap();
2231
2232        let result = min_array::<Int32Type, _>(typed_array);
2233        assert_eq!(result, None);
2234
2235        let result = max_array::<Int32Type, _>(typed_array);
2236        assert_eq!(result, None);
2237    }
2238
2239    #[test]
2240    fn test_ree_min_max_array_float() {
2241        let run_array = make_run_array::<Int16Type, Float64Type, _>(&[5.5, 5.5, 2.1, 8.9, 8.9]);
2242        let typed_array = run_array.downcast::<Float64Array>().unwrap();
2243
2244        let result = min_array::<Float64Type, _>(typed_array);
2245        assert_eq!(result, Some(2.1));
2246
2247        let result = max_array::<Float64Type, _>(typed_array);
2248        assert_eq!(result, Some(8.9));
2249    }
2250
2251    #[test]
2252    fn test_ree_min_max_array_with_nulls() {
2253        let run_array = make_run_array::<Int16Type, UInt8Type, _>(&[None, Some(10)]);
2254        let typed_array = run_array.downcast::<UInt8Array>().unwrap();
2255
2256        let result = min_array::<UInt8Type, _>(typed_array);
2257        assert_eq!(result, Some(10));
2258
2259        let result = max_array::<UInt8Type, _>(typed_array);
2260        assert_eq!(result, Some(10));
2261    }
2262
2263    #[test]
2264    fn test_ree_min_max_array_sliced() {
2265        let run_array = make_run_array::<Int16Type, Int32Type, _>(&[0, 30, 30, 10, 20, 20, 100]);
2266        // Skip 1 value at the start and 1 at the end.
2267        let sliced = run_array.slice(1, 5);
2268        let typed_array = sliced.downcast::<Int32Array>().unwrap();
2269
2270        let result = min_array::<Int32Type, _>(typed_array);
2271        assert_eq!(result, Some(10));
2272
2273        let result = max_array::<Int32Type, _>(typed_array);
2274        assert_eq!(result, Some(30));
2275    }
2276
2277    #[test]
2278    fn test_ree_min_max_array_sliced_mid_run() {
2279        let run_array = make_run_array::<Int16Type, Int32Type, _>(&[0, 0, 30, 10, 20, 100, 100]);
2280        // Skip 1 value at the start and 1 at the end.
2281        let sliced = run_array.slice(1, 5);
2282        let typed_array = sliced.downcast::<Int32Array>().unwrap();
2283
2284        let result = min_array::<Int32Type, _>(typed_array);
2285        assert_eq!(result, Some(0));
2286
2287        let result = max_array::<Int32Type, _>(typed_array);
2288        assert_eq!(result, Some(100));
2289    }
2290}