interval_tree 0.2.0

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

extern crate interval_tree;

use interval_tree::segmentpoint::{SegmentPointTree};

#[test]
fn queries_on_empty() {
    let t = SegmentPointTree::new(0, 10, 0, Box::new(|x: &i64, y: &i64| x + y));

    assert_eq!(t.query(-1), None);
    assert_eq!(t.query(11), None);
    assert_eq!(t.query(1), Some(0));
    assert_eq!(t.query(5), Some(0));
}

#[test]
#[should_panic]
fn invalid_tree() {
    let _ = SegmentPointTree::new(1000, 10, 0, Box::new(|x: &i64, y: &i64| x + y));
}

#[test]
#[should_panic]
fn invalid_insert() {
    let mut t = SegmentPointTree::new(0, 10, 0, Box::new(|x: &i64, y: &i64| x + y));
    t.insert(5, 15, 1);
}

#[test]
fn singleton_tree() {
    let mut t = SegmentPointTree::new(0, 0, 0, Box::new(|x: &i64, y: &i64| x + y));
    t.insert(0, 0, 10);
    assert_eq!(t.query(0), Some(10));
    t.insert(0, 0, 11);
    assert_eq!(t.query(0), Some(21));
    assert_eq!(t.query(1), None);
    assert_eq!(t.query(-11), None);
    assert_eq!(t.bounds(), (0, 0));
}

#[test]
fn small_queries() {
    let mut t = SegmentPointTree::new(0, 10, 0, Box::new(|x: &i32, y: &i32| x + y));
    t.insert(0, 2, 1);
    t.insert(0, 5, 10);
    t.insert(5, 6, 2);
    t.insert(5, 7, 1);
    t.insert(10, 10, 5);
    assert_eq!(t.bounds(), (0, 10));
    let values = vec![11, 11, 11, 10, 10, 13, 3, 1, 0, 0, 5];
    assert_eq!(t.query(-1), None);
    assert_eq!(t.query(11), None);
    assert_eq!(t.query(100), None);
    for (p, v) in (0..10).zip(values) {
        assert_eq!(t.query(p), Some(v));
    }
}

#[test]
fn small_queries_2() {
    let mut t = SegmentPointTree::new(0, 10, 1, Box::new(|x: &i32, y: &i32| x * y));
    t.insert(0, 2, 1);
    t.insert(0, 5, 3);
    t.insert(5, 6, 2);
    t.insert(5, 7, 1);
    t.insert(10, 10, 0);
    assert_eq!(t.bounds(), (0, 10));
    let values = vec![3, 3, 3, 3, 3, 6, 2, 1, 1, 1, 0];
    assert_eq!(t.query(-1), None);
    assert_eq!(t.query(11), None);
    assert_eq!(t.query(100), None);
    for (p, v) in (0..10).zip(values) {
        assert_eq!(t.query(p), Some(v));
    }
}

#[test]
fn small_queries_3() {
    let concat_f = Box::new(|x: &String, y: &String| (x.clone() + &*y).to_string());
    let mut t:SegmentPointTree<i64, String> = SegmentPointTree::new(4, 6, "".to_string(), concat_f);
    assert_eq!(t.bounds(), (4, 6));
    t.insert(4, 5, "a".to_string());
    t.insert(5, 6, "b".to_string());
    t.insert(5, 5, "c".to_string());
    t.insert(6, 6, "x".to_string());
    let values = vec!["a".to_string(), "abc".to_string(), "bx".to_string()];
    assert_eq!(t.query(3), None);
    assert_eq!(t.query(11), None);
    for (p, v) in (4..6).zip(values) {
        assert_eq!(t.query(p), Some(v));
    }
}

#[test]
fn large_queries() {
    let mut t = SegmentPointTree::new(0, 1_000_000, 0, Box::new(|x: &i64, y: &i64| x + y));
    assert_eq!(t.bounds(), (0, 1_000_000));
    assert_eq!(t.query(-1), None);
    assert_eq!(t.query(2_000_000), None);
    t.insert(0, 1000, 1000);
    t.insert(1, 1000, 1000);
    t.insert(2, 1000, 1000);
    t.insert(3, 1000, 1000);
    t.insert(4, 1000, 1000);

    assert_eq!(t.query(0), Some(1000));
    assert_eq!(t.query(1), Some(2000));
    assert_eq!(t.query(2), Some(3000));
    assert_eq!(t.query(3), Some(4000));
    assert_eq!(t.query(4), Some(5000));
    assert_eq!(t.query(100), Some(5000));
    assert_eq!(t.query(1000), Some(5000));

    t.insert(2000, 10_000, 2000);
    t.insert(2000, 20_000, 2000);
    t.insert(120_444, 120_444, 8);
    t.insert(3000, 100_000, 2000);
    t.insert(3000, 200_000, 2000);

    assert_eq!(t.query(2000), Some(4000));
    assert_eq!(t.query(3000), Some(8000));
    assert_eq!(t.query(100_000), Some(4000));
    assert_eq!(t.query(120_443), Some(2000));
    assert_eq!(t.query(120_444), Some(2008));
    assert_eq!(t.query(120_445), Some(2000));
    assert_eq!(t.query(200_000), Some(2000));

    assert_eq!(t.query(0), Some(1000));
    assert_eq!(t.query(1_000_000), Some(0));
    assert_eq!(t.query(1_000_001), None);
}