1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

// Copyright (C) Parity Technologies (UK) Ltd.
// This file is part of Polkadot.

// Polkadot is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// Polkadot is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with Polkadot.  If not, see <http://www.gnu.org/licenses/>.

use alloc::vec::Vec;
use core::cmp::Ordering;

/// A helper trait to allow calling retain while getting access
/// to the index of the item in the `vec`.
pub trait IndexedRetain<T> {
	/// Retains only the elements specified by the predicate.
	///
	/// In other words, remove all elements `e` residing at
	/// index `i` such that `f(i, &e)` returns `false`. This method
	/// operates in place, visiting each element exactly once in the
	/// original order, and preserves the order of the retained elements.
	fn indexed_retain(&mut self, f: impl FnMut(usize, &T) -> bool);
}

impl<T> IndexedRetain<T> for Vec<T> {
	fn indexed_retain(&mut self, mut f: impl FnMut(usize, &T) -> bool) {
		let mut idx = 0_usize;
		self.retain(move |item| {
			let ret = f(idx, item);
			idx += 1_usize;
			ret
		})
	}
}

/// Helper trait until `is_sorted_by` is stabilized.
/// TODO: <https://github.com/rust-lang/rust/issues/53485>
pub trait IsSortedBy<T> {
	fn is_sorted_by<F>(self, cmp: F) -> bool
	where
		F: FnMut(&T, &T) -> Ordering;
}

impl<'x, T, X> IsSortedBy<T> for X
where
	X: 'x + IntoIterator<Item = &'x T>,
	T: 'x,
{
	fn is_sorted_by<F>(self, mut cmp: F) -> bool
	where
		F: FnMut(&T, &T) -> Ordering,
	{
		let mut iter = self.into_iter();
		let mut previous: &T = if let Some(previous) = iter.next() {
			previous
		} else {
			// empty is always sorted
			return true
		};
		while let Some(cursor) = iter.next() {
			match cmp(&previous, &cursor) {
				Ordering::Greater => return false,
				_ => {
					// ordering is ok
				},
			}
			previous = cursor;
		}
		true
	}
}

#[cfg(test)]
mod tests {
	use super::*;

	#[test]
	fn is_sorted_simple() {
		let v = vec![1_i32, 2, 3, 1000];
		assert!(IsSortedBy::<i32>::is_sorted_by(v.as_slice(), |a: &i32, b: &i32| { a.cmp(b) }));
		assert!(!IsSortedBy::<i32>::is_sorted_by(&v, |a, b| { b.cmp(a) }));

		let v = vec![8_i32, 8, 8, 8];
		assert!(IsSortedBy::<i32>::is_sorted_by(v.as_slice(), |a: &i32, b: &i32| { a.cmp(b) }));
		assert!(IsSortedBy::<i32>::is_sorted_by(v.as_slice(), |a: &i32, b: &i32| { b.cmp(a) }));
	}

	#[test]
	fn is_not_sorted() {
		let v = vec![7, 1, 3];
		assert!(!IsSortedBy::is_sorted_by(&v, |a, b| { a.cmp(b) }));
		assert!(!IsSortedBy::is_sorted_by(&v, |a, b| { b.cmp(a) }));
	}

	#[test]
	fn empty_is_sorted() {
		let v = Vec::<u8>::new();
		assert!(IsSortedBy::is_sorted_by(&v, |_a, _b| { unreachable!() }));
	}

	#[test]
	fn single_items_is_sorted() {
		let v = vec![7_u8];
		assert!(IsSortedBy::is_sorted_by(&v, |_a, _b| { unreachable!() }));
	}
}