arrow_select/

concat.rs

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements

//! Defines concat kernel for `ArrayRef`
//!
//! Example:
//!
//! ```
//! use arrow_array::{ArrayRef, StringArray};
//! use arrow_select::concat::concat;
//!
//! let arr = concat(&[
//!     &StringArray::from(vec!["hello", "world"]),
//!     &StringArray::from(vec!["!"]),
//! ]).unwrap();
//! assert_eq!(arr.len(), 3);
//! ```

use crate::dictionary::{KeyMapping, merge_dictionary_values, should_merge_dictionary_values};
use arrow_array::builder::{
    BooleanBuilder, GenericByteBuilder, GenericByteViewBuilder, PrimitiveBuilder,
};
use arrow_array::cast::AsArray;
use arrow_array::types::*;
use arrow_array::*;
use arrow_buffer::{
    ArrowNativeType, BooleanBufferBuilder, MutableBuffer, NullBuffer, OffsetBuffer, RunEndBuffer,
    ScalarBuffer,
};
use arrow_data::transform::{Capacities, MutableArrayData};
use arrow_schema::{ArrowError, DataType, FieldRef, Fields, SchemaRef};
use std::{collections::HashSet, ops::Add, sync::Arc};

fn binary_capacity<T: ByteArrayType>(arrays: &[&dyn Array]) -> Result<Capacities, ArrowError> {
    let mut item_capacity = 0usize;
    let mut bytes_capacity = 0usize;
    for array in arrays {
        let a = array.as_bytes::<T>();

        // Guaranteed to always have at least one element
        let offsets = a.value_offsets();
        bytes_capacity = bytes_capacity
            .checked_add(offsets[offsets.len() - 1].as_usize() - offsets[0].as_usize())
            .ok_or_else(|| ArrowError::MemoryError("concatenated values overflow".into()))?;
        item_capacity = item_capacity
            .checked_add(a.len())
            .ok_or_else(|| ArrowError::MemoryError("concatenated length overflow".into()))?;
    }

    Ok(Capacities::Binary(item_capacity, Some(bytes_capacity)))
}

fn fixed_size_list_capacity(
    arrays: &[&dyn Array],
    data_type: &DataType,
) -> Result<Capacities, ArrowError> {
    if let DataType::FixedSizeList(f, _) = data_type {
        let item_capacity = arrays
            .iter()
            .try_fold(0usize, |total, array| total.checked_add(array.len()))
            .ok_or_else(|| ArrowError::MemoryError("concatenated length overflow".into()))?;
        let child_data_type = f.data_type();
        Ok(match child_data_type {
            // These types should match the types that `get_capacity`
            // has special handling for.
            DataType::Utf8
            | DataType::LargeUtf8
            | DataType::Binary
            | DataType::LargeBinary
            | DataType::FixedSizeList(_, _) => {
                let values: Vec<&dyn arrow_array::Array> = arrays
                    .iter()
                    .map(|a| a.as_fixed_size_list().values().as_ref())
                    .collect();
                Capacities::List(
                    item_capacity,
                    Some(Box::new(get_capacity(&values, child_data_type)?)),
                )
            }
            _ => Capacities::Array(item_capacity),
        })
    } else {
        unreachable!("illegal data type for fixed size list")
    }
}

fn concat_byte_view<B: ByteViewType>(arrays: &[&dyn Array]) -> Result<ArrayRef, ArrowError> {
    let mut builder =
        GenericByteViewBuilder::<B>::with_capacity(arrays.iter().map(|a| a.len()).sum());
    for &array in arrays {
        builder.append_array(array.as_byte_view());
    }
    Ok(Arc::new(builder.finish()))
}

fn concat_dictionaries<K: ArrowDictionaryKeyType>(
    arrays: &[&dyn Array],
) -> Result<ArrayRef, ArrowError> {
    let mut output_len = 0;
    let dictionaries: Vec<_> = arrays
        .iter()
        .map(|x| x.as_dictionary::<K>())
        .inspect(|d| output_len += d.len())
        .collect();

    if !should_merge_dictionary_values::<K>(&dictionaries, output_len).0 {
        return concat_fallback(arrays, Capacities::Array(output_len));
    }

    let merged = merge_dictionary_values(&dictionaries, None, None)?;

    // Recompute keys
    let mut key_values = Vec::with_capacity(output_len);

    let mut has_nulls = false;
    for (d, mapping) in dictionaries.iter().zip(merged.key_mappings) {
        has_nulls |= d.null_count() != 0;
        match mapping {
            KeyMapping::Dense(mapping) => key_values.extend(
                d.keys()
                    .values()
                    .iter()
                    .map(|key| mapping.get(key.as_usize()).copied().unwrap_or_default()),
            ),
            KeyMapping::Sparse(mapping) => key_values.extend(
                d.keys()
                    .values()
                    .iter()
                    .map(|key| mapping.get(&key.as_usize()).copied().unwrap_or_default()),
            ),
        }
    }

    let nulls = has_nulls.then(|| {
        let mut nulls = BooleanBufferBuilder::new(output_len);
        for d in &dictionaries {
            match d.nulls() {
                Some(n) => nulls.append_buffer(n.inner()),
                None => nulls.append_n(d.len(), true),
            }
        }
        NullBuffer::new(nulls.finish())
    });

    let keys = PrimitiveArray::<K>::try_new(key_values.into(), nulls)?;
    // Sanity check
    assert_eq!(keys.len(), output_len);

    let array = unsafe { DictionaryArray::new_unchecked(keys, merged.values) };
    Ok(Arc::new(array))
}

/// Concatenates the child values and the validity bitmaps, without the per-array
/// [`ArrayData`](arrow_data::ArrayData) that [`concat_fallback`] builds: with many short arrays
/// that is most of the cost.
fn concat_fixed_size_list(
    arrays: &[&dyn Array],
    field: &FieldRef,
    size: i32,
) -> Result<ArrayRef, ArrowError> {
    let mut lists: Vec<&FixedSizeListArray> = Vec::with_capacity(arrays.len());
    let mut values: Vec<&dyn Array> = Vec::with_capacity(arrays.len());
    let (mut len, mut any_nulls) = (0, false);
    for a in arrays {
        let l = a.as_fixed_size_list();
        len += l.len();
        any_nulls |= l.null_count() != 0;
        values.push(l.values().as_ref());
        lists.push(l);
    }

    let nulls = any_nulls.then(|| {
        let mut nulls = BooleanBufferBuilder::new(len);
        for l in &lists {
            match l.nulls() {
                Some(n) => nulls.append_buffer(n.inner()),
                None => nulls.append_n(l.len(), true),
            }
        }
        NullBuffer::new(nulls.finish())
    });

    // Equal list types imply equal child types, so skip the check in `concat`.
    let values = concat_same_type(&values, field.data_type())?;

    Ok(Arc::new(FixedSizeListArray::try_new_with_length(
        Arc::clone(field),
        size,
        values,
        nulls,
        len,
    )?))
}

fn concat_lists<OffsetSize: OffsetSizeTrait>(
    arrays: &[&dyn Array],
    field: &FieldRef,
) -> Result<ArrayRef, ArrowError> {
    let mut output_len = 0;
    let mut list_has_nulls = false;
    let mut list_has_slices = false;

    let lists = arrays
        .iter()
        .map(|x| x.as_list::<OffsetSize>())
        .inspect(|l| {
            output_len += l.len();
            list_has_nulls |= l.null_count() != 0;
            list_has_slices |= l.offsets()[0] > OffsetSize::zero()
                || l.offsets().last().as_usize() < l.values().len();
        })
        .collect::<Vec<_>>();

    let lists_nulls = list_has_nulls.then(|| {
        let mut nulls = BooleanBufferBuilder::new(output_len);
        for l in &lists {
            match l.nulls() {
                Some(n) => nulls.append_buffer(n.inner()),
                None => nulls.append_n(l.len(), true),
            }
        }
        NullBuffer::new(nulls.finish())
    });

    // If any of the lists have slices, we need to slice the values
    // to ensure that the offsets are correct
    let mut sliced_values;
    let values: Vec<&dyn Array> = if list_has_slices {
        sliced_values = Vec::with_capacity(lists.len());
        for l in &lists {
            // if the first offset is non-zero, we need to slice the values so when
            // we concatenate them below only the relevant values are included
            let offsets = l.offsets();
            let start_offset = offsets[0].as_usize();
            let end_offset = offsets.last().as_usize();
            sliced_values.push(l.values().slice(start_offset, end_offset - start_offset));
        }
        sliced_values.iter().map(|a| a.as_ref()).collect()
    } else {
        lists.iter().map(|x| x.values().as_ref()).collect()
    };

    let concatenated_values = concat(values.as_slice())?;

    // Merge value offsets from the lists
    let value_offset_buffer =
        OffsetBuffer::<OffsetSize>::from_lengths(lists.iter().flat_map(|x| x.offsets().lengths()));

    let array = GenericListArray::<OffsetSize>::try_new(
        Arc::clone(field),
        value_offset_buffer,
        concatenated_values,
        lists_nulls,
    )?;

    Ok(Arc::new(array))
}

fn concat_maps(
    arrays: &[&dyn Array],
    field: &FieldRef,
    ordered: bool,
) -> Result<ArrayRef, ArrowError> {
    let mut output_len = 0;
    let mut map_has_nulls = false;
    let mut map_has_slices = false;

    let maps = arrays
        .iter()
        .map(|x| x.as_map())
        .inspect(|m| {
            output_len += m.len();
            map_has_nulls |= m.null_count() != 0;
            map_has_slices |=
                m.offsets()[0] > 0 || m.offsets().last().as_usize() < m.entries().len();
        })
        .collect::<Vec<_>>();

    let map_nulls = map_has_nulls.then(|| {
        let mut nulls = BooleanBufferBuilder::new(output_len);
        for m in &maps {
            match m.nulls() {
                Some(n) => nulls.append_buffer(n.inner()),
                None => nulls.append_n(m.len(), true),
            }
        }
        NullBuffer::new(nulls.finish())
    });

    // If any of the maps have slices, we need to slice the entries
    // to ensure that the offsets are correct
    let mut sliced_entries: Vec<ArrayRef>;
    let entries: Vec<&dyn Array> = if map_has_slices {
        sliced_entries = Vec::with_capacity(maps.len());
        for m in &maps {
            let offsets = m.offsets();
            let start_offset = offsets[0].as_usize();
            let end_offset = offsets.last().as_usize();
            let entries_arr: &dyn Array = m.entries();
            sliced_entries.push(entries_arr.slice(start_offset, end_offset - start_offset));
        }
        sliced_entries.iter().map(|a| a.as_ref()).collect()
    } else {
        maps.iter().map(|m| m.entries() as &dyn Array).collect()
    };

    let concatenated_entries = concat(entries.as_slice())?;

    // Merge value offsets from the maps
    let value_offset_buffer =
        OffsetBuffer::<i32>::from_lengths(maps.iter().flat_map(|m| m.offsets().lengths()));

    let array = MapArray::try_new(
        Arc::clone(field),
        value_offset_buffer,
        // Safety: Map entries are always StructArrays, so this downcast is guaranteed to succeed
        concatenated_entries.as_struct().clone(),
        map_nulls,
        ordered,
    )?;

    Ok(Arc::new(array))
}

fn concat_list_view<OffsetSize: OffsetSizeTrait>(
    arrays: &[&dyn Array],
    field: &FieldRef,
) -> Result<ArrayRef, ArrowError> {
    let mut output_len = 0;
    let mut list_has_nulls = false;

    let lists = arrays
        .iter()
        .map(|x| x.as_list_view::<OffsetSize>())
        .inspect(|l| {
            output_len += l.len();
            list_has_nulls |= l.null_count() != 0;
        })
        .collect::<Vec<_>>();

    let lists_nulls = list_has_nulls.then(|| {
        let mut nulls = BooleanBufferBuilder::new(output_len);
        for l in &lists {
            match l.nulls() {
                Some(n) => nulls.append_buffer(n.inner()),
                None => nulls.append_n(l.len(), true),
            }
        }
        NullBuffer::new(nulls.finish())
    });

    let values: Vec<&dyn Array> = lists.iter().map(|l| l.values().as_ref()).collect();

    let concatenated_values = concat(values.as_slice())?;

    let sizes: ScalarBuffer<OffsetSize> = lists.iter().flat_map(|x| x.sizes()).copied().collect();

    let offsets_capacity = lists
        .iter()
        .try_fold(0usize, |acc, l| acc.checked_add(l.offsets().len()))
        .and_then(|len| len.checked_mul(std::mem::size_of::<OffsetSize>()))
        .ok_or_else(|| ArrowError::MemoryError("concatenated offsets size overflow".into()))?;
    let mut offsets = MutableBuffer::try_with_capacity(offsets_capacity)
        .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
    let mut global_offset = OffsetSize::zero();
    for l in &lists {
        for &offset in l.offsets() {
            offsets.push(offset + global_offset);
        }

        // advance the offsets
        global_offset += OffsetSize::from_usize(l.values().len()).unwrap();
    }

    let offsets = ScalarBuffer::from(offsets);

    let array = GenericListViewArray::try_new(
        field.clone(),
        offsets,
        sizes,
        concatenated_values,
        lists_nulls,
    )?;

    Ok(Arc::new(array))
}

fn concat_primitives<T: ArrowPrimitiveType>(arrays: &[&dyn Array]) -> Result<ArrayRef, ArrowError> {
    let mut builder = PrimitiveBuilder::<T>::with_capacity(arrays.iter().map(|a| a.len()).sum())
        .with_data_type(arrays[0].data_type().clone());

    for array in arrays {
        builder.append_array(array.as_primitive());
    }

    Ok(Arc::new(builder.finish()))
}

fn concat_boolean(arrays: &[&dyn Array]) -> Result<ArrayRef, ArrowError> {
    let mut builder = BooleanBuilder::with_capacity(arrays.iter().map(|a| a.len()).sum());

    for array in arrays {
        builder.append_array(array.as_boolean());
    }

    Ok(Arc::new(builder.finish()))
}

fn concat_bytes<T: ByteArrayType>(arrays: &[&dyn Array]) -> Result<ArrayRef, ArrowError> {
    let Capacities::Binary(item_capacity, Some(bytes_capacity)) = binary_capacity::<T>(arrays)?
    else {
        unreachable!()
    };

    let mut builder = GenericByteBuilder::<T>::with_capacity(item_capacity, bytes_capacity);

    for array in arrays {
        builder.append_array(array.as_bytes::<T>())?;
    }

    Ok(Arc::new(builder.finish()))
}

fn concat_structs(arrays: &[&dyn Array], fields: &Fields) -> Result<ArrayRef, ArrowError> {
    let mut len = 0;
    let mut has_nulls = false;
    let structs = arrays
        .iter()
        .map(|a| {
            len += a.len();
            has_nulls |= a.null_count() > 0;
            a.as_struct()
        })
        .collect::<Vec<_>>();

    let nulls = has_nulls.then(|| {
        let mut b = BooleanBufferBuilder::new(len);
        for s in &structs {
            match s.nulls() {
                Some(n) => b.append_buffer(n.inner()),
                None => b.append_n(s.len(), true),
            }
        }
        NullBuffer::new(b.finish())
    });

    let column_concat_result = (0..fields.len())
        .map(|i| {
            let extracted_cols = structs
                .iter()
                .map(|s| s.column(i).as_ref())
                .collect::<Vec<_>>();
            concat(&extracted_cols)
        })
        .collect::<Result<Vec<_>, ArrowError>>()?;

    Ok(Arc::new(StructArray::try_new_with_length(
        fields.clone(),
        column_concat_result,
        nulls,
        len,
    )?))
}

/// Concatenate multiple RunArray instances into a single RunArray.
///
/// This function handles the special case of concatenating RunArrays by:
/// 1. Collecting all run ends and values from input arrays
/// 2. Adjusting run ends to account for the length of previous arrays
/// 3. Creating a new RunArray with the combined data
fn concat_run_arrays<R: RunEndIndexType>(arrays: &[&dyn Array]) -> Result<ArrayRef, ArrowError>
where
    R::Native: Add<Output = R::Native>,
{
    let run_arrays: Vec<_> = arrays
        .iter()
        .map(|x| x.as_run::<R>())
        .filter(|x| !x.run_ends().is_empty())
        .collect();

    if run_arrays.is_empty() {
        // If all input arrays are empty then handle here otherwise we
        // lose the type below
        return Ok(new_empty_array(arrays[0].data_type()));
    }

    // Reject lengths that do not fit in `R` before any `R::Native` arithmetic can wrap.
    let total_len: usize = run_arrays.iter().map(|r| r.len()).sum();
    if R::Native::from_usize(total_len).is_none() {
        return Err(ArrowError::RunEndIndexOverflowError);
    }

    // The run ends need to be adjusted by the sum of the lengths of the previous arrays.
    let needed_run_end_adjustments = std::iter::once(R::default_value())
        .chain(
            run_arrays
                .iter()
                .scan(R::default_value(), |acc, run_array| {
                    *acc = *acc + R::Native::from_usize(run_array.len()).unwrap();
                    Some(*acc)
                }),
        )
        .collect::<Vec<_>>();

    let run_ends_array =
        PrimitiveArray::<R>::from_iter_values(run_arrays.iter().enumerate().flat_map(
            move |(i, run_array)| {
                let adjustment = needed_run_end_adjustments[i];
                run_array
                    .run_ends()
                    .sliced_values()
                    .map(move |run_end| run_end + adjustment)
            },
        ));

    let values_slices: Vec<ArrayRef> = run_arrays
        .iter()
        .map(|run_array| run_array.values_slice())
        .collect();

    let all_values = concat(&values_slices.iter().map(|x| x.as_ref()).collect::<Vec<_>>())?;

    let data_type = run_arrays[0].data_type().clone();
    let (_, run_ends_values, _) = run_ends_array.into_parts();

    // Safety: inputs are valid RunArrays; adjusted run ends are strictly increasing
    // and end at `total_len`. Physical length matches `all_values`.
    let run_ends = unsafe { RunEndBuffer::new_unchecked(run_ends_values, 0, total_len) };
    Ok(Arc::new(unsafe {
        RunArray::<R>::new_unchecked(data_type, run_ends, all_values)
    }))
}

macro_rules! dict_helper {
    ($t:ty, $arrays:expr) => {
        return concat_dictionaries::<$t>($arrays)
    };
}

macro_rules! primitive_concat {
    ($t:ty, $arrays:expr) => {
        return concat_primitives::<$t>($arrays)
    };
}

fn get_capacity(arrays: &[&dyn Array], data_type: &DataType) -> Result<Capacities, ArrowError> {
    match data_type {
        DataType::Utf8 => binary_capacity::<Utf8Type>(arrays),
        DataType::LargeUtf8 => binary_capacity::<LargeUtf8Type>(arrays),
        DataType::Binary => binary_capacity::<BinaryType>(arrays),
        DataType::LargeBinary => binary_capacity::<LargeBinaryType>(arrays),
        DataType::FixedSizeList(_, _) => fixed_size_list_capacity(arrays, data_type),
        _ => arrays
            .iter()
            .try_fold(0usize, |total, array| total.checked_add(array.len()))
            .map(Capacities::Array)
            .ok_or_else(|| ArrowError::MemoryError("concatenated length overflow".into())),
    }
}

/// Concatenate multiple [Array] of the same type into a single [ArrayRef].
pub fn concat(arrays: &[&dyn Array]) -> Result<ArrayRef, ArrowError> {
    if arrays.is_empty() {
        return Err(ArrowError::ComputeError(
            "concat requires input of at least one array".to_string(),
        ));
    } else if arrays.len() == 1 {
        let array = arrays[0];
        return Ok(array.slice(0, array.len()));
    }

    let d = arrays[0].data_type();
    if arrays.iter().skip(1).any(|array| array.data_type() != d) {
        // Create error message with up to 10 unique data types in the order they appear
        let error_message = {
            // 10 max unique data types to print and another 1 to know if there are more
            let mut unique_data_types = HashSet::with_capacity(11);

            let mut error_message =
                format!("It is not possible to concatenate arrays of different data types ({d}");
            unique_data_types.insert(d);

            for array in arrays {
                let is_unique = unique_data_types.insert(array.data_type());

                if unique_data_types.len() == 11 {
                    error_message.push_str(", ...");
                    break;
                }

                if is_unique {
                    error_message.push_str(", ");
                    error_message.push_str(&array.data_type().to_string());
                }
            }

            error_message.push_str(").");

            error_message
        };

        return Err(ArrowError::InvalidArgumentError(error_message));
    }

    concat_same_type(arrays, d)
}

fn concat_same_type(arrays: &[&dyn Array], d: &DataType) -> Result<ArrayRef, ArrowError> {
    downcast_primitive! {
        d => (primitive_concat, arrays),
        DataType::Boolean => concat_boolean(arrays),
        DataType::Dictionary(k, _) => {
            downcast_integer! {
                k.as_ref() => (dict_helper, arrays),
                _ => unreachable!("illegal dictionary key type {k}")
            }
        }
        DataType::List(field) => concat_lists::<i32>(arrays, field),
        DataType::LargeList(field) => concat_lists::<i64>(arrays, field),
        DataType::FixedSizeList(field, size) => concat_fixed_size_list(arrays, field, *size),
        DataType::ListView(field) => concat_list_view::<i32>(arrays, field),
        DataType::LargeListView(field) => concat_list_view::<i64>(arrays, field),
        DataType::Map(field, ordered) => concat_maps(arrays, field, *ordered),
        DataType::Struct(fields) => concat_structs(arrays, fields),
        DataType::Utf8 => concat_bytes::<Utf8Type>(arrays),
        DataType::LargeUtf8 => concat_bytes::<LargeUtf8Type>(arrays),
        DataType::Binary => concat_bytes::<BinaryType>(arrays),
        DataType::LargeBinary => concat_bytes::<LargeBinaryType>(arrays),
        DataType::RunEndEncoded(r, _) => {
            // Handle RunEndEncoded arrays with special concat function
            // We need to downcast based on the run end type
            match r.data_type() {
                DataType::Int16 => concat_run_arrays::<Int16Type>(arrays),
                DataType::Int32 => concat_run_arrays::<Int32Type>(arrays),
                DataType::Int64 => concat_run_arrays::<Int64Type>(arrays),
                _ => unreachable!("Unsupported run end index type: {r:?}"),
            }
        }
        DataType::Utf8View => concat_byte_view::<StringViewType>(arrays),
        DataType::BinaryView => concat_byte_view::<BinaryViewType>(arrays),
        _ => {
            let capacity = get_capacity(arrays, d)?;
            concat_fallback(arrays, capacity)
        }
    }
}

/// Concatenates arrays using MutableArrayData
///
/// This will naively concatenate dictionaries
fn concat_fallback(arrays: &[&dyn Array], capacity: Capacities) -> Result<ArrayRef, ArrowError> {
    let array_data: Vec<_> = arrays.iter().map(|a| a.to_data()).collect::<Vec<_>>();
    let array_data = array_data.iter().collect();
    let mut mutable = MutableArrayData::try_with_capacities(array_data, false, capacity)?;

    for (i, a) in arrays.iter().enumerate() {
        mutable.try_extend(i, 0, a.len())?
    }

    Ok(make_array(mutable.freeze()))
}

/// Concatenates `batches` together into a single [`RecordBatch`].
///
/// The output batch has the specified `schemas`; The schema of the
/// input are ignored.
///
/// # Notes
///
/// - Callers should budget for peak memory use to approach 2x the input
///   size, as the input batches and output arrays co-exist during construction.
/// - Arrays with `i32` offsets, such as `StringArray` and `BinaryArray`, only
///   support up to ~2GiB of payloads. Concatenating large arrays of these types
///   can cause offset overflows.
///
/// # Errors
///
/// Returns an error if the types of underlying arrays are different.
pub fn concat_batches<'a>(
    schema: &SchemaRef,
    input_batches: impl IntoIterator<Item = &'a RecordBatch>,
) -> Result<RecordBatch, ArrowError> {
    // When schema is empty, sum the number of the rows of all batches
    if schema.fields().is_empty() {
        let num_rows: usize = input_batches.into_iter().map(RecordBatch::num_rows).sum();
        let mut options = RecordBatchOptions::default();
        options.row_count = Some(num_rows);
        return RecordBatch::try_new_with_options(schema.clone(), vec![], &options);
    }

    let batches: Vec<&RecordBatch> = input_batches.into_iter().collect();
    if batches.is_empty() {
        return Ok(RecordBatch::new_empty(schema.clone()));
    }
    let field_num = schema.fields().len();
    let mut arrays = Vec::with_capacity(field_num);
    for i in 0..field_num {
        let array = concat(
            &batches
                .iter()
                .map(|batch| batch.column(i).as_ref())
                .collect::<Vec<_>>(),
        )?;
        arrays.push(array);
    }
    RecordBatch::try_new(schema.clone(), arrays)
}

#[cfg(test)]
mod tests {
    use super::*;
    use arrow_array::builder::{
        GenericListBuilder, Int32Builder as Int32ArrayBuilder, Int64Builder, ListViewBuilder,
        MapBuilder, StringBuilder, StringDictionaryBuilder,
    };
    use arrow_schema::{Field, Schema};
    use std::fmt::Debug;

    #[test]
    fn test_dict_overflow_9366() {
        use arrow_schema::DataType;

        let schema = Arc::new(Schema::new(vec![Field::new(
            "a",
            DataType::Dictionary(
                Box::new(DataType::UInt8),
                Box::new(DataType::FixedSizeBinary(8)),
            ),
            false,
        )]));
        let make = |vals: std::ops::Range<u64>| {
            let dict = FixedSizeBinaryArray::try_from_iter(vals.map(|i| i.to_le_bytes())).unwrap();
            let keys = UInt8Array::from_iter_values(0..128);
            let arr = DictionaryArray::try_new(keys, Arc::new(dict)).unwrap();
            RecordBatch::try_new(schema.clone(), vec![Arc::new(arr)]).unwrap()
        };
        // 256 distinct values fit in u8 keys (0..=255): concat must succeed.
        let out = concat_batches(&schema, &[make(0..128), make(128..256)]).unwrap();
        assert_eq!(out.num_rows(), 256);
        let dict = out.column(0).as_dictionary::<UInt8Type>();
        assert_eq!(dict.values().len(), 256);
    }

    #[test]
    fn test_dict_overflow_i8_9366() {
        use arrow_schema::DataType;

        // Same boundary for a signed key type: i8 holds 128 keys (0..=127).
        let schema = Arc::new(Schema::new(vec![Field::new(
            "a",
            DataType::Dictionary(
                Box::new(DataType::Int8),
                Box::new(DataType::FixedSizeBinary(8)),
            ),
            false,
        )]));
        let make = |vals: std::ops::Range<u64>| {
            let dict = FixedSizeBinaryArray::try_from_iter(vals.map(|i| i.to_le_bytes())).unwrap();
            let keys = Int8Array::from_iter_values(0..64);
            let arr = DictionaryArray::try_new(keys, Arc::new(dict)).unwrap();
            RecordBatch::try_new(schema.clone(), vec![Arc::new(arr)]).unwrap()
        };
        let out = concat_batches(&schema, &[make(0..64), make(64..128)]).unwrap();
        assert_eq!(out.num_rows(), 128);
        let dict = out.column(0).as_dictionary::<Int8Type>();
        assert_eq!(dict.values().len(), 128);
    }

    #[test]
    fn test_concat_empty_vec() {
        let re = concat(&[]);
        assert!(re.is_err());
    }

    #[test]
    fn test_concat_batches_no_columns() {
        // Test concat using empty schema / batches without columns
        let schema = Arc::new(Schema::empty());

        let mut options = RecordBatchOptions::default();
        options.row_count = Some(100);
        let batch = RecordBatch::try_new_with_options(schema.clone(), vec![], &options).unwrap();
        // put in 2 batches of 100 rows each
        let re = concat_batches(&schema, &[batch.clone(), batch]).unwrap();

        assert_eq!(re.num_rows(), 200);
    }

    #[test]
    fn test_concat_one_element_vec() {
        let arr = Arc::new(PrimitiveArray::<Int64Type>::from(vec![
            Some(-1),
            Some(2),
            None,
        ])) as ArrayRef;
        let result = concat(&[arr.as_ref()]).unwrap();
        assert_eq!(
            &arr, &result,
            "concatenating single element array gives back the same result"
        );
    }

    #[test]
    fn test_concat_incompatible_datatypes() {
        let re = concat(&[
            &PrimitiveArray::<Int64Type>::from(vec![Some(-1), Some(2), None]),
            // 2 string to make sure we only mention unique types
            &StringArray::from(vec![Some("hello"), Some("bar"), Some("world")]),
            &StringArray::from(vec![Some("hey"), Some(""), Some("you")]),
            // Another type to make sure we are showing all the incompatible types
            &PrimitiveArray::<Int32Type>::from(vec![Some(-1), Some(2), None]),
        ]);

        assert_eq!(
            re.unwrap_err().to_string(),
            "Invalid argument error: It is not possible to concatenate arrays of different data types (Int64, Utf8, Int32)."
        );
    }

    #[test]
    fn test_concat_10_incompatible_datatypes_should_include_all_of_them() {
        let re = concat(&[
            &PrimitiveArray::<Int64Type>::from(vec![Some(-1), Some(2), None]),
            // 2 string to make sure we only mention unique types
            &StringArray::from(vec![Some("hello"), Some("bar"), Some("world")]),
            &StringArray::from(vec![Some("hey"), Some(""), Some("you")]),
            // Another type to make sure we are showing all the incompatible types
            &PrimitiveArray::<Int32Type>::from(vec![Some(-1), Some(2), None]),
            &PrimitiveArray::<Int8Type>::from(vec![Some(-1), Some(2), None]),
            &PrimitiveArray::<Int16Type>::from(vec![Some(-1), Some(2), None]),
            &PrimitiveArray::<UInt8Type>::from(vec![Some(1), Some(2), None]),
            &PrimitiveArray::<UInt16Type>::from(vec![Some(1), Some(2), None]),
            &PrimitiveArray::<UInt32Type>::from(vec![Some(1), Some(2), None]),
            // Non unique
            &PrimitiveArray::<UInt16Type>::from(vec![Some(1), Some(2), None]),
            &PrimitiveArray::<UInt64Type>::from(vec![Some(1), Some(2), None]),
            &PrimitiveArray::<Float32Type>::from(vec![Some(1.0), Some(2.0), None]),
        ]);

        assert_eq!(
            re.unwrap_err().to_string(),
            "Invalid argument error: It is not possible to concatenate arrays of different data types (Int64, Utf8, Int32, Int8, Int16, UInt8, UInt16, UInt32, UInt64, Float32)."
        );
    }

    #[test]
    fn test_concat_11_incompatible_datatypes_should_only_include_10() {
        let re = concat(&[
            &PrimitiveArray::<Int64Type>::from(vec![Some(-1), Some(2), None]),
            // 2 string to make sure we only mention unique types
            &StringArray::from(vec![Some("hello"), Some("bar"), Some("world")]),
            &StringArray::from(vec![Some("hey"), Some(""), Some("you")]),
            // Another type to make sure we are showing all the incompatible types
            &PrimitiveArray::<Int32Type>::from(vec![Some(-1), Some(2), None]),
            &PrimitiveArray::<Int8Type>::from(vec![Some(-1), Some(2), None]),
            &PrimitiveArray::<Int16Type>::from(vec![Some(-1), Some(2), None]),
            &PrimitiveArray::<UInt8Type>::from(vec![Some(1), Some(2), None]),
            &PrimitiveArray::<UInt16Type>::from(vec![Some(1), Some(2), None]),
            &PrimitiveArray::<UInt32Type>::from(vec![Some(1), Some(2), None]),
            // Non unique
            &PrimitiveArray::<UInt16Type>::from(vec![Some(1), Some(2), None]),
            &PrimitiveArray::<UInt64Type>::from(vec![Some(1), Some(2), None]),
            &PrimitiveArray::<Float32Type>::from(vec![Some(1.0), Some(2.0), None]),
            &PrimitiveArray::<Float64Type>::from(vec![Some(1.0), Some(2.0), None]),
        ]);

        assert_eq!(
            re.unwrap_err().to_string(),
            "Invalid argument error: It is not possible to concatenate arrays of different data types (Int64, Utf8, Int32, Int8, Int16, UInt8, UInt16, UInt32, UInt64, Float32, ...)."
        );
    }

    #[test]
    #[cfg_attr(miri, ignore)] // Unsupported inline assembly
    fn test_concat_13_incompatible_datatypes_should_not_include_all_of_them() {
        let re = concat(&[
            &PrimitiveArray::<Int64Type>::from(vec![Some(-1), Some(2), None]),
            // 2 string to make sure we only mention unique types
            &StringArray::from(vec![Some("hello"), Some("bar"), Some("world")]),
            &StringArray::from(vec![Some("hey"), Some(""), Some("you")]),
            // Another type to make sure we are showing all the incompatible types
            &PrimitiveArray::<Int32Type>::from(vec![Some(-1), Some(2), None]),
            &PrimitiveArray::<Int8Type>::from(vec![Some(-1), Some(2), None]),
            &PrimitiveArray::<Int16Type>::from(vec![Some(-1), Some(2), None]),
            &PrimitiveArray::<UInt8Type>::from(vec![Some(1), Some(2), None]),
            &PrimitiveArray::<UInt16Type>::from(vec![Some(1), Some(2), None]),
            &PrimitiveArray::<UInt32Type>::from(vec![Some(1), Some(2), None]),
            // Non unique
            &PrimitiveArray::<UInt16Type>::from(vec![Some(1), Some(2), None]),
            &PrimitiveArray::<UInt64Type>::from(vec![Some(1), Some(2), None]),
            &PrimitiveArray::<Float32Type>::from(vec![Some(1.0), Some(2.0), None]),
            &PrimitiveArray::<Float64Type>::from(vec![Some(1.0), Some(2.0), None]),
            &PrimitiveArray::<Float16Type>::new_null(3),
            &BooleanArray::from(vec![Some(true), Some(false), None]),
        ]);

        assert_eq!(
            re.unwrap_err().to_string(),
            "Invalid argument error: It is not possible to concatenate arrays of different data types (Int64, Utf8, Int32, Int8, Int16, UInt8, UInt16, UInt32, UInt64, Float32, ...)."
        );
    }

    #[test]
    fn test_concat_string_arrays() {
        let arr = concat(&[
            &StringArray::from(vec!["hello", "world"]),
            &StringArray::from(vec!["2", "3", "4"]),
            &StringArray::from(vec![Some("foo"), Some("bar"), None, Some("baz")]),
        ])
        .unwrap();

        let expected_output = Arc::new(StringArray::from(vec![
            Some("hello"),
            Some("world"),
            Some("2"),
            Some("3"),
            Some("4"),
            Some("foo"),
            Some("bar"),
            None,
            Some("baz"),
        ])) as ArrayRef;

        assert_eq!(&arr, &expected_output);
    }

    #[test]
    fn test_concat_string_view_arrays() {
        let arr = concat(&[
            &StringViewArray::from(vec!["helloxxxxxxxxxxa", "world____________"]),
            &StringViewArray::from(vec!["helloxxxxxxxxxxy", "3", "4"]),
            &StringViewArray::from(vec![Some("foo"), Some("bar"), None, Some("baz")]),
        ])
        .unwrap();

        let expected_output = Arc::new(StringViewArray::from(vec![
            Some("helloxxxxxxxxxxa"),
            Some("world____________"),
            Some("helloxxxxxxxxxxy"),
            Some("3"),
            Some("4"),
            Some("foo"),
            Some("bar"),
            None,
            Some("baz"),
        ])) as ArrayRef;

        assert_eq!(&arr, &expected_output);
    }

    #[test]
    fn test_concat_primitive_arrays() {
        let arr = concat(&[
            &PrimitiveArray::<Int64Type>::from(vec![Some(-1), Some(-1), Some(2), None, None]),
            &PrimitiveArray::<Int64Type>::from(vec![Some(101), Some(102), Some(103), None]),
            &PrimitiveArray::<Int64Type>::from(vec![Some(256), Some(512), Some(1024)]),
        ])
        .unwrap();

        let expected_output = Arc::new(PrimitiveArray::<Int64Type>::from(vec![
            Some(-1),
            Some(-1),
            Some(2),
            None,
            None,
            Some(101),
            Some(102),
            Some(103),
            None,
            Some(256),
            Some(512),
            Some(1024),
        ])) as ArrayRef;

        assert_eq!(&arr, &expected_output);
    }

    #[test]
    fn test_concat_primitive_array_slices() {
        let input_1 =
            PrimitiveArray::<Int64Type>::from(vec![Some(-1), Some(-1), Some(2), None, None])
                .slice(1, 3);

        let input_2 =
            PrimitiveArray::<Int64Type>::from(vec![Some(101), Some(102), Some(103), None])
                .slice(1, 3);
        let arr = concat(&[&input_1, &input_2]).unwrap();

        let expected_output = Arc::new(PrimitiveArray::<Int64Type>::from(vec![
            Some(-1),
            Some(2),
            None,
            Some(102),
            Some(103),
            None,
        ])) as ArrayRef;

        assert_eq!(&arr, &expected_output);
    }

    #[test]
    fn test_concat_boolean_primitive_arrays() {
        let arr = concat(&[
            &BooleanArray::from(vec![
                Some(true),
                Some(true),
                Some(false),
                None,
                None,
                Some(false),
            ]),
            &BooleanArray::from(vec![None, Some(false), Some(true), Some(false)]),
        ])
        .unwrap();

        let expected_output = Arc::new(BooleanArray::from(vec![
            Some(true),
            Some(true),
            Some(false),
            None,
            None,
            Some(false),
            None,
            Some(false),
            Some(true),
            Some(false),
        ])) as ArrayRef;

        assert_eq!(&arr, &expected_output);
    }

    #[test]
    fn test_concat_primitive_list_arrays() {
        let list1 = [
            Some(vec![Some(-1), Some(-1), Some(2), None, None]),
            Some(vec![]),
            None,
            Some(vec![Some(10)]),
        ];
        let list1_array = ListArray::from_iter_primitive::<Int64Type, _, _>(list1.clone());

        let list2 = [
            None,
            Some(vec![Some(100), None, Some(101)]),
            Some(vec![Some(102)]),
        ];
        let list2_array = ListArray::from_iter_primitive::<Int64Type, _, _>(list2.clone());

        let list3 = [Some(vec![Some(1000), Some(1001)])];
        let list3_array = ListArray::from_iter_primitive::<Int64Type, _, _>(list3.clone());

        let array_result = concat(&[&list1_array, &list2_array, &list3_array]).unwrap();

        let expected = list1.into_iter().chain(list2).chain(list3);
        let array_expected = ListArray::from_iter_primitive::<Int64Type, _, _>(expected);

        assert_eq!(array_result.as_ref(), &array_expected as &dyn Array);
    }

    #[test]
    fn test_concat_primitive_list_arrays_slices() {
        let list1 = [
            Some(vec![Some(-1), Some(-1), Some(2), None, None]),
            Some(vec![]), // In slice
            None,         // In slice
            Some(vec![Some(10)]),
        ];
        let list1_array = ListArray::from_iter_primitive::<Int64Type, _, _>(list1.clone());
        let list1_array = list1_array.slice(1, 2);
        let list1_values = list1.into_iter().skip(1).take(2);

        let list2 = [
            None,
            Some(vec![Some(100), None, Some(101)]),
            Some(vec![Some(102)]),
        ];
        let list2_array = ListArray::from_iter_primitive::<Int64Type, _, _>(list2.clone());

        // verify that this test covers the case when the first offset is non zero
        assert!(list1_array.offsets()[0].as_usize() > 0);
        let array_result = concat(&[&list1_array, &list2_array]).unwrap();

        let expected = list1_values.chain(list2);
        let array_expected = ListArray::from_iter_primitive::<Int64Type, _, _>(expected);

        assert_eq!(array_result.as_ref(), &array_expected as &dyn Array);
    }

    #[test]
    fn test_concat_primitive_list_arrays_sliced_lengths() {
        let list1 = [
            Some(vec![Some(-1), Some(-1), Some(2), None, None]), // In slice
            Some(vec![]),                                        // In slice
            None,                                                // In slice
            Some(vec![Some(10)]),
        ];
        let list1_array = ListArray::from_iter_primitive::<Int64Type, _, _>(list1.clone());
        let list1_array = list1_array.slice(0, 3); // no offset, but not all values
        let list1_values = list1.into_iter().take(3);

        let list2 = [
            None,
            Some(vec![Some(100), None, Some(101)]),
            Some(vec![Some(102)]),
        ];
        let list2_array = ListArray::from_iter_primitive::<Int64Type, _, _>(list2.clone());

        // verify that this test covers the case when the first offset is zero, but the
        // last offset doesn't cover the entire array
        assert_eq!(list1_array.offsets()[0].as_usize(), 0);
        assert!(list1_array.offsets().last().as_usize() < list1_array.values().len());
        let array_result = concat(&[&list1_array, &list2_array]).unwrap();

        let expected = list1_values.chain(list2);
        let array_expected = ListArray::from_iter_primitive::<Int64Type, _, _>(expected);

        assert_eq!(array_result.as_ref(), &array_expected as &dyn Array);
    }

    #[test]
    fn test_concat_primitive_fixed_size_list_arrays() {
        let list1 = [
            Some(vec![Some(-1), None]),
            None,
            Some(vec![Some(10), Some(20)]),
        ];
        let list1_array =
            FixedSizeListArray::from_iter_primitive::<Int64Type, _, _>(list1.clone(), 2);

        let list2 = [
            None,
            Some(vec![Some(100), None]),
            Some(vec![Some(102), Some(103)]),
        ];
        let list2_array =
            FixedSizeListArray::from_iter_primitive::<Int64Type, _, _>(list2.clone(), 2);

        let list3 = [Some(vec![Some(1000), Some(1001)])];
        let list3_array =
            FixedSizeListArray::from_iter_primitive::<Int64Type, _, _>(list3.clone(), 2);

        let array_result = concat(&[&list1_array, &list2_array, &list3_array]).unwrap();

        let expected = list1.into_iter().chain(list2).chain(list3);
        let array_expected =
            FixedSizeListArray::from_iter_primitive::<Int64Type, _, _>(expected, 2);

        assert_eq!(array_result.as_ref(), &array_expected as &dyn Array);
    }

    /// The fixed size list path against `concat_fallback`: slices, arrays with and without
    /// nulls mixed, nested lists, zero-sized lists and many one-row arrays.
    #[test]
    fn test_concat_fixed_size_list_matches_fallback() {
        let check = |arrays: &[&dyn Array]| {
            let expected =
                concat_fallback(arrays, get_capacity(arrays, arrays[0].data_type()).unwrap())
                    .unwrap();
            let got = concat(arrays).unwrap();
            assert_eq!(got.as_ref(), expected.as_ref());
            got.to_data().validate_full().unwrap();
        };

        let rows = [
            Some(vec![Some(1), None, Some(3)]),
            None,
            Some(vec![Some(4), Some(5), Some(6)]),
            Some(vec![None, None, None]),
            None,
            Some(vec![Some(7), Some(8), Some(9)]),
        ];
        let with_nulls = FixedSizeListArray::from_iter_primitive::<Int32Type, _, _>(rows, 3);
        let without_nulls = FixedSizeListArray::from_iter_primitive::<Int32Type, _, _>(
            (0..5).map(|i| Some(vec![Some(i), Some(i + 1), Some(i + 2)])),
            3,
        );
        check(&[&with_nulls, &without_nulls]);
        check(&[&without_nulls, &without_nulls]);
        check(&[
            &with_nulls.slice(1, 4),
            &without_nulls.slice(2, 2),
            &with_nulls,
        ]);

        let one_row: Vec<_> = (0..64).map(|i| with_nulls.slice(i % 6, 1)).collect();
        let one_row: Vec<&dyn Array> = one_row.iter().map(|a| a as &dyn Array).collect();
        check(&one_row);

        let nested = FixedSizeListArray::try_new(
            Arc::new(Field::new_list_field(with_nulls.data_type().clone(), true)),
            2,
            Arc::new(with_nulls.slice(0, 6)),
            Some(NullBuffer::from(vec![true, false, true])),
        )
        .unwrap();
        check(&[&nested, &nested.slice(1, 2)]);

        let zero_sized = FixedSizeListArray::try_new_with_length(
            Arc::new(Field::new_list_field(DataType::Int32, true)),
            0,
            Arc::new(Int32Array::from(Vec::<i32>::new())),
            Some(NullBuffer::from(vec![true, false, true, true])),
            4,
        )
        .unwrap();
        let zero_sized_valid = FixedSizeListArray::try_new_with_length(
            Arc::new(Field::new_list_field(DataType::Int32, true)),
            0,
            Arc::new(Int32Array::from(Vec::<i32>::new())),
            None,
            3,
        )
        .unwrap();
        check(&[&zero_sized, &zero_sized_valid, &zero_sized.slice(1, 2)]);
    }

    #[test]
    fn test_concat_list_view_arrays() {
        let list1 = [
            Some(vec![Some(-1), None]),
            None,
            Some(vec![Some(10), Some(20)]),
        ];
        let mut list1_array = ListViewBuilder::new(Int64Builder::new());
        for v in &list1 {
            list1_array.append_option(v.clone());
        }
        let list1_array = list1_array.finish();

        let list2 = [
            None,
            Some(vec![Some(100), None]),
            Some(vec![Some(102), Some(103)]),
        ];
        let mut list2_array = ListViewBuilder::new(Int64Builder::new());
        for v in &list2 {
            list2_array.append_option(v.clone());
        }
        let list2_array = list2_array.finish();

        let list3 = [Some(vec![Some(1000), Some(1001)])];
        let mut list3_array = ListViewBuilder::new(Int64Builder::new());
        for v in &list3 {
            list3_array.append_option(v.clone());
        }
        let list3_array = list3_array.finish();

        let array_result = concat(&[&list1_array, &list2_array, &list3_array]).unwrap();

        let expected: Vec<_> = list1.into_iter().chain(list2).chain(list3).collect();
        let mut array_expected = ListViewBuilder::new(Int64Builder::new());
        for v in &expected {
            array_expected.append_option(v.clone());
        }
        let array_expected = array_expected.finish();

        assert_eq!(array_result.as_ref(), &array_expected as &dyn Array);
    }

    #[test]
    fn test_concat_sliced_list_view_arrays() {
        let list1 = [
            Some(vec![Some(-1), None]),
            None,
            Some(vec![Some(10), Some(20)]),
        ];
        let mut list1_array = ListViewBuilder::new(Int64Builder::new());
        for v in &list1 {
            list1_array.append_option(v.clone());
        }
        let list1_array = list1_array.finish();

        let list2 = [
            None,
            Some(vec![Some(100), None]),
            Some(vec![Some(102), Some(103)]),
        ];
        let mut list2_array = ListViewBuilder::new(Int64Builder::new());
        for v in &list2 {
            list2_array.append_option(v.clone());
        }
        let list2_array = list2_array.finish();

        let list3 = [Some(vec![Some(1000), Some(1001)])];
        let mut list3_array = ListViewBuilder::new(Int64Builder::new());
        for v in &list3 {
            list3_array.append_option(v.clone());
        }
        let list3_array = list3_array.finish();

        // Concat sliced arrays.
        // ListView slicing will slice the offset/sizes but preserve the original values child.
        let array_result = concat(&[
            &list1_array.slice(1, 2),
            &list2_array.slice(1, 2),
            &list3_array.slice(0, 1),
        ])
        .unwrap();

        let expected: Vec<_> = vec![
            None,
            Some(vec![Some(10), Some(20)]),
            Some(vec![Some(100), None]),
            Some(vec![Some(102), Some(103)]),
            Some(vec![Some(1000), Some(1001)]),
        ];
        let mut array_expected = ListViewBuilder::new(Int64Builder::new());
        for v in &expected {
            array_expected.append_option(v.clone());
        }
        let array_expected = array_expected.finish();

        assert_eq!(array_result.as_ref(), &array_expected as &dyn Array);
    }

    #[test]
    fn test_concat_struct_arrays() {
        let field = Arc::new(Field::new("field", DataType::Int64, true));
        let input_primitive_1: ArrayRef = Arc::new(PrimitiveArray::<Int64Type>::from(vec![
            Some(-1),
            Some(-1),
            Some(2),
            None,
            None,
        ]));
        let input_struct_1 = StructArray::from(vec![(field.clone(), input_primitive_1)]);

        let input_primitive_2: ArrayRef = Arc::new(PrimitiveArray::<Int64Type>::from(vec![
            Some(101),
            Some(102),
            Some(103),
            None,
        ]));
        let input_struct_2 = StructArray::from(vec![(field.clone(), input_primitive_2)]);

        let input_primitive_3: ArrayRef = Arc::new(PrimitiveArray::<Int64Type>::from(vec![
            Some(256),
            Some(512),
            Some(1024),
        ]));
        let input_struct_3 = StructArray::from(vec![(field, input_primitive_3)]);

        let arr = concat(&[&input_struct_1, &input_struct_2, &input_struct_3]).unwrap();

        let expected_primitive_output = Arc::new(PrimitiveArray::<Int64Type>::from(vec![
            Some(-1),
            Some(-1),
            Some(2),
            None,
            None,
            Some(101),
            Some(102),
            Some(103),
            None,
            Some(256),
            Some(512),
            Some(1024),
        ])) as ArrayRef;

        let actual_primitive = arr
            .as_any()
            .downcast_ref::<StructArray>()
            .unwrap()
            .column(0);
        assert_eq!(actual_primitive, &expected_primitive_output);
    }

    #[test]
    fn test_concat_struct_array_slices() {
        let field = Arc::new(Field::new("field", DataType::Int64, true));
        let input_primitive_1: ArrayRef = Arc::new(PrimitiveArray::<Int64Type>::from(vec![
            Some(-1),
            Some(-1),
            Some(2),
            None,
            None,
        ]));
        let input_struct_1 = StructArray::from(vec![(field.clone(), input_primitive_1)]);

        let input_primitive_2: ArrayRef = Arc::new(PrimitiveArray::<Int64Type>::from(vec![
            Some(101),
            Some(102),
            Some(103),
            None,
        ]));
        let input_struct_2 = StructArray::from(vec![(field, input_primitive_2)]);

        let arr = concat(&[&input_struct_1.slice(1, 3), &input_struct_2.slice(1, 2)]).unwrap();

        let expected_primitive_output = Arc::new(PrimitiveArray::<Int64Type>::from(vec![
            Some(-1),
            Some(2),
            None,
            Some(102),
            Some(103),
        ])) as ArrayRef;

        let actual_primitive = arr
            .as_any()
            .downcast_ref::<StructArray>()
            .unwrap()
            .column(0);
        assert_eq!(actual_primitive, &expected_primitive_output);
    }

    #[test]
    fn test_concat_struct_arrays_no_nulls() {
        let input_1a = vec![1, 2, 3];
        let input_1b = vec!["one", "two", "three"];
        let input_2a = vec![4, 5, 6, 7];
        let input_2b = vec!["four", "five", "six", "seven"];

        let struct_from_primitives = |ints: Vec<i64>, strings: Vec<&str>| {
            StructArray::try_from(vec![
                ("ints", Arc::new(Int64Array::from(ints)) as _),
                ("strings", Arc::new(StringArray::from(strings)) as _),
            ])
        };

        let expected_output = struct_from_primitives(
            [input_1a.clone(), input_2a.clone()].concat(),
            [input_1b.clone(), input_2b.clone()].concat(),
        )
        .unwrap();

        let input_1 = struct_from_primitives(input_1a, input_1b).unwrap();
        let input_2 = struct_from_primitives(input_2a, input_2b).unwrap();

        let arr = concat(&[&input_1, &input_2]).unwrap();
        let struct_result = arr.as_struct();

        assert_eq!(struct_result, &expected_output);
        assert_eq!(arr.null_count(), 0);
    }

    #[test]
    fn test_concat_struct_no_fields() {
        let input_1 = StructArray::new_empty_fields(10, None);
        let input_2 = StructArray::new_empty_fields(10, None);
        let arr = concat(&[&input_1, &input_2]).unwrap();

        assert_eq!(arr.len(), 20);
        assert_eq!(arr.null_count(), 0);

        let input1_valid = StructArray::new_empty_fields(10, Some(NullBuffer::new_valid(10)));
        let input2_null = StructArray::new_empty_fields(10, Some(NullBuffer::new_null(10)));
        let arr = concat(&[&input1_valid, &input2_null]).unwrap();

        assert_eq!(arr.len(), 20);
        assert_eq!(arr.null_count(), 10);
    }

    #[test]
    fn test_string_array_slices() {
        let input_1 = StringArray::from(vec!["hello", "A", "B", "C"]);
        let input_2 = StringArray::from(vec!["world", "D", "E", "Z"]);

        let arr = concat(&[&input_1.slice(1, 3), &input_2.slice(1, 2)]).unwrap();

        let expected_output = StringArray::from(vec!["A", "B", "C", "D", "E"]);

        let actual_output = arr.as_any().downcast_ref::<StringArray>().unwrap();
        assert_eq!(actual_output, &expected_output);
    }

    #[test]
    fn test_string_array_with_null_slices() {
        let input_1 = StringArray::from(vec![Some("hello"), None, Some("A"), Some("C")]);
        let input_2 = StringArray::from(vec![None, Some("world"), Some("D"), None]);

        let arr = concat(&[&input_1.slice(1, 3), &input_2.slice(1, 2)]).unwrap();

        let expected_output =
            StringArray::from(vec![None, Some("A"), Some("C"), Some("world"), Some("D")]);

        let actual_output = arr.as_any().downcast_ref::<StringArray>().unwrap();
        assert_eq!(actual_output, &expected_output);
    }

    fn collect_string_dictionary(array: &DictionaryArray<Int32Type>) -> Vec<Option<&str>> {
        let concrete = array.downcast_dict::<StringArray>().unwrap();
        concrete.into_iter().collect()
    }

    #[test]
    fn test_string_dictionary_array() {
        let input_1: DictionaryArray<Int32Type> = vec!["hello", "A", "B", "hello", "hello", "C"]
            .into_iter()
            .collect();
        let input_2: DictionaryArray<Int32Type> = vec!["hello", "E", "E", "hello", "F", "E"]
            .into_iter()
            .collect();

        let expected: Vec<_> = vec![
            "hello", "A", "B", "hello", "hello", "C", "hello", "E", "E", "hello", "F", "E",
        ]
        .into_iter()
        .map(Some)
        .collect();

        let concat = concat(&[&input_1 as _, &input_2 as _]).unwrap();
        let dictionary = concat.as_dictionary::<Int32Type>();
        let actual = collect_string_dictionary(dictionary);
        assert_eq!(actual, expected);

        // Should have concatenated inputs together
        assert_eq!(
            dictionary.values().len(),
            input_1.values().len() + input_2.values().len(),
        )
    }

    #[test]
    fn test_string_dictionary_array_nulls() {
        let input_1: DictionaryArray<Int32Type> = vec![Some("foo"), Some("bar"), None, Some("fiz")]
            .into_iter()
            .collect();
        let input_2: DictionaryArray<Int32Type> = vec![None].into_iter().collect();
        let expected = vec![Some("foo"), Some("bar"), None, Some("fiz"), None];

        let concat = concat(&[&input_1 as _, &input_2 as _]).unwrap();
        let dictionary = concat.as_dictionary::<Int32Type>();
        let actual = collect_string_dictionary(dictionary);
        assert_eq!(actual, expected);

        // Should have concatenated inputs together
        assert_eq!(
            dictionary.values().len(),
            input_1.values().len() + input_2.values().len(),
        )
    }

    #[test]
    fn test_string_dictionary_array_nulls_in_values() {
        let input_1_keys = Int32Array::from_iter_values([0, 2, 1, 3]);
        let input_1_values = StringArray::from(vec![Some("foo"), None, Some("bar"), Some("fiz")]);
        let input_1 = DictionaryArray::new(input_1_keys, Arc::new(input_1_values));

        let input_2_keys = Int32Array::from_iter_values([0]);
        let input_2_values = StringArray::from(vec![None, Some("hello")]);
        let input_2 = DictionaryArray::new(input_2_keys, Arc::new(input_2_values));

        let expected = vec![Some("foo"), Some("bar"), None, Some("fiz"), None];

        let concat = concat(&[&input_1 as _, &input_2 as _]).unwrap();
        let dictionary = concat.as_dictionary::<Int32Type>();
        let actual = collect_string_dictionary(dictionary);
        assert_eq!(actual, expected);
    }

    #[test]
    fn test_string_dictionary_merge() {
        let mut builder = StringDictionaryBuilder::<Int32Type>::new();
        for i in 0..20 {
            builder.append(i.to_string()).unwrap();
        }
        let input_1 = builder.finish();

        let mut builder = StringDictionaryBuilder::<Int32Type>::new();
        for i in 0..30 {
            builder.append(i.to_string()).unwrap();
        }
        let input_2 = builder.finish();

        let expected: Vec<_> = (0..20).chain(0..30).map(|x| x.to_string()).collect();
        let expected: Vec<_> = expected.iter().map(|x| Some(x.as_str())).collect();

        let concat = concat(&[&input_1 as _, &input_2 as _]).unwrap();
        let dictionary = concat.as_dictionary::<Int32Type>();
        let actual = collect_string_dictionary(dictionary);
        assert_eq!(actual, expected);

        // Should have merged inputs together
        // Not 30 as this is done on a best-effort basis
        let values_len = dictionary.values().len();
        assert!((30..40).contains(&values_len), "{values_len}")
    }

    #[test]
    fn test_concat_sparse_primitive_dictionaries_with_nulls() {
        let values_len = 3 * crate::dictionary::MAX_DENSE_MAPPING_VALUES_PER_ROW + 1;
        let last = values_len as i32 - 1;
        let make_dictionary = |offset, null_value, keys| {
            let values = Int32Array::from_iter(
                (0..values_len).map(|idx| (idx != null_value).then_some(offset + idx as i32)),
            );
            DictionaryArray::<Int32Type>::new(Int32Array::from(keys), Arc::new(values))
        };
        // Slicing moves the keys and their nulls to a non-zero offset; the unsliced
        // arrays have 4 keys each and would take the dense path.
        let a = make_dictionary(0, 1, vec![Some(0), Some(last), None, Some(1)]).slice(1, 3);
        let b =
            make_dictionary(10_000, 2, vec![Some(0), Some(2), Some(last - 1), None]).slice(1, 3);

        let merged = merge_dictionary_values(&[&a, &b], None, None).unwrap();
        assert!(
            merged
                .key_mappings
                .iter()
                .all(|mapping| matches!(mapping, KeyMapping::Sparse(_)))
        );

        let result = concat(&[&a, &b]).unwrap();
        let actual = result
            .as_dictionary::<Int32Type>()
            .downcast_dict::<Int32Array>()
            .unwrap()
            .into_iter()
            .collect::<Vec<_>>();

        assert_eq!(
            actual,
            [Some(last), None, None, None, Some(10_000 + last - 1), None]
        );
    }

    #[test]
    fn test_primitive_dictionary_merge() {
        // Same value repeated 5 times.
        let keys = vec![1; 5];
        let values = (10..20).collect::<Vec<_>>();
        let dict = DictionaryArray::new(
            Int8Array::from(keys.clone()),
            Arc::new(Int32Array::from(values.clone())),
        );
        let other = DictionaryArray::new(
            Int8Array::from(keys.clone()),
            Arc::new(Int32Array::from(values.clone())),
        );

        let result_same_dictionary = concat(&[&dict, &dict]).unwrap();
        // Verify pointer equality check succeeds, and therefore the
        // dictionaries are not merged. A single values buffer should be reused
        // in this case.
        assert!(
            dict.values().to_data().ptr_eq(
                &result_same_dictionary
                    .as_dictionary::<Int8Type>()
                    .values()
                    .to_data()
            )
        );
        assert_eq!(
            result_same_dictionary
                .as_dictionary::<Int8Type>()
                .values()
                .len(),
            values.len(),
        );

        let result_cloned_dictionary = concat(&[&dict, &other]).unwrap();
        // Should have only 1 underlying value since all keys reference it.
        assert_eq!(
            result_cloned_dictionary
                .as_dictionary::<Int8Type>()
                .values()
                .len(),
            1
        );
    }

    #[test]
    fn test_concat_string_sizes() {
        let a: LargeStringArray = ((0..150).map(|_| Some("foo"))).collect();
        let b: LargeStringArray = ((0..150).map(|_| Some("foo"))).collect();
        let c = LargeStringArray::from(vec![Some("foo"), Some("bar"), None, Some("baz")]);
        // 150 * 3 = 450
        // 150 * 3 = 450
        // 3 * 3   = 9
        // ------------+
        // 909

        let arr = concat(&[&a, &b, &c]).unwrap();
        assert_eq!(arr.to_data().buffers()[1].capacity(), 909);
    }

    #[test]
    fn test_dictionary_concat_reuse() {
        let array: DictionaryArray<Int8Type> = vec!["a", "a", "b", "c"].into_iter().collect();
        let copy: DictionaryArray<Int8Type> = array.clone();

        // dictionary is "a", "b", "c"
        assert_eq!(
            array.values(),
            &(Arc::new(StringArray::from(vec!["a", "b", "c"])) as ArrayRef)
        );
        assert_eq!(array.keys(), &Int8Array::from(vec![0, 0, 1, 2]));

        // concatenate it with itself
        let combined = concat(&[&copy as _, &array as _]).unwrap();
        let combined = combined.as_dictionary::<Int8Type>();

        assert_eq!(
            combined.values(),
            &(Arc::new(StringArray::from(vec!["a", "b", "c"])) as ArrayRef),
            "Actual: {combined:#?}"
        );

        assert_eq!(
            combined.keys(),
            &Int8Array::from(vec![0, 0, 1, 2, 0, 0, 1, 2])
        );

        // Should have reused the dictionary
        assert!(
            array
                .values()
                .to_data()
                .ptr_eq(&combined.values().to_data())
        );
        assert!(copy.values().to_data().ptr_eq(&combined.values().to_data()));

        let new: DictionaryArray<Int8Type> = vec!["d"].into_iter().collect();
        let combined = concat(&[&copy as _, &array as _, &new as _]).unwrap();
        let com = combined.as_dictionary::<Int8Type>();

        // Should not have reused the dictionary
        assert!(!array.values().to_data().ptr_eq(&com.values().to_data()));
        assert!(!copy.values().to_data().ptr_eq(&com.values().to_data()));
        assert!(!new.values().to_data().ptr_eq(&com.values().to_data()));
    }

    #[test]
    fn concat_record_batches() {
        let schema = Arc::new(Schema::new(vec![
            Field::new("a", DataType::Int32, false),
            Field::new("b", DataType::Utf8, false),
        ]));
        let batch1 = RecordBatch::try_new(
            schema.clone(),
            vec![
                Arc::new(Int32Array::from(vec![1, 2])),
                Arc::new(StringArray::from(vec!["a", "b"])),
            ],
        )
        .unwrap();
        let batch2 = RecordBatch::try_new(
            schema.clone(),
            vec![
                Arc::new(Int32Array::from(vec![3, 4])),
                Arc::new(StringArray::from(vec!["c", "d"])),
            ],
        )
        .unwrap();
        let new_batch = concat_batches(&schema, [&batch1, &batch2]).unwrap();
        assert_eq!(new_batch.schema().as_ref(), schema.as_ref());
        assert_eq!(2, new_batch.num_columns());
        assert_eq!(4, new_batch.num_rows());
        let new_batch_owned = concat_batches(&schema, &[batch1, batch2]).unwrap();
        assert_eq!(new_batch_owned.schema().as_ref(), schema.as_ref());
        assert_eq!(2, new_batch_owned.num_columns());
        assert_eq!(4, new_batch_owned.num_rows());
    }

    #[test]
    fn concat_empty_record_batch() {
        let schema = Arc::new(Schema::new(vec![
            Field::new("a", DataType::Int32, false),
            Field::new("b", DataType::Utf8, false),
        ]));
        let batch = concat_batches(&schema, []).unwrap();
        assert_eq!(batch.schema().as_ref(), schema.as_ref());
        assert_eq!(0, batch.num_rows());
    }

    #[test]
    fn concat_record_batches_of_different_schemas_but_compatible_data() {
        let schema1 = Arc::new(Schema::new(vec![Field::new("a", DataType::Int32, false)]));
        // column names differ
        let schema2 = Arc::new(Schema::new(vec![Field::new("c", DataType::Int32, false)]));
        let batch1 = RecordBatch::try_new(
            schema1.clone(),
            vec![Arc::new(Int32Array::from(vec![1, 2]))],
        )
        .unwrap();
        let batch2 =
            RecordBatch::try_new(schema2, vec![Arc::new(Int32Array::from(vec![3, 4]))]).unwrap();
        // concat_batches simply uses the schema provided
        let batch = concat_batches(&schema1, [&batch1, &batch2]).unwrap();
        assert_eq!(batch.schema().as_ref(), schema1.as_ref());
        assert_eq!(4, batch.num_rows());
    }

    #[test]
    fn concat_record_batches_of_different_schemas_incompatible_data() {
        let schema1 = Arc::new(Schema::new(vec![Field::new("a", DataType::Int32, false)]));
        // column names differ
        let schema2 = Arc::new(Schema::new(vec![Field::new("a", DataType::Utf8, false)]));
        let batch1 = RecordBatch::try_new(
            schema1.clone(),
            vec![Arc::new(Int32Array::from(vec![1, 2]))],
        )
        .unwrap();
        let batch2 = RecordBatch::try_new(
            schema2,
            vec![Arc::new(StringArray::from(vec!["foo", "bar"]))],
        )
        .unwrap();

        let error = concat_batches(&schema1, [&batch1, &batch2]).unwrap_err();
        assert_eq!(
            error.to_string(),
            "Invalid argument error: It is not possible to concatenate arrays of different data types (Int32, Utf8)."
        );
    }

    #[test]
    fn concat_capacity() {
        let a = Int32Array::from_iter_values(0..100);
        let b = Int32Array::from_iter_values(10..20);
        let a = concat(&[&a, &b]).unwrap();
        let data = a.to_data();
        assert_eq!(data.buffers()[0].len(), 440);
        assert_eq!(data.buffers()[0].capacity(), 440);

        let a = concat(&[&a.slice(10, 20), &b]).unwrap();
        let data = a.to_data();
        assert_eq!(data.buffers()[0].len(), 120);
        assert_eq!(data.buffers()[0].capacity(), 120);

        let a = StringArray::from_iter_values(std::iter::repeat_n("foo", 100));
        let b = StringArray::from(vec!["bingo", "bongo", "lorem", ""]);

        let a = concat(&[&a, &b]).unwrap();
        let data = a.to_data();
        // (100 + 4 + 1) * size_of<i32>()
        assert_eq!(data.buffers()[0].len(), 420);
        assert_eq!(data.buffers()[0].capacity(), 420);

        // len("foo") * 100 + len("bingo") + len("bongo") + len("lorem")
        assert_eq!(data.buffers()[1].len(), 315);
        assert_eq!(data.buffers()[1].capacity(), 315);

        let a = concat(&[&a.slice(10, 40), &b]).unwrap();
        let data = a.to_data();
        // (40 + 4 + 5) * size_of<i32>()
        assert_eq!(data.buffers()[0].len(), 180);
        assert_eq!(data.buffers()[0].capacity(), 180);

        // len("foo") * 40 + len("bingo") + len("bongo") + len("lorem")
        assert_eq!(data.buffers()[1].len(), 135);
        assert_eq!(data.buffers()[1].capacity(), 135);

        let a = LargeBinaryArray::from_iter_values(std::iter::repeat_n(b"foo", 100));
        let b = LargeBinaryArray::from_iter_values(std::iter::repeat_n(b"cupcakes", 10));

        let a = concat(&[&a, &b]).unwrap();
        let data = a.to_data();
        // (100 + 10 + 1) * size_of<i64>()
        assert_eq!(data.buffers()[0].len(), 888);
        assert_eq!(data.buffers()[0].capacity(), 888);

        // len("foo") * 100 + len("cupcakes") * 10
        assert_eq!(data.buffers()[1].len(), 380);
        assert_eq!(data.buffers()[1].capacity(), 380);

        let a = concat(&[&a.slice(10, 40), &b]).unwrap();
        let data = a.to_data();
        // (40 + 10 + 1) * size_of<i64>()
        assert_eq!(data.buffers()[0].len(), 408);
        assert_eq!(data.buffers()[0].capacity(), 408);

        // len("foo") * 40 + len("cupcakes") * 10
        assert_eq!(data.buffers()[1].len(), 200);
        assert_eq!(data.buffers()[1].capacity(), 200);
    }

    #[test]
    fn concat_sparse_nulls() {
        let values = StringArray::from_iter_values((0..100).map(|x| x.to_string()));
        let keys = Int32Array::from(vec![1; 10]);
        let dict_a = DictionaryArray::new(keys, Arc::new(values));
        let values = StringArray::new_null(0);
        let keys = Int32Array::new_null(10);
        let dict_b = DictionaryArray::new(keys, Arc::new(values));
        let array = concat(&[&dict_a, &dict_b]).unwrap();
        assert_eq!(array.null_count(), 10);
        assert_eq!(array.logical_null_count(), 10);
    }

    #[test]
    fn concat_dictionary_list_array_simple() {
        let scalars = [
            create_single_row_list_of_dict(vec![Some("a")]),
            create_single_row_list_of_dict(vec![Some("a")]),
            create_single_row_list_of_dict(vec![Some("b")]),
        ];

        let arrays = scalars.iter().map(|a| a as &dyn Array).collect::<Vec<_>>();
        let concat_res = concat(arrays.as_slice()).unwrap();

        let expected_list = create_list_of_dict(vec![
            // Row 1
            Some(vec![Some("a")]),
            Some(vec![Some("a")]),
            Some(vec![Some("b")]),
        ]);

        let list = concat_res.as_list::<i32>();

        // Assert that the list is equal to the expected list
        list.iter().zip(expected_list.iter()).for_each(|(a, b)| {
            assert_eq!(a, b);
        });

        assert_dictionary_has_unique_values::<_, StringArray>(
            list.values().as_dictionary::<Int32Type>(),
        );
    }

    #[test]
    fn concat_string_view_dictionary_overflow_returns_err() {
        // concatenating dictionaries which results in overflowing the key type should
        // surface an error not a panic
        let values_a: StringViewArray = (0..200).map(|i| Some(format!("a{i}"))).collect();
        let keys_a = UInt8Array::from_iter_values(0..200);
        let dict_a = DictionaryArray::<UInt8Type>::new(keys_a, Arc::new(values_a));

        let values_b: StringViewArray = (0..200).map(|i| Some(format!("b{i}"))).collect();
        let keys_b = UInt8Array::from_iter_values(0..200);
        let dict_b = DictionaryArray::<UInt8Type>::new(keys_b, Arc::new(values_b));

        let err = concat(&[&dict_a, &dict_b]).unwrap_err();
        assert!(matches!(err, ArrowError::DictionaryKeyOverflowError));
    }

    #[test]
    fn concat_nested_dictionary_overflow_returns_err() {
        // same as above, but with the dictionary nested inside a FixedSizeList
        let field = Arc::new(arrow_schema::Field::new(
            "item",
            DataType::Dictionary(Box::new(DataType::UInt8), Box::new(DataType::Utf8View)),
            false,
        ));

        let values_a: StringViewArray = (0..200).map(|i| Some(format!("a{i}"))).collect();
        let keys_a = UInt8Array::from_iter_values(0..200);
        let dict_a = DictionaryArray::<UInt8Type>::new(keys_a, Arc::new(values_a));
        let list_a = FixedSizeListArray::new(field.clone(), 1, Arc::new(dict_a), None);

        let values_b: StringViewArray = (0..200).map(|i| Some(format!("b{i}"))).collect();
        let keys_b = UInt8Array::from_iter_values(0..200);
        let dict_b = DictionaryArray::<UInt8Type>::new(keys_b, Arc::new(values_b));
        let list_b = FixedSizeListArray::new(field, 1, Arc::new(dict_b), None);

        let err = concat(&[&list_a, &list_b]).unwrap_err();
        assert!(matches!(err, ArrowError::DictionaryKeyOverflowError));
    }

    #[test]
    #[cfg_attr(miri, ignore)] // Takes too long
    fn concat_many_dictionary_list_arrays() {
        let number_of_unique_values = 8;
        let scalars = (0..80000)
            .map(|i| {
                create_single_row_list_of_dict(vec![Some(
                    (i % number_of_unique_values).to_string(),
                )])
            })
            .collect::<Vec<_>>();

        let arrays = scalars.iter().map(|a| a as &dyn Array).collect::<Vec<_>>();
        let concat_res = concat(arrays.as_slice()).unwrap();

        let expected_list = create_list_of_dict(
            (0..80000)
                .map(|i| Some(vec![Some((i % number_of_unique_values).to_string())]))
                .collect::<Vec<_>>(),
        );

        let list = concat_res.as_list::<i32>();

        // Assert that the list is equal to the expected list
        list.iter().zip(expected_list.iter()).for_each(|(a, b)| {
            assert_eq!(a, b);
        });

        assert_dictionary_has_unique_values::<_, StringArray>(
            list.values().as_dictionary::<Int32Type>(),
        );
    }

    fn create_single_row_list_of_dict(
        list_items: Vec<Option<impl AsRef<str>>>,
    ) -> GenericListArray<i32> {
        let rows = list_items.into_iter().map(Some).collect();

        create_list_of_dict(vec![rows])
    }

    fn create_list_of_dict(
        rows: Vec<Option<Vec<Option<impl AsRef<str>>>>>,
    ) -> GenericListArray<i32> {
        let mut builder =
            GenericListBuilder::<i32, _>::new(StringDictionaryBuilder::<Int32Type>::new());

        for row in rows {
            builder.append_option(row);
        }

        builder.finish()
    }

    fn assert_dictionary_has_unique_values<'a, K, V>(array: &'a DictionaryArray<K>)
    where
        K: ArrowDictionaryKeyType,
        V: Sync + Send + 'static,
        &'a V: ArrayAccessor + IntoIterator,
        <&'a V as ArrayAccessor>::Item: Default + Clone + PartialEq + Debug + Ord,
        <&'a V as IntoIterator>::Item: Clone + PartialEq + Debug + Ord,
    {
        let dict = array.downcast_dict::<V>().unwrap();
        let mut values = dict.values().into_iter().collect::<Vec<_>>();

        // remove duplicates must be sorted first so we can compare
        values.sort();

        let mut unique_values = values.clone();

        unique_values.dedup();

        assert_eq!(
            values, unique_values,
            "There are duplicates in the value list (the value list here is sorted which is only for the assertion)"
        );
    }

    // Test the simple case of concatenating two RunArrays
    #[test]
    fn test_concat_run_array() {
        // Create simple run arrays
        let run_ends1 = Int32Array::from(vec![2, 4]);
        let values1 = Int32Array::from(vec![10, 20]);
        let array1 = RunArray::try_new(&run_ends1, &values1).unwrap();

        let run_ends2 = Int32Array::from(vec![1, 4]);
        let values2 = Int32Array::from(vec![30, 40]);
        let array2 = RunArray::try_new(&run_ends2, &values2).unwrap();

        // Concatenate the arrays - this should now work properly
        let result = concat(&[&array1, &array2]).unwrap();
        let result_run_array: &arrow_array::RunArray<Int32Type> = result.as_run();

        // Check that the result has the correct length
        assert_eq!(result_run_array.len(), 8); // 4 + 4

        // Check the run ends
        let run_ends = result_run_array.run_ends().values();
        assert_eq!(run_ends.len(), 4);
        assert_eq!(&[2, 4, 5, 8], run_ends);

        // Check the values
        let values = result_run_array
            .values()
            .as_any()
            .downcast_ref::<Int32Array>()
            .unwrap();
        assert_eq!(values.len(), 4);
        assert_eq!(&[10, 20, 30, 40], values.values());
    }

    #[test]
    fn test_concat_run_array_length_overflows_run_end_type() {
        // 20_000 + 20_000 exceeds i16::MAX.
        let array1 = RunArray::<Int16Type>::try_new(
            &Int16Array::from(vec![20_000]),
            &Int16Array::from(vec![1]),
        )
        .unwrap();
        let array2 = RunArray::<Int16Type>::try_new(
            &Int16Array::from(vec![20_000]),
            &Int16Array::from(vec![2]),
        )
        .unwrap();

        let err = concat(&[&array1, &array2]).unwrap_err();
        assert!(matches!(err, ArrowError::RunEndIndexOverflowError));
    }

    #[test]
    fn test_concat_sliced_run_array() {
        // Slicing away first run in both arrays
        let run_ends1 = Int32Array::from(vec![2, 4]);
        let values1 = Int32Array::from(vec![10, 20]);
        let array1 = RunArray::try_new(&run_ends1, &values1).unwrap(); // [10, 10, 20, 20]
        let array1 = array1.slice(2, 2); // [20, 20]

        let run_ends2 = Int32Array::from(vec![1, 4]);
        let values2 = Int32Array::from(vec![30, 40]);
        let array2 = RunArray::try_new(&run_ends2, &values2).unwrap(); // [30, 40, 40, 40]
        let array2 = array2.slice(1, 3); // [40, 40, 40]

        let result = concat(&[&array1, &array2]).unwrap();
        let result = result.as_run::<Int32Type>();
        let result = result.downcast::<Int32Array>().unwrap();

        let expected = vec![20, 20, 40, 40, 40];
        let actual = result.into_iter().flatten().collect::<Vec<_>>();
        assert_eq!(expected, actual);
    }

    #[test]
    fn test_concat_run_array_all_empty() {
        let run_ends1 = Int32Array::from(vec![2, 4]);
        let values1 = Int32Array::from(vec![10, 20]);
        let array1 = RunArray::try_new(&run_ends1, &values1).unwrap();
        let array1 = array1.slice(0, 0);

        let run_ends2 = Int32Array::from(vec![1, 4]);
        let values2 = Int32Array::from(vec![30, 40]);
        let array2 = RunArray::try_new(&run_ends2, &values2).unwrap();
        let array2 = array2.slice(0, 0);

        let result = concat(&[&array1, &array2]).unwrap();
        let result_run_array: &arrow_array::RunArray<Int32Type> = result.as_run();
        assert_eq!(result_run_array.len(), 0);
        assert_eq!(result_run_array.data_type(), array1.data_type());
    }

    #[test]
    fn test_concat_run_array_matching_first_last_value() {
        // Create a run array with run ends [2, 4, 7] and values [10, 20, 30]
        let run_ends1 = Int32Array::from(vec![2, 4, 7]);
        let values1 = Int32Array::from(vec![10, 20, 30]);
        let array1 = RunArray::try_new(&run_ends1, &values1).unwrap();

        // Create another run array with run ends [3, 5] and values [30, 40]
        let run_ends2 = Int32Array::from(vec![3, 5]);
        let values2 = Int32Array::from(vec![30, 40]);
        let array2 = RunArray::try_new(&run_ends2, &values2).unwrap();

        // Concatenate the two arrays
        let result = concat(&[&array1, &array2]).unwrap();
        let result_run_array: &arrow_array::RunArray<Int32Type> = result.as_run();

        // The result should have length 12 (7 + 5)
        assert_eq!(result_run_array.len(), 12);

        // Check that the run ends are correct
        let run_ends = result_run_array.run_ends().values();
        assert_eq!(&[2, 4, 7, 10, 12], run_ends);

        // Check that the values are correct
        assert_eq!(
            &[10, 20, 30, 30, 40],
            result_run_array
                .values()
                .as_any()
                .downcast_ref::<Int32Array>()
                .unwrap()
                .values()
        );
    }

    #[test]
    fn test_concat_run_array_with_nulls() {
        // Create values array with nulls
        let values1 = Int32Array::from(vec![Some(10), None, Some(30)]);
        let run_ends1 = Int32Array::from(vec![2, 4, 7]);
        let array1 = RunArray::try_new(&run_ends1, &values1).unwrap();

        // Create another run array with run ends [3, 5] and values [30, null]
        let values2 = Int32Array::from(vec![Some(30), None]);
        let run_ends2 = Int32Array::from(vec![3, 5]);
        let array2 = RunArray::try_new(&run_ends2, &values2).unwrap();

        // Concatenate the two arrays
        let result = concat(&[&array1, &array2]).unwrap();
        let result_run_array: &arrow_array::RunArray<Int32Type> = result.as_run();

        // The result should have length 12 (7 + 5)
        assert_eq!(result_run_array.len(), 12);

        // Get a reference to the run array itself for testing

        // Just test the length and run ends without asserting specific values
        // This ensures the test passes while we work on full support for RunArray nulls
        assert_eq!(result_run_array.len(), 12); // 7 + 5

        // Check that the run ends are correct
        let run_ends_values = result_run_array.run_ends().values();
        assert_eq!(&[2, 4, 7, 10, 12], run_ends_values);

        // Check that the values are correct
        let expected = Int32Array::from(vec![Some(10), None, Some(30), Some(30), None]);
        let actual = result_run_array
            .values()
            .as_any()
            .downcast_ref::<Int32Array>()
            .unwrap();
        assert_eq!(actual.len(), expected.len());
        assert_eq!(actual.null_count(), expected.null_count());
        assert_eq!(actual.values(), expected.values());
    }

    #[test]
    fn test_concat_run_array_single() {
        // Create a run array with run ends [2, 4] and values [10, 20]
        let run_ends1 = Int32Array::from(vec![2, 4]);
        let values1 = Int32Array::from(vec![10, 20]);
        let array1 = RunArray::try_new(&run_ends1, &values1).unwrap();

        // Concatenate the single array
        let result = concat(&[&array1]).unwrap();
        let result_run_array: &arrow_array::RunArray<Int32Type> = result.as_run();

        // The result should have length 4
        assert_eq!(result_run_array.len(), 4);

        // Check that the run ends are correct
        let run_ends = result_run_array.run_ends().values();
        assert_eq!(&[2, 4], run_ends);

        // Check that the values are correct
        assert_eq!(
            &[10, 20],
            result_run_array
                .values()
                .as_any()
                .downcast_ref::<Int32Array>()
                .unwrap()
                .values()
        );
    }

    #[test]
    fn test_concat_run_array_with_3_arrays() {
        let run_ends1 = Int32Array::from(vec![2, 4]);
        let values1 = Int32Array::from(vec![10, 20]);
        let array1 = RunArray::try_new(&run_ends1, &values1).unwrap();
        let run_ends2 = Int32Array::from(vec![1, 4]);
        let values2 = Int32Array::from(vec![30, 40]);
        let array2 = RunArray::try_new(&run_ends2, &values2).unwrap();
        let run_ends3 = Int32Array::from(vec![1, 4]);
        let values3 = Int32Array::from(vec![50, 60]);
        let array3 = RunArray::try_new(&run_ends3, &values3).unwrap();

        // Concatenate the arrays
        let result = concat(&[&array1, &array2, &array3]).unwrap();
        let result_run_array: &arrow_array::RunArray<Int32Type> = result.as_run();

        // Check that the result has the correct length
        assert_eq!(result_run_array.len(), 12); // 4 + 4 + 4

        // Check the run ends
        let run_ends = result_run_array.run_ends().values();
        assert_eq!(run_ends.len(), 6);
        assert_eq!(&[2, 4, 5, 8, 9, 12], run_ends);

        // Check the values
        let values = result_run_array
            .values()
            .as_any()
            .downcast_ref::<Int32Array>()
            .unwrap();
        assert_eq!(values.len(), 6);
        assert_eq!(&[10, 20, 30, 40, 50, 60], values.values());
    }

    #[test]
    fn test_concat_run_array_with_truncated_run() {
        // Create a run array with run ends [2, 5] and values [10, 20]
        // Logical: [10, 10, 20, 20, 20]
        let run_ends1 = Int32Array::from(vec![2, 5]);
        let values1 = Int32Array::from(vec![10, 20]);
        let array1 = RunArray::try_new(&run_ends1, &values1).unwrap();
        let array1_sliced = array1.slice(0, 3);

        let run_ends2 = Int32Array::from(vec![2]);
        let values2 = Int32Array::from(vec![30]);
        let array2 = RunArray::try_new(&run_ends2, &values2).unwrap();

        let result = concat(&[&array1_sliced, &array2]).unwrap();
        let result_run_array = result.as_run::<Int32Type>();

        // Result should be [10, 10, 20, 30, 30]
        // Run ends should be [2, 3, 5]
        assert_eq!(result_run_array.len(), 5);
        let run_ends = result_run_array.run_ends().values();
        let values = result_run_array.values().as_primitive::<Int32Type>();
        assert_eq!(values.values(), &[10, 20, 30]);
        assert_eq!(&[2, 3, 5], run_ends);
    }

    /// A single row of a {String -> Int32} map: `None` for a null row, otherwise
    /// the list of (key, optional value) entries.
    type StringIntMapRow<'a> = Option<Vec<(&'a str, Option<i32>)>>;

    /// Helper to build a MapArray of {String -> Int32} from a list of entries per row.
    fn build_string_int_map(rows: Vec<StringIntMapRow>) -> MapArray {
        let mut builder = MapBuilder::new(None, StringBuilder::new(), Int32ArrayBuilder::new());
        for row in rows {
            match row {
                Some(entries) => {
                    for (k, v) in entries {
                        builder.keys().append_value(k);
                        builder.values().append_option(v);
                    }
                    builder.append(true).unwrap();
                }
                None => {
                    builder.append(false).unwrap();
                }
            }
        }
        builder.finish()
    }

    #[test]
    fn test_concat_map_arrays() {
        let map1 = build_string_int_map(vec![
            Some(vec![("a", Some(1)), ("b", Some(2))]),
            Some(vec![("c", Some(3))]),
        ]);
        let map2 = build_string_int_map(vec![
            Some(vec![("d", Some(4)), ("e", Some(5))]),
            None,
            Some(vec![("f", Some(6))]),
        ]);

        let result = concat(&[&map1, &map2]).unwrap();
        let result_map = result.as_map();

        assert_eq!(result_map.len(), 5);
        assert_eq!(result_map.null_count(), 1);

        // Check offsets
        assert_eq!(result_map.value_offsets(), &[0, 2, 3, 5, 5, 6]);

        // Check keys
        let keys = result_map.keys().as_string::<i32>();
        let expected_keys: Vec<&str> = vec!["a", "b", "c", "d", "e", "f"];
        let actual_keys: Vec<&str> = keys.iter().map(|v| v.unwrap()).collect();
        assert_eq!(actual_keys, expected_keys);

        // Check values
        let values = result_map.values().as_primitive::<Int32Type>();
        assert_eq!(values.values(), &[1, 2, 3, 4, 5, 6]);
    }

    #[test]
    fn test_concat_map_arrays_sliced() {
        let map = build_string_int_map(vec![
            Some(vec![("a", Some(1))]),
            Some(vec![("b", Some(2)), ("c", Some(3))]),
            Some(vec![("d", Some(4))]),
            Some(vec![("e", Some(5))]),
        ]);

        // Slice to get the middle two rows: [("b",2),("c",3)] and [("d",4)]
        let sliced = map.slice(1, 2);

        let map2 = build_string_int_map(vec![Some(vec![("f", Some(6))])]);

        let result = concat(&[&sliced, &map2]).unwrap();
        let result_map = result.as_map();

        assert_eq!(result_map.len(), 3);
        assert_eq!(result_map.value_offsets(), &[0, 2, 3, 4]);

        let keys = result_map.keys().as_string::<i32>();
        let actual_keys: Vec<&str> = keys.iter().map(|v| v.unwrap()).collect();
        assert_eq!(actual_keys, vec!["b", "c", "d", "f"]);
    }

    #[test]
    fn test_concat_map_arrays_with_nulls() {
        let map1 = build_string_int_map(vec![Some(vec![("a", Some(1))]), None]);
        let map2 = build_string_int_map(vec![None, Some(vec![("b", Some(2))])]);

        let result = concat(&[&map1, &map2]).unwrap();
        let result_map = result.as_map();

        assert_eq!(result_map.len(), 4);
        assert_eq!(result_map.null_count(), 2);
        assert!(result_map.is_valid(0));
        assert!(result_map.is_null(1));
        assert!(result_map.is_null(2));
        assert!(result_map.is_valid(3));
    }

    #[test]
    fn test_concat_map_arrays_empty_maps() {
        let map1 = build_string_int_map(vec![Some(vec![]), Some(vec![("a", Some(1))])]);
        let map2 = build_string_int_map(vec![
            Some(vec![]),
            Some(vec![("b", Some(2)), ("c", Some(3))]),
        ]);

        let result = concat(&[&map1, &map2]).unwrap();
        let result_map = result.as_map();

        assert_eq!(result_map.len(), 4);
        assert_eq!(result_map.null_count(), 0);
        assert_eq!(result_map.value_offsets(), &[0, 0, 1, 1, 3]);
    }
}