diff options
| -rw-r--r-- | library/alloc/tests/slice.rs | 39 | ||||
| -rw-r--r-- | library/core/src/slice/iter.rs | 238 | ||||
| -rw-r--r-- | library/core/src/slice/mod.rs | 14 |
3 files changed, 128 insertions, 163 deletions
diff --git a/library/alloc/tests/slice.rs b/library/alloc/tests/slice.rs index e2fdb5a6b5a..8f03a9240e2 100644 --- a/library/alloc/tests/slice.rs +++ b/library/alloc/tests/slice.rs @@ -1904,24 +1904,43 @@ fn test_group_by() { let slice = &[1, 1, 1, 3, 3, 2, 2, 2]; let mut iter = slice.group_by(|a, b| a == b); - assert_eq!(iter.next(), Some(&[1, 1, 1][..])); - - assert_eq!(iter.remaining(), &[3, 3, 2, 2, 2]); - assert_eq!(iter.next(), Some(&[3, 3][..])); assert_eq!(iter.next(), Some(&[2, 2, 2][..])); assert_eq!(iter.next(), None); -} - -#[test] -fn test_group_by_rev() { - let slice = &[1, 1, 1, 3, 3, 2, 2, 2]; let mut iter = slice.group_by(|a, b| a == b); - assert_eq!(iter.next_back(), Some(&[2, 2, 2][..])); assert_eq!(iter.next_back(), Some(&[3, 3][..])); assert_eq!(iter.next_back(), Some(&[1, 1, 1][..])); assert_eq!(iter.next_back(), None); + + let mut iter = slice.group_by(|a, b| a == b); + assert_eq!(iter.next(), Some(&[1, 1, 1][..])); + assert_eq!(iter.next_back(), Some(&[2, 2, 2][..])); + assert_eq!(iter.next(), Some(&[3, 3][..])); + assert_eq!(iter.next_back(), None); +} + +#[test] +fn test_group_by_mut() { + let slice = &mut [1, 1, 1, 3, 3, 2, 2, 2]; + + let mut iter = slice.group_by_mut(|a, b| a == b); + assert_eq!(iter.next(), Some(&mut [1, 1, 1][..])); + assert_eq!(iter.next(), Some(&mut [3, 3][..])); + assert_eq!(iter.next(), Some(&mut [2, 2, 2][..])); + assert_eq!(iter.next(), None); + + let mut iter = slice.group_by_mut(|a, b| a == b); + assert_eq!(iter.next_back(), Some(&mut [2, 2, 2][..])); + assert_eq!(iter.next_back(), Some(&mut [3, 3][..])); + assert_eq!(iter.next_back(), Some(&mut [1, 1, 1][..])); + assert_eq!(iter.next_back(), None); + + let mut iter = slice.group_by_mut(|a, b| a == b); + assert_eq!(iter.next(), Some(&mut [1, 1, 1][..])); + assert_eq!(iter.next_back(), Some(&mut [2, 2, 2][..])); + assert_eq!(iter.next(), Some(&mut [3, 3][..])); + assert_eq!(iter.next_back(), None); } diff --git a/library/core/src/slice/iter.rs b/library/core/src/slice/iter.rs index 917997f902a..8f52fa852ba 100644 --- a/library/core/src/slice/iter.rs +++ b/library/core/src/slice/iter.rs @@ -2968,127 +2968,6 @@ unsafe impl<'a, T> TrustedRandomAccess for IterMut<'a, T> { } } -macro_rules! group_by { - (struct $name:ident, $elem:ty, $mkslice:ident) => { - #[unstable(feature = "slice_group_by", issue = "0")] - impl<'a, T: 'a, P> $name<'a, T, P> { - #[inline] - fn is_empty(&self) -> bool { - self.ptr == self.end - } - - #[inline] - fn remaining_len(&self) -> usize { - unsafe { self.end.offset_from(self.ptr) as usize } - } - } - - #[unstable(feature = "slice_group_by", issue = "0")] - impl<'a, T: 'a, P> Iterator for $name<'a, T, P> - where P: FnMut(&T, &T) -> bool, - { - type Item = $elem; - - fn next(&mut self) -> Option<Self::Item> { - // we use an unsafe block to avoid bounds checking here. - // this is safe because the only thing we do here is to get - // two elements at `ptr` and `ptr + 1`, bounds checking is done by hand. - unsafe { - if self.is_empty() { return None } - - let mut i = 0; - let mut ptr = self.ptr; - - // we need to get *two* contiguous elements so we check that: - // - the first element is at the `end - 1` position because - // - the second one will be read from `ptr + 1` that must - // be lower or equal to `end` - while ptr != self.end.sub(1) { - let a = &*ptr; - ptr = ptr.add(1); - let b = &*ptr; - - i += 1; - - if !(self.predicate)(a, b) { - let slice = $mkslice(self.ptr, i); - self.ptr = ptr; - return Some(slice) - } - } - - // `i` is either `0` or the slice `length - 1` because either: - // - we have not entered the loop and so `i` is equal to `0` - // the slice length is necessarily `1` because we ensure it is not empty - // - we have entered the loop and we have not early returned - // so `i` is equal to the slice `length - 1` - let slice = $mkslice(self.ptr, i + 1); - self.ptr = self.end; - Some(slice) - } - } - - fn size_hint(&self) -> (usize, Option<usize>) { - if self.is_empty() { return (0, Some(0)) } - let len = self.remaining_len(); - (1, Some(len)) - } - - fn last(mut self) -> Option<Self::Item> { - self.next_back() - } - } - - #[unstable(feature = "slice_group_by", issue = "0")] - impl<'a, T: 'a, P> DoubleEndedIterator for $name<'a, T, P> - where P: FnMut(&T, &T) -> bool, - { - fn next_back(&mut self) -> Option<Self::Item> { - // during the loop we retrieve two elements at `ptr` and `ptr - 1`. - unsafe { - if self.is_empty() { return None } - - let mut i = 0; - // we ensure that the first element that will be read - // is not under `end` because `end` is out of bound. - let mut ptr = self.end.sub(1); - - while ptr != self.ptr { - // we first get `a` that is at the left of `ptr` - // then `b` that is under the `ptr` position. - let a = &*ptr.sub(1); - let b = &*ptr; - - i += 1; - - if !(self.predicate)(a, b) { - // the slice to return starts at the `ptr` position - // and `i` is the length of it. - let slice = $mkslice(ptr, i); - - // because `end` is always an invalid bound - // we use `ptr` as `end` for the future call to `next`. - self.end = ptr; - return Some(slice) - } - - ptr = ptr.sub(1); - } - - let slice = $mkslice(self.ptr, i + 1); - self.ptr = self.end; - Some(slice) - } - } - } - - #[unstable(feature = "slice_group_by", issue = "0")] - impl<'a, T: 'a, P> FusedIterator for $name<'a, T, P> - where P: FnMut(&T, &T) -> bool, - { } - } -} - /// An iterator over slice in (non-overlapping) chunks separated by a predicate. /// /// This struct is created by the [`group_by`] method on [slices]. @@ -3098,25 +2977,65 @@ macro_rules! group_by { #[unstable(feature = "slice_group_by", issue = "0")] #[derive(Debug)] // FIXME implement Debug to be more user friendly pub struct GroupBy<'a, T: 'a, P> { - ptr: *const T, - end: *const T, + slice: &'a [T], predicate: P, - _phantom: marker::PhantomData<&'a T>, } #[unstable(feature = "slice_group_by", issue = "0")] -impl<'a, T: 'a, P> GroupBy<'a, T, P> +impl<'a, T: 'a, P> GroupBy<'a, T, P> { + pub(super) fn new(slice: &'a [T], predicate: P) -> Self { + GroupBy { slice, predicate } + } +} + +#[unstable(feature = "slice_group_by", issue = "0")] +impl<'a, T: 'a, P> Iterator for GroupBy<'a, T, P> where P: FnMut(&T, &T) -> bool, { - /// Returns the remainder of the original slice that is going to be - /// returned by the iterator. - pub fn remaining(&self) -> &[T] { - let len = self.remaining_len(); - unsafe { from_raw_parts(self.ptr, len) } + type Item = &'a [T]; + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + if self.slice.is_empty() { + None + } else { + let mut len = 1; + let mut iter = self.slice.windows(2); + while let Some([l, r]) = iter.next() { + if (self.predicate)(l, r) { len += 1 } else { break } + } + let (head, tail) = self.slice.split_at(len); + self.slice = tail; + Some(head) + } } } -group_by!{ struct GroupBy, &'a [T], from_raw_parts } +#[unstable(feature = "slice_group_by", issue = "0")] +impl<'a, T: 'a, P> DoubleEndedIterator for GroupBy<'a, T, P> +where P: FnMut(&T, &T) -> bool, +{ + #[inline] + fn next_back(&mut self) -> Option<Self::Item> { + if self.slice.is_empty() { + None + } else { + let mut len = 1; + let mut iter = self.slice.windows(2); + while let Some([l, r]) = iter.next_back() { + if (self.predicate)(l, r) { len += 1 } else { break } + } + let (head, tail) = self.slice.split_at(self.slice.len() - len); + self.slice = head; + Some(tail) + } + } +} + +#[unstable(feature = "slice_group_by", issue = "0")] +impl<'a, T: 'a, P> FusedIterator for GroupBy<'a, T, P> +where P: FnMut(&T, &T) -> bool, +{ } /// An iterator over slice in (non-overlapping) mutable chunks separated /// by a predicate. @@ -3128,22 +3047,59 @@ group_by!{ struct GroupBy, &'a [T], from_raw_parts } #[unstable(feature = "slice_group_by", issue = "0")] #[derive(Debug)] // FIXME implement Debug to be more user friendly pub struct GroupByMut<'a, T: 'a, P> { - ptr: *mut T, - end: *mut T, + slice: &'a mut [T], predicate: P, - _phantom: marker::PhantomData<&'a T>, } #[unstable(feature = "slice_group_by", issue = "0")] -impl<'a, T: 'a, P> GroupByMut<'a, T, P> +impl<'a, T: 'a, P> GroupByMut<'a, T, P> { + pub(super) fn new(slice: &'a mut [T], predicate: P) -> Self { + GroupByMut { slice, predicate } + } +} + +#[unstable(feature = "slice_group_by", issue = "0")] +impl<'a, T: 'a, P> Iterator for GroupByMut<'a, T, P> where P: FnMut(&T, &T) -> bool, { - /// Returns the remainder of the original slice that is going to be - /// returned by the iterator. - pub fn into_remaining(self) -> &'a mut [T] { - let len = self.remaining_len(); - unsafe { from_raw_parts_mut(self.ptr, len) } + type Item = &'a mut [T]; + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + if self.slice.is_empty() { + None + } else { + let mut len = 1; + let mut iter = self.slice.windows(2); + while let Some([l, r]) = iter.next() { + if (self.predicate)(l, r) { len += 1 } else { break } + } + let slice = mem::take(&mut self.slice); + let (head, tail) = slice.split_at_mut(len); + self.slice = tail; + Some(head) + } } } -group_by!{ struct GroupByMut, &'a mut [T], from_raw_parts_mut } +#[unstable(feature = "slice_group_by", issue = "0")] +impl<'a, T: 'a, P> DoubleEndedIterator for GroupByMut<'a, T, P> +where P: FnMut(&T, &T) -> bool, +{ + #[inline] + fn next_back(&mut self) -> Option<Self::Item> { + if self.slice.is_empty() { + None + } else { + let mut len = 1; + let mut iter = self.slice.windows(2); + while let Some([l, r]) = iter.next_back() { + if (self.predicate)(l, r) { len += 1 } else { break } + } + let slice = mem::take(&mut self.slice); + let (head, tail) = slice.split_at_mut(slice.len() - len); + self.slice = head; + Some(tail) + } + } +} diff --git a/library/core/src/slice/mod.rs b/library/core/src/slice/mod.rs index e366baa34c6..2e304cc5d2e 100644 --- a/library/core/src/slice/mod.rs +++ b/library/core/src/slice/mod.rs @@ -1233,12 +1233,7 @@ impl<T> [T] { pub fn group_by<F>(&self, pred: F) -> GroupBy<T, F> where F: FnMut(&T, &T) -> bool { - GroupBy { - ptr: self.as_ptr(), - end: unsafe { self.as_ptr().add(self.len()) }, - predicate: pred, - _phantom: marker::PhantomData, - } + GroupBy::new(self, pred) } /// Returns an iterator over the slice producing non-overlapping mutable @@ -1267,12 +1262,7 @@ impl<T> [T] { pub fn group_by_mut<F>(&mut self, pred: F) -> GroupByMut<T, F> where F: FnMut(&T, &T) -> bool { - GroupByMut { - ptr: self.as_mut_ptr(), - end: unsafe { self.as_mut_ptr().add(self.len()) }, - predicate: pred, - _phantom: marker::PhantomData, - } + GroupByMut::new(self, pred) } /// Divides one slice into two at an index. |