definitions of is_sorted

is_sorted.rs

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)