fresh/model/

marker_tree.rs

use std::cell::{RefCell, RefMut};
use std::cmp::{max, Ordering};
use std::collections::HashMap;
use std::mem;
use std::rc::{Rc, Weak};

/// Use a simple u64 for marker IDs
pub type MarkerId = u64;

// ---
// 1. Core Data Structures and Pointers
// ---

#[derive(Debug, Clone, PartialEq)]
pub struct Interval {
    pub start: u64,
    pub end: u64,
}

/// Type of marker - either a position marker or a line anchor
#[derive(Debug, Clone, PartialEq)]
pub enum MarkerType {
    /// Regular position marker (for overlays, cursors, etc.)
    Position,
    /// Line anchor with estimated/exact line number
    LineAnchor {
        estimated_line: usize,
        confidence: AnchorConfidence,
    },
}

/// Confidence level for line anchor estimates
#[derive(Debug, Clone, PartialEq)]
pub enum AnchorConfidence {
    /// Exact line number (scanned from known position)
    Exact,
    /// Estimated from average line length
    Estimated,
    /// Relative to another anchor
    Relative(MarkerId),
}

#[derive(Debug, Clone, PartialEq)]
pub struct Marker {
    pub id: MarkerId,
    pub interval: Interval,
    pub marker_type: MarkerType,
    /// Insertion gravity at the marker's exact position.
    /// - `true` (right gravity, default): text inserted exactly at the marker
    ///   position pushes the marker forward (the marker moves after the text).
    /// - `false` (left gravity): text inserted exactly at the marker position
    ///   leaves it in place (the marker stays before the text).
    ///
    /// Only matters for insertions landing on the marker's own position;
    /// insertions strictly before always shift it, insertions strictly after
    /// never do. Used to keep search-match highlights from growing when text
    /// is typed immediately after a match (issue #2053).
    pub right_gravity: bool,
}

/// A Strong pointer to a tree node (child/sibling/map reference)
type NodePtr = Option<Rc<RefCell<Node>>>;
/// A Weak pointer to a tree node (parent reference, doesn't count for ownership)
type WeakNodePtr = Weak<RefCell<Node>>;

/// The internal tree node
#[derive(Debug)]
struct Node {
    pub marker: Marker,

    /// AVL: Height of this node's subtree
    pub height: i32,
    /// Augmentation: The max 'end' value in this node's subtree
    pub max_end: u64,
    /// VSCode-style: The delta to be applied to this node and its children
    pub lazy_delta: i64,

    pub parent: WeakNodePtr,
    pub left: NodePtr,
    pub right: NodePtr,
}

/// The main Interval Tree structure
#[derive(Debug, Default)]
pub struct IntervalTree {
    root: NodePtr,
    next_id: u64,
    /// ID-to-Node map for O(1) lookups
    marker_map: HashMap<MarkerId, Rc<RefCell<Node>>>,
}

// ---
// 2. Node Helpers (Pushing Deltas, Stats, Heights)
// ---

impl Node {
    fn new(marker: Marker, parent: WeakNodePtr) -> Rc<RefCell<Self>> {
        // Fix E0382: Calculate max_end before moving ownership of `marker` into the struct.
        let max_end_val = marker.interval.end;

        Rc::new(RefCell::new(Node {
            marker,
            height: 1,
            max_end: max_end_val,
            lazy_delta: 0,
            parent,
            left: None,
            right: None,
        }))
    }

    /// Gets the height of a node (0 for None).
    fn height(node: &NodePtr) -> i32 {
        node.as_ref().map_or(0, |n| n.borrow().height)
    }

    /// Calculates the balance factor of a node (height(left) - height(right)).
    fn balance_factor(node: &Rc<RefCell<Self>>) -> i32 {
        let n = node.borrow();
        Self::height(&n.left) - Self::height(&n.right)
    }

    /// Pushes this node's lazy_delta down to its immediate children.
    fn push_delta(node_rc: &Rc<RefCell<Self>>) {
        let mut node = node_rc.borrow_mut();
        if node.lazy_delta == 0 {
            return;
        }

        let delta = node.lazy_delta;

        // Apply delta to self (start and end)
        node.marker.interval.start = (node.marker.interval.start as i64 + delta) as u64;
        node.marker.interval.end = (node.marker.interval.end as i64 + delta) as u64;

        // Apply delta to children (only update their lazy_delta fields)
        if let Some(ref left) = node.left {
            left.borrow_mut().lazy_delta += delta;
        }
        if let Some(ref right) = node.right {
            right.borrow_mut().lazy_delta += delta;
        }

        node.lazy_delta = 0;

        // The max_end needs to be updated after the push
        let max_l = node.left.as_ref().map_or(0, |l| l.borrow().max_end);
        let max_r = node.right.as_ref().map_or(0, |r| r.borrow().max_end);
        node.max_end = max(node.marker.interval.end, max(max_l, max_r));
    }

    /// Updates a node's height and max_end based on its children.
    fn update_stats(node: &Rc<RefCell<Self>>) {
        let mut n = node.borrow_mut();
        let height_l = Self::height(&n.left);
        let height_r = Self::height(&n.right);

        n.height = 1 + max(height_l, height_r);

        let max_l = n.left.as_ref().map_or(0, |l| l.borrow().max_end);
        let max_r = n.right.as_ref().map_or(0, |r| r.borrow().max_end);
        n.max_end = max(n.marker.interval.end, max(max_l, max_r));
    }
}

// ---
// 3. Main Public API
// ---

impl IntervalTree {
    pub fn new() -> Self {
        Self::default()
    }

    /// Inserts a new marker interval. Performance: O(log n)
    pub fn insert(&mut self, start: u64, end: u64) -> MarkerId {
        self.insert_with_type(start, end, MarkerType::Position)
    }

    /// Inserts a new left-gravity marker interval: text inserted exactly at the
    /// marker's position leaves it in place rather than pushing it forward.
    /// Performance: O(log n)
    pub fn insert_left_gravity(&mut self, start: u64, end: u64) -> MarkerId {
        self.insert_full(start, end, MarkerType::Position, false)
    }

    /// Insert a marker with a specific ID and type (for set_position).
    /// The caller must ensure the ID is not already in use.
    fn insert_with_id(
        &mut self,
        id: MarkerId,
        start: u64,
        end: u64,
        marker_type: MarkerType,
        right_gravity: bool,
    ) {
        debug_assert!(
            id < self.next_id,
            "insert_with_id: id {} must be < next_id {}",
            id,
            self.next_id
        );
        debug_assert!(
            !self.marker_map.contains_key(&id),
            "insert_with_id: id {} already in use",
            id
        );
        let marker = Marker {
            id,
            interval: Interval { start, end },
            marker_type,
            right_gravity,
        };

        let new_node = Node::new(marker.clone(), Weak::new());
        self.root = Self::insert_recursive(self.root.take(), new_node.clone());
        self.marker_map.insert(id, new_node);
    }

    /// Insert a marker with a specific type (right gravity).
    pub fn insert_with_type(&mut self, start: u64, end: u64, marker_type: MarkerType) -> MarkerId {
        self.insert_full(start, end, marker_type, true)
    }

    /// Insert a marker with a specific type and gravity.
    fn insert_full(
        &mut self,
        start: u64,
        end: u64,
        marker_type: MarkerType,
        right_gravity: bool,
    ) -> MarkerId {
        let id = self.next_id;
        self.next_id += 1;
        let marker = Marker {
            id,
            interval: Interval { start, end },
            marker_type,
            right_gravity,
        };

        let new_node = Node::new(marker.clone(), Weak::new());
        self.root = Self::insert_recursive(self.root.take(), new_node.clone());

        self.marker_map.insert(id, new_node);
        id
    }

    /// Insert a line anchor at a specific position
    pub fn insert_line_anchor(
        &mut self,
        start: u64,
        end: u64,
        estimated_line: usize,
        confidence: AnchorConfidence,
    ) -> MarkerId {
        self.insert_with_type(
            start,
            end,
            MarkerType::LineAnchor {
                estimated_line,
                confidence,
            },
        )
    }

    /// Finds the current true position of a marker by its ID. Performance: O(log n)
    pub fn get_position(&self, id: MarkerId) -> Option<(u64, u64)> {
        let node_rc = self.marker_map.get(&id)?;
        let mut node_opt = Some(Rc::clone(node_rc));
        let mut current_delta: i64 = 0;

        // Walk up the tree, collecting all deltas that haven't been applied yet.
        while let Some(current_rc) = node_opt {
            let current = current_rc.borrow();

            // Add this node's delta (if any)
            current_delta += current.lazy_delta;

            // Move up to the parent
            node_opt = current.parent.upgrade();
        }

        let raw_marker = node_rc.borrow().marker.interval.clone();

        let start = (raw_marker.start as i64 + current_delta) as u64;
        let end = (raw_marker.end as i64 + current_delta) as u64;

        Some((start, end))
    }

    /// Deletes a marker by its ID. Performance: O(log n)
    pub fn delete(&mut self, id: MarkerId) -> bool {
        let (start, _) = match self.get_position(id) {
            Some(pos) => pos,
            None => return false,
        };

        if !self.marker_map.contains_key(&id) {
            return false;
        }

        self.root = Self::delete_recursive(self.root.take(), start, id, &mut self.marker_map);

        self.marker_map.remove(&id).is_some()
    }

    /// Move a marker to a new position, preserving its ID and type.
    /// Implemented as delete + reinsert with the same ID.
    /// Returns false if the marker doesn't exist.
    /// Performance: O(log n)
    pub fn set_position(&mut self, id: MarkerId, new_start: u64, new_end: u64) -> bool {
        // Get the marker's type and gravity before deleting
        let (marker_type, right_gravity) = match self.get_marker(id) {
            Some(m) => (m.marker_type, m.right_gravity),
            None => return false,
        };

        // Delete from tree
        if !self.delete(id) {
            return false;
        }

        // Reinsert with same ID
        self.insert_with_id(id, new_start, new_end, marker_type, right_gravity);
        true
    }

    /// Adjusts all markers for a text edit (insertion or deletion).
    /// Performance: O(log n) due to lazy delta propagation.
    pub fn adjust_for_edit(&mut self, pos: u64, delta: i64) {
        Self::adjust_recursive(&mut self.root, pos, delta);
    }

    /// Finds all markers that overlap a given query range.
    /// Performance: O(log n + k)
    pub fn query(&self, query_start: u64, query_end: u64) -> Vec<Marker> {
        let mut results = Vec::new();
        Self::query_recursive(&self.root, query_start, query_end, &mut results);
        results
    }

    /// Get the marker data for a given marker ID
    pub fn get_marker(&self, id: MarkerId) -> Option<Marker> {
        let node_rc = self.marker_map.get(&id)?;
        Some(node_rc.borrow().marker.clone())
    }

    /// Update a line anchor's estimated line number and confidence
    pub fn update_line_anchor(
        &mut self,
        id: MarkerId,
        estimated_line: usize,
        confidence: AnchorConfidence,
    ) -> bool {
        if let Some(node_rc) = self.marker_map.get(&id) {
            let mut node = node_rc.borrow_mut();
            node.marker.marker_type = MarkerType::LineAnchor {
                estimated_line,
                confidence,
            };
            true
        } else {
            false
        }
    }

    /// Query only line anchors in a range
    pub fn query_line_anchors(&self, query_start: u64, query_end: u64) -> Vec<Marker> {
        self.query(query_start, query_end)
            .into_iter()
            .filter(|m| matches!(m.marker_type, MarkerType::LineAnchor { .. }))
            .collect()
    }
}

// ---
// 4. Recursive Implementation Details (Insert, Delete, Adjust)
// ---

impl IntervalTree {
    /// Recursive helper for insert
    fn insert_recursive(root: NodePtr, new_node: Rc<RefCell<Node>>) -> NodePtr {
        // Remove unnecessary 'mut'
        let root = match root {
            Some(r) => r,
            None => return Some(new_node),
        };

        Node::push_delta(&root);

        let (start, id) = (
            new_node.borrow().marker.interval.start,
            new_node.borrow().marker.id,
        );

        let mut root_mut = root.borrow_mut();
        let (root_start, root_id) = (root_mut.marker.interval.start, root_mut.marker.id);

        if start < root_start || (start == root_start && id < root_id) {
            root_mut.left = Self::insert_recursive(root_mut.left.take(), Rc::clone(&new_node));
            root_mut.left.as_ref().unwrap().borrow_mut().parent = Rc::downgrade(&root);
        } else {
            root_mut.right = Self::insert_recursive(root_mut.right.take(), Rc::clone(&new_node));
            root_mut.right.as_ref().unwrap().borrow_mut().parent = Rc::downgrade(&root);
        }

        drop(root_mut);
        Node::update_stats(&root);
        Self::balance(root)
    }

    /// Recursive helper for delete
    fn delete_recursive(
        root: NodePtr,
        start: u64,
        id: MarkerId,
        marker_map: &mut HashMap<MarkerId, Rc<RefCell<Node>>>,
    ) -> NodePtr {
        // Remove unnecessary 'mut'
        let root = root?;

        Node::push_delta(&root);

        let mut root_mut = root.borrow_mut();
        let (root_start, root_id) = (root_mut.marker.interval.start, root_mut.marker.id);

        match start.cmp(&root_start) {
            Ordering::Less => {
                root_mut.left = Self::delete_recursive(root_mut.left.take(), start, id, marker_map);
            }
            Ordering::Greater => {
                root_mut.right =
                    Self::delete_recursive(root_mut.right.take(), start, id, marker_map);
            }
            Ordering::Equal => match id.cmp(&root_id) {
                Ordering::Less => {
                    root_mut.left =
                        Self::delete_recursive(root_mut.left.take(), start, id, marker_map);
                }
                Ordering::Greater => {
                    root_mut.right =
                        Self::delete_recursive(root_mut.right.take(), start, id, marker_map);
                }
                Ordering::Equal => {
                    return Self::perform_node_deletion(root_mut, Rc::clone(&root), marker_map);
                }
            },
        }

        drop(root_mut);
        Node::update_stats(&root);
        Self::balance(root)
    }

    /// Handles the actual structural changes for deletion.
    fn perform_node_deletion(
        mut node: RefMut<Node>,
        node_rc: Rc<RefCell<Node>>,
        marker_map: &mut HashMap<MarkerId, Rc<RefCell<Node>>>,
    ) -> NodePtr {
        if node.left.is_none() {
            let right = node.right.take();
            if let Some(ref r) = right {
                r.borrow_mut().parent = node.parent.clone();
            }
            right
        } else if node.right.is_none() {
            let left = node.left.take();
            if let Some(ref l) = left {
                l.borrow_mut().parent = node.parent.clone();
            }
            left
        } else {
            let successor_rc = Self::min_node(node.right.as_ref().unwrap());

            let (_successor_start, successor_id) = {
                let s = successor_rc.borrow();
                (s.marker.interval.start, s.marker.id)
            };

            // Capture the original node's marker identity BEFORE we swap
            // it away. After the swap `successor_rc` carries this
            // marker, and that's what delete_recursive must now search
            // for in the right subtree to remove it.
            let (orig_start, orig_id) = (node.marker.interval.start, node.marker.id);

            mem::swap(&mut node.marker, &mut successor_rc.borrow_mut().marker);

            // `node_rc` now carries the successor's marker, so external
            // references (marker_map) to `successor_id` must point here
            // instead of at the old successor node (which is about to
            // be removed). Without this update, `get_position(successor_id)`
            // would keep resolving via the orphaned successor node and
            // return stale data — the root cause of end-of-line inlay
            // hints flipping to the start of their line after a nearby
            // delete, because the orphan misses all subsequent
            // adjust_for_edit calls.
            marker_map.insert(successor_id, Rc::clone(&node_rc));

            // Remove the old successor node. After the swap it holds
            // the original marker (orig_start, orig_id), so search by
            // THAT key — not by (successor_start, successor_id) which
            // no longer corresponds to any node in the subtree.
            node.right = Self::delete_recursive(node.right.take(), orig_start, orig_id, marker_map);

            drop(node);
            Node::update_stats(&node_rc);
            Self::balance(node_rc)
        }
    }

    /// Finds the minimum node in a subtree (for deletion)
    fn min_node(node_rc: &Rc<RefCell<Node>>) -> Rc<RefCell<Node>> {
        let mut current = Rc::clone(node_rc);
        loop {
            Node::push_delta(&current);

            // Fix E0506: Clone the next node pointer before the borrow (Ref<Node>) on
            // `current` is dropped and potentially prevents reassignment.
            let next_left_opt = current.borrow().left.clone();

            if let Some(next) = next_left_opt {
                current = next;
            } else {
                break current;
            }
        }
    }

    /// CORRECTED Recursive helper for `adjust_for_edit` (O(log n) lazy update)
    fn adjust_recursive(node_opt: &mut NodePtr, pos: u64, delta: i64) {
        let node_rc = match node_opt {
            Some(n) => n,
            None => return,
        };

        Node::push_delta(node_rc);

        let mut node = node_rc.borrow_mut();
        let start = node.marker.interval.start;
        // Left-gravity markers stay put when text is inserted exactly at their
        // position (the insertion goes after them); right-gravity markers (the
        // default) are pushed forward. Gravity only changes behaviour for
        // insertions (delta > 0) landing exactly on the boundary.
        let left_gravity = !node.marker.right_gravity;

        if pos <= start {
            // CASE 1: Edit is at or before this node's start.
            // This node and everything to its right must be shifted.

            // Whether this node's own start should shift. A left-gravity marker
            // does NOT move when the insertion lands exactly on it.
            let stay_put = left_gravity && delta > 0 && pos == start;

            // 1. Shift the current node's start position directly, clamping at `pos` if needed.
            if !stay_put {
                if delta < 0 {
                    node.marker.interval.start = (start as i64 + delta).max(pos as i64) as u64;
                } else {
                    node.marker.interval.start = (start as i64 + delta) as u64;
                }
            }

            // 2. Handle the right subtree.
            // For insertions strictly before this node's start, every node to
            // the right has start > pos and shifts uniformly, so lazy
            // propagation is safe and efficient. When the insertion lands
            // exactly on this node's start (pos == start), the right subtree may
            // contain other markers also sitting at `pos` whose gravity must be
            // respected individually, so recurse instead of shifting them all.
            // Deletions always recurse so nodes can clamp to `pos`.
            if delta < 0 || pos == start {
                Self::adjust_recursive(&mut node.right, pos, delta);
            } else if let Some(ref right) = node.right {
                right.borrow_mut().lazy_delta += delta;
            }

            // 3. Recurse left, as it may contain markers spanning the edit pos.
            Self::adjust_recursive(&mut node.left, pos, delta);
        } else {
            // pos > start
            // CASE 2: This node's start is BEFORE the edit.
            // Its start is unaffected. We only need to check the right subtree
            // for nodes that might be affected.
            Self::adjust_recursive(&mut node.right, pos, delta);
        }

        // Handle the interval span case (where the edit falls inside [start, end]).
        // A left-gravity marker's end stays put for an insertion landing exactly
        // on it, matching its start behaviour above.
        let end = node.marker.interval.end;
        let shift_end = if left_gravity && delta > 0 {
            end > pos
        } else {
            end >= pos
        };
        if shift_end {
            node.marker.interval.end =
                (end as i64 + delta).max(node.marker.interval.start as i64) as u64;
        }

        drop(node);
        Node::update_stats(node_rc);
    }

    /// Recursive helper for query
    fn query_recursive(
        node_opt: &NodePtr,
        query_start: u64,
        query_end: u64,
        results: &mut Vec<Marker>,
    ) {
        let node_rc = match node_opt {
            Some(n) => n,
            None => return,
        };

        Node::push_delta(node_rc);
        let node = node_rc.borrow();

        let i = &node.marker.interval;
        if i.start <= query_end && i.end >= query_start {
            results.push(node.marker.clone());
        }

        if node.left.is_some() && node.left.as_ref().unwrap().borrow().max_end >= query_start {
            Self::query_recursive(&node.left, query_start, query_end, results);
        }

        if node.right.is_some() && node.marker.interval.start <= query_end {
            Self::query_recursive(&node.right, query_start, query_end, results);
        }
    }

    // --- AVL Balancing ---

    fn balance(node: Rc<RefCell<Node>>) -> NodePtr {
        let bf = Node::balance_factor(&node);

        if bf > 1 {
            let left_rc = node.borrow().left.as_ref().unwrap().clone();
            if Node::balance_factor(&left_rc) < 0 {
                // Fix RefCell borrow issue: extract left child before rotating
                let left_child = node.borrow_mut().left.take().unwrap();
                node.borrow_mut().left = Self::rotate_left(left_child);
            }
            Self::rotate_right(node)
        } else if bf < -1 {
            let right_rc = node.borrow().right.as_ref().unwrap().clone();
            if Node::balance_factor(&right_rc) > 0 {
                // Fix RefCell borrow issue: extract right child before rotating
                let right_child = node.borrow_mut().right.take().unwrap();
                node.borrow_mut().right = Self::rotate_right(right_child);
            }
            Self::rotate_left(node)
        } else {
            Some(node)
        }
    }

    fn rotate_left(node_rc: Rc<RefCell<Node>>) -> NodePtr {
        Node::push_delta(&node_rc);
        let x_rc = node_rc.borrow_mut().right.take().unwrap();
        Node::push_delta(&x_rc);

        let mut y = node_rc.borrow_mut();
        let mut x = x_rc.borrow_mut();

        y.right = x.left.take();
        if let Some(ref r) = y.right {
            r.borrow_mut().parent = Rc::downgrade(&node_rc);
        }
        x.left = Some(Rc::clone(&node_rc));
        x.parent = y.parent.clone();
        y.parent = Rc::downgrade(&x_rc);

        drop(x);
        drop(y);

        Node::update_stats(&node_rc);
        Node::update_stats(&x_rc);
        Some(x_rc)
    }

    fn rotate_right(node_rc: Rc<RefCell<Node>>) -> NodePtr {
        Node::push_delta(&node_rc);
        let x_rc = node_rc.borrow_mut().left.take().unwrap();
        Node::push_delta(&x_rc);

        let mut y = node_rc.borrow_mut();
        let mut x = x_rc.borrow_mut();

        y.left = x.right.take();
        if let Some(ref l) = y.left {
            l.borrow_mut().parent = Rc::downgrade(&node_rc);
        }
        x.right = Some(Rc::clone(&node_rc));
        x.parent = y.parent.clone();
        y.parent = Rc::downgrade(&x_rc);

        drop(x);
        drop(y);

        Node::update_stats(&node_rc);
        Node::update_stats(&x_rc);
        Some(x_rc)
    }
}

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

    /// Helper to insert and return the ID, making test setup cleaner.
    fn insert_marker(tree: &mut IntervalTree, start: u64, end: u64) -> MarkerId {
        tree.insert(start, end)
    }

    /// Helper to get position and unwrap, or panic with a clear message.
    fn get_pos(tree: &IntervalTree, id: MarkerId) -> (u64, u64) {
        tree.get_position(id)
            .unwrap_or_else(|| panic!("Marker ID {} not found.", id))
    }

    // --- Insertion gravity (issue #2053) ---

    #[test]
    fn test_left_gravity_marker_stays_on_insert_at_position() {
        // A left-gravity point marker models the end of a fixed-width
        // highlight (e.g. a search match). Inserting text exactly at its
        // position must NOT move it, so the highlight does not grow.
        let mut tree = IntervalTree::new();
        let m = tree.insert_left_gravity(3, 3);

        // Insert 4 bytes immediately at the marker.
        tree.adjust_for_edit(3, 4);

        assert_eq!(
            get_pos(&tree, m),
            (3, 3),
            "left-gravity marker must stay put when text is inserted at its position"
        );
    }

    #[test]
    fn test_right_gravity_marker_moves_on_insert_at_position() {
        // The default (right gravity) point marker moves forward when text is
        // inserted exactly at its position.
        let mut tree = IntervalTree::new();
        let m = tree.insert(3, 3);

        tree.adjust_for_edit(3, 4);

        assert_eq!(get_pos(&tree, m), (7, 7));
    }

    #[test]
    fn test_left_gravity_marker_still_shifts_on_insert_before() {
        // Left gravity only changes the exact-boundary case; insertions
        // strictly before the marker still shift it.
        let mut tree = IntervalTree::new();
        let m = tree.insert_left_gravity(5, 5);

        tree.adjust_for_edit(2, 3);

        assert_eq!(get_pos(&tree, m), (8, 8));
    }

    #[test]
    fn test_search_match_does_not_grow_on_adjacent_insert() {
        // Reproduces #2053 at the marker level: a match highlight spanning
        // [0, 3) is modelled by a right-gravity start marker at 0 and a
        // left-gravity end marker at 3. Typing immediately after the match
        // (at position 3) must leave both markers anchored to the match.
        let mut tree = IntervalTree::new();
        let start = tree.insert(0, 0);
        let end = tree.insert_left_gravity(3, 3);

        // User types "X" right after the match.
        tree.adjust_for_edit(3, 1);

        assert_eq!(get_pos(&tree, start), (0, 0));
        assert_eq!(
            get_pos(&tree, end),
            (3, 3),
            "highlight end must not extend over text typed after the match"
        );
    }

    #[test]
    fn test_adjacent_matches_keep_independent_gravity_at_shared_boundary() {
        // Two adjacent matches (e.g. searching "ab" in "abab") share a
        // boundary at position 2: the first match's left-gravity end and the
        // second match's right-gravity start both sit at 2. Inserting there
        // must keep the first match fixed while the second match shifts.
        let mut tree = IntervalTree::new();
        let m1_start = tree.insert(0, 0);
        let m1_end = tree.insert_left_gravity(2, 2);
        let m2_start = tree.insert(2, 2);
        let m2_end = tree.insert_left_gravity(4, 4);

        // Insert 3 bytes exactly at the shared boundary.
        tree.adjust_for_edit(2, 3);

        assert_eq!(get_pos(&tree, m1_start), (0, 0));
        assert_eq!(get_pos(&tree, m1_end), (2, 2), "first match must not grow");
        assert_eq!(get_pos(&tree, m2_start), (5, 5), "second match shifts");
        assert_eq!(get_pos(&tree, m2_end), (7, 7));
    }

    #[test]
    fn test_initial_insert_and_delete() {
        let mut tree = IntervalTree::new();
        let id1 = insert_marker(&mut tree, 10, 20);
        let id2 = insert_marker(&mut tree, 30, 40);

        assert_eq!(get_pos(&tree, id1), (10, 20));
        assert_eq!(get_pos(&tree, id2), (30, 40));

        assert!(tree.delete(id1));
        assert_eq!(tree.get_position(id1), None);
        assert_eq!(get_pos(&tree, id2), (30, 40));
    }

    #[test]
    fn test_basic_edit_adjustment() {
        let mut tree = IntervalTree::new();
        let id1 = insert_marker(&mut tree, 10, 20); // Before edit
        let id2 = insert_marker(&mut tree, 30, 40); // At/After edit

        // Insert 5 characters at position 30
        tree.adjust_for_edit(30, 5);

        // id1 (10-20) should not move
        assert_eq!(
            get_pos(&tree, id1),
            (10, 20),
            "Marker before edit should not move."
        );

        // id2 (30-40) should move to (35-45)
        assert_eq!(
            get_pos(&tree, id2),
            (35, 45),
            "Marker at/after edit should move."
        );

        // Delete 10 characters at position 5
        tree.adjust_for_edit(5, -10); // All markers are after position 5

        // id1 (10-20) is inside the deletion [5, 15) and should be clamped and shrunk.
        assert_eq!(
            get_pos(&tree, id1),
            (5, 10),
            "Marker moved back by deletion."
        );

        // id2 (35-45) -> (25-35)
        assert_eq!(
            get_pos(&tree, id2),
            (25, 35),
            "Marker moved back by deletion."
        );
    }

    #[test]
    fn test_problematic_lazy_delta_scenario() {
        // This test replicates the tricky tree structure to ensure the O(log n) lazy
        // delta propagation works correctly and doesn't over-propagate to left children.

        let mut tree = IntervalTree::new();

        // Setup the tree with specific positions to force a parent/child relationship
        // that caused the previous bug:
        // L(100) -> P(200) <- R(300)
        let id_p = insert_marker(&mut tree, 200, 250); // Parent node (P)
        let id_r = insert_marker(&mut tree, 300, 350); // Right child (R)
        let id_l = insert_marker(&mut tree, 100, 150); // Left child (L)

        // --- Verify initial state ---
        assert_eq!(
            get_pos(&tree, id_l),
            (100, 150),
            "L initial position incorrect."
        );
        assert_eq!(
            get_pos(&tree, id_p),
            (200, 250),
            "P initial position incorrect."
        );
        assert_eq!(
            get_pos(&tree, id_r),
            (300, 350),
            "R initial position incorrect."
        );

        // --- Apply the problematic edit ---
        // Edit: Insert 50 characters at position 150 (P=150, delta=+50)
        // L(100) should NOT move (100 < 150).
        // P(200) and R(300) should move (+50).
        tree.adjust_for_edit(150, 50);

        // --- Verify corrected final state ---

        // L(100) should have its end expanded (100 < 150, but 150 >= 150).
        assert_eq!(
            get_pos(&tree, id_l),
            (100, 200),
            "L(100) should expand to (100, 200)."
        );

        // P(200) should be shifted (200 >= 150) -> 250
        assert_eq!(
            get_pos(&tree, id_p),
            (250, 300),
            "P(200) did not shift correctly. Should be 250."
        );

        // R(300) should be shifted (300 >= 150) -> 350
        assert_eq!(
            get_pos(&tree, id_r),
            (350, 400),
            "R(300) did not shift correctly. Should be 350."
        );
    }

    #[test]
    fn test_interval_spanning_edit() {
        let mut tree = IntervalTree::new();
        // Marker S starts before edit, but spans it.
        let id_s = insert_marker(&mut tree, 50, 200);

        // Edit: Insert 10 characters at position 100 (P=100, delta=+10)
        tree.adjust_for_edit(100, 10);

        // S(50, 200) starts before 100, so its start (50) is fixed.
        // Its end (200) is at/after 100, so its end should move to 210.
        assert_eq!(
            get_pos(&tree, id_s),
            (50, 210),
            "Spanning marker end did not move correctly."
        );
    }

    #[test]
    fn test_deletion_engulfing_marker_start() {
        let mut tree = IntervalTree::new();
        let id1 = insert_marker(&mut tree, 8, 20);

        // Delete 10 chars at pos 5. Deletion is on [5, 15).
        // Marker is on [8, 20). The part [8, 15) is deleted.
        // New start should be clamped at the deletion position: 5.
        // End is adjusted by delta: 20 - 10 = 10.
        // So new interval should be (5, 10).
        tree.adjust_for_edit(5, -10);

        assert_eq!(
            get_pos(&tree, id1),
            (5, 10),
            "Marker should be clamped and shrunk."
        );
    }

    #[test]
    fn test_zero_length_marker() {
        let mut tree = IntervalTree::new();
        let id1 = insert_marker(&mut tree, 10, 10);

        // Insertion at the marker's position should push it.
        tree.adjust_for_edit(10, 5);
        assert_eq!(
            get_pos(&tree, id1),
            (15, 15),
            "Insertion at zero-length marker."
        );

        // Insertion before should also push it.
        tree.adjust_for_edit(5, 5);
        assert_eq!(
            get_pos(&tree, id1),
            (20, 20),
            "Insertion before zero-length marker."
        );

        // Deletion after should not affect it.
        tree.adjust_for_edit(25, -5);
        assert_eq!(
            get_pos(&tree, id1),
            (20, 20),
            "Deletion after zero-length marker."
        );

        // Deletion that contains the marker.
        tree.adjust_for_edit(15, -10);
        // Marker at 20. Deletion on [15, 25).
        // Start becomes max(15, 20-10) = 15.
        // End becomes max(new_start, 20-10) = max(15, 10) = 15.
        assert_eq!(
            get_pos(&tree, id1),
            (15, 15),
            "Deletion containing zero-length marker."
        );
    }

    #[test]
    fn test_edit_at_pos_zero() {
        let mut tree = IntervalTree::new();
        let id1 = insert_marker(&mut tree, 10, 20);

        // Insertion at pos 0
        tree.adjust_for_edit(0, 5);
        assert_eq!(get_pos(&tree, id1), (15, 25), "Insertion at pos 0.");

        // Deletion at pos 0
        tree.adjust_for_edit(0, -5);
        assert_eq!(get_pos(&tree, id1), (10, 20), "Deletion at pos 0.");

        // Deletion at pos 0 that engulfs the start.
        tree.adjust_for_edit(0, -15);
        // Marker at (10, 20). Deletion on [0, 15).
        // New start becomes max(0, 10-15) = 0.
        // New end becomes max(new_start, 20-15) = max(0, 5) = 5.
        assert_eq!(get_pos(&tree, id1), (0, 5), "Engulfing deletion at pos 0.");
    }

    #[test]
    fn test_deletion_preserves_marker_ordering() {
        // This test reproduces the bug found in prop_marker_ordering_preserved
        // where lazy delta propagation causes ordering violations.
        let mut tree = IntervalTree::new();

        // Create markers in order: [0, 10, 20, 30, 40] (spacing=10)
        let id0 = insert_marker(&mut tree, 0, 0);
        let id1 = insert_marker(&mut tree, 10, 10);
        let id2 = insert_marker(&mut tree, 20, 20);
        let id3 = insert_marker(&mut tree, 30, 30);
        let id4 = insert_marker(&mut tree, 40, 40);

        // Verify initial state
        assert_eq!(get_pos(&tree, id0), (0, 0));
        assert_eq!(get_pos(&tree, id1), (10, 10));
        assert_eq!(get_pos(&tree, id2), (20, 20));
        assert_eq!(get_pos(&tree, id3), (30, 30));
        assert_eq!(get_pos(&tree, id4), (40, 40));

        // Delete 16 bytes starting at position 5
        // This deletes range [5, 21)
        // Expected positions after: [0, 5, 5, 14, 24]
        tree.adjust_for_edit(5, -16);

        // Get all positions
        let positions = vec![
            get_pos(&tree, id0).0,
            get_pos(&tree, id1).0,
            get_pos(&tree, id2).0,
            get_pos(&tree, id3).0,
            get_pos(&tree, id4).0,
        ];

        // Verify ordering is preserved (no inversions)
        for i in 0..positions.len() - 1 {
            assert!(
                positions[i] <= positions[i + 1],
                "Ordering violated at index {}: {:?}[{}]={} > {:?}[{}]={}",
                i,
                positions,
                i,
                positions[i],
                positions,
                i + 1,
                positions[i + 1]
            );
        }

        // Verify specific expected positions
        assert_eq!(get_pos(&tree, id0), (0, 0), "Marker at 0 should stay at 0");
        assert_eq!(
            get_pos(&tree, id1),
            (5, 5),
            "Marker at 10 should clamp to 5"
        );
        assert_eq!(
            get_pos(&tree, id2),
            (5, 5),
            "Marker at 20 should clamp to 5"
        );
        assert_eq!(
            get_pos(&tree, id3),
            (14, 14),
            "Marker at 30 should shift to 14"
        );
        assert_eq!(
            get_pos(&tree, id4),
            (24, 24),
            "Marker at 40 should shift to 24"
        );
    }
}