1 use std::cmp;
2
3 // Note: There are different ways to implement ZipSlices.
4 // This version performed the best in benchmarks.
5 //
6 // I also implemented a version with three pointes (tptr, tend, uptr),
7 // that mimiced slice::Iter and only checked bounds by using tptr == tend,
8 // but that was inferior to this solution.
9
10 /// An iterator which iterates two slices simultaneously.
11 ///
12 /// `ZipSlices` acts like a double-ended `.zip()` iterator.
13 ///
14 /// It was intended to be more efficient than `.zip()`, and it was, then
15 /// rustc changed how it optimizes so it can not promise improved performance
16 /// at this time.
17 ///
18 /// Note that elements past the end of the shortest of the two slices are ignored.
19 ///
20 /// Iterator element type for `ZipSlices<T, U>` is `(T::Item, U::Item)`. For example,
21 /// for a `ZipSlices<&'a [A], &'b mut [B]>`, the element type is `(&'a A, &'b mut B)`.
22 #[derive(Clone)]
23 pub struct ZipSlices<T, U> {
24 t: T,
25 u: U,
26 len: usize,
27 index: usize,
28 }
29
30 impl<'a, 'b, A, B> ZipSlices<&'a [A], &'b [B]> {
31 /// Create a new `ZipSlices` from slices `a` and `b`.
32 ///
33 /// Act like a double-ended `.zip()` iterator, but more efficiently.
34 ///
35 /// Note that elements past the end of the shortest of the two slices are ignored.
36 #[inline(always)]
new(a: &'a [A], b: &'b [B]) -> Self37 pub fn new(a: &'a [A], b: &'b [B]) -> Self {
38 let minl = cmp::min(a.len(), b.len());
39 ZipSlices {
40 t: a,
41 u: b,
42 len: minl,
43 index: 0,
44 }
45 }
46 }
47
48 impl<T, U> ZipSlices<T, U>
49 where T: Slice,
50 U: Slice
51 {
52 /// Create a new `ZipSlices` from slices `a` and `b`.
53 ///
54 /// Act like a double-ended `.zip()` iterator, but more efficiently.
55 ///
56 /// Note that elements past the end of the shortest of the two slices are ignored.
57 #[inline(always)]
from_slices(a: T, b: U) -> Self58 pub fn from_slices(a: T, b: U) -> Self {
59 let minl = cmp::min(a.len(), b.len());
60 ZipSlices {
61 t: a,
62 u: b,
63 len: minl,
64 index: 0,
65 }
66 }
67 }
68
69 impl<T, U> Iterator for ZipSlices<T, U>
70 where T: Slice,
71 U: Slice
72 {
73 type Item = (T::Item, U::Item);
74
75 #[inline(always)]
next(&mut self) -> Option<Self::Item>76 fn next(&mut self) -> Option<Self::Item> {
77 unsafe {
78 if self.index >= self.len {
79 None
80 } else {
81 let i = self.index;
82 self.index += 1;
83 Some((
84 self.t.get_unchecked(i),
85 self.u.get_unchecked(i)))
86 }
87 }
88 }
89
90 #[inline]
size_hint(&self) -> (usize, Option<usize>)91 fn size_hint(&self) -> (usize, Option<usize>) {
92 let len = self.len - self.index;
93 (len, Some(len))
94 }
95 }
96
97 impl<T, U> DoubleEndedIterator for ZipSlices<T, U>
98 where T: Slice,
99 U: Slice
100 {
101 #[inline(always)]
next_back(&mut self) -> Option<Self::Item>102 fn next_back(&mut self) -> Option<Self::Item> {
103 unsafe {
104 if self.index >= self.len {
105 None
106 } else {
107 self.len -= 1;
108 let i = self.len;
109 Some((
110 self.t.get_unchecked(i),
111 self.u.get_unchecked(i)))
112 }
113 }
114 }
115 }
116
117 impl<T, U> ExactSizeIterator for ZipSlices<T, U>
118 where T: Slice,
119 U: Slice
120 {}
121
122 unsafe impl<T, U> Slice for ZipSlices<T, U>
123 where T: Slice,
124 U: Slice
125 {
126 type Item = (T::Item, U::Item);
127
len(&self) -> usize128 fn len(&self) -> usize {
129 self.len - self.index
130 }
131
get_unchecked(&mut self, i: usize) -> Self::Item132 unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
133 (self.t.get_unchecked(i),
134 self.u.get_unchecked(i))
135 }
136 }
137
138 /// A helper trait to let `ZipSlices` accept both `&[T]` and `&mut [T]`.
139 ///
140 /// Unsafe trait because:
141 ///
142 /// - Implementors must guarantee that `get_unchecked` is valid for all indices `0..len()`.
143 pub unsafe trait Slice {
144 /// The type of a reference to the slice's elements
145 type Item;
146 #[doc(hidden)]
len(&self) -> usize147 fn len(&self) -> usize;
148 #[doc(hidden)]
get_unchecked(&mut self, i: usize) -> Self::Item149 unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item;
150 }
151
152 unsafe impl<'a, T> Slice for &'a [T] {
153 type Item = &'a T;
154 #[inline(always)]
len(&self) -> usize155 fn len(&self) -> usize { (**self).len() }
156 #[inline(always)]
get_unchecked(&mut self, i: usize) -> &'a T157 unsafe fn get_unchecked(&mut self, i: usize) -> &'a T {
158 debug_assert!(i < self.len());
159 (**self).get_unchecked(i)
160 }
161 }
162
163 unsafe impl<'a, T> Slice for &'a mut [T] {
164 type Item = &'a mut T;
165 #[inline(always)]
len(&self) -> usize166 fn len(&self) -> usize { (**self).len() }
167 #[inline(always)]
get_unchecked(&mut self, i: usize) -> &'a mut T168 unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut T {
169 debug_assert!(i < self.len());
170 // override the lifetime constraints of &mut &'a mut [T]
171 (*(*self as *mut [T])).get_unchecked_mut(i)
172 }
173 }
174
175 #[test]
zipslices()176 fn zipslices() {
177
178 let xs = [1, 2, 3, 4, 5, 6];
179 let ys = [1, 2, 3, 7];
180 ::itertools::assert_equal(ZipSlices::new(&xs, &ys), xs.iter().zip(&ys));
181
182 let xs = [1, 2, 3, 4, 5, 6];
183 let mut ys = [0; 6];
184 for (x, y) in ZipSlices::from_slices(&xs[..], &mut ys[..]) {
185 *y = *x;
186 }
187 ::itertools::assert_equal(&xs, &ys);
188 }
189