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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

//! 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, const INCL: bool = false> {
    data: V,
    separator: &'p P,

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

pub(super) type SplitInclusiveProducer<'p, P, V> = SplitProducer<'p, P, V, true>;

/// 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<const INCL: bool>(self, index: usize) -> (Self, Self);
    fn fold_splits<F, const INCL: bool>(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,
        }
    }
}

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

impl<'p, P, V, const INCL: bool> SplitProducer<'p, P, V, INCL>
where
    V: Fissile<P> + Send,
{
    /// 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::<F, INCL>(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::<INCL>(index);
            let folder = left.fold_splits::<F, INCL>(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, const INCL: bool> UnindexedProducer for SplitProducer<'p, P, V, INCL>
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::<INCL>(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)
    }
}