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

slice_group_by/exponential_group/
exponential_group_by_key.rs
