arrow_array/

iterator.rs

// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.

//! Idiomatic iterators for [`Array`](crate::Array)

use crate::array::{
    ArrayAccessor, BooleanArray, FixedSizeBinaryArray, GenericBinaryArray, GenericListArray,
    GenericStringArray, PrimitiveArray,
};
use crate::{FixedSizeListArray, GenericListViewArray, MapArray};
use arrow_buffer::NullBuffer;

/// An iterator that returns Some(T) or None, that can be used on any [`ArrayAccessor`]
///
/// # Performance
///
/// [`ArrayIter`] provides an idiomatic way to iterate over an array, however, this
/// comes at the cost of performance. In particular the interleaved handling of
/// the null mask is often sub-optimal.
///
/// If performing an infallible operation, it is typically faster to perform the operation
/// on every index of the array, and handle the null mask separately. For [`PrimitiveArray`]
/// this functionality is provided by [`compute::unary`]
///
/// If performing a fallible operation, it isn't possible to perform the operation independently
/// of the null mask, as this might result in a spurious failure on a null index. However,
/// there are more efficient ways to iterate over just the non-null indices, this functionality
/// is provided by [`compute::try_unary`]
///
/// [`PrimitiveArray`]: crate::PrimitiveArray
/// [`compute::unary`]: https://docs.rs/arrow/latest/arrow/compute/fn.unary.html
/// [`compute::try_unary`]: https://docs.rs/arrow/latest/arrow/compute/fn.try_unary.html
#[derive(Debug, Clone)]
pub struct ArrayIter<T: ArrayAccessor> {
    array: T,
    logical_nulls: Option<NullBuffer>,
    current: usize,
    current_end: usize,
}

impl<T: ArrayAccessor> ArrayIter<T> {
    /// create a new iterator
    pub fn new(array: T) -> Self {
        let len = array.len();
        let logical_nulls = array.logical_nulls().filter(|x| x.null_count() > 0);
        ArrayIter {
            array,
            logical_nulls,
            current: 0,
            current_end: len,
        }
    }

    #[inline]
    fn is_null(&self, idx: usize) -> bool {
        self.logical_nulls
            .as_ref()
            .map(|x| x.is_null(idx))
            .unwrap_or_default()
    }
}

impl<T: ArrayAccessor> Iterator for ArrayIter<T> {
    type Item = Option<T::Item>;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.current == self.current_end {
            None
        } else if self.is_null(self.current) {
            self.current += 1;
            Some(None)
        } else {
            let old = self.current;
            self.current += 1;
            // Safety:
            // we just checked bounds in `self.current_end == self.current`
            // this is safe on the premise that this struct is initialized with
            // current = array.len()
            // and that current_end is ever only decremented
            unsafe { Some(Some(self.array.value_unchecked(old))) }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (
            self.current_end - self.current,
            Some(self.current_end - self.current),
        )
    }

    #[inline]
    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        // Check if we can advance to the desired offset
        match self.current.checked_add(n) {
            // Yes, and still within bounds
            Some(new_current) if new_current < self.current_end => {
                self.current = new_current;
            }

            // Either overflow or would exceed current_end
            _ => {
                self.current = self.current_end;
                return None;
            }
        }

        self.next()
    }

    #[inline]
    fn last(mut self) -> Option<Self::Item> {
        self.next_back()
    }

    #[inline]
    fn count(self) -> usize
    where
        Self: Sized,
    {
        self.len()
    }
}

impl<T: ArrayAccessor> DoubleEndedIterator for ArrayIter<T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.current_end == self.current {
            None
        } else {
            self.current_end -= 1;
            Some(if self.is_null(self.current_end) {
                None
            } else {
                // Safety:
                // we just checked bounds in `self.current_end == self.current`
                // this is safe on the premise that this struct is initialized with
                // current = array.len()
                // and that current_end is ever only decremented
                unsafe { Some(self.array.value_unchecked(self.current_end)) }
            })
        }
    }

    #[inline]
    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
        // Check if we advance to the one before the desired offset
        match self.current_end.checked_sub(n) {
            // Yes, and still within bounds
            Some(new_offset) if self.current < new_offset => {
                self.current_end = new_offset;
            }

            // Either underflow or would exceed current
            _ => {
                self.current = self.current_end;
                return None;
            }
        }

        self.next_back()
    }
}

/// all arrays have known size.
impl<T: ArrayAccessor> ExactSizeIterator for ArrayIter<T> {}

/// an iterator that returns Some(T) or None, that can be used on any PrimitiveArray
pub type PrimitiveIter<'a, T> = ArrayIter<&'a PrimitiveArray<T>>;
/// an iterator that returns Some(T) or None, that can be used on any BooleanArray
pub type BooleanIter<'a> = ArrayIter<&'a BooleanArray>;
/// an iterator that returns Some(T) or None, that can be used on any Utf8Array
pub type GenericStringIter<'a, T> = ArrayIter<&'a GenericStringArray<T>>;
/// an iterator that returns Some(T) or None, that can be used on any BinaryArray
pub type GenericBinaryIter<'a, T> = ArrayIter<&'a GenericBinaryArray<T>>;
/// an iterator that returns Some(T) or None, that can be used on any FixedSizeBinaryArray
pub type FixedSizeBinaryIter<'a> = ArrayIter<&'a FixedSizeBinaryArray>;
/// an iterator that returns Some(T) or None, that can be used on any FixedSizeListArray
pub type FixedSizeListIter<'a> = ArrayIter<&'a FixedSizeListArray>;
/// an iterator that returns Some(T) or None, that can be used on any ListArray
pub type GenericListArrayIter<'a, O> = ArrayIter<&'a GenericListArray<O>>;
/// an iterator that returns Some(T) or None, that can be used on any MapArray
pub type MapArrayIter<'a> = ArrayIter<&'a MapArray>;
/// an iterator that returns Some(T) or None, that can be used on any ListArray
pub type GenericListViewArrayIter<'a, O> = ArrayIter<&'a GenericListViewArray<O>>;
#[cfg(test)]
mod tests {
    use crate::array::{ArrayRef, BinaryArray, BooleanArray, Int32Array, StringArray};
    use crate::iterator::ArrayIter;
    use rand::rngs::StdRng;
    use rand::{Rng, SeedableRng};
    use std::fmt::Debug;
    use std::sync::Arc;

    #[test]
    fn test_primitive_array_iter_round_trip() {
        let array = Int32Array::from(vec![Some(0), None, Some(2), None, Some(4)]);
        let array = Arc::new(array) as ArrayRef;

        let array = array.as_any().downcast_ref::<Int32Array>().unwrap();

        // to and from iter, with a +1
        let result: Int32Array = array.iter().map(|e| e.map(|e| e + 1)).collect();

        let expected = Int32Array::from(vec![Some(1), None, Some(3), None, Some(5)]);
        assert_eq!(result, expected);

        // check if DoubleEndedIterator is implemented
        let result: Int32Array = array.iter().rev().collect();
        let rev_array = Int32Array::from(vec![Some(4), None, Some(2), None, Some(0)]);
        assert_eq!(result, rev_array);
        // check if ExactSizeIterator is implemented
        let _ = array.iter().rposition(|opt_b| opt_b == Some(1));
    }

    #[test]
    fn test_double_ended() {
        let array = Int32Array::from(vec![Some(0), None, Some(2), None, Some(4)]);
        let mut a = array.iter();
        assert_eq!(a.next(), Some(Some(0)));
        assert_eq!(a.next(), Some(None));
        assert_eq!(a.next_back(), Some(Some(4)));
        assert_eq!(a.next_back(), Some(None));
        assert_eq!(a.next_back(), Some(Some(2)));
        // the two sides have met: None is returned by both
        assert_eq!(a.next_back(), None);
        assert_eq!(a.next(), None);
    }

    #[test]
    fn test_string_array_iter_round_trip() {
        let array = StringArray::from(vec![Some("a"), None, Some("aaa"), None, Some("aaaaa")]);
        let array = Arc::new(array) as ArrayRef;

        let array = array.as_any().downcast_ref::<StringArray>().unwrap();

        // to and from iter, with a +1
        let result: StringArray = array
            .iter()
            .map(|e| {
                e.map(|e| {
                    let mut a = e.to_string();
                    a.push('b');
                    a
                })
            })
            .collect();

        let expected =
            StringArray::from(vec![Some("ab"), None, Some("aaab"), None, Some("aaaaab")]);
        assert_eq!(result, expected);

        // check if DoubleEndedIterator is implemented
        let result: StringArray = array.iter().rev().collect();
        let rev_array = StringArray::from(vec![Some("aaaaa"), None, Some("aaa"), None, Some("a")]);
        assert_eq!(result, rev_array);
        // check if ExactSizeIterator is implemented
        let _ = array.iter().rposition(|opt_b| opt_b == Some("a"));
    }

    #[test]
    fn test_binary_array_iter_round_trip() {
        let array = BinaryArray::from(vec![
            Some(b"a" as &[u8]),
            None,
            Some(b"aaa"),
            None,
            Some(b"aaaaa"),
        ]);

        // to and from iter
        let result: BinaryArray = array.iter().collect();

        assert_eq!(result, array);

        // check if DoubleEndedIterator is implemented
        let result: BinaryArray = array.iter().rev().collect();
        let rev_array = BinaryArray::from(vec![
            Some(b"aaaaa" as &[u8]),
            None,
            Some(b"aaa"),
            None,
            Some(b"a"),
        ]);
        assert_eq!(result, rev_array);

        // check if ExactSizeIterator is implemented
        let _ = array.iter().rposition(|opt_b| opt_b == Some(&[9]));
    }

    #[test]
    fn test_boolean_array_iter_round_trip() {
        let array = BooleanArray::from(vec![Some(true), None, Some(false)]);

        // to and from iter
        let result: BooleanArray = array.iter().collect();

        assert_eq!(result, array);

        // check if DoubleEndedIterator is implemented
        let result: BooleanArray = array.iter().rev().collect();
        let rev_array = BooleanArray::from(vec![Some(false), None, Some(true)]);
        assert_eq!(result, rev_array);

        // check if ExactSizeIterator is implemented
        let _ = array.iter().rposition(|opt_b| opt_b == Some(true));
    }

    trait SharedBetweenArrayIterAndSliceIter:
        ExactSizeIterator<Item = Option<i32>> + DoubleEndedIterator<Item = Option<i32>> + Clone
    {
    }
    impl<T: Clone + ExactSizeIterator<Item = Option<i32>> + DoubleEndedIterator<Item = Option<i32>>>
        SharedBetweenArrayIterAndSliceIter for T
    {
    }

    fn get_int32_iterator_cases() -> impl Iterator<Item = (Int32Array, Vec<Option<i32>>)> {
        let mut rng = StdRng::seed_from_u64(42);

        let no_nulls_and_no_duplicates = (0..10).map(Some).collect::<Vec<Option<i32>>>();
        let no_nulls_random_values = (0..10)
            .map(|_| rng.random::<i32>())
            .map(Some)
            .collect::<Vec<Option<i32>>>();

        let all_nulls = (0..10).map(|_| None).collect::<Vec<Option<i32>>>();
        let only_start_nulls = (0..10)
            .map(|item| if item < 4 { None } else { Some(item) })
            .collect::<Vec<Option<i32>>>();
        let only_end_nulls = (0..10)
            .map(|item| if item > 8 { None } else { Some(item) })
            .collect::<Vec<Option<i32>>>();
        let only_middle_nulls = (0..10)
            .map(|item| {
                if (4..=8).contains(&item) && rng.random_bool(0.9) {
                    None
                } else {
                    Some(item)
                }
            })
            .collect::<Vec<Option<i32>>>();
        let random_values_with_random_nulls = (0..10)
            .map(|_| {
                if rng.random_bool(0.3) {
                    None
                } else {
                    Some(rng.random::<i32>())
                }
            })
            .collect::<Vec<Option<i32>>>();

        let no_nulls_and_some_duplicates = (0..10)
            .map(|item| item % 3)
            .map(Some)
            .collect::<Vec<Option<i32>>>();
        let no_nulls_and_all_same_value =
            (0..10).map(|_| 9).map(Some).collect::<Vec<Option<i32>>>();
        let no_nulls_and_continues_duplicates = [0, 0, 0, 1, 1, 2, 2, 2, 2, 3]
            .map(Some)
            .into_iter()
            .collect::<Vec<Option<i32>>>();

        let single_null_and_no_duplicates = (0..10)
            .map(|item| if item == 4 { None } else { Some(item) })
            .collect::<Vec<Option<i32>>>();
        let multiple_nulls_and_no_duplicates = (0..10)
            .map(|item| if item % 3 == 2 { None } else { Some(item) })
            .collect::<Vec<Option<i32>>>();
        let continues_nulls_and_no_duplicates = [
            Some(0),
            Some(1),
            None,
            None,
            Some(2),
            Some(3),
            None,
            Some(4),
            Some(5),
            None,
        ]
        .into_iter()
        .collect::<Vec<Option<i32>>>();

        [
            no_nulls_and_no_duplicates,
            no_nulls_random_values,
            no_nulls_and_some_duplicates,
            no_nulls_and_all_same_value,
            no_nulls_and_continues_duplicates,
            all_nulls,
            only_start_nulls,
            only_end_nulls,
            only_middle_nulls,
            random_values_with_random_nulls,
            single_null_and_no_duplicates,
            multiple_nulls_and_no_duplicates,
            continues_nulls_and_no_duplicates,
        ]
        .map(|case| (Int32Array::from(case.clone()), case))
        .into_iter()
    }

    trait SetupIter {
        fn description(&self) -> String;
        fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I);
    }

    struct NoSetup;
    impl SetupIter for NoSetup {
        fn description(&self) -> String {
            "no setup".to_string()
        }
        fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, _iter: &mut I) {
            // none
        }
    }

    fn setup_and_assert_cases_on_single_operation(
        o: &impl ConsumingArrayIteratorOp,
        setup_iterator: impl SetupIter,
    ) {
        for (array, source) in get_int32_iterator_cases() {
            let mut actual = ArrayIter::new(&array);
            let mut expected = source.iter().copied();

            setup_iterator.setup(&mut actual);
            setup_iterator.setup(&mut expected);

            let current_iterator_values: Vec<Option<i32>> = expected.clone().collect();

            assert_eq!(
                o.get_value(actual),
                o.get_value(expected),
                "Failed on op {} for {} (left actual, right expected) ({current_iterator_values:?})",
                o.name(),
                setup_iterator.description(),
            );
        }
    }

    /// Trait representing an operation on a [`ArrayIter`]
    /// that can be compared against a slice iterator
    ///
    /// this is for consuming operations (e.g. `count`, `last`, etc)
    trait ConsumingArrayIteratorOp {
        /// What the operation returns (e.g. Option<i32> for last, usize for count, etc)
        type Output: PartialEq + Debug;

        /// The name of the operation, used for error messages
        fn name(&self) -> String;

        /// Get the value of the operation for the provided iterator
        /// This will be either a [`ArrayIter`] or a slice iterator to make sure they produce the same result
        ///
        /// Example implementation:
        /// 1. for `last` it will be the last value
        /// 2. for `count` it will be the returned length
        fn get_value<T: SharedBetweenArrayIterAndSliceIter>(&self, iter: T) -> Self::Output;
    }

    /// Trait representing an operation on a [`ArrayIter`]
    /// that can be compared against a slice iterator.
    ///
    /// This is for mutating operations (e.g. `position`, `any`, `find`, etc)
    trait MutatingArrayIteratorOp {
        /// What the operation returns (e.g. Option<i32> for last, usize for count, etc)
        type Output: PartialEq + Debug;

        /// The name of the operation, used for error messages
        fn name(&self) -> String;

        /// Get the value of the operation for the provided iterator
        /// This will be either a [`ArrayIter`] or a slice iterator to make sure they produce the same result
        ///
        /// Example implementation:
        /// 1. for `for_each` it will be the iterator element that the function was called with
        /// 2. for `fold` it will be the accumulator and the iterator element from each call, as well as the final result
        fn get_value<T: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut T) -> Self::Output;
    }

    /// Helper function that will assert that the provided operation
    /// produces the same result for both [`ArrayIter`] and slice iterator
    /// under various consumption patterns (e.g. some calls to next/next_back/consume_all/etc)
    fn assert_array_iterator_cases<O: ConsumingArrayIteratorOp>(o: O) {
        setup_and_assert_cases_on_single_operation(&o, NoSetup);

        struct Next;
        impl SetupIter for Next {
            fn description(&self) -> String {
                "new iter after consuming 1 element from the start".to_string()
            }
            fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
                iter.next();
            }
        }
        setup_and_assert_cases_on_single_operation(&o, Next);

        struct NextBack;
        impl SetupIter for NextBack {
            fn description(&self) -> String {
                "new iter after consuming 1 element from the end".to_string()
            }

            fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
                iter.next_back();
            }
        }

        setup_and_assert_cases_on_single_operation(&o, NextBack);

        struct NextAndBack;
        impl SetupIter for NextAndBack {
            fn description(&self) -> String {
                "new iter after consuming 1 element from start and end".to_string()
            }

            fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
                iter.next();
                iter.next_back();
            }
        }

        setup_and_assert_cases_on_single_operation(&o, NextAndBack);

        struct NextUntilLast;
        impl SetupIter for NextUntilLast {
            fn description(&self) -> String {
                "new iter after consuming all from the start but 1".to_string()
            }
            fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
                let len = iter.len();
                if len > 1 {
                    iter.nth(len - 2);
                }
            }
        }
        setup_and_assert_cases_on_single_operation(&o, NextUntilLast);

        struct NextBackUntilFirst;
        impl SetupIter for NextBackUntilFirst {
            fn description(&self) -> String {
                "new iter after consuming all from the end but 1".to_string()
            }

            fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
                let len = iter.len();
                if len > 1 {
                    iter.nth_back(len - 2);
                }
            }
        }
        setup_and_assert_cases_on_single_operation(&o, NextBackUntilFirst);

        struct NextFinish;
        impl SetupIter for NextFinish {
            fn description(&self) -> String {
                "new iter after consuming all from the start".to_string()
            }
            fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
                iter.nth(iter.len());
            }
        }
        setup_and_assert_cases_on_single_operation(&o, NextFinish);

        struct NextBackFinish;
        impl SetupIter for NextBackFinish {
            fn description(&self) -> String {
                "new iter after consuming all from the end".to_string()
            }
            fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
                iter.nth_back(iter.len());
            }
        }
        setup_and_assert_cases_on_single_operation(&o, NextBackFinish);

        struct NextUntilLastNone;
        impl SetupIter for NextUntilLastNone {
            fn description(&self) -> String {
                "new iter that have no nulls left".to_string()
            }
            fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
                let last_null_position = iter.clone().rposition(|item| item.is_none());

                // move the iterator to the location where there are no nulls anymore
                if let Some(last_null_position) = last_null_position {
                    iter.nth(last_null_position);
                }
            }
        }
        setup_and_assert_cases_on_single_operation(&o, NextUntilLastNone);

        struct NextUntilLastSome;
        impl SetupIter for NextUntilLastSome {
            fn description(&self) -> String {
                "iter that only have nulls left".to_string()
            }
            fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
                let last_some_position = iter.clone().rposition(|item| item.is_some());

                // move the iterator to the location where there are only nulls
                if let Some(last_some_position) = last_some_position {
                    iter.nth(last_some_position);
                }
            }
        }
        setup_and_assert_cases_on_single_operation(&o, NextUntilLastSome);
    }

    /// Helper function that will assert that the provided operation
    /// produces the same result for both [`ArrayIter`] and slice iterator
    /// under various consumption patterns (e.g. some calls to next/next_back/consume_all/etc)
    ///
    /// this is different from [`assert_array_iterator_cases`] as this also check that the state after the call is correct
    /// to make sure we don't leave the iterator in incorrect state
    fn assert_array_iterator_cases_mutate<O: MutatingArrayIteratorOp>(o: O) {
        struct Adapter<O: MutatingArrayIteratorOp> {
            o: O,
        }

        #[derive(Debug, PartialEq)]
        struct AdapterOutput<Value> {
            value: Value,
            /// collect on the iterator after running the operation
            leftover: Vec<Option<i32>>,
        }

        impl<O: MutatingArrayIteratorOp> ConsumingArrayIteratorOp for Adapter<O> {
            type Output = AdapterOutput<O::Output>;

            fn name(&self) -> String {
                self.o.name()
            }

            fn get_value<T: SharedBetweenArrayIterAndSliceIter>(
                &self,
                mut iter: T,
            ) -> Self::Output {
                let value = self.o.get_value(&mut iter);

                // Get the rest of the iterator to make sure we leave the iterator in a valid state
                let leftover: Vec<_> = iter.collect();

                AdapterOutput { value, leftover }
            }
        }

        assert_array_iterator_cases(Adapter { o })
    }

    #[derive(Debug, PartialEq)]
    struct CallTrackingAndResult<Result: Debug + PartialEq, CallArgs: Debug + PartialEq> {
        result: Result,
        calls: Vec<CallArgs>,
    }
    type CallTrackingWithInputType<Result> = CallTrackingAndResult<Result, Option<i32>>;
    type CallTrackingOnly = CallTrackingWithInputType<()>;

    #[test]
    fn assert_position() {
        struct PositionOp {
            reverse: bool,
            number_of_false: usize,
        }

        impl MutatingArrayIteratorOp for PositionOp {
            type Output = CallTrackingWithInputType<Option<usize>>;
            fn name(&self) -> String {
                if self.reverse {
                    format!("rposition with {} false returned", self.number_of_false)
                } else {
                    format!("position with {} false returned", self.number_of_false)
                }
            }

            fn get_value<T: SharedBetweenArrayIterAndSliceIter>(
                &self,
                iter: &mut T,
            ) -> Self::Output {
                let mut items = vec![];

                let mut count = 0;

                let cb = |item| {
                    items.push(item);

                    if count < self.number_of_false {
                        count += 1;
                        false
                    } else {
                        true
                    }
                };

                let position_result = if self.reverse {
                    iter.rposition(cb)
                } else {
                    iter.position(cb)
                };

                CallTrackingAndResult {
                    result: position_result,
                    calls: items,
                }
            }
        }

        for reverse in [false, true] {
            for number_of_false in [0, 1, 2, usize::MAX] {
                assert_array_iterator_cases_mutate(PositionOp {
                    reverse,
                    number_of_false,
                });
            }
        }
    }

    #[test]
    fn assert_nth() {
        for (array, source) in get_int32_iterator_cases() {
            let actual = ArrayIter::new(&array);
            let expected = source.iter().copied();
            {
                let mut actual = actual.clone();
                let mut expected = expected.clone();
                for _ in 0..expected.len() {
                    #[allow(clippy::iter_nth_zero)]
                    let actual_val = actual.nth(0);
                    #[allow(clippy::iter_nth_zero)]
                    let expected_val = expected.nth(0);
                    assert_eq!(actual_val, expected_val, "Failed on nth(0)");
                }
            }

            {
                let mut actual = actual.clone();
                let mut expected = expected.clone();
                for _ in 0..expected.len() {
                    let actual_val = actual.nth(1);
                    let expected_val = expected.nth(1);
                    assert_eq!(actual_val, expected_val, "Failed on nth(1)");
                }
            }

            {
                let mut actual = actual.clone();
                let mut expected = expected.clone();
                for _ in 0..expected.len() {
                    let actual_val = actual.nth(2);
                    let expected_val = expected.nth(2);
                    assert_eq!(actual_val, expected_val, "Failed on nth(2)");
                }
            }
        }
    }

    #[test]
    fn assert_nth_back() {
        for (array, source) in get_int32_iterator_cases() {
            let actual = ArrayIter::new(&array);
            let expected = source.iter().copied();
            {
                let mut actual = actual.clone();
                let mut expected = expected.clone();
                for _ in 0..expected.len() {
                    #[allow(clippy::iter_nth_zero)]
                    let actual_val = actual.nth_back(0);
                    #[allow(clippy::iter_nth_zero)]
                    let expected_val = expected.nth_back(0);
                    assert_eq!(actual_val, expected_val, "Failed on nth_back(0)");
                }
            }

            {
                let mut actual = actual.clone();
                let mut expected = expected.clone();
                for _ in 0..expected.len() {
                    let actual_val = actual.nth_back(1);
                    let expected_val = expected.nth_back(1);
                    assert_eq!(actual_val, expected_val, "Failed on nth_back(1)");
                }
            }

            {
                let mut actual = actual.clone();
                let mut expected = expected.clone();
                for _ in 0..expected.len() {
                    let actual_val = actual.nth_back(2);
                    let expected_val = expected.nth_back(2);
                    assert_eq!(actual_val, expected_val, "Failed on nth_back(2)");
                }
            }
        }
    }

    #[test]
    fn assert_last() {
        for (array, source) in get_int32_iterator_cases() {
            let mut actual_forward = ArrayIter::new(&array);
            let mut expected_forward = source.iter().copied();

            for _ in 0..source.len() + 1 {
                {
                    let actual_forward_clone = actual_forward.clone();
                    let expected_forward_clone = expected_forward.clone();

                    assert_eq!(actual_forward_clone.last(), expected_forward_clone.last());
                }

                actual_forward.next();
                expected_forward.next();
            }

            let mut actual_backward = ArrayIter::new(&array);
            let mut expected_backward = source.iter().copied();
            for _ in 0..source.len() + 1 {
                {
                    assert_eq!(
                        actual_backward.clone().last(),
                        expected_backward.clone().last()
                    );
                }

                actual_backward.next_back();
                expected_backward.next_back();
            }
        }
    }

    #[test]
    fn assert_for_each() {
        struct ForEachOp;

        impl ConsumingArrayIteratorOp for ForEachOp {
            type Output = CallTrackingOnly;

            fn name(&self) -> String {
                "for_each".to_string()
            }

            fn get_value<T: SharedBetweenArrayIterAndSliceIter>(&self, iter: T) -> Self::Output {
                let mut items = Vec::with_capacity(iter.len());

                iter.for_each(|item| {
                    items.push(item);
                });

                CallTrackingAndResult {
                    calls: items,
                    result: (),
                }
            }
        }

        assert_array_iterator_cases(ForEachOp)
    }

    #[test]
    fn assert_fold() {
        struct FoldOp {
            reverse: bool,
        }

        #[derive(Debug, PartialEq)]
        struct CallArgs {
            acc: Option<i32>,
            item: Option<i32>,
        }

        impl ConsumingArrayIteratorOp for FoldOp {
            type Output = CallTrackingAndResult<Option<i32>, CallArgs>;

            fn name(&self) -> String {
                if self.reverse {
                    "rfold".to_string()
                } else {
                    "fold".to_string()
                }
            }

            fn get_value<T: SharedBetweenArrayIterAndSliceIter>(&self, iter: T) -> Self::Output {
                let mut items = Vec::with_capacity(iter.len());

                let cb = |acc, item| {
                    items.push(CallArgs { item, acc });

                    item.map(|val| val + 100)
                };

                let result = if self.reverse {
                    iter.rfold(Some(1), cb)
                } else {
                    #[allow(clippy::manual_try_fold)]
                    iter.fold(Some(1), cb)
                };

                CallTrackingAndResult {
                    calls: items,
                    result,
                }
            }
        }

        assert_array_iterator_cases(FoldOp { reverse: false });
        assert_array_iterator_cases(FoldOp { reverse: true });
    }

    #[test]
    fn assert_count() {
        struct CountOp;

        impl ConsumingArrayIteratorOp for CountOp {
            type Output = usize;

            fn name(&self) -> String {
                "count".to_string()
            }

            fn get_value<T: SharedBetweenArrayIterAndSliceIter>(&self, iter: T) -> Self::Output {
                iter.count()
            }
        }

        assert_array_iterator_cases(CountOp)
    }

    #[test]
    fn assert_any() {
        struct AnyOp {
            false_count: usize,
        }

        impl MutatingArrayIteratorOp for AnyOp {
            type Output = CallTrackingWithInputType<bool>;

            fn name(&self) -> String {
                format!("any with {} false returned", self.false_count)
            }

            fn get_value<T: SharedBetweenArrayIterAndSliceIter>(
                &self,
                iter: &mut T,
            ) -> Self::Output {
                let mut items = Vec::with_capacity(iter.len());

                let mut count = 0;
                let res = iter.any(|item| {
                    items.push(item);

                    if count < self.false_count {
                        count += 1;
                        false
                    } else {
                        true
                    }
                });

                CallTrackingWithInputType {
                    calls: items,
                    result: res,
                }
            }
        }

        for false_count in [0, 1, 2, usize::MAX] {
            assert_array_iterator_cases_mutate(AnyOp { false_count });
        }
    }

    #[test]
    fn assert_all() {
        struct AllOp {
            true_count: usize,
        }

        impl MutatingArrayIteratorOp for AllOp {
            type Output = CallTrackingWithInputType<bool>;

            fn name(&self) -> String {
                format!("all with {} false returned", self.true_count)
            }

            fn get_value<T: SharedBetweenArrayIterAndSliceIter>(
                &self,
                iter: &mut T,
            ) -> Self::Output {
                let mut items = Vec::with_capacity(iter.len());

                let mut count = 0;
                let res = iter.all(|item| {
                    items.push(item);

                    if count < self.true_count {
                        count += 1;
                        true
                    } else {
                        false
                    }
                });

                CallTrackingWithInputType {
                    calls: items,
                    result: res,
                }
            }
        }

        for true_count in [0, 1, 2, usize::MAX] {
            assert_array_iterator_cases_mutate(AllOp { true_count });
        }
    }

    #[test]
    fn assert_find() {
        struct FindOp {
            reverse: bool,
            false_count: usize,
        }

        impl MutatingArrayIteratorOp for FindOp {
            type Output = CallTrackingWithInputType<Option<Option<i32>>>;

            fn name(&self) -> String {
                if self.reverse {
                    format!("rfind with {} false returned", self.false_count)
                } else {
                    format!("find with {} false returned", self.false_count)
                }
            }

            fn get_value<T: SharedBetweenArrayIterAndSliceIter>(
                &self,
                iter: &mut T,
            ) -> Self::Output {
                let mut items = vec![];

                let mut count = 0;

                let cb = |item: &Option<i32>| {
                    items.push(*item);

                    if count < self.false_count {
                        count += 1;
                        false
                    } else {
                        true
                    }
                };

                let position_result = if self.reverse {
                    iter.rfind(cb)
                } else {
                    iter.find(cb)
                };

                CallTrackingWithInputType {
                    calls: items,
                    result: position_result,
                }
            }
        }

        for reverse in [false, true] {
            for false_count in [0, 1, 2, usize::MAX] {
                assert_array_iterator_cases_mutate(FindOp {
                    reverse,
                    false_count,
                });
            }
        }
    }

    #[test]
    fn assert_find_map() {
        struct FindMapOp {
            number_of_nones: usize,
        }

        impl MutatingArrayIteratorOp for FindMapOp {
            type Output = CallTrackingWithInputType<Option<&'static str>>;

            fn name(&self) -> String {
                format!("find_map with {} None returned", self.number_of_nones)
            }

            fn get_value<T: SharedBetweenArrayIterAndSliceIter>(
                &self,
                iter: &mut T,
            ) -> Self::Output {
                let mut items = vec![];

                let mut count = 0;

                let result = iter.find_map(|item| {
                    items.push(item);

                    if count < self.number_of_nones {
                        count += 1;
                        None
                    } else {
                        Some("found it")
                    }
                });

                CallTrackingAndResult {
                    result,
                    calls: items,
                }
            }
        }

        for number_of_nones in [0, 1, 2, usize::MAX] {
            assert_array_iterator_cases_mutate(FindMapOp { number_of_nones });
        }
    }

    #[test]
    fn assert_partition() {
        struct PartitionOp<F: Fn(usize, &Option<i32>) -> bool> {
            description: &'static str,
            predicate: F,
        }

        #[derive(Debug, PartialEq)]
        struct PartitionResult {
            left: Vec<Option<i32>>,
            right: Vec<Option<i32>>,
        }

        impl<F: Fn(usize, &Option<i32>) -> bool> ConsumingArrayIteratorOp for PartitionOp<F> {
            type Output = CallTrackingWithInputType<PartitionResult>;

            fn name(&self) -> String {
                format!("partition by {}", self.description)
            }

            fn get_value<T: SharedBetweenArrayIterAndSliceIter>(&self, iter: T) -> Self::Output {
                let mut items = vec![];

                let mut index = 0;

                let (left, right) = iter.partition(|item| {
                    items.push(*item);

                    let res = (self.predicate)(index, item);

                    index += 1;
                    res
                });

                CallTrackingAndResult {
                    result: PartitionResult { left, right },
                    calls: items,
                }
            }
        }

        assert_array_iterator_cases(PartitionOp {
            description: "None on one side and Some(*) on the other",
            predicate: |_, item| item.is_none(),
        });

        assert_array_iterator_cases(PartitionOp {
            description: "all true",
            predicate: |_, _| true,
        });

        assert_array_iterator_cases(PartitionOp {
            description: "all false",
            predicate: |_, _| false,
        });

        let random_values = (0..100).map(|_| rand::random_bool(0.5)).collect::<Vec<_>>();
        assert_array_iterator_cases(PartitionOp {
            description: "random",
            predicate: |index, _| random_values[index % random_values.len()],
        });
    }
}