minerva 0.2.0

//! Run-coalesced region endpoint coordinate for the order thread.

extern crate alloc;

use alloc::collections::{BTreeMap, BTreeSet};
use alloc::vec::Vec;

use super::super::placement::Dot;
use super::NIL;

/// The dot one counter past `dot` on its own station: the successor-shaped
/// edge the ends plane contracts. `None` at the `u64::MAX` ceiling, where
/// no successor exists.
fn successor_of(dot: Dot) -> Option<Dot> {
    dot.counter_nonzero()
        .checked_add(1)
        .map(|next| Dot::new(dot.station(), next))
}

/// One node in a rooted link-cut forest. The represented parent points
/// toward a region endpoint; auxiliary children are splay-tree links.
#[derive(Clone, Copy, Debug)]
struct LinkNode {
    left: u32,
    right: u32,
    parent: u32,
}

impl LinkNode {
    const EMPTY: Self = Self {
        left: NIL,
        right: NIL,
        parent: NIL,
    };
}

/// A dynamic rooted forest supporting endpoint lookup and parent-edge
/// replacement in `O(log n)` amortized time. No evert operation is
/// exposed: represented roots remain the terminal region endpoints.
#[derive(Clone, Debug, Default)]
struct EndpointForest {
    nodes: Vec<LinkNode>,
}

impl EndpointForest {
    fn push_node(&mut self) {
        self.nodes.push(LinkNode::EMPTY);
    }

    fn reset(&mut self, id: u32) {
        self.nodes[id as usize] = LinkNode::EMPTY;
    }

    fn is_aux_root(&self, id: u32) -> bool {
        let parent = self.nodes[id as usize].parent;
        parent == NIL
            || (self.nodes[parent as usize].left != id && self.nodes[parent as usize].right != id)
    }

    fn rotate(&mut self, id: u32) {
        let parent = self.nodes[id as usize].parent;
        let grand = self.nodes[parent as usize].parent;
        let parent_is_aux_root = self.is_aux_root(parent);
        if self.nodes[parent as usize].left == id {
            let middle = self.nodes[id as usize].right;
            self.nodes[parent as usize].left = middle;
            if middle != NIL {
                self.nodes[middle as usize].parent = parent;
            }
            self.nodes[id as usize].right = parent;
        } else {
            debug_assert_eq!(self.nodes[parent as usize].right, id);
            let middle = self.nodes[id as usize].left;
            self.nodes[parent as usize].right = middle;
            if middle != NIL {
                self.nodes[middle as usize].parent = parent;
            }
            self.nodes[id as usize].left = parent;
        }
        self.nodes[parent as usize].parent = id;
        self.nodes[id as usize].parent = grand;
        if !parent_is_aux_root {
            if self.nodes[grand as usize].left == parent {
                self.nodes[grand as usize].left = id;
            } else {
                debug_assert_eq!(self.nodes[grand as usize].right, parent);
                self.nodes[grand as usize].right = id;
            }
        }
    }

    fn splay(&mut self, id: u32) {
        while !self.is_aux_root(id) {
            let parent = self.nodes[id as usize].parent;
            if !self.is_aux_root(parent) {
                let grand = self.nodes[parent as usize].parent;
                let id_is_left = self.nodes[parent as usize].left == id;
                let parent_is_left = self.nodes[grand as usize].left == parent;
                if id_is_left == parent_is_left {
                    self.rotate(parent);
                } else {
                    self.rotate(id);
                }
            }
            self.rotate(id);
        }
    }

    /// Exposes the represented-root-to-`id` path and splays `id`.
    fn access(&mut self, id: u32) {
        let mut current = id;
        let mut last = NIL;
        while current != NIL {
            self.splay(current);
            let path_parent = self.nodes[current as usize].parent;
            self.nodes[current as usize].right = last;
            if last != NIL {
                self.nodes[last as usize].parent = current;
            }
            last = current;
            current = path_parent;
        }
        self.splay(id);
    }

    /// Returns the represented root, the terminal endpoint of `id`.
    fn root(&mut self, id: u32) -> u32 {
        self.access(id);
        let mut root = id;
        while self.nodes[root as usize].left != NIL {
            root = self.nodes[root as usize].left;
        }
        self.splay(root);
        root
    }

    /// Replaces `id`'s represented parent. `id` must be the root of its
    /// component after the old parent edge is cut.
    fn replace_parent(&mut self, id: u32, parent: Option<u32>) {
        self.access(id);
        let old_path = self.nodes[id as usize].left;
        if old_path != NIL {
            self.nodes[id as usize].left = NIL;
            self.nodes[old_path as usize].parent = NIL;
        }
        if let Some(parent) = parent {
            #[cfg(debug_assertions)]
            {
                assert_eq!(self.root(id), id, "the replaced node is a component root");
                assert_ne!(self.root(parent), id, "region links stay acyclic");
            }
            self.nodes[id as usize].parent = parent;
        }
    }

    /// The represented parent of `id` (`NIL` at a component root): after
    /// exposing the root-to-`id` path, the parent is the path node just
    /// above `id`, the rightmost of its left subtree (splayed afterward,
    /// keeping the amortized bound). What lets a segment transfer its
    /// inherited edge on a split or merge without storing edges twice.
    fn represented_parent(&mut self, id: u32) -> u32 {
        self.access(id);
        let mut node = self.nodes[id as usize].left;
        if node == NIL {
            return NIL;
        }
        while self.nodes[node as usize].right != NIL {
            node = self.nodes[node as usize].right;
        }
        self.splay(node);
        node
    }
}

/// One link-cut forest half with lazily allocated per-dot nodes (the
/// starts side): honest traffic has few `Before` relations, so a dot
/// with no node is its own region start and pays no storage at all.
#[derive(Clone, Debug)]
struct SparseForest {
    forest: EndpointForest,
    /// Node id to dot.
    dots: Vec<Dot>,
    /// Retired node ids, reused first.
    free: Vec<u32>,
    /// Dot to node id, for dots participating in any edge.
    index: BTreeMap<Dot, u32>,
}

impl SparseForest {
    pub(super) const fn new() -> Self {
        Self {
            forest: EndpointForest { nodes: Vec::new() },
            dots: Vec::new(),
            free: Vec::new(),
            index: BTreeMap::new(),
        }
    }

    /// The node for `dot`, allocated on first participation in an edge.
    fn ensure(&mut self, dot: Dot) -> u32 {
        if let Some(&id) = self.index.get(&dot) {
            return id;
        }
        let id = if let Some(id) = self.free.pop() {
            self.forest.reset(id);
            self.dots[id as usize] = dot;
            id
        } else {
            let id = u32::try_from(self.dots.len())
                .ok()
                .filter(|&id| id != NIL)
                .expect("the plane's live-entry ceiling bounds region endpoints");
            self.forest.push_node();
            self.dots.push(dot);
            id
        };
        let _ = self.index.insert(dot, id);
        id
    }

    /// The terminal endpoint of `dot`: the represented root of its node,
    /// or `dot` itself where no edge ever touched it.
    fn endpoint(&mut self, dot: Dot) -> Dot {
        match self.index.get(&dot) {
            Some(&id) => {
                let root = self.forest.root(id);
                self.dots[root as usize]
            }
            None => dot,
        }
    }

    /// Replaces `dot`'s edge. A `None` on a node-less dot stays free.
    fn replace(&mut self, dot: Dot, child: Option<Dot>) {
        match child {
            Some(child) => {
                let child_id = self.ensure(child);
                let id = self.ensure(dot);
                self.forest.replace_parent(id, Some(child_id));
            }
            None => {
                if let Some(&id) = self.index.get(&dot) {
                    self.forest.replace_parent(id, None);
                }
            }
        }
    }

    /// Retires `dot`'s node if present. The caller's excision protocol
    /// guarantees isolation: every edge touching a sterile dot was
    /// replaced away before its retirement.
    fn remove(&mut self, dot: Dot) {
        if let Some(id) = self.index.remove(&dot) {
            debug_assert_eq!(self.forest.root(id), id, "a sterile dot has no start child");
            self.forest.reset(id);
            self.free.push(id);
        }
    }

    #[cfg(test)]
    fn live_nodes(&self) -> usize {
        self.index.len()
    }
}

/// The ends side, run-coalesced (arc 11 phase five): an ends edge that
/// points at its own dot successor is arithmetic (honest typing is
/// nothing else), so the forest's nodes are *segments*, maximal
/// successor-edged spans, and only the edges at their tails are stored.
/// Segment extents are derived per query from the break set, so a typing
/// append is pure set arithmetic: no allocation and no forest operation.
///
/// The head invariant that makes contraction sound: an explicit edge's
/// target is always a segment head, because an edge targets the parent's
/// last `After` child, a dot anchored `After` the parent; its own
/// predecessor's successor edge would need the same dot anchored `After`
/// that predecessor, and a dot has one anchor. Successor-shaped edges are
/// therefore never stored, and every stored edge lands on a head.
#[derive(Clone, Debug)]
struct SegmentPlane {
    forest: EndpointForest,
    /// Node id to segment head dot.
    seg_heads: Vec<Dot>,
    /// Retired node ids, reused first.
    free: Vec<u32>,
    /// Every segment: head dot to forest node id (`NIL` until an edge
    /// touches the segment).
    heads: BTreeMap<Dot, u32>,
    /// Every segment tail: the placed dots whose ends edge is not their
    /// dot successor (an explicit edge, or none).
    breaks: BTreeSet<Dot>,
}

impl SegmentPlane {
    const fn new() -> Self {
        Self {
            forest: EndpointForest { nodes: Vec::new() },
            seg_heads: Vec::new(),
            free: Vec::new(),
            heads: BTreeMap::new(),
            breaks: BTreeSet::new(),
        }
    }

    /// The head of the segment covering `dot`, `None` for a dot no
    /// segment covers (unplaced or never inserted). Two range probes on
    /// the `O(segments)` sets.
    fn head_of(&self, dot: Dot) -> Option<Dot> {
        let (&head, _) = self.heads.range(..=dot).next_back()?;
        if head.station() != dot.station() {
            return None;
        }
        (dot.counter() <= self.tail_of(head).counter()).then_some(head)
    }

    /// The tail of the segment headed at `head`: the first break at or
    /// past it (every segment's last dot is a break, so the probe is
    /// total for a live head).
    fn tail_of(&self, head: Dot) -> Dot {
        let tail = *self
            .breaks
            .range(head..)
            .next()
            .expect("every segment ends at a break");
        debug_assert_eq!(
            tail.station(),
            head.station(),
            "a segment stays inside its station"
        );
        tail
    }

    /// Allocates a forest node for the segment headed at `head`.
    fn alloc_node(&mut self, head: Dot) -> u32 {
        if let Some(id) = self.free.pop() {
            self.forest.reset(id);
            self.seg_heads[id as usize] = head;
            id
        } else {
            let id = u32::try_from(self.seg_heads.len())
                .ok()
                .filter(|&id| id != NIL)
                .expect("the plane's live-entry ceiling bounds segment nodes");
            self.forest.push_node();
            self.seg_heads.push(head);
            id
        }
    }

    /// The forest node of the segment headed at `head`, allocated on
    /// first edge contact.
    fn ensure_node(&mut self, head: Dot) -> u32 {
        let existing = *self.heads.get(&head).expect("a live segment head");
        if existing != NIL {
            return existing;
        }
        let id = self.alloc_node(head);
        let _ = self.heads.insert(head, id);
        id
    }

    /// Registers a newly placed dot as its own single-dot segment; the
    /// caller's edge replacements merge it into its neighbors.
    pub(super) fn insert(&mut self, dot: Dot) -> bool {
        if self.head_of(dot).is_some() {
            return false;
        }
        let _ = self.heads.insert(dot, NIL);
        let _ = self.breaks.insert(dot);
        true
    }

    /// Registers a whole freshly placed chain run `head ..= tail` (one
    /// station, consecutive dots, each the sole `After` child of its
    /// predecessor) as ONE segment: the bulk-ingest form of per-dot
    /// [`insert`](Self::insert) followed by the successor-edge merges the
    /// per-dot protocol would run, whose net effect is exactly this one
    /// head and one break. Refuses a run any existing segment covers
    /// (either end probed; fresh dots are never covered).
    pub(super) fn insert_run(&mut self, head: Dot, tail: Dot) -> bool {
        debug_assert_eq!(
            head.station(),
            tail.station(),
            "a run stays inside its station"
        );
        debug_assert!(
            head.counter() <= tail.counter(),
            "a run's head precedes its tail"
        );
        if self.head_of(head).is_some() || self.head_of(tail).is_some() {
            return false;
        }
        let _ = self.heads.insert(head, NIL);
        let _ = self.breaks.insert(tail);
        true
    }

    /// Retires a sterile placed dot. The excision protocol has already
    /// replaced every touching edge, so the dot is a single-dot,
    /// edge-free segment by the time it leaves.
    pub(super) fn remove(&mut self, dot: Dot) -> bool {
        let Some(head) = self.head_of(dot) else {
            return false;
        };
        debug_assert_eq!(head, dot, "a retiring dot is its own segment head");
        debug_assert_eq!(self.tail_of(dot), dot, "a retiring dot is its own tail");
        if let Some(id) = self.heads.remove(&dot)
            && id != NIL
        {
            debug_assert_eq!(self.forest.root(id), id, "a sterile dot has no end child");
            self.forest.reset(id);
            self.free.push(id);
        }
        let _ = self.breaks.remove(&dot);
        true
    }

    /// The region end of `dot`: the terminal segment's tail, one
    /// amortized-logarithmic forest access past the coverage probes.
    fn endpoint(&mut self, dot: Dot) -> Option<Dot> {
        let head = self.head_of(dot)?;
        let id = *self.heads.get(&head).expect("coverage implies a head");
        let terminal_head = if id == NIL {
            head
        } else {
            let root = self.forest.root(id);
            self.seg_heads[root as usize]
        };
        Some(self.tail_of(terminal_head))
    }

    /// Cuts the segment's stored tail edge and links the new one, if any.
    fn set_tail_edge(&mut self, head: Dot, child: Option<Dot>) {
        if let Some(&id) = self.heads.get(&head)
            && id != NIL
        {
            self.forest.replace_parent(id, None);
        }
        let Some(child) = child else {
            return;
        };
        debug_assert_eq!(
            self.head_of(child),
            Some(child),
            "an explicit edge targets a segment head (the one-anchor argument)"
        );
        let child_id = self.ensure_node(child);
        let id = self.ensure_node(head);
        self.forest.replace_parent(id, Some(child_id));
    }

    /// Replaces the ends edge of `dot`. Successor-shaped edges merge
    /// segments; a mid-segment replacement splits at `dot`; everything
    /// else is a stored-edge swap. `false` when `dot` or the named child
    /// is uncovered (the unplaced-component contract the rebuild path
    /// asserts against).
    fn replace(&mut self, dot: Dot, child: Option<Dot>) -> bool {
        let Some(head) = self.head_of(dot) else {
            return false;
        };
        if let Some(child) = child
            && self.head_of(child).is_none()
        {
            return false;
        }
        let tail = self.tail_of(head);
        let successor = successor_of(dot);
        if dot.counter() < tail.counter() {
            // `dot` is successor-edged (a segment interior).
            if child == successor {
                return true;
            }
            // Split: [head..dot] keeps the node identity (stored edges
            // land on heads at or below `dot`); [dot+1..tail] is a fresh
            // segment inheriting the stored tail edge, if any.
            let succ = successor.expect("a segment interior has a successor");
            let old_id = *self.heads.get(&head).expect("coverage implies a head");
            let mut new_id = NIL;
            if old_id != NIL {
                let inherited = self.forest.represented_parent(old_id);
                if inherited != NIL {
                    self.forest.replace_parent(old_id, None);
                    new_id = self.alloc_node(succ);
                    self.forest.replace_parent(new_id, Some(inherited));
                }
            }
            let _ = self.heads.insert(succ, new_id);
            let _ = self.breaks.insert(dot);
            self.set_tail_edge(head, child);
            return true;
        }
        // `dot` is the tail: this segment's own edge moves.
        if child.is_some() && child == successor {
            // The successor segment joins: its extent and stored edge
            // transfer to this head, and its node retires (nothing
            // targets a successor-shaped head, the one-anchor argument).
            let succ = successor.expect("a successor-shaped child exists");
            let succ_id = self
                .heads
                .remove(&succ)
                .expect("the covered successor child is a segment head");
            let my_id = *self.heads.get(&head).expect("coverage implies a head");
            if my_id != NIL {
                self.forest.replace_parent(my_id, None);
            }
            let _ = self.breaks.remove(&dot);
            if succ_id != NIL {
                let inherited = self.forest.represented_parent(succ_id);
                if inherited != NIL {
                    self.forest.replace_parent(succ_id, None);
                    let id = self.ensure_node(head);
                    self.forest.replace_parent(id, Some(inherited));
                }
                debug_assert_eq!(
                    self.forest.root(succ_id),
                    succ_id,
                    "a merged head keeps no children"
                );
                self.forest.reset(succ_id);
                self.free.push(succ_id);
            }
            return true;
        }
        self.set_tail_edge(head, child);
        true
    }

    /// Segments held (the coalescing accounting read: on honest chained
    /// traffic this is the run count, not the placed-dot count).
    #[cfg(test)]
    fn segments(&self) -> usize {
        self.heads.len()
    }

    /// Placed dots covered, summed over segment extents: `O(segments)`.
    #[cfg(test)]
    fn covered(&self) -> usize {
        self.heads
            .keys()
            .map(|&head| {
                usize::try_from(self.tail_of(head).counter() - head.counter() + 1)
                    .expect("span fits")
            })
            .sum()
    }

    #[cfg(test)]
    fn live_nodes(&self) -> usize {
        self.heads.values().filter(|&&id| id != NIL).count()
    }

    #[cfg(test)]
    pub(super) fn check_invariants(&self) {
        assert_eq!(self.heads.len(), self.breaks.len(), "one tail per segment");
        let mut prev: Option<Dot> = None;
        for (&head, &id) in &self.heads {
            let tail = self.tail_of(head);
            assert!(
                head.counter() <= tail.counter(),
                "a segment's head precedes its tail"
            );
            if let Some(prev_tail) = prev
                && prev_tail.station() == head.station()
            {
                assert!(
                    prev_tail.counter() < head.counter(),
                    "segments never overlap"
                );
            }
            prev = Some(tail);
            if id != NIL {
                assert_eq!(self.seg_heads[id as usize], head, "node names its head");
            }
        }
        let live = self.live_nodes();
        assert_eq!(
            live + self.free.len(),
            self.seg_heads.len(),
            "every node is live or retired"
        );
    }
}

/// Maintained region starts and ends (arc 11 phase five, run-coalesced):
/// the starts side is a lazy per-dot forest over the last `Before` child
/// edges (rare on honest traffic), the ends side a segment-contracted
/// forest over the last `After` child edges (mostly successor-shaped on
/// honest traffic, so mostly arithmetic). Replacing either child edge is
/// logarithmic amortized and endpoint lookup never walks
/// attacker-controlled depth; membership authority is the ends side's
/// segment coverage.
#[derive(Clone, Debug)]
pub(super) struct RegionEnds {
    starts: SparseForest,
    ends: SegmentPlane,
}

#[derive(Clone, Copy, Debug)]
pub(super) enum RegionBoundary {
    Start,
    End,
}

impl RegionEnds {
    pub(super) const fn new() -> Self {
        Self {
            starts: SparseForest::new(),
            ends: SegmentPlane::new(),
        }
    }

    pub(super) fn insert(&mut self, dot: Dot) -> bool {
        self.ends.insert(dot)
    }

    pub(super) fn insert_run(&mut self, head: Dot, tail: Dot) -> bool {
        self.ends.insert_run(head, tail)
    }

    pub(super) fn remove(&mut self, dot: Dot) -> bool {
        let removed = self.ends.remove(dot);
        if removed {
            self.starts.remove(dot);
        }
        removed
    }

    pub(super) fn rebuild(
        &mut self,
        placed: impl Iterator<Item = Dot>,
        ends_edges: &BTreeMap<Dot, Dot>,
        starts_edges: &BTreeMap<Dot, Dot>,
    ) {
        let mut sorted: Vec<Dot> = placed.collect();
        sorted.sort_unstable();
        debug_assert!(
            sorted.windows(2).all(|pair| pair[0] < pair[1]),
            "the walk yields each placed dot once"
        );
        let is_placed = |dot: Dot| sorted.binary_search(&dot).is_ok();
        let mut heads: Vec<(Dot, u32)> = Vec::new();
        let mut breaks: Vec<Dot> = Vec::new();
        let mut stored: Vec<(Dot, Dot)> = Vec::new();
        let mut current_head: Option<Dot> = None;
        let mut prev: Option<(Dot, bool)> = None;
        for &dot in &sorted {
            let extends =
                prev.is_some_and(|(p, p_succ): (Dot, bool)| p_succ && successor_of(p) == Some(dot));
            if !extends {
                heads.push((dot, NIL));
                current_head = Some(dot);
            }
            let successor = successor_of(dot);
            let edge = ends_edges
                .get(&dot)
                .copied()
                .filter(|&child| is_placed(child));
            let succ_edged = edge.is_some() && edge == successor;
            if !succ_edged {
                breaks.push(dot);
                if let Some(child) = edge {
                    let head = current_head.expect("a scanned dot has a segment head");
                    stored.push((head, child));
                }
            }
            prev = Some((dot, succ_edged));
        }
        self.ends = SegmentPlane::new();
        self.ends.heads = heads.into_iter().collect();
        self.ends.breaks = breaks.into_iter().collect();
        for (head, child) in stored {
            debug_assert_eq!(
                self.ends.head_of(child),
                Some(child),
                "a stored edge targets a segment head (the one-anchor argument)"
            );
            let child_id = self.ends.ensure_node(child);
            let id = self.ends.ensure_node(head);
            self.ends.forest.replace_parent(id, Some(child_id));
        }
        self.starts = SparseForest::new();
        for (&dot, &child) in starts_edges {
            if is_placed(dot) && is_placed(child) {
                self.starts.replace(dot, Some(child));
            }
        }
    }

    pub(super) fn endpoint(&mut self, dot: Dot, boundary: RegionBoundary) -> Option<Dot> {
        match boundary {
            RegionBoundary::Start => {
                let _ = self.ends.head_of(dot)?;
                Some(self.starts.endpoint(dot))
            }
            RegionBoundary::End => self.ends.endpoint(dot),
        }
    }

    pub(super) fn replace(
        &mut self,
        dot: Dot,
        child: Option<Dot>,
        boundary: RegionBoundary,
    ) -> bool {
        match boundary {
            RegionBoundary::Start => {
                if self.ends.head_of(dot).is_none() {
                    return false;
                }
                if let Some(child) = child
                    && self.ends.head_of(child).is_none()
                {
                    return false;
                }
                self.starts.replace(dot, child);
                true
            }
            RegionBoundary::End => self.ends.replace(dot, child),
        }
    }

    #[cfg(test)]
    pub(super) fn covered(&self) -> usize {
        self.ends.covered()
    }

    #[cfg(test)]
    pub(super) fn segments(&self) -> usize {
        self.ends.segments()
    }

    #[cfg(test)]
    pub(super) fn forest_nodes(&self) -> usize {
        self.ends.live_nodes() + self.starts.live_nodes()
    }

    #[cfg(test)]
    pub(super) fn is_empty(&self) -> bool {
        self.ends.heads.is_empty()
    }

    #[cfg(test)]
    pub(super) fn check_invariants(&self) {
        self.ends.check_invariants();
        let mut copy = self.clone();
        let heads: Vec<Dot> = self.ends.heads.keys().copied().collect();
        for head in heads {
            assert!(copy.endpoint(head, RegionBoundary::Start).is_some());
            assert!(copy.endpoint(head, RegionBoundary::End).is_some());
        }
    }
}

#[cfg(test)]
mod tests;