range_set_blaze/

map.rs

use crate::{
    CheckSortedDisjoint, Integer, IntoKeys, Keys, RangeSetBlaze, SortedDisjoint,
    iter_map::{IntoIterMap, IterMap},
    map_op, map_unary_op,
    range_values::{IntoRangeValuesIter, MapIntoRangesIter, MapRangesIter, RangeValuesIter},
    set::extract_range,
    sorted_disjoint_map::{IntoString, SortedDisjointMap},
    sym_diff_iter_map::SymDiffIterMap,
    unsorted_priority_map::{SortedDisjointMapWithLenSoFar, UnsortedPriorityMap},
    values::{IntoValues, Values},
};
#[cfg(feature = "cursor_nightly_experimental")]
use alloc::collections::btree_map::CursorMut;
#[cfg(feature = "std")]
use alloc::sync::Arc;
#[cfg(any(
    test,
    feature = "test_util",
    not(feature = "cursor_nightly_experimental")
))]
use alloc::vec::Vec;
use alloc::{collections::BTreeMap, rc::Rc};
#[cfg(feature = "cursor_nightly_experimental")]
use core::ops::Bound;
use core::{
    cmp::{Ordering, max},
    convert::From,
    fmt, mem,
    ops::{BitOr, BitOrAssign, Index, RangeBounds, RangeInclusive},
    panic,
};
use num_traits::{One, Zero};

const STREAM_OVERHEAD: usize = 10;

/// A cheap-to-clone representation that carries a logical `Eq + Clone` value for use by
/// [`SortedDisjointMap`].
///
/// `ValueCarrier` enables [`SortedDisjointMap`] to map sorted, disjoint ranges of integers
/// to values of type `V: Eq + Clone`. It supports plain references (`&V`), shared ownership types
/// (`Rc<V>` and `Arc<V>`), compound carriers such as `Option<&V>`, and the by-value `bool`
/// carrier, avoiding unnecessary cloning of values while enabling ownership when needed.
///
/// All types implementing `ValueCarrier` must also implement `Clone`. For standard carriers like
/// `&V`, `Rc<V>`, `Arc<V>`, their `Option` forms, and `bool`, this is efficient—cloning
/// typically just copies a pointer and a discriminant or a small value.
///
/// # Motivation
///
/// Iterating over `(range, value)` pairs—such as with [`RangeMapBlaze::range_values`]—benefits
/// from using cheap-to-clone representations. Other APIs, like
/// [`RangeMapBlaze::into_range_values`], require owned values. `ValueCarrier` bridges this gap by
/// abstracting over carriers that can later be materialized into values you can store or return
/// independently of the original container.
///
/// This also enables shared ownership via `Rc` and `Arc`, reducing allocation and allowing values to be
/// freed when the reference count drops to zero.
///
/// # Examples
///
/// The following demonstrates the [`SortedDisjointMap::intersection`] operation working with
/// iterators of both `(RangeInclusive<Integer>, &Eq + Clone)` and `(RangeInclusive<Integer>, Rc<Eq + Clone>)`.
/// (However, types cannot be mixed in the same operation due to Rust's strong type system.)
///
/// ```rust
/// use range_set_blaze::prelude::*;
/// use std::rc::Rc;
///
/// let a = RangeMapBlaze::from_iter([(3..=10, "a".to_string())]);
/// let b = RangeMapBlaze::from_iter([(2..=3, "b".to_string()), (5..=100, "b".to_string())]);
///
/// let mut c = a.range_values() & b.range_values();
/// assert_eq!(c.next(), Some((3..=3, &"b".to_string())));
/// assert_eq!(c.next(), Some((5..=10, &"b".to_string())));
/// assert_eq!(c.next(), None);
///
/// let mut c = a.into_range_values() & b.into_range_values();
/// assert_eq!(c.next(), Some((3..=3, Rc::new("b".to_string()))));
/// assert_eq!(c.next(), Some((5..=10, Rc::new("b".to_string()))));
/// assert_eq!(c.next(), None);
/// ```
pub trait ValueCarrier: Clone {
    /// The logical `Eq + Clone` value represented by this carrier.
    type Value: Eq + Clone;

    /// Compares the logical values represented by two value carriers.
    ///
    /// This deliberately avoids requiring `Borrow<Self::Value>`: compound
    /// representations such as `Option<&V>` cannot borrow an `Option<V>`
    /// without first materializing one, but can still compare their logical
    /// values cheaply. Implementations must define an equivalence relation and
    /// agree with comparing the results of [`ValueCarrier::into_value`].
    fn value_eq(&self, other: &Self) -> bool;

    /// Materializes a `Self::Value` (`V`) value from this carrier.
    ///
    /// The returned `V` may or may not be a uniquely owned allocation. If `V` itself is a
    /// reference type (e.g., `&'static str`), the result is still a reference; in that case
    /// this operation is just a cheap pointer copy. In other words, “owned” here means
    /// “a standalone `V` value you can keep,” not necessarily a unique heap allocation.
    ///
    /// Behavior:
    /// - `bool` → returns itself.
    /// - `&V` → calls `Clone::clone` on `V`. If `V` is a reference (e.g., `&'static str`),
    ///   this simply copies the reference without allocation.
    /// - `Rc<V>` / `Arc<V>` → tries to unwrap if uniquely owned; otherwise clones `V`.
    ///
    /// This is typically used when converting a stream of `(range, value)` pairs into values
    /// that can be stored or returned independently of the original container.
    ///
    /// # Examples
    /// ```
    /// use std::rc::Rc;
    /// use range_set_blaze::ValueCarrier;
    ///
    /// // Owning target: cloning duplicates the data
    /// let s = String::from("hi");
    /// let owned_s: String = (&s).into_value(); // clones the String
    ///
    /// // Reference target: no allocation; still a reference
    /// let static_s: &'static str = "hi";
    /// let r: &&'static str = &static_s;
    /// let still_ref: &'static str = r.into_value(); // copies the reference
    ///
    /// // Rc: move out if unique, else clone
    /// let rc = Rc::new(String::from("hello"));
    /// let moved_or_cloned: String = rc.into_value();
    /// ```
    fn into_value(self) -> Self::Value;
}

// Implementations for built-in value carriers
impl ValueCarrier for bool {
    type Value = Self;

    #[inline]
    fn value_eq(&self, other: &Self) -> bool {
        self == other
    }

    #[inline]
    fn into_value(self) -> Self::Value {
        self
    }
}

impl<V> ValueCarrier for &V
where
    V: Eq + Clone,
{
    type Value = V;

    #[inline]
    fn value_eq(&self, other: &Self) -> bool {
        **self == **other
    }

    #[inline]
    fn into_value(self) -> Self::Value {
        self.clone()
    }
}

impl<V> ValueCarrier for Rc<V>
where
    V: Eq + Clone,
{
    type Value = V;

    #[inline]
    fn value_eq(&self, other: &Self) -> bool {
        self.as_ref() == other.as_ref()
    }

    #[inline]
    fn into_value(self) -> Self::Value {
        Self::try_unwrap(self).unwrap_or_else(|rc| (*rc).clone())
    }
}

#[cfg(feature = "std")]
impl<V> ValueCarrier for Arc<V>
where
    V: Eq + Clone,
{
    type Value = V;

    #[inline]
    fn value_eq(&self, other: &Self) -> bool {
        self.as_ref() == other.as_ref()
    }

    #[inline]
    fn into_value(self) -> Self::Value {
        Self::try_unwrap(self).unwrap_or_else(|arc| (*arc).clone())
    }
}

impl<VC> ValueCarrier for Option<VC>
where
    VC: ValueCarrier,
{
    type Value = Option<VC::Value>;

    #[inline]
    fn value_eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Some(a), Some(b)) => a.value_eq(b),
            (None, None) => true,
            _ => false,
        }
    }

    #[inline]
    fn into_value(self) -> Self::Value {
        self.map(ValueCarrier::into_value)
    }
}

#[expect(clippy::redundant_pub_crate)]
#[derive(Clone, Hash, Default, PartialEq, Eq, Debug)]
pub(crate) struct EndValue<T, V> {
    pub(crate) end: T,
    pub(crate) value: V,
}

#[cfg(feature = "cursor_nightly_experimental")]
enum PredecessorInsertAction<T> {
    Unaffected,
    MergeSameValue,
    KeepLeftResidual { left_end: T, right_start: Option<T> },
}

#[cfg(feature = "cursor_nightly_experimental")]
enum ForwardInsertAction<T> {
    MergeSameValue,
    DeleteOverwritten,
    KeepRightResidual { right_start: T },
}

#[cfg(feature = "cursor_nightly_experimental")]
struct CursorScanResult<T, V> {
    pending_end: T,
    right_residual: Option<(T, EndValue<T, V>)>,
    unchanged: bool,
}

// These classifiers are the proof-relevant algorithm. On a sorted canonical list of
// `(start, end, value)` triples, classify the predecessor once, then repeatedly classify the
// first unprocessed triple. The cursor code below only realizes the resulting remove, retain,
// merge, and residual operations in a B-tree.
#[cfg(feature = "cursor_nightly_experimental")]
fn classify_predecessor<T: Integer>(
    stored_end: T,
    pending_start: T,
    pending_end: T,
    same_value: bool,
) -> PredecessorInsertAction<T> {
    let overlaps = stored_end >= pending_start;
    let touches = stored_end.checked_add_one() == Some(pending_start);
    if !(overlaps || touches && same_value) {
        PredecessorInsertAction::Unaffected
    } else if same_value {
        PredecessorInsertAction::MergeSameValue
    } else {
        let right_start = if stored_end > pending_end {
            Some(pending_end.add_one())
        } else {
            None
        };
        PredecessorInsertAction::KeepLeftResidual {
            left_end: pending_start.sub_one(),
            right_start,
        }
    }
}

#[cfg(feature = "cursor_nightly_experimental")]
fn classify_forward<T: Integer>(
    stored_start: T,
    stored_end: T,
    pending_end: T,
    same_value: bool,
) -> Option<ForwardInsertAction<T>> {
    let overlaps = stored_start <= pending_end;
    let touches = pending_end.checked_add_one() == Some(stored_start);
    if !(overlaps || touches && same_value) {
        None
    } else if same_value {
        Some(ForwardInsertAction::MergeSameValue)
    } else if stored_end > pending_end {
        Some(ForwardInsertAction::KeepRightResidual {
            right_start: pending_end.add_one(),
        })
    } else {
        Some(ForwardInsertAction::DeleteOverwritten)
    }
}

/// A map from integers to values stored as a map of sorted & disjoint ranges to values.
///
/// Internally, the map stores the
/// ranges and values in a cache-efficient [`BTreeMap`].
///
/// For a side-by-side introduction to range lookups and gap filling, see the
/// [Ranges and gaps guide][crate::gaps].
///
/// # Table of Contents
/// * [`RangeMapBlaze` Constructors](#rangemapblaze-constructors)
///    * [Performance](#constructor-performance)
///    * [Examples](struct.RangeMapBlaze.html#constructor-examples)
/// * [`RangeMapBlaze` Set Operations](#rangemapblaze-set-operations)
///    * [Performance](struct.RangeMapBlaze.html#set-operation-performance)
///    * [Examples](struct.RangeMapBlaze.html#set-operation-examples)
/// * [`RangeMapBlaze` Union- and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods)
/// * [`RangeMapBlaze` Comparisons](#rangemapblaze-comparisons)
/// * [Additional Examples](#additional-examples)
///
/// # `RangeMapBlaze` Constructors
///
/// You can create `RangeMapBlaze`'s from unsorted and overlapping integers (or ranges), along with values.
/// However, if you know that your input is sorted and disjoint, you can speed up construction.
///
/// Here are the constructors, followed by a
/// description of the performance, and then some examples.
///
///
/// | Methods                                     | Input                        | Notes                    |
/// |---------------------------------------------|------------------------------|--------------------------|
/// | [`new`]/[`default`]                         |                              |                          |
/// | [`from_iter`][1]/[`collect`][1]           | iterator of `(integer, value)` | References to the pair or value is OK. |
/// | [`from_iter`][2]/[`collect`][2]           | iterator of `(range, value)`   | References to the pair or value is OK. |
/// | [`from_sorted_disjoint_map`][3]/<br>[`into_range_set_blaze`][3b] | [`SortedDisjointMap`] iterator |               |
/// | [`from`][4] /[`into`][4]                    | array of `(integer, value)`  |                          |
///
///
/// [`BTreeMap`]: alloc::collections::BTreeMap
/// [`new`]: RangeMapBlaze::new
/// [`default`]: RangeMapBlaze::default
/// [1]: struct.RangeMapBlaze.html#impl-FromIterator<(T,+V)>-for-RangeMapBlaze<T,+V>
/// [2]: struct.RangeMapBlaze.html#impl-FromIterator<(RangeInclusive<T>,+V)>-for-RangeMapBlaze<T,+V>
/// [3]: `RangeMapBlaze::from_sorted_disjoint_map`
/// [3b]: `SortedDisjointMap::into_range_map_blaze
/// [`SortedDisjointMap`]: crate::SortedDisjointMap.html#table-of-contents
/// [4]: `RangeMapBlaze::from`
///
/// # Constructor Performance
///
/// The [`from_iter`][1]/[`collect`][1] constructors are designed to work fast on 'clumpy' data.
/// By 'clumpy', we mean that the number of ranges needed to represent the data is
/// small compared to the number of input integers. To understand this, consider the internals
/// of the constructors:
///
///  Internally, the `from_iter`/`collect` constructors take these steps:
/// * collect adjacent integers/ranges with equal values into disjoint ranges, O(*n₁*)
/// * sort the disjoint ranges by their `start`, O(*n₂* ln *n₂*)
/// * merge ranges giving precedence to the originally right-most values, O(*n₂*)
/// * create a `BTreeMap` from the now sorted & disjoint ranges, O(*n₃* ln *n₃*)
///
/// where *n₁* is the number of input integers/ranges, *n₂* is the number of disjoint & unsorted ranges,
/// and *n₃* is the final number of sorted & disjoint ranges with equal values.
///
/// For example, an input of
///  * `(3, "a"), (2, "a"), (1, "a"), (4, "a"), (100, "c"), (5, "b"), (4, "b"), (5, "b")`, becomes
///  * `(1..=4, "a"), (100..=100, "c"), (4..=5, "b")`, and then
///  * `(1..=4, "a"), (4..=5, "b"), (100..=100, "c")`, and finally
///  * `(1..=4, "a"), (5..=5, "b"), (100..=100, "c")`.
///
/// What is the effect of clumpy data?
/// Notice that if *n₂* ≈ sqrt(*n₁*), then construction is O(*n₁*).
/// Indeed, as long as *n₂* ≤ *n₁*/ln(*n₁*), then construction is O(*n₁*).
/// Moreover, we'll see that set operations are O(*n₃*). Thus, if *n₃* ≈ sqrt(*n₁*) then set operations are O(sqrt(*n₁*)),
/// a quadratic improvement an O(*n₁*) implementation that ignores the clumps.
///
/// ## Constructor Examples
///
/// ```
/// use range_set_blaze::prelude::*;
///
/// // Create an empty set with 'new' or 'default'.
/// let a0 = RangeMapBlaze::<i32, &str>::new();
/// let a1 = RangeMapBlaze::<i32, &str>::default();
/// assert!(a0 == a1 && a0.is_empty());
///
/// // 'from_iter'/'collect': From an iterator of integers.
/// // Duplicates and out-of-order elements are fine.
/// // Values have right-to-left precedence.
/// let a0 = RangeMapBlaze::from_iter([(100, "b"), (1, "c"),(3, "a"), (2, "a"), (1, "a")]);
/// let a1: RangeMapBlaze<i32, &str> = [(100, "b"), (1, "c"), (3, "a"), (2, "a"), (1, "a")].into_iter().collect();
/// assert!(a0 == a1 && a0.to_string() == r#"(1..=3, "a"), (100..=100, "b")"#);
///
/// // 'from_iter'/'collect': From an iterator of inclusive ranges, start..=end.
/// // Overlapping, out-of-order, and empty ranges are fine.
/// // Values have right-to-left precedence.
/// #[allow(clippy::reversed_empty_ranges)]
/// let a0 = RangeMapBlaze::from_iter([(2..=2, "b"), (1..=2, "a"), (-10..=-5, "c"), (1..=0, "d")]);
/// #[allow(clippy::reversed_empty_ranges)]
/// let a1: RangeMapBlaze<i32, &str> = [(2..=2, "b"), (1..=2, "a"), (-10..=-5, "c"), (1..=0, "d")].into_iter().collect();
/// assert!(a0 == a1 && a0.to_string() == r#"(-10..=-5, "c"), (1..=2, "a")"#);
///
/// // If we know the ranges are already sorted and disjoint,
/// // we can avoid work and use 'from_sorted_disjoint_map'/'into_sorted_disjoint_map'.
/// let a0 = RangeMapBlaze::from_sorted_disjoint_map(CheckSortedDisjointMap::new([(-10..=-5, &"c"), (1..=2, &"a")]));
/// let a1: RangeMapBlaze<i32, &str> = CheckSortedDisjointMap::new([(-10..=-5, &"c"), (1..=2, &"a")]).into_range_map_blaze();
/// assert_eq!(a0, a1);
/// assert_eq!(a0.to_string(),r#"(-10..=-5, "c"), (1..=2, "a")"#);
///
/// // For compatibility with `BTreeMap`, we also support
/// // 'from'/'into' from arrays of integers.
/// let a0 = RangeMapBlaze::from([(100, "b"), (1, "c"),(3, "a"), (2, "a"), (1, "a")]);
/// let a1: RangeMapBlaze<i32, &str> = [(100, "b"), (1, "c"),(3, "a"), (2, "a"), (1, "a")].into();
/// assert_eq!(a0, a1);
/// assert_eq!(a0.to_string(), r#"(1..=3, "a"), (100..=100, "b")"#);
/// ```
///
/// # `RangeMapBlaze` Set Operations
///
/// You can perform set operations on `RangeMapBlaze`s
/// and `RangeSetBlaze`s using operators. In the table below, `a`, `b`, and `c` are `RangeMapBlaze`s and `s` is a `RangeSetBlaze`.
///
/// | Set Operation           | Operator                           | Multiway Method                        |
/// |--------------------------|------------------------------------|----------------------------------------|
/// | union                    | [`a` &#124; `b`]                   | `[a, b, c]`.[`union`]\(\)              |
/// | intersection             | [`a & b`]                          | `[a, b, c]`.[`intersection`]\(\)              |
/// | intersection             | [`a & s`]                          | *n/a*                                  |
/// | difference               | [`a - b`]                          | *n/a*                                  |
/// | difference               | [`a - s`]                          | *n/a*                                  |
/// | symmetric difference     | [`a ^ b`]                          | `[a, b, c]`.[`symmetric_difference`]\(\) |
/// | complement (to set)      | [`!a`]                             | *n/a*                                  |
/// | complement (to map)      | [`a.complement_with(&value)`]      | *n/a*                                  |
///
/// The result of all operations is a new `RangeMapBlaze` except for `!a`, which returns a `RangeSetBlaze`.
///
/// The union of any number of maps is defined such that, for any overlapping keys,
/// the values from the right-most input take precedence. This approach ensures
/// that the data from the right-most inputs remains dominant when merging with
/// later inputs. Likewise, for symmetric difference of three or more maps.
///
/// `RangeMapBlaze` also implements many other methods, such as [`insert`], [`pop_first`] and [`split_off`]. Many of
/// these methods match those of `BTreeMap`.
///
/// [`a` &#124; `b`]: struct.RangeMapBlaze.html#impl-BitOr-for-RangeMapBlaze<T,+V>
/// [`a & b`]: struct.RangeMapBlaze.html#impl-BitAnd-for-RangeMapBlaze<T,+V>
/// [`a & s`]: struct.RangeMapBlaze.html#impl-BitAnd<%26RangeSetBlaze<T>>-for-%26RangeMapBlaze<T,+V>
/// [`a - b`]: struct.RangeMapBlaze.html#impl-Sub-for-RangeMapBlaze<T,+V>
/// [`a - s`]: struct.RangeMapBlaze.html#impl-Sub<%26RangeSetBlaze<T>>-for-%26RangeMapBlaze<T,+V>
/// [`a ^ b`]: struct.RangeMapBlaze.html#impl-BitXor-for-RangeMapBlaze<T,+V>
/// [`!a`]: struct.RangeMapBlaze.html#impl-Not-for-%26RangeMapBlaze<T,+V>
/// [`a.complement_with(&value)`]: struct.RangeMapBlaze.html#method.complement_with
/// [`union`]: trait.MultiwayRangeMapBlazeRef.html#method.union
/// [`intersection`]: trait.MultiwayRangeMapBlazeRef.html#method.intersection
/// [`symmetric_difference`]: trait.MultiwayRangeMapBlazeRef.html#method.symmetric_difference
/// [`insert`]: RangeMapBlaze::insert
/// [`pop_first`]: RangeMapBlaze::pop_first
/// [`split_off`]: RangeMapBlaze::split_off
///
/// ## Set Operation Performance
///
/// Every operation is implemented as
/// 1. a single pass over the sorted & disjoint ranges
/// 2. the construction of a new `RangeMapBlaze`
///
/// Thus, applying multiple operators creates intermediate
/// `RangeMapBlaze`'s. If you wish, you can avoid these intermediate
/// `RangeMapBlaze`'s by switching to the [`SortedDisjointMap`] API. The last example below
/// demonstrates this.
///
/// Several union-related operators — such as [`|`] (union) and [`|=`] (union append) — include performance
/// optimizations for common cases, including when one operand is much smaller than the other.
/// These optimizations reduce allocations and merging overhead.
/// **See:** [Summary of Union and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods).
///
/// [`SortedDisjointMap`]: crate::SortedDisjointMap.html#table-of-contents
/// [`|`]: struct.RangeMapBlaze.html#impl-BitOr-for-RangeMapBlaze%3CT,+V%3E
/// [`|=`]: struct.RangeMapBlaze.html#impl-BitOrAssign-for-RangeMapBlaze%3CT,+V%3E
///
/// ## Set Operation Examples
///
/// ```
/// use range_set_blaze::prelude::*;
///
/// let a = RangeMapBlaze::from_iter([(2..=6, "a")]);
/// let b = RangeMapBlaze::from_iter([(1..=2, "b"), (5..=100, "b")]);
///
/// // Union of two 'RangeMapBlaze's. Alternatively, we can take ownership via 'a | b'.
/// // Values have right-to-left precedence.
/// let result = &a | &b;
/// assert_eq!(result.to_string(), r#"(1..=2, "b"), (3..=4, "a"), (5..=100, "b")"#);
///
/// // Intersection of two 'RangeMapBlaze's.
/// let result = &a & &b; // Alternatively, 'a & b'.
/// assert_eq!(result.to_string(), r#"(2..=2, "b"), (5..=6, "b")"#);
///
/// // Set difference of two 'RangeMapBlaze's.
/// let result = &a - &b; // Alternatively, 'a - b'.
/// assert_eq!(result.to_string(), r#"(3..=4, "a")"#);
///
/// // Symmetric difference of two 'RangeMapBlaze's.
/// let result = &a ^ &b; // Alternatively, 'a ^ b'.
/// assert_eq!(result.to_string(), r#"(1..=1, "b"), (3..=4, "a"), (7..=100, "b")"#);
///
/// // complement of a 'RangeMapBlaze' is a `RangeSetBlaze`.
/// let result = !&b; // Alternatively, '!b'.
/// assert_eq!(result.to_string(), "-2147483648..=0, 3..=4, 101..=2147483647"
/// );
/// // use `complement_with` to create a 'RangeMapBlaze'.
/// let result = b.complement_with(&"z");
/// assert_eq!(result.to_string(), r#"(-2147483648..=0, "z"), (3..=4, "z"), (101..=2147483647, "z")"#);
///
/// // Multiway union of 'RangeMapBlaze's.
/// let z = RangeMapBlaze::from_iter([(2..=2, "z"), (6..=200, "z")]);
/// let result = [&z, &a, &b].union();
/// assert_eq!(result.to_string(), r#"(1..=2, "b"), (3..=4, "a"), (5..=100, "b"), (101..=200, "z")"# );
///
/// // Multiway intersection of 'RangeMapBlaze's.
/// let result = [&z, &a, &b].intersection();
/// assert_eq!(result.to_string(), r#"(2..=2, "b"), (6..=6, "b")"#);
///
/// // Applying multiple operators
/// let result0 = &b - (&z | &a); // Creates an intermediate 'RangeMapBlaze'.
/// // Alternatively, we can use the 'SortedDisjointMap' API and avoid the intermediate 'RangeMapBlaze'.
/// let result1 = RangeMapBlaze::from_sorted_disjoint_map(
///          b.range_values() - (a.range_values() | z.range_values()));
/// assert_eq!(result0, result1);
/// assert_eq!(result0.to_string(), r#"(1..=1, "b")"#);
/// ```
///
/// # `RangeMapBlaze` Union- and Extend-like Methods
///
/// | Operation & Syntax                  | Input Type           | Pre-merge Touching | Cases Optimized |
/// |-------------------------------------|----------------------|---------------------|------------------|
/// | [`a` &#124;= `b`]                   | `RangeMapBlaze`      | -                   | 3                |
/// | [`a` &#124;= `&b`]                  | `&RangeMapBlaze`     | -                   | 3                |
/// | [`a` &#124; `b`]                    | `RangeMapBlaze`      | -                   | 3                |
/// | [`a` &#124; `&b`]                   | `&RangeMapBlaze`     | -                   | 3                |
/// | [`&a` &#124; `b`]                   | `RangeMapBlaze`      | -                   | 3                |
/// | [`&a` &#124; `&b`]                  | `&RangeMapBlaze`     | -                   | 3                |
/// | [`a.extend([(r, v)])`][extend_rv]   | iter `(range, value)`     | Yes                 | 1                |
/// | [`a.extend([(i, v)])`][extend_iv]   | iter `(integer, value)`   | Yes                 | 1                |
/// | [`a.extend_simple(...)`][extend_simple] | iter `(range, value)` | No                  | 1                |
/// | [`a.extend_with(&b)`][extend_with]  | `&RangeMapBlaze`     | -                   | 1                |
/// | [`a.extend_from(b)`][extend_from]   | `RangeMapBlaze`      | -                   | 1                |
/// | [`b.append(&mut a)`][append]        | `&mut RangeMapBlaze` | -                   | 1                |
///
/// Notes:
///
/// - **Pre-merge Touching** means adjacent or overlapping ranges with the same value are combined into a single range before insertions.
/// - **Cases Optimized** indicates how many usage scenarios have dedicated performance paths:
///     - `3` = optimized for small-left, small-right, and similar-sized inputs
///     - `1` = optimized for small-right inputs only
///
/// [`a` &#124;= `b`]: struct.RangeMapBlaze.html#impl-BitOrAssign-for-RangeMapBlaze%3CT,+V%3E
/// [`a` &#124;= `&b`]: struct.RangeMapBlaze.html#impl-BitOrAssign%3C%26RangeMapBlaze%3CT,+V%3E%3E-for-RangeMapBlaze%3CT,+V%3E
/// [`a` &#124; `b`]: struct.RangeMapBlaze.html#impl-BitOr-for-RangeMapBlaze%3CT,+V%3E
/// [`a` &#124; `&b`]: struct.RangeMapBlaze.html#impl-BitOr%3C%26RangeMapBlaze%3CT,+V%3E%3E-for-RangeMapBlaze%3CT,+V%3E
/// [`&a` &#124; `b`]: struct.RangeMapBlaze.html#impl-BitOr%3CRangeMapBlaze%3CT,+V%3E%3E-for-%26RangeMapBlaze%3CT,+V%3E
/// [`&a` &#124; `&b`]: struct.RangeMapBlaze.html#impl-BitOr%3C%26RangeMapBlaze%3CT,+V%3E%3E-for-%26RangeMapBlaze%3CT,+V%3E
/// [extend_rv]: struct.RangeMapBlaze.html#impl-Extend%3C(RangeInclusive%3CT%3E,+V)%3E-for-RangeMapBlaze%3CT,+V%3E
/// [extend_iv]: struct.RangeMapBlaze.html#impl-Extend%3C(T,+V)%3E-for-RangeMapBlaze%3CT,+V%3E
/// [extend_simple]: struct.RangeMapBlaze.html#method.extend_simple
/// [extend_with]: struct.RangeMapBlaze.html#method.extend_with
/// [extend_from]: struct.RangeMapBlaze.html#method.extend_from
/// [append]: struct.RangeMapBlaze.html#method.append
///
/// # `RangeMapBlaze` Comparisons
///
/// `RangeMapBlaze` supports comparisons for equality and lexicographic order:
///
/// - **Equality**: Use `==` and `!=` to check if two `RangeMapBlaze` instances
///   are equal. Two `RangeMapBlaze` instances are considered equal if they
///   contain the same ranges and associated values.
/// - **Ordering**: If the values implement `Ord`, you can use `<`, `<=`, `>`, and `>=`
///   to compare two `RangeMapBlaze` instances. These comparisons are lexicographic,
///   similar to `BTreeMap`, meaning they compare the ranges and their values in sequence.
/// - **Partial Ordering**: If the values implement `PartialOrd` but not `Ord`, you can use
///   the [`partial_cmp`] method to compare two `RangeMapBlaze` instances. This method returns
///   an `Option<Ordering>` that indicates the relative order of the instances or `None` if the
///   values are not comparable.
///
/// See [`partial_cmp`] and [`cmp`] for more examples.
///
///
/// [`BTreeMap`]: alloc::collections::BTreeMap
/// [`partial_cmp`]: RangeMapBlaze::partial_cmp
/// [`cmp`]: RangeMapBlaze::cmp
///
/// # Additional Examples
///
/// See the [module-level documentation] for additional examples.
///
/// [module-level documentation]: index.html
#[derive(Clone, Hash, PartialEq)]
pub struct RangeMapBlaze<T: Integer, V> {
    pub(crate) len: <T as Integer>::SafeLen,
    pub(crate) btree_map: BTreeMap<T, EndValue<T, V>>,
}

/// Creates a new, empty `RangeMapBlaze`.
///
/// # Examples
///
/// ```
/// use range_set_blaze::RangeMapBlaze;
///
/// let a = RangeMapBlaze::<i32, &str>::default();
/// assert!(a.is_empty());
/// ```
impl<T: Integer, V: Eq + Clone> Default for RangeMapBlaze<T, V> {
    fn default() -> Self {
        Self {
            len: <T as Integer>::SafeLen::zero(),
            btree_map: BTreeMap::new(),
        }
    }
}

impl<T: Integer, V: Eq + Clone + fmt::Debug> fmt::Debug for RangeMapBlaze<T, V> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.range_values().into_string())
    }
}

impl<T: Integer, V: Eq + Clone + fmt::Debug> fmt::Display for RangeMapBlaze<T, V> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.range_values().into_string())
    }
}

impl<T: Integer, V: Eq + Clone> RangeMapBlaze<T, V> {
    /// Gets an iterator that visits the integer elements in the [`RangeMapBlaze`] in
    /// ascending and/or descending order. Double-ended.
    ///
    /// Also see the [`RangeMapBlaze::ranges`] method.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(1..=3,"a")]);
    /// let mut map_iter = map.iter();
    /// assert_eq!(map_iter.next(), Some((1, &"a")));
    /// assert_eq!(map_iter.next(), Some((2, &"a")));
    /// assert_eq!(map_iter.next(), Some((3, &"a")));
    /// assert_eq!(map_iter.next(), None);
    /// ```
    ///
    /// Values returned by `.next()` are in ascending order.
    /// Values returned by `.next_back()` are in descending order.
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(3,"c"), (1,"a"), (2,"b")]);
    /// let mut map_iter = map.iter();
    /// assert_eq!(map_iter.next(), Some((1, &"a")));
    /// assert_eq!(map_iter.next_back(), Some((3, &"c")));
    /// assert_eq!(map_iter.next(), Some((2, &"b")));
    /// assert_eq!(map_iter.next_back(), None);
    /// ```
    pub fn iter(&self) -> IterMap<T, &V, RangeValuesIter<'_, T, V>> {
        // If the user asks for an iter, we give them a RangesIter iterator
        // and we iterate that one integer at a time.
        IterMap::new(self.range_values())
    }

    /// Gets an iterator that visits the integer elements in the [`RangeMapBlaze`] in
    /// ascending and/or descending order. Double-ended.
    ///
    /// For a consuming version, see the [`RangeMapBlaze::into_keys`] method.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(1..=3,"a")]);
    /// let mut keys_iter = map.keys();
    /// assert_eq!(keys_iter.next(), Some(1));
    /// assert_eq!(keys_iter.next(), Some(2));
    /// assert_eq!(keys_iter.next(), Some(3));
    /// assert_eq!(keys_iter.next(), None);
    /// ```
    ///
    /// Keys returned by `.next()` are in ascending order.
    /// Keys returned by `.next_back()` are in descending order.
    ///
    /// ```
    /// # use range_set_blaze::RangeMapBlaze;
    /// let map = RangeMapBlaze::from_iter([(3,"c"), (1,"a"), (2,"b")]);
    /// let mut keys_iter = map.keys();
    /// assert_eq!(keys_iter.next(), Some(1));
    /// assert_eq!(keys_iter.next_back(), Some(3));
    /// assert_eq!(keys_iter.next(), Some(2));
    /// assert_eq!(keys_iter.next_back(), None);
    /// ```
    pub fn keys(&self) -> Keys<T, &V, RangeValuesIter<'_, T, V>> {
        Keys::new(self.range_values())
    }

    /// Gets an iterator that visits the integer elements in the [`RangeMapBlaze`] in
    /// ascending and/or descending order. Double-ended.
    ///
    /// The iterator consumes the [`RangeMapBlaze`], yielding one integer at a time from its ranges.
    /// For a non-consuming version, see the [`RangeMapBlaze::keys`] method.
    ///
    /// # Examples
    ///
    /// Iterating in ascending order:
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(1..=3, "a")]);
    /// let mut into_keys_iter = map.into_keys();
    /// assert_eq!(into_keys_iter.next(), Some(1));
    /// assert_eq!(into_keys_iter.next(), Some(2));
    /// assert_eq!(into_keys_iter.next(), Some(3));
    /// assert_eq!(into_keys_iter.next(), None);
    /// ```
    ///
    /// Iterating in both ascending and descending order:
    ///
    /// ```
    /// # use range_set_blaze::RangeMapBlaze;
    /// let map = RangeMapBlaze::from_iter([(1..=3, "a"), (5..=5, "b")]);
    /// let mut into_keys_iter = map.into_keys();
    /// assert_eq!(into_keys_iter.next(), Some(1));
    /// assert_eq!(into_keys_iter.next_back(), Some(5));
    /// assert_eq!(into_keys_iter.next(), Some(2));
    /// assert_eq!(into_keys_iter.next_back(), Some(3));
    /// assert_eq!(into_keys_iter.next(), None);
    /// ```
    ///
    /// Keys returned by `.next()` are in ascending order.
    /// Keys returned by `.next_back()` are in descending order.
    #[inline]
    pub fn into_keys(self) -> IntoKeys<T, V> {
        IntoKeys::new(self.btree_map.into_iter())
    }

    /// Gets an iterator that visits the values in the [`RangeMapBlaze`] in
    /// the order corresponding to the integer elements. Double-ended.
    ///
    /// For a consuming version, see the [`RangeMapBlaze::into_values`] method.
    ///
    /// # Examples
    ///
    /// Iterating over values:
    ///
    /// ```rust
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(3, "c"), (1, "a"), (2, "b")]);
    /// let mut values_iter = map.values();
    /// assert_eq!(values_iter.next(), Some(&"a"));
    /// assert_eq!(values_iter.next(), Some(&"b"));
    /// assert_eq!(values_iter.next(), Some(&"c"));
    /// assert_eq!(values_iter.next(), None);
    /// ```
    ///
    /// Values returned by `.next()` are in the order of corresponding integer elements.
    /// Values returned by `.next_back()` correspond to elements in descending integer order.
    ///
    /// ```rust
    /// # use range_set_blaze::RangeMapBlaze;
    /// let map = RangeMapBlaze::from_iter([(3, "c"), (1, "a"), (2, "b")]);
    /// let mut values_iter = map.values();
    /// assert_eq!(values_iter.next(), Some(&"a"));
    /// assert_eq!(values_iter.next_back(), Some(&"c"));
    /// assert_eq!(values_iter.next(), Some(&"b"));
    /// assert_eq!(values_iter.next_back(), None);
    /// ```
    pub fn values(&self) -> Values<T, &V, RangeValuesIter<'_, T, V>> {
        Values::new(self.range_values())
    }

    /// Gets an iterator that visits the values in the [`RangeMapBlaze`] in
    /// the order corresponding to the integer elements. Double-ended.
    ///
    /// The iterator consumes the [`RangeMapBlaze`], yielding one value at a time for
    /// each integer in its ranges. For a non-consuming version, see the [`RangeMapBlaze::values`] method.
    ///
    /// # Examples
    ///
    /// Iterating over values in ascending order:
    ///
    /// ```rust
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(3, "c"), (1, "a"), (2, "b")]);
    /// let mut into_values_iter = map.into_values();
    /// assert_eq!(into_values_iter.next(), Some("a"));
    /// assert_eq!(into_values_iter.next(), Some("b"));
    /// assert_eq!(into_values_iter.next(), Some("c"));
    /// assert_eq!(into_values_iter.next(), None);
    /// ```
    ///
    /// Iterating over values in both ascending and descending order:
    ///
    /// ```rust
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(1..=3, "a"), (5..=5, "b")]);
    /// let mut into_values_iter = map.into_values();
    /// assert_eq!(into_values_iter.next(), Some("a"));
    /// assert_eq!(into_values_iter.next_back(), Some("b"));
    /// assert_eq!(into_values_iter.next(), Some("a"));
    /// assert_eq!(into_values_iter.next_back(), Some("a"));
    /// assert_eq!(into_values_iter.next(), None);
    /// ```
    ///
    /// Values returned by `.next()` correspond to elements in ascending integer order.
    /// Values returned by `.next_back()` correspond to elements in descending integer order.
    #[inline]
    pub fn into_values(self) -> IntoValues<T, V> {
        IntoValues::new(self.btree_map.into_iter())
    }

    /// Returns the first element in the set, if any.
    /// This element is always the minimum of all integer elements in the set.
    ///
    /// # Examples
    ///
    /// Basic usage:
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut map = RangeMapBlaze::new();
    /// assert_eq!(map.first_key_value(), None);
    /// map.insert(1,"a");
    /// assert_eq!(map.first_key_value(), Some((1, &"a")));
    /// map.insert(2,"b");
    /// assert_eq!(map.first_key_value(), Some((1, &"a")));
    /// ```
    #[must_use]
    pub fn first_key_value(&self) -> Option<(T, &V)> {
        self.btree_map
            .first_key_value()
            .map(|(k, end_value)| (*k, &end_value.value))
    }

    /// Returns the element in the set, if any, that is equal to
    /// the value.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(3,"c"), (1,"a"), (2,"b")]);
    /// assert_eq!(map.get(2), Some(&"b"));
    /// assert_eq!(map.get(4), None);
    /// ```
    pub fn get(&self, key: T) -> Option<&V> {
        self.get_key_value(key).map(|(_, value)| value)
    }

    /// Returns the key and value in the map, if any, that contains the given key.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(3..=5, "c"), (1..=2, "a")]);
    /// assert_eq!(map.get_key_value(2), Some((2, &"a")));
    /// assert_eq!(map.get_key_value(4), Some((4, &"c")));
    /// assert_eq!(map.get_key_value(6), None);
    /// ```
    pub fn get_key_value(&self, key: T) -> Option<(T, &V)> {
        self.containing_entry(key)
            .map(|(_start, end_value)| (key, &end_value.value))
    }

    /// Returns the stored range and value containing `key`, if any.
    ///
    /// See the [Ranges and gaps guide][crate::gaps] for the corresponding set
    /// API and for the difference between `range_at` and `range_or_gap_at`.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(1..=3, "red"), (7..=10, "blue")]);
    /// assert_eq!(map.range_at(2), Some((1..=3, &"red")));
    /// assert_eq!(map.range_at(5), None);
    /// ```
    #[must_use]
    pub fn range_at(&self, key: T) -> Option<(RangeInclusive<T>, &V)> {
        self.containing_entry(key)
            .map(|(start, end_value)| (*start..=end_value.end, &end_value.value))
    }
    /// Returns the stored mapped range or maximal gap containing `key`.
    ///
    /// The returned value is `Some(&V)` when the range is mapped and `None`
    /// when it is a gap.
    ///
    /// See the [Ranges and gaps guide][crate::gaps] for the corresponding set
    /// API and for examples of querying both kinds of container.
    ///
    /// # Performance
    ///
    /// Performs one tree lookup for a mapped key and two tree lookups for a
    /// gap, taking `O(log r)` time, where `r` is the number of mapped ranges.
    ///
    /// # Examples
    ///
    /// ```
    /// # use range_set_blaze::RangeMapBlaze;
    /// let map = RangeMapBlaze::from_iter([(1..=3, "red"), (7..=10, "blue")]);
    /// assert_eq!(map.range_or_gap_at(2), (1..=3, Some(&"red")));
    /// assert_eq!(map.range_or_gap_at(5), (4..=6, None));
    /// assert_eq!(map.range_or_gap_at(8), (7..=10, Some(&"blue")));
    /// ```
    #[must_use]
    #[inline]
    pub fn range_or_gap_at(&self, key: T) -> (RangeInclusive<T>, Option<&V>) {
        #[cfg(feature = "cursor_nightly_experimental")]
        return self.range_or_gap_at_cursor(key);

        #[cfg(not(feature = "cursor_nightly_experimental"))]
        self.range_or_gap_at_baseline(key)
    }

    #[cfg(any(test, not(feature = "cursor_nightly_experimental")))]
    #[inline]
    pub(crate) fn range_or_gap_at_baseline(&self, key: T) -> (RangeInclusive<T>, Option<&V>) {
        if let Some((start_before, end_value)) = self.predecessor_entry(key) {
            if key <= end_value.end {
                return (*start_before..=end_value.end, Some(&end_value.value));
            }
            if let Some((start_next, _)) = self.btree_map.range(key..).next() {
                return (end_value.end.add_one()..=start_next.sub_one(), None);
            }
            return (end_value.end.add_one()..=T::max_value(), None);
        }

        if let Some((start_next, _)) = self.btree_map.range(key..).next() {
            return (T::min_value()..=start_next.sub_one(), None);
        }
        (T::min_value()..=T::max_value(), None)
    }

    #[cfg(feature = "cursor_nightly_experimental")]
    #[inline]
    pub(crate) fn range_or_gap_at_cursor(&self, key: T) -> (RangeInclusive<T>, Option<&V>) {
        // A single position exposes both ranges adjacent to `key`; unlike the baseline,
        // a gap does not require a second logarithmic search for its right boundary.
        let cursor = self.btree_map.lower_bound(Bound::Included(&key));

        if let Some((start_before, end_value)) = cursor.peek_prev() {
            if key <= end_value.end {
                return (*start_before..=end_value.end, Some(&end_value.value));
            }
            if let Some((start_next, end_value_next)) = cursor.peek_next() {
                if key == *start_next {
                    return (
                        *start_next..=end_value_next.end,
                        Some(&end_value_next.value),
                    );
                }
                return (end_value.end.add_one()..=start_next.sub_one(), None);
            }
            return (end_value.end.add_one()..=T::max_value(), None);
        }

        if let Some((start_next, end_value)) = cursor.peek_next() {
            if key == *start_next {
                return (*start_next..=end_value.end, Some(&end_value.value));
            }
            return (T::min_value()..=start_next.sub_one(), None);
        }
        (T::min_value()..=T::max_value(), None)
    }

    /// Returns the last element in the set, if any.
    /// This element is always the maximum of all elements in the set.
    ///
    /// # Examples
    ///
    /// Basic usage:
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut map = RangeMapBlaze::new();
    /// assert_eq!(map.last_key_value(), None);
    /// map.insert(1, "a");
    /// assert_eq!(map.last_key_value(), Some((1, &"a")));
    /// map.insert(2, "b");
    /// assert_eq!(map.last_key_value(), Some((2, &"b")));
    /// ```
    #[must_use]
    pub fn last_key_value(&self) -> Option<(T, &V)> {
        self.btree_map
            .last_key_value()
            .map(|(_, end_value)| (end_value.end, &end_value.value))
    }

    /// Create a [`RangeMapBlaze`] from a [`SortedDisjointMap`] iterator.
    ///
    /// *For more about constructors and performance, see [`RangeMapBlaze` Constructors](struct.RangeMapBlaze.html#rangemapblaze-constructors).*
    ///
    /// [`SortedDisjointMap`]: crate::SortedDisjointMap.html#table-of-contents
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::prelude::*;
    ///
    /// let a0 = RangeMapBlaze::from_sorted_disjoint_map(CheckSortedDisjointMap::new([(-10..=-5, &"a"), (1..=2, &"b")]));
    /// let a1: RangeMapBlaze<i32,_> = CheckSortedDisjointMap::new([(-10..=-5, &"a"), (1..=2, &"b")]).into_range_map_blaze();
    /// assert!(a0 == a1 && a0.to_string() == r#"(-10..=-5, "a"), (1..=2, "b")"#);
    /// ```
    pub fn from_sorted_disjoint_map<VC, I>(iter: I) -> Self
    where
        VC: ValueCarrier<Value = V>,
        I: SortedDisjointMap<T, VC>,
    {
        let mut iter_with_len = SortedDisjointMapWithLenSoFar::new(iter);
        let btree_map: BTreeMap<T, EndValue<T, VC::Value>> = (&mut iter_with_len).collect();
        Self {
            btree_map,
            len: iter_with_len.len_so_far(),
        }
    }

    #[allow(dead_code)]
    #[must_use]
    pub(crate) fn len_slow(&self) -> <T as Integer>::SafeLen {
        Self::btree_map_len(&self.btree_map)
    }

    /// Moves all elements from `other` into `self`, leaving `other` empty.
    ///
    /// This method has *right-to-left precedence*:  if any ranges overlap, values in `other`
    /// will overwrite those in `self`.
    ///
    /// # Performance
    ///
    /// This method inserts each range from `other` into `self` one-by-one, with overall time
    /// complexity `O(n log m)`, where `n` is the number of ranges in `other` and `m` is the number
    /// of ranges in `self`.
    ///
    /// For large `n`, consider using the `|` operator, which performs a sorted merge and runs in `O(n + m)` time.
    ///
    /// **See:** [Summary of Union and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods).
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut a = RangeMapBlaze::from_iter([(1..=3,"a")]);
    /// let mut b = RangeMapBlaze::from_iter([(3..=5,"b")]);
    ///
    /// a.append(&mut b);
    ///
    /// assert_eq!(a.len(), 5u64);
    /// assert_eq!(b.len(), 0u64);
    ///
    /// assert_eq!(a[1], "a");
    /// assert_eq!(a[2], "a");
    /// assert_eq!(a[3], "b");
    /// assert_eq!(a[4], "b");
    /// assert_eq!(a[5], "b");
    /// ```
    pub fn append(&mut self, other: &mut Self) {
        let original_other_btree_map = mem::take(&mut other.btree_map);
        other.len = <T as Integer>::SafeLen::zero();

        for (start, end_value) in original_other_btree_map {
            self.internal_add(start..=end_value.end, end_value.value);
        }
    }

    /// Clears the map, removing all elements.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut a = RangeMapBlaze::new();
    /// a.insert(1, "a");
    /// a.clear();
    /// assert!(a.is_empty());
    /// ```
    pub fn clear(&mut self) {
        self.btree_map.clear();
        self.len = <T as Integer>::SafeLen::zero();
    }

    /// Returns `true` if the map contains no elements.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut a = RangeMapBlaze::new();
    /// assert!(a.is_empty());
    /// a.insert(1, "a");
    /// assert!(!a.is_empty());
    /// ```
    #[must_use]
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.btree_map.is_empty()
    }
    /// Returns `true` if the map contains all possible integers.
    ///
    /// For type `T`, this means the union of ranges covers `T::min_value()` through `T::max_value()`.
    /// Complexity: O(1) using a precomputed length.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// // Multiple ranges covering all values is universal
    /// let multi_universal = RangeMapBlaze::from_iter([
    ///     (0_u8..=100, "first"),
    ///     (101_u8..=255, "second")
    /// ]);
    /// assert!(multi_universal.is_universal());
    ///
    /// // Incomplete coverage is not universal
    /// let incomplete = RangeMapBlaze::from_iter([(1_u8..=255, "missing_zero")]);
    /// assert!(!incomplete.is_universal());
    /// ```
    #[must_use]
    #[inline]
    pub fn is_universal(&self) -> bool {
        self.len() == T::safe_len(&(T::min_value()..=T::max_value()))
    }
    /// Returns `true` if the set contains an element equal to the value.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(3,"c"), (1,"a"), (2,"b")]);
    /// assert_eq!(map.contains_key(1), true);
    /// assert_eq!(map.contains_key(4), false);
    /// ```
    pub fn contains_key(&self, key: T) -> bool {
        self.containing_entry(key).is_some()
    }

    fn predecessor_entry(&self, key: T) -> Option<(&T, &EndValue<T, V>)> {
        self.btree_map.range(..=key).next_back()
    }

    fn containing_entry(&self, key: T) -> Option<(&T, &EndValue<T, V>)> {
        self.predecessor_entry(key)
            .and_then(|(start, end_value)| (key <= end_value.end).then_some((start, end_value)))
    }

    // LATER: might be able to shorten code by combining cases
    #[cfg(any(
        test,
        feature = "test_util",
        not(feature = "cursor_nightly_experimental")
    ))]
    fn delete_extra(&mut self, internal_range: &RangeInclusive<T>) {
        let (start, end) = internal_range.clone().into_inner();
        let mut after = self.btree_map.range_mut(start..);
        let (start_after, end_value_after) = after
            .next()
            .expect("Real Assert: There will always be a next");
        debug_assert!(start == *start_after && end == end_value_after.end);

        let mut end_new = end;
        let mut end_new_same_val = end;
        let delete_list = after
            .map_while(|(start_delete, end_value_delete)| {
                // same values
                if end_value_after.value == end_value_delete.value {
                    // must check this in two parts to avoid overflow
                    if *start_delete <= end || *start_delete <= end.add_one() {
                        end_new_same_val = max(end_new_same_val, end_value_delete.end);
                        end_new = max(end_new, end_value_delete.end);
                        self.len -= T::safe_len(&(*start_delete..=end_value_delete.end));
                        Some(*start_delete)
                    } else {
                        None
                    }
                // different values
                } else if *start_delete <= end {
                    end_new = max(end_new, end_value_delete.end);
                    self.len -= T::safe_len(&(*start_delete..=end_value_delete.end));
                    Some(*start_delete)
                } else {
                    None
                }
            })
            .collect::<Vec<_>>();
        if end >= end_new {
            for start in delete_list {
                self.btree_map.remove(&start);
            }
        } else if end_new_same_val > end {
            // last item is the same as the new and extends beyond the new
            self.len += T::safe_len(&(end..=end_new.sub_one()));
            debug_assert!(*start_after <= end_new);
            end_value_after.end = end_new;
            for start in delete_list {
                self.btree_map.remove(&start);
            }
        } else {
            // last item extends beyond the new but has a different value.
            for &start in &delete_list[0..delete_list.len() - 1] {
                self.btree_map.remove(&start);
                // take the last one
            }
            let last = self
                .btree_map
                .remove(&delete_list[delete_list.len() - 1])
                .expect("Real Assert: There will always be a last");
            let last_end = last.end;
            debug_assert!(end.add_one() <= last.end); // real assert
            self.btree_map.insert(end.add_one(), last);
            self.len += T::safe_len(&(end.add_one()..=last_end));
        }
    }

    /// Adds a value to the set.
    ///
    /// Returns whether the value was newly inserted. That is:
    ///
    /// - If the set did not previously contain an equal value, `true` is
    ///   returned.
    /// - If the set already contained an equal value, `false` is returned, and
    ///   the entry is not updated.
    ///
    /// # Performance
    /// Inserting n items will take in O(n log m) time, where n is the number of inserted items and m is the number of ranges in `self`.
    /// When n is large, consider using `|` which is O(n+m) time.
    /// The nightly-only `cursor_nightly_experimental` feature speeds up this method by roughly 1.7x; see the
    /// [Cargo Features section of the README](crate#cargo-features).
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut map = RangeMapBlaze::new();
    /// assert_eq!(map.insert(37, "a"), None);
    /// assert_eq!(map.is_empty(), false);
    ///
    /// map.insert(37, "b");
    /// assert_eq!(map.insert(37, "c"), Some("b"));
    /// assert_eq!(map[37], "c");
    /// ```
    pub fn insert(&mut self, key: T, value: V) -> Option<V> {
        let old = self.get(key).cloned();
        self.internal_add(key..=key, value);
        old
    }

    // LATER: Think about an entry API with or_insert and or_insert_with

    /// Constructs an iterator over a sub-range of elements in the set.
    ///
    /// Not to be confused with [`RangeMapBlaze::ranges`], which returns an iterator over the ranges in the set.
    ///
    /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
    /// yield elements from min (inclusive) to max (exclusive).
    /// The range may also be entered as `(Bound<T, V, VC>, Bound<T, V, VC>)`, so for example
    /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
    /// range from 4 to 10.
    ///
    /// # Panics
    ///
    /// Panics if start (inclusive) is greater than end (inclusive).
    ///
    /// # Performance
    ///
    /// Although this could be written to run in time O(ln(n)) in the number of ranges, it is currently O(n) in the number of ranges.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    /// use core::ops::Bound::Included;
    ///
    /// let mut map = RangeMapBlaze::new();
    /// map.insert(3, "a");
    /// map.insert(5, "b");
    /// map.insert(8, "c");
    /// for (key, value) in map.range((Included(4), Included(8))) {
    ///     println!("{key}: {value}");
    /// } // prints "5: b" and "8: c"
    /// assert_eq!(Some((5, "b")), map.range(4..).next());
    /// ```
    #[allow(clippy::manual_assert)] // We use "if...panic!" for coverage auditing.
    pub fn range<R>(&self, range: R) -> IntoIterMap<T, V>
    where
        R: RangeBounds<T>,
    {
        // LATER 'range' could be made more efficient (it currently creates a RangeMapBlaze for no good reason)
        let (start, end) = extract_range(range);
        assert!(
            start <= end,
            "start (inclusive) must be less than or equal to end (inclusive)"
        );

        let bounds = CheckSortedDisjoint::new([start..=end]);
        let range_map_blaze = self
            .range_values()
            .map_and_set_intersection(bounds)
            .into_range_map_blaze();
        range_map_blaze.into_iter()
    }

    /// Adds a range to the set.
    ///
    /// Returns whether any values where newly inserted. That is:
    ///
    /// - If the set did not previously contain some value in the range, `true` is
    ///   returned.
    /// - If the set already contained every value in the range, `false` is returned, and
    ///   the entry is not updated.
    ///
    /// # Performance
    /// Inserting n items will take in O(n log m) time, where n is the number of inserted items and m is the number of ranges in `self`.
    /// When n is large, consider using `|` which is O(n+m) time.
    /// The nightly-only `cursor_nightly_experimental` feature speeds up this method by roughly 1.7x; see the
    /// [Cargo Features section of the README](crate#cargo-features).
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut map = RangeMapBlaze::new();
    /// assert_eq!(map.ranges_insert(2..=5, "a"), true);
    /// assert_eq!(map.ranges_insert(5..=6, "b"), true);
    /// assert_eq!(map.ranges_insert(3..=4, "c"), false);
    /// assert_eq!(map.len(), 5u64);
    /// ```
    pub fn ranges_insert<R>(&mut self, range: R, value: V) -> bool
    where
        R: RangeBounds<T>,
    {
        let len_before = self.len;
        let (start, end) = extract_range(range);
        self.internal_add(start..=end, value);
        self.len != len_before
    }

    /// If the set contains an element equal to the value, removes it from the
    /// set and drops it. Returns whether such an element was present.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut map = RangeMapBlaze::new();
    /// map.insert(1, "a");
    /// assert_eq!(map.remove(1), Some("a"));
    /// assert_eq!(map.remove(1), None);
    /// ```
    #[allow(clippy::missing_panics_doc)]
    pub fn remove(&mut self, key: T) -> Option<V> {
        // The code can have only one mutable reference to self.btree_map.

        // Find that range that might contain the key
        let (start_ref, end_value_mut) = self.btree_map.range_mut(..=key).next_back()?;
        let end = end_value_mut.end;

        // If the key is not in the range, we're done
        if end < key {
            return None;
        }
        let start = *start_ref;
        debug_assert!(start <= key, "Real Assert: start <= key");

        // It's in the range.
        self.len -= <T::SafeLen>::one();

        let value = if start == key {
            self.btree_map
                .remove(&start)
                .expect("Real Assert: There will always be a start")
                .value
        } else {
            debug_assert!(start < key, "Real Assert: start < key");
            // This range will now end at key-1.
            end_value_mut.end = key.sub_one();
            end_value_mut.value.clone()
        };

        // If needed, add a new range after key
        if key < end {
            self.btree_map.insert(
                key.add_one(),
                EndValue {
                    end,
                    value: value.clone(),
                },
            );
        }

        Some(value)
    }

    /// Splits the collection into two at the value. Returns a new collection
    /// with all elements greater than or equal to the value.
    ///
    /// # Examples
    ///
    /// Basic usage:
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut a = RangeMapBlaze::new();
    /// a.insert(1, "a");
    /// a.insert(2, "b");
    /// a.insert(3, "c");
    /// a.insert(17, "d");
    /// a.insert(41, "e");
    ///
    /// let b = a.split_off(3);
    ///
    /// assert_eq!(a, RangeMapBlaze::from_iter([(1..=1, "a"), (2..=2, "b")]));
    /// assert_eq!(b, RangeMapBlaze::from_iter([(3..=3, "c"), (17..=17, "d"), (41..=41, "e")]));
    /// ```
    #[must_use]
    pub fn split_off(&mut self, key: T) -> Self {
        let old_len = self.len;
        let old_btree_len = self.btree_map.len();
        let mut new_btree = self.btree_map.split_off(&key);
        let Some(last_entry) = self.btree_map.last_entry() else {
            // Left is empty
            self.len = T::SafeLen::zero();
            return Self {
                btree_map: new_btree,
                len: old_len,
            };
        };

        let end_value = last_entry.get();
        let end = end_value.end;
        if end < key {
            // The split is clean
            let (a_len, b_len) = self.two_element_lengths(old_btree_len, &new_btree, old_len);
            self.len = a_len;
            return Self {
                btree_map: new_btree,
                len: b_len,
            };
        }

        // The split is not clean, so we must move some keys from the end of self to the start of b.
        let value = end_value.value.clone();
        last_entry.into_mut().end = key.sub_one();
        new_btree.insert(key, EndValue { end, value });
        let (a_len, b_len) = self.two_element_lengths(old_btree_len, &new_btree, old_len);
        self.len = a_len;
        Self {
            btree_map: new_btree,
            len: b_len,
        }
    }

    // Find the len of the smaller btree_map and then the element len of self & b.
    fn two_element_lengths(
        &self,
        old_btree_len: usize,
        new_btree: &BTreeMap<T, EndValue<T, V>>,
        mut old_len: <T as Integer>::SafeLen,
    ) -> (<T as Integer>::SafeLen, <T as Integer>::SafeLen) {
        if old_btree_len / 2 < new_btree.len() {
            let a_len = Self::btree_map_len(&self.btree_map);
            old_len -= a_len;
            (a_len, old_len)
        } else {
            let b_len = Self::btree_map_len(new_btree);
            old_len -= b_len;
            (old_len, b_len)
        }
    }

    fn btree_map_len(btree_map: &BTreeMap<T, EndValue<T, V>>) -> T::SafeLen {
        btree_map.iter().fold(
            <T as Integer>::SafeLen::zero(),
            |acc, (start, end_value)| acc + T::safe_len(&(*start..=end_value.end)),
        )
    }

    #[cfg(any(
        test,
        feature = "test_util",
        not(feature = "cursor_nightly_experimental")
    ))]
    #[inline]
    fn has_gap(end_before: T, start: T) -> bool {
        end_before
            .checked_add_one()
            .is_some_and(|end_before_succ| end_before_succ < start)
    }

    // https://stackoverflow.com/questions/49599833/how-to-find-next-smaller-key-in-btreemap-btreeset
    // https://stackoverflow.com/questions/35663342/how-to-modify-partially-remove-a-range-from-a-btreemap
    // LATER might be able to shorten code by combining cases
    // FUTURE: would be nice of BTreeMap to have a partition_point function that returns two iterators
    #[allow(clippy::too_many_lines)]
    #[allow(clippy::cognitive_complexity)]
    #[cfg(any(
        test,
        feature = "test_util",
        not(feature = "cursor_nightly_experimental")
    ))]
    pub(crate) fn internal_add_baseline(&mut self, range: RangeInclusive<T>, value: V) {
        let (start, end) = range.clone().into_inner();

        // === case: empty
        if end < start {
            return;
        }
        let mut before_iter = self.btree_map.range_mut(..=start).rev();

        // === case: no before
        let Some((start_before, end_value_before)) = before_iter.next() else {
            // no before, so must be first
            self.internal_add2(&range, value);
            // You must return or break out of the current block after handling the failure case
            return;
        };

        let start_before = *start_before;
        let end_before = end_value_before.end;

        // === case: gap between before and new
        if Self::has_gap(end_before, start) {
            // there is a gap between the before and the new
            // ??? aa...
            self.internal_add2(&range, value);
            return;
        }

        let before_contains_new = end_before >= end;
        let same_value = value == end_value_before.value;

        // === case: same value and before contains new
        if before_contains_new && same_value {
            // same value, so do nothing
            // AAAAA
            //  aaa
            return;
        }

        // === case: same value and new extends beyond before
        if !before_contains_new && same_value {
            // same value, so just extend the before
            // AAA
            //  aaaa...
            self.len += T::safe_len(&(end_before..=end.sub_one()));
            debug_assert!(start_before <= end); // real assert
            end_value_before.end = end;
            self.delete_extra(&(start_before..=end));
            return;
        }

        // Thus, the values are different

        let same_start = start == start_before;

        // === case: new goes beyond before and different values
        if !before_contains_new && !same_value && same_start {
            // Thus, values are different, before contains new, and they start together

            let interesting_before_before = before_iter.next().and_then(|bb| {
                let (_, bb_value) = &bb;
                (bb_value.end.add_one() == start && bb_value.value == value).then_some(bb)
            });

            // === case: values are different, new extends beyond before, and they start together and an interesting before-before
            // an interesting before-before: something before before, touching and with the same value as new
            if let Some(bb) = interesting_before_before {
                debug_assert!(!before_contains_new && !same_value && same_start);

                // AABBBB
                //   aaaaaaa
                // AAAAAAAAA
                let (bb_start, bb_value) = bb;
                self.len += T::safe_len(&(bb_value.end.add_one()..=end));
                let bb_start = *bb_start;
                debug_assert!(bb_start <= end); // real assert
                bb_value.end = end;
                self.delete_extra(&(bb_start..=end));
                return;
            }

            // === case: values are different, they start together but new ends later and no interesting before-before
            debug_assert!(!same_value && same_start && interesting_before_before.is_none());

            // ^BBBB
            //  aaaaaaa
            // ^AAAAAAA
            debug_assert!(end_before < end); // real assert
            self.len += T::safe_len(&(end_before.add_one()..=end));
            end_value_before.end = end;
            end_value_before.value = value;
            self.delete_extra(&range);
            return;
        }
        if !before_contains_new && !same_value && !same_start {
            // different value, so must trim the before and then insert the new
            // BBB
            //  aaaa...
            if start <= end_before {
                self.len -= T::safe_len(&(start..=end_before));
                debug_assert!(start_before <= start.sub_one()); // real assert
                end_value_before.end = start.sub_one(); // safe because !same_start
            }
            self.internal_add2(&range, value);
            return;
        }

        // Thus, the values are different and before contains new
        debug_assert!(before_contains_new && !same_value);

        let same_end = end == end_before;

        // === case: values are different and new is surrounded by before
        if !same_start && !same_end {
            debug_assert!(before_contains_new && !same_value);
            debug_assert!(start_before < start && end < end_before);
            // Different values still ...
            // The new starts later and ends before,
            // BBBBBB
            //   aaa
            // BBAAAB
            //  so trim the before and then insert two
            debug_assert!(start_before <= start.sub_one()); // real assert
            end_value_before.end = start.sub_one();
            let before_value = end_value_before.value.clone();
            debug_assert!(start <= end); // real assert
            self.btree_map.insert(start, EndValue { end, value });
            debug_assert!(end.add_one() <= end_before); // real assert
            self.btree_map.insert(
                end.add_one(),
                EndValue {
                    end: end_before,
                    value: before_value,
                },
            );
            return;
        }

        // === case: values are different, new instead of before and they end together
        if !same_start && same_end {
            debug_assert!(before_contains_new && !same_value);
            debug_assert!(start_before < start && end == end_before);
            // Different values still ...
            // The new starts later but they end together,
            // BBBBB???
            //   aaa
            // BBAAA???
            //  so trim the before and then insert the new.
            debug_assert!(start_before <= start.sub_one()); // real assert
            end_value_before.end = start.sub_one();
            debug_assert!(start <= end); // real assert
            self.btree_map.insert(start, EndValue { end, value });
            self.delete_extra(&(start..=end));
            return;
        }

        // Thus, values are different, before contains new, and they start together

        let interesting_before_before = before_iter.next().and_then(|bb| {
            let (_, bb_value) = &bb;
            (bb_value.end.add_one() == start && bb_value.value == value).then_some(bb)
        });

        // === case: values are different, before contains new, and they start together and an interesting before-before
        // an interesting before-before: something before before, touching and with the same value as new
        if let Some(bb) = interesting_before_before {
            debug_assert!(before_contains_new && !same_value && same_start);

            // AABBBB???
            //   aaaa
            // AAAAAA???
            let (bb_start, bb_value) = bb;
            self.len += T::safe_len(&(bb_value.end.add_one()..=end));
            let bb_start = *bb_start;
            debug_assert!(bb_start <= end); // real assert
            bb_value.end = end;
            self.delete_extra(&(bb_start..=end));
            return;
        }

        // === case: values are different, they start and end together and no interesting before-before
        if same_end {
            debug_assert!(!same_value && same_start && interesting_before_before.is_none());

            // ^BBBB???
            //  aaaa
            // ^AAAA???
            end_value_before.value = value;
            self.delete_extra(&(start_before..=end));
            return;
        }

        // === case: values are different, they start together, new ends first, and no interesting before-before
        {
            debug_assert!(
                !same_value
                    && same_start
                    && end < end_before
                    && interesting_before_before.is_none()
            );

            // ^BBBB
            //  aaa
            // ^AAAB
            let value_before = mem::replace(&mut end_value_before.value, value);
            debug_assert!(start_before <= end); // real assert
            end_value_before.end = end;
            debug_assert!(end.add_one() <= end_before); // real assert
            self.btree_map.insert(
                end.add_one(),
                EndValue {
                    end: end_before,
                    value: value_before,
                },
            );
        }
    }

    #[cfg(feature = "cursor_nightly_experimental")]
    fn cursor_insert_range(
        cursor: &mut CursorMut<'_, T, EndValue<T, V>>,
        len: &mut T::SafeLen,
        start: T,
        end: T,
        value: V,
    ) {
        assert!(
            cursor.insert_before(start, EndValue { end, value }).is_ok(),
            "Real Assert: the range belongs at the cursor"
        );
        // `insert_before` moves the gap after the new entry: `peek_prev` is the inserted range,
        // while `peek_next` is the entry that followed the old gap.
        *len += T::safe_len(&(start..=end));
    }

    #[cfg(feature = "cursor_nightly_experimental")]
    fn cursor_scan_forward(
        cursor: &mut CursorMut<'_, T, EndValue<T, V>>,
        len: &mut T::SafeLen,
        pending_start: T,
        mut pending_end: T,
        pending_is_stored: bool,
        value: &V,
    ) -> CursorScanResult<T, V> {
        loop {
            let candidate = cursor
                .peek_next()
                .map(|(start, end_value)| (*start, end_value.end, end_value.value == *value));
            let Some((stored_start, stored_end, same_value)) = candidate else {
                return CursorScanResult {
                    pending_end,
                    right_residual: None,
                    unchanged: false,
                };
            };
            if !pending_is_stored
                && stored_start == pending_start
                && same_value
                && stored_end >= pending_end
            {
                return CursorScanResult {
                    pending_end,
                    right_residual: None,
                    unchanged: true,
                };
            }
            let Some(action) = classify_forward(stored_start, stored_end, pending_end, same_value)
            else {
                return CursorScanResult {
                    pending_end,
                    right_residual: None,
                    unchanged: false,
                };
            };

            let (_, removed) = cursor
                .remove_next()
                .expect("Real Assert: the peeked successor still exists");
            // The gap is preserved: `peek_prev` is unchanged and `peek_next` is the next suffix.
            *len -= T::safe_len(&(stored_start..=removed.end));

            match action {
                ForwardInsertAction::MergeSameValue => {
                    let extended_end = max(pending_end, removed.end);
                    if pending_is_stored && extended_end > pending_end {
                        cursor
                            .peek_prev()
                            .map(|(_, end_value)| end_value)
                            .expect("Real Assert: the stored pending range is the predecessor")
                            .end = extended_end;
                        *len += T::safe_len(&(pending_end.add_one()..=extended_end));
                    }
                    pending_end = extended_end;
                }
                ForwardInsertAction::DeleteOverwritten => {}
                ForwardInsertAction::KeepRightResidual { right_start } => {
                    return CursorScanResult {
                        pending_end,
                        right_residual: Some((right_start, removed)),
                        unchanged: false,
                    };
                }
            }
        }
    }

    #[cfg(feature = "cursor_nightly_experimental")]
    pub(crate) fn internal_add_cursor(&mut self, range: RangeInclusive<T>, value: V) {
        let (mut pending_start, mut pending_end) = range.into_inner();
        if pending_end < pending_start {
            return;
        }

        let mut right_residual = None;
        let mut pending_is_stored = false;
        let mut cursor = self
            .btree_map
            .lower_bound_mut(Bound::Included(&pending_start));

        // Cursor position: `peek_prev` is the greatest stored start below `pending_start`, and
        // `peek_next` is the least stored start at or above it.
        // The predecessor starts strictly before `pending_start`. It is the only stored range
        // on the left that can overlap or touch the insertion. Removing it first also makes the
        // exact-start normalization case explicit: a following range that starts at the insertion
        // boundary can be removed without hiding an equal-valued predecessor.
        let predecessor = cursor
            .peek_prev()
            .map(|(start, end_value)| (*start, end_value.end, end_value.value == value));
        if let Some((stored_start, stored_end, same_value)) = predecessor {
            match classify_predecessor(stored_end, pending_start, pending_end, same_value) {
                PredecessorInsertAction::Unaffected => {}
                PredecessorInsertAction::MergeSameValue => {
                    if stored_end >= pending_end {
                        return;
                    }
                    let end_value = cursor
                        .peek_prev()
                        .map(|(_, end_value)| end_value)
                        .expect("Real Assert: the peeked predecessor still exists");
                    self.len += T::safe_len(&(stored_end.add_one()..=pending_end));
                    end_value.end = pending_end;
                    pending_start = stored_start;
                    pending_is_stored = true;
                    // Mutating the predecessor's end does not move the cursor. The predecessor
                    // is now the pending range, `peek_prev` refers to it, and `peek_next` is
                    // unchanged.
                }
                PredecessorInsertAction::KeepLeftResidual {
                    left_end,
                    right_start,
                } => {
                    let end_value = cursor
                        .peek_prev()
                        .map(|(_, end_value)| end_value)
                        .expect("Real Assert: the peeked predecessor still exists");
                    right_residual = right_start.map(|right_start| {
                        (
                            right_start,
                            EndValue {
                                end: stored_end,
                                value: end_value.value.clone(),
                            },
                        )
                    });
                    end_value.end = left_end;
                    self.len -= T::safe_len(&(pending_start..=stored_end));
                    // Mutating the predecessor's end does not move the cursor: `peek_prev` is the
                    // trimmed left residual and `peek_next` is unchanged. A value clone occurs
                    // only when the old range also leaves a right residual.
                }
            }
        }

        if right_residual.is_none() {
            // The forward scan maintains the invariant documented above.
            let scan_result = Self::cursor_scan_forward(
                &mut cursor,
                &mut self.len,
                pending_start,
                pending_end,
                pending_is_stored,
                &value,
            );
            if scan_result.unchanged {
                return;
            }
            pending_end = scan_result.pending_end;
            right_residual = scan_result.right_residual;
        }

        if !pending_is_stored {
            Self::cursor_insert_range(
                &mut cursor,
                &mut self.len,
                pending_start,
                pending_end,
                value,
            );
        }

        if let Some((residual_start, residual_end_value)) = right_residual {
            let residual_end = residual_end_value.end;
            Self::cursor_insert_range(
                &mut cursor,
                &mut self.len,
                residual_start,
                residual_end,
                residual_end_value.value,
            );
        }

        debug_assert!(self.len == self.len_slow());
    }

    #[inline]
    pub(crate) fn internal_add(&mut self, range: RangeInclusive<T>, value: V) {
        #[cfg(feature = "cursor_nightly_experimental")]
        {
            self.internal_add_cursor(range, value);
        }

        #[cfg(not(feature = "cursor_nightly_experimental"))]
        {
            self.internal_add_baseline(range, value);
        }
    }

    #[cfg(any(
        test,
        feature = "test_util",
        not(feature = "cursor_nightly_experimental")
    ))]
    #[inline]
    fn internal_add2(&mut self, internal_range: &RangeInclusive<T>, value: V) {
        let (start, end) = internal_range.clone().into_inner();
        let end_value = EndValue { end, value };
        debug_assert!(start <= end_value.end); // real assert
        let was_there = self.btree_map.insert(start, end_value);
        debug_assert!(was_there.is_none()); // no range with the same start should be there
        self.delete_extra(internal_range);
        self.len += T::safe_len(internal_range);
    }

    /// Returns the number of elements in the set.
    ///
    /// The number is allowed to be very, very large.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::prelude::*;
    ///
    /// let mut a = RangeMapBlaze::new();
    /// assert_eq!(a.len(), 0u64);
    /// a.insert(1, "a");
    /// assert_eq!(a.len(), 1u64);
    ///
    /// let a = RangeMapBlaze::from_iter([
    ///     (-170_141_183_460_469_231_731_687_303_715_884_105_728_i128..=10, "a"),
    ///     (-10..=170_141_183_460_469_231_731_687_303_715_884_105_726, "a")]);
    /// assert_eq!(
    ///     a.len(),
    ///     UIntPlusOne::UInt(340282366920938463463374607431768211455)
    /// );
    /// ```
    #[must_use]
    pub const fn len(&self) -> <T as Integer>::SafeLen {
        self.len
    }

    /// Makes a new, empty [`RangeMapBlaze`].
    ///
    /// # Examples
    ///
    /// ```
    /// # #![allow(unused_mut)]
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut map = RangeMapBlaze::new();
    ///
    /// // entries can now be inserted into the empty map
    /// map.insert(1, "a");
    /// assert_eq!(map[1], "a");
    /// ```
    #[inline]
    #[must_use]
    pub fn new() -> Self {
        Self {
            btree_map: BTreeMap::new(),
            len: <T as Integer>::SafeLen::zero(),
        }
    }

    /// Extends the [`RangeMapBlaze`] with an iterator of `(range, value)` pairs without pre-merging.
    ///
    /// Unlike [`RangeMapBlaze::extend`], this method does **not** merge adjacent or overlapping ranges
    /// before inserting. Each `(range, value)` pair is added as-is, making it faster when the input
    /// is already well-structured or disjoint.
    ///
    /// This method has *right-to-left precedence*: later ranges in the iterator overwrite earlier ones.
    ///
    /// **See:** [Summary of Union and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods).
    ///
    /// # Examples
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    /// let mut a = RangeMapBlaze::from_iter([(1..=4, "a")]);
    /// a.extend_simple([(3..=5, "b"), (5..=5, "c")]);
    /// assert_eq!(a, RangeMapBlaze::from_iter([(1..=2, "a"), (3..=4, "b"), (5..=5, "c")]));
    ///
    /// let mut a = RangeMapBlaze::from_iter([(1..=4, "a")]);
    /// a.extend([(3..=5, "b"), (5..=5, "c")]);
    /// assert_eq!(a, RangeMapBlaze::from_iter([(1..=2, "a"), (3..=4, "b"), (5..=5, "c")]));
    ///
    /// let mut a = RangeMapBlaze::from_iter([(3..=5, "b"), (5..=5, "c")]);
    /// let mut b = RangeMapBlaze::from_iter([(1..=4, "a")]);
    /// a |= b;
    /// assert_eq!(a, RangeMapBlaze::from_iter([(1..=4, "a"), (5..=5, "c")]));
    /// ```
    pub fn extend_simple<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = (RangeInclusive<T>, V)>,
    {
        let iter = iter.into_iter();

        for (range, value) in iter {
            self.internal_add(range, value);
        }
    }

    /// Extends the [`RangeMapBlaze`] with the contents of an owned [`RangeMapBlaze`].
    ///
    /// This method follows standard *right-to-left precedence*: If the maps contain overlapping ranges,
    /// values from `other` will overwrite those in `self`.
    ///
    /// Compared to [`RangeMapBlaze::extend_with`], this method can be more efficient because it can
    /// consume the internal data structures of `other` directly, avoiding some cloning.
    ///
    /// **See:** [Summary of Union and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods).
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    /// let mut a = RangeMapBlaze::from_iter([(1..=4, "a")]);
    /// let mut b = RangeMapBlaze::from_iter([(3..=4, "b"), (5..=5, "c")]);
    /// a.extend_from(b);
    /// assert_eq!(a, RangeMapBlaze::from_iter([(1..=2, "a"), (3..=4, "b"), (5..=5, "c")]));
    /// ```
    #[inline]
    pub fn extend_from(&mut self, other: Self) {
        for (start, end_value) in other.btree_map {
            let range = start..=end_value.end;
            self.internal_add(range, end_value.value);
        }
    }

    /// Extends the [`RangeMapBlaze`] with the contents of a borrowed [`RangeMapBlaze`].
    ///
    /// This method follows standard *right-to-left precedence*: If the maps contain overlapping ranges,
    /// values from `other` will overwrite those in `self`.
    ///
    /// This method is simple and predictable but not the most efficient option when
    /// the right-hand side is larger. For better performance when ownership is available,
    /// consider using [`RangeMapBlaze::extend_from`] or the `|=` operator.
    ///
    /// **See:** [Summary of Union and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods).
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    /// let mut a = RangeMapBlaze::from_iter([(1..=4, "a")]);
    /// let mut b = RangeMapBlaze::from_iter([(3..=4, "b"), (5..=5, "c")]);
    /// a.extend_from(b);
    /// assert_eq!(a, RangeMapBlaze::from_iter([(1..=2, "a"), (3..=4, "b"), (5..=5, "c")]));
    /// ```
    #[inline]
    pub fn extend_with(&mut self, other: &Self) {
        for (start, end_value) in &other.btree_map {
            let range = *start..=end_value.end;
            self.internal_add(range, end_value.value.clone());
        }
    }

    /// Removes the first element from the set and returns it, if any.
    /// The first element is always the minimum element in the set.
    ///
    /// Often, internally, the value must be cloned.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut map = RangeMapBlaze::new();
    ///
    /// map.insert(1, "a");
    /// map.insert(2, "b");
    /// while let Some((key, _val)) = map.pop_first() {
    ///     assert!(map.iter().all(|(k, _v)| k > key));
    /// }
    /// assert!(map.is_empty());
    /// ```
    pub fn pop_first(&mut self) -> Option<(T, V)>
    where
        V: Clone,
    {
        let entry = self.btree_map.first_entry()?;
        // We must remove the entry because the key will change
        let (start, end_value) = entry.remove_entry();

        self.len -= T::SafeLen::one();
        if start == end_value.end {
            Some((start, end_value.value))
        } else {
            let value = end_value.value.clone();
            self.btree_map.insert(start.add_one(), end_value);
            Some((start, value))
        }
    }

    /// Removes the last value from the set and returns it, if any.
    /// The last value is always the maximum value in the set.
    ///
    /// Often, internally, the value must be cloned.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut map = RangeMapBlaze::new();
    /// map.insert(1, "a");
    /// map.insert(2, "b");
    /// while let Some((key, _val)) = map.pop_last() {
    ///      assert!(map.iter().all(|(k, _v)| k < key));
    /// }
    /// assert!(map.is_empty());
    /// ```
    pub fn pop_last(&mut self) -> Option<(T, V)> {
        let mut entry = self.btree_map.last_entry()?;
        let start = *entry.key();
        self.len -= T::SafeLen::one();
        let end = entry.get().end;
        if start == end {
            let (_, end_value) = entry.remove_entry();
            let value = end_value.value;
            Some((end, value))
        } else {
            let value = entry.get().value.clone();
            entry.get_mut().end.assign_sub_one();
            Some((end, value))
        }
    }

    /// An iterator that visits the ranges and values in the [`RangeMapBlaze`],
    ///
    /// Also see [`RangeMapBlaze::iter`] and [`RangeMapBlaze::into_range_values`].
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(30..=40, "c"), (15..=25, "b"), (10..=20, "a")]);
    /// let mut range_values = map.range_values();
    /// assert_eq!(range_values.next(), Some((10..=20, &"a")));
    /// assert_eq!(range_values.next(), Some((21..=25, &"b")));
    /// assert_eq!(range_values.next(), Some((30..=40, &"c")));
    /// assert_eq!(range_values.next(), None);
    /// ```
    ///
    /// Values returned by the iterator are returned in ascending order
    /// with right-to-left precedence.
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(10..=20, "a"), (15..=25, "b"), (30..=40, "c")]);
    /// let mut range_values = map.range_values();
    /// assert_eq!(range_values.next(), Some((10..=14, &"a")));
    /// assert_eq!(range_values.next(), Some((15..=25, &"b")));
    /// assert_eq!(range_values.next(), Some((30..=40, &"c")));
    /// assert_eq!(range_values.next(), None);
    /// ```
    pub fn range_values(&self) -> RangeValuesIter<'_, T, V> {
        RangeValuesIter::new(&self.btree_map)
    }

    /// Returns a [`RangeMapBlaze`] over the complete integer domain, mapping
    /// present ranges to `Some(value)` and gaps to `None`.
    ///
    /// The result covers [`Integer::min_value`] through [`Integer::max_value`].
    /// The `None` values are ordinary map values, so the resulting map's key
    /// domain is universal. Because map operators act on those key ranges, `!`
    /// on the filled map yields an empty set rather than negating the `Option`
    /// values.
    ///
    /// Materializing the result clones each value out of this map. To avoid both
    /// the intermediate collection and those clones, use
    /// [`SortedDisjointMap::fill_gaps`] on a map stream such as
    /// [`RangeMapBlaze::range_values`], which borrows the values instead.
    ///
    /// The [Ranges and gaps guide][crate::gaps] compares this materialized form
    /// with the lazy streaming form and its set counterpart.
    ///
    /// # Examples
    ///
    /// ```
    /// # use range_set_blaze::RangeMapBlaze;
    /// let map = RangeMapBlaze::from_iter([(1..=3, "red"), (7..=10, "blue")]);
    /// let filled = map.fill_gaps();
    /// assert_eq!(filled.get(i32::MIN), Some(&None));
    /// assert_eq!(filled.get(2), Some(&Some("red")));
    /// assert_eq!(filled.get(5), Some(&None));
    /// assert_eq!(filled.get(8), Some(&Some("blue")));
    /// assert_eq!(filled.get(i32::MAX), Some(&None));
    /// ```
    #[must_use]
    pub fn fill_gaps(&self) -> RangeMapBlaze<T, Option<V>> {
        self.range_values().fill_gaps().into_range_map_blaze()
    }

    /// An iterator that visits the ranges and values in the [`RangeMapBlaze`]. Double-ended.
    ///
    /// Also see [`RangeMapBlaze::iter`] and [`RangeMapBlaze::range_values`].
    ///
    /// # Examples
    ///
    /// ```
    /// extern crate alloc;
    /// use alloc::rc::Rc;
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(30..=40, "c"), (15..=25, "b"), (10..=20, "a")]);
    /// let mut range_values = map.into_range_values();
    /// assert_eq!(range_values.next(), Some((10..=20, Rc::new("a"))));
    /// assert_eq!(range_values.next(), Some((21..=25, Rc::new("b"))));
    /// assert_eq!(range_values.next(), Some((30..=40, Rc::new("c"))));
    /// assert_eq!(range_values.next(), None);
    /// ```
    ///
    /// Values returned by the iterator are returned in ascending order
    /// with right-to-left precedence.
    ///
    /// ```
    /// # extern crate alloc;
    /// use alloc::rc::Rc;
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(10..=20, "a"), (15..=25, "b"), (30..=40, "c")]);
    /// let mut range_values = map.into_range_values();
    /// assert_eq!(range_values.next(), Some((10..=14, Rc::new("a"))));
    /// assert_eq!(range_values.next(), Some((15..=25, Rc::new("b"))));
    /// assert_eq!(range_values.next(), Some((30..=40, Rc::new("c"))));
    /// assert_eq!(range_values.next(), None);
    /// ```
    pub fn into_range_values(self) -> IntoRangeValuesIter<T, V> {
        IntoRangeValuesIter::new(self.btree_map)
    }

    /// An iterator that visits the ranges in the [`RangeMapBlaze`],
    /// i.e., the integers as sorted & disjoint ranges.
    ///
    /// Also see [`RangeMapBlaze::iter`] and [`RangeMapBlaze::into_range_values`].
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(10..=20, "a"), (15..=25, "b"), (30..=40, "c")]);
    /// let mut ranges = map.ranges();
    /// assert_eq!(ranges.next(), Some(10..=25));
    /// assert_eq!(ranges.next(), Some(30..=40));
    /// assert_eq!(ranges.next(), None);
    /// ```
    ///
    /// Values returned by the iterator are returned in ascending order
    /// with right-to-left precedence.
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(30..=40, "c"), (15..=25, "b"), (10..=20, "a")]);
    /// let mut ranges = map.ranges();
    /// assert_eq!(ranges.next(), Some(10..=25));
    /// assert_eq!(ranges.next(), Some(30..=40));
    /// assert_eq!(ranges.next(), None);
    /// ```
    pub fn ranges(&self) -> MapRangesIter<'_, T, V> {
        MapRangesIter::new(self.btree_map.iter())
    }

    /// An iterator that visits the ranges in the [`RangeMapBlaze`],
    /// i.e., the integers as sorted & disjoint ranges.
    ///
    /// Also see [`RangeMapBlaze::iter`] and [`RangeMapBlaze::into_range_values`].
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(10..=20, "a"), (15..=25, "b"), (30..=40, "c")]);
    /// let mut ranges = map.into_ranges();
    /// assert_eq!(ranges.next(), Some(10..=25));
    /// assert_eq!(ranges.next(), Some(30..=40));
    /// assert_eq!(ranges.next(), None);
    /// ```
    ///
    /// Values returned by the iterator are returned in ascending order
    /// with right-to-left precedence.
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(30..=40, "c"), (15..=25, "b"), (10..=20, "a")]);
    /// let mut ranges = map.into_ranges();
    /// assert_eq!(ranges.next(), Some(10..=25));
    /// assert_eq!(ranges.next(), Some(30..=40));
    /// assert_eq!(ranges.next(), None);
    /// ```
    pub fn into_ranges(self) -> MapIntoRangesIter<T, V> {
        MapIntoRangesIter::new(self.btree_map.into_iter())
    }

    /// Returns the number of sorted & disjoint ranges in the set.
    ///
    /// # Example
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// // We put in three ranges, but they are not sorted & disjoint.
    /// let map = RangeMapBlaze::from_iter([(10..=20,"a"), (15..=25,"a"), (30..=40,"b")]);
    /// // After RangeMapBlaze sorts & 'disjoint's them, we see two ranges.
    /// assert_eq!(map.ranges_len(), 2);
    /// assert_eq!(map.to_string(), r#"(10..=25, "a"), (30..=40, "b")"#);
    /// ```
    #[must_use]
    pub fn ranges_len(&self) -> usize {
        self.btree_map.len()
    }

    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let map = RangeMapBlaze::from_iter([(10u16..=20, "a"), (15..=25, "b"), (30..=40, "c")]);
    /// let complement = map.complement_with(&"z");
    /// assert_eq!(complement.to_string(), r#"(0..=9, "z"), (26..=29, "z"), (41..=65535, "z")"#);
    /// ```
    #[must_use]
    pub fn complement_with(&self, value: &V) -> Self {
        self.ranges()
            .complement()
            .map(|r| (r, value.clone()))
            .collect()
    }

    // FUTURE BTreeSet some of these as 'const' but it uses unstable. When stable, add them here and elsewhere.

    /// Returns the number of sorted & disjoint ranges i
    /// n the set.
    ///
    /// # Example
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// // We put in four ranges, but they are not sorted & disjoint.
    /// let map = RangeMapBlaze::from_iter([(28..=35, "c"), (30..=40, "c"), (15..=25, "b"), (10..=20, "a")]);
    /// // After RangeMapBlaze sorts & 'disjoint's them, we see three ranges.
    /// assert_eq!(map.range_values_len(), 3);
    /// assert_eq!(map.to_string(), r#"(10..=20, "a"), (21..=25, "b"), (28..=40, "c")"#);
    /// ```
    #[must_use]
    pub fn range_values_len(&self) -> usize {
        self.btree_map.len()
    }

    /// Retains only the elements specified by the predicate.
    ///
    /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`.
    /// The elements are visited in ascending key order.
    ///
    /// Because if visits every element in every range, it is expensive compared to
    /// [`RangeMapBlaze::ranges_retain`].
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut map: RangeMapBlaze<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
    /// // Keep only the elements with even-numbered keys.
    /// map.retain(|&k, _| k % 2 == 0);
    /// assert!(map.into_iter().eq(vec![(0, 0), (2, 20), (4, 40), (6, 60)]));
    /// ```
    pub fn retain<F>(&mut self, f: F)
    where
        F: Fn(&T, &V) -> bool,
    {
        *self = self.iter().filter(|(k, v)| f(k, v)).collect();
    }

    /// Retains only the `(range, value)` pairs specified by the predicate.
    ///
    /// In other words, removes all `(range, value)` pairs for which `f(&range, &value)`
    /// returns `false`. The `(range, value)` pairs are visited in ascending range order.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    ///
    /// let mut map: RangeMapBlaze<i32, &str> = RangeMapBlaze::from_iter([(0..=3, "low"), (4..=7, "high")]);
    /// // Keep only the ranges with a specific value.
    /// map.ranges_retain(|range, &value| value == "low");
    /// assert_eq!(map, RangeMapBlaze::from_iter([(0..=3, "low")]));
    /// ```
    pub fn ranges_retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&RangeInclusive<T>, &V) -> bool,
    {
        self.btree_map.retain(|start, end_value| {
            let range = *start..=end_value.end;
            if f(&range, &end_value.value) {
                true
            } else {
                self.len -= T::safe_len(&range);
                false
            }
        });
    }
}

impl<T, V> IntoIterator for RangeMapBlaze<T, V>
where
    T: Integer,
    V: Eq + Clone,
{
    type Item = (T, V);
    type IntoIter = IntoIterMap<T, V>;

    /// Gets an iterator for moving out the [`RangeSetBlaze`]'s integer contents.
    /// Double-ended.
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeSetBlaze;
    ///
    /// let set = RangeSetBlaze::from_iter([1, 2, 3, 4]);
    ///
    /// let v: Vec<_> = set.into_iter().collect();
    /// assert_eq!(v, [1, 2, 3, 4]);
    ///
    /// let set = RangeSetBlaze::from_iter([1, 2, 3, 4]);
    /// let v: Vec<_> = set.into_iter().rev().collect();
    /// assert_eq!(v, [4, 3, 2, 1]);
    /// ```
    fn into_iter(self) -> IntoIterMap<T, V> {
        IntoIterMap::new(self.btree_map.into_iter())
    }
}

// Implementing `IntoIterator` for `&RangeMapBlaze<T, V>` because BTreeMap does.
impl<'a, T: Integer, V: Eq + Clone> IntoIterator for &'a RangeMapBlaze<T, V> {
    type IntoIter = IterMap<T, &'a V, RangeValuesIter<'a, T, V>>;
    type Item = (T, &'a V);

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

impl<T: Integer, V: Eq + Clone> BitOr<Self> for RangeMapBlaze<T, V> {
    /// Unions the contents of two [`RangeMapBlaze`]'s.
    ///
    /// This operator has *right precedence*: when overlapping ranges are present,
    /// values on the right-hand side take priority over those self.
    ///
    /// This method is optimized for three usage scenarios:
    /// when the left-hand side is much smaller, when the right-hand side is much smaller,
    /// and when both sides are of similar size.
    ///
    /// **Also See:** [Summary of Union and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods).
    ///
    /// # Examples
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    /// let a = RangeMapBlaze::from_iter([(1..=2, "a"), (5..=100, "a")]);
    /// let b = RangeMapBlaze::from_iter([(2..=6, "b")]);
    /// let union = a | b;  // Alternatively, '&a | &b', etc.
    /// assert_eq!(union, RangeMapBlaze::from_iter([(1..=1, "a"), (2..=6, "b"), (7..=100, "a")]));
    /// ```
    type Output = Self;
    fn bitor(self, other: Self) -> Self {
        let b_len = other.ranges_len();
        if b_len == 0 {
            return self;
        }
        let a_len = self.ranges_len();
        if a_len == 0 {
            return other;
        }
        if much_greater_than(a_len, b_len) {
            return small_b_over_a(self, other);
        }
        if much_greater_than(b_len, a_len) {
            return small_a_under_b(self, other);
        }
        // Sizes are comparable, use the iterator union
        (self.into_range_values() | other.into_range_values()).into_range_map_blaze()
    }
}

impl<T: Integer, V: Eq + Clone> BitOr<&Self> for RangeMapBlaze<T, V> {
    /// Unions the contents of two [`RangeMapBlaze`]'s.
    ///
    /// This operator has *right precedence*: when overlapping ranges are present,
    /// values on the right-hand side take priority over those self.
    ///
    /// This method is optimized for three usage scenarios:
    /// when the left-hand side is much smaller, when the right-hand side is much smaller,
    /// and when both sides are of similar size.
    ///
    /// **Also See:** [Summary of Union and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods).
    ///
    /// # Examples
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    /// let a = RangeMapBlaze::from_iter([(1..=2, "a"), (5..=100, "a")]);
    /// let b = RangeMapBlaze::from_iter([(2..=6, "b")]);
    /// let union = a | &b; // Alternatively, 'a | b', etc.
    /// assert_eq!(union, RangeMapBlaze::from_iter([(1..=1, "a"), (2..=6, "b"), (7..=100, "a")]));
    /// ```
    type Output = Self;
    fn bitor(self, other: &Self) -> Self {
        let b_len = other.ranges_len();
        if b_len == 0 {
            return self;
        }
        let a_len = self.ranges_len();
        if a_len == 0 {
            return other.clone();
        }
        if much_greater_than(a_len, b_len) {
            return small_b_over_a(self, other.clone());
        }
        if much_greater_than(b_len, a_len) {
            return small_a_under_b(self, other.clone());
        }

        // Sizes are comparable, use the iterator union
        (self.range_values() | other.range_values()).into_range_map_blaze()
    }
}

impl<T: Integer, V: Eq + Clone> BitOr<RangeMapBlaze<T, V>> for &RangeMapBlaze<T, V> {
    type Output = RangeMapBlaze<T, V>;
    /// Unions the contents of two [`RangeMapBlaze`]'s.
    ///
    /// This operator has *right precedence*: when overlapping ranges are present,
    /// values on the right-hand side take priority over those self.
    ///
    /// This method is optimized for three usage scenarios:
    /// when the left-hand side is much smaller, when the right-hand side is much smaller,
    /// and when both sides are of similar size.
    ///
    /// **Also See:** [Summary of Union and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods).
    ///
    /// # Examples
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    /// let a = RangeMapBlaze::from_iter([(1..=2, "a"), (5..=100, "a")]);
    /// let b = RangeMapBlaze::from_iter([(2..=6, "b")]);
    /// let union = &a | b;  // Alternatively, 'a | b', etc.
    /// assert_eq!(union, RangeMapBlaze::from_iter([(1..=1, "a"), (2..=6, "b"), (7..=100, "a")]));
    /// ```
    fn bitor(self, other: RangeMapBlaze<T, V>) -> RangeMapBlaze<T, V> {
        let a_len = self.ranges_len();
        if a_len == 0 {
            return other;
        }
        let b_len = other.ranges_len();
        if b_len == 0 {
            return self.clone();
        }
        if much_greater_than(b_len, a_len) {
            return small_a_under_b(self.clone(), other);
        }
        if much_greater_than(a_len, b_len) {
            return small_b_over_a(self.clone(), other);
        }
        // Sizes are comparable, use the iterator union
        (self.range_values() | other.range_values()).into_range_map_blaze()
    }
}

impl<T: Integer, V: Eq + Clone> BitOr<&RangeMapBlaze<T, V>> for &RangeMapBlaze<T, V> {
    type Output = RangeMapBlaze<T, V>;
    /// Unions the contents of two [`RangeMapBlaze`]'s.
    ///
    /// This operator has *right precedence*: when overlapping ranges are present,
    /// values on the right-hand side take priority over those self.
    ///
    /// This method is optimized for three usage scenarios:
    /// when the left-hand side is much smaller, when the right-hand side is much smaller,
    /// and when both sides are of similar size.
    ///
    /// **Also See:** [Summary of Union and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods).
    ///
    /// # Examples
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    /// let a = RangeMapBlaze::from_iter([(1..=2, "a"), (5..=100, "a")]);
    /// let b = RangeMapBlaze::from_iter([(2..=6, "b")]);
    /// let union = &a | &b; // Alternatively, 'a | b', etc.
    /// assert_eq!(union, RangeMapBlaze::from_iter([(1..=1, "a"), (2..=6, "b"), (7..=100, "a")]));
    /// ```
    fn bitor(self, other: &RangeMapBlaze<T, V>) -> RangeMapBlaze<T, V> {
        let a_len = self.ranges_len();
        if a_len == 0 {
            return other.clone();
        }
        let b_len = other.ranges_len();
        if b_len == 0 {
            return self.clone();
        }
        if much_greater_than(a_len, b_len) {
            return small_b_over_a(self.clone(), other.clone());
        }
        if much_greater_than(b_len, a_len) {
            return small_a_under_b(self.clone(), other.clone());
        }
        // Sizes are comparable, use the iterator union
        (self.range_values() | other.range_values()).into_range_map_blaze()
    }
}

map_op!(
     BitAnd bitand,
    RangeMapBlaze<T, V>,          // RHS concrete type

    /// Intersects the contents of two [`RangeMapBlaze`]'s.
    ///
    /// Either, neither, or both inputs may be borrowed.
    ///
    /// # Examples
    /// ```
    /// use range_set_blaze::prelude::*;
    ///
    /// let a = RangeMapBlaze::from_iter([(1..=2, "a"), (5..=100, "a")]);
    /// let b = RangeMapBlaze::from_iter([(2..=6, "b")]);
    /// let result = &a & &b; // Alternatively, 'a & b'.
    /// assert_eq!(result.to_string(), r#"(2..=2, "b"), (5..=6, "b")"#);
    /// ```
    "placeholder",

    // owned ∩ owned
    |a, b| {
        b.into_range_values()
         .map_and_set_intersection(a.into_ranges())
         .into_range_map_blaze()
    },

    // owned ∩ &borrowed
    |a, &b| {
        b.range_values()
         .map_and_set_intersection(a.into_ranges())
         .into_range_map_blaze()
    },

    // &borrowed ∩ owned
    |&a, b| {
        b.into_range_values()
         .map_and_set_intersection(a.ranges())
         .into_range_map_blaze()
    },

    // &borrowed ∩ &borrowed
    |&a, &b| {
        b.range_values()
         .map_and_set_intersection(a.ranges())
         .into_range_map_blaze()
    },
);

map_op!(
     BitAnd bitand,
    RangeSetBlaze<T>,          // RHS concrete type

/// Find the intersection between a [`RangeMapBlaze`] and a [`RangeSetBlaze`]. The result is a new [`RangeMapBlaze`].
///
/// Either, neither, or both inputs may be borrowed.
///
/// # Examples
/// ```
/// use range_set_blaze::prelude::*;
///
/// let a = RangeMapBlaze::from_iter([(1..=100, "a")]);
/// let b = RangeSetBlaze::from_iter([2..=6]);
/// let result = &a & &b; // Alternatively, 'a & b'.
/// assert_eq!(result.to_string(), r#"(2..=6, "a")"#);
/// ```
    "placeholder",

    // owned ∩ owned
    |a, b| {
        a.into_range_values()
         .map_and_set_intersection(b.into_ranges())
         .into_range_map_blaze()
    },

    // owned ∩ &borrowed
    |a, &b| {
        a.into_range_values()
         .map_and_set_intersection(b.ranges())
         .into_range_map_blaze()
    },

    // &borrowed ∩ owned
    |&a, b| {
        a.range_values()
         .map_and_set_intersection(b.into_ranges())
         .into_range_map_blaze()
    },

    // &borrowed ∩ &borrowed
    |&a, &b| {
        a.range_values()
         .map_and_set_intersection(b.ranges())
         .into_range_map_blaze()
    },
);

map_op!(
    BitXor bitxor,                           // trait + method name
    RangeMapBlaze<T, V>,                     // RHS concrete type

/// Symmetric difference the contents of two [`RangeMapBlaze`]'s.
///
/// Either, neither, or both inputs may be borrowed.
///
/// # Examples
/// ```
/// use range_set_blaze::prelude::*;
///
/// let a = RangeMapBlaze::from_iter([(1..=2, "a"), (5..=100, "a")]);
/// let b = RangeMapBlaze::from_iter([(2..=6, "b")]);
/// let result = &a ^ &b; // Alternatively, 'a ^ b'.
/// assert_eq!(result.to_string(), r#"(1..=1, "a"), (3..=4, "b"), (7..=100, "a")"#);
/// ```
    "placeholder",

    // ── owned ^ owned ────────────────────────────────────────────
    |a, b| {
        SymDiffIterMap::new2(
            a.into_range_values(),
            b.into_range_values(),
        )
        .into_range_map_blaze()
    },

    // ── owned ^ &borrowed ────────────────────────────────────────
    |a, &b| {
        SymDiffIterMap::new2(
            a.range_values(),
            b.range_values(),
        )
        .into_range_map_blaze()
    },

    // ── &borrowed ^ owned ────────────────────────────────────────
    |&a, b| {
        SymDiffIterMap::new2(
            a.range_values(),
            b.range_values(),
        )
        .into_range_map_blaze()
    },

    // ── &borrowed ^ &borrowed ────────────────────────────────────
    |&a, &b| {
        SymDiffIterMap::new2(
            a.range_values(),
            b.range_values(),
        )
        .into_range_map_blaze()
    },
);

map_op!(
    Sub sub,                                 // trait + method name
    RangeMapBlaze<T, V>,         // RHS concrete type

    /// **Difference** of two [`RangeMapBlaze`] values (`a - b`).
    ///
    /// Either, neither, or both inputs may be borrowed.
    ///
    /// # Example
    /// ```
    /// use range_set_blaze::prelude::*;
    ///
    /// let a = RangeMapBlaze::from_iter([(1..=2, "a"), (5..=100, "a")]);
    /// let b = RangeMapBlaze::from_iter([(2..=6, "b")]);
    /// let result = &a - &b;                // or `a - b`
    /// assert_eq!(result.to_string(),
    ///            r#"(1..=1, "a"), (7..=100, "a")"#);
    /// ```
    "placeholder",

    // ── owned − owned ────────────────────────────────────────────
    |a, b| {
        a.into_range_values()
         .map_and_set_difference(b.ranges())
         .into_range_map_blaze()
    },

    // ── owned − &borrowed ────────────────────────────────────────
    |a, &b| {
        a.into_range_values()
         .map_and_set_difference(b.ranges())
         .into_range_map_blaze()
    },

    // ── &borrowed − owned ────────────────────────────────────────
    |&a, b| {
        a.range_values()
         .map_and_set_difference(b.into_ranges())
         .into_range_map_blaze()
    },

    // ── &borrowed − &borrowed ────────────────────────────────────
    |&a, &b| {
        a.range_values()
         .map_and_set_difference(b.ranges())
         .into_range_map_blaze()
    },
);

map_op!(
    Sub sub,                                 // trait + method name
    RangeSetBlaze<T>,         // RHS concrete type

/// Find the difference between a [`RangeMapBlaze`] and a [`RangeSetBlaze`]. The result is a new [`RangeMapBlaze`].
///
/// Either, neither, or both inputs may be borrowed.
///
/// # Examples
/// ```
/// use range_set_blaze::prelude::*;
///
/// let a = RangeMapBlaze::from_iter([(1..=100, "a")]);
/// let b = RangeSetBlaze::from_iter([2..=6]);
/// let result = &a - &b; // Alternatively, 'a - b'.
/// assert_eq!(result.to_string(), r#"(1..=1, "a"), (7..=100, "a")"#);
/// ```
    "placeholder",

    // ── owned − owned ────────────────────────────────────────────
    |a, b| {
        a.into_range_values()
         .map_and_set_difference(b.ranges())
         .into_range_map_blaze()
    },

    // ── owned − &borrowed ────────────────────────────────────────
    |a, &b| {
        a.into_range_values()
         .map_and_set_difference(b.ranges())
         .into_range_map_blaze()
    },

    // ── &borrowed − owned ────────────────────────────────────────
    |&a, b| {
        a.range_values()
         .map_and_set_difference(b.into_ranges())
         .into_range_map_blaze()
    },

    // ── &borrowed − &borrowed ────────────────────────────────────
    |&a, &b| {
        a.range_values()
         .map_and_set_difference(b.ranges())
         .into_range_map_blaze()
    },
);

map_unary_op!(
    Not not,                                   // trait + method
    RangeSetBlaze<T>,                          // output type

    /// Takes the complement of a [`RangeMapBlaze`].
    ///
    /// Produces a [`RangeSetBlaze`] containing all integers *not* present
    /// in the map’s key ranges.
    ///
    /// # Example
    /// ```
    /// use range_set_blaze::prelude::*;
    /// let map =
    ///     RangeMapBlaze::from_iter([(10u8..=20, "a"), (15..=25, "b"),
    ///                               (30..=40, "c")]);
    /// let complement = !&map;                // or `!map`
    /// assert_eq!(complement.to_string(), "0..=9, 26..=29, 41..=255");
    /// ```
    "placeholder",

    // body for &map
    |&m| {
        m.ranges()
         .complement()
         .into_range_set_blaze()
    }
);

impl<T, V> Extend<(T, V)> for RangeMapBlaze<T, V>
where
    T: Integer,
    V: Eq + Clone,
{
    /// Extends the [`RangeMapBlaze`] with the contents of an iterator of integer-value pairs.
    ///
    /// This method has *right-to-left precedence*: later values in the iterator take priority
    /// over earlier ones, matching the behavior of standard `BTreeMap::extend`.
    ///
    /// Each integer is treated as a singleton range. Adjacent integers with the same value
    /// are merged before insertion. For alternatives that skip merging or accept full ranges,
    /// see [`RangeMapBlaze::extend_simple`] and [`RangeMapBlaze::extend`].
    ///
    /// **See:** [Summary of Union and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods).
    ///
    /// # Examples
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    /// let mut a = RangeMapBlaze::from_iter([(3, "a"), (4, "e"), (5, "f"), (5, "g")]);
    /// a.extend([(1..=4, "b")]);
    /// assert_eq!(a, RangeMapBlaze::from_iter([(1..=4, "b"), (5..=5, "g")]));
    ///
    /// let mut a = RangeMapBlaze::from_iter([(3, "a"), (4, "e"), (5, "f"), (5, "g")]);
    /// let mut b = RangeMapBlaze::from_iter([(1..=4, "b")]);
    /// a |= b;
    /// assert_eq!(a, RangeMapBlaze::from_iter([(1..=4, "b"), (5..=5, "g")]));
    /// ```
    #[inline]
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = (T, V)>,
    {
        let iter = iter.into_iter();

        // We gather adjacent values into ranges via UnsortedPriorityMap, but ignore the priority.
        for priority in UnsortedPriorityMap::new(iter.map(|(r, v)| (r..=r, Rc::new(v)))) {
            let (range, value) = priority.into_range_value();
            let value: V = Rc::try_unwrap(value).unwrap_or_else(|_| unreachable!());
            self.internal_add(range, value);
        }
    }
}

impl<T, V> Extend<(RangeInclusive<T>, V)> for RangeMapBlaze<T, V>
where
    T: Integer,
    V: Eq + Clone,
{
    /// Extends the [`RangeMapBlaze`] with the contents of an iterator of range-value pairs.
    ///
    /// This method has *right-to-left precedence* — like `BTreeMap` and all other
    /// `RangeMapBlaze` methods.
    ///
    /// It first merges any adjacent or overlapping ranges with the same value, then adds them one by one.
    /// For alternatives that skip merging or that accept integer-value pairs, see
    /// [`RangeMapBlaze::extend_simple`] and the `(integer, value)` overload.
    ///
    /// **See:** [Summary of Union and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods).
    /// # Examples
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    /// let mut a = RangeMapBlaze::from_iter([(1..=4, "a")]);
    /// a.extend([(3..=5, "b"), (5..=5, "c")]);
    /// assert_eq!(a, RangeMapBlaze::from_iter([(1..=2, "a"), (3..=4, "b"), (5..=5, "c")]));
    ///
    /// // `extend_simple` is a more efficient for the case where the ranges a likely disjoint.
    /// let mut a = RangeMapBlaze::from_iter([(1..=4, "a")]);
    /// a.extend_simple([(3..=5, "b"), (5..=5, "c")]);
    /// assert_eq!(a, RangeMapBlaze::from_iter([(1..=2, "a"), (3..=4, "b"), (5..=5, "c")]));
    ///
    /// let mut a = RangeMapBlaze::from_iter([(1..=4, "a")]);
    /// let mut b = RangeMapBlaze::from_iter([(3..=5, "b"), (5..=5, "c")]);
    /// a |= b;
    /// assert_eq!(a, RangeMapBlaze::from_iter([(1..=2, "a"), (3..=4, "b"), (5..=5, "c")]));
    /// ```
    #[inline]
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = (RangeInclusive<T>, V)>,
    {
        let iter = iter.into_iter();

        // We gather adjacent values into ranges via UnsortedPriorityMap, but ignore the priority.
        for priority in UnsortedPriorityMap::new(iter.map(|(r, v)| (r, Rc::new(v)))) {
            let (range, value) = priority.into_range_value();
            let value = Rc::try_unwrap(value).unwrap_or_else(|_| unreachable!());
            self.internal_add(range, value);
        }
    }
}

impl<T, V, const N: usize> From<[(T, V); N]> for RangeMapBlaze<T, V>
where
    T: Integer,
    V: Eq + Clone,
{
    /// For compatibility with [`BTreeMap`] you may create a [`RangeSetBlaze`] from an array of integers.
    ///
    /// *For more about constructors and performance, see [`RangeSetBlaze` Constructors](struct.RangeSetBlaze.html#rangesetblaze-constructors).*
    ///
    /// [`BTreeMap`]: alloc::collections::BTreeMap
    ///
    /// # Examples
    ///
    /// ```
    /// use range_set_blaze::RangeSetBlaze;
    ///
    /// let a0 = RangeSetBlaze::from([3, 2, 1, 100, 1]);
    /// let a1: RangeSetBlaze<i32> = [3, 2, 1, 100, 1].into();
    /// assert!(a0 == a1 && a0.to_string() == "1..=3, 100..=100")
    /// ```
    fn from(arr: [(T, V); N]) -> Self {
        arr.into_iter().collect()
    }
}

// implement Index trait
impl<T: Integer, V: Eq + Clone> Index<T> for RangeMapBlaze<T, V> {
    type Output = V;

    /// Returns a reference to the value corresponding to the supplied key.
    ///
    /// # Panics
    ///
    /// Panics if the key is not present in the `BTreeMap`.
    #[inline]
    #[allow(clippy::manual_assert)] // We use "if...panic!" for coverage auditing.
    fn index(&self, index: T) -> &Self::Output {
        self.get(index).unwrap_or_else(|| {
            panic!("no entry found for key");
        })
    }
}

// LATER define value_per_range and into_value_per_range

impl<T, V> PartialOrd for RangeMapBlaze<T, V>
where
    T: Integer,
    V: Eq + Clone + Ord,
{
    /// We define a partial ordering on `RangeMapBlaze`. Following the convention of
    /// [`BTreeMap`], the ordering is lexicographic, *not* by subset/superset.
    ///
    /// [`BTreeMap`]: alloc::collections::BTreeMap
    ///
    /// # Examples
    /// ```
    /// use range_set_blaze::prelude::*;
    ///
    /// let a = RangeMapBlaze::from_iter([(1..=3, "a"), (5..=100, "a")]);
    /// let b = RangeMapBlaze::from_iter([(2..=2, "b")] );
    /// assert!(a < b); // Lexicographic comparison
    /// // More lexicographic comparisons
    /// assert!(a <= b);
    /// assert!(b > a);
    /// assert!(b >= a);
    /// assert!(a != b);
    /// assert!(a == a);
    /// use core::cmp::Ordering;
    /// assert_eq!(a.cmp(&b), Ordering::Less);
    ///
    /// // Floats aren't comparable, but we can convert them to comparable bits.
    /// let a = RangeMapBlaze::from_iter([(2..=3, 1.0f32.to_bits()), (5..=100, 2.0f32.to_bits())]);
    /// let b = RangeMapBlaze::from_iter([(2..=2, f32::NAN.to_bits())] );
    /// assert_eq!(a.partial_cmp(&b), Some(Ordering::Less));
    /// ```
    #[inline]
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<T, V> Ord for RangeMapBlaze<T, V>
where
    T: Integer,
    V: Eq + Clone + Ord,
{
    /// We define an ordering on `RangeMapBlaze`. Following the convention of
    /// [`BTreeMap`], the ordering is lexicographic, *not* by subset/superset.
    ///
    /// [`BTreeMap`]: alloc::collections::BTreeMap
    ///
    /// # Examples
    /// ```
    /// use range_set_blaze::prelude::*;
    ///
    /// let a = RangeMapBlaze::from_iter([(1..=3, "a"), (5..=100, "a")]);
    /// let b = RangeMapBlaze::from_iter([(2..=2, "b")] );
    /// assert!(a < b); // Lexicographic comparison
    /// // More lexicographic comparisons
    /// assert!(a <= b);
    /// assert!(b > a);
    /// assert!(b >= a);
    /// assert!(a != b);
    /// assert!(a == a);
    /// use core::cmp::Ordering;
    /// assert_eq!(a.cmp(&b), Ordering::Less);
    ///
    /// // Floats aren't comparable, but we can convert them to comparable bits.
    /// let a = RangeMapBlaze::from_iter([(2..=3, 1.0f32.to_bits()), (5..=100, 2.0f32.to_bits())]);
    /// let b = RangeMapBlaze::from_iter([(2..=2, f32::NAN.to_bits())] );
    /// assert_eq!(a.partial_cmp(&b), Some(Ordering::Less));
    /// ```
    #[inline]
    fn cmp(&self, other: &Self) -> Ordering {
        // fast by ranges:
        let mut a = self.range_values();
        let mut b = other.range_values();
        let mut a_rx = a.next();
        let mut b_rx = b.next();
        loop {
            // compare Some/None
            match (a_rx, &b_rx) {
                (Some(_), None) => return Ordering::Greater,
                (None, Some(_)) => return Ordering::Less,
                (None, None) => return Ordering::Equal,
                (Some((a_r, a_v)), Some((b_r, b_v))) => {
                    // if tie, compare starts
                    match a_r.start().cmp(b_r.start()) {
                        Ordering::Greater => return Ordering::Greater,
                        Ordering::Less => return Ordering::Less,
                        Ordering::Equal => { /* keep going */ }
                    }

                    // if tie, compare values
                    match a_v.cmp(b_v) {
                        Ordering::Less => return Ordering::Less,
                        Ordering::Greater => return Ordering::Greater,
                        Ordering::Equal => { /* keep going */ }
                    }

                    // if tie, compare ends
                    match a_r.end().cmp(b_r.end()) {
                        Ordering::Less => {
                            a_rx = a.next();
                            b_rx = Some(((*a_r.end()).add_one()..=*b_r.end(), b_v));
                        }
                        Ordering::Greater => {
                            a_rx = Some(((*b_r.end()).add_one()..=*a_r.end(), a_v));
                            b_rx = b.next();
                        }
                        Ordering::Equal => {
                            a_rx = a.next();
                            b_rx = b.next();
                        }
                    }
                }
            }
        }
    }
}

impl<T: Integer, V: Eq + Clone> Eq for RangeMapBlaze<T, V> {}

impl<T: Integer, V: Eq + Clone> BitOrAssign<&Self> for RangeMapBlaze<T, V> {
    /// Adds the contents of another [`RangeMapBlaze`] to this one.
    ///
    /// This operator has *right precedence*: when overlapping ranges are present,
    /// values on the right-hand side take priority over those self.
    ///
    /// To get *left precedence*, swap the operands.
    ///
    /// This method is optimized for three usage scenarios:
    /// when the left-hand side is much smaller, when the right-hand side is much smaller,
    /// and when both sides are of similar size
    ///
    /// **Also See:** [Summary of Union and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods).
    ///
    /// # Examples
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    /// let mut a = RangeMapBlaze::from_iter([(3, "a"), (4, "e"), (5, "f"), (5, "g")]);
    /// let mut b = RangeMapBlaze::from_iter([(1..=4, "b")]);
    /// a |= &b;
    /// assert_eq!(a, RangeMapBlaze::from_iter([(1..=4, "b"), (5..=5, "g")]));
    /// ```
    fn bitor_assign(&mut self, other: &Self) {
        let original_self = mem::take(self); // Take ownership of self
        *self = original_self | other; // Use the union operator to combine
    }
}

impl<T: Integer, V: Eq + Clone> BitOrAssign<Self> for RangeMapBlaze<T, V> {
    /// Adds the contents of another [`RangeMapBlaze`] to this one.
    ///
    /// This operator has *right precedence*: when overlapping ranges are present,
    /// values on the right-hand side take priority over those self.
    /// To get *left precedence*, swap the operands.
    ///
    /// This method is optimized for three usage scenarios:
    /// when the left-hand side is much smaller, when the right-hand side is much smaller,
    /// and when both sides are of similar size
    ///
    /// **Also See:** [Summary of Union and Extend-like Methods](#rangemapblaze-union--and-extend-like-methods).
    ///
    /// # Examples
    /// ```
    /// use range_set_blaze::RangeMapBlaze;
    /// let mut a = RangeMapBlaze::from_iter([(3, "a"), (4, "e"), (5, "f"), (5, "g")]);
    /// let mut b = RangeMapBlaze::from_iter([(1..=4, "b")]);
    /// a |= &b;
    /// assert_eq!(a, RangeMapBlaze::from_iter([(1..=4, "b"), (5..=5, "g")]));
    /// ```
    fn bitor_assign(&mut self, other: Self) {
        *self = mem::take(self) | other;
    }
}

#[inline]
fn much_greater_than(a_len: usize, b_len: usize) -> bool {
    let a_len_log2_plus_one: usize = a_len
        .checked_ilog2()
        .map_or(0, |log| log.try_into().expect("log2 fits usize"))
        + 1;
    b_len * a_len_log2_plus_one < STREAM_OVERHEAD * a_len + b_len
}

#[inline]
fn small_b_over_a<T: Integer, V: Eq + Clone>(
    mut a: RangeMapBlaze<T, V>,
    b: RangeMapBlaze<T, V>,
) -> RangeMapBlaze<T, V> {
    debug_assert!(much_greater_than(a.ranges_len(), b.ranges_len()));
    for (start, end_value) in b.btree_map {
        a.internal_add(start..=(end_value.end), end_value.value);
    }
    a
}

#[inline]
fn small_a_under_b<T: Integer, V: Eq + Clone>(
    a: RangeMapBlaze<T, V>,
    mut b: RangeMapBlaze<T, V>,
) -> RangeMapBlaze<T, V> {
    debug_assert!(much_greater_than(b.ranges_len(), a.ranges_len()));
    let difference = a - &b;
    b.extend_simple(
        difference
            .btree_map
            .into_iter()
            .map(|(start, v)| (start..=v.end, v.value)),
    );
    b
}