slice_group_by/exponential_group/
exponential_group_by.rs

1use crate::{exponential_search_by, offset_from};
2use std::cmp::Ordering::{Greater, Less};
3use std::slice::{from_raw_parts, from_raw_parts_mut};
4use std::{fmt, marker};
5
6macro_rules! exponential_group_by {
7    (struct $name:ident, $elem:ty, $mkslice:ident) => {
8        impl<'a, T: 'a, P> $name<'a, T, P> {
9            #[inline]
10            pub fn is_empty(&self) -> bool {
11                self.ptr == self.end
12            }
13
14            #[inline]
15            pub fn remainder_len(&self) -> usize {
16                unsafe { offset_from(self.end, self.ptr) }
17            }
18        }
19
20        impl<'a, T: 'a, P> std::iter::Iterator for $name<'a, T, P>
21        where
22            P: FnMut(&T, &T) -> bool,
23        {
24            type Item = $elem;
25
26            fn next(&mut self) -> Option<Self::Item> {
27                if self.is_empty() {
28                    return None;
29                }
30
31                let first = unsafe { &*self.ptr };
32
33                let len = self.remainder_len();
34                let tail = unsafe { $mkslice(self.ptr.add(1), len - 1) };
35
36                let predicate = |x: &T| {
37                    if (self.predicate)(first, x) {
38                        Less
39                    } else {
40                        Greater
41                    }
42                };
43                let index = exponential_search_by(tail, predicate).unwrap_err();
44
45                let left = unsafe { $mkslice(self.ptr, index + 1) };
46                self.ptr = unsafe { self.ptr.add(index + 1) };
47
48                Some(left)
49            }
50
51            fn size_hint(&self) -> (usize, Option<usize>) {
52                if self.is_empty() {
53                    return (0, Some(0));
54                }
55
56                let len = self.remainder_len();
57                (1, Some(len))
58            }
59
60            fn last(mut self) -> Option<Self::Item> {
61                self.next_back()
62            }
63        }
64
65        impl<'a, T: 'a, P> std::iter::DoubleEndedIterator for $name<'a, T, P>
66        where
67            P: FnMut(&T, &T) -> bool,
68        {
69            fn next_back(&mut self) -> Option<Self::Item> {
70                if self.is_empty() {
71                    return None;
72                }
73
74                let last = unsafe { &*self.end.sub(1) };
75
76                let len = self.remainder_len();
77                let head = unsafe { $mkslice(self.ptr, len - 1) };
78
79                let predicate = |x: &T| {
80                    if (self.predicate)(last, x) {
81                        Greater
82                    } else {
83                        Less
84                    }
85                };
86                let index = exponential_search_by(head, predicate).unwrap_err();
87
88                let right = unsafe { $mkslice(self.ptr.add(index), len - index) };
89                self.end = unsafe { self.end.sub(len - index) };
90
91                Some(right)
92            }
93        }
94
95        impl<'a, T: 'a, P> std::iter::FusedIterator for $name<'a, T, P> where
96            P: FnMut(&T, &T) -> bool
97        {
98        }
99    };
100}
101
102/// An iterator that will reutrn non-overlapping groups in the slice using *exponential search*.
103///
104/// It will not necessarily gives contiguous elements to the predicate function.
105/// The predicate function should implement an order consistent with the sort order of the slice.
106pub struct ExponentialGroupBy<'a, T, P> {
107    ptr: *const T,
108    end: *const T,
109    predicate: P,
110    _phantom: marker::PhantomData<&'a T>,
111}
112
113impl<'a, T: 'a, P> ExponentialGroupBy<'a, T, P>
114where
115    P: FnMut(&T, &T) -> bool,
116{
117    pub fn new(slice: &'a [T], predicate: P) -> Self {
118        ExponentialGroupBy {
119            ptr: slice.as_ptr(),
120            end: unsafe { slice.as_ptr().add(slice.len()) },
121            predicate,
122            _phantom: marker::PhantomData,
123        }
124    }
125}
126
127impl<'a, T: 'a, P> ExponentialGroupBy<'a, T, P> {
128    /// Returns the remainder of the original slice that is going to be
129    /// returned by the iterator.
130    pub fn remainder(&self) -> &[T] {
131        let len = self.remainder_len();
132        unsafe { from_raw_parts(self.ptr, len) }
133    }
134}
135
136impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for ExponentialGroupBy<'a, T, P> {
137    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
138        f.debug_struct("ExponentialGroupBy")
139            .field("remainder", &self.remainder())
140            .finish()
141    }
142}
143
144exponential_group_by! { struct ExponentialGroupBy, &'a [T], from_raw_parts }
145
146/// An iterator that will reutrn non-overlapping *mutable* groups
147/// in the slice using *exponential search*.
148///
149/// It will not necessarily gives contiguous elements to the predicate function.
150/// The predicate function should implement an order consistent with the sort order of the slice.
151pub struct ExponentialGroupByMut<'a, T, P> {
152    ptr: *mut T,
153    end: *mut T,
154    predicate: P,
155    _phantom: marker::PhantomData<&'a mut T>,
156}
157
158impl<'a, T: 'a, P> ExponentialGroupByMut<'a, T, P>
159where
160    P: FnMut(&T, &T) -> bool,
161{
162    pub fn new(slice: &'a mut [T], predicate: P) -> Self {
163        let ptr = slice.as_mut_ptr();
164        let end = unsafe { ptr.add(slice.len()) };
165        ExponentialGroupByMut {
166            ptr,
167            end,
168            predicate,
169            _phantom: marker::PhantomData,
170        }
171    }
172}
173
174impl<'a, T: 'a, P> ExponentialGroupByMut<'a, T, P> {
175    /// Returns the remainder of the original slice that is going to be
176    /// returned by the iterator.
177    pub fn into_remainder(self) -> &'a mut [T] {
178        let len = self.remainder_len();
179        unsafe { from_raw_parts_mut(self.ptr, len) }
180    }
181}
182
183impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for ExponentialGroupByMut<'a, T, P> {
184    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
185        let len = self.remainder_len();
186        let remainder = unsafe { from_raw_parts(self.ptr, len) };
187
188        f.debug_struct("ExponentialGroupByMut")
189            .field("remaining", &remainder)
190            .finish()
191    }
192}
193
194exponential_group_by! { struct ExponentialGroupByMut, &'a mut [T], from_raw_parts_mut }
slice_group_by/exponential_group/exponential_group_by.rs

slice_group_by/exponential_group/
exponential_group_by.rs
