## Coverage Report

#### Created: 2025-11-17 14:14

next uncovered line (L), next uncovered region (R), next uncovered branch (B)

    /Users/andrewlamb/Software/arrow-rs/arrow-array/src/iterator.rs

    Line
    Count
    Source
    1
    // Licensed to the Apache Software Foundation (ASF) under one
    2
    // or more contributor license agreements.  See the NOTICE file
    3
    // distributed with this work for additional information
    4
    // regarding copyright ownership.  The ASF licenses this file
    5
    // to you under the Apache License, Version 2.0 (the
    6
    // "License"); you may not use this file except in compliance
    7
    // with the License.  You may obtain a copy of the License at
    8
    //
    9
    //   http://www.apache.org/licenses/LICENSE-2.0
    10
    //
    11
    // Unless required by applicable law or agreed to in writing,
    12
    // software distributed under the License is distributed on an
    13
    // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
    14
    // KIND, either express or implied.  See the License for the
    15
    // specific language governing permissions and limitations
    16
    // under the License.
    17
    18
    //! Idiomatic iterators for [`Array`](crate::Array)
    19
    20
    use crate::array::{
    21
        ArrayAccessor, BooleanArray, FixedSizeBinaryArray, GenericBinaryArray, GenericListArray,
    22
        GenericStringArray, PrimitiveArray,
    23
    };
    24
    use crate::{FixedSizeListArray, GenericListViewArray, MapArray};
    25
    use arrow_buffer::NullBuffer;
    26
    27
    /// An iterator that returns Some(T) or None, that can be used on any [`ArrayAccessor`]
    28
    ///
    29
    /// # Performance
    30
    ///
    31
    /// [`ArrayIter`] provides an idiomatic way to iterate over an array, however, this
    32
    /// comes at the cost of performance. In particular the interleaved handling of
    33
    /// the null mask is often sub-optimal.
    34
    ///
    35
    /// If performing an infallible operation, it is typically faster to perform the operation
    36
    /// on every index of the array, and handle the null mask separately. For [`PrimitiveArray`]
    37
    /// this functionality is provided by [`compute::unary`]
    38
    ///
    39
    /// If performing a fallible operation, it isn't possible to perform the operation independently
    40
    /// of the null mask, as this might result in a spurious failure on a null index. However,
    41
    /// there are more efficient ways to iterate over just the non-null indices, this functionality
    42
    /// is provided by [`compute::try_unary`]
    43
    ///
    44
    /// [`PrimitiveArray`]: crate::PrimitiveArray
    45
    /// [`compute::unary`]: https://docs.rs/arrow/latest/arrow/compute/fn.unary.html
    46
    /// [`compute::try_unary`]: https://docs.rs/arrow/latest/arrow/compute/fn.try_unary.html
    47
    #[derive(Debug, Clone)]
    48
    pub struct ArrayIter<T: ArrayAccessor> {
    49
        array: T,
    50
        logical_nulls: Option<NullBuffer>,
    51
        current: usize,
    52
        current_end: usize,
    53
    }
    54
    55
    impl<T: ArrayAccessor> ArrayIter<T> {
    56
        /// create a new iterator
    57
    1.95k
        pub fn new(array: T) -> Self {
    58
    1.95k
            let len = array.len();
    59
    1.95k
            let logical_nulls = array.logical_nulls().filter(|x| x1.47k.null_count1.47k() > 0);
    60
    1.95k
            ArrayIter {
    61
    1.95k
                array,
    62
    1.95k
                logical_nulls,
    63
    1.95k
                current: 0,
    64
    1.95k
                current_end: len,
    65
    1.95k
            }
    66
    1.95k
        }
    67
    68
        #[inline]
    69
    308k
        fn is_null(&self, idx: usize) -> bool {
    70
    308k
            self.logical_nulls
    71
    308k
                .as_ref()
    72
    308k
                .map(|x| x111k.is_null111k(idx111k))
    73
    308k
                .unwrap_or_default()
    74
    308k
        }
    75
    }
    76
    77
    impl<T: ArrayAccessor> Iterator for ArrayIter<T> {
    78
        type Item = Option<T::Item>;
    79
    80
        #[inline]
    81
    310k
        fn next(&mut self) -> Option<Self::Item> {
    82
    310k
            if self.current == self.current_end {
    83
    1.18k
                None
    84
    308k
            } else if self.is_null(self.current) {
    85
    45.2k
                self.current += 1;
    86
    45.2k
                Some(None)
    87
            } else {
    88
    263k
                let old = self.current;
    89
    263k
                self.current += 1;
    90
                // Safety:
    91
                // we just checked bounds in `self.current_end == self.current`
    92
                // this is safe on the premise that this struct is initialized with
    93
                // current = array.len()
    94
                // and that current_end is ever only decremented
    95
    263k
                unsafe { Some(Some(self.array.value_unchecked(old))) }
    96
            }
    97
    310k
        }
    98
    99
    2.86k
        fn size_hint(&self) -> (usize, Option<usize>) {
    100
    2.86k
            (
    101
    2.86k
                self.current_end - self.current,
    102
    2.86k
                Some(self.current_end - self.current),
    103
    2.86k
            )
    104
    2.86k
        }
    105
    106
        #[inline]
    107
        fn nth(&mut self, n: usize) -> Option<Self::Item> {
    108
            // Check if we can advance to the desired offset
    109
            match self.current.checked_add(n) {
    110
                // Yes, and still within bounds
    111
                Some(new_current) if new_current < self.current_end => {
    112
                    self.current = new_current;
    113
                }
    114
    115
                // Either overflow or would exceed current_end
    116
                _ => {
    117
                    self.current = self.current_end;
    118
                    return None;
    119
                }
    120
            }
    121
    122
            self.next()
    123
        }
    124
    125
        #[inline]
    126
        fn last(mut self) -> Option<Self::Item> {
    127
            self.next_back()
    128
        }
    129
    130
        #[inline]
    131
        fn count(self) -> usize
    132
        where
    133
            Self: Sized,
    134
        {
    135
            self.len()
    136
        }
    137
    }
    138
    139
    impl<T: ArrayAccessor> DoubleEndedIterator for ArrayIter<T> {
    140
        fn next_back(&mut self) -> Option<Self::Item> {
    141
            if self.current_end == self.current {
    142
                None
    143
            } else {
    144
                self.current_end -= 1;
    145
                Some(if self.is_null(self.current_end) {
    146
                    None
    147
                } else {
    148
                    // Safety:
    149
                    // we just checked bounds in `self.current_end == self.current`
    150
                    // this is safe on the premise that this struct is initialized with
    151
                    // current = array.len()
    152
                    // and that current_end is ever only decremented
    153
                    unsafe { Some(self.array.value_unchecked(self.current_end)) }
    154
                })
    155
            }
    156
        }
    157
    158
        #[inline]
    159
        fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
    160
            // Check if we advance to the one before the desired offset
    161
            match self.current_end.checked_sub(n) {
    162
                // Yes, and still within bounds
    163
                Some(new_offset) if self.current < new_offset => {
    164
                    self.current_end = new_offset;
    165
                }
    166
    167
                // Either underflow or would exceed current
    168
                _ => {
    169
                    self.current = self.current_end;
    170
                    return None;
    171
                }
    172
            }
    173
    174
            self.next_back()
    175
        }
    176
    }
    177
    178
    /// all arrays have known size.
    179
    impl<T: ArrayAccessor> ExactSizeIterator for ArrayIter<T> {}
    180
    181
    /// an iterator that returns Some(T) or None, that can be used on any PrimitiveArray
    182
    pub type PrimitiveIter<'a, T> = ArrayIter<&'a PrimitiveArray<T>>;
    183
    /// an iterator that returns Some(T) or None, that can be used on any BooleanArray
    184
    pub type BooleanIter<'a> = ArrayIter<&'a BooleanArray>;
    185
    /// an iterator that returns Some(T) or None, that can be used on any Utf8Array
    186
    pub type GenericStringIter<'a, T> = ArrayIter<&'a GenericStringArray<T>>;
    187
    /// an iterator that returns Some(T) or None, that can be used on any BinaryArray
    188
    pub type GenericBinaryIter<'a, T> = ArrayIter<&'a GenericBinaryArray<T>>;
    189
    /// an iterator that returns Some(T) or None, that can be used on any FixedSizeBinaryArray
    190
    pub type FixedSizeBinaryIter<'a> = ArrayIter<&'a FixedSizeBinaryArray>;
    191
    /// an iterator that returns Some(T) or None, that can be used on any FixedSizeListArray
    192
    pub type FixedSizeListIter<'a> = ArrayIter<&'a FixedSizeListArray>;
    193
    /// an iterator that returns Some(T) or None, that can be used on any ListArray
    194
    pub type GenericListArrayIter<'a, O> = ArrayIter<&'a GenericListArray<O>>;
    195
    /// an iterator that returns Some(T) or None, that can be used on any MapArray
    196
    pub type MapArrayIter<'a> = ArrayIter<&'a MapArray>;
    197
    /// an iterator that returns Some(T) or None, that can be used on any ListArray
    198
    pub type GenericListViewArrayIter<'a, O> = ArrayIter<&'a GenericListViewArray<O>>;
    199
    #[cfg(test)]
    200
    mod tests {
    201
        use crate::array::{ArrayRef, BinaryArray, BooleanArray, Int32Array, StringArray};
    202
        use crate::iterator::ArrayIter;
    203
        use rand::rngs::StdRng;
    204
        use rand::{Rng, SeedableRng};
    205
        use std::fmt::Debug;
    206
        use std::sync::Arc;
    207
    208
        #[test]
    209
        fn test_primitive_array_iter_round_trip() {
    210
            let array = Int32Array::from(vec![Some(0), None, Some(2), None, Some(4)]);
    211
            let array = Arc::new(array) as ArrayRef;
    212
    213
            let array = array.as_any().downcast_ref::<Int32Array>().unwrap();
    214
    215
            // to and from iter, with a +1
    216
            let result: Int32Array = array.iter().map(|e| e.map(|e| e + 1)).collect();
    217
    218
            let expected = Int32Array::from(vec![Some(1), None, Some(3), None, Some(5)]);
    219
            assert_eq!(result, expected);
    220
    221
            // check if DoubleEndedIterator is implemented
    222
            let result: Int32Array = array.iter().rev().collect();
    223
            let rev_array = Int32Array::from(vec![Some(4), None, Some(2), None, Some(0)]);
    224
            assert_eq!(result, rev_array);
    225
            // check if ExactSizeIterator is implemented
    226
            let _ = array.iter().rposition(|opt_b| opt_b == Some(1));
    227
        }
    228
    229
        #[test]
    230
        fn test_double_ended() {
    231
            let array = Int32Array::from(vec![Some(0), None, Some(2), None, Some(4)]);
    232
            let mut a = array.iter();
    233
            assert_eq!(a.next(), Some(Some(0)));
    234
            assert_eq!(a.next(), Some(None));
    235
            assert_eq!(a.next_back(), Some(Some(4)));
    236
            assert_eq!(a.next_back(), Some(None));
    237
            assert_eq!(a.next_back(), Some(Some(2)));
    238
            // the two sides have met: None is returned by both
    239
            assert_eq!(a.next_back(), None);
    240
            assert_eq!(a.next(), None);
    241
        }
    242
    243
        #[test]
    244
        fn test_string_array_iter_round_trip() {
    245
            let array = StringArray::from(vec![Some("a"), None, Some("aaa"), None, Some("aaaaa")]);
    246
            let array = Arc::new(array) as ArrayRef;
    247
    248
            let array = array.as_any().downcast_ref::<StringArray>().unwrap();
    249
    250
            // to and from iter, with a +1
    251
            let result: StringArray = array
    252
                .iter()
    253
                .map(|e| {
    254
                    e.map(|e| {
    255
                        let mut a = e.to_string();
    256
                        a.push('b');
    257
                        a
    258
                    })
    259
                })
    260
                .collect();
    261
    262
            let expected =
    263
                StringArray::from(vec![Some("ab"), None, Some("aaab"), None, Some("aaaaab")]);
    264
            assert_eq!(result, expected);
    265
    266
            // check if DoubleEndedIterator is implemented
    267
            let result: StringArray = array.iter().rev().collect();
    268
            let rev_array = StringArray::from(vec![Some("aaaaa"), None, Some("aaa"), None, Some("a")]);
    269
            assert_eq!(result, rev_array);
    270
            // check if ExactSizeIterator is implemented
    271
            let _ = array.iter().rposition(|opt_b| opt_b == Some("a"));
    272
        }
    273
    274
        #[test]
    275
        fn test_binary_array_iter_round_trip() {
    276
            let array = BinaryArray::from(vec![
    277
                Some(b"a" as &[u8]),
    278
                None,
    279
                Some(b"aaa"),
    280
                None,
    281
                Some(b"aaaaa"),
    282
            ]);
    283
    284
            // to and from iter
    285
            let result: BinaryArray = array.iter().collect();
    286
    287
            assert_eq!(result, array);
    288
    289
            // check if DoubleEndedIterator is implemented
    290
            let result: BinaryArray = array.iter().rev().collect();
    291
            let rev_array = BinaryArray::from(vec![
    292
                Some(b"aaaaa" as &[u8]),
    293
                None,
    294
                Some(b"aaa"),
    295
                None,
    296
                Some(b"a"),
    297
            ]);
    298
            assert_eq!(result, rev_array);
    299
    300
            // check if ExactSizeIterator is implemented
    301
            let _ = array.iter().rposition(|opt_b| opt_b == Some(&[9]));
    302
        }
    303
    304
        #[test]
    305
        fn test_boolean_array_iter_round_trip() {
    306
            let array = BooleanArray::from(vec![Some(true), None, Some(false)]);
    307
    308
            // to and from iter
    309
            let result: BooleanArray = array.iter().collect();
    310
    311
            assert_eq!(result, array);
    312
    313
            // check if DoubleEndedIterator is implemented
    314
            let result: BooleanArray = array.iter().rev().collect();
    315
            let rev_array = BooleanArray::from(vec![Some(false), None, Some(true)]);
    316
            assert_eq!(result, rev_array);
    317
    318
            // check if ExactSizeIterator is implemented
    319
            let _ = array.iter().rposition(|opt_b| opt_b == Some(true));
    320
        }
    321
    322
        trait SharedBetweenArrayIterAndSliceIter:
    323
            ExactSizeIterator<Item = Option<i32>> + DoubleEndedIterator<Item = Option<i32>> + Clone
    324
        {
    325
        }
    326
        impl<T: Clone + ExactSizeIterator<Item = Option<i32>> + DoubleEndedIterator<Item = Option<i32>>>
    327
            SharedBetweenArrayIterAndSliceIter for T
    328
        {
    329
        }
    330
    331
        fn get_int32_iterator_cases() -> impl Iterator<Item = (Int32Array, Vec<Option<i32>>)> {
    332
            let mut rng = StdRng::seed_from_u64(42);
    333
    334
            let no_nulls_and_no_duplicates = (0..10).map(Some).collect::<Vec<Option<i32>>>();
    335
            let no_nulls_random_values = (0..10)
    336
                .map(|_| rng.random::<i32>())
    337
                .map(Some)
    338
                .collect::<Vec<Option<i32>>>();
    339
    340
            let all_nulls = (0..10).map(|_| None).collect::<Vec<Option<i32>>>();
    341
            let only_start_nulls = (0..10)
    342
                .map(|item| if item < 4 { None } else { Some(item) })
    343
                .collect::<Vec<Option<i32>>>();
    344
            let only_end_nulls = (0..10)
    345
                .map(|item| if item > 8 { None } else { Some(item) })
    346
                .collect::<Vec<Option<i32>>>();
    347
            let only_middle_nulls = (0..10)
    348
                .map(|item| {
    349
                    if (4..=8).contains(&item) && rng.random_bool(0.9) {
    350
                        None
    351
                    } else {
    352
                        Some(item)
    353
                    }
    354
                })
    355
                .collect::<Vec<Option<i32>>>();
    356
            let random_values_with_random_nulls = (0..10)
    357
                .map(|_| {
    358
                    if rng.random_bool(0.3) {
    359
                        None
    360
                    } else {
    361
                        Some(rng.random::<i32>())
    362
                    }
    363
                })
    364
                .collect::<Vec<Option<i32>>>();
    365
    366
            let no_nulls_and_some_duplicates = (0..10)
    367
                .map(|item| item % 3)
    368
                .map(Some)
    369
                .collect::<Vec<Option<i32>>>();
    370
            let no_nulls_and_all_same_value =
    371
                (0..10).map(|_| 9).map(Some).collect::<Vec<Option<i32>>>();
    372
            let no_nulls_and_continues_duplicates = [0, 0, 0, 1, 1, 2, 2, 2, 2, 3]
    373
                .map(Some)
    374
                .into_iter()
    375
                .collect::<Vec<Option<i32>>>();
    376
    377
            let single_null_and_no_duplicates = (0..10)
    378
                .map(|item| if item == 4 { None } else { Some(item) })
    379
                .collect::<Vec<Option<i32>>>();
    380
            let multiple_nulls_and_no_duplicates = (0..10)
    381
                .map(|item| if item % 3 == 2 { None } else { Some(item) })
    382
                .collect::<Vec<Option<i32>>>();
    383
            let continues_nulls_and_no_duplicates = [
    384
                Some(0),
    385
                Some(1),
    386
                None,
    387
                None,
    388
                Some(2),
    389
                Some(3),
    390
                None,
    391
                Some(4),
    392
                Some(5),
    393
                None,
    394
            ]
    395
            .into_iter()
    396
            .collect::<Vec<Option<i32>>>();
    397
    398
            [
    399
                no_nulls_and_no_duplicates,
    400
                no_nulls_random_values,
    401
                no_nulls_and_some_duplicates,
    402
                no_nulls_and_all_same_value,
    403
                no_nulls_and_continues_duplicates,
    404
                all_nulls,
    405
                only_start_nulls,
    406
                only_end_nulls,
    407
                only_middle_nulls,
    408
                random_values_with_random_nulls,
    409
                single_null_and_no_duplicates,
    410
                multiple_nulls_and_no_duplicates,
    411
                continues_nulls_and_no_duplicates,
    412
            ]
    413
            .map(|case| (Int32Array::from(case.clone()), case))
    414
            .into_iter()
    415
        }
    416
    417
        trait SetupIter {
    418
            fn description(&self) -> String;
    419
            fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I);
    420
        }
    421
    422
        struct NoSetup;
    423
        impl SetupIter for NoSetup {
    424
            fn description(&self) -> String {
    425
                "no setup".to_string()
    426
            }
    427
            fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, _iter: &mut I) {
    428
                // none
    429
            }
    430
        }
    431
    432
        fn setup_and_assert_cases_on_single_operation(
    433
            o: &impl ConsumingArrayIteratorOp,
    434
            setup_iterator: impl SetupIter,
    435
        ) {
    436
            for (array, source) in get_int32_iterator_cases() {
    437
                let mut actual = ArrayIter::new(&array);
    438
                let mut expected = source.iter().copied();
    439
    440
                setup_iterator.setup(&mut actual);
    441
                setup_iterator.setup(&mut expected);
    442
    443
                let current_iterator_values: Vec<Option<i32>> = expected.clone().collect();
    444
    445
                assert_eq!(
    446
                    o.get_value(actual),
    447
                    o.get_value(expected),
    448
                    "Failed on op {} for {} (left actual, right expected) ({current_iterator_values:?})",
    449
                    o.name(),
    450
                    setup_iterator.description(),
    451
                );
    452
            }
    453
        }
    454
    455
        /// Trait representing an operation on a [`ArrayIter`]
    456
        /// that can be compared against a slice iterator
    457
        ///
    458
        /// this is for consuming operations (e.g. `count`, `last`, etc)
    459
        trait ConsumingArrayIteratorOp {
    460
            /// What the operation returns (e.g. Option<i32> for last, usize for count, etc)
    461
            type Output: PartialEq + Debug;
    462
    463
            /// The name of the operation, used for error messages
    464
            fn name(&self) -> String;
    465
    466
            /// Get the value of the operation for the provided iterator
    467
            /// This will be either a [`ArrayIter`] or a slice iterator to make sure they produce the same result
    468
            ///
    469
            /// Example implementation:
    470
            /// 1. for `last` it will be the last value
    471
            /// 2. for `count` it will be the returned length
    472
            fn get_value<T: SharedBetweenArrayIterAndSliceIter>(&self, iter: T) -> Self::Output;
    473
        }
    474
    475
        /// Trait representing an operation on a [`ArrayIter`]
    476
        /// that can be compared against a slice iterator.
    477
        ///
    478
        /// This is for mutating operations (e.g. `position`, `any`, `find`, etc)
    479
        trait MutatingArrayIteratorOp {
    480
            /// What the operation returns (e.g. Option<i32> for last, usize for count, etc)
    481
            type Output: PartialEq + Debug;
    482
    483
            /// The name of the operation, used for error messages
    484
            fn name(&self) -> String;
    485
    486
            /// Get the value of the operation for the provided iterator
    487
            /// This will be either a [`ArrayIter`] or a slice iterator to make sure they produce the same result
    488
            ///
    489
            /// Example implementation:
    490
            /// 1. for `for_each` it will be the iterator element that the function was called with
    491
            /// 2. for `fold` it will be the accumulator and the iterator element from each call, as well as the final result
    492
            fn get_value<T: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut T) -> Self::Output;
    493
        }
    494
    495
        /// Helper function that will assert that the provided operation
    496
        /// produces the same result for both [`ArrayIter`] and slice iterator
    497
        /// under various consumption patterns (e.g. some calls to next/next_back/consume_all/etc)
    498
        fn assert_array_iterator_cases<O: ConsumingArrayIteratorOp>(o: O) {
    499
            setup_and_assert_cases_on_single_operation(&o, NoSetup);
    500
    501
            struct Next;
    502
            impl SetupIter for Next {
    503
                fn description(&self) -> String {
    504
                    "new iter after consuming 1 element from the start".to_string()
    505
                }
    506
                fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
    507
                    iter.next();
    508
                }
    509
            }
    510
            setup_and_assert_cases_on_single_operation(&o, Next);
    511
    512
            struct NextBack;
    513
            impl SetupIter for NextBack {
    514
                fn description(&self) -> String {
    515
                    "new iter after consuming 1 element from the end".to_string()
    516
                }
    517
    518
                fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
    519
                    iter.next_back();
    520
                }
    521
            }
    522
    523
            setup_and_assert_cases_on_single_operation(&o, NextBack);
    524
    525
            struct NextAndBack;
    526
            impl SetupIter for NextAndBack {
    527
                fn description(&self) -> String {
    528
                    "new iter after consuming 1 element from start and end".to_string()
    529
                }
    530
    531
                fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
    532
                    iter.next();
    533
                    iter.next_back();
    534
                }
    535
            }
    536
    537
            setup_and_assert_cases_on_single_operation(&o, NextAndBack);
    538
    539
            struct NextUntilLast;
    540
            impl SetupIter for NextUntilLast {
    541
                fn description(&self) -> String {
    542
                    "new iter after consuming all from the start but 1".to_string()
    543
                }
    544
                fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
    545
                    let len = iter.len();
    546
                    if len > 1 {
    547
                        iter.nth(len - 2);
    548
                    }
    549
                }
    550
            }
    551
            setup_and_assert_cases_on_single_operation(&o, NextUntilLast);
    552
    553
            struct NextBackUntilFirst;
    554
            impl SetupIter for NextBackUntilFirst {
    555
                fn description(&self) -> String {
    556
                    "new iter after consuming all from the end but 1".to_string()
    557
                }
    558
    559
                fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
    560
                    let len = iter.len();
    561
                    if len > 1 {
    562
                        iter.nth_back(len - 2);
    563
                    }
    564
                }
    565
            }
    566
            setup_and_assert_cases_on_single_operation(&o, NextBackUntilFirst);
    567
    568
            struct NextFinish;
    569
            impl SetupIter for NextFinish {
    570
                fn description(&self) -> String {
    571
                    "new iter after consuming all from the start".to_string()
    572
                }
    573
                fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
    574
                    iter.nth(iter.len());
    575
                }
    576
            }
    577
            setup_and_assert_cases_on_single_operation(&o, NextFinish);
    578
    579
            struct NextBackFinish;
    580
            impl SetupIter for NextBackFinish {
    581
                fn description(&self) -> String {
    582
                    "new iter after consuming all from the end".to_string()
    583
                }
    584
                fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
    585
                    iter.nth_back(iter.len());
    586
                }
    587
            }
    588
            setup_and_assert_cases_on_single_operation(&o, NextBackFinish);
    589
    590
            struct NextUntilLastNone;
    591
            impl SetupIter for NextUntilLastNone {
    592
                fn description(&self) -> String {
    593
                    "new iter that have no nulls left".to_string()
    594
                }
    595
                fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
    596
                    let last_null_position = iter.clone().rposition(|item| item.is_none());
    597
    598
                    // move the iterator to the location where there are no nulls anymore
    599
                    if let Some(last_null_position) = last_null_position {
    600
                        iter.nth(last_null_position);
    601
                    }
    602
                }
    603
            }
    604
            setup_and_assert_cases_on_single_operation(&o, NextUntilLastNone);
    605
    606
            struct NextUntilLastSome;
    607
            impl SetupIter for NextUntilLastSome {
    608
                fn description(&self) -> String {
    609
                    "iter that only have nulls left".to_string()
    610
                }
    611
                fn setup<I: SharedBetweenArrayIterAndSliceIter>(&self, iter: &mut I) {
    612
                    let last_some_position = iter.clone().rposition(|item| item.is_some());
    613
    614
                    // move the iterator to the location where there are only nulls
    615
                    if let Some(last_some_position) = last_some_position {
    616
                        iter.nth(last_some_position);
    617
                    }
    618
                }
    619
            }
    620
            setup_and_assert_cases_on_single_operation(&o, NextUntilLastSome);
    621
        }
    622
    623
        /// Helper function that will assert that the provided operation
    624
        /// produces the same result for both [`ArrayIter`] and slice iterator
    625
        /// under various consumption patterns (e.g. some calls to next/next_back/consume_all/etc)
    626
        ///
    627
        /// this is different from [`assert_array_iterator_cases`] as this also check that the state after the call is correct
    628
        /// to make sure we don't leave the iterator in incorrect state
    629
        fn assert_array_iterator_cases_mutate<O: MutatingArrayIteratorOp>(o: O) {
    630
            struct Adapter<O: MutatingArrayIteratorOp> {
    631
                o: O,
    632
            }
    633
    634
            #[derive(Debug, PartialEq)]
    635
            struct AdapterOutput<Value> {
    636
                value: Value,
    637
                /// collect on the iterator after running the operation
    638
                leftover: Vec<Option<i32>>,
    639
            }
    640
    641
            impl<O: MutatingArrayIteratorOp> ConsumingArrayIteratorOp for Adapter<O> {
    642
                type Output = AdapterOutput<O::Output>;
    643
    644
                fn name(&self) -> String {
    645
                    self.o.name()
    646
                }
    647
    648
                fn get_value<T: SharedBetweenArrayIterAndSliceIter>(
    649
                    &self,
    650
                    mut iter: T,
    651
                ) -> Self::Output {
    652
                    let value = self.o.get_value(&mut iter);
    653
    654
                    // Get the rest of the iterator to make sure we leave the iterator in a valid state
    655
                    let leftover: Vec<_> = iter.collect();
    656
    657
                    AdapterOutput { value, leftover }
    658
                }
    659
            }
    660
    661
            assert_array_iterator_cases(Adapter { o })
    662
        }
    663
    664
        #[derive(Debug, PartialEq)]
    665
        struct CallTrackingAndResult<Result: Debug + PartialEq, CallArgs: Debug + PartialEq> {
    666
            result: Result,
    667
            calls: Vec<CallArgs>,
    668
        }
    669
        type CallTrackingWithInputType<Result> = CallTrackingAndResult<Result, Option<i32>>;
    670
        type CallTrackingOnly = CallTrackingWithInputType<()>;
    671
    672
        #[test]
    673
        fn assert_position() {
    674
            struct PositionOp {
    675
                reverse: bool,
    676
                number_of_false: usize,
    677
            }
    678
    679
            impl MutatingArrayIteratorOp for PositionOp {
    680
                type Output = CallTrackingWithInputType<Option<usize>>;
    681
                fn name(&self) -> String {
    682
                    if self.reverse {
    683
                        format!("rposition with {} false returned", self.number_of_false)
    684
                    } else {
    685
                        format!("position with {} false returned", self.number_of_false)
    686
                    }
    687
                }
    688
    689
                fn get_value<T: SharedBetweenArrayIterAndSliceIter>(
    690
                    &self,
    691
                    iter: &mut T,
    692
                ) -> Self::Output {
    693
                    let mut items = vec![];
    694
    695
                    let mut count = 0;
    696
    697
                    let cb = |item| {
    698
                        items.push(item);
    699
    700
                        if count < self.number_of_false {
    701
                            count += 1;
    702
                            false
    703
                        } else {
    704
                            true
    705
                        }
    706
                    };
    707
    708
                    let position_result = if self.reverse {
    709
                        iter.rposition(cb)
    710
                    } else {
    711
                        iter.position(cb)
    712
                    };
    713
    714
                    CallTrackingAndResult {
    715
                        result: position_result,
    716
                        calls: items,
    717
                    }
    718
                }
    719
            }
    720
    721
            for reverse in [false, true] {
    722
                for number_of_false in [0, 1, 2, usize::MAX] {
    723
                    assert_array_iterator_cases_mutate(PositionOp {
    724
                        reverse,
    725
                        number_of_false,
    726
                    });
    727
                }
    728
            }
    729
        }
    730
    731
        #[test]
    732
        fn assert_nth() {
    733
            for (array, source) in get_int32_iterator_cases() {
    734
                let actual = ArrayIter::new(&array);
    735
                let expected = source.iter().copied();
    736
                {
    737
                    let mut actual = actual.clone();
    738
                    let mut expected = expected.clone();
    739
                    for _ in 0..expected.len() {
    740
                        #[allow(clippy::iter_nth_zero)]
    741
                        let actual_val = actual.nth(0);
    742
                        #[allow(clippy::iter_nth_zero)]
    743
                        let expected_val = expected.nth(0);
    744
                        assert_eq!(actual_val, expected_val, "Failed on nth(0)");
    745
                    }
    746
                }
    747
    748
                {
    749
                    let mut actual = actual.clone();
    750
                    let mut expected = expected.clone();
    751
                    for _ in 0..expected.len() {
    752
                        let actual_val = actual.nth(1);
    753
                        let expected_val = expected.nth(1);
    754
                        assert_eq!(actual_val, expected_val, "Failed on nth(1)");
    755
                    }
    756
                }
    757
    758
                {
    759
                    let mut actual = actual.clone();
    760
                    let mut expected = expected.clone();
    761
                    for _ in 0..expected.len() {
    762
                        let actual_val = actual.nth(2);
    763
                        let expected_val = expected.nth(2);
    764
                        assert_eq!(actual_val, expected_val, "Failed on nth(2)");
    765
                    }
    766
                }
    767
            }
    768
        }
    769
    770
        #[test]
    771
        fn assert_nth_back() {
    772
            for (array, source) in get_int32_iterator_cases() {
    773
                let actual = ArrayIter::new(&array);
    774
                let expected = source.iter().copied();
    775
                {
    776
                    let mut actual = actual.clone();
    777
                    let mut expected = expected.clone();
    778
                    for _ in 0..expected.len() {
    779
                        #[allow(clippy::iter_nth_zero)]
    780
                        let actual_val = actual.nth_back(0);
    781
                        #[allow(clippy::iter_nth_zero)]
    782
                        let expected_val = expected.nth_back(0);
    783
                        assert_eq!(actual_val, expected_val, "Failed on nth_back(0)");
    784
                    }
    785
                }
    786
    787
                {
    788
                    let mut actual = actual.clone();
    789
                    let mut expected = expected.clone();
    790
                    for _ in 0..expected.len() {
    791
                        let actual_val = actual.nth_back(1);
    792
                        let expected_val = expected.nth_back(1);
    793
                        assert_eq!(actual_val, expected_val, "Failed on nth_back(1)");
    794
                    }
    795
                }
    796
    797
                {
    798
                    let mut actual = actual.clone();
    799
                    let mut expected = expected.clone();
    800
                    for _ in 0..expected.len() {
    801
                        let actual_val = actual.nth_back(2);
    802
                        let expected_val = expected.nth_back(2);
    803
                        assert_eq!(actual_val, expected_val, "Failed on nth_back(2)");
    804
                    }
    805
                }
    806
            }
    807
        }
    808
    809
        #[test]
    810
        fn assert_last() {
    811
            for (array, source) in get_int32_iterator_cases() {
    812
                let mut actual_forward = ArrayIter::new(&array);
    813
                let mut expected_forward = source.iter().copied();
    814
    815
                for _ in 0..source.len() + 1 {
    816
                    {
    817
                        let actual_forward_clone = actual_forward.clone();
    818
                        let expected_forward_clone = expected_forward.clone();
    819
    820
                        assert_eq!(actual_forward_clone.last(), expected_forward_clone.last());
    821
                    }
    822
    823
                    actual_forward.next();
    824
                    expected_forward.next();
    825
                }
    826
    827
                let mut actual_backward = ArrayIter::new(&array);
    828
                let mut expected_backward = source.iter().copied();
    829
                for _ in 0..source.len() + 1 {
    830
                    {
    831
                        assert_eq!(
    832
                            actual_backward.clone().last(),
    833
                            expected_backward.clone().last()
    834
                        );
    835
                    }
    836
    837
                    actual_backward.next_back();
    838
                    expected_backward.next_back();
    839
                }
    840
            }
    841
        }
    842
    843
        #[test]
    844
        fn assert_for_each() {
    845
            struct ForEachOp;
    846
    847
            impl ConsumingArrayIteratorOp for ForEachOp {
    848
                type Output = CallTrackingOnly;
    849
    850
                fn name(&self) -> String {
    851
                    "for_each".to_string()
    852
                }
    853
    854
                fn get_value<T: SharedBetweenArrayIterAndSliceIter>(&self, iter: T) -> Self::Output {
    855
                    let mut items = Vec::with_capacity(iter.len());
    856
    857
                    iter.for_each(|item| {
    858
                        items.push(item);
    859
                    });
    860
    861
                    CallTrackingAndResult {
    862
                        calls: items,
    863
                        result: (),
    864
                    }
    865
                }
    866
            }
    867
    868
            assert_array_iterator_cases(ForEachOp)
    869
        }
    870
    871
        #[test]
    872
        fn assert_fold() {
    873
            struct FoldOp {
    874
                reverse: bool,
    875
            }
    876
    877
            #[derive(Debug, PartialEq)]
    878
            struct CallArgs {
    879
                acc: Option<i32>,
    880
                item: Option<i32>,
    881
            }
    882
    883
            impl ConsumingArrayIteratorOp for FoldOp {
    884
                type Output = CallTrackingAndResult<Option<i32>, CallArgs>;
    885
    886
                fn name(&self) -> String {
    887
                    if self.reverse {
    888
                        "rfold".to_string()
    889
                    } else {
    890
                        "fold".to_string()
    891
                    }
    892
                }
    893
    894
                fn get_value<T: SharedBetweenArrayIterAndSliceIter>(&self, iter: T) -> Self::Output {
    895
                    let mut items = Vec::with_capacity(iter.len());
    896
    897
                    let cb = |acc, item| {
    898
                        items.push(CallArgs { item, acc });
    899
    900
                        item.map(|val| val + 100)
    901
                    };
    902
    903
                    let result = if self.reverse {
    904
                        iter.rfold(Some(1), cb)
    905
                    } else {
    906
                        #[allow(clippy::manual_try_fold)]
    907
                        iter.fold(Some(1), cb)
    908
                    };
    909
    910
                    CallTrackingAndResult {
    911
                        calls: items,
    912
                        result,
    913
                    }
    914
                }
    915
            }
    916
    917
            assert_array_iterator_cases(FoldOp { reverse: false });
    918
            assert_array_iterator_cases(FoldOp { reverse: true });
    919
        }
    920
    921
        #[test]
    922
        fn assert_count() {
    923
            struct CountOp;
    924
    925
            impl ConsumingArrayIteratorOp for CountOp {
    926
                type Output = usize;
    927
    928
                fn name(&self) -> String {
    929
                    "count".to_string()
    930
                }
    931
    932
                fn get_value<T: SharedBetweenArrayIterAndSliceIter>(&self, iter: T) -> Self::Output {
    933
                    iter.count()
    934
                }
    935
            }
    936
    937
            assert_array_iterator_cases(CountOp)
    938
        }
    939
    940
        #[test]
    941
        fn assert_any() {
    942
            struct AnyOp {
    943
                false_count: usize,
    944
            }
    945
    946
            impl MutatingArrayIteratorOp for AnyOp {
    947
                type Output = CallTrackingWithInputType<bool>;
    948
    949
                fn name(&self) -> String {
    950
                    format!("any with {} false returned", self.false_count)
    951
                }
    952
    953
                fn get_value<T: SharedBetweenArrayIterAndSliceIter>(
    954
                    &self,
    955
                    iter: &mut T,
    956
                ) -> Self::Output {
    957
                    let mut items = Vec::with_capacity(iter.len());
    958
    959
                    let mut count = 0;
    960
                    let res = iter.any(|item| {
    961
                        items.push(item);
    962
    963
                        if count < self.false_count {
    964
                            count += 1;
    965
                            false
    966
                        } else {
    967
                            true
    968
                        }
    969
                    });
    970
    971
                    CallTrackingWithInputType {
    972
                        calls: items,
    973
                        result: res,
    974
                    }
    975
                }
    976
            }
    977
    978
            for false_count in [0, 1, 2, usize::MAX] {
    979
                assert_array_iterator_cases_mutate(AnyOp { false_count });
    980
            }
    981
        }
    982
    983
        #[test]
    984
        fn assert_all() {
    985
            struct AllOp {
    986
                true_count: usize,
    987
            }
    988
    989
            impl MutatingArrayIteratorOp for AllOp {
    990
                type Output = CallTrackingWithInputType<bool>;
    991
    992
                fn name(&self) -> String {
    993
                    format!("all with {} false returned", self.true_count)
    994
                }
    995
    996
                fn get_value<T: SharedBetweenArrayIterAndSliceIter>(
    997
                    &self,
    998
                    iter: &mut T,
    999
                ) -> Self::Output {
    1000
                    let mut items = Vec::with_capacity(iter.len());
    1001
    1002
                    let mut count = 0;
    1003
                    let res = iter.all(|item| {
    1004
                        items.push(item);
    1005
    1006
                        if count < self.true_count {
    1007
                            count += 1;
    1008
                            true
    1009
                        } else {
    1010
                            false
    1011
                        }
    1012
                    });
    1013
    1014
                    CallTrackingWithInputType {
    1015
                        calls: items,
    1016
                        result: res,
    1017
                    }
    1018
                }
    1019
            }
    1020
    1021
            for true_count in [0, 1, 2, usize::MAX] {
    1022
                assert_array_iterator_cases_mutate(AllOp { true_count });
    1023
            }
    1024
        }
    1025
    1026
        #[test]
    1027
        fn assert_find() {
    1028
            struct FindOp {
    1029
                reverse: bool,
    1030
                false_count: usize,
    1031
            }
    1032
    1033
            impl MutatingArrayIteratorOp for FindOp {
    1034
                type Output = CallTrackingWithInputType<Option<Option<i32>>>;
    1035
    1036
                fn name(&self) -> String {
    1037
                    if self.reverse {
    1038
                        format!("rfind with {} false returned", self.false_count)
    1039
                    } else {
    1040
                        format!("find with {} false returned", self.false_count)
    1041
                    }
    1042
                }
    1043
    1044
                fn get_value<T: SharedBetweenArrayIterAndSliceIter>(
    1045
                    &self,
    1046
                    iter: &mut T,
    1047
                ) -> Self::Output {
    1048
                    let mut items = vec![];
    1049
    1050
                    let mut count = 0;
    1051
    1052
                    let cb = |item: &Option<i32>| {
    1053
                        items.push(*item);
    1054
    1055
                        if count < self.false_count {
    1056
                            count += 1;
    1057
                            false
    1058
                        } else {
    1059
                            true
    1060
                        }
    1061
                    };
    1062
    1063
                    let position_result = if self.reverse {
    1064
                        iter.rfind(cb)
    1065
                    } else {
    1066
                        iter.find(cb)
    1067
                    };
    1068
    1069
                    CallTrackingWithInputType {
    1070
                        calls: items,
    1071
                        result: position_result,
    1072
                    }
    1073
                }
    1074
            }
    1075
    1076
            for reverse in [false, true] {
    1077
                for false_count in [0, 1, 2, usize::MAX] {
    1078
                    assert_array_iterator_cases_mutate(FindOp {
    1079
                        reverse,
    1080
                        false_count,
    1081
                    });
    1082
                }
    1083
            }
    1084
        }
    1085
    1086
        #[test]
    1087
        fn assert_find_map() {
    1088
            struct FindMapOp {
    1089
                number_of_nones: usize,
    1090
            }
    1091
    1092
            impl MutatingArrayIteratorOp for FindMapOp {
    1093
                type Output = CallTrackingWithInputType<Option<&'static str>>;
    1094
    1095
                fn name(&self) -> String {
    1096
                    format!("find_map with {} None returned", self.number_of_nones)
    1097
                }
    1098
    1099
                fn get_value<T: SharedBetweenArrayIterAndSliceIter>(
    1100
                    &self,
    1101
                    iter: &mut T,
    1102
                ) -> Self::Output {
    1103
                    let mut items = vec![];
    1104
    1105
                    let mut count = 0;
    1106
    1107
                    let result = iter.find_map(|item| {
    1108
                        items.push(item);
    1109
    1110
                        if count < self.number_of_nones {
    1111
                            count += 1;
    1112
                            None
    1113
                        } else {
    1114
                            Some("found it")
    1115
                        }
    1116
                    });
    1117
    1118
                    CallTrackingAndResult {
    1119
                        result,
    1120
                        calls: items,
    1121
                    }
    1122
                }
    1123
            }
    1124
    1125
            for number_of_nones in [0, 1, 2, usize::MAX] {
    1126
                assert_array_iterator_cases_mutate(FindMapOp { number_of_nones });
    1127
            }
    1128
        }
    1129
    1130
        #[test]
    1131
        fn assert_partition() {
    1132
            struct PartitionOp<F: Fn(usize, &Option<i32>) -> bool> {
    1133
                description: &'static str,
    1134
                predicate: F,
    1135
            }
    1136
    1137
            #[derive(Debug, PartialEq)]
    1138
            struct PartitionResult {
    1139
                left: Vec<Option<i32>>,
    1140
                right: Vec<Option<i32>>,
    1141
            }
    1142
    1143
            impl<F: Fn(usize, &Option<i32>) -> bool> ConsumingArrayIteratorOp for PartitionOp<F> {
    1144
                type Output = CallTrackingWithInputType<PartitionResult>;
    1145
    1146
                fn name(&self) -> String {
    1147
                    format!("partition by {}", self.description)
    1148
                }
    1149
    1150
                fn get_value<T: SharedBetweenArrayIterAndSliceIter>(&self, iter: T) -> Self::Output {
    1151
                    let mut items = vec![];
    1152
    1153
                    let mut index = 0;
    1154
    1155
                    let (left, right) = iter.partition(|item| {
    1156
                        items.push(*item);
    1157
    1158
                        let res = (self.predicate)(index, item);
    1159
    1160
                        index += 1;
    1161
                        res
    1162
                    });
    1163
    1164
                    CallTrackingAndResult {
    1165
                        result: PartitionResult { left, right },
    1166
                        calls: items,
    1167
                    }
    1168
                }
    1169
            }
    1170
    1171
            assert_array_iterator_cases(PartitionOp {
    1172
                description: "None on one side and Some(*) on the other",
    1173
                predicate: |_, item| item.is_none(),
    1174
            });
    1175
    1176
            assert_array_iterator_cases(PartitionOp {
    1177
                description: "all true",
    1178
                predicate: |_, _| true,
    1179
            });
    1180
    1181
            assert_array_iterator_cases(PartitionOp {
    1182
                description: "all false",
    1183
                predicate: |_, _| false,
    1184
            });
    1185
    1186
            let random_values = (0..100).map(|_| rand::random_bool(0.5)).collect::<Vec<_>>();
    1187
            assert_array_iterator_cases(PartitionOp {
    1188
                description: "random",
    1189
                predicate: |index, _| random_values[index % random_values.len()],
    1190
            });
    1191
        }
    1192
    }