btree_set_range/
btree_set_range.rs

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
use std::collections::BTreeSet;
use std::ops::Bound::{self, *};

use quickcheck::{quickcheck, TestResult};

/// Covers every `std::ops::Range*` plus variants with exclusive start.
type RangeAny<T> = (Bound<T>, Bound<T>);

/// Mimic `RangeBounds::contains`, stabilized in Rust 1.35.
trait RangeBounds<T> {
    fn contains(&self, _: &T) -> bool;
}

impl<T: PartialOrd> RangeBounds<T> for RangeAny<T> {
    fn contains(&self, item: &T) -> bool {
        (match &self.0 {
            Included(start) => start <= item,
            Excluded(start) => start < item,
            Unbounded => true,
        }) && (match &self.1 {
            Included(end) => item <= end,
            Excluded(end) => item < end,
            Unbounded => true,
        })
    }
}

/// Checks conditions where `BTreeSet::range` panics:
/// - Panics if range start > end.
/// - Panics if range start == end and both bounds are Excluded.
fn panics<T: PartialOrd>(range: RangeAny<T>) -> bool {
    match (&range.0, &range.1) {
        (Excluded(start), Excluded(end)) => start >= end,
        (Included(start), Excluded(end))
        | (Excluded(start), Included(end))
        | (Included(start), Included(end)) => start > end,
        (Unbounded, _) | (_, Unbounded) => false,
    }
}

/// Checks that `BTreeSet::range` returns all items contained in the given `range`.
fn check_range(set: BTreeSet<i32>, range: RangeAny<i32>) -> TestResult {
    if panics(range) {
        TestResult::discard()
    } else {
        let xs: BTreeSet<_> = set.range(range).cloned().collect();
        TestResult::from_bool(
            set.iter().all(|x| range.contains(x) == xs.contains(x)),
        )
    }
}

fn main() {
    quickcheck(check_range as fn(_, _) -> TestResult);
}