polkadot_runtime_parachains/paras_inherent/
misc.rs

1// Copyright (C) Parity Technologies (UK) Ltd.
2// This file is part of Polkadot.
3
4// Polkadot is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8
9// Polkadot is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12// GNU General Public License for more details.
13
14// You should have received a copy of the GNU General Public License
15// along with Polkadot.  If not, see <http://www.gnu.org/licenses/>.
16
17use alloc::vec::Vec;
18use core::cmp::Ordering;
19
20/// A helper trait to allow calling retain while getting access
21/// to the index of the item in the `vec`.
22pub trait IndexedRetain<T> {
23	/// Retains only the elements specified by the predicate.
24	///
25	/// In other words, remove all elements `e` residing at
26	/// index `i` such that `f(i, &e)` returns `false`. This method
27	/// operates in place, visiting each element exactly once in the
28	/// original order, and preserves the order of the retained elements.
29	fn indexed_retain(&mut self, f: impl FnMut(usize, &T) -> bool);
30}
31
32impl<T> IndexedRetain<T> for Vec<T> {
33	fn indexed_retain(&mut self, mut f: impl FnMut(usize, &T) -> bool) {
34		let mut idx = 0_usize;
35		self.retain(move |item| {
36			let ret = f(idx, item);
37			idx += 1_usize;
38			ret
39		})
40	}
41}
42
43/// Helper trait until `is_sorted_by` is stabilized.
44/// TODO: <https://github.com/rust-lang/rust/issues/53485>
45pub trait IsSortedBy<T> {
46	fn is_sorted_by<F>(self, cmp: F) -> bool
47	where
48		F: FnMut(&T, &T) -> Ordering;
49}
50
51impl<'x, T, X> IsSortedBy<T> for X
52where
53	X: 'x + IntoIterator<Item = &'x T>,
54	T: 'x,
55{
56	fn is_sorted_by<F>(self, mut cmp: F) -> bool
57	where
58		F: FnMut(&T, &T) -> Ordering,
59	{
60		let mut iter = self.into_iter();
61		let mut previous: &T = if let Some(previous) = iter.next() {
62			previous
63		} else {
64			// empty is always sorted
65			return true
66		};
67		while let Some(cursor) = iter.next() {
68			match cmp(&previous, &cursor) {
69				Ordering::Greater => return false,
70				_ => {
71					// ordering is ok
72				},
73			}
74			previous = cursor;
75		}
76		true
77	}
78}
79
80#[cfg(test)]
81mod tests {
82	use super::*;
83
84	#[test]
85	fn is_sorted_simple() {
86		let v = vec![1_i32, 2, 3, 1000];
87		assert!(IsSortedBy::<i32>::is_sorted_by(v.as_slice(), |a: &i32, b: &i32| { a.cmp(b) }));
88		assert!(!IsSortedBy::<i32>::is_sorted_by(&v, |a, b| { b.cmp(a) }));
89
90		let v = vec![8_i32, 8, 8, 8];
91		assert!(IsSortedBy::<i32>::is_sorted_by(v.as_slice(), |a: &i32, b: &i32| { a.cmp(b) }));
92		assert!(IsSortedBy::<i32>::is_sorted_by(v.as_slice(), |a: &i32, b: &i32| { b.cmp(a) }));
93	}
94
95	#[test]
96	fn is_not_sorted() {
97		let v = vec![7, 1, 3];
98		assert!(!IsSortedBy::is_sorted_by(&v, |a, b| { a.cmp(b) }));
99		assert!(!IsSortedBy::is_sorted_by(&v, |a, b| { b.cmp(a) }));
100	}
101
102	#[test]
103	fn empty_is_sorted() {
104		let v = Vec::<u8>::new();
105		assert!(IsSortedBy::is_sorted_by(&v, |_a, _b| { unreachable!() }));
106	}
107
108	#[test]
109	fn single_items_is_sorted() {
110		let v = vec![7_u8];
111		assert!(IsSortedBy::is_sorted_by(&v, |_a, _b| { unreachable!() }));
112	}
113}
polkadot_runtime_parachains/paras_inherent/misc.rs

polkadot_runtime_parachains/paras_inherent/
misc.rs
