slice_group_by/linear_group/
linear_group_by.rs

1use std::iter::FusedIterator;
2use std::{mem, fmt, slice};
3
4unsafe fn split_at_unchecked<T>(slice: &[T], mid: usize) -> (&[T], &[T]) {
5    (slice.get_unchecked(..mid), slice.get_unchecked(mid..))
6}
7
8unsafe fn split_at_mut_unchecked<T>(slice: &mut [T], mid: usize) -> (&mut [T], &mut [T]) {
9    // split_at_mut_unchecked
10    let len = slice.len();
11    let ptr = slice.as_mut_ptr();
12
13    // SAFETY: Caller has to check that `0 <= mid <= slice.len()`.
14    //
15    // `[ptr; mid]` and `[mid; len]` are not overlapping, so returning a mutable reference
16    // is fine.
17    (slice::from_raw_parts_mut(ptr, mid), slice::from_raw_parts_mut(ptr.add(mid), len - mid))
18}
19
20pub struct LinearGroupBy<'a, T: 'a, P> {
21    slice: &'a [T],
22    predicate: P,
23}
24
25impl<'a, T: 'a, P> LinearGroupBy<'a, T, P> {
26    pub(crate) fn new(slice: &'a [T], predicate: P) -> Self {
27        LinearGroupBy { slice, predicate }
28    }
29}
30
31impl<'a, T: 'a, P> Iterator for LinearGroupBy<'a, T, P>
32where
33    P: FnMut(&T, &T) -> bool,
34{
35    type Item = &'a [T];
36
37    #[inline]
38    fn next(&mut self) -> Option<Self::Item> {
39        if self.slice.is_empty() {
40            None
41        } else {
42            let mut len = 1;
43            let mut iter = self.slice.windows(2);
44            while let Some([l, r]) = iter.next() {
45                if (self.predicate)(l, r) { len += 1 } else { break }
46            }
47            let (head, tail) = unsafe { split_at_unchecked(self.slice, len) };
48            self.slice = tail;
49            Some(head)
50        }
51    }
52
53    #[inline]
54    fn size_hint(&self) -> (usize, Option<usize>) {
55        if self.slice.is_empty() { (0, Some(0)) } else { (1, Some(self.slice.len())) }
56    }
57
58    #[inline]
59    fn last(mut self) -> Option<Self::Item> {
60        self.next_back()
61    }
62}
63
64impl<'a, T: 'a, P> DoubleEndedIterator for LinearGroupBy<'a, T, P>
65where
66    P: FnMut(&T, &T) -> bool,
67{
68    #[inline]
69    fn next_back(&mut self) -> Option<Self::Item> {
70        if self.slice.is_empty() {
71            None
72        } else {
73            let mut len = 1;
74            let mut iter = self.slice.windows(2);
75            while let Some([l, r]) = iter.next_back() {
76                if (self.predicate)(l, r) { len += 1 } else { break }
77            }
78            let (head, tail) = unsafe { split_at_unchecked(self.slice, self.slice.len() - len) };
79            self.slice = head;
80            Some(tail)
81        }
82    }
83}
84
85impl<'a, T: 'a, P> FusedIterator for LinearGroupBy<'a, T, P> where P: FnMut(&T, &T) -> bool {}
86
87impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for LinearGroupBy<'a, T, P> {
88    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
89        f.debug_struct("LinearGroupBy").field("slice", &self.slice).finish()
90    }
91}
92
93pub struct LinearGroupByMut<'a, T: 'a, P> {
94    slice: &'a mut [T],
95    predicate: P,
96}
97
98impl<'a, T: 'a, P> LinearGroupByMut<'a, T, P> {
99    pub(crate) fn new(slice: &'a mut [T], predicate: P) -> Self {
100        LinearGroupByMut { slice, predicate }
101    }
102}
103
104impl<'a, T: 'a, P> Iterator for LinearGroupByMut<'a, T, P>
105where
106    P: FnMut(&T, &T) -> bool,
107{
108    type Item = &'a mut [T];
109
110    #[inline]
111    fn next(&mut self) -> Option<Self::Item> {
112        if self.slice.is_empty() {
113            None
114        } else {
115            let mut len = 1;
116            let mut iter = self.slice.windows(2);
117            while let Some([l, r]) = iter.next() {
118                if (self.predicate)(l, r) { len += 1 } else { break }
119            }
120            let slice = mem::take(&mut self.slice);
121            let (head, tail) = unsafe { split_at_mut_unchecked(slice, len) };
122            self.slice = tail;
123            Some(head)
124        }
125    }
126
127    #[inline]
128    fn size_hint(&self) -> (usize, Option<usize>) {
129        if self.slice.is_empty() { (0, Some(0)) } else { (1, Some(self.slice.len())) }
130    }
131
132    #[inline]
133    fn last(mut self) -> Option<Self::Item> {
134        self.next_back()
135    }
136}
137
138impl<'a, T: 'a, P> DoubleEndedIterator for LinearGroupByMut<'a, T, P>
139where
140    P: FnMut(&T, &T) -> bool,
141{
142    #[inline]
143    fn next_back(&mut self) -> Option<Self::Item> {
144        if self.slice.is_empty() {
145            None
146        } else {
147            let mut len = 1;
148            let mut iter = self.slice.windows(2);
149            while let Some([l, r]) = iter.next_back() {
150                if (self.predicate)(l, r) { len += 1 } else { break }
151            }
152            let slice = mem::take(&mut self.slice);
153            let (head, tail) = unsafe { split_at_mut_unchecked(slice, slice.len() - len) };
154            self.slice = head;
155            Some(tail)
156        }
157    }
158}
159
160impl<'a, T: 'a, P> FusedIterator for LinearGroupByMut<'a, T, P> where P: FnMut(&T, &T) -> bool {}
161
162impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for LinearGroupByMut<'a, T, P> {
163    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
164        f.debug_struct("LinearGroupByMut").field("slice", &self.slice).finish()
165    }
166}
slice_group_by/linear_group/linear_group_by.rs

slice_group_by/linear_group/
linear_group_by.rs
