monolith

public
Star0
Watch0
336 commits 1 branch 0 tags 0 releases1.5 MiB
use monolith_planner::Rect;
use slotmap::{SlotMap, new_key_type};
use std::collections::HashMap;
use std::hash::Hash;

new_key_type! { pub struct NodeId; }

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serde", serde(rename_all = "kebab-case"))]
pub enum Axis {
    Horizontal,
    Vertical,
}

impl Axis {
    pub fn other(self) -> Self {
        match self {
            Self::Horizontal => Self::Vertical,
            Self::Vertical => Self::Horizontal,
        }
    }

    fn index(self) -> usize {
        match self {
            Self::Horizontal => 0,
            Self::Vertical => 1,
        }
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serde", serde(rename_all = "kebab-case"))]
pub enum Dir {
    Left,
    Right,
    Up,
    Down,
}

impl Dir {
    pub fn axis(self) -> Axis {
        match self {
            Self::Left | Self::Right => Axis::Horizontal,
            Self::Up | Self::Down => Axis::Vertical,
        }
    }

    pub fn forward(self) -> bool {
        matches!(self, Self::Right | Self::Down)
    }
}

const MIN_SHARE: f64 = 0.05;

/// A window's width and height relative to its neighbours'.
type Size = [f64; 2];

#[derive(Clone, Debug)]
enum Kind<W> {
    Leaf(W, Size),
    Container {
        axis: Axis,
        children: Vec<NodeId>,
        expanded: Option<NodeId>,
    },
}

#[derive(Clone, Debug)]
struct Node<W> {
    parent: Option<NodeId>,
    kind: Kind<W>,
}

/// One output's tiling tree. Every tiled window of every tag lives here, the
/// caller's visibility filter decides which ones take space.
///
/// Children run on the axis opposite their parent. Containers hold at least
/// two children, hidden ones included, and a container left with one child
/// is replaced by it.
#[derive(Clone, Debug)]
pub struct Tree<W> {
    nodes: SlotMap<NodeId, Node<W>>,
    root: Option<NodeId>,
    leaves: HashMap<W, NodeId>,
    stack: Axis,
}

impl<W: Copy + Eq + Hash> Default for Tree<W> {
    fn default() -> Self {
        Self {
            nodes: SlotMap::with_key(),
            root: None,
            leaves: HashMap::new(),
            stack: Axis::Vertical,
        }
    }
}

impl<W: Copy + Eq + Hash> Tree<W> {
    /// The axis tag rows stack along.
    pub fn stack_axis(&self) -> Axis {
        self.stack
    }

    pub fn contains(&self, w: W) -> bool {
        self.leaves.contains_key(&w)
    }

    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }

    pub fn windows(&self) -> impl Iterator<Item = W> + '_ {
        self.leaves.keys().copied()
    }

    /// Inserts `w` as the next sibling of `anchor`, or as a new row if
    /// `anchor` is not in the tree.
    pub fn insert_after(&mut self, w: W, anchor: W, vis: impl Fn(W) -> bool) {
        let Some(&a) = self.leaves.get(&anchor) else {
            return self.insert_row(w, vis);
        };
        match self.position(a) {
            Some((p, i)) if Some(p) == self.root && self.axis(p) == Some(self.stack) => {
                let n = self.new_leaf(w, self.size(a));
                self.unlink(p, i);
                let c = self.new_container(self.stack.other());
                self.attach(c, 0, a);
                self.attach(c, 1, n);
                self.attach(p, i, c);
                self.reveal(n, true);
            }
            Some((p, i)) => {
                let n = self.new_leaf(w, self.size(p));
                self.attach(p, i + 1, n);
                self.rescale_hidden(n, true, &vis);
                self.reveal(n, true);
            }
            None => {
                let n = self.new_leaf(w, self.size(a));
                let c = self.new_container(self.stack.other());
                self.attach(c, 0, a);
                self.attach(c, 1, n);
                self.root = Some(c);
            }
        }
    }

    /// Inserts `w` after `anchor` by splitting `anchor` along `axis`. They
    /// share the space `anchor` had, and its siblings keep theirs.
    pub fn insert_split(&mut self, w: W, anchor: W, axis: Axis, vis: impl Fn(W) -> bool) {
        let Some(&a) = self.leaves.get(&anchor) else {
            return self.insert_row(w, vis);
        };
        let size = self.size(a);
        let n = self.new_leaf(w, size);
        match self.position(a) {
            Some((p, i)) if self.axis(p) == Some(axis) => {
                self.halve(a, axis);
                self.halve(n, axis);
                self.attach(p, i + 1, n);
            }
            Some((p, i)) => {
                self.unlink(p, i);
                let c = self.new_container(axis);
                self.attach(c, 0, a);
                self.attach(c, 1, n);
                self.attach(p, i, c);
            }
            None => {
                let c = self.new_container(axis);
                self.attach(c, 0, a);
                self.attach(c, 1, n);
                self.root = Some(c);
            }
        }
        self.reveal(n, true);
    }

    fn halve(&mut self, leaf: NodeId, axis: Axis) {
        if let Kind::Leaf(_, size) = &mut self.nodes[leaf].kind {
            size[axis.index()] /= 2.0;
        }
    }

    /// Scales the hidden siblings of a visible `n` arriving in or leaving its
    /// container by as much as the visible ones grow or shrink together, so
    /// the share they come back to does not drift as windows come and go.
    fn rescale_hidden(&mut self, n: NodeId, arriving: bool, vis: &impl Fn(W) -> bool) {
        let (Some((p, _)), true) = (self.position(n), self.visible(n, vis)) else {
            return;
        };
        let axis = self.axis(p).expect("parents are containers");
        let (shown, hidden): (Vec<NodeId>, Vec<NodeId>) = self
            .children(p)
            .iter()
            .filter(|&&c| c != n)
            .partition(|&&c| self.visible(c, vis));
        let rest: f64 = shown.iter().map(|&c| self.extent(c, axis, vis)).sum();
        if rest <= 0.0 {
            return;
        }
        let with = rest + self.extent(n, axis, vis);
        let by = if arriving { with / rest } else { rest / with };
        for c in hidden {
            self.scale(c, axis, by);
        }
    }

    /// Appends `w` as a row of its own along the stacking axis.
    pub fn insert_row(&mut self, w: W, vis: impl Fn(W) -> bool) {
        let size = self.root.map_or([1.0; 2], |r| self.size(r));
        let n = self.new_leaf(w, size);
        match self.root {
            None => self.root = Some(n),
            Some(r) if self.axis(r) == Some(self.stack) => {
                let end = self.children(r).len();
                self.attach(r, end, n);
                self.rescale_hidden(n, true, &vis);
            }
            Some(r) => {
                let c = self.new_container(self.stack);
                self.attach(c, 0, r);
                self.attach(c, 1, n);
                self.root = Some(c);
            }
        }
        self.reveal(n, true);
    }

    pub fn remove(&mut self, w: W, vis: impl Fn(W) -> bool) -> bool {
        let Some(&n) = self.leaves.get(&w) else {
            return false;
        };
        self.rescale_hidden(n, false, &vis);
        self.leaves.remove(&w);
        self.detach(n);
        self.nodes.remove(n);
        true
    }

    pub fn retain(&mut self, mut keep: impl FnMut(W) -> bool) {
        let gone: Vec<W> = self.windows().filter(|&w| !keep(w)).collect();
        for w in gone {
            self.remove(w, |_| false);
        }
    }

    /// Moves a window one step in `dir`. Leaves swap slots with the next
    /// visible sibling, enter a sibling container, or step out beside their
    /// container. Hidden windows never move, and an extended window moves
    /// its group as a rigid block.
    pub fn move_window(&mut self, w: W, dir: Dir, vis: impl Fn(W) -> bool) -> bool {
        let Some(&n) = self.leaves.get(&w).filter(|_| vis(w)) else {
            return false;
        };
        let block = self.group(w, &vis).unwrap_or(n);
        self.until_seen(&vis, |t| {
            let moved = t.move_node(block, dir, &vis, block == n);
            t.reveal(n, moved)
        })
    }

    /// Moves the group or container holding `w` as a block, merging it into
    /// the next lane in `dir` like `merge_window` when `merge` is set. A
    /// window sitting directly in the root is its own block.
    pub fn move_container(&mut self, w: W, dir: Dir, merge: bool, vis: impl Fn(W) -> bool) -> bool {
        let Some(&n) = self.leaves.get(&w).filter(|_| vis(w)) else {
            return false;
        };
        let group = self.group(w, &vis);
        self.until_seen(&vis, |t| {
            let block = group.unwrap_or_else(|| {
                t.nodes[n]
                    .parent
                    .filter(|&p| Some(p) != t.root)
                    .unwrap_or(n)
            });
            if merge {
                t.merge_node(n, block, dir, &vis)
            } else {
                let moved = t.move_node(block, dir, &vis, false);
                t.reveal(n, moved)
            }
        })
    }

    /// Moves a window to the end of the next visible lane in `dir` among its
    /// siblings. A lone window there becomes a stack with it. A window with no
    /// sibling lane that way leaves its stack as `move_window` would, so it
    /// takes one press to step out and another to merge. An extended window
    /// takes its group along.
    pub fn merge_window(&mut self, w: W, dir: Dir, vis: impl Fn(W) -> bool) -> bool {
        let Some(&n) = self.leaves.get(&w).filter(|_| vis(w)) else {
            return false;
        };
        let block = self.group(w, &vis).unwrap_or(n);
        self.until_seen(&vis, |t| t.merge_node(n, block, dir, &vis))
    }

    fn merge_node(&mut self, leaf: NodeId, n: NodeId, dir: Dir, vis: &impl Fn(W) -> bool) -> bool {
        if let Some((p, i)) = self.position(n)
            && self.axis(p) == Some(dir.axis())
            && let Some(j) = self.next_shown(p, i, dir, vis)
        {
            self.join_lane(n, p, j);
            return self.reveal(leaf, true);
        }
        let moved = self.move_node(n, dir, vis, true);
        self.reveal(leaf, moved)
    }

    /// The outermost container `w` is extended in, the block it moves as.
    fn group(&self, w: W, vis: &impl Fn(W) -> bool) -> Option<NodeId> {
        self.shown_path(w, vis)
            .into_iter()
            .take_while(|&(p, c)| self.expanded(p) == Some(c))
            .last()
            .map(|(p, _)| p)
    }

    /// Whether `w` is extended over windows it shares a container with.
    pub fn grouped(&self, w: W, vis: impl Fn(W) -> bool) -> bool {
        self.group(w, &vis).is_some()
    }

    /// The shown windows in the block `w` moves as, `w` alone when it is not
    /// extended.
    pub fn group_windows(&self, w: W, vis: impl Fn(W) -> bool) -> Vec<W> {
        let Some(g) = self.group(w, &vis) else {
            return vec![w];
        };
        let mut out = Vec::new();
        self.shown_leaves(g, &vis, &mut out);
        out
    }

    /// Whether a visible window extended over `w` takes all its room.
    pub fn eclipsed(&self, w: W, vis: impl Fn(W) -> bool) -> bool {
        let Some(&leaf) = self.leaves.get(&w) else {
            return false;
        };
        let mut cur = leaf;
        while let Some(p) = self.nodes[cur].parent {
            if self
                .expanded(p)
                .is_some_and(|e| e != cur && self.visible(e, &vis))
            {
                return true;
            }
            cur = p;
        }
        false
    }

    /// Repeats `step` until the visible layout changes, or undoes it all when
    /// it never does. Steps around hidden windows otherwise ate keypresses
    /// and rearranged windows the user could not see.
    fn until_seen(
        &mut self,
        vis: &impl Fn(W) -> bool,
        mut step: impl FnMut(&mut Self) -> bool,
    ) -> bool {
        let seen = |t: &Self| -> Vec<(W, Rect)> {
            t.arrange(Rect::new(0.0, 0.0, 1000.0, 1000.0), 0.0, vis)
                .into_iter()
                .filter(|p| vis(p.0))
                .collect()
        };
        let same = |a: &[(W, Rect)], b: &[(W, Rect)]| {
            a.len() == b.len()
                && a.iter().all(|(v, r)| {
                    b.iter().any(|(w, s)| {
                        v == w
                            && [r.x - s.x, r.y - s.y, r.w - s.w, r.h - s.h]
                                .iter()
                                .all(|d| d.abs() < 1e-6)
                    })
                })
        };
        let before = self.clone();
        let start = seen(self);
        for _ in 0..=before.nodes.len() {
            if !step(self) {
                break;
            }
            if !same(&start, &seen(self)) {
                return true;
            }
        }
        *self = before;
        false
    }

    /// Undoes any expansion along `leaf`'s ancestry that favours another
    /// child, once it has `moved` or arrived. An expanded container gives its
    /// other children no room, so a window moved into one vanished while
    /// staying focused.
    fn reveal(&mut self, leaf: NodeId, moved: bool) -> bool {
        let mut cur = leaf;
        while moved && let Some(p) = self.nodes[cur].parent {
            if let Kind::Container { expanded, .. } = &mut self.nodes[p].kind
                && expanded.is_some_and(|e| e != cur)
            {
                *expanded = None;
            }
            cur = p;
        }
        moved
    }

    /// Whether every container above `w` is expanded towards it.
    pub fn maximized(&self, w: W, vis: impl Fn(W) -> bool) -> bool {
        let path = self.shown_path(w, &vis);
        !path.is_empty() && path.iter().all(|&(p, c)| self.expanded(p) == Some(c))
    }

    /// `w`'s ancestry as (container, child) pairs, leaving out containers
    /// where the child has no visible sibling. Those look like nothing on
    /// screen, so expanding there would do nothing the user could see.
    fn shown_path(&self, w: W, vis: &impl Fn(W) -> bool) -> Vec<(NodeId, NodeId)> {
        let Some(&leaf) = self.leaves.get(&w) else {
            return Vec::new();
        };
        let mut path = Vec::new();
        let mut cur = leaf;
        while let Some(p) = self.nodes[cur].parent {
            let shared = self
                .children(p)
                .iter()
                .any(|&c| c != cur && self.visible(c, vis));
            if shared {
                path.push((p, cur));
            }
            cur = p;
        }
        path
    }

    /// Transposes the whole tree.
    pub fn flip(&mut self) {
        self.stack = self.stack.other();
        for node in self.nodes.values_mut() {
            match &mut node.kind {
                Kind::Container { axis, .. } => *axis = axis.other(),
                Kind::Leaf(_, size) => size.reverse(),
            }
        }
    }

    /// Toggles expansion for `count` levels of `w`'s visible ancestry,
    /// starting `skip` levels up. Level 0 expands the window inside the
    /// nearest container where it has a visible sibling.
    pub fn toggle_expand(
        &mut self,
        w: W,
        skip: usize,
        count: usize,
        vis: impl Fn(W) -> bool,
    ) -> bool {
        let path: Vec<_> = self
            .shown_path(w, &vis)
            .into_iter()
            .skip(skip)
            .take(count)
            .collect();
        if path.is_empty() {
            return false;
        }
        let all = path.iter().all(|&(p, c)| self.expanded(p) == Some(c));
        for (p, c) in path {
            if let Kind::Container { expanded, .. } = &mut self.nodes[p].kind {
                *expanded = (!all).then_some(c);
            }
        }
        true
    }

    /// Grows `w` by `delta`, a fraction of the visible length of the nearest
    /// container along `axis` where it has a visible sibling. Hidden siblings
    /// keep their sizes, and with them their share.
    pub fn resize(&mut self, w: W, axis: Axis, delta: f64, vis: impl Fn(W) -> bool) -> bool {
        let Some(&leaf) = self.leaves.get(&w) else {
            return false;
        };
        let mut cur = leaf;
        while let Some(p) = self.nodes[cur].parent {
            if self.axis(p) == Some(axis) {
                let shown: Vec<(NodeId, f64)> = self
                    .children(p)
                    .iter()
                    .filter(|&&c| self.visible(c, &vis))
                    .map(|&c| (c, self.extent(c, axis, &vis)))
                    .collect();
                if shown.len() >= 2 {
                    let sum: f64 = shown.iter().map(|s| s.1).sum();
                    let old = self.extent(cur, axis, &vis);
                    let max = 1.0 - MIN_SHARE * (shown.len() - 1) as f64;
                    let new = (old / sum + delta).clamp(MIN_SHARE, max) * sum;
                    let scale = (sum - new) / (sum - old);
                    for (c, _) in shown {
                        self.scale(c, axis, if c == cur { new / old } else { scale });
                    }
                    return true;
                }
            }
            cur = p;
        }
        false
    }

    /// Gives every visible child of the nearest container where `w` has a
    /// visible sibling an equal share along that container's axis.
    pub fn balance(&mut self, w: W, vis: impl Fn(W) -> bool) -> bool {
        let Some(&(p, _)) = self.shown_path(w, &vis).first() else {
            return false;
        };
        let Some(axis) = self.axis(p) else {
            return false;
        };
        let shown: Vec<(NodeId, f64)> = self
            .children(p)
            .iter()
            .filter(|&&c| self.visible(c, &vis))
            .map(|&c| (c, self.extent(c, axis, &vis)))
            .collect();
        let mean = shown.iter().map(|s| s.1).sum::<f64>() / shown.len() as f64;
        for (c, e) in shown {
            if e > 0.0 {
                self.scale(c, axis, mean / e);
            }
        }
        true
    }

    /// The lane a window's split on side `dir` lives in, as the child holding
    /// the window, its parent and the index of the visible sibling across
    /// the split.
    fn split_across(
        &self,
        w: W,
        dir: Dir,
        vis: &impl Fn(W) -> bool,
    ) -> Option<(NodeId, NodeId, usize)> {
        let mut cur = *self.leaves.get(&w)?;
        if !self.visible(cur, vis) {
            return None;
        }
        while let Some((p, i)) = self.position(cur) {
            if self.axis(p) == Some(dir.axis())
                && let Some(j) = self.next_shown(p, i, dir, vis)
            {
                return Some((cur, p, j));
            }
            cur = p;
        }
        None
    }

    /// Whether the split on side `dir` of `w` has a visible window across it.
    pub fn has_split(&self, w: W, dir: Dir, vis: impl Fn(W) -> bool) -> bool {
        self.split_across(w, dir, &vis).is_some()
    }

    /// Moves the split on side `dir` of `w` by `px` along that side's axis,
    /// positive toward the right or bottom. Only the two children meeting at
    /// the split change, so the split follows the pointer.
    pub fn move_split(
        &mut self,
        w: W,
        dir: Dir,
        px: f64,
        area: Rect,
        gap: f64,
        vis: impl Fn(W) -> bool,
    ) -> bool {
        let Some((cur, p, j)) = self.split_across(w, dir, &vis) else {
            return false;
        };
        let axis = dir.axis();
        let other = self.children(p)[j];
        let (first, second) = if dir.forward() {
            (cur, other)
        } else {
            (other, cur)
        };
        let mut leaves = Vec::new();
        self.shown_leaves(first, &vis, &mut leaves);
        let (start, end) = self
            .arrange(area, gap, &vis)
            .iter()
            .filter(|(l, _)| leaves.contains(l))
            .map(|(_, r)| span(*r, axis))
            .fold((f64::MAX, f64::MIN), |(s, e), (rs, rl)| {
                (s.min(rs), e.max(rs + rl))
            });
        let ef = self.extent(first, axis, &vis);
        let es = self.extent(second, axis, &vis);
        if end <= start || ef <= 0.0 || es <= 0.0 {
            return true;
        }
        let sum: f64 = self
            .children(p)
            .iter()
            .filter(|&&c| self.visible(c, &vis))
            .map(|&c| self.extent(c, axis, &vis))
            .sum();
        let min = MIN_SHARE * sum;
        let du = (px * ef / (end - start)).clamp(-(ef - min).max(0.0), (es - min).max(0.0));
        self.scale(first, axis, (ef + du) / ef);
        self.scale(second, axis, (es - du) / es);
        true
    }

    fn shown_leaves(&self, n: NodeId, vis: &impl Fn(W) -> bool, out: &mut Vec<W>) {
        match &self.nodes[n].kind {
            Kind::Leaf(w, _) => {
                if vis(*w) {
                    out.push(*w);
                }
            }
            Kind::Container { children, .. } => {
                for &c in children {
                    self.shown_leaves(c, vis, out);
                }
            }
        }
    }

    /// Scales every window under `n` along `axis`, hidden ones too, so they
    /// keep their proportions for when they are shown again.
    fn scale(&mut self, n: NodeId, axis: Axis, by: f64) {
        match &mut self.nodes[n].kind {
            Kind::Leaf(_, size) => size[axis.index()] *= by,
            Kind::Container { children, .. } => {
                for c in children.clone() {
                    self.scale(c, axis, by);
                }
            }
        }
    }

    /// How much room `n` asks for along `axis` among its siblings. A
    /// container asks for the mean of what its visible children ask for, so
    /// windows of other tags sharing a lane change nothing on screen, and a
    /// window carries its own size wherever it moves.
    fn extent(&self, n: NodeId, axis: Axis, vis: &impl Fn(W) -> bool) -> f64 {
        match &self.nodes[n].kind {
            Kind::Leaf(_, size) => size[axis.index()],
            Kind::Container { children, .. } => {
                let shown: Vec<f64> = children
                    .iter()
                    .filter(|&&c| self.visible(c, vis))
                    .map(|&c| self.extent(c, axis, vis))
                    .collect();
                if shown.is_empty() {
                    children
                        .iter()
                        .map(|&c| self.extent(c, axis, vis))
                        .sum::<f64>()
                        / children.len() as f64
                } else {
                    shown.iter().sum::<f64>() / shown.len() as f64
                }
            }
        }
    }

    /// The size a window placed in `n`'s stead would take, ignoring
    /// visibility since new windows land on any tag.
    fn size(&self, n: NodeId) -> Size {
        let all = |_: W| true;
        [
            self.extent(n, Axis::Horizontal, &all),
            self.extent(n, Axis::Vertical, &all),
        ]
    }

    /// Lays the tree out in `area`. Hidden windows come back as zero-size
    /// rects on the boundary where they would reappear.
    pub fn arrange(&self, area: Rect, gap: f64, vis: impl Fn(W) -> bool) -> Vec<(W, Rect)> {
        let mut out = Vec::with_capacity(self.leaves.len());
        if let Some(r) = self.root {
            let area = if self.visible(r, &vis) {
                area
            } else if area.w >= area.h {
                Rect::new(area.right(), area.y, 0.0, area.h)
            } else {
                Rect::new(area.x, area.bottom(), area.w, 0.0)
            };
            self.place(r, area, gap, &vis, &mut out);
        }
        out
    }

    fn place(
        &self,
        n: NodeId,
        r: Rect,
        gap: f64,
        vis: &impl Fn(W) -> bool,
        out: &mut Vec<(W, Rect)>,
    ) {
        let (axis, children, expanded) = match &self.nodes[n].kind {
            Kind::Leaf(w, _) => return out.push((*w, r)),
            Kind::Container {
                axis,
                children,
                expanded,
            } => (*axis, children, *expanded),
        };
        let shown: Vec<bool> = children.iter().map(|&c| self.visible(c, vis)).collect();
        let (start, len) = span(r, axis);
        if let Some(e) = expanded.and_then(|e| children.iter().position(|&c| c == e))
            && shown[e]
        {
            for (i, &c) in children.iter().enumerate() {
                let sub = match i.cmp(&e) {
                    std::cmp::Ordering::Equal => r,
                    std::cmp::Ordering::Less => with_span(r, axis, start, 0.0),
                    std::cmp::Ordering::Greater => with_span(r, axis, start + len, 0.0),
                };
                self.place(c, sub, gap, vis, out);
            }
            return;
        }
        let count = shown.iter().filter(|s| **s).count();
        let extents: Vec<f64> = children
            .iter()
            .zip(&shown)
            .map(|(&c, &s)| if s { self.extent(c, axis, vis) } else { 0.0 })
            .collect();
        let total: f64 = extents.iter().sum();
        let gaps = count.saturating_sub(1) as f64;
        let gap = if gaps > 0.0 { gap.min(len / gaps) } else { gap };
        let avail = len - gap * gaps;
        let last = shown.iter().rposition(|s| *s);
        let mut pos = start;
        let mut seen = false;
        for (i, &c) in children.iter().enumerate() {
            if shown[i] {
                if seen {
                    pos += gap;
                }
                let l = avail * extents[i] / total;
                self.place(c, with_span(r, axis, pos, l), gap, vis, out);
                pos += l;
                seen = true;
            } else {
                let between = seen && last.is_some_and(|l| l > i);
                let at = if between { pos + gap / 2.0 } else { pos };
                self.place(c, with_span(r, axis, at, 0.0), gap, vis, out);
            }
        }
    }

    fn move_node(&mut self, n: NodeId, dir: Dir, vis: &impl Fn(W) -> bool, enter: bool) -> bool {
        let mut cur = n;
        while let Some((p, i)) = self.position(cur) {
            if self.axis(p) == Some(dir.axis()) {
                let hidden_lane = self
                    .adjacent(p, i, dir)
                    .filter(|&j| enter && !self.visible(self.children(p)[j], vis));
                if cur != n {
                    if let Some(j) = hidden_lane {
                        self.join_lane(n, p, j);
                    } else {
                        let at = if dir.forward() { i + 1 } else { i };
                        self.relocate(n, p, at);
                    }
                    return true;
                }
                if let Some(j) = self.next_shown(p, i, dir, vis) {
                    let sib = self.children(p)[j];
                    if enter && self.shown_windows(sib, vis) > 1 {
                        self.join_lane(n, p, j);
                    } else {
                        let children = self.children_mut(p);
                        children.swap(i, j);
                    }
                    return true;
                }
                if let Some(j) = hidden_lane {
                    self.join_lane(n, p, j);
                    return true;
                }
            }
            cur = p;
        }
        if cur == n || self.axis(cur) == Some(dir.axis()) {
            return false;
        }
        let (old, i) = self.position(n).expect("n is below the root");
        self.unlink(old, i);
        self.normalize(old);
        let r = self.root.expect("the rest of the tree survives");
        if self.axis(r) == Some(dir.axis()) {
            let at = if dir.forward() {
                self.children(r).len()
            } else {
                0
            };
            self.attach(r, at, n);
        } else {
            let c = self.new_container(dir.axis());
            self.attach(c, 0, r);
            let at = if dir.forward() {
                self.children(c).len()
            } else {
                0
            };
            self.attach(c, at, n);
            self.root = Some(c);
        }
        true
    }

    fn next_shown(&self, p: NodeId, i: usize, dir: Dir, vis: &impl Fn(W) -> bool) -> Option<usize> {
        let children = self.children(p);
        if dir.forward() {
            (i + 1..children.len()).find(|&j| self.visible(children[j], vis))
        } else {
            (0..i).rev().find(|&j| self.visible(children[j], vis))
        }
    }

    fn adjacent(&self, p: NodeId, i: usize, dir: Dir) -> Option<usize> {
        let j = if dir.forward() {
            i + 1
        } else {
            i.checked_sub(1)?
        };
        (j < self.children(p).len()).then_some(j)
    }

    /// Moves `n` to the end of the lane at `p`'s child `j`. A lone window
    /// there becomes a lane of its own, perpendicular to `p`.
    fn join_lane(&mut self, n: NodeId, p: NodeId, j: usize) {
        let lane = self.children(p)[j];
        let lane = if self.axis(lane).is_some() {
            lane
        } else {
            let c = self.new_container(self.axis(p).expect("p is a container").other());
            self.children_mut(p)[j] = c;
            self.nodes[c].parent = Some(p);
            if let Kind::Container { expanded, .. } = &mut self.nodes[p].kind
                && *expanded == Some(lane)
            {
                *expanded = Some(c);
            }
            self.attach(c, 0, lane);
            c
        };
        let end = self.children(lane).len();
        self.relocate(n, lane, end);
    }

    fn relocate(&mut self, n: NodeId, p: NodeId, at: usize) {
        let (old, i) = self.position(n).expect("relocated nodes have a parent");
        let at = if old == p && i < at { at - 1 } else { at };
        self.unlink(old, i);
        self.attach(p, at, n);
        self.normalize(old);
    }

    /// Places `node` among `p`'s children. A container running along `p`'s
    /// axis is dissolved into `p` so axes keep alternating, unless it holds an
    /// extended window, whose group is turned across instead to survive.
    fn attach(&mut self, p: NodeId, at: usize, node: NodeId) {
        if self.axis(node).is_some() && self.axis(node) == self.axis(p) {
            if self.expanded(node).is_some() {
                self.transpose(node);
                self.nodes[node].parent = Some(p);
                self.children_mut(p).insert(at, node);
                return;
            }
            let children = self.children(node).to_vec();
            self.nodes.remove(node);
            for (k, &c) in children.iter().enumerate() {
                self.nodes[c].parent = Some(p);
                self.children_mut(p).insert(at + k, c);
            }
        } else {
            self.nodes[node].parent = Some(p);
            self.children_mut(p).insert(at, node);
        }
    }

    fn unlink(&mut self, p: NodeId, i: usize) {
        let child = self.unlink_dead(p, i);
        self.nodes[child].parent = None;
    }

    fn detach(&mut self, n: NodeId) {
        match self.position(n) {
            Some((p, i)) => {
                self.unlink(p, i);
                self.normalize(p);
            }
            None => self.root = None,
        }
    }

    fn transpose(&mut self, n: NodeId) {
        match &mut self.nodes[n].kind {
            Kind::Container { axis, children, .. } => {
                *axis = axis.other();
                for c in children.clone() {
                    self.transpose(c);
                }
            }
            Kind::Leaf(_, size) => size.reverse(),
        }
    }

    /// Repairs a container that lost a child.
    fn normalize(&mut self, c: NodeId) {
        if self.children(c).len() >= 2 {
            return;
        }
        let pos = self.position(c);
        let was_expanded = pos.is_some_and(|(p, _)| self.expanded(p) == Some(c));
        let Some(Node {
            kind: Kind::Container { children, .. },
            ..
        }) = self.nodes.remove(c)
        else {
            unreachable!("only containers are normalized");
        };
        let only = children.into_iter().next();
        match (only, pos) {
            (None, Some((p, i))) => {
                self.unlink_dead(p, i);
                self.normalize(p);
            }
            (None, None) => self.root = None,
            (Some(only), Some((p, i))) => {
                self.unlink_dead(p, i);
                self.attach(p, i, only);
                if was_expanded
                    && self.nodes.contains_key(only)
                    && let Kind::Container { expanded, .. } = &mut self.nodes[p].kind
                {
                    *expanded = Some(only);
                }
            }
            (Some(only), None) => {
                self.nodes[only].parent = None;
                self.root = Some(only);
            }
        }
    }

    /// Like `unlink`, for a child whose node is already gone.
    fn unlink_dead(&mut self, p: NodeId, i: usize) -> NodeId {
        let Kind::Container {
            children, expanded, ..
        } = &mut self.nodes[p].kind
        else {
            unreachable!("parents are containers");
        };
        let child = children.remove(i);
        if *expanded == Some(child) {
            *expanded = None;
        }
        child
    }

    fn new_leaf(&mut self, w: W, size: Size) -> NodeId {
        let n = self.nodes.insert(Node {
            parent: None,
            kind: Kind::Leaf(w, size),
        });
        self.leaves.insert(w, n);
        n
    }

    fn new_container(&mut self, axis: Axis) -> NodeId {
        self.nodes.insert(Node {
            parent: None,
            kind: Kind::Container {
                axis,
                children: Vec::new(),
                expanded: None,
            },
        })
    }

    fn position(&self, n: NodeId) -> Option<(NodeId, usize)> {
        let p = self.nodes[n].parent?;
        let i = self.children(p).iter().position(|&c| c == n)?;
        Some((p, i))
    }

    fn axis(&self, n: NodeId) -> Option<Axis> {
        match &self.nodes[n].kind {
            Kind::Container { axis, .. } => Some(*axis),
            Kind::Leaf(..) => None,
        }
    }

    fn expanded(&self, n: NodeId) -> Option<NodeId> {
        match &self.nodes[n].kind {
            Kind::Container { expanded, .. } => *expanded,
            Kind::Leaf(..) => None,
        }
    }

    fn children(&self, n: NodeId) -> &[NodeId] {
        match &self.nodes[n].kind {
            Kind::Container { children, .. } => children,
            Kind::Leaf(..) => &[],
        }
    }

    fn children_mut(&mut self, n: NodeId) -> &mut Vec<NodeId> {
        match &mut self.nodes[n].kind {
            Kind::Container { children, .. } => children,
            Kind::Leaf(..) => unreachable!("leaves have no children"),
        }
    }

    fn visible(&self, n: NodeId, vis: &impl Fn(W) -> bool) -> bool {
        match &self.nodes[n].kind {
            Kind::Leaf(w, _) => vis(*w),
            Kind::Container { children, .. } => children.iter().any(|&c| self.visible(c, vis)),
        }
    }

    fn shown_windows(&self, n: NodeId, vis: &impl Fn(W) -> bool) -> usize {
        match &self.nodes[n].kind {
            Kind::Leaf(w, _) => usize::from(vis(*w)),
            Kind::Container { children, .. } => {
                children.iter().map(|&c| self.shown_windows(c, vis)).sum()
            }
        }
    }

    #[cfg(test)]
    pub(crate) fn shape(&self) -> String
    where
        W: std::fmt::Debug,
    {
        fn go<W: Copy + Eq + Hash + std::fmt::Debug>(t: &Tree<W>, n: NodeId) -> String {
            match &t.nodes[n].kind {
                Kind::Leaf(w, [x, y]) => format!("{w:?}[{x:.6},{y:.6}]"),
                Kind::Container {
                    axis,
                    children,
                    expanded,
                } => {
                    let inner: Vec<String> = children.iter().map(|&c| go(t, c)).collect();
                    let e = expanded.and_then(|e| children.iter().position(|&c| c == e));
                    format!("{axis:?}{e:?}({})", inner.join(" "))
                }
            }
        }
        self.root.map(|r| go(self, r)).unwrap_or_default()
    }

    #[cfg(test)]
    pub(crate) fn check(&self) {
        let reachable = match self.root {
            Some(r) => {
                assert!(self.nodes[r].parent.is_none());
                self.check_node(r)
            }
            None => 0,
        };
        assert_eq!(reachable, self.nodes.len(), "orphaned nodes");
        for (&w, &n) in &self.leaves {
            assert!(matches!(self.nodes[n].kind, Kind::Leaf(x, _) if x == w));
        }
    }

    #[cfg(test)]
    fn check_node(&self, n: NodeId) -> usize {
        match &self.nodes[n].kind {
            Kind::Leaf(_, size) => {
                assert!(
                    size.iter().all(|s| *s > 0.0 && s.is_finite()),
                    "size {size:?}"
                );
                1
            }
            Kind::Container {
                axis,
                children,
                expanded,
            } => {
                assert!(
                    children.len() >= 2,
                    "container with {} children",
                    children.len()
                );
                if let Some(e) = expanded {
                    assert!(children.contains(e));
                }
                let mut count = 1;
                for &c in children {
                    assert_eq!(self.nodes[c].parent, Some(n));
                    assert_ne!(self.axis(c), Some(*axis), "axes must alternate");
                    count += self.check_node(c);
                }
                count
            }
        }
    }
}

fn span(r: Rect, axis: Axis) -> (f64, f64) {
    match axis {
        Axis::Horizontal => (r.x, r.w),
        Axis::Vertical => (r.y, r.h),
    }
}

fn with_span(r: Rect, axis: Axis, start: f64, len: f64) -> Rect {
    match axis {
        Axis::Horizontal => Rect::new(start, r.y, len, r.h),
        Axis::Vertical => Rect::new(r.x, start, r.w, len),
    }
}