treez 1.6.0

A collection of useful data structures.
Documentation 
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

use std::cmp;

#[cfg(test)]
extern crate rand;

#[cfg(test)]
use self::rand::distributions::{Distribution, Uniform};

/// find first index where arr[idx] > v; assume arr is sorted
pub fn upper_bound<T>(arr: &[T], v: &T) -> usize
where
    T: cmp::Ord,
{
    let mut l = 0;
    let mut r = arr.len();
    while l < r {
        let m = (l + r) / 2;
        let vm = &arr[m];
        match vm.cmp(v) {
            cmp::Ordering::Less => {
                l = m + 1;
            }
            cmp::Ordering::Greater => {
                r = m;
            }
            cmp::Ordering::Equal => {
                l = m + 1;
            }
        }
    }
    assert_eq!(l, r);
    l
}

#[test]
fn test_upper_bound() {
    let distr = Uniform::from(0..20);
    let mut rng = rand::thread_rng();

    let mut arr = (0..1000)
        .map(|_| distr.sample(&mut rng))
        .collect::<Vec<_>>();
    arr.sort();
    let val = distr.sample(&mut rng);

    let idx = upper_bound(&arr[..], &val);

    let mut check = 0;
    for (i, v) in arr.iter().enumerate() {
        check = i;
        if *v > val {
            break;
        }
    }
    assert_eq!(check, idx);
}

#[test]
fn test_upper_bound_end() {
    let distr = Uniform::from(0..20);
    let mut rng = rand::thread_rng();

    let mut arr = (0..1000)
        .map(|_| distr.sample(&mut rng))
        .collect::<Vec<_>>();
    arr.sort();
    let val = 99;

    let idx = upper_bound(&arr[..], &val);

    assert_eq!(arr.len(), idx);
}