Revision control
Copy as Markdown
Other Tools
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);
}