// Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
// SPDX-License-Identifier: Apache-2.0
use crate::interval_set::{Interval, IntervalBound, IntervalSetError};
use alloc::collections::VecDeque;
use core::{
cmp::{max, min, Ordering},
num::NonZeroUsize,
ops::Range,
};
#[inline]
pub(crate) fn remove<T: IntervalBound + Ord>(
ranges: &mut VecDeque<Interval<T>>,
range: Interval<T>,
start_index: usize,
limit: Option<NonZeroUsize>,
) -> Result<usize, IntervalSetError> {
// this range is intentionally invalid and will only be
// valid if the `scan` method finds a match
#[allow(clippy::reversed_empty_ranges)]
let replace_range = core::usize::MAX..0;
let can_push_range = limit.map(|l| l.get() > ranges.len() + 1).unwrap_or(true);
let mut removal = Removal {
replace_range,
push_range: None,
can_push_range,
};
let iter = ranges.iter_mut().enumerate().skip(start_index);
if let Some(index) = removal.scan(iter, &range) {
return Ok(index);
}
removal.apply(ranges)
}
/// A structure to keep temporary state for a removal
#[derive(Debug)]
struct Removal<T> {
replace_range: Range<usize>,
push_range: Option<Interval<T>>,
can_push_range: bool,
}
impl<'a, T: 'a + IntervalBound + Ord> Removal<T> {
/// Scans over the Intervals and updates the `Removal` state with the
/// applicable interval ranges
///
/// Returns `Some(index)` if the removal can be applied to a single interval
#[inline]
fn scan<I: Iterator<Item = (usize, &'a mut Interval<T>)>>(
&mut self,
ranges: I,
range_a: &Interval<T>,
) -> Option<usize> {
use Ordering::*;
for (slot_index, range_b) in ranges {
match (
range_a.start.cmp(&range_b.start),
range_a.end.cmp(&range_b.end),
) {
// range A is a subset of range B
//
// Before:
//
// range A: |-----|
// range B: |---------|
//
// After:
//
// range A: |-----|
// range B: |---|
//
(Equal, Less) => {
range_b.start = range_a.end_exclusive();
return Some(slot_index);
}
// range A is a subset of range B
//
// Before:
//
// range A: |-----|
// range B: |---------|
//
// After:
//
// range A: |-----|
// range B: |---|
//
(Greater, Equal) => {
range_b.end = range_a.start_exclusive();
return Some(slot_index + 1);
}
// range A is a subset of range B
//
// Before:
//
// range A: |----|
// range B: |---------|
//
// After:
//
// range A: |----|
// range B: |--| |-|
//
(Greater, Less) => {
self.push_range(range_a.end_exclusive(), range_b.end)?;
range_b.end = range_a.start_exclusive();
let next_slot = slot_index + 1;
self.set_start(next_slot);
self.set_end(next_slot);
break;
}
// range A is part of range B.
//
// Before:
//
// range A: |--------|
// range B: |--------|
//
// After:
//
// range A: |--------|
// range B: |----|
//
(Greater, Greater) if range_a.should_coalesce(range_b) => {
range_b.end = range_a.start_exclusive();
let next_slot = slot_index + 1;
self.set_start(next_slot);
continue;
}
// range A comes later
//
// range A: |-----|
// range B: |----|
//
(Greater, Greater) => {
continue;
}
// range A contains range B, spilling over into the next slot
//
// Before:
//
// range A: |---------|
// range B: |---|
//
// After:
//
// range A: |---------|
// range B: |
//
(Equal, Greater) |
// range A contains range B, spilling over into the next slot
//
// range A: |---------|
// range B: |---|
//
// mark B as obsolete
//
(Less, Greater) => {
self.set_start(slot_index);
let next_slot = slot_index + 1;
self.set_end(next_slot);
continue;
}
// the ranges are equal
//
// range A: |---------|
// range B: |---------|
//
(Equal, Equal) |
// range A ends with range B
//
// range A: |---------|
// range B: |---|
//
// mark B as obsolete
//
(Less, Equal) => {
self.set_start(slot_index);
let next_slot = slot_index + 1;
self.set_end(next_slot);
break;
}
// range A overlaps part of range B
//
// Before:
//
// range A: |--------|
// range B: |--------|
//
// After:
//
// range A: |--------|
// range B: |----|
//
(Less, Less) if range_b.should_coalesce(range_a) => {
range_b.start = range_a.end_exclusive();
self.set_end(slot_index);
break;
}
// range A comes before range B
//
// range A: |---|
// range B: |--------|
//
// returns; no more searching needed
//
(Less, Less) => {
break;
}
}
}
None
}
/// Applies the `Removal` to the given set of `Interval`s.
#[inline]
fn apply(self, ranges: &mut VecDeque<Interval<T>>) -> Result<usize, IntervalSetError> {
let replace_range = self.replace_range;
let index = replace_range.start;
if let Some(interval) = self.push_range {
if self.can_push_range {
ranges.insert(index, interval);
return Ok(index);
} else {
return Err(IntervalSetError::LimitExceeded);
}
}
match replace_range.end.checked_sub(index) {
None => Ok(0),
Some(0) => Ok(index),
Some(1) => {
ranges.remove(index);
Ok(index)
}
Some(_) => {
ranges.drain(replace_range);
Ok(index)
}
}
}
#[inline]
fn set_start(&mut self, start: usize) {
self.replace_range.start = min(self.replace_range.start, start);
}
#[inline]
fn set_end(&mut self, end: usize) {
self.replace_range.end = max(self.replace_range.end, end);
}
#[inline]
fn push_range(&mut self, start: T, end: T) -> Option<()> {
debug_assert!(self.push_range.is_none());
self.push_range = Some(Interval { start, end });
if self.can_push_range {
Some(())
} else {
None
}
}
}