intervalmap 0.1.1

use std::{
    collections::BTreeMap,
    ops::{Bound, Range, RangeBounds},
};

use crate::{interval::Interval, IndexType};

/// A map from non-overlapping intervals to values.
///
/// `IntervalMap` stores a collection of non-overlapping intervals, each associated
/// with a value. When inserting a new interval, any existing intervals that overlap
/// are split or removed as needed. Adjacent intervals with the same value are
/// automatically merged.
///
/// # Type Parameters
///
/// * `Ix` - The index type for interval bounds. Defaults to `u32`.
/// * `V` - The value type associated with each interval.
///
/// # Examples
///
/// ```
/// use intervalmap::IntervalMap;
///
/// let mut map: IntervalMap<u32, &str> = IntervalMap::new();
/// map.insert(0..10, "first");
/// map.insert(20..30, "second");
///
/// assert_eq!(map.get(5), Some(&"first"));
/// assert_eq!(map.get(15), None);
/// assert_eq!(map.get(25), Some(&"second"));
/// ```
#[derive(Debug, Clone)]
pub struct IntervalMap<Ix = u32, V = ()> {
    /// Internal storage: maps interval start -> (end, value)
    /// Invariant: intervals never overlap
    map: BTreeMap<Ix, (Ix, V)>,
}

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

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

    /// Returns the number of intervals in the map.
    ///
    /// Note: This is the count of stored intervals, not the total span covered.
    #[inline]
    pub fn len(&self) -> usize {
        self.map.len()
    }

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

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

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

    /// Returns a reference to the value at the given point, if any.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalMap;
    ///
    /// let mut map = IntervalMap::new();
    /// map.insert(0..10, "hello");
    ///
    /// assert_eq!(map.get(5), Some(&"hello"));
    /// assert_eq!(map.get(10), None);
    /// ```
    pub fn get(&self, point: Ix) -> Option<&V> {
        // Find the interval that might contain this point
        // We need the largest start <= point
        self.map
            .range(..=point)
            .next_back()
            .filter(|(&start, &(end, _))| {
                let interval = Interval::new(start, end);
                interval.contains_point(point)
            })
            .map(|(_, (_, v))| v)
    }

    /// Returns a mutable reference to the value at the given point, if any.
    pub fn get_mut(&mut self, point: Ix) -> Option<&mut V> {
        // Find the interval that might contain this point
        let start = self
            .map
            .range(..=point)
            .next_back()
            .filter(|(&start, &(end, _))| {
                let interval = Interval::new(start, end);
                interval.contains_point(point)
            })
            .map(|(&start, _)| start)?;

        self.map.get_mut(&start).map(|(_, v)| v)
    }

    /// Returns the interval and value at the given point, if any.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalMap;
    ///
    /// let mut map = IntervalMap::new();
    /// map.insert(0..10, "value");
    ///
    /// let (range, value) = map.get_interval(5).unwrap();
    /// assert_eq!(range, 0..10);
    /// assert_eq!(*value, "value");
    /// ```
    pub fn get_interval(&self, point: Ix) -> Option<(Range<Ix>, &V)> {
        self.map
            .range(..=point)
            .next_back()
            .filter(|(&start, &(end, _))| {
                let interval = Interval::new(start, end);
                interval.contains_point(point)
            })
            .map(|(&start, (end, v))| (start..*end, v))
    }

    /// Returns an iterator over all intervals and their values.
    ///
    /// Intervals are yielded in ascending order by start position.
    pub fn iter(&self) -> Iter<'_, Ix, V> {
        Iter {
            inner: self.map.iter(),
        }
    }

    /// Returns the first (lowest) interval and its value, or `None` if empty.
    ///
    /// This is an O(log n) operation.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalMap;
    ///
    /// let mut map = IntervalMap::new();
    /// assert_eq!(map.first(), None);
    ///
    /// map.insert(10..20, "a");
    /// map.insert(0..5, "b");
    /// assert_eq!(map.first(), Some((0..5, &"b")));
    /// ```
    pub fn first(&self) -> Option<(Range<Ix>, &V)> {
        self.map
            .iter()
            .next()
            .map(|(&start, (end, v))| (start..*end, v))
    }

    /// Returns the last (highest) interval and its value, or `None` if empty.
    ///
    /// This is an O(log n) operation.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalMap;
    ///
    /// let mut map = IntervalMap::new();
    /// assert_eq!(map.last(), None);
    ///
    /// map.insert(0..5, "a");
    /// map.insert(10..20, "b");
    /// assert_eq!(map.last(), Some((10..20, &"b")));
    /// ```
    pub fn last(&self) -> Option<(Range<Ix>, &V)> {
        self.map
            .iter()
            .next_back()
            .map(|(&start, (end, v))| (start..*end, v))
    }

    /// 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::IntervalMap;
    ///
    /// let mut map = IntervalMap::new();
    /// assert_eq!(map.span(), None);
    ///
    /// map.insert(5..10, "a");
    /// map.insert(20..30, "b");
    /// assert_eq!(map.span(), Some(5..30));
    /// ```
    pub fn span(&self) -> Option<Range<Ix>> {
        let (first_range, _) = self.first()?;
        let (last_range, _) = self.last()?;
        Some(first_range.start..last_range.end)
    }

    /// Removes the interval with the given start key.
    ///
    /// This is a low-level method primarily for internal use.
    pub(crate) fn remove_by_start(&mut self, start: Ix) {
        self.map.remove(&start);
    }

    /// Splits the interval containing the given point into two intervals.
    ///
    /// If no interval contains the point, or if the point is at the start
    /// or end of an interval, nothing happens.
    pub(crate) fn split_at(&mut self, point: Ix)
    where
        V: Clone,
    {
        // Find the interval containing this point
        if let Some((&start, &(end, ref value))) = self
            .map
            .range(..=point)
            .next_back()
            .filter(|(&start, &(end, _))| start < point && point < end)
        {
            let value = value.clone();
            // Remove the original interval
            self.map.remove(&start);
            // Insert the two new intervals
            self.map.insert(start, (point, value.clone()));
            self.map.insert(point, (end, value));
        }
    }

    /// Converts a `RangeBounds` to an `Interval`, using appropriate bounds.
    fn range_to_interval<R: RangeBounds<Ix>>(&self, range: R) -> Interval<Ix>
    where
        Ix: num_traits::One + num_traits::Bounded,
    {
        let start = match range.start_bound() {
            Bound::Included(&s) => s,
            Bound::Excluded(&s) => s + Ix::one(),
            Bound::Unbounded => Ix::min_value(),
        };

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

        Interval::new(start, end)
    }
}

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

        // Check interval that might start before and extend into our range
        if let Some((_, &(end, _))) = self.map.range(..interval.start).next_back() {
            if end > interval.start {
                return true;
            }
        }

        // Check if any interval starts within our range
        self.map
            .range(interval.start..interval.end)
            .next()
            .is_some()
    }

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

        // Find the first interval that could cover the start of our range
        let mut covered_until = interval.start;

        // Check interval that might start before and extend into our range
        if let Some((_, &(end, _))) = self.map.range(..=interval.start).next_back() {
            if end > interval.start {
                covered_until = end;
            }
        }

        // If we haven't found coverage starting at interval.start, return false
        if covered_until <= interval.start {
            // Need to check if there's an interval starting exactly at interval.start
            if let Some(&(end, _)) = self.map.get(&interval.start) {
                covered_until = end;
            }
            else {
                return false;
            }
        }

        // Now check that subsequent intervals form contiguous coverage
        for (&start, &(end, _)) in self.map.range(interval.start..interval.end) {
            if start > covered_until {
                // Gap in coverage
                return false;
            }
            if end > covered_until {
                covered_until = end;
            }
        }

        // Check if we've covered all the way to the end
        covered_until >= interval.end
    }
}

impl<Ix: IndexType + num_traits::One + num_traits::Bounded, V: Clone + PartialEq>
    IntervalMap<Ix, V>
{
    /// Inserts an interval with the given value.
    ///
    /// If the new interval overlaps with existing intervals:
    /// - Existing intervals are split at the boundaries of the new interval
    /// - The overlapping portions take the new value
    /// - Adjacent intervals with the same value are merged
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalMap;
    ///
    /// let mut map = IntervalMap::new();
    /// map.insert(0..10, "a");
    /// map.insert(5..15, "b");
    ///
    /// // Result: [0,5) -> "a", [5,15) -> "b"
    /// assert_eq!(map.get(3), Some(&"a"));
    /// assert_eq!(map.get(7), Some(&"b"));
    /// ```
    pub fn insert<R: RangeBounds<Ix>>(&mut self, range: R, value: V) {
        let interval = self.range_to_interval(range);
        if interval.is_empty() {
            return;
        }

        self.insert_internal(interval, value);
    }

    /// Internal insert implementation.
    fn insert_internal(&mut self, interval: Interval<Ix>, value: V) {
        // Collect all intervals that overlap with or touch the new interval
        let overlapping = self.find_overlapping_or_touching(interval);

        // Remove overlapping intervals and collect fragments
        let mut fragments: Vec<(Interval<Ix>, V)> = Vec::new();

        for (start, _) in overlapping {
            if let Some((old_end, old_value)) = self.map.remove(&start) {
                let old_interval = Interval::new(start, old_end);

                // Left fragment: portion before new interval
                if old_interval.start < interval.start {
                    fragments.push((
                        Interval::new(old_interval.start, interval.start),
                        old_value.clone(),
                    ));
                }

                // Right fragment: portion after new interval
                if old_interval.end > interval.end {
                    fragments.push((Interval::new(interval.end, old_interval.end), old_value));
                }
            }
        }

        // Insert the new interval
        self.map
            .insert(interval.start, (interval.end, value.clone()));

        // Re-insert fragments
        for (frag_interval, frag_value) in fragments {
            self.map
                .insert(frag_interval.start, (frag_interval.end, frag_value));
        }

        // Merge with neighbors if they have the same value
        self.merge_neighbors(interval.start, &value);
    }

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

        self.remove_internal(interval);
    }

    /// Internal remove implementation.
    fn remove_internal(&mut self, interval: Interval<Ix>) {
        // Find all overlapping intervals
        let overlapping = self.find_overlapping(interval);

        // Remove and re-insert non-overlapping portions
        for (start, _) in overlapping {
            if let Some((old_end, old_value)) = self.map.remove(&start) {
                let old_interval = Interval::new(start, old_end);

                // Re-insert left portion
                if old_interval.start < interval.start {
                    self.map
                        .insert(old_interval.start, (interval.start, old_value.clone()));
                }

                // Re-insert right portion
                if old_interval.end > interval.end {
                    self.map.insert(interval.end, (old_interval.end, old_value));
                }
            }
        }
    }

    /// Finds all intervals that overlap with the given interval.
    fn find_overlapping(&self, interval: Interval<Ix>) -> Vec<(Ix, Ix)> {
        let mut result = Vec::new();

        // Check interval that might start before and extend into our range
        if let Some((&start, &(end, _))) = self.map.range(..interval.start).next_back() {
            if end > interval.start {
                result.push((start, end));
            }
        }

        // Check all intervals starting within our range
        for (&start, &(end, _)) in self.map.range(interval.start..interval.end) {
            result.push((start, end));
        }

        result
    }

    /// Finds all intervals that overlap with or touch the given interval.
    fn find_overlapping_or_touching(&self, interval: Interval<Ix>) -> Vec<(Ix, Ix)> {
        let mut result = Vec::new();

        // Check interval that might start before and extend into/touch our range
        if let Some((&start, &(end, _))) = self.map.range(..interval.start).next_back() {
            if end >= interval.start {
                result.push((start, end));
            }
        }

        // Check all intervals starting within or at the end of our range
        for (&start, &(end, _)) in self.map.range(interval.start..=interval.end) {
            result.push((start, end));
        }

        result
    }

    /// Merges adjacent intervals with the same value.
    fn merge_neighbors(&mut self, start: Ix, value: &V) {
        // Get current interval
        let Some(&(end, _)) = self.map.get(&start)
        else {
            return;
        };

        // Try to merge with the interval immediately after
        if let Some(&(next_end, ref next_value)) = self.map.get(&end) {
            if next_value == value {
                self.map.remove(&end);
                self.map.insert(start, (next_end, value.clone()));
                // Update end for potential further merging
                self.merge_neighbors(start, value);
                return;
            }
        }

        // Try to merge with the interval immediately before
        if let Some((&prev_start, &(prev_end, ref prev_value))) =
            self.map.range(..start).next_back()
        {
            if prev_end == start && prev_value == value {
                let current_end = self.map.get(&start).map(|(e, _)| *e).unwrap_or(end);
                self.map.remove(&start);
                self.map.insert(prev_start, (current_end, value.clone()));
            }
        }
    }
}

/// An iterator over the intervals and values in an `IntervalMap`.
pub struct Iter<'a, Ix, V> {
    inner: std::collections::btree_map::Iter<'a, Ix, (Ix, V)>,
}

impl<'a, Ix: IndexType, V> Iterator for Iter<'a, Ix, V> {
    type Item = (Range<Ix>, &'a V);

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|(&start, (end, v))| (start..*end, v))
    }

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

impl<'a, Ix: IndexType, V> ExactSizeIterator for Iter<'a, Ix, V> {}

impl<'a, Ix: IndexType, V> DoubleEndedIterator for Iter<'a, Ix, V> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner
            .next_back()
            .map(|(&start, (end, v))| (start..*end, v))
    }
}

impl<'a, Ix: IndexType, V> IntoIterator for &'a IntervalMap<Ix, V> {
    type Item = (Range<Ix>, &'a V);
    type IntoIter = Iter<'a, Ix, V>;

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

/// An owning iterator over the intervals and values in an `IntervalMap`.
pub struct IntoIter<Ix, V> {
    inner: std::collections::btree_map::IntoIter<Ix, (Ix, V)>,
}

impl<Ix: IndexType, V> Iterator for IntoIter<Ix, V> {
    type Item = (Range<Ix>, V);

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

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

impl<Ix: IndexType, V> ExactSizeIterator for IntoIter<Ix, V> {}

impl<Ix: IndexType, V> IntoIterator for IntervalMap<Ix, V> {
    type Item = (Range<Ix>, V);
    type IntoIter = IntoIter<Ix, V>;

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

// ============================================================================
// Entry API
// ============================================================================

/// A view into a single entry in an `IntervalMap`, which may either be vacant or occupied.
///
/// This enum is constructed from the [`entry`] method on [`IntervalMap`].
///
/// [`entry`]: IntervalMap::entry
pub enum Entry<'a, Ix: IndexType, V> {
    /// A vacant entry - no interval contains this point.
    Vacant(VacantEntry<'a, Ix, V>),
    /// An occupied entry - an interval contains this point.
    Occupied(OccupiedEntry<'a, Ix, V>),
}

/// A view into a vacant entry in an `IntervalMap`.
pub struct VacantEntry<'a, Ix: IndexType, V> {
    map: &'a mut IntervalMap<Ix, V>,
    point: Ix,
}

/// A view into an occupied entry in an `IntervalMap`.
pub struct OccupiedEntry<'a, Ix: IndexType, V> {
    map: &'a mut IntervalMap<Ix, V>,
    /// The start of the interval containing the point
    interval_start: Ix,
}

impl<Ix: IndexType + num_traits::One + num_traits::Bounded, V: Clone + PartialEq>
    IntervalMap<Ix, V>
{
    /// Gets the given point's corresponding entry in the map for in-place manipulation.
    ///
    /// # Examples
    ///
    /// ```
    /// use intervalmap::IntervalMap;
    /// use intervalmap::interval_map::Entry;
    ///
    /// let mut map: IntervalMap<u32, i32> = IntervalMap::new();
    ///
    /// // Insert a default value if the point is not covered
    /// match map.entry(5) {
    ///     Entry::Vacant(e) => { e.insert(4..8, 100); }
    ///     Entry::Occupied(_) => {}
    /// }
    ///
    /// assert_eq!(map.get(5), Some(&100));
    /// ```
    pub fn entry(&mut self, point: Ix) -> Entry<'_, Ix, V> {
        // Find if there's an interval containing this point
        let interval_start = self
            .map
            .range(..=point)
            .next_back()
            .filter(|(&start, &(end, _))| {
                let interval = Interval::new(start, end);
                interval.contains_point(point)
            })
            .map(|(&start, _)| start);

        match interval_start {
            Some(start) => Entry::Occupied(OccupiedEntry {
                map: self,
                interval_start: start,
            }),
            None => Entry::Vacant(VacantEntry { map: self, point }),
        }
    }
}

impl<'a, Ix: IndexType + num_traits::One + num_traits::Bounded, V: Clone + PartialEq>
    Entry<'a, Ix, V>
{
    /// Returns a reference to the value if occupied.
    pub fn get(&self) -> Option<&V> {
        match self {
            Entry::Occupied(e) => Some(e.get()),
            Entry::Vacant(_) => None,
        }
    }

    /// Ensures a value is in the entry by inserting the default if empty.
    ///
    /// The provided range must contain the queried point.
    pub fn or_insert<R: RangeBounds<Ix>>(self, range: R, default: V) -> &'a mut V {
        match self {
            Entry::Occupied(e) => e.into_mut(),
            Entry::Vacant(e) => e.insert(range, default),
        }
    }

    /// Ensures a value is in the entry by inserting the result of the function if empty.
    pub fn or_insert_with<R: RangeBounds<Ix>, F: FnOnce() -> V>(
        self,
        range: R,
        default: F,
    ) -> &'a mut V {
        match self {
            Entry::Occupied(e) => e.into_mut(),
            Entry::Vacant(e) => e.insert(range, default()),
        }
    }
}

impl<'a, Ix: IndexType, V> OccupiedEntry<'a, Ix, V> {
    /// Gets a reference to the value in the entry.
    pub fn get(&self) -> &V {
        &self.map.map.get(&self.interval_start).unwrap().1
    }

    /// Gets a mutable reference to the value in the entry.
    pub fn get_mut(&mut self) -> &mut V {
        &mut self.map.map.get_mut(&self.interval_start).unwrap().1
    }

    /// Converts the entry into a mutable reference to the value.
    pub fn into_mut(self) -> &'a mut V {
        &mut self.map.map.get_mut(&self.interval_start).unwrap().1
    }

    /// Returns the interval containing the queried point.
    pub fn interval(&self) -> Range<Ix> {
        let (end, _) = self.map.map.get(&self.interval_start).unwrap();
        self.interval_start..*end
    }
}

impl<'a, Ix: IndexType + num_traits::One + num_traits::Bounded, V: Clone + PartialEq>
    VacantEntry<'a, Ix, V>
{
    /// The point that was queried.
    pub fn point(&self) -> Ix {
        self.point
    }

    /// Inserts a value for the given range, returning a mutable reference.
    ///
    /// # Panics
    ///
    /// Panics if the range does not contain the queried point.
    pub fn insert<R: RangeBounds<Ix>>(self, range: R, value: V) -> &'a mut V {
        let interval = self.map.range_to_interval(range);
        assert!(
            interval.contains_point(self.point),
            "inserted range must contain the queried point"
        );
        self.map.insert_internal(interval, value);
        self.map.get_mut(self.point).unwrap()
    }
}

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

    #[test]
    fn test_new_map_is_empty() {
        let map: IntervalMap<u32, i32> = IntervalMap::new();
        assert!(map.is_empty());
        assert_eq!(map.len(), 0);
    }

    #[test]
    fn test_insert_single_interval() {
        let mut map = IntervalMap::new();
        map.insert(0..10, "value");

        assert_eq!(map.len(), 1);
        assert_eq!(map.get(0), Some(&"value"));
        assert_eq!(map.get(5), Some(&"value"));
        assert_eq!(map.get(9), Some(&"value"));
        assert_eq!(map.get(10), None);
    }

    #[test]
    fn test_insert_non_overlapping() {
        let mut map = IntervalMap::new();
        map.insert(0..10, "a");
        map.insert(20..30, "b");

        assert_eq!(map.len(), 2);
        assert_eq!(map.get(5), Some(&"a"));
        assert_eq!(map.get(15), None);
        assert_eq!(map.get(25), Some(&"b"));
    }

    #[test]
    fn test_insert_overlapping_splits() {
        let mut map = IntervalMap::new();
        map.insert(0..10, "a");
        map.insert(5..15, "b");

        // Should result in [0,5) -> "a", [5,15) -> "b"
        assert_eq!(map.len(), 2);
        assert_eq!(map.get(3), Some(&"a"));
        assert_eq!(map.get(5), Some(&"b"));
        assert_eq!(map.get(12), Some(&"b"));
    }

    #[test]
    fn test_insert_completely_overlapping() {
        let mut map = IntervalMap::new();
        map.insert(0..20, "a");
        map.insert(5..15, "b");

        // Should result in [0,5) -> "a", [5,15) -> "b", [15,20) -> "a"
        assert_eq!(map.len(), 3);
        assert_eq!(map.get(3), Some(&"a"));
        assert_eq!(map.get(10), Some(&"b"));
        assert_eq!(map.get(17), Some(&"a"));
    }

    #[test]
    fn test_insert_merges_same_value() {
        let mut map = IntervalMap::new();
        map.insert(0..10, "a");
        map.insert(10..20, "a");

        // Should merge into [0,20) -> "a"
        assert_eq!(map.len(), 1);
        assert_eq!(map.get(5), Some(&"a"));
        assert_eq!(map.get(15), Some(&"a"));
    }

    #[test]
    fn test_remove_middle() {
        let mut map = IntervalMap::new();
        map.insert(0..20, "value");
        map.remove(5..15);

        // Should result in [0,5) -> "value", [15,20) -> "value"
        assert_eq!(map.len(), 2);
        assert!(map.contains(3));
        assert!(!map.contains(10));
        assert!(map.contains(17));
    }

    #[test]
    fn test_remove_entire() {
        let mut map = IntervalMap::new();
        map.insert(5..15, "value");
        map.remove(0..20);

        assert!(map.is_empty());
    }

    #[test]
    fn test_get_interval() {
        let mut map = IntervalMap::new();
        map.insert(5..15, "value");

        let (range, value) = map.get_interval(10).unwrap();
        assert_eq!(range, 5..15);
        assert_eq!(*value, "value");

        assert!(map.get_interval(20).is_none());
    }

    #[test]
    fn test_clear() {
        let mut map = IntervalMap::new();
        map.insert(0..10, "a");
        map.insert(20..30, "b");

        map.clear();
        assert!(map.is_empty());
    }

    #[test]
    fn test_iter() {
        let mut map = IntervalMap::new();
        map.insert(0..10, "a");
        map.insert(20..30, "b");

        let entries: Vec<_> = map.iter().collect();
        assert_eq!(entries.len(), 2);
        assert_eq!(entries[0], (0..10, &"a"));
        assert_eq!(entries[1], (20..30, &"b"));
    }

    #[test]
    fn test_entry_vacant() {
        let mut map: IntervalMap<u32, i32> = IntervalMap::new();

        match map.entry(5) {
            Entry::Vacant(e) => {
                e.insert(0..10, 42);
            }
            Entry::Occupied(_) => panic!("expected vacant"),
        }

        assert_eq!(map.get(5), Some(&42));
    }

    #[test]
    fn test_entry_occupied() {
        let mut map = IntervalMap::new();
        map.insert(0..10, 42);

        match map.entry(5) {
            Entry::Vacant(_) => panic!("expected occupied"),
            Entry::Occupied(mut e) => {
                assert_eq!(*e.get(), 42);
                *e.get_mut() = 100;
            }
        }

        assert_eq!(map.get(5), Some(&100));
    }

    #[test]
    fn test_entry_or_insert() {
        let mut map: IntervalMap<u32, i32> = IntervalMap::new();

        let val = map.entry(5).or_insert(0..10, 42);
        assert_eq!(*val, 42);

        let val = map.entry(5).or_insert(0..10, 100);
        assert_eq!(*val, 42); // unchanged
    }
}