use super::IntervalOps;
pub struct MergeDomain<T: IntervalOps> {
pub items: Vec<T>,
}
impl<T: IntervalOps> MergeDomain<T> {
pub fn from_intervals(mut intervals: Vec<T>) -> Self {
intervals.sort_by(|a, b| a.min().partial_cmp(&b.min()).unwrap());
let mut items: Vec<T> = Vec::with_capacity(intervals.len());
for x in intervals {
match items.last_mut() {
Some(last) if last.overlaps(x) => {
*last = x.new_containing(last);
}
_ => items.push(x),
}
}
let mut constructed = MergeDomain { items };
constructed.mut_resolve_wrap();
constructed
}
pub fn new_empty() -> Self {
MergeDomain { items: Vec::new() }
}
pub fn is_empty(&self) -> bool {
self.items.is_empty()
}
pub fn len(&self) -> usize {
self.items.len()
}
pub fn insert(&mut self, item: T) {
let search = self
.items
.binary_search_by(|i| i.min().partial_cmp(&item.min()).unwrap());
let check_i = search.unwrap_or_else(|i| i);
let overlaps = self.find_overlaps_no_wrap(&item, check_i.saturating_sub(1));
if overlaps.is_empty() {
self.items.insert(check_i, item);
} else {
let mut working = item;
for i in overlaps.iter().rev() {
let popped = self.items.remove(*i);
working = working.new_containing(&popped);
}
self.items.insert(overlaps[0], working);
}
self.mut_resolve_wrap();
}
fn mut_resolve_wrap(&mut self) {
if T::wraps() && self.items.len() > 2 {
if self.items[0].overlaps(self.items[self.items.len() - 1]) {
let last = self.items.pop().unwrap();
self.items[0] = last.new_containing(&self.items[0]);
}
}
}
fn find_overlaps_no_wrap(&self, item: &T, start_i: usize) -> Vec<usize> {
let mut overlaps = vec![];
for i in start_i..self.items.len() {
if self.items[i].min() > item.max() {
break;
}
if item.overlaps(self.items[i]) {
overlaps.push(i);
}
}
overlaps
}
pub fn modify_at(&'_ mut self, index: usize) -> Option<ItemEditHandle<'_, T>> {
if index < self.items.len() {
Some(ItemEditHandle {
domain: self,
index,
})
} else {
None
}
}
pub fn modify_all(&'_ mut self, action: &dyn Fn(T) -> Option<T>) {
let modified = self
.items
.iter()
.filter_map(|item| action(*item))
.filter(|item| !item.is_empty())
.collect::<Vec<_>>();
let surrogate = Self::from_intervals(modified);
self.items = surrogate.items;
}
}
#[allow(dead_code)] enum ModAct<T: IntervalOps> {
None,
Delete,
Replace(T),
}
#[allow(dead_code)] pub trait IntervalHandleEdit<T: IntervalOps> {
fn delete(self);
fn replace(self, item: T);
fn modify(self, action: &dyn Fn(&T) -> Option<T>);
}
pub struct ItemEditHandle<'a, T: IntervalOps> {
domain: &'a mut MergeDomain<T>,
index: usize,
}
impl<'a, T: IntervalOps> ItemEditHandle<'a, T> {
pub fn item(&self) -> &T {
&self.domain.items[self.index]
}
}
impl<'a, T: IntervalOps> IntervalHandleEdit<T> for ItemEditHandle<'a, T> {
fn delete(self) {
self.domain.items.remove(self.index);
}
fn replace(self, item: T) {
self.domain.items.remove(self.index);
if !item.is_empty() {
self.domain.insert(item);
}
}
fn modify(self, action: &dyn Fn(&T) -> Option<T>) {
if let Some(result) = action(self.item()) {
self.replace(result);
} else {
self.delete();
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::common::IntervalMergeDomain;
use crate::common::interval::{Interval, IntervalMerge};
fn no_overlaps(x: &IntervalMerge) -> bool {
for i in 0..x.items.len() {
for k in i + 1..x.items.len() {
if x.items[i].overlaps(x.items[k]) {
return false;
}
}
}
true
}
fn is_sorted(x: &IntervalMerge) -> bool {
for i in 0..(x.items.len().saturating_sub(1)) {
if x.items[i + 1].min < x.items[i].min {
return false;
}
}
true
}
fn interval(min: f64, max: f64) -> Interval {
Interval::new(min, max)
}
#[test]
fn insert_into_empty() {
let mut d = IntervalMerge::new_empty();
d.insert(interval(1.0, 3.0));
assert_eq!(d.items.len(), 1);
assert_eq!(d.items[0].min, 1.0);
assert_eq!(d.items[0].max, 3.0);
}
#[test]
fn insert_two_disjoint_in_order() {
let mut d = IntervalMerge::new_empty();
d.insert(interval(0.0, 1.0));
d.insert(interval(2.0, 3.0));
assert_eq!(d.items.len(), 2);
assert!(is_sorted(&d));
assert!(no_overlaps(&d));
assert_eq!(d.items[0].min, 0.0);
assert_eq!(d.items[1].min, 2.0);
}
#[test]
fn insert_two_disjoint_reverse_order() {
let mut d = IntervalMerge::new_empty();
d.insert(interval(2.0, 3.0));
d.insert(interval(0.0, 1.0));
assert_eq!(d.items.len(), 2);
assert!(is_sorted(&d));
assert!(no_overlaps(&d));
assert_eq!(d.items[0].min, 0.0);
assert_eq!(d.items[1].min, 2.0);
}
#[test]
fn insert_three_disjoint_random_order() {
let mut d = IntervalMerge::new_empty();
d.insert(interval(4.0, 5.0));
d.insert(interval(0.0, 1.0));
d.insert(interval(2.0, 3.0));
assert_eq!(d.items.len(), 3);
assert!(is_sorted(&d));
assert!(no_overlaps(&d));
}
#[test]
fn insert_overlapping_merges() {
let mut d = IntervalMerge::new_empty();
d.insert(interval(0.0, 2.0));
d.insert(interval(1.0, 3.0));
assert_eq!(d.items.len(), 1);
assert_eq!(d.items[0].min, 0.0);
assert_eq!(d.items[0].max, 3.0);
}
#[test]
fn insert_contained_interval() {
let mut d = IntervalMerge::new_empty();
d.insert(interval(0.0, 10.0));
d.insert(interval(3.0, 7.0));
assert_eq!(d.items.len(), 1);
assert_eq!(d.items[0].min, 0.0);
assert_eq!(d.items[0].max, 10.0);
}
#[test]
fn insert_containing_interval() {
let mut d = IntervalMerge::new_empty();
d.insert(interval(3.0, 7.0));
d.insert(interval(0.0, 10.0));
assert_eq!(d.items.len(), 1);
assert_eq!(d.items[0].min, 0.0);
assert_eq!(d.items[0].max, 10.0);
}
#[test]
fn insert_bridges_two_existing() {
let mut d = IntervalMerge::new_empty();
d.insert(interval(0.0, 1.0));
d.insert(interval(3.0, 4.0));
d.insert(interval(0.5, 3.5)); assert_eq!(d.items.len(), 1);
assert_eq!(d.items[0].min, 0.0);
assert_eq!(d.items[0].max, 4.0);
assert!(is_sorted(&d));
assert!(no_overlaps(&d));
}
#[test]
fn insert_bridges_three_existing() {
let mut d = IntervalMerge::new_empty();
d.insert(interval(0.0, 1.0));
d.insert(interval(2.0, 3.0));
d.insert(interval(4.0, 5.0));
d.insert(interval(0.5, 4.5)); assert_eq!(d.items.len(), 1);
assert_eq!(d.items[0].min, 0.0);
assert_eq!(d.items[0].max, 5.0);
}
#[test]
fn from_intervals_empty() {
let d = IntervalMerge::from_intervals(vec![]);
assert_eq!(d.items.len(), 0);
}
#[test]
fn from_intervals_disjoint_unsorted() {
let d = IntervalMerge::from_intervals(vec![
interval(4.0, 5.0),
interval(0.0, 1.0),
interval(2.0, 3.0),
]);
assert_eq!(d.items.len(), 3);
assert!(is_sorted(&d));
assert!(no_overlaps(&d));
assert_eq!(d.items[0].min, 0.0);
assert_eq!(d.items[1].min, 2.0);
assert_eq!(d.items[2].min, 4.0);
}
#[test]
fn from_intervals_with_overlaps() {
let d = IntervalMerge::from_intervals(vec![
interval(0.0, 2.0),
interval(3.0, 5.0),
interval(1.5, 4.0), ]);
assert_eq!(d.items.len(), 1);
assert_eq!(d.items[0].min, 0.0);
assert_eq!(d.items[0].max, 5.0);
}
#[test]
fn from_intervals_mixed() {
let d = IntervalMerge::from_intervals(vec![
interval(0.0, 1.0),
interval(0.5, 1.5), interval(3.0, 4.0),
interval(3.5, 5.0), interval(7.0, 8.0), ]);
assert_eq!(d.items.len(), 3);
assert!(is_sorted(&d));
assert!(no_overlaps(&d));
assert_eq!(d.items[0].min, 0.0);
assert_eq!(d.items[0].max, 1.5);
assert_eq!(d.items[1].min, 3.0);
assert_eq!(d.items[1].max, 5.0);
assert_eq!(d.items[2].min, 7.0);
assert_eq!(d.items[2].max, 8.0);
}
#[test]
fn modify_at_remove() {
let mut d = IntervalMerge::new_empty();
d.insert(interval(0.0, 1.0));
d.insert(interval(2.0, 3.0));
d.insert(interval(4.0, 5.0));
let h = d.modify_at(1).unwrap();
assert_eq!(h.item().min, 2.0);
h.delete();
assert_eq!(d.items.len(), 2);
assert_eq!(d.items[0].min, 0.0);
assert_eq!(d.items[1].min, 4.0);
}
#[test]
fn modify_at_no_action_is_noop() {
let mut d = IntervalMerge::new_empty();
d.insert(interval(0.0, 1.0));
d.modify_at(0).unwrap();
assert_eq!(d.items.len(), 1);
}
#[test]
fn modify_at_replace_merges() {
let mut d = IntervalMerge::new_empty();
d.insert(interval(0.0, 1.0));
d.insert(interval(5.0, 6.0));
d.modify_at(0).unwrap().replace(interval(0.0, 5.5)); assert_eq!(d.items.len(), 1);
assert_eq!(d.items[0].min, 0.0);
assert_eq!(d.items[0].max, 6.0);
}
#[test]
fn modify_at_set_zero_length_removes() {
let mut d = IntervalMerge::new_empty();
d.insert(interval(0.0, 1.0));
d.insert(interval(2.0, 3.0));
d.modify_at(0).unwrap().replace(interval(0.5, 0.5));
assert_eq!(d.items.len(), 1);
assert_eq!(d.items[0].min, 2.0);
}
#[test]
fn modify_at_out_of_bounds() {
let mut d = IntervalMergeDomain::empty();
d.insert(interval(0.0, 1.0));
assert!(d.modify_at(1).is_none());
}
}