//! Range utilities.

use core::ops::{

  Bound,

  Range,

  RangeBounds,

};

/// Extension methods for working with various range types.

pub trait RangeExt<T>: RangeBounds<T>

where T: Ord

{

  /// Normalizes a range-like type to a canonical half-open `Range`.

  ///

  /// ## Parameters

  ///

  /// - `self`: The range to normalize.

  /// - `start`: An optional fallback *inclusive* lower bound.

  /// - `end`: An optional fallback *exclusive* upper bound.

  ///

  /// ## Returns

  ///

  /// A `Range` whose start and end values are the following, in order of

  /// decreasing priority:

  ///

  /// - `self.start()`, or if absent, the `start` parameter, or if it is

  ///   `None`, `0`.

  /// - `self.end()`, or if absent, the `end` parameter, or if it is `None`,

  ///   !0`.

  fn normalize(

    self,

    start: impl Into<Option<T>>,

    end: impl Into<Option<T>>,

  ) -> Range<T>;

  /// Finds the intersection between two range-likes. The produced `Range`

  /// spans only the elements common to both.

  ///

  /// This returns `None` if the ranges do not have an intersection (at least

  /// one element present in both ranges).

  fn intersection<R>(self, other: R) -> Option<Range<T>>

  where R: RangeExt<T>;

  /// Finds the union between two range-likes. The produced `Range` spans all

  /// elements present in at least one of them.

  ///

  /// This returns `None` if the ranges do not have an intersection (at least

  /// one element present in both ranges).

  fn union<R>(self, other: R) -> Option<Range<T>>

  where R: RangeExt<T>;

}

//  TODO(myrrlyn): Use funty to extend this for all integers.

impl<R> RangeExt<usize> for R

where R: RangeBounds<usize>

{

  fn normalize(

    self,

    start: impl Into<Option<usize>>,

    end: impl Into<Option<usize>>,

  ) -> Range<usize> {

    let start = match self.start_bound() {

      Bound::Unbounded => start.into().unwrap_or(0),

      Bound::Included(&v) => v,

      Bound::Excluded(&v) => v.saturating_add(1),

    };

    let end = match self.end_bound() {

      Bound::Unbounded => end.into().unwrap_or(!0),

      Bound::Included(&v) => v.saturating_add(1),

      Bound::Excluded(&v) => v,

    };

    if start > end {

      end .. start

    }

    else {

      start .. end

    }

  }

  fn intersection<R2>(self, other: R2) -> Option<Range<usize>>

  where R2: RangeExt<usize> {

    let Range { start: a1, end: a2 } = self.normalize(None, None);

    let Range { start: b1, end: b2 } = other.normalize(None, None);

    if b1 < a1 {

      return (b1 .. b2).intersection(a1 .. a2);

    }

    if !(a1 .. a2).contains(&b1) {

      return None;

    }

    let start = a1.max(b1);

    let end = a2.min(b2);

    if start > end {

      Some(end .. start)

    }

    else {

      Some(start .. end)

    }

  }

  fn union<R2>(self, other: R2) -> Option<Range<usize>>

  where R2: RangeExt<usize> {

    let Range { start: a1, end: a2 } = self.normalize(None, None);

    let Range { start: b1, end: b2 } = other.normalize(None, None);

    if b1 < a1 {

      return (b1 .. b2).intersection(a1 .. a2);

    }

    if !(a1 .. a2).contains(&b1) {

      return None;

    }

    let start = a1.min(b1);

    let end = a2.max(b2);

    if start > end {

      Some(end .. start)

    }

    else {

      Some(start .. end)

    }

  }

}

#[cfg(test)]

mod tests {

  use super::*;

  #[test]

  fn normalize() {

    let r = (..).normalize(1, 10);

    assert!(r.contains(&1));

    assert!(r.contains(&9));

    assert!(!r.contains(&0));

    assert!(!r.contains(&10));

    let r = (.. 10).normalize(1, 20);

    assert!(r.contains(&1));

    assert!(r.contains(&9));

    assert!(!r.contains(&0));

    assert!(!r.contains(&10));

    let r = (4 ..).normalize(6, 10);

    assert!(r.contains(&4));

    assert!(r.contains(&9));

    assert!(!r.contains(&3));

    assert!(!r.contains(&10));

    let r = (4 ..= 10).normalize(6, 8);

    assert!(r.contains(&4));

    assert!(r.contains(&10));

    assert!(!r.contains(&3));

    assert!(!r.contains(&11));

    let r = (..= 10).normalize(1, 8);

    assert!(r.contains(&1));

    assert!(r.contains(&10));

    assert!(!r.contains(&0));

    assert!(!r.contains(&11));

  }

  #[test]

  fn intersect() {

    let a = 3 .. 10;

    let b = 7 ..= 20;

    assert_eq!(a.intersection(b), Some(7 .. 10));

    let c = 3 .. 10;

    let d = 13 ..= 20;

    assert!(c.intersection(d).is_none());

  }

  #[test]

  fn union() {

    let a = 3 .. 10;

    let b = 7 ..= 20;

    assert_eq!(a.union(b), Some(3 .. 21));

    let c = 3 .. 10;

    let d = 13 ..= 20;

    assert!(c.union(d).is_none());

  }

}