summaryrefslogtreecommitdiffstats
path: root/third_party/rust/itertools/benches/extra/zipslices.rs
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/itertools/benches/extra/zipslices.rs')
-rw-r--r--third_party/rust/itertools/benches/extra/zipslices.rs188
1 files changed, 188 insertions, 0 deletions
diff --git a/third_party/rust/itertools/benches/extra/zipslices.rs b/third_party/rust/itertools/benches/extra/zipslices.rs
new file mode 100644
index 0000000000..633be59068
--- /dev/null
+++ b/third_party/rust/itertools/benches/extra/zipslices.rs
@@ -0,0 +1,188 @@
+use std::cmp;
+
+// Note: There are different ways to implement ZipSlices.
+// This version performed the best in benchmarks.
+//
+// I also implemented a version with three pointers (tptr, tend, uptr),
+// that mimiced slice::Iter and only checked bounds by using tptr == tend,
+// but that was inferior to this solution.
+
+/// An iterator which iterates two slices simultaneously.
+///
+/// `ZipSlices` acts like a double-ended `.zip()` iterator.
+///
+/// It was intended to be more efficient than `.zip()`, and it was, then
+/// rustc changed how it optimizes so it can not promise improved performance
+/// at this time.
+///
+/// Note that elements past the end of the shortest of the two slices are ignored.
+///
+/// Iterator element type for `ZipSlices<T, U>` is `(T::Item, U::Item)`. For example,
+/// for a `ZipSlices<&'a [A], &'b mut [B]>`, the element type is `(&'a A, &'b mut B)`.
+#[derive(Clone)]
+pub struct ZipSlices<T, U> {
+ t: T,
+ u: U,
+ len: usize,
+ index: usize,
+}
+
+impl<'a, 'b, A, B> ZipSlices<&'a [A], &'b [B]> {
+ /// Create a new `ZipSlices` from slices `a` and `b`.
+ ///
+ /// Act like a double-ended `.zip()` iterator, but more efficiently.
+ ///
+ /// Note that elements past the end of the shortest of the two slices are ignored.
+ #[inline(always)]
+ pub fn new(a: &'a [A], b: &'b [B]) -> Self {
+ let minl = cmp::min(a.len(), b.len());
+ ZipSlices {
+ t: a,
+ u: b,
+ len: minl,
+ index: 0,
+ }
+ }
+}
+
+impl<T, U> ZipSlices<T, U>
+ where T: Slice,
+ U: Slice
+{
+ /// Create a new `ZipSlices` from slices `a` and `b`.
+ ///
+ /// Act like a double-ended `.zip()` iterator, but more efficiently.
+ ///
+ /// Note that elements past the end of the shortest of the two slices are ignored.
+ #[inline(always)]
+ pub fn from_slices(a: T, b: U) -> Self {
+ let minl = cmp::min(a.len(), b.len());
+ ZipSlices {
+ t: a,
+ u: b,
+ len: minl,
+ index: 0,
+ }
+ }
+}
+
+impl<T, U> Iterator for ZipSlices<T, U>
+ where T: Slice,
+ U: Slice
+{
+ type Item = (T::Item, U::Item);
+
+ #[inline(always)]
+ fn next(&mut self) -> Option<Self::Item> {
+ unsafe {
+ if self.index >= self.len {
+ None
+ } else {
+ let i = self.index;
+ self.index += 1;
+ Some((
+ self.t.get_unchecked(i),
+ self.u.get_unchecked(i)))
+ }
+ }
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ let len = self.len - self.index;
+ (len, Some(len))
+ }
+}
+
+impl<T, U> DoubleEndedIterator for ZipSlices<T, U>
+ where T: Slice,
+ U: Slice
+{
+ #[inline(always)]
+ fn next_back(&mut self) -> Option<Self::Item> {
+ unsafe {
+ if self.index >= self.len {
+ None
+ } else {
+ self.len -= 1;
+ let i = self.len;
+ Some((
+ self.t.get_unchecked(i),
+ self.u.get_unchecked(i)))
+ }
+ }
+ }
+}
+
+impl<T, U> ExactSizeIterator for ZipSlices<T, U>
+ where T: Slice,
+ U: Slice
+{}
+
+unsafe impl<T, U> Slice for ZipSlices<T, U>
+ where T: Slice,
+ U: Slice
+{
+ type Item = (T::Item, U::Item);
+
+ fn len(&self) -> usize {
+ self.len - self.index
+ }
+
+ unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
+ (self.t.get_unchecked(i),
+ self.u.get_unchecked(i))
+ }
+}
+
+/// A helper trait to let `ZipSlices` accept both `&[T]` and `&mut [T]`.
+///
+/// Unsafe trait because:
+///
+/// - Implementors must guarantee that `get_unchecked` is valid for all indices `0..len()`.
+pub unsafe trait Slice {
+ /// The type of a reference to the slice's elements
+ type Item;
+ #[doc(hidden)]
+ fn len(&self) -> usize;
+ #[doc(hidden)]
+ unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item;
+}
+
+unsafe impl<'a, T> Slice for &'a [T] {
+ type Item = &'a T;
+ #[inline(always)]
+ fn len(&self) -> usize { (**self).len() }
+ #[inline(always)]
+ unsafe fn get_unchecked(&mut self, i: usize) -> &'a T {
+ debug_assert!(i < self.len());
+ (**self).get_unchecked(i)
+ }
+}
+
+unsafe impl<'a, T> Slice for &'a mut [T] {
+ type Item = &'a mut T;
+ #[inline(always)]
+ fn len(&self) -> usize { (**self).len() }
+ #[inline(always)]
+ unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut T {
+ debug_assert!(i < self.len());
+ // override the lifetime constraints of &mut &'a mut [T]
+ (*(*self as *mut [T])).get_unchecked_mut(i)
+ }
+}
+
+#[test]
+fn zipslices() {
+
+ let xs = [1, 2, 3, 4, 5, 6];
+ let ys = [1, 2, 3, 7];
+ ::itertools::assert_equal(ZipSlices::new(&xs, &ys), xs.iter().zip(&ys));
+
+ let xs = [1, 2, 3, 4, 5, 6];
+ let mut ys = [0; 6];
+ for (x, y) in ZipSlices::from_slices(&xs[..], &mut ys[..]) {
+ *y = *x;
+ }
+ ::itertools::assert_equal(&xs, &ys);
+}