vers-vecs 1.9.1

A collection of succinct data structures supported by fast implementations of rank and select queries.
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

use crate::rmq::binary_rmq::BinaryRmq;
use rand::RngCore;

#[test]
fn small_test() {
    let rmq = BinaryRmq::from_vec(vec![9, 6, 10, 4, 0, 8, 3, 7, 1, 2, 5]);

    assert_eq!(rmq.range_min(0, 0), 0);
    assert_eq!(rmq.range_min(0, 1), 1);
    assert_eq!(rmq.range_min(0, 2), 1);
    assert_eq!(rmq.range_min(0, 3), 3);
    assert_eq!(rmq.range_min(5, 8), 8);
    assert_eq!(rmq.range_min(5, 9), 8);
    assert_eq!(rmq.range_min(9, 10), 9);
    assert_eq!(rmq.range_min(0, 10), 4);
}

#[test]
fn randomized_test() {
    let mut rng = rand::thread_rng();
    const L: usize = 100;

    let mut numbers_vec = Vec::with_capacity(L);
    for _ in 0..L {
        numbers_vec.push(rng.next_u64());
    }

    let rmq = BinaryRmq::from_vec(numbers_vec.clone());

    for i in 0..L {
        for j in i..L {
            let min = numbers_vec[i..=j].iter().min().unwrap();
            assert_eq!(
                numbers_vec[rmq.range_min(i, j)],
                *min,
                "i = {}, j = {}",
                i,
                j
            );
        }
    }
}

#[test]
fn test_iter() {
    let rmq = BinaryRmq::from_vec(vec![1, 2, 3, 4, 5]);
    let mut iter = rmq.iter();
    assert_eq!(iter.next(), Some(&1));
    assert_eq!(iter.next(), Some(&2));
    assert_eq!(iter.next(), Some(&3));
    assert_eq!(iter.next(), Some(&4));
    assert_eq!(iter.next(), Some(&5));
    assert_eq!(iter.next(), None);
}

#[test]
fn test_range_operators() {
    let rmq = BinaryRmq::from_vec(vec![5, 4, 3, 2, 1]);
    assert_eq!(rmq.range_min(0, 3), 3);
    assert_eq!(rmq.range_min_with_range(0..3), 2);
    assert_eq!(rmq.range_min_with_range(0..=3), 3);
}

#[test]
fn test_empty_rmq() {
    let rmq = BinaryRmq::from_vec(Vec::<u64>::new());
    assert!(rmq.is_empty());
    // calling functions on an empty rmq will panic because the upper bound is inclusive, but there
    // is no valid index in an empty array, so we can't test anything else
}