interval 0.0.1

//! Provides a type representing an integer interval. Should work as
//! expected with any type implementing the Int trait.
//!
//! I do have an implementation that is generic to Int and Float
//! numeric types, but I don't have a use-case for that and it is less
//! efficient for integer intervals. Nevertheless, if you are
//! interested, please contact me and I'll make it available.

use std::fmt::Show;
use std::num::Int;

/// Represents an interval [begin, end]. We use inclusive bounds so
/// that we can have a set that includes the maximum value of the
/// type.
///
/// We only support integral intervals here. Real intervals are more
/// complicated since we'd need to be able to specify whether their
/// bounds are open or closed. That generality would come at a cost of
/// efficiency.
///
/// Representation of the empty set:
/// We need some way of representing the empty set. While there are
/// many [begin, end] pairs that would be empty, we represent all
/// empty sets with [1, 0] for a few reasons:
///  * This same formula to compute length on non-empty sets will
///    produce a length of zero for [1, 0].
///  * We have the Zero and One traits to produce this value for any
///    type implementing the Int trait.
///
/// It is best not to rely on our implementation detail to determine
/// if the interval is empty, and instead just query the `is_empty()`
/// method.
#[deriving(Clone, Copy, PartialEq, Eq)]
pub struct Interval<T: Int> {
    /// The beginning of the interval, inclusive.
    pub begin: T,
    /// The end of the interval, inclusive.
    pub end: T,
}

impl<T: Int + Show> Interval<T> {
    // See our implementation of `Show` for why `T` must implement
    // `Show`, despite being a known integral type.

    /// Creates a new empty interval.
    pub fn empty() -> Interval<T> {
        let interval = Interval{begin: Int::one(), end: Int::zero()};
        // Ensure that this behaves as we would expect. We also have a
        // test for this.
        debug_assert!(interval.is_empty());
        debug_assert_eq!(interval.len(), 0);
        interval
    }

    /// Creates a new interval [begin, end] which must be non-empty.
    pub fn new(begin: T, end: T) -> Interval<T> {
        if begin > end { panic!("begin not <= end. [{}, {}]", begin, end); }
        Interval{begin: begin, end: end}
    }
}

/// Intervals are partially ordered in the sense that an interval is
/// before another interval if all of its values are before all of the
/// other interval's values. Otherwise, there is no ordering between
/// the intervals.
///
/// The empty interval is unordered, it can only compare equal to
/// itself.
impl<T: Int> PartialOrd for Interval<T> {
    fn partial_cmp(&self, other: &Interval<T>) -> Option<Ordering> {
        // TODO This is not correct if exactly one interval is empty.

        // TODO If one interval's end touches the other interval's
        // begin, there is no ordering between the intervals. If this
        // is the behavior we want, document it, otherwise, fix it.

        if self == other { return Some(Equal); }
        if self.end < other.begin { return Some(Less); }
        if self.begin > other.end { return Some(Greater); }
        None
    }
}

/// Intervals are showable, will render as [%d, %d], unless empty in
/// which case it will render as ∅.
impl<T: Int + Show> Show for Interval<T> {
    // Unfortunately, `T` must implement `Show` here since otherwise
    // we cannot render it. We are pretty sure that `T` will implement
    // either `Signed` or `Unsigned`, but there is not any way to
    // enforce that in the type system that I'm aware of. If we could
    // do so, we could use either :d or :u in the format string.

    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
        if self.is_empty() {
            write!(fmt, "∅")
        } else {
            write!(fmt, "[{}, {}]", self.begin, self.end)
        }
    }
}

/// While the Rust collections library is in flux, define the
/// Collection trait here.
pub trait Collection {
    fn is_empty(&self) -> bool { self.len() == 0 }
    fn len(&self) -> uint;
}

/// An interval models a collection of integers that are constrained
/// by being contiguous.
impl<T: Int> Collection for Interval<T> {
    fn len(&self) -> uint {
        let dist = self.end - self.begin + Int::one();
        dist.to_uint().expect("could not determine length")
    }
}

/// Temporarily provide the Set trait. See `trait Collection` for the
/// rationale.
pub trait Set<T> {
    fn contains(&self, value: &T) -> bool;
    fn is_disjoint(&self, other: &Self) -> bool;
    fn is_subset(&self, other: &Self) -> bool;
    fn is_superset(&self, other: &Self) -> bool { other.is_subset(self) }
}

/// An interval modeled as a collection of integers easily models the
/// Set trait.
impl<T: Int> Set<T> for Interval<T> {
    fn contains(&self, value: &T) -> bool {
        *value >= self.begin && *value <= self.end
    }
    fn is_disjoint(&self, other: &Interval<T>) -> bool {
        self.end < other.begin || self.begin > other.end
    }
    fn is_subset(&self, other: &Interval<T>) -> bool {
        self.begin >= other.begin && self.end <= other.end
    }
}

// TODO implement the Iterator trait. Possibly consider implementing
// DoubleEndedIterator and RandomAccessIterator, too.

#[test]
fn test_show() {
    let i = Interval::new(0i, 1);
    assert_eq!(format!("{}", i), "[0, 1]".to_string());
}

#[test]
fn test_show_empty() {
    let i: Interval<int> = Interval::empty();
    assert_eq!(format!("{}", i), "∅".to_string());
}

#[test]
fn test_equality() {
    let empty: Interval<int> = Interval::empty();
    let i = Interval::new(0i, 1);

    assert_eq!(empty, empty);
    assert_eq!(i, i);

    assert!(empty != i);
}

#[test]
fn test_ordering() {
    let before = Interval::new(0i, 2);
    let after = Interval::new(3i, 5);

    assert!(before < after);
    assert!(after > before);

    let intersecting = Interval::new(1i, 4);

    assert!(!(before < intersecting));
    assert!(!(before > intersecting));

    assert!(!(after < intersecting));
    assert!(!(after > intersecting));
}

// This test is broken. The implementation of `PartialOrd` needs to be
// fixed to always return `None` for a comparison between an empty and
// a non-empty set.
#[test]
#[ignore]
fn test_empty_ordering() {
    let empty: Interval<int> = Interval::empty();

    let i = Interval::new(-1, 0);
    assert!(!(i < empty));
    assert!(!(i > empty));
}

#[test]
fn test_empty_collection() {
    let i: Interval<int> = Interval::empty();
    assert!(i.is_empty());
    assert_eq!(i.len(), 0);
}

#[test]
fn test_empty_set() {
    let empty_set: Interval<int> = Interval::empty();
    // Our representation of the empty set is [1, 0], let's be sure
    // that [-1, 0, 1, 2] are not elements of the empty set.
    assert_eq!(empty_set.begin, Int::one());
    assert_eq!(empty_set.end, Int::zero());
    for i in [-1, 0, 1, 2].iter() { assert!(!empty_set.contains(i)); }

    // Identity: empty set is disjoint with itself.
    //
    // ∅ ∩ ∅ = ∅
    assert!(empty_set.is_disjoint(&empty_set));
    // Identity: empty set is a subset of itself.
    //
    // ∅ ⊂ ∅
    assert!(empty_set.is_subset(&empty_set));
    // Identity: empty set is a superset of itself.
    //
    // ∅ ⊃ ∅
    assert!(empty_set.is_superset(&empty_set));
}

#[test]
fn test_singleton() {
    let singleton = Interval::new(1i, 1);
    assert!(!singleton.is_empty());
    assert_eq!(singleton.len(), 1);
    assert!(singleton.contains(&1));
    assert!(!singleton.contains(&0));
    assert!(!singleton.contains(&2));

    assert!(!singleton.is_disjoint(&singleton));
    assert!(singleton.is_subset(&singleton));
    assert!(singleton.is_superset(&singleton));
}

#[test]
fn test_abutting() {
    // Test behavior of two intervals that overlap.
    let first = Interval::new(0i, 1);
    let second = Interval::new(1i, 2);
    assert!(!first.is_disjoint(&second));
    assert!(!first.is_subset(&second));
    assert!(!first.is_superset(&second));
}

#[test]
fn test_adjacent() {
    // Test behavior of two intervals that are adjacent.
    let first = Interval::new(0i, 1);
    let second = Interval::new(2i, 3);
    assert!(first.is_disjoint(&second));
    assert!(!first.is_subset(&second));
    assert!(!first.is_superset(&second));
}