]>
Commit | Line | Data |
---|---|---|
c295e0f8 XL |
1 | use std::cmp; |
2 | ||
3 | // Note: There are different ways to implement ZipSlices. | |
4 | // This version performed the best in benchmarks. | |
5 | // | |
2b03887a | 6 | // I also implemented a version with three pointers (tptr, tend, uptr), |
c295e0f8 XL |
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)] | |
37 | 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)] | |
58 | 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)] | |
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] | |
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)] | |
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 | ||
128 | fn len(&self) -> usize { | |
129 | self.len - self.index | |
130 | } | |
131 | ||
132 | 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)] | |
147 | fn len(&self) -> usize; | |
148 | #[doc(hidden)] | |
149 | 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)] | |
155 | fn len(&self) -> usize { (**self).len() } | |
156 | #[inline(always)] | |
157 | 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)] | |
166 | fn len(&self) -> usize { (**self).len() } | |
167 | #[inline(always)] | |
168 | 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] | |
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 | } |