int-interval-set 0.3.4

Integer half-open interval set structures built on top of int-interval.
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

use criterion::{BenchmarkId, Criterion, black_box, criterion_group, criterion_main};
use int_interval::I32CO;
use int_interval_set::I32COSet;
use range_collections::range_set::{RangeSet, RangeSet2};
use range_set_blaze::RangeSetBlaze;

type Bounds = (i32, i32);

const INTERVALS: usize = 64;

const QUERIES: &[(&str, Bounds)] = &[
    ("before_all", (-16, -8)),
    ("hit_first", (1, 3)),
    ("adjacent_left_middle", (252, 256)),
    ("gap_middle", (260, 264)),
    ("hit_middle", (257, 259)),
    ("span_middle_gap", (258, 266)),
    ("adjacent_right_last", (508, 512)),
    ("after_all", (520, 528)),
];

/// Produces 64 canonical intervals:
///
/// ```text
/// [0, 4), [8, 12), ..., [504, 508)
/// ```
fn bounds() -> Vec<Bounds> {
    (0..INTERVALS)
        .map(|i| {
            let start = i as i32 * 8;
            (start, start + 4)
        })
        .collect()
}

fn int_interval_set(bounds: &[Bounds]) -> I32COSet {
    bounds
        .iter()
        .map(|&(start, end_excl)| I32CO::try_new(start, end_excl).unwrap())
        .collect()
}

fn range_set_blaze(bounds: &[Bounds]) -> RangeSetBlaze<i32> {
    bounds
        .iter()
        .map(|&(start, end_excl)| start..=(end_excl - 1))
        .collect()
}

fn range_collections(bounds: &[Bounds]) -> RangeSet2<i32> {
    let mut set = RangeSet2::empty();

    for &(start, end_excl) in bounds {
        set |= RangeSet::from(start..end_excl);
    }

    set
}

fn bench_case(
    c: &mut Criterion,
    case: &str,
    query: Bounds,
    int_interval_set: &I32COSet,
    range_set_blaze: &RangeSetBlaze<i32>,
    range_collections: &RangeSet2<i32>,
) {
    let mut group = c.benchmark_group("intersects_interval");
    let (start, end_excl) = query;

    let int_interval_query = I32CO::try_new(start, end_excl).unwrap();

    let range_set_blaze_query = RangeSetBlaze::from_iter([start..=(end_excl - 1)]);

    let range_collections_query: RangeSet2<i32> = RangeSet::from(start..end_excl);

    group.bench_function(BenchmarkId::new("int_interval_set", case), |b| {
        b.iter(|| black_box(int_interval_set).intersects_interval(black_box(int_interval_query)));
    });

    group.bench_function(BenchmarkId::new("range_set_blaze", case), |b| {
        b.iter(|| !black_box(range_set_blaze).is_disjoint(black_box(&range_set_blaze_query)));
    });

    group.bench_function(BenchmarkId::new("range_collections", case), |b| {
        b.iter(|| black_box(range_collections).intersects(black_box(&range_collections_query)));
    });

    group.finish();
}

fn bench_intersects_interval(c: &mut Criterion) {
    let bounds = bounds();

    let int_interval_set = int_interval_set(&bounds);
    let range_set_blaze = range_set_blaze(&bounds);
    let range_collections = range_collections(&bounds);

    for &(case, query) in QUERIES {
        bench_case(
            c,
            case,
            query,
            &int_interval_set,
            &range_set_blaze,
            &range_collections,
        );
    }
}

mod support;

criterion_group! {
    name = benches;
    config = support::config();
    targets = bench_intersects_interval
}

criterion_main!(benches);