//! Type and functions for comparing inclusive ranges

use ::{std};

use num_traits::PrimInt;

///////////////////////////////////////////////////////////////////////////////
//  enums                                                                    //
///////////////////////////////////////////////////////////////////////////////

/// Result of comparing a pair of ranges `(A,B)`
#[derive(Debug,Eq,PartialEq)]
pub enum RangeCompare {
  Disjoint  (RangeDisjoint),
  Intersect (RangeIntersect)
}

/// Ways in which a pair of ranges `(A,B)` can be disjoint
#[derive(Debug,Eq,PartialEq)]
pub enum RangeDisjoint {
  /// `A = B = {}`
  EmptyBoth,
  /// `A = {}`
  EmptyLhs,
  /// `B = {}`
  EmptyRhs,
  /// `[ A ]  [ B ]`
  LessThanProper,
  /// `[ A ][ B ]`
  LessThanAdjacent,
  /// `[ B ]  [ A ]`
  GreaterThanProper,
  /// `[ B ][ A ]`
  GreaterThanAdjacent
}

/// Ways in which a pair of ranges `(A,B)` can intersect
#[derive(Debug,Eq,PartialEq)]
pub enum RangeIntersect {
  /// `[ A=B ]`
  EqualTo,
  /// `[ A [ ] B ]`
  OverlapsLeft,
  /// `[ B [ ] A ]`
  OverlapsRight,
  /// `[ B ] A ]`
  ContainsFirst,
  /// `[ A [ B ] ]`
  ContainsProper,
  /// `[ A [ B ]`
  ContainsLast,
  /// `[ A ] B ]`
  ContainedByFirst,
  /// `[ [ A ] B ]`
  ContainedByProper,
  /// `[ B [ A ]`
  ContainedByLast
}

///////////////////////////////////////////////////////////////////////////////
//  functions                                                                //
///////////////////////////////////////////////////////////////////////////////

/// Compare two inclusive ranges.
///
/// ```
/// # #![feature(inclusive_range_syntax)]
/// # use range_set::*;
/// assert_eq!(
///   range_compare (&(0..=5), &(0..=5)),
///   RangeCompare::Intersect (RangeIntersect::EqualTo));
/// assert_eq!(
///   range_compare (&(1..=0), &(1..=0)),
///   RangeCompare::Disjoint (RangeDisjoint::EmptyBoth));
/// ```
pub fn range_compare <T : PrimInt> (
  left : &std::ops::RangeInclusive <T>, right : &std::ops::RangeInclusive <T>
) -> RangeCompare {
  if let Some (disjoint) = RangeDisjoint::compare (left, right) {
    disjoint.into()
  } else if let Some (intersect) = RangeIntersect::compare (left, right) {
    intersect.into()
  } else {
    unreachable!()
  }
}

/// Compute the intersection of two inclusive ranges. Returns an empty range
/// if they are disjoint.
///
/// ```
/// # #![feature(inclusive_range_syntax)]
/// # use range_set::*;
/// assert_eq!(
///   intersection (&(0..=3), &(2..=5)),
///   2..=3);
/// assert!(is_empty (&intersection (&(0..=2), &(3..=5))));
/// ```
pub fn intersection <T : PrimInt> (
  left : &std::ops::RangeInclusive <T>, right : &std::ops::RangeInclusive <T>
) -> std::ops::RangeInclusive <T> {
  if let None = RangeDisjoint::compare (left, right) {
    std::cmp::max (left.start, right.start)..=std::cmp::min (left.end, right.end)
  } else {
    T::one()..=T::zero()
  }
}

/// TODO: replace with standard library is_empty method when PR #48087 is merged
///
/// ```
/// # #![feature(inclusive_range_syntax)]
/// # use range_set::*;
/// assert!(is_empty (&(1..=0)));
/// ```
#[inline]
pub fn is_empty <T : PrimInt>
  (range : &std::ops::RangeInclusive <T>) -> bool
{
  range.end < range.start
}

///////////////////////////////////////////////////////////////////////////////
//  impls                                                                    //
///////////////////////////////////////////////////////////////////////////////

impl From <RangeDisjoint> for RangeCompare {
  fn from (disjoint : RangeDisjoint) -> Self {
    RangeCompare::Disjoint (disjoint)
  }
}

impl From <RangeIntersect> for RangeCompare {
  fn from (intersect : RangeIntersect) -> Self {
    RangeCompare::Intersect (intersect)
  }
}

impl RangeDisjoint {
  /// Tests two inclusive ranges for disjointness, returning `None` if they
  /// intersect.
  ///
  /// ```
  /// # #![feature(inclusive_range_syntax)]
  /// # use range_set::*;
  /// assert_eq!(RangeDisjoint::compare (&(0..=5), &(0..=5)), None);
  /// assert_eq!(
  ///   RangeDisjoint::compare (&(1..=0), &(1..=0)),
  ///   Some (RangeDisjoint::EmptyBoth));
  /// assert_eq!(
  ///   RangeDisjoint::compare (&(1..=0), &(0..=5)),
  ///   Some (RangeDisjoint::EmptyLhs));
  /// assert_eq!(
  ///   RangeDisjoint::compare (&(0..=5), &(1..=0)),
  ///   Some (RangeDisjoint::EmptyRhs));
  /// assert_eq!(
  ///   RangeDisjoint::compare (&(0..=2), &(4..=5)),
  ///   Some (RangeDisjoint::LessThanProper));
  /// assert_eq!(
  ///   RangeDisjoint::compare (&(0..=2), &(3..=5)),
  ///   Some (RangeDisjoint::LessThanAdjacent));
  /// assert_eq!(
  ///   RangeDisjoint::compare (&(4..=5), &(0..=2)),
  ///   Some (RangeDisjoint::GreaterThanProper));
  /// assert_eq!(
  ///   RangeDisjoint::compare (&(3..=5), &(0..=2)),
  ///   Some (RangeDisjoint::GreaterThanAdjacent));
  /// ```
  pub fn compare <T : PrimInt> (
    left : &std::ops::RangeInclusive <T>, right : &std::ops::RangeInclusive <T>
  ) -> Option <Self> {
    match (is_empty (left), is_empty (right)) {
      (true, true)   => Some (RangeDisjoint::EmptyBoth),
      (true, false)  => Some (RangeDisjoint::EmptyLhs),
      (false, true)  => Some (RangeDisjoint::EmptyRhs),
      (false, false) => if right.start <= left.end && left.start <= right.end
        || left.start <= right.end && right.start <= left.end
      {
        None  // intersection
      } else {
        Some (
          if left.end < right.start {
            match right.start - left.end {
              x if x == T::one() => RangeDisjoint::LessThanAdjacent,
              _                  => RangeDisjoint::LessThanProper
            }
          } else {
            debug_assert!(right.end < left.start);
            match left.start - right.end {
              x if x == T::one() => RangeDisjoint::GreaterThanAdjacent,
              _                  => RangeDisjoint::GreaterThanProper
            }
          }
        )
      }
    }
  }
}

impl RangeIntersect {
  /// Test two inclusive ranges for intersection, returning `None` if the
  /// ranges are disjoint.
  ///
  /// ```
  /// # #![feature(inclusive_range_syntax)]
  /// # use range_set::*;
  /// assert_eq!(RangeIntersect::compare (&(0..=1), &(4..=5)), None);
  /// assert_eq!(
  ///   RangeIntersect::compare (&(0..=5), &(0..=5)),
  ///   Some (RangeIntersect::EqualTo));
  /// assert_eq!(
  ///   RangeIntersect::compare (&(0..=5), &(1..=4)),
  ///   Some (RangeIntersect::ContainsProper));
  /// assert_eq!(
  ///   RangeIntersect::compare (&(1..=4), &(0..=5)),
  ///   Some (RangeIntersect::ContainedByProper));
  /// assert_eq!(
  ///   RangeIntersect::compare (&(0..=5), &(0..=3)),
  ///   Some (RangeIntersect::ContainsFirst));
  /// assert_eq!(
  ///   RangeIntersect::compare (&(0..=5), &(4..=5)),
  ///   Some (RangeIntersect::ContainsLast));
  /// assert_eq!(
  ///   RangeIntersect::compare (&(0..=2), &(0..=5)),
  ///   Some (RangeIntersect::ContainedByFirst));
  /// assert_eq!(
  ///   RangeIntersect::compare (&(4..=5), &(0..=5)),
  ///   Some (RangeIntersect::ContainedByLast));
  /// assert_eq!(
  ///   RangeIntersect::compare (&(0..=3), &(3..=5)),
  ///   Some (RangeIntersect::OverlapsLeft));
  /// assert_eq!(
  ///   RangeIntersect::compare (&(3..=5), &(0..=3)),
  ///   Some (RangeIntersect::OverlapsRight));
  /// ```
  pub fn compare <T : PrimInt> (
    left : &std::ops::RangeInclusive <T>, right : &std::ops::RangeInclusive <T>
  ) -> Option <Self> {
    match (is_empty (left), is_empty (right)) {
      (true, true) | (true, false) | (false, true) => None,
      (false, false) => if left.end < right.start || right.end < left.start {
        None  // disjoint
      } else {
        Some (if left == right {
          RangeIntersect::EqualTo
        } else {
          match left.start.cmp (&right.start) {
            std::cmp::Ordering::Less => match left.end.cmp (&right.end) {
              std::cmp::Ordering::Less    => RangeIntersect::OverlapsLeft,
              std::cmp::Ordering::Equal   => RangeIntersect::ContainsLast,
              std::cmp::Ordering::Greater => RangeIntersect::ContainsProper
            }
            std::cmp::Ordering::Equal => match left.end.cmp (&right.end) {
              std::cmp::Ordering::Less    => RangeIntersect::ContainedByFirst,
              std::cmp::Ordering::Equal   => unreachable!(),
              std::cmp::Ordering::Greater => RangeIntersect::ContainsFirst
            }
            std::cmp::Ordering::Greater => match left.end.cmp (&right.end) {
              std::cmp::Ordering::Less    => RangeIntersect::ContainedByProper,
              std::cmp::Ordering::Equal   => RangeIntersect::ContainedByLast,
              std::cmp::Ordering::Greater => RangeIntersect::OverlapsRight
            }
          }
        })
      }
    }
  }
}