1 //! Helper traits for sequences.
2
3 #![allow(dead_code)]
4
5 use crate::lib::{cmp, iter, marker, mem, ops, ptr, slice};
6 use arrayvec;
7
8 #[cfg(all(feature = "correct", feature = "radix"))]
9 use crate::lib::Vec;
10
11 // ARRVEC
12
13 /// Macro to automate simplify the creation of an ArrayVec.
14 #[macro_export]
15 macro_rules! arrvec {
16 // This only works if the ArrayVec is the same size as the input array.
17 ($elem:expr; $n:expr) => ({
18 $crate::arrayvec::ArrayVec::from([$elem; $n])
19 });
20 // This just repeatedly calls `push`. I don't believe there's a concise way to count the number of expressions.
21 ($($x:expr),*$(,)*) => ({
22 // Allow an unused mut variable, since if the sequence is empty,
23 // the vec will never be mutated.
24 #[allow(unused_mut)] {
25 let mut vec = $crate::arrayvec::ArrayVec::new();
26 $(vec.push($x);)*
27 vec
28 }
29 });
30 }
31
32 // INSERT MANY
33
34 /// Insert multiple elements at position `index`.
35 ///
36 /// Shifts all elements before index to the back of the iterator.
37 /// It uses size hints to try to minimize the number of moves,
38 /// however, it does not rely on them. We cannot internally allocate, so
39 /// if we overstep the lower_size_bound, we have to do extensive
40 /// moves to shift each item back incrementally.
41 ///
42 /// This implementation is adapted from [`smallvec`], which has a battle-tested
43 /// implementation that has been revised for at least a security advisory
44 /// warning. Smallvec is similarly licensed under an MIT/Apache dual license.
45 ///
46 /// [`smallvec`]: https://github.com/servo/rust-smallvec
insert_many<V, T, I>(vec: &mut V, index: usize, iterable: I) where V: VecLike<T>, I: iter::IntoIterator<Item=T>47 pub fn insert_many<V, T, I>(vec: &mut V, index: usize, iterable: I)
48 where V: VecLike<T>,
49 I: iter::IntoIterator<Item=T>
50 {
51 let mut iter = iterable.into_iter();
52 if index == vec.len() {
53 return vec.extend(iter);
54 }
55
56 let (lower_size_bound, _) = iter.size_hint();
57 assert!(lower_size_bound <= core::isize::MAX as usize); // Ensure offset is indexable
58 assert!(index + lower_size_bound >= index); // Protect against overflow
59
60 let mut num_added = 0;
61 let old_len = vec.len();
62 assert!(index <= old_len);
63
64 unsafe {
65 // Reserve space for `lower_size_bound` elements.
66 vec.reserve(lower_size_bound);
67 let start = vec.as_mut_ptr();
68 let ptr = start.add(index);
69
70 // Move the trailing elements.
71 ptr::copy(ptr, ptr.add(lower_size_bound), old_len - index);
72
73 // In case the iterator panics, don't double-drop the items we just copied above.
74 vec.set_len(0);
75 let mut guard = DropOnPanic {
76 start,
77 skip: index..(index + lower_size_bound),
78 len: old_len + lower_size_bound,
79 };
80
81 while num_added < lower_size_bound {
82 let element = match iter.next() {
83 Some(x) => x,
84 None => break,
85 };
86 let cur = ptr.add(num_added);
87 ptr::write(cur, element);
88 guard.skip.start += 1;
89 num_added += 1;
90 }
91
92 if num_added < lower_size_bound {
93 // Iterator provided fewer elements than the hint. Move the tail backward.
94 ptr::copy(
95 ptr.add(lower_size_bound),
96 ptr.add(num_added),
97 old_len - index,
98 );
99 }
100 // There are no more duplicate or uninitialized slots, so the guard is not needed.
101 vec.set_len(old_len + num_added);
102 mem::forget(guard);
103 }
104
105 // Insert any remaining elements one-by-one.
106 for element in iter {
107 vec.insert(index + num_added, element);
108 num_added += 1;
109 }
110
111 struct DropOnPanic<T> {
112 start: *mut T,
113 skip: ops::Range<usize>, // Space we copied-out-of, but haven't written-to yet.
114 len: usize,
115 }
116
117 impl<T> Drop for DropOnPanic<T> {
118 fn drop(&mut self) {
119 for i in 0..self.len {
120 if !self.skip.contains(&i) {
121 unsafe {
122 ptr::drop_in_place(self.start.add(i));
123 }
124 }
125 }
126 }
127 }
128 }
129
130 // REMOVE_MANY
131
132 /// Remove many elements from a vec-like container.
133 ///
134 /// Does not change the size of the vector, and may leak
135 /// if the destructor panics. **Must** call `set_len` after,
136 /// and ideally before (to 0).
remove_many<V, T, R>(vec: &mut V, range: R) where V: VecLike<T>, R: ops::RangeBounds<usize>137 fn remove_many<V, T, R>(vec: &mut V, range: R)
138 where V: VecLike<T>,
139 R: ops::RangeBounds<usize>
140 {
141 // Get the bounds on the items we're removing.
142 let len = vec.len();
143 let start = match range.start_bound() {
144 ops::Bound::Included(&n) => n,
145 ops::Bound::Excluded(&n) => n + 1,
146 ops::Bound::Unbounded => 0,
147 };
148 let end = match range.end_bound() {
149 ops::Bound::Included(&n) => n + 1,
150 ops::Bound::Excluded(&n) => n,
151 ops::Bound::Unbounded => len,
152 };
153 assert!(start <= end);
154 assert!(end <= len);
155
156 // Drop the existing items.
157 unsafe {
158 // Set len temporarily to the start, in case we panic on a drop.
159 // This means we leak memory, but we don't allow any double freeing,
160 // or use after-free.
161 vec.set_len(start);
162 // Iteratively drop the range.
163 let mut first = vec.as_mut_ptr().add(start);
164 let last = vec.as_mut_ptr().add(end);
165 while first < last {
166 ptr::drop_in_place(first);
167 first = first.add(1);
168 }
169
170 // Now we need to copy the end range into the buffer.
171 let count = len - end;
172 if count != 0 {
173 let src = vec.as_ptr().add(end);
174 let dst = vec.as_mut_ptr().add(start);
175 ptr::copy(src, dst, count);
176 }
177
178 // Set the proper length, now that we've moved items in.
179 vec.set_len(start + count);
180 }
181 }
182
183 // HELPERS
184 // -------
185
186 // RSLICE INDEX
187
188 /// A trait for reversed-indexing operations.
189 pub trait RSliceIndex<T: ?Sized> {
190 /// Output type for the index.
191 type Output: ?Sized;
192
193 /// Get reference to element or subslice.
rget(self, slc: &T) -> Option<&Self::Output>194 fn rget(self, slc: &T) -> Option<&Self::Output>;
195
196 /// Get mutable reference to element or subslice.
rget_mut(self, slc: &mut T) -> Option<&mut Self::Output>197 fn rget_mut(self, slc: &mut T) -> Option<&mut Self::Output>;
198
199 /// Get reference to element or subslice without bounds checking.
rget_unchecked(self, slc: &T) -> &Self::Output200 unsafe fn rget_unchecked(self, slc: &T) -> &Self::Output;
201
202 /// Get mutable reference to element or subslice without bounds checking.
rget_unchecked_mut(self, slc: &mut T) -> &mut Self::Output203 unsafe fn rget_unchecked_mut(self, slc: &mut T) -> &mut Self::Output;
204
205 /// Get reference to element or subslice, panic if out-of-bounds.
rindex(self, slc: &T) -> &Self::Output206 fn rindex(self, slc: &T) -> &Self::Output;
207
208 /// Get mutable reference to element or subslice, panic if out-of-bounds.
rindex_mut(self, slc: &mut T) -> &mut Self::Output209 fn rindex_mut(self, slc: &mut T) -> &mut Self::Output;
210 }
211
212 impl<T> RSliceIndex<[T]> for usize {
213 type Output = T;
214
215 #[inline]
rget(self, slc: &[T]) -> Option<&T>216 fn rget(self, slc: &[T]) -> Option<&T> {
217 let len = slc.len();
218 slc.get(len - self - 1)
219 }
220
221 #[inline]
rget_mut(self, slc: &mut [T]) -> Option<&mut T>222 fn rget_mut(self, slc: &mut [T]) -> Option<&mut T> {
223 let len = slc.len();
224 slc.get_mut(len - self - 1)
225 }
226
227 #[inline]
rget_unchecked(self, slc: &[T]) -> &T228 unsafe fn rget_unchecked(self, slc: &[T]) -> &T {
229 let len = slc.len();
230 slc.get_unchecked(len - self - 1)
231 }
232
233 #[inline]
rget_unchecked_mut(self, slc: &mut [T]) -> &mut T234 unsafe fn rget_unchecked_mut(self, slc: &mut [T]) -> &mut T {
235 let len = slc.len();
236 slc.get_unchecked_mut(len - self - 1)
237 }
238
239 #[inline]
rindex(self, slc: &[T]) -> &T240 fn rindex(self, slc: &[T]) -> &T {
241 let len = slc.len();
242 &(*slc)[len - self - 1]
243 }
244
245 #[inline]
rindex_mut(self, slc: &mut [T]) -> &mut T246 fn rindex_mut(self, slc: &mut [T]) -> &mut T {
247 let len = slc.len();
248 &mut (*slc)[len - self - 1]
249 }
250 }
251
252 /// REVERSE VIEW
253
254 /// Reverse, immutable view of a sequence.
255 pub struct ReverseView<'a, T: 'a> {
256 inner: &'a [T],
257 }
258
259 impl<'a, T> ops::Index<usize> for ReverseView<'a, T> {
260 type Output = T;
261
262 #[inline]
index(&self, index: usize) -> &T263 fn index(&self, index: usize) -> &T {
264 self.inner.rindex(index)
265 }
266 }
267
268 /// REVERSE VIEW MUT
269
270 /// Reverse, mutable view of a sequence.
271 pub struct ReverseViewMut<'a, T: 'a> {
272 inner: &'a mut [T],
273 }
274
275 impl<'a, T: 'a> ops::Index<usize> for ReverseViewMut<'a, T> {
276 type Output = T;
277
278 #[inline]
index(&self, index: usize) -> &T279 fn index(&self, index: usize) -> &T {
280 self.inner.rindex(index)
281 }
282 }
283
284 impl<'a, T: 'a> ops::IndexMut<usize> for ReverseViewMut<'a, T> {
285 #[inline]
index_mut(&mut self, index: usize) -> &mut T286 fn index_mut(&mut self, index: usize) -> &mut T {
287 self.inner.rindex_mut(index)
288 }
289 }
290
291 // SLICELIKE
292
293 /// Implied base trait for slice-like types.
294 ///
295 /// Used to provide specializations since it requires no generic function parameters.
296 pub trait SliceLikeImpl<T> {
297 // AS SLICE
298
299 /// Get slice of immutable elements.
as_slice(&self) -> &[T]300 fn as_slice(&self) -> &[T];
301
302 /// Get slice of mutable elements.
as_mut_slice(&mut self) -> &mut [T]303 fn as_mut_slice(&mut self) -> &mut [T];
304 }
305
306 impl<T> SliceLikeImpl<T> for [T] {
307 // AS SLICE
308
309 #[inline]
as_slice(&self) -> &[T]310 fn as_slice(&self) -> &[T] {
311 self
312 }
313
314 #[inline]
as_mut_slice(&mut self) -> &mut [T]315 fn as_mut_slice(&mut self) -> &mut [T] {
316 self
317 }
318 }
319
320 #[cfg(all(feature = "correct", feature = "radix"))]
321 impl<T> SliceLikeImpl<T> for Vec<T> {
322 // AS SLICE
323
324 #[inline]
as_slice(&self) -> &[T]325 fn as_slice(&self) -> &[T] {
326 Vec::as_slice(self)
327 }
328
329 #[inline]
as_mut_slice(&mut self) -> &mut [T]330 fn as_mut_slice(&mut self) -> &mut [T] {
331 Vec::as_mut_slice(self)
332 }
333 }
334
335 impl<A: arrayvec::Array> SliceLikeImpl<A::Item> for arrayvec::ArrayVec<A> {
336 // AS SLICE
337
338 #[inline]
as_slice(&self) -> &[A::Item]339 fn as_slice(&self) -> &[A::Item] {
340 arrayvec::ArrayVec::as_slice(self)
341 }
342
343 #[inline]
as_mut_slice(&mut self) -> &mut [A::Item]344 fn as_mut_slice(&mut self) -> &mut [A::Item] {
345 arrayvec::ArrayVec::as_mut_slice(self)
346 }
347 }
348
349 /// Collection that has a `contains()` method.
350 pub trait Contains<T: PartialEq> {
351 /// Check if slice contains element.
contains(&self, x: &T) -> bool352 fn contains(&self, x: &T) -> bool;
353 }
354
355 impl<T: PartialEq> Contains<T> for dyn SliceLikeImpl<T> {
356 #[inline]
contains(&self, x: &T) -> bool357 fn contains(&self, x: &T) -> bool {
358 <[T]>::contains(self.as_slice(), x)
359 }
360 }
361
362 /// Collection that has a `starts_with()` method.
363 pub trait StartsWith<T: PartialEq> {
364 /// Check if slice starts_with subslice.
starts_with(&self, x: &[T]) -> bool365 fn starts_with(&self, x: &[T]) -> bool;
366 }
367
368 impl<T: PartialEq> StartsWith<T> for dyn SliceLikeImpl<T> {
369 #[inline]
starts_with(&self, x: &[T]) -> bool370 fn starts_with(&self, x: &[T]) -> bool {
371 <[T]>::starts_with(self.as_slice(), x)
372 }
373 }
374
375 /// Collection that has a `ends_with()` method.
376 pub trait EndsWith<T: PartialEq> {
377 /// Check if slice ends_with subslice.
ends_with(&self, x: &[T]) -> bool378 fn ends_with(&self, x: &[T]) -> bool;
379 }
380
381 impl<T: PartialEq> EndsWith<T> for dyn SliceLikeImpl<T> {
382 #[inline]
ends_with(&self, x: &[T]) -> bool383 fn ends_with(&self, x: &[T]) -> bool {
384 <[T]>::ends_with(self.as_slice(), x)
385 }
386 }
387
388 /// Collection that has a `binary_search()` method.
389 pub trait BinarySearch<T: Ord> {
390 /// Perform binary search for value.
binary_search(&self, x: &T) -> Result<usize, usize>391 fn binary_search(&self, x: &T) -> Result<usize, usize>;
392 }
393
394 impl<T: Ord> BinarySearch<T> for dyn SliceLikeImpl<T> {
395 #[inline]
binary_search(&self, x: &T) -> Result<usize, usize>396 fn binary_search(&self, x: &T) -> Result<usize, usize> {
397 <[T]>::binary_search(self.as_slice(), x)
398 }
399 }
400
401 /// Collection that has a `sort()` method.
402 pub trait Sort<T: Ord> {
403 // TODO(ahuszagh) Currently bugged on no_std.
404 ///// Sort sequence.
405 //fn sort(&mut self);
406 }
407
408 impl<T: Ord> Sort<T> for dyn SliceLikeImpl<T> {
409 //
410 //#[inline]
411 //fn sort(&mut self) {
412 // <[T]>::sort(self.as_mut_slice())
413 //}
414 }
415
416 /// Collection that has a `sort_unstable()` method.
417 pub trait SortUnstable<T: Ord> {
418 /// Sort sequence without preserving order of equal elements.
sort_unstable(&mut self)419 fn sort_unstable(&mut self);
420 }
421
422 impl<T: Ord> SortUnstable<T> for dyn SliceLikeImpl<T> {
423 #[inline]
sort_unstable(&mut self)424 fn sort_unstable(&mut self) {
425 <[T]>::sort_unstable(self.as_mut_slice())
426 }
427 }
428
429 /// Collection that has a `clone_from_slice()` method.
430 pub trait CloneFromSlice<T: Clone> {
431 /// Clone items from src into self.
clone_from_slice(&mut self, src: &[T])432 fn clone_from_slice(&mut self, src: &[T]);
433 }
434
435 impl<T: Clone> CloneFromSlice<T> for dyn SliceLikeImpl<T> {
436 #[inline]
clone_from_slice(&mut self, src: &[T])437 fn clone_from_slice(&mut self, src: &[T]) {
438 <[T]>::clone_from_slice(self.as_mut_slice(), src)
439 }
440 }
441
442 /// Collection that has a `copy_from_slice()` method.
443 pub trait CopyFromSlice<T: Copy> {
444 /// Copy items from src into self.
copy_from_slice(&mut self, src: &[T])445 fn copy_from_slice(&mut self, src: &[T]);
446 }
447
448 impl<T: Copy> CopyFromSlice<T> for dyn SliceLikeImpl<T> {
449 #[inline]
copy_from_slice(&mut self, src: &[T])450 fn copy_from_slice(&mut self, src: &[T]) {
451 <[T]>::copy_from_slice(self.as_mut_slice(), src)
452 }
453 }
454
455 /// Slice-like container.
456 pub trait SliceLike<T>: SliceLikeImpl<T> {
457 // CORE
458 // ----
459
460 // GET
461
462 /// Get an immutable reference to item at index.
get<I: slice::SliceIndex<[T]>>(&self, index: I) -> Option<&I::Output>463 fn get<I: slice::SliceIndex<[T]>>(&self, index: I) -> Option<&I::Output>;
464
465 /// Get a mutable reference to item at index.
get_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> Option<&mut I::Output>466 fn get_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> Option<&mut I::Output>;
467
468 /// Get an immutable reference to item at index.
get_unchecked<I: slice::SliceIndex<[T]>>(&self, index: I) -> &I::Output469 unsafe fn get_unchecked<I: slice::SliceIndex<[T]>>(&self, index: I) -> &I::Output;
470
471 /// Get a mutable reference to item at index.
get_unchecked_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output472 unsafe fn get_unchecked_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output;
473
474 // INDEX
475
476 /// Get immutable element(s) via indexing.
index<I: slice::SliceIndex<[T]>>(&self, index: I) -> &I::Output477 fn index<I: slice::SliceIndex<[T]>>(&self, index: I) -> &I::Output;
478
479 /// Get mutable element(s) via indexing.
index_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output480 fn index_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output;
481
482 // RGET
483
484 /// Get reference to element or subslice.
rget<I: RSliceIndex<[T]>>(&self, index: I) -> Option<&I::Output>485 fn rget<I: RSliceIndex<[T]>>(&self, index: I) -> Option<&I::Output>;
486
487 /// Get mutable reference to element or subslice.
rget_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> Option<&mut I::Output>488 fn rget_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> Option<&mut I::Output>;
489
490 /// Get reference to element or subslice without bounds checking.
rget_unchecked<I: RSliceIndex<[T]>>(&self, index: I) -> &I::Output491 unsafe fn rget_unchecked<I: RSliceIndex<[T]>>(&self, index: I) -> &I::Output;
492
493 /// Get mutable reference to element or subslice without bounds checking.
rget_unchecked_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output494 unsafe fn rget_unchecked_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output;
495
496 // RINDEX
497
498 /// Get reference to element or subslice.
rindex<I: RSliceIndex<[T]>>(&self, index: I) -> &I::Output499 fn rindex<I: RSliceIndex<[T]>>(&self, index: I) -> &I::Output;
500
501 /// Get mutable reference to element or subslice.
rindex_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output502 fn rindex_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output;
503
504 // DERIVATIVE
505 // ----------
506
507 // AS PTR
508
509 /// Get pointer to start of contiguous collection.
510 #[inline]
as_ptr(&self) -> *const T511 fn as_ptr(&self) -> *const T {
512 <[T]>::as_ptr(self.as_slice())
513 }
514
515 /// Get mutable pointer to start of contiguous collection.
516 #[inline]
as_mut_ptr(&mut self) -> *mut T517 fn as_mut_ptr(&mut self) -> *mut T {
518 <[T]>::as_mut_ptr(self.as_mut_slice())
519 }
520
521 // BINARY SEARCH BY
522
523 /// Perform binary search with a predicate.
524 #[inline]
binary_search_by<F>(&self, func: F) -> Result<usize, usize> where F: FnMut(&T) -> cmp::Ordering525 fn binary_search_by<F>(&self, func: F)
526 -> Result<usize, usize>
527 where F: FnMut(&T) -> cmp::Ordering
528 {
529 <[T]>::binary_search_by(self.as_slice(), func)
530 }
531
532 /// Perform binary search by key with key extractor.
533 #[inline]
binary_search_by_key<K, F>(&self, key: &K, func: F) -> Result<usize, usize> where K: Ord, F: FnMut(&T) -> K534 fn binary_search_by_key<K, F>(&self, key: &K, func: F)
535 -> Result<usize, usize>
536 where K: Ord,
537 F: FnMut(&T) -> K
538 {
539 <[T]>::binary_search_by_key(self.as_slice(), key, func)
540 }
541
542 // CHUNKS
543
544 /// Get iterator over `size`-length immutable elements in sequence.
545 #[inline]
chunks(&self, size: usize) -> slice::Chunks<T>546 fn chunks(&self, size: usize) -> slice::Chunks<T> {
547 <[T]>::chunks(self.as_slice(), size)
548 }
549
550 /// Get iterator over `size`-length mutable elements in sequence.
551 #[inline]
chunks_mut(&mut self, size: usize) -> slice::ChunksMut<T>552 fn chunks_mut(&mut self, size: usize) -> slice::ChunksMut<T> {
553 <[T]>::chunks_mut(self.as_mut_slice(), size)
554 }
555
556 // CHUNKS EXACT
557 // Currently unused, restore and add default implementation if required
558 // later. Requires rustc >= 1.31.0.
559 //
560 // /// Get iterator over exactly `size`-length immutable elements in sequence.
561 // #[inline]
562 // fn chunks_exact(&self, size: usize) -> slice::ChunksExact<T> {
563 // <[T]>::chunks_exact(self.as_slice(), size)
564 // }
565 //
566 // /// Get iterator over exactly `size`-length mutable elements in sequence.
567 // #[inline]
568 // fn chunks_exact_mut(&mut self, size: usize) -> slice::ChunksExactMut<T> {
569 // <[T]>::chunks_exact_mut(self.as_mut_slice(), size)
570 // }
571
572 // FIRST
573
574 /// Get an immutable reference to the first item.
575 #[inline]
first(&self) -> Option<&T>576 fn first(&self) -> Option<&T> {
577 self.as_slice().get(0)
578 }
579
580 /// Get a mutable reference to the first item.
581 #[inline]
first_mut(&mut self) -> Option<&mut T>582 fn first_mut(&mut self) -> Option<&mut T> {
583 self.as_mut_slice().get_mut(0)
584 }
585
586 /// Get an immutable reference to the first item without bounds checking.
587 #[inline]
first_unchecked(&self) -> &T588 unsafe fn first_unchecked(&self) -> &T {
589 self.as_slice().get_unchecked(0)
590 }
591
592 /// Get a mutable reference to the first item without bounds checking.
593 #[inline]
first_unchecked_mut(&mut self) -> &mut T594 unsafe fn first_unchecked_mut(&mut self) -> &mut T {
595 self.as_mut_slice().get_unchecked_mut(0)
596 }
597
598 // ITER
599
600 /// Iterate over immutable elements in the collection.
601 #[inline]
iter(&self) -> slice::Iter<T>602 fn iter(&self) -> slice::Iter<T> {
603 <[T]>::iter(self.as_slice())
604 }
605
606 /// Iterate over mutable elements in the collection.
607 #[inline]
iter_mut(&mut self) -> slice::IterMut<T>608 fn iter_mut(&mut self) -> slice::IterMut<T> {
609 <[T]>::iter_mut(self.as_mut_slice())
610 }
611
612 // LAST
613
614 /// Get an immutable reference to the last item.
615 #[inline]
last(&self) -> Option<&T>616 fn last(&self) -> Option<&T> {
617 self.rget(0)
618 }
619
620 /// Get a mutable reference to the last item.
621 #[inline]
last_mut(&mut self) -> Option<&mut T>622 fn last_mut(&mut self) -> Option<&mut T> {
623 self.rget_mut(0)
624 }
625
626 /// Get an immutable reference to the last item without bounds checking.
627 #[inline]
last_unchecked(&self) -> &T628 unsafe fn last_unchecked(&self) -> &T {
629 debug_assert!(self.len() > 0);
630 self.rget_unchecked(0)
631 }
632
633 /// Get a mutable reference to the last item without bounds checking.
634 #[inline]
last_unchecked_mut(&mut self) -> &mut T635 unsafe fn last_unchecked_mut(&mut self) -> &mut T {
636 debug_assert!(self.len() > 0);
637 self.rget_unchecked_mut(0)
638 }
639
640 // LEN
641
642 /// Get if the collection is empty.
643 #[inline]
is_empty(&self) -> bool644 fn is_empty(&self) -> bool {
645 <[T]>::is_empty(self.as_slice())
646 }
647
648 /// Get the length of the collection.
649 #[inline]
len(&self) -> usize650 fn len(&self) -> usize {
651 <[T]>::len(self.as_slice())
652 }
653
654 // Currently unused, restore and add default implementation if required
655 // later. Requires rustc >= 1.31.0.
656 // // RCHUNKS
657 //
658 // /// Get iterator over `size`-length immutable elements in sequence.
659 // #[inline]
660 // fn rchunks(&self, size: usize) -> slice::RChunks<T> {
661 // <[T]>::rchunks(self.as_slice(), size)
662 // }
663 //
664 // /// Get iterator over `size`-length mutable elements in sequence.
665 // #[inline]
666 // fn rchunks_mut(&mut self, size: usize) -> slice::RChunksMut<T> {
667 // <[T]>::rchunks_mut(self.as_mut_slice(), size)
668 // }
669 //
670 // // RCHUNKS EXACT
671 //
672 // /// Get iterator over exactly `size`-length immutable elements in sequence.
673 // #[inline]
674 // fn rchunks_exact(&self, size: usize) -> slice::RChunksExact<T> {
675 // <[T]>::rchunks_exact(self.as_slice(), size)
676 // }
677 //
678 // /// Get iterator over exactly `size`-length mutable elements in sequence.
679 // #[inline]
680 // fn rchunks_exact_mut(&mut self, size: usize) -> slice::RChunksExactMut<T> {
681 // <[T]>::rchunks_exact_mut(self.as_mut_slice(), size)
682 // }
683
684 // REVERSE
685
686 /// Reverse elements in collection.
687 #[inline]
reverse(&mut self)688 fn reverse(&mut self) {
689 <[T]>::reverse(self.as_mut_slice())
690 }
691
692 // ROTATE
693
694 // Currently unused, restore and add default implementation if required
695 // later. Requires rustc >= 1.26.0.
696 // /// Rotate elements of slice left.
697 // #[inline]
698 // fn rotate_left(&mut self, mid: usize) {
699 // <[T]>::rotate_left(self.as_mut_slice(), mid)
700 // }
701 //
702 // /// Rotate elements of slice right.
703 // #[inline]
704 // fn rotate_right(&mut self, mid: usize) {
705 // <[T]>::rotate_right(self.as_mut_slice(), mid)
706 // }
707
708 // RSPLIT
709
710 // Currently unused, restore and add default implementation if required
711 // later. Requires rustc >= 1.27.0.
712 // /// Split on condition into immutable subslices, start from the back of the slice.
713 // #[inline]
714 // fn rsplit<F: FnMut(&T) -> bool>(&self, func: F) -> slice::RSplit<T, F> {
715 // <[T]>::rsplit(self.as_slice(), func)
716 // }
717 //
718 // /// Split on condition into mutable subslices, start from the back of the slice.
719 // #[inline]
720 // fn rsplit_mut<F: FnMut(&T) -> bool>(&mut self, func: F) -> slice::RSplitMut<T, F> {
721 // <[T]>::rsplit_mut(self.as_mut_slice(), func)
722 // }
723
724 // RSPLITN
725
726 /// `rsplit()` with n subslices.
727 #[inline]
rsplitn<F: FnMut(&T) -> bool>(&self, n: usize, func: F) -> slice::RSplitN<T, F>728 fn rsplitn<F: FnMut(&T) -> bool>(&self, n: usize, func: F) -> slice::RSplitN<T, F> {
729 <[T]>::rsplitn(self.as_slice(), n, func)
730 }
731
732 /// `rsplit_mut()` with n subslices.
733 #[inline]
rsplitn_mut<F: FnMut(&T) -> bool>(&mut self, n: usize, func: F) -> slice::RSplitNMut<T, F>734 fn rsplitn_mut<F: FnMut(&T) -> bool>(&mut self, n: usize, func: F) -> slice::RSplitNMut<T, F> {
735 <[T]>::rsplitn_mut(self.as_mut_slice(), n, func)
736 }
737
738 // SORT BY
739
740 /// Perform sort with a predicate.
741 #[inline]
sort_by<F>(&mut self, func: F) where F: FnMut(&T, &T) -> cmp::Ordering742 fn sort_by<F>(&mut self, func: F)
743 where F: FnMut(&T, &T) -> cmp::Ordering
744 {
745 <[T]>::sort_by(self.as_mut_slice(), func)
746 }
747
748 /// Perform sort by key with key extractor.
749 #[inline]
sort_by_key<K, F>(&mut self, func: F) where K: Ord, F: FnMut(&T) -> K750 fn sort_by_key<K, F>(&mut self, func: F)
751 where K: Ord,
752 F: FnMut(&T) -> K
753 {
754 <[T]>::sort_by_key(self.as_mut_slice(), func)
755 }
756
757 // SORT UNSTABLE BY
758
759 /// Perform untable sort with a predicate.
760 #[inline]
sort_unstable_by<F>(&mut self, func: F) where F: FnMut(&T, &T) -> cmp::Ordering761 fn sort_unstable_by<F>(&mut self, func: F)
762 where F: FnMut(&T, &T) -> cmp::Ordering
763 {
764 <[T]>::sort_unstable_by(self.as_mut_slice(), func)
765 }
766
767 /// Perform untable sort by key with key extractor.
768 #[inline]
sort_unstable_by_key<K, F>(&mut self, func: F) where K: Ord, F: FnMut(&T) -> K769 fn sort_unstable_by_key<K, F>(&mut self, func: F)
770 where K: Ord,
771 F: FnMut(&T) -> K
772 {
773 <[T]>::sort_unstable_by_key(self.as_mut_slice(), func)
774 }
775
776 // SPLIT
777
778 /// Split on condition into immutable subslices, start from the front of the slice.
779 #[inline]
split<F: FnMut(&T) -> bool>(&self, func: F) -> slice::Split<T, F>780 fn split<F: FnMut(&T) -> bool>(&self, func: F) -> slice::Split<T, F> {
781 <[T]>::split(self.as_slice(), func)
782 }
783
784 /// Split on condition into mutable subslices, start from the front of the slice.
785 #[inline]
split_mut<F: FnMut(&T) -> bool>(&mut self, func: F) -> slice::SplitMut<T, F>786 fn split_mut<F: FnMut(&T) -> bool>(&mut self, func: F) -> slice::SplitMut<T, F> {
787 <[T]>::split_mut(self.as_mut_slice(), func)
788 }
789
790 // SPLIT AT
791
792 /// Split at index, return immutable values for the values before and after.
793 #[inline]
split_at(&self, index: usize) -> (&[T], &[T])794 fn split_at(&self, index: usize) -> (&[T], &[T]) {
795 <[T]>::split_at(self.as_slice(), index)
796 }
797
798 /// Split at index, return immutable values for the values before and after.
799 #[inline]
split_at_mut(&mut self, index: usize) -> (&mut [T], &mut [T])800 fn split_at_mut(&mut self, index: usize) -> (&mut [T], &mut [T]) {
801 <[T]>::split_at_mut(self.as_mut_slice(), index)
802 }
803
804 // SPLIT FIRST
805
806 /// Split at first item, returning values or None if empty.
807 #[inline]
split_first(&self) -> Option<(&T, &[T])>808 fn split_first(&self) -> Option<(&T, &[T])> {
809 <[T]>::split_first(self.as_slice())
810 }
811
812 /// Split at first item, returning values or None if empty.
813 #[inline]
split_first_mut(&mut self) -> Option<(&mut T, &mut [T])>814 fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> {
815 <[T]>::split_first_mut(self.as_mut_slice())
816 }
817
818 // SPLIT LAST
819
820 /// Split at last item, returning values or None if empty.
821 #[inline]
split_last(&self) -> Option<(&T, &[T])>822 fn split_last(&self) -> Option<(&T, &[T])> {
823 <[T]>::split_last(self.as_slice())
824 }
825
826 /// Split at last item, returning values or None if empty.
827 #[inline]
split_last_mut(&mut self) -> Option<(&mut T, &mut [T])>828 fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> {
829 <[T]>::split_last_mut(self.as_mut_slice())
830 }
831
832 // SPLIT N
833
834 /// `split()` with n subslices.
835 #[inline]
splitn<F: FnMut(&T) -> bool>(&self, n: usize, func: F) -> slice::SplitN<T, F>836 fn splitn<F: FnMut(&T) -> bool>(&self, n: usize, func: F) -> slice::SplitN<T, F> {
837 <[T]>::splitn(self.as_slice(), n, func)
838 }
839
840 /// `split_mut()` with n subslices.
841 #[inline]
splitn_mut<F: FnMut(&T) -> bool>(&mut self, n: usize, func: F) -> slice::SplitNMut<T, F>842 fn splitn_mut<F: FnMut(&T) -> bool>(&mut self, n: usize, func: F) -> slice::SplitNMut<T, F> {
843 <[T]>::splitn_mut(self.as_mut_slice(), n, func)
844 }
845
846 // SWAP
847
848 /// Swap two elements in the container by index.
849 #[inline]
swap(&mut self, x: usize, y: usize)850 fn swap(&mut self, x: usize, y: usize) {
851 <[T]>::swap(self.as_mut_slice(), x, y)
852 }
853
854 /// Swap all elements in `self` with `other`.
855 #[inline]
swap_with_slice(&mut self, other: &mut [T])856 fn swap_with_slice(&mut self, other: &mut [T]) {
857 <[T]>::swap_with_slice(self.as_mut_slice(), other)
858 }
859
860 // WINDOWS
861
862 /// View windows of `n`-length contiguous subslices.
863 #[inline]
windows(&self, size: usize) -> slice::Windows<T>864 fn windows(&self, size: usize) -> slice::Windows<T> {
865 <[T]>::windows(self.as_slice(), size)
866 }
867
868 // RVIEW
869
870 /// Create a reverse view of the vector for indexing.
871 #[inline]
rview<'a>(&'a self) -> ReverseView<'a, T>872 fn rview<'a>(&'a self) -> ReverseView<'a, T> {
873 ReverseView { inner: self.as_slice() }
874 }
875
876 /// Create a reverse, mutable view of the vector for indexing.
877 #[inline]
rview_mut<'a>(&'a mut self) -> ReverseViewMut<'a, T>878 fn rview_mut<'a>(&'a mut self) -> ReverseViewMut<'a, T> {
879 ReverseViewMut { inner: self.as_mut_slice() }
880 }
881 }
882
883 impl<T> SliceLike<T> for [T] {
884 // GET
885
886 /// Get an immutable reference to item at index.
887 #[inline]
get<I: slice::SliceIndex<[T]>>(&self, index: I) -> Option<&I::Output>888 fn get<I: slice::SliceIndex<[T]>>(&self, index: I) -> Option<&I::Output> {
889 return <[T]>::get(self, index);
890 }
891
892 /// Get an mutable reference to item at index.
893 #[inline]
get_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> Option<&mut I::Output>894 fn get_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> Option<&mut I::Output> {
895 return <[T]>::get_mut(self, index);
896 }
897
898 /// Get an immutable reference to item at index.
899 #[inline]
get_unchecked<I: slice::SliceIndex<[T]>>(&self, index: I) -> &I::Output900 unsafe fn get_unchecked<I: slice::SliceIndex<[T]>>(&self, index: I) -> &I::Output {
901 return <[T]>::get_unchecked(self, index);
902 }
903
904 /// Get an mutable reference to item at index.
905 #[inline]
get_unchecked_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output906 unsafe fn get_unchecked_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output {
907 return <[T]>::get_unchecked_mut(self, index);
908 }
909
910 // INDEX
911
912 #[inline]
index<I: slice::SliceIndex<[T]>>(&self, index: I) -> &I::Output913 fn index<I: slice::SliceIndex<[T]>>(&self, index: I) -> &I::Output {
914 return <[T] as ops::Index<I>>::index(self, index);
915 }
916
917 #[inline]
index_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output918 fn index_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output {
919 return <[T] as ops::IndexMut<I>>::index_mut(self, index);
920 }
921
922 // RGET
923
924 #[inline]
rget<I: RSliceIndex<[T]>>(&self, index: I) -> Option<&I::Output>925 fn rget<I: RSliceIndex<[T]>>(&self, index: I)
926 -> Option<&I::Output>
927 {
928 index.rget(self)
929 }
930
931 #[inline]
rget_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> Option<&mut I::Output>932 fn rget_mut<I: RSliceIndex<[T]>>(&mut self, index: I)
933 -> Option<&mut I::Output>
934 {
935 index.rget_mut(self)
936 }
937
938 #[inline]
rget_unchecked<I: RSliceIndex<[T]>>(&self, index: I) -> &I::Output939 unsafe fn rget_unchecked<I: RSliceIndex<[T]>>(&self, index: I)
940 -> &I::Output
941 {
942 index.rget_unchecked(self)
943 }
944
945 #[inline]
rget_unchecked_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output946 unsafe fn rget_unchecked_mut<I: RSliceIndex<[T]>>(&mut self, index: I)
947 -> &mut I::Output
948 {
949 index.rget_unchecked_mut(self)
950 }
951
952 // RINDEX
953
954 #[inline]
rindex<I: RSliceIndex<[T]>>(&self, index: I) -> &I::Output955 fn rindex<I: RSliceIndex<[T]>>(&self, index: I) -> &I::Output {
956 index.rindex(self)
957 }
958
959 #[inline]
rindex_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output960 fn rindex_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output {
961 index.rindex_mut(self)
962 }
963 }
964
965 #[cfg(all(feature = "correct", feature = "radix"))]
966 impl<T> SliceLike<T> for Vec<T> {
967 // GET
968
969 /// Get an immutable reference to item at index.
970 #[inline]
get<I: slice::SliceIndex<[T]>>(&self, index: I) -> Option<&I::Output>971 fn get<I: slice::SliceIndex<[T]>>(&self, index: I) -> Option<&I::Output> {
972 return self.as_slice().get(index);
973 }
974
975 /// Get an mutable reference to item at index.
976 #[inline]
get_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> Option<&mut I::Output>977 fn get_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> Option<&mut I::Output> {
978 return self.as_mut_slice().get_mut(index);
979 }
980
981 /// Get an immutable reference to item at index.
982 #[inline]
get_unchecked<I: slice::SliceIndex<[T]>>(&self, index: I) -> &I::Output983 unsafe fn get_unchecked<I: slice::SliceIndex<[T]>>(&self, index: I) -> &I::Output {
984 return self.as_slice().get_unchecked(index);
985 }
986
987 /// Get an mutable reference to item at index.
988 #[inline]
get_unchecked_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output989 unsafe fn get_unchecked_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output {
990 return self.as_mut_slice().get_unchecked_mut(index);
991 }
992
993 // INDEX
994
995 #[inline]
index<I: slice::SliceIndex<[T]>>(&self, index: I) -> &I::Output996 fn index<I: slice::SliceIndex<[T]>>(&self, index: I) -> &I::Output {
997 return self.as_slice().index(index);
998 }
999
1000 #[inline]
index_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output1001 fn index_mut<I: slice::SliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output {
1002 return self.as_mut_slice().index_mut(index);
1003 }
1004
1005 // RGET
1006
1007 #[inline]
rget<I: RSliceIndex<[T]>>(&self, index: I) -> Option<&I::Output>1008 fn rget<I: RSliceIndex<[T]>>(&self, index: I)
1009 -> Option<&I::Output>
1010 {
1011 index.rget(self.as_slice())
1012 }
1013
1014 #[inline]
rget_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> Option<&mut I::Output>1015 fn rget_mut<I: RSliceIndex<[T]>>(&mut self, index: I)
1016 -> Option<&mut I::Output>
1017 {
1018 index.rget_mut(self.as_mut_slice())
1019 }
1020
1021 #[inline]
rget_unchecked<I: RSliceIndex<[T]>>(&self, index: I) -> &I::Output1022 unsafe fn rget_unchecked<I: RSliceIndex<[T]>>(&self, index: I)
1023 -> &I::Output
1024 {
1025 index.rget_unchecked(self.as_slice())
1026 }
1027
1028 #[inline]
rget_unchecked_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output1029 unsafe fn rget_unchecked_mut<I: RSliceIndex<[T]>>(&mut self, index: I)
1030 -> &mut I::Output
1031 {
1032 index.rget_unchecked_mut(self.as_mut_slice())
1033 }
1034
1035 // RINDEX
1036
1037 #[inline]
rindex<I: RSliceIndex<[T]>>(&self, index: I) -> &I::Output1038 fn rindex<I: RSliceIndex<[T]>>(&self, index: I) -> &I::Output {
1039 index.rindex(self.as_slice())
1040 }
1041
1042 #[inline]
rindex_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output1043 fn rindex_mut<I: RSliceIndex<[T]>>(&mut self, index: I) -> &mut I::Output {
1044 index.rindex_mut(self.as_mut_slice())
1045 }
1046 }
1047
1048 impl<A: arrayvec::Array> SliceLike<A::Item> for arrayvec::ArrayVec<A> {
1049 // GET
1050
1051 /// Get an immutable reference to item at index.
1052 #[inline]
get<I: slice::SliceIndex<[A::Item]>>(&self, index: I) -> Option<&I::Output>1053 fn get<I: slice::SliceIndex<[A::Item]>>(&self, index: I) -> Option<&I::Output> {
1054 return self.as_slice().get(index);
1055 }
1056
1057 /// Get an mutable reference to item at index.
1058 #[inline]
get_mut<I: slice::SliceIndex<[A::Item]>>(&mut self, index: I) -> Option<&mut I::Output>1059 fn get_mut<I: slice::SliceIndex<[A::Item]>>(&mut self, index: I) -> Option<&mut I::Output> {
1060 return self.as_mut_slice().get_mut(index);
1061 }
1062
1063 /// Get an immutable reference to item at index.
1064 #[inline]
get_unchecked<I: slice::SliceIndex<[A::Item]>>(&self, index: I) -> &I::Output1065 unsafe fn get_unchecked<I: slice::SliceIndex<[A::Item]>>(&self, index: I) -> &I::Output {
1066 return self.as_slice().get_unchecked(index);
1067 }
1068
1069 /// Get an mutable reference to item at index.
1070 #[inline]
get_unchecked_mut<I: slice::SliceIndex<[A::Item]>>(&mut self, index: I) -> &mut I::Output1071 unsafe fn get_unchecked_mut<I: slice::SliceIndex<[A::Item]>>(&mut self, index: I) -> &mut I::Output {
1072 return self.as_mut_slice().get_unchecked_mut(index);
1073 }
1074
1075 // INDEX
1076
1077 #[inline]
index<I: slice::SliceIndex<[A::Item]>>(&self, index: I) -> &I::Output1078 fn index<I: slice::SliceIndex<[A::Item]>>(&self, index: I) -> &I::Output {
1079 return self.as_slice().index(index);
1080 }
1081
1082 #[inline]
index_mut<I: slice::SliceIndex<[A::Item]>>(&mut self, index: I) -> &mut I::Output1083 fn index_mut<I: slice::SliceIndex<[A::Item]>>(&mut self, index: I) -> &mut I::Output {
1084 return self.as_mut_slice().index_mut(index);
1085 }
1086
1087 // RGET
1088
1089 #[inline]
rget<I: RSliceIndex<[A::Item]>>(&self, index: I) -> Option<&I::Output>1090 fn rget<I: RSliceIndex<[A::Item]>>(&self, index: I)
1091 -> Option<&I::Output>
1092 {
1093 index.rget(self.as_slice())
1094 }
1095
1096 #[inline]
rget_mut<I: RSliceIndex<[A::Item]>>(&mut self, index: I) -> Option<&mut I::Output>1097 fn rget_mut<I: RSliceIndex<[A::Item]>>(&mut self, index: I)
1098 -> Option<&mut I::Output>
1099 {
1100 index.rget_mut(self.as_mut_slice())
1101 }
1102
1103 #[inline]
rget_unchecked<I: RSliceIndex<[A::Item]>>(&self, index: I) -> &I::Output1104 unsafe fn rget_unchecked<I: RSliceIndex<[A::Item]>>(&self, index: I)
1105 -> &I::Output
1106 {
1107 index.rget_unchecked(self.as_slice())
1108 }
1109
1110 #[inline]
rget_unchecked_mut<I: RSliceIndex<[A::Item]>>(&mut self, index: I) -> &mut I::Output1111 unsafe fn rget_unchecked_mut<I: RSliceIndex<[A::Item]>>(&mut self, index: I)
1112 -> &mut I::Output
1113 {
1114 index.rget_unchecked_mut(self.as_mut_slice())
1115 }
1116
1117 // RINDEX
1118
1119 #[inline]
rindex<I: RSliceIndex<[A::Item]>>(&self, index: I) -> &I::Output1120 fn rindex<I: RSliceIndex<[A::Item]>>(&self, index: I) -> &I::Output {
1121 index.rindex(self.as_slice())
1122 }
1123
1124 #[inline]
rindex_mut<I: RSliceIndex<[A::Item]>>(&mut self, index: I) -> &mut I::Output1125 fn rindex_mut<I: RSliceIndex<[A::Item]>>(&mut self, index: I) -> &mut I::Output {
1126 index.rindex_mut(self.as_mut_slice())
1127 }
1128 }
1129
1130 // VECTOR
1131 // ------
1132
1133 // VECLIKE
1134
1135 /// Vector-like container.
1136 pub trait VecLike<T>:
1137 Default +
1138 iter::FromIterator<T> +
1139 iter::IntoIterator +
1140 ops::DerefMut<Target = [T]> +
1141 Extend<T> +
1142 SliceLike<T>
1143 {
1144 /// Create new, empty vector.
new() -> Self1145 fn new() -> Self;
1146
1147 /// Create new, empty vector with preallocated, uninitialized storage.
with_capacity(capacity: usize) -> Self1148 fn with_capacity(capacity: usize) -> Self;
1149
1150 /// Get the capacity of the underlying storage.
capacity(&self) -> usize1151 fn capacity(&self) -> usize;
1152
1153 /// Reserve additional capacity for the collection.
reserve(&mut self, capacity: usize)1154 fn reserve(&mut self, capacity: usize);
1155
1156 /// Reserve minimal additional capacity for the collection.
reserve_exact(&mut self, additional: usize)1157 fn reserve_exact(&mut self, additional: usize);
1158
1159 /// Shrink capacity to fit data size.
shrink_to_fit(&mut self)1160 fn shrink_to_fit(&mut self);
1161
1162 /// Truncate vector to new length, dropping any items after `len`.
truncate(&mut self, len: usize)1163 fn truncate(&mut self, len: usize);
1164
1165 /// Set the buffer length (unsafe).
set_len(&mut self, new_len: usize)1166 unsafe fn set_len(&mut self, new_len: usize);
1167
1168 /// Remove element from vector and return it, replacing it with the last item in the vector.
swap_remove(&mut self, index: usize) -> T1169 fn swap_remove(&mut self, index: usize) -> T;
1170
1171 /// Insert element at index, shifting all elements after.
insert(&mut self, index: usize, element: T)1172 fn insert(&mut self, index: usize, element: T);
1173
1174 /// Remove element from vector at index, shifting all elements after.
remove(&mut self, index: usize) -> T1175 fn remove(&mut self, index: usize) -> T;
1176
1177 /// Append an element to the vector.
push(&mut self, value: T)1178 fn push(&mut self, value: T);
1179
1180 /// Pop an element from the end of the vector.
pop(&mut self) -> Option<T>1181 fn pop(&mut self) -> Option<T>;
1182
1183 /// Clear the buffer
clear(&mut self)1184 fn clear(&mut self);
1185
1186 /// Insert many elements at index, pushing everything else to the back.
insert_many<I: iter::IntoIterator<Item=T>>(&mut self, index: usize, iterable: I)1187 fn insert_many<I: iter::IntoIterator<Item=T>>(&mut self, index: usize, iterable: I);
1188
1189 /// Remove many elements from range.
remove_many<R: ops::RangeBounds<usize>>(&mut self, range: R)1190 fn remove_many<R: ops::RangeBounds<usize>>(&mut self, range: R);
1191 }
1192
1193 #[cfg(all(feature = "correct", feature = "radix"))]
1194 impl<T> VecLike<T> for Vec<T> {
1195 #[inline]
new() -> Vec<T>1196 fn new() -> Vec<T> {
1197 Vec::new()
1198 }
1199
1200 #[inline]
with_capacity(capacity: usize) -> Vec<T>1201 fn with_capacity(capacity: usize) -> Vec<T> {
1202 Vec::with_capacity(capacity)
1203 }
1204
1205 #[inline]
capacity(&self) -> usize1206 fn capacity(&self) -> usize {
1207 Vec::capacity(self)
1208 }
1209
1210 #[inline]
reserve(&mut self, capacity: usize)1211 fn reserve(&mut self, capacity: usize) {
1212 Vec::reserve(self, capacity)
1213 }
1214
1215 #[inline]
reserve_exact(&mut self, capacity: usize)1216 fn reserve_exact(&mut self, capacity: usize) {
1217 Vec::reserve_exact(self, capacity)
1218 }
1219
1220 #[inline]
shrink_to_fit(&mut self)1221 fn shrink_to_fit(&mut self) {
1222 Vec::shrink_to_fit(self)
1223 }
1224
1225 #[inline]
truncate(&mut self, len: usize)1226 fn truncate(&mut self, len: usize) {
1227 Vec::truncate(self, len)
1228 }
1229
1230 #[inline]
set_len(&mut self, new_len: usize)1231 unsafe fn set_len(&mut self, new_len: usize) {
1232 Vec::set_len(self, new_len);
1233 }
1234
1235 #[inline]
swap_remove(&mut self, index: usize) -> T1236 fn swap_remove(&mut self, index: usize) -> T {
1237 Vec::swap_remove(self, index)
1238 }
1239
1240 #[inline]
insert(&mut self, index: usize, element: T)1241 fn insert(&mut self, index: usize, element: T) {
1242 Vec::insert(self, index, element)
1243 }
1244
1245 #[inline]
remove(&mut self, index: usize) -> T1246 fn remove(&mut self, index: usize) -> T {
1247 Vec::remove(self, index)
1248 }
1249
1250 #[inline]
push(&mut self, value: T)1251 fn push(&mut self, value: T) {
1252 Vec::push(self, value);
1253 }
1254
1255 #[inline]
pop(&mut self) -> Option<T>1256 fn pop(&mut self) -> Option<T> {
1257 Vec::pop(self)
1258 }
1259
1260 #[inline]
clear(&mut self)1261 fn clear(&mut self) {
1262 Vec::clear(self);
1263 }
1264
1265 #[inline]
insert_many<I: iter::IntoIterator<Item=T>>(&mut self, index: usize, iterable: I)1266 fn insert_many<I: iter::IntoIterator<Item=T>>(&mut self, index: usize, iterable: I) {
1267 self.splice(index..index, iterable);
1268 }
1269
1270 #[inline]
remove_many<R: ops::RangeBounds<usize>>(&mut self, range: R)1271 fn remove_many<R: ops::RangeBounds<usize>>(&mut self, range: R) {
1272 remove_many(self, range)
1273 }
1274 }
1275
1276 impl<A: arrayvec::Array> VecLike<A::Item> for arrayvec::ArrayVec<A> {
1277 #[inline]
new() -> arrayvec::ArrayVec<A>1278 fn new() -> arrayvec::ArrayVec<A> {
1279 arrayvec::ArrayVec::new()
1280 }
1281
1282 #[inline]
with_capacity(capacity: usize) -> arrayvec::ArrayVec<A>1283 fn with_capacity(capacity: usize) -> arrayvec::ArrayVec<A> {
1284 let mut v = arrayvec::ArrayVec::new();
1285 v.reserve(capacity);
1286 v
1287 }
1288
1289 #[inline]
capacity(&self) -> usize1290 fn capacity(&self) -> usize {
1291 arrayvec::ArrayVec::capacity(self)
1292 }
1293
1294 #[inline]
reserve(&mut self, capacity: usize)1295 fn reserve(&mut self, capacity: usize) {
1296 assert!(self.len() + capacity <= self.capacity());
1297 }
1298
1299 #[inline]
reserve_exact(&mut self, capacity: usize)1300 fn reserve_exact(&mut self, capacity: usize) {
1301 assert!(self.len() + capacity <= self.capacity());
1302 }
1303
1304 #[inline]
shrink_to_fit(&mut self)1305 fn shrink_to_fit(&mut self) {
1306 }
1307
1308 #[inline]
truncate(&mut self, len: usize)1309 fn truncate(&mut self, len: usize) {
1310 arrayvec::ArrayVec::truncate(self, len)
1311 }
1312
1313 #[inline]
set_len(&mut self, new_len: usize)1314 unsafe fn set_len(&mut self, new_len: usize) {
1315 arrayvec::ArrayVec::set_len(self, new_len);
1316 }
1317
1318 #[inline]
swap_remove(&mut self, index: usize) -> A::Item1319 fn swap_remove(&mut self, index: usize) -> A::Item {
1320 arrayvec::ArrayVec::swap_remove(self, index)
1321 }
1322
1323 #[inline]
insert(&mut self, index: usize, element: A::Item)1324 fn insert(&mut self, index: usize, element: A::Item) {
1325 arrayvec::ArrayVec::insert(self, index, element)
1326 }
1327
1328 #[inline]
remove(&mut self, index: usize) -> A::Item1329 fn remove(&mut self, index: usize) -> A::Item {
1330 arrayvec::ArrayVec::remove(self, index)
1331 }
1332
1333 #[inline]
push(&mut self, value: A::Item)1334 fn push(&mut self, value: A::Item) {
1335 arrayvec::ArrayVec::push(self, value);
1336 }
1337
1338 #[inline]
pop(&mut self) -> Option<A::Item>1339 fn pop(&mut self) -> Option<A::Item> {
1340 arrayvec::ArrayVec::pop(self)
1341 }
1342
1343 #[inline]
clear(&mut self)1344 fn clear(&mut self) {
1345 arrayvec::ArrayVec::clear(self);
1346 }
1347
1348 #[inline]
insert_many<I: iter::IntoIterator<Item=A::Item>>(&mut self, index: usize, iterable: I)1349 fn insert_many<I: iter::IntoIterator<Item=A::Item>>(&mut self, index: usize, iterable: I) {
1350 insert_many(self, index, iterable)
1351 }
1352
1353 #[inline]
remove_many<R: ops::RangeBounds<usize>>(&mut self, range: R)1354 fn remove_many<R: ops::RangeBounds<usize>>(&mut self, range: R) {
1355 remove_many(self, range)
1356 }
1357 }
1358
1359 // CLONEABLE VECLIKE
1360
1361 /// Vector-like container with cloneable values.
1362 ///
1363 /// Implemented for Vec, SmallVec, and StackVec.
1364 pub trait CloneableVecLike<T: Clone + Copy + Send>: Send + VecLike<T>
1365 {
1366 /// Extend collection from slice.
extend_from_slice(&mut self, other: &[T])1367 fn extend_from_slice(&mut self, other: &[T]);
1368
1369 /// Resize container to new length, with a default value if adding elements.
resize(&mut self, len: usize, value: T)1370 fn resize(&mut self, len: usize, value: T);
1371 }
1372
1373 #[cfg(all(feature = "correct", feature = "radix"))]
1374 impl<T> CloneableVecLike<T> for Vec<T>
1375 where T: Clone + Copy + Send
1376 {
1377 #[inline]
extend_from_slice(&mut self, other: &[T])1378 fn extend_from_slice(&mut self, other: &[T]) {
1379 Vec::extend_from_slice(self, other)
1380 }
1381
1382 #[inline]
resize(&mut self, len: usize, value: T)1383 fn resize(&mut self, len: usize, value: T) {
1384 Vec::resize(self, len, value)
1385 }
1386 }
1387
1388 impl<A: arrayvec::Array> CloneableVecLike<A::Item> for arrayvec::ArrayVec<A>
1389 where A: Send,
1390 A::Index: Send,
1391 A::Item: Clone + Copy + Send
1392 {
1393 #[inline]
extend_from_slice(&mut self, other: &[A::Item])1394 fn extend_from_slice(&mut self, other: &[A::Item]) {
1395 self.extend(other.iter().cloned())
1396 }
1397
1398 #[inline]
resize(&mut self, len: usize, value: A::Item)1399 fn resize(&mut self, len: usize, value: A::Item) {
1400 assert!(len <= self.capacity());
1401 let old_len = self.len();
1402 if len > old_len {
1403 self.extend(iter::repeat(value).take(len - old_len));
1404 } else {
1405 self.truncate(len);
1406 }
1407 }
1408 }
1409
1410 // TESTS
1411 // -----
1412
1413 #[cfg(test)]
1414 mod tests {
1415 use super::*;
1416
1417 #[test]
test_insert_many()1418 fn test_insert_many() {
1419 type V = arrayvec::ArrayVec<[u8; 8]>;
1420 let mut v: V = V::new();
1421 for x in 0..4 {
1422 v.push(x);
1423 }
1424 assert_eq!(v.len(), 4);
1425 v.insert_many(1, [5, 6].iter().cloned());
1426 assert_eq!(&v[..], &[0, 5, 6, 1, 2, 3]);
1427 }
1428
1429 #[cfg(all(feature = "correct", feature = "radix"))]
1430 #[test]
remove_many_test()1431 fn remove_many_test() {
1432 let mut x = vec![0, 1, 2, 3, 4, 5];
1433 x.remove_many(0..3);
1434 assert_eq!(x, vec![3, 4, 5]);
1435 assert_eq!(x.len(), 3);
1436
1437 let mut x = vec![0, 1, 2, 3, 4, 5];
1438 x.remove_many(..);
1439 assert_eq!(x, vec![]);
1440
1441 let mut x = vec![0, 1, 2, 3, 4, 5];
1442 x.remove_many(3..);
1443 assert_eq!(x, vec![0, 1, 2]);
1444
1445 let mut x = vec![0, 1, 2, 3, 4, 5];
1446 x.remove_many(..3);
1447 assert_eq!(x, vec![3, 4, 5]);
1448 }
1449 }
1450