use crate::interval::Interval;
use crate::interval::ToInterval;
use crate::ops::*;
use trilean::SKleene;
use gcollections::*;
use gcollections::ops::*;
use std::iter::{Peekable, IntoIterator};
use std::fmt::{Formatter, Display, Error};
use std::ops::{Add, Sub, Mul};
use num_traits::{Zero, Num};
#[derive(Debug, Clone)]
pub struct IntervalSet<Bound: Width> {
intervals: Vec<Interval<Bound>>,
size: Bound::Output
}
impl<Bound: Width> IntervalKind for IntervalSet<Bound> {}
impl<Bound: Width> Collection for IntervalSet<Bound>
{
type Item = Bound;
}
impl<Bound: Width> IntoIterator for IntervalSet<Bound>
{
type Item = Interval<Bound>;
type IntoIter = ::std::vec::IntoIter<Self::Item>;
fn into_iter(self) -> Self::IntoIter {
self.intervals.into_iter()
}
}
impl<'a, Bound: Width> IntoIterator for &'a IntervalSet<Bound>
{
type Item = &'a Interval<Bound>;
type IntoIter = ::std::slice::Iter<'a, Interval<Bound>>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a, Bound: Width> IntoIterator for &'a mut IntervalSet<Bound>
{
type Item = &'a mut Interval<Bound>;
type IntoIter = ::std::slice::IterMut<'a, Interval<Bound>>;
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl<Bound: Width> IntervalSet<Bound>
{
pub fn iter(&self) -> ::std::slice::Iter<Interval<Bound>> {
self.intervals.iter()
}
pub fn iter_mut(&mut self) -> ::std::slice::IterMut<Interval<Bound>> {
self.intervals.iter_mut()
}
}
impl<Bound> IntervalSet<Bound> where
Bound: Width + Num
{
pub fn interval_count(&self) -> usize {
self.intervals.len()
}
fn from_interval(i: Interval<Bound>) -> IntervalSet<Bound> {
let size = i.size().clone();
IntervalSet {
intervals: vec![i],
size
}
}
fn front(&self) -> &Interval<Bound> {
debug_assert!(!self.is_empty(), "Cannot access the first interval of an empty set.");
&self.intervals[0]
}
fn back_idx(&self) -> usize {
self.intervals.len() - 1
}
fn back(&self) -> &Interval<Bound> {
debug_assert!(!self.is_empty(), "Cannot access the last interval of an empty set.");
&self.intervals[self.back_idx()]
}
fn span(&self) -> Interval<Bound> {
if self.is_empty() {
Interval::empty()
}
else {
self.span_slice(0, self.back_idx())
}
}
fn span_slice(&self, left: usize, right: usize) -> Interval<Bound> {
Interval::new(
self.intervals[left].lower(),
self.intervals[right].upper()
)
}
fn push(&mut self, x: Interval<Bound>) {
debug_assert!(!x.is_empty(), "Cannot push empty interval.");
debug_assert!(self.is_empty() || !joinable(self.back(), &x),
"The intervals array must be ordered and intervals must not be joinable. For a safe push, use the union operation.");
self.size = self.size.clone() + x.size();
self.intervals.push(x);
}
fn pop(&mut self) -> Option<Interval<Bound>> {
if let Some(x) = self.intervals.pop() {
self.size = self.size.clone() - x.size();
Some(x)
} else {
None
}
}
fn join_or_push(&mut self, x: Interval<Bound>) {
if self.is_empty() {
self.push(x);
}
else {
debug_assert!(!x.is_empty(), "Cannot push empty interval.");
debug_assert!(self.back().lower() <= x.lower(),
"This operation is only for pushing interval to the back of the array, possibly overlapping with the last element.");
let joint =
if joinable(self.back(), &x) {
self.pop().unwrap().hull(&x)
}
else {
x
};
self.push(joint);
}
}
fn extend_at_back<I>(&mut self, iterable: I) where
I: IntoIterator<Item=Interval<Bound>>,
Bound: PartialOrd
{
for interval in iterable {
self.join_or_push(interval);
}
}
fn find_interval_between(&self, value: &Bound,
mut left: usize, mut right: usize) -> (usize, usize)
{
debug_assert!(left <= right);
debug_assert!(right < self.intervals.len());
debug_assert!(self.span_slice(left, right).contains(value));
while left <= right {
let mid_idx = left + (right - left) / 2;
let mid = &self.intervals[mid_idx];
if &mid.lower() > value {
right = mid_idx - 1;
}
else if &mid.upper() < value {
left = mid_idx + 1;
}
else {
return (mid_idx, mid_idx)
}
}
(right, left)
}
fn find_interval(&self, value: &Bound) -> Option<(usize, usize)> {
if !self.span().contains(value) {
None
}
else {
Some(self.find_interval_between(value, 0, self.back_idx()))
}
}
fn for_all_pairs<F>(&self, other: &IntervalSet<Bound>, f: F) -> IntervalSet<Bound> where
F: Fn(&Interval<Bound>, &Interval<Bound>) -> Interval<Bound>
{
let mut res = IntervalSet::empty();
for i in &self.intervals {
for j in &other.intervals {
res = res.union(&IntervalSet::from_interval(f(i,j)));
}
}
res
}
fn stable_map<F>(&self, f: F) -> IntervalSet<Bound> where
F: Fn(&Interval<Bound>) -> Interval<Bound>
{
IntervalSet {
intervals: self.intervals.iter().map(f).collect(),
size: self.size.clone()
}
}
fn map<F>(&self, f: F) -> IntervalSet<Bound> where
F: Fn(&Interval<Bound>) -> Interval<Bound>
{
self.intervals.iter().fold(IntervalSet::empty(),
|mut r, i| { r.push(f(i)); r })
}
}
fn joinable<Bound>(first: &Interval<Bound>, second: &Interval<Bound>) -> bool where
Bound: Width + Num
{
if first.upper() == Bound::max_value() { true }
else { first.upper() + Bound::one() >= second.lower() }
}
impl<Bound> Extend<Interval<Bound>> for IntervalSet<Bound> where
Bound: Width + Num
{
fn extend<I>(&mut self, iterable: I) where
I: IntoIterator<Item=Interval<Bound>>
{
let mut intervals: Vec<_> = iterable.into_iter().map(|i| i.to_interval()).collect();
intervals.sort_unstable_by_key(|i| i.lower());
let mut set = IntervalSet::empty();
set.extend_at_back(intervals);
*self = self.union(&set);
}
}
impl<Bound: Width + Num> Eq for IntervalSet<Bound> {}
impl<Bound> PartialEq<IntervalSet<Bound>> for IntervalSet<Bound> where
Bound: Width + Num
{
fn eq(&self, other: &IntervalSet<Bound>) -> bool {
if self.size() != other.size() { false }
else {
self.intervals == other.intervals
}
}
}
impl<Bound> Range for IntervalSet<Bound> where
Bound: Width + Num
{
fn new(lb: Bound, ub: Bound) -> IntervalSet<Bound> {
debug_assert!(lb <= ub, "Cannot build empty interval set with an invalid range. use crate::intervalSet::empty().");
let i = Interval::new(lb, ub);
IntervalSet::from_interval(i)
}
}
impl<Bound> Whole for IntervalSet<Bound> where
Bound: Width + Num
{
fn whole() -> IntervalSet<Bound> {
let mut res = IntervalSet::empty();
res.push(Interval::whole());
res
}
}
impl<Bound> Bounded for IntervalSet<Bound> where
Bound: Width + Num + PartialOrd
{
fn lower(&self) -> Bound {
debug_assert!(!self.is_empty(), "Cannot access lower bound on empty interval.");
self.front().lower()
}
fn upper(&self) -> Bound {
debug_assert!(!self.is_empty(), "Cannot access upper bound on empty interval.");
self.back().upper()
}
}
impl <Bound: Width+Num> Singleton for IntervalSet<Bound>
{
fn singleton(x: Bound) -> IntervalSet<Bound> {
IntervalSet::new(x.clone(), x)
}
}
impl<Bound: Width+Num> Empty for IntervalSet<Bound>
{
fn empty() -> IntervalSet<Bound> {
IntervalSet {
intervals: vec![],
size: <<Bound as Width>::Output>::zero()
}
}
}
impl<Bound: Width+Num> Cardinality for IntervalSet<Bound>
{
type Size = <Bound as Width>::Output;
fn size(&self) -> <Bound as Width>::Output {
self.size.clone()
}
}
impl<Bound: Width+Num> Contains for IntervalSet<Bound>
{
fn contains(&self, value: &Bound) -> bool {
if let Some((left, right)) = self.find_interval(value) {
left == right
} else {
false
}
}
}
fn advance_one<I, F, Item>(a : &mut Peekable<I>, b: &mut Peekable<I>, choose: F) -> Item where
I: Iterator<Item=Item>,
F: Fn(&Item, &Item) -> bool,
Item: Bounded
{
static NON_EMPTY_PRECONDITION: &str =
"`advance_one` expects both interval iterators to be non_empty.";
let who_advance = {
let i = a.peek().expect(NON_EMPTY_PRECONDITION);
let j = b.peek().expect(NON_EMPTY_PRECONDITION);
choose(i, j)
};
let to_advance = if who_advance { a } else { b };
to_advance.next().unwrap()
}
fn advance_lower<I, Item, B>(a : &mut Peekable<I>, b: &mut Peekable<I>) -> Item where
I: Iterator<Item=Item>,
Item: Bounded + Collection<Item=B>,
B: Ord
{
advance_one(a, b, |i,j| i.lower() < j.lower())
}
fn advance_lub<I, Item, B>(a : &mut Peekable<I>, b: &mut Peekable<I>) -> Item where
I: Iterator<Item=Item>,
Item: Bounded + Collection<Item=B>,
B: Ord
{
advance_one(a, b, |i, j| i.upper() < j.upper())
}
fn from_lower_iterator<I, Bound>(a : &mut Peekable<I>, b: &mut Peekable<I>) -> IntervalSet<Bound> where
I: Iterator<Item=Interval<Bound>>,
Bound: Width+Num
{
if a.peek().is_none() || b.peek().is_none() {
IntervalSet::empty()
} else {
let first = advance_lower(a, b);
IntervalSet::from_interval(first)
}
}
impl<Bound> Union<Bound> for IntervalSet<Bound> where
Bound: Width + Num + Clone
{
type Output = IntervalSet<Bound>;
fn union(&self, rhs: &Bound) -> IntervalSet<Bound> {
self.union(&IntervalSet::singleton(rhs.clone()))
}
}
impl<Bound: Width+Num> Union for IntervalSet<Bound>
{
type Output = IntervalSet<Bound>;
fn union(&self, rhs: &IntervalSet<Bound>) -> IntervalSet<Bound> {
let a = &mut self.intervals.iter().cloned().peekable();
let b = &mut rhs.intervals.iter().cloned().peekable();
let mut res = from_lower_iterator(a, b);
while a.peek().is_some() && b.peek().is_some() {
let lower = advance_lower(a, b);
res.join_or_push(lower);
}
res.extend_at_back(a);
res.extend_at_back(b);
res
}
}
fn advance_to_first_overlapping<I, Item, B>(a : &mut Peekable<I>, b: &mut Peekable<I>) -> bool where
I: Iterator<Item=Item>,
Item: Bounded + Overlap + Collection<Item=B>,
B: Ord
{
while a.peek().is_some() && b.peek().is_some() {
let overlapping = {
let i = a.peek().unwrap();
let j = b.peek().unwrap();
i.overlap(j)
};
if overlapping {
return true
} else {
advance_lower(a, b);
}
}
false
}
impl<Bound> Intersection<Bound> for IntervalSet<Bound> where
Bound: Width + Num + Clone
{
type Output = IntervalSet<Bound>;
fn intersection(&self, rhs: &Bound) -> IntervalSet<Bound> {
self.intersection(&IntervalSet::singleton(rhs.clone()))
}
}
impl<Bound: Width+Num> Intersection for IntervalSet<Bound>
{
type Output = IntervalSet<Bound>;
fn intersection(&self, rhs: &IntervalSet<Bound>) -> IntervalSet<Bound> {
let a = &mut self.intervals.iter().cloned().peekable();
let b = &mut rhs.intervals.iter().cloned().peekable();
let mut res = IntervalSet::empty();
while advance_to_first_overlapping(a, b) {
{
let i = a.peek().unwrap();
let j = b.peek().unwrap();
res.push(i.intersection(j));
}
advance_lub(a, b); }
res
}
}
fn push_left_complement<Bound: Width+Num>(x: &Interval<Bound>, res: &mut IntervalSet<Bound>) {
let min = <Bound as Width>::min_value();
if x.lower() != min {
res.push(Interval::new(min, x.lower() - Bound::one()));
}
}
fn push_right_complement<Bound: Width+Num>(x: &Interval<Bound>, res: &mut IntervalSet<Bound>) {
let max = <Bound as Width>::max_value();
if x.upper() != max {
res.push(Interval::new(x.upper() + Bound::one(), max));
}
}
impl<Bound: Width+Num> Complement for IntervalSet<Bound>
{
fn complement(&self) -> IntervalSet<Bound> {
let mut res = IntervalSet::empty();
if self.is_empty() {
res.push(Interval::whole());
}
else {
let one = Bound::one();
push_left_complement(self.front(), &mut res);
for i in 1..self.intervals.len() {
let current = &self.intervals[i];
let previous = &self.intervals[i-1];
res.push(Interval::new(
previous.upper() + one.clone(),
current.lower() - one.clone()));
}
push_right_complement(self.back(), &mut res);
}
res
}
}
impl<Bound> Difference<Bound> for IntervalSet<Bound> where
Bound: Width + Num + Clone
{
type Output = IntervalSet<Bound>;
fn difference(&self, rhs: &Bound) -> IntervalSet<Bound> {
self.difference(&IntervalSet::singleton(rhs.clone()))
}
}
impl<Bound: Width+Num> Difference for IntervalSet<Bound> {
type Output = IntervalSet<Bound>;
fn difference(&self, rhs: &IntervalSet<Bound>) -> IntervalSet<Bound> {
self.intersection(&rhs.complement())
}
}
impl<Bound> SymmetricDifference<Bound> for IntervalSet<Bound> where
Bound: Width + Num + Clone
{
type Output = IntervalSet<Bound>;
fn symmetric_difference(&self, rhs: &Bound) -> IntervalSet<Bound> {
self.symmetric_difference(&IntervalSet::singleton(rhs.clone()))
}
}
impl<Bound: Width+Num> SymmetricDifference for IntervalSet<Bound> {
type Output = IntervalSet<Bound>;
fn symmetric_difference(&self, rhs: &IntervalSet<Bound>) -> IntervalSet<Bound> {
let union = self.union(rhs);
let intersection = self.intersection(rhs);
union.difference(&intersection)
}
}
impl<Bound: Width+Num> Overlap for IntervalSet<Bound> {
fn overlap(&self, rhs: &IntervalSet<Bound>) -> bool {
let a = &mut self.intervals.iter().cloned().peekable();
let b = &mut rhs.intervals.iter().cloned().peekable();
advance_to_first_overlapping(a, b)
}
}
impl<Bound: Width+Num> Overlap<Bound> for IntervalSet<Bound> {
fn overlap(&self, value: &Bound) -> bool {
if let Some((l, u)) = self.find_interval(value) {
l == u
}
else {
false
}
}
}
impl<Bound: Width+Num> Overlap<Optional<Bound>> for IntervalSet<Bound> {
fn overlap(&self, value: &Optional<Bound>) -> bool {
value.as_ref().map_or(false, |b| self.overlap(b))
}
}
macro_rules! primitive_interval_set_overlap
{
( $( $source:ty ),* ) =>
{$(
impl Overlap<IntervalSet<$source>> for $source {
fn overlap(&self, other: &IntervalSet<$source>) -> bool {
other.overlap(self)
}
}
)*}
}
primitive_interval_set_overlap!(i8,u8,i16,u16,i32,u32,i64,u64,isize,usize);
impl<Bound: Width+Num> Disjoint for IntervalSet<Bound> {
fn is_disjoint(&self, rhs: &IntervalSet<Bound>) -> bool {
!self.overlap(rhs)
}
}
impl<Bound: Width+Num> ShrinkLeft for IntervalSet<Bound> where
<Bound as Width>::Output: Clone
{
fn shrink_left(&self, lb: Bound) -> IntervalSet<Bound> {
if let Some((left, _)) = self.find_interval(&lb) {
let mut res = IntervalSet::empty();
if self.intervals[left].upper() >= lb {
res.push(Interval::new(lb, self.intervals[left].upper()));
}
for i in (left+1)..self.intervals.len() {
res.push(self.intervals[i].clone());
}
res
}
else if self.is_empty() || lb > self.back().upper() {
IntervalSet::empty()
} else {
self.clone()
}
}
}
impl<Bound: Width+Num> ShrinkRight for IntervalSet<Bound> where
<Bound as Width>::Output: Clone
{
fn shrink_right(&self, ub: Bound) -> IntervalSet<Bound> {
if let Some((_, right)) = self.find_interval(&ub) {
let mut res = IntervalSet::empty();
for i in 0..right {
res.push(self.intervals[i].clone());
}
if self.intervals[right].lower() <= ub {
res.push(Interval::new(self.intervals[right].lower(), ub));
}
res
}
else if self.is_empty() || ub < self.front().lower() {
IntervalSet::empty()
} else {
self.clone()
}
}
}
impl<Bound: Width+Num> Subset for IntervalSet<Bound>
{
fn is_subset(&self, other: &IntervalSet<Bound>) -> bool {
if self.is_empty() { true }
else if self.size() > other.size() || !self.span().is_subset(&other.span()) { false }
else {
let mut left = 0;
let right = other.intervals.len() - 1;
for interval in &self.intervals {
let (l, r) = other.find_interval_between(&interval.lower(), left, right);
if l == r && interval.is_subset(&other.intervals[l]) {
left = l;
} else {
return false;
}
}
true
}
}
}
impl<Bound: Width+Num> ProperSubset for IntervalSet<Bound>
{
fn is_proper_subset(&self, other: &IntervalSet<Bound>) -> bool {
self.is_subset(other) && self.size() != other.size()
}
}
forward_all_binop!(impl<Bound: +Num+Width> Add for IntervalSet<Bound>, add);
impl<'a, 'b, Bound: Num+Width> Add<&'b IntervalSet<Bound>> for &'a IntervalSet<Bound> {
type Output = IntervalSet<Bound>;
fn add(self, other: &IntervalSet<Bound>) -> IntervalSet<Bound> {
self.for_all_pairs(other, |i, j| i + j)
}
}
forward_all_binop!(impl<Bound: +Num+Width+Clone> Add for IntervalSet<Bound>, add, Bound);
impl<'a, 'b, Bound: Num+Width+Clone> Add<&'b Bound> for &'a IntervalSet<Bound> {
type Output = IntervalSet<Bound>;
fn add(self, other: &Bound) -> IntervalSet<Bound> {
self.stable_map(|x| x + other.clone())
}
}
forward_all_binop!(impl<Bound: +Num+Width> Sub for IntervalSet<Bound>, sub);
impl<'a, 'b, Bound: Num+Width> Sub<&'b IntervalSet<Bound>> for &'a IntervalSet<Bound> {
type Output = IntervalSet<Bound>;
fn sub(self, other: &IntervalSet<Bound>) -> IntervalSet<Bound> {
self.for_all_pairs(other, |i, j| i - j)
}
}
forward_all_binop!(impl<Bound: +Num+Width+Clone> Sub for IntervalSet<Bound>, sub, Bound);
impl<'a, 'b, Bound: Num+Width+Clone> Sub<&'b Bound> for &'a IntervalSet<Bound> {
type Output = IntervalSet<Bound>;
fn sub(self, other: &Bound) -> IntervalSet<Bound> {
self.stable_map(|x| x - other.clone())
}
}
forward_all_binop!(impl<Bound: +Num+Width> Mul for IntervalSet<Bound>, mul);
impl<'a, 'b, Bound: Num+Width> Mul<&'b IntervalSet<Bound>> for &'a IntervalSet<Bound> {
type Output = IntervalSet<Bound>;
fn mul(self, other: &IntervalSet<Bound>) -> IntervalSet<Bound> {
self.for_all_pairs(other, |i, j| i * j)
}
}
forward_all_binop!(impl<Bound: +Num+Width+Clone> Mul for IntervalSet<Bound>, mul, Bound);
impl<'a, 'b, Bound: Num+Width+Clone> Mul<&'b Bound> for &'a IntervalSet<Bound> {
type Output = IntervalSet<Bound>;
fn mul(self, other: &Bound) -> IntervalSet<Bound> {
if self.is_empty() {
IntervalSet::empty()
} else if other == &Bound::zero() {
IntervalSet::singleton(Bound::zero())
} else if other == &Bound::one() {
self.clone()
} else {
self.map(|i| i * other.clone())
}
}
}
pub trait ToIntervalSet<Bound> where
Bound: Width
{
fn to_interval_set(self) -> IntervalSet<Bound>;
}
impl<Bound: Width+Num> ToIntervalSet<Bound> for (Bound, Bound)
{
fn to_interval_set(self) -> IntervalSet<Bound> {
vec![self].to_interval_set()
}
}
impl<Bound> ToIntervalSet<Bound> for Vec<(Bound, Bound)> where
Bound: Width + Num
{
fn to_interval_set(self) -> IntervalSet<Bound> {
let mut intervals = IntervalSet::empty();
let mut to_add: Vec<_> = self.into_iter().map(|i| i.to_interval()).collect();
to_add.sort_unstable_by_key(|i| i.lower());
intervals.extend_at_back(to_add);
intervals
}
}
impl<Bound: Display+Width+Num> Display for IntervalSet<Bound> where
<Bound as Width>::Output: Display
{
fn fmt(&self, formatter: &mut Formatter) -> Result<(), Error> {
if self.intervals.len() == 1 {
self.intervals[0].fmt(formatter)
}
else {
formatter.write_str("{")?;
for interval in &self.intervals {
formatter.write_fmt(format_args!("{}", interval))?;
}
formatter.write_str("}")
}
}
}
impl<Bound> Join for IntervalSet<Bound> where
Bound: Width + Num
{
fn join(self, other: IntervalSet<Bound>) -> IntervalSet<Bound> {
self.intersection(&other)
}
}
impl<Bound> Meet for IntervalSet<Bound> where
Bound: Width + Num
{
fn meet(self, other: IntervalSet<Bound>) -> IntervalSet<Bound> {
self.union(&other)
}
}
impl<Bound> Entailment for IntervalSet<Bound> where
Bound: Width + Num
{
fn entail(&self, other: &IntervalSet<Bound>) -> SKleene {
if self.is_subset(other) {
SKleene::True
}
else if other.is_subset(self) {
SKleene::False
}
else {
SKleene::Unknown
}
}
}
impl<Bound> Top for IntervalSet<Bound> where
Bound: Width + Num
{
fn top() -> IntervalSet<Bound> {
IntervalSet::empty()
}
}
impl<Bound> Bot for IntervalSet<Bound> where
Bound: Width + Num
{
fn bot() -> IntervalSet<Bound> {
IntervalSet::whole()
}
}
#[allow(non_upper_case_globals)]
#[cfg(test)]
mod tests {
use super::*;
const extend_example: [(i32, i32); 2] = [
(11, 33),
(-55, -44),
];
fn test_inside_outside(is: IntervalSet<i32>, inside: Vec<i32>, outside: Vec<i32>) {
for i in &inside {
assert!(is.contains(i),
"{} is not contained inside {}, but it should.", i, is);
}
for i in &outside {
assert!(!is.contains(i),
"{} is contained inside {}, but it should not.", i, is);
}
}
fn make_interval_set(intervals: Vec<(i32, i32)>) -> IntervalSet<i32> {
intervals.to_interval_set()
}
fn test_result(test_id: String, result: &IntervalSet<i32>, expected: &IntervalSet<i32>) {
assert!(result.intervals == expected.intervals,
"{} | {} is different from the expected value: {}.", test_id, result, expected);
}
fn test_binary_op_sym<F>(test_id: String, a: Vec<(i32,i32)>, b: Vec<(i32,i32)>, op: F, expected: Vec<(i32,i32)>) where
F: Fn(&IntervalSet<i32>, &IntervalSet<i32>) -> IntervalSet<i32>
{
test_binary_op(test_id.clone(), a.clone(), b.clone(), |i,j| op(i,j), expected.clone());
test_binary_op(test_id, b, a, op, expected);
}
fn test_binary_op<F>(test_id: String, a: Vec<(i32,i32)>, b: Vec<(i32,i32)>, op: F, expected: Vec<(i32,i32)>) where
F: Fn(&IntervalSet<i32>, &IntervalSet<i32>) -> IntervalSet<i32>
{
println!("Info: {}.", test_id);
let a = make_interval_set(a);
let b = make_interval_set(b);
let expected = make_interval_set(expected);
test_result(test_id, &op(&a, &b), &expected);
}
fn test_binary_value_op<F>(test_id: String, a: Vec<(i32,i32)>, b: i32, op: F, expected: Vec<(i32,i32)>) where
F: Fn(&IntervalSet<i32>, i32) -> IntervalSet<i32>
{
println!("Info: {}.", test_id);
let a = make_interval_set(a);
let expected = make_interval_set(expected);
test_result(test_id, &op(&a, b), &expected);
}
fn test_binary_bool_op_sym<F>(test_id: String, a: Vec<(i32,i32)>, b: Vec<(i32,i32)>, op: F, expected: bool) where
F: Fn(&IntervalSet<i32>, &IntervalSet<i32>) -> bool
{
test_binary_bool_op(test_id.clone(), a.clone(), b.clone(), |i,j| op(i,j), expected);
test_binary_bool_op(test_id, b, a, op, expected);
}
fn test_binary_bool_op<F>(test_id: String, a: Vec<(i32,i32)>, b: Vec<(i32,i32)>, op: F, expected: bool) where
F: Fn(&IntervalSet<i32>, &IntervalSet<i32>) -> bool
{
println!("Info: {}.", test_id);
let a = make_interval_set(a);
let b = make_interval_set(b);
assert_eq!(op(&a, &b), expected);
}
fn test_binary_value_bool_op<V, F>(test_id: String, a: Vec<(i32,i32)>, b: V, op: F, expected: bool) where
F: Fn(&IntervalSet<i32>, &V) -> bool
{
println!("Info: {}.", test_id);
let a = make_interval_set(a);
assert_eq!(op(&a, &b), expected);
}
fn test_op<F>(test_id: String, a: Vec<(i32,i32)>, op: F, expected: Vec<(i32,i32)>) where
F: Fn(&IntervalSet<i32>) -> IntervalSet<i32>
{
println!("Info: {}.", test_id);
let a = make_interval_set(a);
let expected = make_interval_set(expected);
let result = op(&a);
test_result(test_id, &result, &expected);
}
#[test]
fn test_contains() {
let cases = vec![
(vec![], vec![], vec![-2,-1,0,1,2]),
(vec![(1,2)], vec![1,2], vec![-1,0,3,4]),
(vec![(1,2),(7,9)], vec![1,2,7,8,9], vec![-1,0,3,4,5,6,10,11]),
(vec![(1,2),(4,5),(7,9)], vec![1,2,4,5,7,8,9], vec![-1,0,3,6,10,11])
];
for (is, inside, outside) in cases {
let is = make_interval_set(is);
test_inside_outside(is, inside, outside);
}
}
#[test]
fn test_complement() {
let min = <i32 as Width>::min_value();
let max = <i32 as Width>::max_value();
let cases = vec![
(1, vec![], vec![(min, max)]),
(2, vec![(min, max)], vec![]),
(3, vec![(0,0)], vec![(min,-1),(1,max)]),
(4, vec![(-5,5)], vec![(min,-6),(6,max)]),
(5, vec![(-5,-1),(1,5)], vec![(min,-6),(0,0),(6, max)]),
(6, vec![(min,-1),(1,5)], vec![(0,0),(6, max)]),
(7, vec![(-5,-1),(1,max)], vec![(min,-6),(0,0)]),
(8, vec![(min,-1),(1,max)], vec![(0,0)]),
(9, vec![(-5,-3),(0,1),(3,5)], vec![(min,-6),(-2,-1),(2,2),(6, max)])
];
for (id, a, expected) in cases {
test_op(format!("test #{} of complement", id), a.clone(), |x| x.complement(), expected);
test_op(format!("test #{} of complement(complement)", id), a.clone(), |x| x.complement().complement(), a);
}
}
#[test]
fn test_union() {
let sym_cases = vec![
(1, vec![], vec![], vec![]),
(2, vec![], vec![(1,2)], vec![(1,2)]),
(3, vec![], vec![(1,2),(7,9)], vec![(1,2),(7,9)]),
(4, vec![(1,2),(7,9)], vec![(1,2)], vec![(1,2),(7,9)]),
(5, vec![(1,2),(7,9)], vec![(1,2),(7,9)], vec![(1,2),(7,9)]),
(6, vec![(-3,-1)], vec![(1,2),(7,9)], vec![(-3,-1),(1,2),(7,9)]),
(7, vec![(-3,0)], vec![(1,2),(7,9)], vec![(-3,2),(7,9)]),
(8, vec![(-3,1)], vec![(1,2),(7,9)], vec![(-3,2),(7,9)]),
(9, vec![(2,7)], vec![(1,2),(7,9)], vec![(1,9)]),
(10, vec![(3,7)], vec![(1,2),(7,9)], vec![(1,9)]),
(11, vec![(4,5)], vec![(1,2),(7,9)], vec![(1,2),(4,5),(7,9)]),
(12, vec![(2,8)], vec![(1,2),(7,9)], vec![(1,9)]),
(13, vec![(2,6)], vec![(1,2),(7,9)], vec![(1,9)]),
(14, vec![(3,6)], vec![(1,2),(7,9)], vec![(1,9)]),
(15, vec![(8,9)], vec![(1,2),(7,9)], vec![(1,2),(7,9)]),
(16, vec![(8,10)], vec![(1,2),(7,9)], vec![(1,2),(7,10)]),
(17, vec![(9,10)], vec![(1,2),(7,9)], vec![(1,2),(7,10)]),
(18, vec![(6,10)], vec![(1,2),(7,9)], vec![(1,2),(6,10)]),
(19, vec![(10,11)], vec![(1,2),(7,9)], vec![(1,2),(7,11)]),
(20, vec![(11,12)], vec![(1,2),(7,9)], vec![(1,2),(7,9),(11,12)]),
(21, vec![(-3,-1),(4,5),(11,12)], vec![(1,2),(7,9)], vec![(-3,-1),(1,2),(4,5),(7,9),(11,12)]),
(22, vec![(-3,0),(3,6),(10,11)], vec![(1,2),(7,9)], vec![(-3,11)]),
(23, vec![(-3,1),(3,7),(9,11)], vec![(1,2),(7,9)], vec![(-3,11)]),
(24, vec![(-3,5),(7,11)], vec![(1,2),(7,9)], vec![(-3,5),(7,11)]),
(25, vec![(-3,5),(7,8),(12,12)], vec![(1,2),(7,9)], vec![(-3,5),(7,9),(12,12)]),
(26, vec![(-1,11)], vec![(1,2),(7,9)], vec![(-1,11)]),
];
for (id, a, b, expected) in sym_cases {
test_binary_op_sym(format!("test #{} of union", id), a, b, |x,y| x.union(y), expected);
}
}
#[test]
fn test_intersection() {
let sym_cases = vec![
(1, vec![], vec![], vec![]),
(2, vec![], vec![(1,2)], vec![]),
(3, vec![], vec![(1,2),(7,9)], vec![]),
(4, vec![(1,2),(7,9)], vec![(1,2)], vec![(1,2)]),
(5, vec![(1,2),(7,9)], vec![(1,2),(7,9)], vec![(1,2),(7,9)]),
(6, vec![(-3,-1)], vec![(1,2),(7,9)], vec![]),
(7, vec![(-3,0)], vec![(1,2),(7,9)], vec![]),
(8, vec![(-3,1)], vec![(1,2),(7,9)], vec![(1,1)]),
(9, vec![(2,7)], vec![(1,2),(7,9)], vec![(2,2),(7,7)]),
(10, vec![(3,7)], vec![(1,2),(7,9)], vec![(7,7)]),
(11, vec![(4,5)], vec![(1,2),(7,9)], vec![]),
(12, vec![(2,8)], vec![(1,2),(7,9)], vec![(2,2),(7,8)]),
(13, vec![(2,6)], vec![(1,2),(7,9)], vec![(2,2)]),
(14, vec![(3,6)], vec![(1,2),(7,9)], vec![]),
(15, vec![(8,9)], vec![(1,2),(7,9)], vec![(8,9)]),
(16, vec![(8,10)], vec![(1,2),(7,9)], vec![(8,9)]),
(17, vec![(9,10)], vec![(1,2),(7,9)], vec![(9,9)]),
(18, vec![(6,10)], vec![(1,2),(7,9)], vec![(7,9)]),
(19, vec![(10,11)], vec![(1,2),(7,9)], vec![]),
(20, vec![(11,12)], vec![(1,2),(7,9)], vec![]),
(21, vec![(-3,-1),(4,5),(11,12)], vec![(1,2),(7,9)], vec![]),
(22, vec![(-3,0),(3,6),(10,11)], vec![(1,2),(7,9)], vec![]),
(23, vec![(-3,1),(3,7),(9,11)], vec![(1,2),(7,9)], vec![(1,1),(7,7),(9,9)]),
(24, vec![(-3,5),(7,11)], vec![(1,2),(7,9)], vec![(1,2),(7,9)]),
(25, vec![(-3,5),(7,8),(12,12)], vec![(1,2),(7,9)], vec![(1,2),(7,8)]),
(26, vec![(-1,11)], vec![(1,2),(7,9)], vec![(1,2),(7,9)]),
];
for (id, a, b, expected) in sym_cases {
test_binary_op_sym(format!("test #{} of intersection", id), a, b, |x,y| x.intersection(y), expected);
}
}
#[test]
fn test_to_interval_set() {
let intervals = vec![(3, 8), (2, 5)].to_interval_set();
assert_eq!(intervals.interval_count(), 1);
assert_eq!(intervals.lower(), 2);
assert_eq!(intervals.upper(), 8);
}
#[test]
#[should_panic(expected = "This operation is only for pushing interval to the back of the array, possibly overlapping with the last element.")]
fn test_extend_back() {
let mut set = IntervalSet::empty();
let intervals = extend_example.map(|i| i.to_interval());
set.extend_at_back(intervals);
assert_eq!(set.interval_count(), 2);
}
#[test]
fn test_extend_empty() {
let mut set = IntervalSet::empty();
let intervals = extend_example.map(|i| i.to_interval());
set.extend(intervals);
assert_eq!(set.interval_count(), 2);
}
#[test]
fn test_extend_non_empty() {
let mut intervals = vec![(10, 15), (20, 30)].to_interval_set();
let at_start = vec![(0, 5).to_interval()];
intervals.extend(at_start);
let in_middle = vec![(17, 18).to_interval()];
intervals.extend(in_middle);
assert_eq!(intervals.interval_count(), 4);
assert_eq!(intervals.lower(), 0);
assert_eq!(intervals.upper(), 30);
}
#[test]
fn test_difference() {
let cases = vec![
(1, vec![], vec![], vec![], vec![]),
(2, vec![], vec![(1,2)], vec![], vec![(1,2)]),
(3, vec![], vec![(1,2),(7,9)], vec![], vec![(1,2),(7,9)]),
(4, vec![(1,2),(7,9)], vec![(1,2)], vec![(7,9)], vec![]),
(5, vec![(1,2),(7,9)], vec![(1,2),(7,9)], vec![], vec![]),
(6, vec![(-3,-1)], vec![(1,2),(7,9)], vec![(-3,-1)], vec![(1,2),(7,9)]),
(7, vec![(-3,0)], vec![(1,2),(7,9)], vec![(-3,0)], vec![(1,2),(7,9)]),
(8, vec![(-3,1)], vec![(1,2),(7,9)], vec![(-3,0)], vec![(2,2),(7,9)]),
(9, vec![(2,7)], vec![(1,2),(7,9)], vec![(3,6)], vec![(1,1),(8,9)]),
(10, vec![(3,7)], vec![(1,2),(7,9)], vec![(3,6)], vec![(1,2),(8,9)]),
(11, vec![(4,5)], vec![(1,2),(7,9)], vec![(4,5)], vec![(1,2),(7,9)]),
(12, vec![(2,8)], vec![(1,2),(7,9)], vec![(3,6)], vec![(1,1),(9,9)]),
(13, vec![(2,6)], vec![(1,2),(7,9)], vec![(3,6)], vec![(1,1),(7,9)]),
(14, vec![(3,6)], vec![(1,2),(7,9)], vec![(3,6)], vec![(1,2),(7,9)]),
(15, vec![(8,9)], vec![(1,2),(7,9)], vec![], vec![(1,2),(7,7)]),
(16, vec![(8,10)], vec![(1,2),(7,9)], vec![(10,10)], vec![(1,2),(7,7)]),
(17, vec![(9,10)], vec![(1,2),(7,9)], vec![(10,10)], vec![(1,2),(7,8)]),
(18, vec![(6,10)], vec![(1,2),(7,9)], vec![(6,6),(10,10)], vec![(1,2)]),
(19, vec![(10,11)], vec![(1,2),(7,9)], vec![(10,11)], vec![(1,2),(7,9)]),
(20, vec![(11,12)], vec![(1,2),(7,9)], vec![(11,12)], vec![(1,2),(7,9)]),
(21, vec![(-3,-1),(4,5),(11,12)], vec![(1,2),(7,9)], vec![(-3,-1),(4,5),(11,12)], vec![(1,2),(7,9)]),
(22, vec![(-3,0),(3,6),(10,11)], vec![(1,2),(7,9)], vec![(-3,0),(3,6),(10,11)], vec![(1,2),(7,9)]),
(23, vec![(-3,1),(3,7),(9,11)], vec![(1,2),(7,9)], vec![(-3,0),(3,6),(10,11)], vec![(2,2),(8,8)]),
(24, vec![(-3,5),(7,11)], vec![(1,2),(7,9)], vec![(-3,0),(3,5),(10,11)], vec![]),
(25, vec![(-3,5),(7,8),(12,12)], vec![(1,2),(7,9)], vec![(-3,0),(3,5),(12,12)], vec![(9,9)]),
(26, vec![(-1,11)], vec![(1,2),(7,9)], vec![(-1,0),(3,6),(10,11)], vec![]),
];
for (id, a, b, expected, expected_sym) in cases {
test_binary_op(format!("test #{} of difference", id), a.clone(), b.clone(), |x,y| x.difference(y), expected);
test_binary_op(format!("test #{} of difference", id), b, a, |x,y| x.difference(y), expected_sym);
}
}
#[test]
fn test_symmetric_difference() {
let sym_cases = vec![
(1, vec![], vec![], vec![]),
(2, vec![], vec![(1,2)], vec![(1,2)]),
(3, vec![], vec![(1,2),(7,9)], vec![(1,2),(7,9)]),
(4, vec![(1,2),(7,9)], vec![(1,2)], vec![(7,9)]),
(5, vec![(1,2),(7,9)], vec![(1,2),(7,9)], vec![]),
(6, vec![(-3,-1)], vec![(1,2),(7,9)], vec![(-3,-1),(1,2),(7,9)]),
(7, vec![(-3,0)], vec![(1,2),(7,9)], vec![(-3,2),(7,9)]),
(8, vec![(-3,1)], vec![(1,2),(7,9)], vec![(-3,0),(2,2),(7,9)]),
(9, vec![(2,7)], vec![(1,2),(7,9)], vec![(1,1),(3,6),(8,9)]),
(10, vec![(3,7)], vec![(1,2),(7,9)], vec![(1,6),(8,9)]),
(11, vec![(4,5)], vec![(1,2),(7,9)], vec![(1,2),(4,5),(7,9)]),
(12, vec![(2,8)], vec![(1,2),(7,9)], vec![(1,1),(3,6),(9,9)]),
(13, vec![(2,6)], vec![(1,2),(7,9)], vec![(1,1),(3,9)]),
(14, vec![(3,6)], vec![(1,2),(7,9)], vec![(1,9)]),
(15, vec![(8,9)], vec![(1,2),(7,9)], vec![(1,2),(7,7)]),
(16, vec![(8,10)], vec![(1,2),(7,9)], vec![(1,2),(7,7),(10,10)]),
(17, vec![(9,10)], vec![(1,2),(7,9)], vec![(1,2),(7,8),(10,10)]),
(18, vec![(6,10)], vec![(1,2),(7,9)], vec![(1,2),(6,6),(10,10)]),
(19, vec![(10,11)], vec![(1,2),(7,9)], vec![(1,2),(7,11)]),
(20, vec![(11,12)], vec![(1,2),(7,9)], vec![(1,2),(7,9),(11,12)]),
(21, vec![(-3,-1),(4,5),(11,12)], vec![(1,2),(7,9)], vec![(-3,-1),(1,2),(4,5),(7,9),(11,12)]),
(22, vec![(-3,0),(3,6),(10,11)], vec![(1,2),(7,9)], vec![(-3,11)]),
(23, vec![(-3,1),(3,7),(9,11)], vec![(1,2),(7,9)], vec![(-3,0),(2,6),(8,8),(10,11)]),
(24, vec![(-3,5),(7,11)], vec![(1,2),(7,9)], vec![(-3,0),(3,5),(10,11)]),
(25, vec![(-3,5),(7,8),(12,12)], vec![(1,2),(7,9)], vec![(-3,0),(3,5),(9,9),(12,12)]),
(26, vec![(-1,11)], vec![(1,2),(7,9)], vec![(-1,0),(3,6),(10,11)]),
];
for (id, a, b, expected) in sym_cases {
test_binary_op_sym(format!("test #{} of symmetric difference", id),
a, b, |x,y| x.symmetric_difference(y), expected);
}
}
#[test]
fn test_overlap_and_is_disjoint() {
let sym_cases = vec![
(1, vec![], vec![], false),
(2, vec![], vec![(1,2)], false),
(3, vec![], vec![(1,2),(7,9)], false),
(4, vec![(1,2),(7,9)], vec![(1,2)], true),
(5, vec![(1,2),(7,9)], vec![(1,2),(7,9)], true),
(6, vec![(-3,-1)], vec![(1,2),(7,9)], false),
(7, vec![(-3,0)], vec![(1,2),(7,9)], false),
(8, vec![(-3,1)], vec![(1,2),(7,9)], true),
(9, vec![(2,7)], vec![(1,2),(7,9)], true),
(10, vec![(3,7)], vec![(1,2),(7,9)], true),
(11, vec![(4,5)], vec![(1,2),(7,9)], false),
(12, vec![(2,8)], vec![(1,2),(7,9)], true),
(13, vec![(2,6)], vec![(1,2),(7,9)], true),
(14, vec![(3,6)], vec![(1,2),(7,9)], false),
(15, vec![(8,9)], vec![(1,2),(7,9)], true),
(16, vec![(8,10)], vec![(1,2),(7,9)], true),
(17, vec![(9,10)], vec![(1,2),(7,9)], true),
(18, vec![(6,10)], vec![(1,2),(7,9)], true),
(19, vec![(10,11)], vec![(1,2),(7,9)], false),
(20, vec![(11,12)], vec![(1,2),(7,9)], false),
(21, vec![(-3,-1),(4,5),(11,12)], vec![(1,2),(7,9)], false),
(22, vec![(-3,0),(3,6),(10,11)], vec![(1,2),(7,9)], false),
(23, vec![(-3,1),(3,7),(9,11)], vec![(1,2),(7,9)], true),
(24, vec![(-3,5),(7,11)], vec![(1,2),(7,9)], true),
(25, vec![(-3,5),(7,8),(12,12)], vec![(1,2),(7,9)], true),
(26, vec![(-1,11)], vec![(1,2),(7,9)], true),
];
for (id, a, b, expected) in sym_cases {
test_binary_bool_op_sym(format!("test #{} of overlap", id),
a.clone(), b.clone(), |x,y| x.overlap(y), expected);
test_binary_bool_op_sym(format!("test #{} of is_disjoint", id),
a, b, |x,y| x.is_disjoint(y), !expected);
}
}
fn overlap_cases() -> Vec<(u32, Vec<(i32,i32)>, i32, bool)> {
vec![
(1, vec![], 0, false),
(2, vec![(1,2)], 0, false),
(3, vec![(1,2)], 1, true),
(4, vec![(1,2)], 2, true),
(5, vec![(1,2)], 3, false),
(6, vec![(1,3),(5,7)], 2, true),
(7, vec![(1,3),(5,7)], 6, true),
(8, vec![(1,3),(5,7)], 4, false),
(9, vec![(1,3),(5,7)], 0, false),
(10, vec![(1,3),(5,7)], 8, false)
]
}
#[test]
fn test_overlap_bound() {
let cases = overlap_cases();
for (id, a, b, expected) in cases {
test_binary_value_bool_op(format!("test #{} of overlap_bound", id),
a.clone(), b, |x,y| x.overlap(y), expected);
test_binary_value_bool_op(format!("test #{} of overlap_bound", id),
a, b, |x,y| y.overlap(x), expected);
}
}
#[test]
fn test_overlap_option() {
let mut cases: Vec<(u32, Vec<(i32,i32)>, Optional<i32>, bool)> = overlap_cases().into_iter()
.map(|(id,a,b,e)| (id,a,Optional::singleton(b),e))
.collect();
cases.extend(
vec![
(11, vec![], Optional::empty(), false),
(12, vec![(1,2)], Optional::empty(), false),
(13, vec![(1,3),(5,7)], Optional::empty(), false),
].into_iter()
);
for (id, a, b, expected) in cases {
test_binary_value_bool_op(format!("test #{} of overlap_option", id),
a.clone(), b, |x,y| x.overlap(y), expected);
}
}
#[test]
fn test_shrink() {
let min = <i32 as Width>::min_value();
let max = <i32 as Width>::max_value();
let cases = vec![
(1, vec![], 0, vec![], vec![]),
(2, vec![(min, max)], 0, vec![(0, max)], vec![(min,0)]),
(3, vec![(0,0)], 0, vec![(0,0)], vec![(0,0)]),
(4, vec![(0,0)], -1, vec![(0,0)], vec![]),
(5, vec![(0,0)], 1, vec![], vec![(0,0)]),
(6, vec![(-5,5)], 0, vec![(0,5)], vec![(-5,0)]),
(7, vec![(-5,5)], -5, vec![(-5,5)], vec![(-5,-5)]),
(8, vec![(-5,5)], 5, vec![(5,5)], vec![(-5,5)]),
(9, vec![(-5,-1),(1,5)], 0, vec![(1,5)], vec![(-5,-1)]),
(10, vec![(-5,-1),(1,5)], 1, vec![(1,5)], vec![(-5,-1),(1,1)]),
(11, vec![(-5,-1),(1,5)], -1, vec![(-1,-1),(1,5)], vec![(-5,-1)]),
(12, vec![(min,-1),(1,5)], min, vec![(min,-1),(1,5)], vec![(min,min)]),
(13, vec![(min,-1),(1,5)], max, vec![], vec![(min,-1),(1,5)]),
(14, vec![(-5,-1),(1,max)], max, vec![(max, max)], vec![(-5,-1),(1,max)]),
(15, vec![(min,-1),(1,max)], 0, vec![(1, max)], vec![(min, -1)]),
(16, vec![(-5,-3),(0,1),(3,5)], 1, vec![(1,1),(3,5)], vec![(-5,-3),(0,1)])
];
for (id, a, v, expected_left, expected_right) in cases {
test_binary_value_op(format!("test #{} of shrink_left", id),
a.clone(), v, |x, v| x.shrink_left(v), expected_left);
test_binary_value_op(format!("test #{} of shrink_right", id),
a, v, |x, v| x.shrink_right(v), expected_right);
}
}
#[test]
fn test_subset() {
let cases = vec![
(1, vec![], vec![], true, true, false, false),
(2, vec![], vec![(1,2)], true, false, true, false),
(3, vec![], vec![(1,2),(7,9)], true, false, true, false),
(4, vec![(1,2),(7,9)], vec![(1,2)], false, true, false, true),
(5, vec![(1,2),(7,9)], vec![(1,2),(7,9)], true, true, false, false),
(6, vec![(2,7)], vec![(1,2),(7,9)], false, false, false, false),
(7, vec![(3,7)], vec![(1,2),(7,9)], false, false, false, false),
(8, vec![(4,5)], vec![(1,2),(7,9)], false, false, false, false),
(9, vec![(2,8)], vec![(1,2),(7,9)], false, false, false, false),
(10, vec![(-3,-1),(4,5),(11,12)], vec![(-2,-1),(7,9)], false, false, false, false),
(11, vec![(-3,0),(3,6),(10,11)], vec![(-2,-1),(4,4),(10,10)], false, true, false, true),
(12, vec![(-3,0),(3,6),(10,11)], vec![(-3,0),(3,6),(10,11)], true, true, false, false),
(13, vec![(-1,11)], vec![(1,2),(7,9)], false, true, false, true),
];
for (id, a, b, expected, expected_sym, expected_proper, expected_proper_sym) in cases {
test_binary_bool_op(format!("test #{} of subset", id), a.clone(), b.clone(), |x,y| x.is_subset(y), expected);
test_binary_bool_op(format!("test #{} of subset", id), b.clone(), a.clone(), |x,y| x.is_subset(y), expected_sym);
test_binary_bool_op(format!("test #{} of proper subset", id), a.clone(), b.clone(), |x,y| x.is_proper_subset(y), expected_proper);
test_binary_bool_op(format!("test #{} of proper subset", id), b.clone(), a.clone(), |x,y| x.is_proper_subset(y), expected_proper_sym);
}
}
#[test]
fn test_arithmetics() {
let cases = vec![
(1, vec![], vec![], vec![], vec![], vec![], vec![]),
(2, vec![], vec![(1,1),(3,5)], vec![], vec![], vec![], vec![]),
(3, vec![(1,1),(3,5)], vec![(0,0)], vec![(1,1),(3,5)], vec![(1,1),(3,5)], vec![(-5,-3),(-1,-1)], vec![(0,0)]),
(4, vec![(1,1),(3,5)], vec![(1,1)], vec![(2,2),(4,6)], vec![(0,0),(2,4)], vec![(-4,-2),(0,0)], vec![(1,1),(3,5)]),
(5, vec![(1,1),(3,5)], vec![(0,1),(4,5)],
vec![(1,10)],
vec![(-4,5)],
vec![(-5,4)],
vec![(0,5),(12,25)]),
];
for (id, a, b, e_add, e_sub, e_sub_sym, e_mul) in cases {
test_binary_op_sym(format!("test #{} of `a+b`", id),
a.clone(), b.clone(), |x,y| x + y, e_add);
test_binary_op(format!("test #{} of `a-b`", id),
a.clone(), b.clone(), |x,y| x - y, e_sub);
test_binary_op(format!("test #{} of `b-a`", id),
b.clone(), a.clone(), |x,y| x - y, e_sub_sym);
test_binary_op_sym(format!("test #{} of `a*b`", id),
a.clone(), b.clone(), |x,y| x * y, e_mul);
}
}
#[test]
fn test_arithmetics_bound() {
let i1_35 = vec![(1,1),(3,5)];
let cases = vec![
(1, vec![], 0, vec![], vec![], vec![]),
(2, vec![(0,0)], 0, vec![(0,0)], vec![(0,0)], vec![(0,0)]),
(3, i1_35.clone(), 0, i1_35.clone(), i1_35.clone(), vec![(0,0)]),
(4, vec![], 1, vec![], vec![], vec![]),
(5, vec![(0,0)], 1, vec![(1,1)], vec![(-1,-1)], vec![(0,0)]),
(6, i1_35.clone(), 1, vec![(2,2),(4,6)], vec![(0,0),(2,4)], i1_35.clone()),
(7, vec![], 3, vec![], vec![], vec![]),
(8, vec![(0,0)], 3, vec![(3,3)], vec![(-3,-3)], vec![(0,0)]),
(9, i1_35.clone(), 3, vec![(4,4),(6,8)], vec![(-2,-2),(0,2)], vec![(3,3),(9,15)])
];
for (id, a, b, e_add, e_sub, e_mul) in cases {
test_binary_value_op(format!("test #{} of `a+b`", id),
a.clone(), b.clone(), |x,y| x + y, e_add);
test_binary_value_op(format!("test #{} of `a-b`", id),
a.clone(), b.clone(), |x,y| x - y, e_sub);
test_binary_value_op(format!("test #{} of `a*b`", id),
a.clone(), b.clone(), |x,y| x * y, e_mul);
}
}
#[test]
fn test_lattice() {
use gcollections::ops::lattice::test::*;
use trilean::SKleene::*;
let whole = IntervalSet::<i32>::whole();
let empty = IntervalSet::<i32>::empty();
let a = vec![(0,5), (10,15)].to_interval_set();
let b = vec![(5,10)].to_interval_set();
let c = vec![(6,9)].to_interval_set();
let d = vec![(4,6), (8,10)].to_interval_set();
let e = vec![(5,5), (10,10)].to_interval_set();
let f = vec![(6,6), (8,9)].to_interval_set();
let g = vec![(0,15)].to_interval_set();
let h = vec![(4,10)].to_interval_set();
let tester = LatticeTester::new(
0,
vec![empty.clone(), empty.clone(), whole.clone(), a.clone(), b.clone(), c.clone()],
vec![whole.clone(), a.clone(), a.clone(), b.clone(), c.clone(), d.clone()],
vec![True, True, False, Unknown, False, Unknown],
vec![empty.clone(), empty.clone(), a.clone(), e.clone(), c.clone(), f.clone()],
vec![whole.clone(), a.clone(), whole.clone(), g.clone(), b.clone(), h.clone()]
);
tester.test_all();
}
#[test]
fn test_iterator() {
let empty = IntervalSet::<i32>::empty();
let mut a = vec![(0,5), (10,15)].to_interval_set();
let mut iter = a.clone().into_iter();
assert_eq!(iter.next(), Some(Interval::new(0,5)), "test 1 of test_iterator");
assert_eq!(iter.next(), Some(Interval::new(10,15)), "test 2 of test_iterator");
assert_eq!(iter.next(), None, "test 3 of test_iterator");
for _x in a.clone() {}
for _x in &a {}
for _x in &mut a {}
for _x in empty {
assert!(false, "test 4 of test_iterator: empty interval must not yield an element.");
}
}
}