/*
 * A module to handle simple interval and interval set arithmetic.
 */

use std::cmp::{Ordering, min, max};
use std::ops::{Add, Sub, RangeBounds};

/// Represents a bound that is capable of total ordering.
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub enum Bound<T> {
    /// The value is part of the interval.
    Included(T),
    /// The value is not part of the interval (less).
    LowerExcluded(T),
    /// The value is not part of the interval (greater).
    UpperExcluded(T),
    /// The value goes to negative infinity.
    LowerUnbounded,
    /// The value goes to positive infinity.
    UpperUnbounded,
}

// Simple construction methods

impl <T> Bound<T> where T: Copy + Eq {
    /// Constructs a lower bound from a Rust Bound type.
    fn from_bound_lower(b: std::ops::Bound<&T>) -> Self {
        match b {
            std::ops::Bound::Unbounded => Bound::LowerUnbounded,
            std::ops::Bound::Included(x) => Bound::Included(*x),
            std::ops::Bound::Excluded(x) => Bound::LowerExcluded(*x),
        }
    }

    /// Constructs an upper bound from a Rust Bound type.
    fn from_bound_upper(b: std::ops::Bound<&T>) -> Self {
        match b {
            std::ops::Bound::Unbounded => Bound::UpperUnbounded,
            std::ops::Bound::Included(x) => Bound::Included(*x),
            std::ops::Bound::Excluded(x) => Bound::UpperExcluded(*x),
        }
    }

    /// Returns true if the bound is touching another (no inclusion).
    fn is_touching(&self, other: &Self) -> bool {
        match (self, other) {
            (Bound::LowerExcluded(x), Bound::Included(y)) => x == y,
            (Bound::UpperExcluded(x), Bound::Included(y)) => x == y,

            (Bound::Included(x), Bound::LowerExcluded(y)) => x == y,
            (Bound::Included(x), Bound::UpperExcluded(y)) => x == y,

            _ => false,
        }
    }
}

// Define the ordering /////////////////////////////////////////////////////////

impl <T> Ord for Bound<T> where T: Ord {
    fn cmp(&self, other: &Self) -> Ordering {
        match (self, other) {
            (Bound::LowerUnbounded, Bound::LowerUnbounded) => Ordering::Equal,
            (Bound::UpperUnbounded, Bound::UpperUnbounded) => Ordering::Equal,

            (Bound::LowerUnbounded, _) => Ordering::Less,
            (Bound::UpperUnbounded, _) => Ordering::Greater,

            (_, Bound::LowerUnbounded) => Ordering::Greater,
            (_, Bound::UpperUnbounded) => Ordering::Less,

            (Bound::LowerExcluded(x), Bound::LowerExcluded(y)) => x.cmp(y),
            (Bound::UpperExcluded(x), Bound::UpperExcluded(y)) => x.cmp(y),
            (Bound::Included(x), Bound::Included(y)) => x.cmp(y),

            (Bound::Included(x), Bound::LowerExcluded(y)) => {
                match x.cmp(y) {
                    Ordering::Equal => Ordering::Less,
                    o => o,
                }
            },

            (Bound::Included(x), Bound::UpperExcluded(y)) => {
                match x.cmp(y) {
                    Ordering::Equal => Ordering::Greater,
                    o => o,
                }
            },

            (Bound::LowerExcluded(x), Bound::Included(y)) => {
                match x.cmp(y) {
                    Ordering::Equal => Ordering::Greater,
                    o => o,
                }
            },

            (Bound::UpperExcluded(x), Bound::Included(y)) => {
                match x.cmp(y) {
                    Ordering::Equal => Ordering::Less,
                    o => o,
                }
            },

            (Bound::LowerExcluded(x), Bound::UpperExcluded(y)) => {
                match x.cmp(y) {
                    Ordering::Equal => Ordering::Greater,
                    o => o,
                }
            },

            (Bound::UpperExcluded(x), Bound::LowerExcluded(y)) => {
                match x.cmp(y) {
                    Ordering::Equal => Ordering::Less,
                    o => o,
                }
            },
        }
    }
}

impl <T> PartialOrd for Bound<T> where T: Ord {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

////////////////////////////////////////////////////////////////////////////////

/// Represents a single, continuous interval. The bounds are given with
/// LowerBound and UpperBound.
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub struct Interval<T> {
    start: Bound<T>,
    end:   Bound<T>,
}

impl <T> Interval<T> where T: Ord + Copy {
    /// Constructs an interval from the given Rust range.
    pub fn from_range<R>(r: R) -> Self where R: RangeBounds<T> {
        Interval{
            start: Bound::from_bound_lower(r.start_bound()),
            end: Bound::from_bound_upper(r.end_bound()),
        }
    }

    /// Constructs an interval from lower and upper interval bounds.
    pub fn from_bounds(start: Bound<T>, end: Bound<T>) -> Self {
        Interval{ start, end }
    }

    /// Returns true if the interval comes before another interval, no
    /// intersection allowed.
    pub fn is_before(&self, other: &Self) -> bool {
        self.end < other.start
    }

    /// Returns true if the interval is disjunct with another.
    pub fn is_disjunct(&self, other: &Self) -> bool {
        self.is_before(other) || other.is_before(self)
    }

    /// Returns true if the interval intersects with another.
    pub fn is_intersecting(&self, other: &Self) -> bool {
        !self.is_disjunct(other)
    }

    /// Returns true if two intervals are touching.
    pub fn is_touching(&self, other: &Self) -> bool {
           self.end.is_touching(&other.start)
        || self.start.is_touching(&other.end)
    }

    /// Returns the union of two intervals or None if the intervals cannot be
    /// unified into a single one.
    pub fn union_with(&self, other: &Self) -> Option<Self> {
        if !self.is_intersecting(other) && !self.is_touching(other) {
            None
        }
        else {
            let start = min(self.start, other.start);
            let end = max(self.end, other.end);
            Some(Interval::from_bounds(start, end))
        }
    }
}

/// Represents a union of multiple intervals. It's always the union of disjoint,
/// non-touching intervals.
#[derive(Debug, PartialEq, Eq)]
pub struct IntervalSet<T> {
    intervals: Vec<Interval<T>>,
}

impl <T> IntervalSet<T> where T: Ord + Copy {
    /// Constructs an empty interval set.
    pub fn new() -> Self {
        IntervalSet{ intervals: Vec::new() }
    }

    /// Adds an interval to the interval set. Only inserts it if it's disjoint
    /// with all other intervals. Otherwise modifies existing intervals.
    pub fn add_interval(&mut self, interval: Interval<T>) {
        let (from, to) = self.overlapping_index(&interval);

        if from == to {
            self.intervals.insert(from, interval);
        }
        else {
            self.intervals[from].start = min(
                self.intervals[from].start,
                interval.start
            );
            self.intervals[from].end = max(
                self.intervals[to - 1].end,
                interval.end
            );
            self.intervals.drain((from + 1)..to);
        }
    }

    /// Adds a native rust-range to the interval set. Basically calls
    /// add_interval after the range is converted into an interval.
    pub fn add_range<R>(&mut self, r: R) where R: RangeBounds<T> {
        self.add_interval(Interval::from_range(r));
    }

    /// Returns the index pair [from; to) where the given interval intersects
    /// with the ones in the interval set.
    fn intersecting_index(&self, interval: &Interval<T>) -> (usize, usize) {
        let from =
        match self.intervals.binary_search_by_key(&interval.start, |x| x.end) {
            Ok(idx) => idx,
            Err(idx) => idx,
        };

        let to =
        match self.intervals[from..].binary_search_by_key(&interval.end, |x| x.start) {
            Ok(idx) => idx,
            Err(idx) => idx,
        } + from;

        (from, to)
    }

    /// Returns the index pair [from; to) where the given interval overlaps
    /// (intersect or touch) with the ones in the interval set.
    fn overlapping_index(&self, interval: &Interval<T>) -> (usize, usize) {
        // Check for intersection
        let (mut from, mut to) = self.intersecting_index(interval);
        // Check for touches
        if from != 0 && interval.is_touching(&self.intervals[from - 1]) {
            from -= 1;
        }
        if to != self.intervals.len() && interval.is_touching(&self.intervals[to]) {
            to += 1;
        }

        (from, to)
    }
}

/// Creates an interval-set by adding each interval with add_interval.
macro_rules! ivset {
    ( $( $x:expr ),* ) => {
        {
            let mut iv = IntervalSet::new();
            $(
                iv.add_range($x);
            )*
            iv
        }
    };
}

/// Creates an interval-set from the elements provided, without checking order
/// or overlaps.
macro_rules! ivset_raw {
    ( $( $x:expr ),* ) => {
        {
            IntervalSet{
                intervals: vec![
                    $(
                        Interval::from_range($x)
                    ),*
                ],
            }
        }
    };
}

fn add_interval_04() -> IntervalSet<u32> {
    ivset![22..65, 78..82, 65..78]
}

fn main() {
    let iv = add_interval_04();
}