intervalmap 0.1.1

use std::ops::{
    BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Range, RangeBounds, Sub,
    SubAssign,
};

use crate::{
    interval_map::{IntervalMap, IntoIter, Iter},
    IndexType,
};

/// A set of non-overlapping intervals with automatic merging.
///
/// `IntervalSet` stores a collection of non-overlapping intervals. When inserting
/// intervals that overlap or are adjacent, they are automatically merged into
/// a single interval.
///
/// # Type Parameters
///
/// * `Ix` - The index type for interval bounds. Defaults to `u32`.
///
/// # Examples
///
/// ```
/// use intervalmap::IntervalSet;
///
/// let mut set = IntervalSet::new();
/// set.insert(0..10);
/// set.insert(5..15);  // Merges with [0, 10) to form [0, 15)
///
/// assert!(set.contains(7));
/// assert!(!set.contains(20));
/// ```
#[derive(Debug, Clone)]
pub struct IntervalSet<Ix = u32> {
    inner: IntervalMap<Ix, ()>,
}

impl<Ix: IndexType> Default for IntervalSet<Ix> {
    fn default() -> Self {
        Self::new()
    }
}

impl<Ix: IndexType> IntervalSet<Ix> {
    /// Creates a new, empty `IntervalSet`.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let set: IntervalSet<u32> = IntervalSet::new();
    /// assert!(set.is_empty());
    /// ```
    #[inline]
    pub fn new() -> Self {
        IntervalSet {
            inner: IntervalMap::new(),
        }
    }

    /// Returns the number of intervals in the set.
    #[inline]
    pub fn len(&self) -> usize {
        self.inner.len()
    }

    /// Returns `true` if the set contains no intervals.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }

    /// Removes all intervals from the set.
    #[inline]
    pub fn clear(&mut self) {
        self.inner.clear();
    }

    /// Returns `true` if the set contains an interval covering the given point.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// set.insert(0..10);
    ///
    /// assert!(set.contains(5));
    /// assert!(!set.contains(10));
    /// ```
    #[inline]
    pub fn contains(&self, point: Ix) -> bool {
        self.inner.contains(point)
    }

    /// Returns the interval containing the given point, if any.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// set.insert(5..15);
    ///
    /// assert_eq!(set.get_interval(10), Some(5..15));
    /// assert_eq!(set.get_interval(20), None);
    /// ```
    pub fn get_interval(&self, point: Ix) -> Option<Range<Ix>> {
        self.inner.get_interval(point).map(|(range, _)| range)
    }

    /// Returns an iterator over the intervals in the set.
    ///
    /// Intervals are yielded in ascending order by start position.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// set.insert(0..10);
    /// set.insert(20..30);
    ///
    /// let intervals: Vec<_> = set.iter().collect();
    /// assert_eq!(intervals, vec![0..10, 20..30]);
    /// ```
    pub fn iter(&self) -> IterSet<'_, Ix> {
        IterSet {
            inner: self.inner.iter(),
        }
    }

    /// Returns the first (lowest) interval, or `None` if empty.
    ///
    /// This is an O(log n) operation.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// assert_eq!(set.first(), None);
    ///
    /// set.insert(10..20);
    /// set.insert(0..5);
    /// assert_eq!(set.first(), Some(0..5));
    /// ```
    pub fn first(&self) -> Option<Range<Ix>> {
        self.inner.first().map(|(range, _)| range)
    }

    /// Returns the last (highest) interval, or `None` if empty.
    ///
    /// This is an O(log n) operation.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// assert_eq!(set.last(), None);
    ///
    /// set.insert(0..5);
    /// set.insert(10..20);
    /// assert_eq!(set.last(), Some(10..20));
    /// ```
    pub fn last(&self) -> Option<Range<Ix>> {
        self.inner.last().map(|(range, _)| range)
    }

    /// Returns the bounding interval that spans from the start of the first
    /// interval to the end of the last interval, or `None` if empty.
    ///
    /// This is an O(log n) operation.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// assert_eq!(set.span(), None);
    ///
    /// set.insert(5..10);
    /// set.insert(20..30);
    /// assert_eq!(set.span(), Some(5..30));
    /// ```
    pub fn span(&self) -> Option<Range<Ix>> {
        self.inner.span()
    }
}

impl<Ix: IndexType + num_traits::One + num_traits::Bounded> IntervalSet<Ix> {
    /// Returns `true` if any interval in the set overlaps with the given range.
    ///
    /// This is an O(log n) operation.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// set.insert(10..20);
    ///
    /// assert!(set.overlaps(15..25));
    /// assert!(set.overlaps(5..15));
    /// assert!(!set.overlaps(0..5));
    /// assert!(!set.overlaps(25..30));
    /// ```
    pub fn overlaps<R: RangeBounds<Ix>>(&self, range: R) -> bool {
        self.inner.overlaps(range)
    }

    /// Returns `true` if the entire range is covered by intervals in the set.
    ///
    /// This is an O(log n + k) operation where k is the number of intervals
    /// overlapping the range.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// set.insert(0..10);
    /// set.insert(10..20);
    ///
    /// assert!(set.covers(5..15));
    /// assert!(set.covers(0..20));
    /// assert!(!set.covers(0..25));  // 20..25 not covered
    /// ```
    pub fn covers<R: RangeBounds<Ix>>(&self, range: R) -> bool {
        self.inner.covers(range)
    }

    /// Inserts an interval into the set.
    ///
    /// If the interval overlaps or is adjacent to existing intervals,
    /// they will be merged.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// set.insert(0..10);
    /// set.insert(10..20);  // Merges into [0, 20)
    ///
    /// assert_eq!(set.len(), 1);
    /// ```
    pub fn insert<R: RangeBounds<Ix>>(&mut self, range: R) {
        self.inner.insert(range, ());
    }

    /// Removes an interval from the set.
    ///
    /// Any existing intervals that overlap with the removed range will be
    /// split, with the overlapping portions removed.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// set.insert(0..20);
    /// set.remove(5..15);
    ///
    /// // Result: [0,5) and [15,20)
    /// assert!(set.contains(3));
    /// assert!(!set.contains(10));
    /// assert!(set.contains(17));
    /// ```
    pub fn remove<R: RangeBounds<Ix>>(&mut self, range: R) {
        self.inner.remove(range);
    }

    /// Returns a new set containing all intervals from both sets.
    ///
    /// Overlapping and adjacent intervals are merged automatically.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::interval_set;
    ///
    /// let a = interval_set!{ 0..10, 20..30 };
    /// let b = interval_set!{ 5..25 };
    /// let union = a.union(&b);
    ///
    /// assert_eq!(union.len(), 1);
    /// assert!(union.contains(15));
    /// ```
    pub fn union(&self, other: &Self) -> Self {
        let mut result = self.clone();
        for interval in other.iter() {
            result.insert(interval);
        }
        result
    }

    /// Returns a new set containing only intervals covered by both sets.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::interval_set;
    ///
    /// let a = interval_set!{ 0..10, 20..30 };
    /// let b = interval_set!{ 5..25 };
    /// let intersection = a.intersection(&b);
    ///
    /// let intervals: Vec<_> = intersection.iter().collect();
    /// assert_eq!(intervals, vec![5..10, 20..25]);
    /// ```
    pub fn intersection(&self, other: &Self) -> Self {
        let mut result = IntervalSet::new();
        let mut iter_a = self.iter().peekable();
        let mut iter_b = other.iter().peekable();

        while let (Some(a), Some(b)) = (iter_a.peek(), iter_b.peek()) {
            // Calculate intersection of current intervals
            let start = a.start.max(b.start);
            let end = a.end.min(b.end);

            if start < end {
                result.insert(start..end);
            }

            // Advance the iterator with the smaller end
            if a.end <= b.end {
                iter_a.next();
            }
            else {
                iter_b.next();
            }
        }

        result
    }

    /// Returns a new set containing intervals from `self` that are not in `other`.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::interval_set;
    ///
    /// let a = interval_set!{ 0..20 };
    /// let b = interval_set!{ 5..15 };
    /// let difference = a.difference(&b);
    ///
    /// let intervals: Vec<_> = difference.iter().collect();
    /// assert_eq!(intervals, vec![0..5, 15..20]);
    /// ```
    pub fn difference(&self, other: &Self) -> Self {
        let mut result = self.clone();
        for interval in other.iter() {
            result.remove(interval);
        }
        result
    }

    /// Returns a new set containing intervals that are in either set, but not both.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::interval_set;
    ///
    /// let a = interval_set!{ 0..10 };
    /// let b = interval_set!{ 5..15 };
    /// let sym_diff = a.symmetric_difference(&b);
    ///
    /// let intervals: Vec<_> = sym_diff.iter().collect();
    /// assert_eq!(intervals, vec![0..5, 10..15]);
    /// ```
    pub fn symmetric_difference(&self, other: &Self) -> Self {
        // (A - B) | (B - A)
        let a_minus_b = self.difference(other);
        let b_minus_a = other.difference(self);
        a_minus_b.union(&b_minus_a)
    }

    /// Returns an iterator over the gaps between intervals in the set.
    ///
    /// This iterates over the ranges that are NOT covered by any interval
    /// in the set, but only between the first and last intervals. It does
    /// not yield unbounded gaps before the first interval or after the last.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// set.insert(0..10);
    /// set.insert(20..30);
    /// set.insert(40..50);
    ///
    /// let gaps: Vec<_> = set.gaps().collect();
    /// assert_eq!(gaps, vec![10..20, 30..40]);
    /// ```
    pub fn gaps(&self) -> Gaps<'_, Ix> {
        Gaps {
            inner: self.inner.iter(),
            prev_end: None,
        }
    }

    /// Returns an iterator over intervals that overlap with the given range.
    ///
    /// This is an O(log n + k) operation where k is the number of overlapping intervals.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// set.insert(0..10);
    /// set.insert(20..30);
    /// set.insert(40..50);
    ///
    /// let overlapping: Vec<_> = set.iter_overlapping(15..45).collect();
    /// assert_eq!(overlapping, vec![20..30, 40..50]);
    /// ```
    pub fn iter_overlapping<R: RangeBounds<Ix>>(&self, range: R) -> IterOverlapping<'_, Ix> {
        IterOverlapping::new(&self.inner, range)
    }

    /// Keeps only the intervals matching the predicate.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// set.insert(0..10);
    /// set.insert(20..30);
    /// set.insert(40..50);
    ///
    /// // Keep only intervals that start before 25
    /// set.retain(|r| r.start < 25);
    ///
    /// let intervals: Vec<_> = set.iter().collect();
    /// assert_eq!(intervals, vec![0..10, 20..30]);
    /// ```
    pub fn retain<F: FnMut(&Range<Ix>) -> bool>(&mut self, mut f: F) {
        let keys_to_remove: Vec<Ix> = self
            .inner
            .iter()
            .filter_map(|(range, _)| {
                if !f(&range) {
                    Some(range.start)
                }
                else {
                    None
                }
            })
            .collect();

        for key in keys_to_remove {
            self.inner.remove_by_start(key);
        }
    }

    /// Splits all intervals at the given point.
    ///
    /// If an interval contains the point, it will be split into two intervals:
    /// one ending at the point and one starting at the point.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalSet;
    ///
    /// let mut set = IntervalSet::new();
    /// set.insert(0..20);
    ///
    /// set.split_at(10);
    ///
    /// let intervals: Vec<_> = set.iter().collect();
    /// assert_eq!(intervals, vec![0..10, 10..20]);
    /// ```
    pub fn split_at(&mut self, point: Ix) {
        self.inner.split_at(point);
    }
}

/// An iterator over the intervals in an `IntervalSet`.
pub struct IterSet<'a, Ix> {
    inner: Iter<'a, Ix, ()>,
}

impl<'a, Ix: IndexType> Iterator for IterSet<'a, Ix> {
    type Item = Range<Ix>;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|(range, _)| range)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

impl<Ix: IndexType> ExactSizeIterator for IterSet<'_, Ix> {}

impl<'a, Ix: IndexType> IntoIterator for &'a IntervalSet<Ix> {
    type Item = Range<Ix>;
    type IntoIter = IterSet<'a, Ix>;

    fn into_iter(self) -> Self::IntoIter {
        IterSet {
            inner: self.inner.iter(),
        }
    }
}

/// An owning iterator over the intervals in an `IntervalSet`.
pub struct IntoIterSet<Ix> {
    inner: IntoIter<Ix, ()>,
}

impl<Ix: IndexType> Iterator for IntoIterSet<Ix> {
    type Item = Range<Ix>;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|(range, _)| range)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

impl<Ix: IndexType> ExactSizeIterator for IntoIterSet<Ix> {}

impl<Ix: IndexType> IntoIterator for IntervalSet<Ix> {
    type Item = Range<Ix>;
    type IntoIter = IntoIterSet<Ix>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIterSet {
            inner: self.inner.into_iter(),
        }
    }
}

/// An iterator over the gaps between intervals in an `IntervalSet`.
pub struct Gaps<'a, Ix> {
    inner: Iter<'a, Ix, ()>,
    prev_end: Option<Ix>,
}

impl<'a, Ix: IndexType> Iterator for Gaps<'a, Ix> {
    type Item = Range<Ix>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let (range, _) = self.inner.next()?;

            match self.prev_end {
                None => {
                    // First interval - just record its end
                    self.prev_end = Some(range.end);
                }
                Some(prev_end) => {
                    self.prev_end = Some(range.end);
                    if prev_end < range.start {
                        // There's a gap between prev_end and this interval's start
                        return Some(prev_end..range.start);
                    }
                    // No gap - intervals are adjacent or overlapping (shouldn't happen)
                }
            }
        }
    }
}

/// An iterator over intervals that overlap with a given range.
pub struct IterOverlapping<'a, Ix: IndexType> {
    inner: Iter<'a, Ix, ()>,
    range_start: Ix,
    range_end: Ix,
    started: bool,
}

impl<'a, Ix: IndexType + num_traits::One + num_traits::Bounded> IterOverlapping<'a, Ix> {
    fn new<R: RangeBounds<Ix>>(map: &'a IntervalMap<Ix, ()>, range: R) -> Self {
        use std::ops::Bound;

        let range_start = match range.start_bound() {
            Bound::Included(&s) => s,
            Bound::Excluded(&s) => s + Ix::one(),
            Bound::Unbounded => Ix::min_value(),
        };

        let range_end = match range.end_bound() {
            Bound::Included(&e) => e + Ix::one(),
            Bound::Excluded(&e) => e,
            Bound::Unbounded => Ix::max_value(),
        };

        IterOverlapping {
            inner: map.iter(),
            range_start,
            range_end,
            started: false,
        }
    }
}

impl<'a, Ix: IndexType> Iterator for IterOverlapping<'a, Ix> {
    type Item = Range<Ix>;

    fn next(&mut self) -> Option<Self::Item> {
        // Empty query range can't overlap with anything
        if self.range_start >= self.range_end {
            return None;
        }

        loop {
            let (interval, _) = self.inner.next()?;

            // Check if interval ends before our range starts - skip it
            if interval.end <= self.range_start {
                continue;
            }

            // Check if interval starts at or after our range ends - we're done
            if interval.start >= self.range_end {
                return None;
            }

            // Interval overlaps with our range
            self.started = true;
            return Some(interval);
        }
    }
}

// ============================================================================
// Operator Implementations
// ============================================================================

/// Union: `&a | &b`
impl<Ix: IndexType + num_traits::One + num_traits::Bounded> BitOr<&IntervalSet<Ix>>
    for &IntervalSet<Ix>
{
    type Output = IntervalSet<Ix>;

    fn bitor(self, other: &IntervalSet<Ix>) -> Self::Output {
        self.union(other)
    }
}

/// Intersection: `&a & &b`
impl<Ix: IndexType + num_traits::One + num_traits::Bounded> BitAnd<&IntervalSet<Ix>>
    for &IntervalSet<Ix>
{
    type Output = IntervalSet<Ix>;

    fn bitand(self, other: &IntervalSet<Ix>) -> Self::Output {
        self.intersection(other)
    }
}

/// Difference: `&a - &b`
impl<Ix: IndexType + num_traits::One + num_traits::Bounded> Sub<&IntervalSet<Ix>>
    for &IntervalSet<Ix>
{
    type Output = IntervalSet<Ix>;

    fn sub(self, other: &IntervalSet<Ix>) -> Self::Output {
        self.difference(other)
    }
}

/// Symmetric Difference: `&a ^ &b`
impl<Ix: IndexType + num_traits::One + num_traits::Bounded> BitXor<&IntervalSet<Ix>>
    for &IntervalSet<Ix>
{
    type Output = IntervalSet<Ix>;

    fn bitxor(self, other: &IntervalSet<Ix>) -> Self::Output {
        self.symmetric_difference(other)
    }
}

/// Union assignment: `a |= &b`
impl<Ix: IndexType + num_traits::One + num_traits::Bounded> BitOrAssign<&IntervalSet<Ix>>
    for IntervalSet<Ix>
{
    fn bitor_assign(&mut self, other: &IntervalSet<Ix>) {
        for interval in other.iter() {
            self.insert(interval);
        }
    }
}

/// Intersection assignment: `a &= &b`
impl<Ix: IndexType + num_traits::One + num_traits::Bounded> BitAndAssign<&IntervalSet<Ix>>
    for IntervalSet<Ix>
{
    fn bitand_assign(&mut self, other: &IntervalSet<Ix>) {
        *self = self.intersection(other);
    }
}

/// Difference assignment: `a -= &b`
impl<Ix: IndexType + num_traits::One + num_traits::Bounded> SubAssign<&IntervalSet<Ix>>
    for IntervalSet<Ix>
{
    fn sub_assign(&mut self, other: &IntervalSet<Ix>) {
        for interval in other.iter() {
            self.remove(interval);
        }
    }
}

/// Symmetric difference assignment: `a ^= &b`
impl<Ix: IndexType + num_traits::One + num_traits::Bounded> BitXorAssign<&IntervalSet<Ix>>
    for IntervalSet<Ix>
{
    fn bitxor_assign(&mut self, other: &IntervalSet<Ix>) {
        *self = self.symmetric_difference(other);
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_interval_set_insert_and_merge() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(5..15);

        // Should merge into [0, 15)
        assert_eq!(set.len(), 1);
        assert!(set.contains(0));
        assert!(set.contains(14));
        assert!(!set.contains(15));
    }

    #[test]
    fn test_interval_set_adjacent_merge() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(10..20);

        // Should merge into [0, 20)
        assert_eq!(set.len(), 1);
        assert!(set.contains(0));
        assert!(set.contains(15));
        assert!(!set.contains(20));
    }

    #[test]
    fn test_interval_set_non_overlapping() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);

        assert_eq!(set.len(), 2);
        assert!(set.contains(5));
        assert!(!set.contains(15));
        assert!(set.contains(25));
    }

    #[test]
    fn test_interval_set_iter() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);

        let intervals: Vec<_> = set.iter().collect();
        assert_eq!(intervals, vec![0..10, 20..30]);
    }

    #[test]
    fn test_interval_set_remove() {
        let mut set = IntervalSet::new();
        set.insert(0..20);
        set.remove(5..15);

        assert_eq!(set.len(), 2);
        assert!(set.contains(3));
        assert!(!set.contains(10));
        assert!(set.contains(17));
    }

    #[test]
    fn test_interval_set_into_iter() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);

        let intervals: Vec<_> = set.into_iter().collect();
        assert_eq!(intervals, vec![0..10, 20..30]);
    }

    // ========================================================================
    // Tests for new utility methods
    // ========================================================================

    #[test]
    fn test_first_empty() {
        let set: IntervalSet<u32> = IntervalSet::new();
        assert_eq!(set.first(), None);
    }

    #[test]
    fn test_first_single() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        assert_eq!(set.first(), Some(10..20));
    }

    #[test]
    fn test_first_multiple() {
        let mut set = IntervalSet::new();
        set.insert(20..30);
        set.insert(5..10);
        set.insert(40..50);
        assert_eq!(set.first(), Some(5..10));
    }

    #[test]
    fn test_last_empty() {
        let set: IntervalSet<u32> = IntervalSet::new();
        assert_eq!(set.last(), None);
    }

    #[test]
    fn test_last_single() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        assert_eq!(set.last(), Some(10..20));
    }

    #[test]
    fn test_last_multiple() {
        let mut set = IntervalSet::new();
        set.insert(20..30);
        set.insert(5..10);
        set.insert(40..50);
        assert_eq!(set.last(), Some(40..50));
    }

    #[test]
    fn test_span_empty() {
        let set: IntervalSet<u32> = IntervalSet::new();
        assert_eq!(set.span(), None);
    }

    #[test]
    fn test_span_single() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        assert_eq!(set.span(), Some(10..20));
    }

    #[test]
    fn test_span_multiple() {
        let mut set = IntervalSet::new();
        set.insert(5..10);
        set.insert(20..30);
        set.insert(40..50);
        assert_eq!(set.span(), Some(5..50));
    }

    #[test]
    fn test_overlaps_empty() {
        let set: IntervalSet<u32> = IntervalSet::new();
        assert!(!set.overlaps(0..10));
    }

    #[test]
    fn test_overlaps_no_overlap() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        assert!(!set.overlaps(0..5));
        assert!(!set.overlaps(25..30));
        assert!(!set.overlaps(0..10)); // Adjacent, not overlapping
        assert!(!set.overlaps(20..30)); // Adjacent, not overlapping
    }

    #[test]
    fn test_overlaps_partial() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        assert!(set.overlaps(5..15));
        assert!(set.overlaps(15..25));
    }

    #[test]
    fn test_overlaps_contained() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        assert!(set.overlaps(12..18));
    }

    #[test]
    fn test_overlaps_containing() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        assert!(set.overlaps(5..25));
    }

    #[test]
    fn test_covers_empty_range() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        // Empty range is always covered
        assert!(set.covers(15..15));
    }

    #[test]
    fn test_covers_empty_set() {
        let set: IntervalSet<u32> = IntervalSet::new();
        assert!(!set.covers(0..10));
    }

    #[test]
    fn test_covers_fully_covered() {
        let mut set = IntervalSet::new();
        set.insert(0..30);
        assert!(set.covers(5..25));
        assert!(set.covers(0..30));
    }

    #[test]
    fn test_covers_contiguous() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(10..20);
        set.insert(20..30);
        assert!(set.covers(0..30));
        assert!(set.covers(5..25));
    }

    #[test]
    fn test_covers_with_gap() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);
        assert!(!set.covers(0..30));
        assert!(!set.covers(5..25));
    }

    #[test]
    fn test_covers_partial() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        assert!(!set.covers(0..15)); // Starts before
        assert!(!set.covers(15..25)); // Ends after
    }

    #[test]
    fn test_gaps_empty() {
        let set: IntervalSet<u32> = IntervalSet::new();
        let gaps: Vec<_> = set.gaps().collect();
        assert!(gaps.is_empty());
    }

    #[test]
    fn test_gaps_single_interval() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        let gaps: Vec<_> = set.gaps().collect();
        assert!(gaps.is_empty());
    }

    #[test]
    fn test_gaps_adjacent() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(10..20);
        // Adjacent intervals get merged, so this becomes one interval
        let gaps: Vec<_> = set.gaps().collect();
        assert!(gaps.is_empty());
    }

    #[test]
    fn test_gaps_multiple() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);
        set.insert(40..50);
        let gaps: Vec<_> = set.gaps().collect();
        assert_eq!(gaps, vec![10..20, 30..40]);
    }

    #[test]
    fn test_iter_overlapping_empty() {
        let set: IntervalSet<u32> = IntervalSet::new();
        let overlapping: Vec<_> = set.iter_overlapping(0..100).collect();
        assert!(overlapping.is_empty());
    }

    #[test]
    fn test_iter_overlapping_none() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);
        let overlapping: Vec<_> = set.iter_overlapping(12..18).collect();
        assert!(overlapping.is_empty());
    }

    #[test]
    fn test_iter_overlapping_some() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);
        set.insert(40..50);
        let overlapping: Vec<_> = set.iter_overlapping(15..45).collect();
        assert_eq!(overlapping, vec![20..30, 40..50]);
    }

    #[test]
    fn test_iter_overlapping_all() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);
        let overlapping: Vec<_> = set.iter_overlapping(0..100).collect();
        assert_eq!(overlapping, vec![0..10, 20..30]);
    }

    #[test]
    fn test_retain_all() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);
        set.retain(|_| true);
        assert_eq!(set.len(), 2);
    }

    #[test]
    fn test_retain_none() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);
        set.retain(|_| false);
        assert!(set.is_empty());
    }

    #[test]
    fn test_retain_some() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);
        set.insert(40..50);
        set.retain(|r| r.start >= 20);
        let intervals: Vec<_> = set.iter().collect();
        assert_eq!(intervals, vec![20..30, 40..50]);
    }

    #[test]
    fn test_split_at_empty() {
        let mut set: IntervalSet<u32> = IntervalSet::new();
        set.split_at(10);
        assert!(set.is_empty());
    }

    #[test]
    fn test_split_at_outside() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        set.split_at(5);
        set.split_at(25);
        // Nothing should change
        let intervals: Vec<_> = set.iter().collect();
        assert_eq!(intervals, vec![10..20]);
    }

    #[test]
    fn test_split_at_boundary() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        set.split_at(10);
        set.split_at(20);
        // Nothing should change
        let intervals: Vec<_> = set.iter().collect();
        assert_eq!(intervals, vec![10..20]);
    }

    #[test]
    fn test_split_at_middle() {
        let mut set = IntervalSet::new();
        set.insert(0..20);
        set.split_at(10);
        let intervals: Vec<_> = set.iter().collect();
        assert_eq!(intervals, vec![0..10, 10..20]);
    }

    #[test]
    fn test_split_at_multiple() {
        let mut set = IntervalSet::new();
        set.insert(0..30);
        set.split_at(10);
        set.split_at(20);
        let intervals: Vec<_> = set.iter().collect();
        assert_eq!(intervals, vec![0..10, 10..20, 20..30]);
    }

    // ========================================================================
    // Corner Cases for Utility Methods
    // ========================================================================

    // --- first()/last() corner cases ---

    #[test]
    fn test_first_last_after_modifications() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        assert_eq!(set.first(), Some(10..20));
        assert_eq!(set.last(), Some(10..20));

        // Add interval before
        set.insert(0..5);
        assert_eq!(set.first(), Some(0..5));
        assert_eq!(set.last(), Some(10..20));

        // Add interval after
        set.insert(30..40);
        assert_eq!(set.first(), Some(0..5));
        assert_eq!(set.last(), Some(30..40));

        // Remove first
        set.remove(0..5);
        assert_eq!(set.first(), Some(10..20));

        // Remove last
        set.remove(30..40);
        assert_eq!(set.last(), Some(10..20));
    }

    #[test]
    fn test_first_last_single_point_interval() {
        let mut set = IntervalSet::new();
        set.insert(5..6); // Single point [5, 6)
        assert_eq!(set.first(), Some(5..6));
        assert_eq!(set.last(), Some(5..6));
    }

    // --- span() corner cases ---

    #[test]
    fn test_span_single_point() {
        let mut set = IntervalSet::new();
        set.insert(5..6);
        assert_eq!(set.span(), Some(5..6));
    }

    #[test]
    fn test_span_after_split() {
        let mut set = IntervalSet::new();
        set.insert(0..100);
        let span_before = set.span();
        set.split_at(50);
        let span_after = set.span();
        // Span should remain the same after split
        assert_eq!(span_before, span_after);
        assert_eq!(span_after, Some(0..100));
    }

    #[test]
    fn test_span_with_gaps() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(90..100);
        // Span includes the gaps
        assert_eq!(set.span(), Some(0..100));
    }

    // --- overlaps() corner cases ---

    #[test]
    fn test_overlaps_empty_query() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        // Empty range should not overlap
        assert!(!set.overlaps(15..15));
    }

    #[test]
    fn test_overlaps_single_point_query() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        // Single point that's inside
        assert!(set.overlaps(15..16));
        // Single point at start
        assert!(set.overlaps(10..11));
        // Single point at end (exclusive, so no overlap)
        assert!(!set.overlaps(20..21));
    }

    #[test]
    fn test_overlaps_exact_match() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        assert!(set.overlaps(10..20));
    }

    #[test]
    fn test_overlaps_touching_boundaries() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        set.insert(30..40);
        // Query that touches but doesn't overlap
        assert!(!set.overlaps(20..30));
        // Query that overlaps end of first
        assert!(set.overlaps(19..30));
        // Query that overlaps start of second
        assert!(set.overlaps(20..31));
    }

    // --- covers() corner cases ---

    #[test]
    fn test_covers_single_point() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        // Single point inside
        assert!(set.covers(15..16));
        // Single point at start
        assert!(set.covers(10..11));
        // Single point just before end
        assert!(set.covers(19..20));
    }

    #[test]
    fn test_covers_exact_boundaries() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        // Exact match
        assert!(set.covers(10..20));
        // Starts at boundary
        assert!(set.covers(10..15));
        // Ends at boundary
        assert!(set.covers(15..20));
    }

    #[test]
    fn test_covers_after_split() {
        let mut set = IntervalSet::new();
        set.insert(0..100);
        assert!(set.covers(25..75));
        set.split_at(50);
        // Should still cover after split
        assert!(set.covers(25..75));
    }

    #[test]
    fn test_covers_barely_not_covered() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        // One point beyond
        assert!(!set.covers(10..21));
        assert!(!set.covers(9..20));
    }

    // --- gaps() corner cases ---

    #[test]
    fn test_gaps_two_intervals_no_gap() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(10..20); // Adjacent - will merge
                            // After merge, no gaps
        let gaps: Vec<_> = set.gaps().collect();
        assert!(gaps.is_empty());
        assert_eq!(set.len(), 1); // Merged into one
    }

    #[test]
    fn test_gaps_single_point_intervals() {
        let mut set = IntervalSet::new();
        set.insert(0..1);
        set.insert(5..6);
        set.insert(10..11);
        let gaps: Vec<_> = set.gaps().collect();
        assert_eq!(gaps, vec![1..5, 6..10]);
    }

    #[test]
    fn test_gaps_large_gap() {
        let mut set: IntervalSet<u32> = IntervalSet::new();
        set.insert(0..10);
        set.insert(1000000..1000010);
        let gaps: Vec<_> = set.gaps().collect();
        assert_eq!(gaps, vec![10..1000000]);
    }

    // --- iter_overlapping() corner cases ---

    #[test]
    fn test_iter_overlapping_exact_match() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);
        set.insert(40..50);
        // Query exactly matching one interval
        let overlapping: Vec<_> = set.iter_overlapping(20..30).collect();
        assert_eq!(overlapping, vec![20..30]);
    }

    #[test]
    fn test_iter_overlapping_empty_query() {
        let mut set = IntervalSet::new();
        set.insert(0..100);
        let overlapping: Vec<_> = set.iter_overlapping(50..50).collect();
        assert!(overlapping.is_empty());
    }

    #[test]
    fn test_iter_overlapping_partial_overlap() {
        let mut set = IntervalSet::new();
        set.insert(10..20);
        // Query that partially overlaps
        let overlapping: Vec<_> = set.iter_overlapping(15..25).collect();
        assert_eq!(overlapping, vec![10..20]);
        let overlapping: Vec<_> = set.iter_overlapping(5..15).collect();
        assert_eq!(overlapping, vec![10..20]);
    }

    #[test]
    fn test_iter_overlapping_between_intervals() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);
        // Query in the gap
        let overlapping: Vec<_> = set.iter_overlapping(12..18).collect();
        assert!(overlapping.is_empty());
    }

    // --- retain() corner cases ---

    #[test]
    fn test_retain_by_length() {
        let mut set = IntervalSet::new();
        set.insert(0..5); // length 5
        set.insert(10..30); // length 20
        set.insert(40..45); // length 5
                            // Keep only intervals with length > 10
        set.retain(|r| r.end - r.start > 10);
        let intervals: Vec<_> = set.iter().collect();
        assert_eq!(intervals, vec![10..30]);
    }

    #[test]
    fn test_retain_then_operations() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);
        set.insert(40..50);
        set.retain(|r| r.start >= 20);

        // Operations should still work after retain
        assert_eq!(set.first(), Some(20..30));
        assert_eq!(set.last(), Some(40..50));
        assert_eq!(set.span(), Some(20..50));
        assert!(set.overlaps(25..45));
        assert!(set.covers(22..28));
    }

    #[test]
    fn test_retain_empty_result() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.retain(|r| r.start > 100);
        assert!(set.is_empty());
        assert_eq!(set.first(), None);
        assert_eq!(set.span(), None);
    }

    // --- split_at() corner cases ---

    #[test]
    fn test_split_at_same_point_twice() {
        let mut set = IntervalSet::new();
        set.insert(0..30);
        set.split_at(15);
        set.split_at(15); // Second split at same point - should be no-op
        let intervals: Vec<_> = set.iter().collect();
        assert_eq!(intervals, vec![0..15, 15..30]);
    }

    #[test]
    fn test_split_at_multiple_intervals() {
        let mut set = IntervalSet::new();
        set.insert(0..20);
        set.insert(30..50);
        // Split point only affects first interval
        set.split_at(10);
        let intervals: Vec<_> = set.iter().collect();
        assert_eq!(intervals, vec![0..10, 10..20, 30..50]);
    }

    #[test]
    fn test_split_at_in_gap() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);
        // Split point in gap - should be no-op
        set.split_at(15);
        let intervals: Vec<_> = set.iter().collect();
        assert_eq!(intervals, vec![0..10, 20..30]);
    }

    #[test]
    fn test_split_preserves_coverage() {
        let mut set = IntervalSet::new();
        set.insert(0..100);
        // Coverage before split
        assert!(set.covers(0..100));
        set.split_at(25);
        set.split_at(50);
        set.split_at(75);
        // Coverage should be preserved after splits
        assert!(set.covers(0..100));
        assert!(set.contains(0));
        assert!(set.contains(25));
        assert!(set.contains(50));
        assert!(set.contains(75));
        assert!(set.contains(99));
    }

    // --- Method interactions ---

    #[test]
    fn test_gaps_after_retain() {
        let mut set = IntervalSet::new();
        set.insert(0..10);
        set.insert(20..30);
        set.insert(40..50);
        set.retain(|r| r.start != 20); // Remove middle interval
        let gaps: Vec<_> = set.gaps().collect();
        assert_eq!(gaps, vec![10..40]); // One big gap now
    }

    #[test]
    fn test_overlaps_after_split() {
        let mut set = IntervalSet::new();
        set.insert(0..100);
        set.split_at(50);
        // Should still overlap the same ranges
        assert!(set.overlaps(25..75));
        assert!(set.overlaps(0..1));
        assert!(set.overlaps(99..100));
    }

    #[test]
    fn test_iter_overlapping_after_split() {
        let mut set = IntervalSet::new();
        set.insert(0..100);
        set.split_at(50);
        // Query should return both split parts
        let overlapping: Vec<_> = set.iter_overlapping(25..75).collect();
        assert_eq!(overlapping, vec![0..50, 50..100]);
    }

    // --- Boundary value tests ---

    #[test]
    fn test_utility_methods_near_max() {
        let mut set: IntervalSet<u32> = IntervalSet::new();
        let max = u32::MAX;
        set.insert((max - 100)..(max - 50));
        set.insert((max - 30)..(max - 10));

        assert_eq!(set.first(), Some((max - 100)..(max - 50)));
        assert_eq!(set.last(), Some((max - 30)..(max - 10)));
        assert_eq!(set.span(), Some((max - 100)..(max - 10)));
        assert!(set.overlaps((max - 80)..(max - 60)));
        assert!(!set.covers((max - 100)..(max - 10))); // Gap exists
    }

    #[test]
    fn test_utility_methods_near_min_signed() {
        let mut set: IntervalSet<i32> = IntervalSet::new();
        let min = i32::MIN;
        set.insert(min..(min + 50));
        set.insert((min + 100)..(min + 150));

        assert_eq!(set.first(), Some(min..(min + 50)));
        assert_eq!(set.last(), Some((min + 100)..(min + 150)));
        assert_eq!(set.span(), Some(min..(min + 150)));

        let gaps: Vec<_> = set.gaps().collect();
        assert_eq!(gaps, vec![(min + 50)..(min + 100)]);
    }

    #[test]
    fn test_utility_methods_crossing_zero() {
        let mut set: IntervalSet<i32> = IntervalSet::new();
        set.insert(-50..50);

        assert_eq!(set.span(), Some(-50..50));
        assert!(set.contains(-25));
        assert!(set.contains(0));
        assert!(set.contains(25));
        assert!(set.covers(-25..25));

        set.split_at(0);
        let intervals: Vec<_> = set.iter().collect();
        assert_eq!(intervals, vec![-50..0, 0..50]);
    }
}