stry_common/utils/fenn/vec.rs
1use core::cmp::Ordering;
2
3/// Extension trait that contains functions that allow for chaining of
4/// [`Vec`].
5///
6/// [`Vec`]: https://doc.rust-lang.org/std/vec/struct.Vec.html
7///
8/// Before:
9///
10/// ```rust
11/// let mut vec = vec![2, 4, 3, 1, 5, 2, 3, 1];
12///
13/// vec.sort();
14///
15/// vec.dedup();
16///
17/// assert_eq!(vec, [1, 2, 3, 4, 5]);
18/// ```
19///
20/// After:
21///
22/// ```rust
23/// use fenn::VecExt;
24///
25/// let vec = vec![2, 4, 3, 1, 5, 2, 3, 1]
26/// .sorted()
27/// .deduped();
28///
29/// assert_eq!(vec, [1, 2, 3, 4, 5]);
30/// ```
31pub trait VecExt<T> {
32 /// Moves all the elements of `other` into `Self`, leaving `other` empty.
33 ///
34 /// # Panics
35 ///
36 /// Panics if the number of elements in the vector overflows a `usize`.
37 ///
38 /// # Examples
39 ///
40 /// ```
41 /// # extern crate fenn;
42 /// use fenn::VecExt;
43 ///
44 /// let mut vec2 = vec![4, 5, 6];
45 /// let vec = vec![1, 2, 3].appended(&mut vec2);
46 ///
47 /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
48 /// assert_eq!(vec2, []);
49 /// ```
50 fn appended(self, other: &mut Self) -> Self;
51
52 /// Clears the vector, removing all values.
53 ///
54 /// Note that this method has no effect on the allocated capacity
55 /// of the vector.
56 ///
57 /// # Examples
58 ///
59 /// ```
60 /// # extern crate fenn;
61 /// use fenn::VecExt;
62 ///
63 /// let v = vec![1, 2, 3].cleared();
64 ///
65 /// assert!(v.is_empty());
66 /// ```
67 fn cleared(self) -> Self;
68
69 /// Removes consecutive repeated elements in the vector according to the
70 /// [`PartialEq`] trait implementation.
71 ///
72 /// If the vector is sorted, this removes all duplicates.
73 ///
74 /// # Examples
75 ///
76 /// ```
77 /// # extern crate fenn;
78 /// use fenn::VecExt;
79 ///
80 /// let vec = vec![1, 2, 2, 3, 2].deduped();
81 ///
82 /// assert_eq!(vec, [1, 2, 3, 2]);
83 /// ```
84 fn deduped(self) -> Self
85 where
86 T: PartialEq;
87
88 /// Removes all but the first of consecutive elements in the vector satisfying a given equality
89 /// relation.
90 ///
91 /// The `same_bucket` function is passed references to two elements from the vector and
92 /// must determine if the elements compare equal. The elements are passed in opposite order
93 /// from their order in the vector, so if `same_bucket(a, b)` returns `true`, `a` is removed.
94 ///
95 /// If the vector is sorted, this removes all duplicates.
96 ///
97 /// # Examples
98 ///
99 /// ```
100 /// # extern crate fenn;
101 /// use fenn::VecExt;
102 ///
103 /// let vec = vec!["foo", "bar", "Bar", "baz", "bar"]
104 /// .deduped_by(|a, b| a.eq_ignore_ascii_case(b));
105 ///
106 /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
107 /// ```
108 fn deduped_by<F>(self, same_bucket: F) -> Self
109 where
110 F: FnMut(&mut T, &mut T) -> bool;
111
112 /// Removes all but the first of consecutive elements in the vector that resolve to the same
113 /// key.
114 ///
115 /// If the vector is sorted, this removes all duplicates.
116 ///
117 /// # Examples
118 ///
119 /// ```
120 /// # extern crate fenn;
121 /// use fenn::VecExt;
122 ///
123 /// let vec = vec![10, 20, 21, 30, 20].deduped_by_key(|i| *i / 10);
124 ///
125 /// assert_eq!(vec, [10, 20, 30, 20]);
126 /// ```
127 fn deduped_by_key<F, K>(self, key: F) -> Self
128 where
129 F: FnMut(&mut T) -> K,
130 K: PartialEq<K>;
131
132 /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
133 ///
134 /// If `new_len` is greater than `len`, the `Vec` is extended by the
135 /// difference, with each additional slot filled with `value`.
136 /// If `new_len` is less than `len`, the `Vec` is simply truncated.
137 ///
138 /// This method requires `T` to implement [`Clone`],
139 /// in order to be able to clone the passed value.
140 ///
141 /// # Examples
142 ///
143 /// ```
144 /// # extern crate fenn;
145 /// use fenn::VecExt;
146 ///
147 /// let vec = vec!["hello"].resized(3, "world");
148 ///
149 /// assert_eq!(vec, ["hello", "world", "world"]);
150 /// ```
151 ///
152 /// ```
153 /// # extern crate fenn;
154 /// use fenn::VecExt;
155 ///
156 /// let vec = vec![1, 2, 3, 4].resized(2, 0);
157 ///
158 /// assert_eq!(vec, [1, 2]);
159 /// ```
160 ///
161 /// [`Clone`]: ../../std/clone/trait.Clone.html
162 fn resized(self, new_len: usize, value: T) -> Self
163 where
164 T: Clone;
165
166 /// Reverses the order of elements in the vector.
167 ///
168 /// # Examples
169 ///
170 /// ```
171 /// # extern crate fenn;
172 /// use fenn::VecExt;
173 ///
174 /// let v = vec![1, 2, 3].reversed();
175 ///
176 /// assert!(v == [3, 2, 1]);
177 /// ```
178 fn reversed(self) -> Self;
179
180 /// Shrinks the capacity of the vector as much as possible.
181 ///
182 /// It will drop down as close as possible to the length but the allocator
183 /// may still inform the vector that there is space for a few more elements.
184 ///
185 /// # Examples
186 ///
187 /// ```
188 /// # extern crate fenn;
189 /// use fenn::{Peep, VecExt};
190 ///
191 /// let mut vec2 = vec![1, 2, 3];
192 /// let vec = Vec::with_capacity(10)
193 /// .appended(&mut vec2)
194 /// .peep(|vec| assert_eq!(vec.capacity(), 10))
195 /// .shrinked_to_fit();
196 ///
197 /// assert!(vec.capacity() >= 3);
198 /// assert_eq!(vec2, []);
199 /// ```
200 fn shrinked_to_fit(self) -> Self;
201
202 /// Sorts the vector.
203 ///
204 /// This sort is stable (i.e., does not reorder equal elements) and `O(n * log(n))` worst-case.
205 ///
206 /// # Current implementation
207 ///
208 /// The current algorithm is an adaptive, iterative merge sort inspired by
209 /// [timsort](https://en.wikipedia.org/wiki/Timsort).
210 /// It is designed to be very fast in cases where the vector is nearly sorted, or consists of
211 /// two or more sorted sequences concatenated one after another.
212 ///
213 /// Also, it allocates temporary storage half the size of `self`, but for short vectors a
214 /// non-allocating insertion sort is used instead.
215 ///
216 /// # Examples
217 ///
218 /// ```
219 /// # extern crate fenn;
220 /// use fenn::VecExt;
221 ///
222 /// let v = vec![-5, 4, 1, -3, 2].sorted();
223 ///
224 /// assert!(v == [-5, -3, 1, 2, 4]);
225 /// ```
226 fn sorted(self) -> Self
227 where
228 T: Ord;
229
230 /// Sorts the vector with a comparator function.
231 ///
232 /// This sort is stable (i.e., does not reorder equal elements) and `O(n * log(n))` worst-case.
233 ///
234 /// The comparator function must define a total ordering for the elements in the vector. If
235 /// the ordering is not total, the order of the elements is unspecified. An order is a
236 /// total order if it is (for all `a`, `b` and `c`):
237 ///
238 /// * total and antisymmetric: exactly one of `a < b`, `a == b` or `a > b` is true, and
239 /// * transitive, `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`.
240 ///
241 /// For example, while [`f64`] doesn't implement [`Ord`] because `NaN != NaN`, we can use
242 /// `partial_cmp` as our sort function when we know the vector doesn't contain a `NaN`.
243 ///
244 /// ```
245 /// # extern crate fenn;
246 /// use fenn::VecExt;
247 ///
248 /// let mut floats = vec![5f64, 4.0, 1.0, 3.0, 2.0]
249 /// .sorted_by(|a, b| a.partial_cmp(b).unwrap());
250 ///
251 /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]);
252 /// ```
253 ///
254 /// # Current implementation
255 ///
256 /// The current algorithm is an adaptive, iterative merge sort inspired by
257 /// [timsort](https://en.wikipedia.org/wiki/Timsort).
258 /// It is designed to be very fast in cases where the vector is nearly sorted, or consists of
259 /// two or more sorted sequences concatenated one after another.
260 ///
261 /// Also, it allocates temporary storage half the size of `self`, but for short vectors a
262 /// non-allocating insertion sort is used instead.
263 ///
264 /// # Examples
265 ///
266 /// ```
267 /// # extern crate fenn;
268 /// use fenn::VecExt;
269 ///
270 /// let mut v = vec![5, 4, 1, 3, 2]
271 /// .sorted_by(|a, b| a.cmp(b));
272 ///
273 /// assert!(v == [1, 2, 3, 4, 5]);
274 /// ```
275 ///
276 /// ```
277 /// # extern crate fenn;
278 /// use fenn::VecExt;
279 ///
280 /// // reverse sorting
281 /// let v = vec![1, 2, 3, 4, 5]
282 /// .sorted_by(|a, b| b.cmp(a));
283 ///
284 /// assert!(v == [5, 4, 3, 2, 1]);
285 /// ```
286 fn sorted_by<F>(self, compare: F) -> Self
287 where
288 F: FnMut(&T, &T) -> Ordering;
289
290 /// Sorts the vector with a key extraction function.
291 ///
292 /// This sort is stable (i.e., does not reorder equal elements) and `O(m * n * log(n))`
293 /// worst-case, where the key function is `O(m)`.
294 ///
295 /// # Current implementation
296 ///
297 /// The current algorithm is an adaptive, iterative merge sort inspired by
298 /// [timsort](https://en.wikipedia.org/wiki/Timsort).
299 /// It is designed to be very fast in cases where the vector is nearly sorted, or consists of
300 /// two or more sorted sequences concatenated one after another.
301 ///
302 /// Also, it allocates temporary storage half the size of `self`, but for short vectors a
303 /// non-allocating insertion sort is used instead.
304 ///
305 /// # Examples
306 ///
307 /// ```
308 /// # extern crate fenn;
309 /// use fenn::VecExt;
310 ///
311 /// let v = vec![-5i32, 4, 1, -3, 2]
312 /// .sorted_by_key(|k| k.abs());
313 ///
314 /// assert!(v == [1, 2, -3, 4, -5]);
315 /// ```
316 fn sorted_by_key<F, K>(self, f: F) -> Self
317 where
318 F: FnMut(&T) -> K,
319 K: Ord;
320
321 /// Shortens the vector, keeping the first `len` elements and dropping
322 /// the rest.
323 ///
324 /// If `len` is greater than the vector's current length, this has no
325 /// effect.
326 ///
327 /// The `drain` method can emulate `truncate`, but causes the excess
328 /// elements to be returned instead of dropped.
329 ///
330 /// Note that this method has no effect on the allocated capacity
331 /// of the vector.
332 ///
333 /// # Examples
334 ///
335 /// Truncating a five element vector to two elements:
336 ///
337 /// ```
338 /// # extern crate fenn;
339 /// use fenn::VecExt;
340 ///
341 /// let vec = vec![1, 2, 3, 4, 5].truncated(2);
342 ///
343 /// assert_eq!(vec, [1, 2]);
344 /// ```
345 ///
346 /// No truncation occurs when `len` is greater than the vector's current
347 /// length:
348 ///
349 /// ```
350 /// # extern crate fenn;
351 /// use fenn::VecExt;
352 ///
353 /// let vec = vec![1, 2, 3].truncated(8);
354 ///
355 /// assert_eq!(vec, [1, 2, 3]);
356 /// ```
357 ///
358 /// Truncating when `len == 0` is equivalent to calling the [`cleared`]
359 /// method.
360 ///
361 /// ```
362 /// # extern crate fenn;
363 /// use fenn::VecExt;
364 ///
365 /// let vec = vec![1, 2, 3].truncated(0);
366 ///
367 /// assert_eq!(vec, []);
368 /// ```
369 ///
370 /// [`cleared`]: #tymethod.cleared
371 fn truncated(self, len: usize) -> Self;
372}
373
374impl<T> VecExt<T> for super::lib::vec::Vec<T> {
375 fn appended(mut self, other: &mut Self) -> Self {
376 self.append(other);
377
378 self
379 }
380
381 fn cleared(mut self) -> Self {
382 self.clear();
383
384 self
385 }
386
387 fn deduped(mut self) -> Self
388 where
389 T: PartialEq,
390 {
391 self.dedup();
392
393 self
394 }
395
396 fn deduped_by<F>(mut self, same_bucket: F) -> Self
397 where
398 F: FnMut(&mut T, &mut T) -> bool,
399 {
400 self.dedup_by(same_bucket);
401
402 self
403 }
404
405 fn deduped_by_key<F, K>(mut self, key: F) -> Self
406 where
407 F: FnMut(&mut T) -> K,
408 K: PartialEq<K>,
409 {
410 self.dedup_by_key(key);
411
412 self
413 }
414
415 fn resized(mut self, new_len: usize, value: T) -> Self
416 where
417 T: Clone,
418 {
419 self.resize(new_len, value);
420
421 self
422 }
423
424 fn reversed(mut self) -> Self {
425 self.reverse();
426
427 self
428 }
429
430 fn shrinked_to_fit(mut self) -> Self {
431 self.shrink_to_fit();
432
433 self
434 }
435
436 fn sorted(mut self) -> Self
437 where
438 T: Ord,
439 {
440 self.sort();
441
442 self
443 }
444
445 fn sorted_by<F>(mut self, compare: F) -> Self
446 where
447 F: FnMut(&T, &T) -> Ordering,
448 {
449 self.sort_by(compare);
450
451 self
452 }
453
454 fn sorted_by_key<F, K>(mut self, f: F) -> Self
455 where
456 F: FnMut(&T) -> K,
457 K: Ord,
458 {
459 self.sort_by_key(f);
460
461 self
462 }
463
464 fn truncated(mut self, len: usize) -> Self {
465 self.truncate(len);
466
467 self
468 }
469}