1use std::iter::Step;
2use std::marker::PhantomData;
3use std::ops::{Bound, RangeBounds};
4use std::range::RangeInclusive;
5
6use smallvec::SmallVec;
7
8use crate::idx::Idx;
9use crate::vec::IndexVec;
10
11#[cfg(test)]
12mod tests;
13
14#[derive(#[automatically_derived]impl<I: ::core::fmt::Debug> ::core::fmt::Debug for
IntervalSet<I> {
#[inline]
#[rustc_trivial_field_reads]
fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
::core::fmt::Formatter::debug_struct_field3_finish(f,
"IntervalSet map domain _data", &self.map, &self.domain,
&&self._data)
}
}Debug, #[automatically_derived]impl<I: ::core::clone::Clone> ::core::clone::Clone for
IntervalSet<I> {
#[inline]
#[rustc_trivial_field_reads]
fn clone(&self) -> Self {
IntervalSet {
map: ::core::clone::Clone::clone(&self.map),
domain: ::core::clone::Clone::clone(&self.domain),
_data: ::core::clone::Clone::clone(&self._data),
}
}
}Clone)]
20pub struct IntervalSet<I> {
21 map: SmallVec<[(u32, u32); 2]>,
23 domain: usize,
24 _data: PhantomData<I>,
25}
26
27#[inline]
28fn inclusive_start<T: Idx>(range: impl RangeBounds<T>) -> u32 {
29 match range.start_bound() {
30 Bound::Included(start) => start.index() as u32,
31 Bound::Excluded(start) => start.index() as u32 + 1,
32 Bound::Unbounded => 0,
33 }
34}
35
36#[inline]
37fn inclusive_end<T: Idx>(domain: usize, range: impl RangeBounds<T>) -> Option<u32> {
38 let end = match range.end_bound() {
39 Bound::Included(end) => end.index() as u32,
40 Bound::Excluded(end) => end.index().checked_sub(1)? as u32,
41 Bound::Unbounded => domain.checked_sub(1)? as u32,
42 };
43 Some(end)
44}
45
46impl<I: Idx> IntervalSet<I> {
47 pub fn new(domain: usize) -> IntervalSet<I> {
48 IntervalSet { map: SmallVec::new(), domain, _data: PhantomData }
49 }
50
51 pub fn clear(&mut self) {
52 self.map.clear();
53 }
54
55 pub fn iter(&self) -> impl Iterator<Item = I>
56 where
57 I: Step,
58 {
59 self.iter_intervals().flatten()
60 }
61
62 pub fn iter_intervals(&self) -> impl Iterator<Item = RangeInclusive<I>>
64 where
65 I: Step,
66 {
67 self.map.iter().map(|&(start, end)| RangeInclusive {
68 start: I::new(start as usize),
69 last: I::new(end as usize),
70 })
71 }
72
73 pub fn insert(&mut self, point: I) -> bool {
75 self.insert_range(point..=point)
76 }
77
78 pub fn insert_range(&mut self, range: impl RangeBounds<I> + Clone) -> bool {
80 let start = inclusive_start(range.clone());
81 let Some(end) = inclusive_end(self.domain, range) else {
82 return false;
84 };
85 if start > end {
86 return false;
87 }
88
89 let next = self.map.partition_point(|r| r.0 <= end + 1);
95 let result = if let Some(right) = next.checked_sub(1) {
96 let (prev_start, prev_end) = self.map[right];
97 if prev_end + 1 >= start {
98 if start < prev_start {
101 let left = self.map.partition_point(|l| l.1 + 1 < start);
104 let min = std::cmp::min(self.map[left].0, start);
105 let max = std::cmp::max(prev_end, end);
106 self.map[right] = (min, max);
107 if left != right {
108 self.map.drain(left..right);
109 }
110 true
111 } else {
112 if end > prev_end {
119 self.map[right].1 = end;
120 true
121 } else {
122 false
123 }
124 }
125 } else {
126 self.map.insert(right + 1, (start, end));
128 true
129 }
130 } else {
131 if self.map.is_empty() {
132 self.map.push((start, end));
135 } else {
136 self.map.insert(next, (start, end));
137 }
138 true
139 };
140 if true {
if !self.check_invariants() {
{
::core::panicking::panic_fmt(format_args!("wrong intervals after insert {0:?}..={1:?} to {2:?}",
start, end, self));
}
};
};debug_assert!(
141 self.check_invariants(),
142 "wrong intervals after insert {start:?}..={end:?} to {self:?}"
143 );
144 result
145 }
146
147 pub fn append(&mut self, point: I) {
150 let point = point.index() as u32;
151
152 if let Some((_, last_end)) = self.map.last_mut() {
153 if !(*last_end <= point) {
::core::panicking::panic("assertion failed: *last_end <= point")
};assert!(*last_end <= point);
154 if point == *last_end {
155 } else if point == *last_end + 1 {
157 *last_end = point;
158 } else {
159 self.map.push((point, point));
160 }
161 } else {
162 self.map.push((point, point));
163 }
164
165 if true {
if !self.check_invariants() {
{
::core::panicking::panic_fmt(format_args!("wrong intervals after append {0:?} to {1:?}",
point, self));
}
};
};debug_assert!(
166 self.check_invariants(),
167 "wrong intervals after append {point:?} to {self:?}"
168 );
169 }
170
171 pub fn append_range(&mut self, range: impl RangeBounds<I> + Clone) {
174 let start = inclusive_start(range.clone());
175 let Some(end) = inclusive_end(self.domain, range) else {
176 return;
178 };
179 if start > end {
180 return;
181 }
182
183 if let Some((_, last_end)) = self.map.last_mut() {
184 if !(*last_end <= start) {
::core::panicking::panic("assertion failed: *last_end <= start")
};assert!(*last_end <= start);
185 if start <= *last_end + 1 {
187 *last_end = end;
188 } else {
189 self.map.push((start, end));
190 }
191 } else {
192 self.map.push((start, end));
193 }
194
195 if true {
if !self.check_invariants() {
{
::core::panicking::panic_fmt(format_args!("wrong intervals after append {0:?}..={1:?} to {2:?}",
start, end, self));
}
};
};debug_assert!(
196 self.check_invariants(),
197 "wrong intervals after append {start:?}..={end:?} to {self:?}"
198 );
199 }
200
201 pub fn contains(&self, needle: I) -> bool {
202 let needle = needle.index() as u32;
203 let Some(last) = self.map.partition_point(|r| r.0 <= needle).checked_sub(1) else {
204 return false;
206 };
207 let (_, prev_end) = &self.map[last];
208 needle <= *prev_end
209 }
210
211 pub fn intersects_range(&self, range: impl RangeBounds<I> + Clone) -> bool {
213 let start = inclusive_start(range.clone());
214 let Some(end) = inclusive_end(self.domain, range) else {
215 return false;
217 };
218 if start > end {
219 return false;
220 }
221
222 let Some(last) = self.map.partition_point(|r| r.0 <= end).checked_sub(1) else {
224 return false;
226 };
227 let (_, prev_end) = &self.map[last];
228 start <= *prev_end
229 }
230
231 pub fn superset(&self, other: &IntervalSet<I>) -> bool
232 where
233 I: Step,
234 {
235 let mut sup_iter = self.iter_intervals();
236 let mut current = None;
237 let contains = |sup: RangeInclusive<I>,
238 sub: RangeInclusive<I>,
239 current: &mut Option<RangeInclusive<I>>| {
240 if sup.last < sub.start {
241 None } else if sup.last >= sub.last && sup.start <= sub.start {
243 *current = Some(sup); Some(true)
245 } else {
246 Some(false)
247 }
248 };
249 other.iter_intervals().all(|sub| {
250 current
251 .take()
252 .and_then(|sup| contains(sup, sub, &mut current))
253 .or_else(|| sup_iter.find_map(|sup| contains(sup, sub, &mut current)))
254 .unwrap_or(false)
255 })
256 }
257
258 pub fn disjoint(&self, other: &IntervalSet<I>) -> bool
259 where
260 I: Step,
261 {
262 let helper = move || {
263 let mut self_iter = self.iter_intervals();
264 let mut other_iter = other.iter_intervals();
265
266 let mut self_current = self_iter.next()?;
267 let mut other_current = other_iter.next()?;
268
269 loop {
270 if self_current.last < other_current.start {
271 self_current = self_iter.next()?;
272 continue;
273 }
274 if other_current.last < self_current.start {
275 other_current = other_iter.next()?;
276 continue;
277 }
278 return Some(false);
279 }
280 };
281 helper().unwrap_or(true)
282 }
283
284 pub fn is_empty(&self) -> bool {
285 self.map.is_empty()
286 }
287
288 pub fn first_unset_in(&self, range: impl RangeBounds<I> + Clone) -> Option<I> {
290 let start = inclusive_start(range.clone());
291 let Some(end) = inclusive_end(self.domain, range) else {
292 return None;
294 };
295 if start > end {
296 return None;
297 }
298 let Some(last) = self.map.partition_point(|r| r.0 <= start).checked_sub(1) else {
299 return Some(I::new(start as usize));
301 };
302 let (_, prev_end) = self.map[last];
303 if start > prev_end {
304 Some(I::new(start as usize))
305 } else if prev_end < end {
306 Some(I::new(prev_end as usize + 1))
307 } else {
308 None
309 }
310 }
311
312 pub fn last_set_in(&self, range: impl RangeBounds<I> + Clone) -> Option<I> {
314 let start = inclusive_start(range.clone());
315 let Some(end) = inclusive_end(self.domain, range) else {
316 return None;
318 };
319 if start > end {
320 return None;
321 }
322 let Some(last) = self.map.partition_point(|r| r.0 <= end).checked_sub(1) else {
323 return None;
325 };
326 let (_, prev_end) = &self.map[last];
327 if start <= *prev_end { Some(I::new(std::cmp::min(*prev_end, end) as usize)) } else { None }
328 }
329
330 pub fn insert_all(&mut self) {
331 self.clear();
332 if let Some(end) = self.domain.checked_sub(1) {
333 self.map.push((0, end.try_into().unwrap()));
334 }
335 if true {
if !self.check_invariants() {
::core::panicking::panic("assertion failed: self.check_invariants()")
};
};debug_assert!(self.check_invariants());
336 }
337
338 pub fn union(&mut self, other: &IntervalSet<I>) -> bool
339 where
340 I: Step,
341 {
342 {
match (&self.domain, &other.domain) {
(left_val, right_val) => {
if !(*left_val == *right_val) {
let kind = ::core::panicking::AssertKind::Eq;
::core::panicking::assert_failed(kind, &*left_val,
&*right_val, ::core::option::Option::None);
}
}
}
};assert_eq!(self.domain, other.domain);
343 if self.map.len() < other.map.len() {
344 let backup = self.clone();
345 self.map.clone_from(&other.map);
346 return self.union(&backup);
347 }
348
349 let mut did_insert = false;
350 for range in other.iter_intervals() {
351 did_insert |= self.insert_range(range);
352 }
353 if true {
if !self.check_invariants() {
::core::panicking::panic("assertion failed: self.check_invariants()")
};
};debug_assert!(self.check_invariants());
354 did_insert
355 }
356
357 fn check_invariants(&self) -> bool {
359 let mut current: Option<u32> = None;
360 for (start, end) in &self.map {
361 if start > end || current.is_some_and(|x| x + 1 >= *start) {
362 return false;
363 }
364 current = Some(*end);
365 }
366 current.is_none_or(|x| x < self.domain as u32)
367 }
368}
369
370#[derive(#[automatically_derived]impl<R: ::core::clone::Clone, C: ::core::clone::Clone>
::core::clone::Clone for SparseIntervalMatrix<R, C> where R: Idx, C: Idx {
#[inline]
#[rustc_trivial_field_reads]
fn clone(&self) -> Self {
SparseIntervalMatrix {
rows: ::core::clone::Clone::clone(&self.rows),
column_size: ::core::clone::Clone::clone(&self.column_size),
}
}
}Clone)]
376pub struct SparseIntervalMatrix<R, C>
377where
378 R: Idx,
379 C: Idx,
380{
381 rows: IndexVec<R, IntervalSet<C>>,
382 column_size: usize,
383}
384
385impl<R: Idx, C: Step + Idx> SparseIntervalMatrix<R, C> {
386 pub fn new(column_size: usize) -> SparseIntervalMatrix<R, C> {
387 SparseIntervalMatrix { rows: IndexVec::new(), column_size }
388 }
389
390 pub fn rows(&self) -> impl Iterator<Item = R> {
391 self.rows.indices()
392 }
393
394 pub fn row(&self, row: R) -> Option<&IntervalSet<C>> {
395 self.rows.get(row)
396 }
397
398 pub fn iter_enumerated(&self) -> impl Iterator<Item = (R, &IntervalSet<C>)> {
399 self.rows.iter_enumerated()
400 }
401
402 pub fn clear_row(&mut self, row: R) {
403 if let Some(row) = self.rows.get_mut(row) {
404 row.clear();
405 }
406 }
407
408 fn ensure_row(&mut self, row: R) -> &mut IntervalSet<C> {
409 self.rows.ensure_contains_elem(row, || IntervalSet::new(self.column_size))
410 }
411
412 pub fn union_row(&mut self, row: R, from: &IntervalSet<C>) -> bool
413 where
414 C: Step,
415 {
416 self.ensure_row(row).union(from)
417 }
418
419 pub fn union_rows(&mut self, read: R, write: R) -> bool
420 where
421 C: Step,
422 {
423 if read == write || self.rows.get(read).is_none() {
424 return false;
425 }
426 self.ensure_row(write);
427 let (read_row, write_row) = self.rows.pick2_mut(read, write);
428 write_row.union(read_row)
429 }
430
431 pub fn disjoint_rows(&self, a: R, b: R) -> bool
432 where
433 C: Step,
434 {
435 let (Some(a), Some(b)) = (self.rows.get(a), self.rows.get(b)) else {
436 return true;
437 };
438 a.disjoint(b)
439 }
440
441 pub fn insert_all_into_row(&mut self, row: R) {
442 self.ensure_row(row).insert_all();
443 }
444
445 pub fn insert_range(&mut self, row: R, range: impl RangeBounds<C> + Clone) {
446 self.ensure_row(row).insert_range(range);
447 }
448
449 pub fn insert(&mut self, row: R, point: C) -> bool {
450 self.ensure_row(row).insert(point)
451 }
452
453 pub fn append(&mut self, row: R, point: C) {
454 self.ensure_row(row).append(point)
455 }
456
457 pub fn append_range(&mut self, row: R, point: impl RangeBounds<C> + Clone) {
458 self.ensure_row(row).append_range(point)
459 }
460
461 pub fn contains(&self, row: R, point: C) -> bool {
462 self.row(row).is_some_and(|r| r.contains(point))
463 }
464}