1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

//! Common splitter for strings and slices
//!
//! This module is private, so these items are effectively `pub(super)`

use crate::iter::plumbing::{Folder, UnindexedProducer};

/// Common producer for splitting on a predicate.
pub(super) struct SplitProducer<'p, P, V> {
    data: V,
    separator: &'p P,

    /// Marks the endpoint beyond which we've already found no separators.
    tail: usize,
}

/// Helper trait so `&str`, `&[T]`, and `&mut [T]` can share `SplitProducer`.
pub(super) trait Fissile<P>: Sized {
    fn length(&self) -> usize;
    fn midpoint(&self, end: usize) -> usize;
    fn find(&self, separator: &P, start: usize, end: usize) -> Option<usize>;
    fn rfind(&self, separator: &P, end: usize) -> Option<usize>;
    fn split_once(self, index: usize) -> (Self, Self);
    fn fold_splits<F>(self, separator: &P, folder: F, skip_last: bool) -> F
    where
        F: Folder<Self>,
        Self: Send;
}

impl<'p, P, V> SplitProducer<'p, P, V>
where
    V: Fissile<P> + Send,
{
    pub(super) fn new(data: V, separator: &'p P) -> Self {
        SplitProducer {
            tail: data.length(),
            data,
            separator,
        }
    }

    /// Common `fold_with` implementation, integrating `SplitTerminator`'s
    /// need to sometimes skip its final empty item.
    pub(super) fn fold_with<F>(self, folder: F, skip_last: bool) -> F
    where
        F: Folder<V>,
    {
        let SplitProducer {
            data,
            separator,
            tail,
        } = self;

        if tail == data.length() {
            // No tail section, so just let `fold_splits` handle it.
            data.fold_splits(separator, folder, skip_last)
        } else if let Some(index) = data.rfind(separator, tail) {
            // We found the last separator to complete the tail, so
            // end with that slice after `fold_splits` finds the rest.
            let (left, right) = data.split_once(index);
            let folder = left.fold_splits(separator, folder, false);
            if skip_last || folder.full() {
                folder
            } else {
                folder.consume(right)
            }
        } else {
            // We know there are no separators at all.  Return our whole data.
            if skip_last {
                folder
            } else {
                folder.consume(data)
            }
        }
    }
}

impl<'p, P, V> UnindexedProducer for SplitProducer<'p, P, V>
where
    V: Fissile<P> + Send,
    P: Sync,
{
    type Item = V;

    fn split(self) -> (Self, Option<Self>) {
        // Look forward for the separator, and failing that look backward.
        let mid = self.data.midpoint(self.tail);
        let index = match self.data.find(self.separator, mid, self.tail) {
            Some(i) => Some(mid + i),
            None => self.data.rfind(self.separator, mid),
        };

        if let Some(index) = index {
            let len = self.data.length();
            let (left, right) = self.data.split_once(index);

            let (left_tail, right_tail) = if index < mid {
                // If we scanned backwards to find the separator, everything in
                // the right side is exhausted, with no separators left to find.
                (index, 0)
            } else {
                let right_index = len - right.length();
                (mid, self.tail - right_index)
            };

            // Create the left split before the separator.
            let left = SplitProducer {
                data: left,
                tail: left_tail,
                ..self
            };

            // Create the right split following the separator.
            let right = SplitProducer {
                data: right,
                tail: right_tail,
                ..self
            };

            (left, Some(right))
        } else {
            // The search is exhausted, no more separators...
            (SplitProducer { tail: 0, ..self }, None)
        }
    }

    fn fold_with<F>(self, folder: F) -> F
    where
        F: Folder<Self::Item>,
    {
        self.fold_with(folder, false)
    }
}