Last active
February 26, 2018 02:55
-
-
Save ExpHP/c23b51f0a9f5f94f2375c93137299604 to your computer and use it in GitHub Desktop.
definitions of is_sorted
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use std::cmp::Ordering; | |
use std::collections::BTreeSet; | |
macro_rules! set { | |
($($t:tt)*) => { vec![$($t)*].into_iter().collect::<BTreeSet<_>>() }; | |
} | |
/// Implements "is subset of" as a comparator. | |
struct Subset<S>(BTreeSet<S>); | |
/// Implements "is suffix of" as a comparator. | |
struct Suffix(String); | |
//---------------------------------------------------- | |
impl<S: ToString> From<S> for Suffix { | |
fn from(s: S) -> Suffix { Suffix(s.to_string()) } | |
} | |
fn partial_cmp_by_le<T, F>(a: &T, b: &T, mut le: F) -> Option<Ordering> | |
where F: FnMut(&T, &T) -> bool { | |
match (le(a, b), le(b, a)) { | |
(true, true) => Some(Ordering::Equal), | |
(true, false) => Some(Ordering::Less), | |
(false, true) => Some(Ordering::Greater), | |
(false, false) => None, | |
} | |
} | |
impl<S: Ord> PartialOrd for Subset<S> { | |
fn partial_cmp(&self, other: &Self) -> Option<Ordering> | |
{ partial_cmp_by_le(self, other, Self::le) } | |
fn le(&self, other: &Self) -> bool | |
{ self.0.is_subset(&other.0) } | |
} | |
impl PartialOrd for Suffix { | |
fn partial_cmp(&self, other: &Self) -> Option<Ordering> | |
{ partial_cmp_by_le(self, other, Self::le) } | |
fn le(&self, other: &Self) -> bool | |
{ other.0.ends_with(&self.0) } | |
} | |
impl<S: Ord> PartialEq for Subset<S> { | |
fn eq(&self, other: &Self) -> bool | |
{ self.partial_cmp(other) == Some(Ordering::Equal) } | |
} | |
impl PartialEq for Suffix { | |
fn eq(&self, other: &Self) -> bool | |
{ self.partial_cmp(other) == Some(Ordering::Equal) } | |
} | |
//---------------------------------------------------- | |
// helper | |
fn pairwise_all<I, F>(iter: I, mut pred: F) -> bool | |
where | |
I: IntoIterator, | |
F: FnMut(&I::Item, &I::Item) -> bool | |
{ | |
let mut iter = iter.into_iter(); | |
if let Some(mut prev) = iter.next() { | |
for x in iter { | |
if !pred(&prev, &x) { | |
return false; | |
} | |
prev = x; | |
} | |
} | |
true | |
} | |
//---------------------------------------------------- | |
// Definition 1: Using "less or equal" | |
fn is_sorted_le<Ts>(iter: Ts) -> bool | |
where Ts: IntoIterator, Ts::Item: PartialOrd, | |
{ pairwise_all(iter, |a, b| a <= b) } | |
// Definition 2: Using "not greater" | |
fn is_sorted_ng<Ts>(iter: Ts) -> bool | |
where Ts: IntoIterator, Ts::Item: PartialOrd, | |
{ pairwise_all(iter, |a, b| !(a > b)) } | |
// These make writing the examples less tedious. | |
// They're basically 'is_sorted_by_key' | |
pub fn by_key_le<B, F, Ts>(key: F, iter: Ts) -> bool | |
where Ts: IntoIterator, F: FnMut(Ts::Item) -> B, B: PartialOrd, | |
{ is_sorted_le(iter.into_iter().map(key)) } | |
pub fn by_key_ng<B, F, Ts>(key: F, iter: Ts) -> bool | |
where Ts: IntoIterator, F: FnMut(Ts::Item) -> B, B: PartialOrd, | |
{ is_sorted_ng(iter.into_iter().map(key)) } | |
//---------------------------------------------------- | |
fn main() { | |
// What do these definitions say on various things? | |
// They agree on the easy cases... | |
// NOTE: | |
// - by_key_le is 'is_sorted_by_key' for the "less or equal" definition | |
// - by_key_ng is 'is_sorted_by_key' for the "not greater" definition | |
assert_eq!(by_key_le(Suffix::from, vec!["n", "man", "woman"]), true); | |
assert_eq!(by_key_ng(Suffix::from, vec!["n", "man", "woman"]), true); | |
assert_eq!(by_key_le(Suffix::from, vec!["woman", "man", "n"]), false); | |
assert_eq!(by_key_ng(Suffix::from, vec!["woman", "man", "n"]), false); | |
assert_eq!(by_key_le(Subset, vec![set![], set![2, 3]]), true); | |
assert_eq!(by_key_ng(Subset, vec![set![], set![2, 3]]), true); | |
assert_eq!(by_key_le(Subset, vec![set![2, 3], set![]]), false); | |
assert_eq!(by_key_ng(Subset, vec![set![2, 3], set![]]), false); | |
assert_eq!(by_key_le(|x| x, vec![1, 1, 1, 1, 1]), true); | |
assert_eq!(by_key_ng(|x| x, vec![1, 1, 1, 1, 1]), true); | |
// Things get more interesting when the '_le' function returns false. | |
let nan = 0.0 / 0.0; | |
// I hope you will agree that 'by_key_le' has a simple definition that | |
// intuitively describes all cases: | |
assert_eq!(by_key_le(|x| x, vec![nan, nan, nan]), false); | |
assert_eq!(by_key_le(|x| x, vec![1.0, nan, 2.0]), false); | |
assert_eq!(by_key_le(|x| x, vec![2.0, nan, 1.0]), false); | |
assert_eq!(by_key_le(|x| x, vec![2.0, nan, 1.0, 7.0]), false); | |
assert_eq!(by_key_le(|x| x, vec![2.0, nan, 1.0, 0.0]), false); | |
assert_eq!(by_key_le(Subset, vec![set![3], set![2]]), false); | |
assert_eq!(by_key_le(Subset, vec![set![2], set![3]]), false); | |
assert_eq!(by_key_le(Subset, vec![set![2], set![3], set![2, 3]]), false); | |
assert_eq!(by_key_le(Subset, vec![set![2], set![2, 3], set![3]]), false); | |
assert_eq!(by_key_le(Subset, vec![set![2], set![2, 3], set![5]]), false); | |
assert_eq!(by_key_le(Subset, vec![set![2, 3], set![5], set![2]]), false); | |
assert_eq!(by_key_le(Suffix::from, vec!["a", "aa", "aaa", "b", "bb", "bbb"]), false); | |
assert_eq!(by_key_le(Suffix::from, vec![ "", "a", "aa", "", "b", "bb"]), false); | |
// ...and that the results produced by 'is_sorted_ng' may be simple | |
// to define, but are worthless. | |
assert_eq!(by_key_ng(|x| x, vec![nan, nan, nan]), true); | |
assert_eq!(by_key_ng(|x| x, vec![1.0, nan, 2.0]), true); | |
assert_eq!(by_key_ng(|x| x, vec![2.0, nan, 1.0]), true); // [1] | |
assert_eq!(by_key_ng(|x| x, vec![2.0, nan, 1.0, 7.0]), true); | |
assert_eq!(by_key_ng(|x| x, vec![2.0, nan, 1.0, 0.0]), false); | |
assert_eq!(by_key_ng(Subset, vec![set![3], set![2]]), true); | |
assert_eq!(by_key_ng(Subset, vec![set![2], set![3]]), true); | |
assert_eq!(by_key_ng(Subset, vec![set![2], set![3], set![2, 3]]), true); | |
assert_eq!(by_key_ng(Subset, vec![set![2], set![2, 3], set![3]]), false); | |
assert_eq!(by_key_ng(Subset, vec![set![2], set![2, 3], set![5]]), true); | |
assert_eq!(by_key_ng(Subset, vec![set![2, 3], set![5], set![2]]), true); // [2] | |
assert_eq!(by_key_ng(Suffix::from, vec!["a", "aa", "aaa", "b", "bb", "bbb"]), true); | |
assert_eq!(by_key_ng(Suffix::from, vec![ "", "a", "aa", "", "b", "bb"]), false); | |
} | |
// [1]: There's an alternate definition of `is_sorted` that could return | |
// false for `[2.0, nan, 1.0]`, but it has quadratic complexity. | |
// [2]: This counterexample was added when it almost appeared that `is_sorted_ng` | |
// might be useful for a dependency solver like `cargo` to verify that a | |
// sequence of packages is topologically ordered. (Hint: It isn't) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment