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
pub struct RangeResolver {
ranges: Vec<(u32, u32)>,
}
impl RangeResolver {
pub fn new() -> Self {
RangeResolver { ranges: Vec::new() }
}
pub fn insert(&mut self, mut start: u32, last: u32) {
let mut new_ranges = Vec::new();
let mut added = false;
for (idx, &(s, l)) in self.ranges.iter().enumerate() {
if l < start {
new_ranges.push((s, l));
continue;
}
if s > last {
if !added {
new_ranges.push((start, last));
}
new_ranges.extend_from_slice(&self.ranges[idx..]);
added = true;
break;
}
// must overlap here
use std::cmp::Ordering;
match start.cmp(&s) {
Ordering::Less => {
match last.cmp(&l) {
Ordering::Less => {
// nnnnnnn
// rrrrr
new_ranges.push((start, s - 1));
new_ranges.push((s, last));
new_ranges.push((last + 1, l));
added = true;
}
Ordering::Equal => {
// nnnnnn
// rrr
new_ranges.push((start, s - 1));
new_ranges.push((s, l));
added = true;
}
Ordering::Greater => {
// nnnnnnn
// rrr
new_ranges.push((start, s - 1));
new_ranges.push((s, l));
start = l + 1;
}
}
}
Ordering::Equal => {
match last.cmp(&l) {
Ordering::Less => {
// nnnn
// rrrrrr
new_ranges.push((start, last));
added = true;
new_ranges.push((last + 1, l));
}
Ordering::Equal => {
// nnnn
// rrrr
new_ranges.push((start, last));
added = true;
}
Ordering::Greater => {
// nnnnnnnn
// rrrr
new_ranges.push((s, l));
start = l + 1;
}
}
}
Ordering::Greater => {
// start > s
match last.cmp(&l) {
Ordering::Less => {
// nnnnn
// rrrrrrrrr
new_ranges.push((s, start - 1));
new_ranges.push((start, last));
new_ranges.push((last + 1, l));
added = true;
}
Ordering::Equal => {
// nnnnnnn
// rrrrrrrrr
new_ranges.push((s, start - 1));
new_ranges.push((start, last));
added = true;
}
Ordering::Greater => {
// nnnnnnnnn
// rrrrrrrrr
new_ranges.push((s, start - 1));
new_ranges.push((start, l));
start = l + 1;
}
}
}
}
}
if !added {
new_ranges.push((start, last));
}
self.ranges = new_ranges;
}
pub fn get_ranges(&self, start: u32, last: u32) -> impl Iterator<Item = usize> {
let first_idx = match self.ranges.binary_search(&(start, start)) {
Ok(idx) => idx,
Err(idx) => idx,
};
let end_idx = match self.ranges.binary_search(&(last, last)) {
Ok(idx) => idx + 1,
Err(idx) => idx,
};
first_idx..end_idx
}
pub fn iter(&self) -> impl Iterator<Item = (u32, u32)> + '_ {
self.ranges.iter().copied()
}
}