monolith

public

Star0

Watch0

121 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,
        }
    }
}

#[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;

#[derive(Clone, Debug)]
struct Child {
    node: NodeId,
    weight: f64,
}

#[derive(Clone, Debug)]
enum Kind<W> {
    Leaf(W),
    Container {
        axis: Axis,
        children: Vec<Child>,
        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) {
        let Some(&a) = self.leaves.get(&anchor) else {
            return self.insert_row(w);
        };
        let n = self.new_leaf(w);
        match self.position(a) {
            Some((p, i)) if Some(p) == self.root && self.axis(p) == Some(self.stack) => {
                let weight = self.unlink(p, i).weight;
                let c = self.new_container(self.stack.other());
                self.attach(c, 0, a, 1.0);
                self.attach(c, 1, n, 1.0);
                self.attach(p, i, c, weight);
            }
            Some((p, i)) => {
                let weight = self.mean_weight(p);
                self.attach(p, i + 1, n, weight);
            }
            None => {
                let c = self.new_container(self.stack.other());
                self.attach(c, 0, a, 1.0);
                self.attach(c, 1, n, 1.0);
                self.root = Some(c);
            }
        }
    }

    /// Appends `w` as a row of its own along the stacking axis.
    pub fn insert_row(&mut self, w: W) {
        let n = self.new_leaf(w);
        match self.root {
            None => self.root = Some(n),
            Some(r) if self.axis(r) == Some(self.stack) => {
                let weight = self.mean_weight(r);
                let end = self.children(r).len();
                self.attach(r, end, n, weight);
            }
            Some(r) => {
                let c = self.new_container(self.stack);
                self.attach(c, 0, r, 1.0);
                self.attach(c, 1, n, 1.0);
                self.root = Some(c);
            }
        }
    }

    pub fn remove(&mut self, w: W) -> bool {
        let Some(n) = self.leaves.remove(&w) else {
            return false;
        };
        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);
        }
    }

    /// 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.
    pub fn move_window(&mut self, w: W, dir: Dir, vis: impl Fn(W) -> bool) -> bool {
        let Some(&n) = self.leaves.get(&w) else {
            return false;
        };
        self.move_node(n, dir, &vis, true)
    }

    /// Moves the container holding `w` as a rigid block. A window sitting
    /// directly in the root is its own block.
    pub fn move_container(&mut self, w: W, dir: Dir, vis: impl Fn(W) -> bool) -> bool {
        let Some(&n) = self.leaves.get(&w) else {
            return false;
        };
        let block = self.nodes[n]
            .parent
            .filter(|&p| Some(p) != self.root)
            .unwrap_or(n);
        self.move_node(block, dir, &vis, false)
    }

    /// 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.
    pub fn merge_window(&mut self, w: W, dir: Dir, vis: impl Fn(W) -> bool) -> bool {
        let Some(&n) = self.leaves.get(&w) else {
            return false;
        };
        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 true;
        }
        self.move_node(n, dir, &vis, true)
    }

    /// 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.node != cur && self.visible(c.node, 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() {
            if let Kind::Container { axis, .. } = &mut node.kind {
                *axis = axis.other();
            }
        }
    }

    /// 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 weights, 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, i)) = self.position(cur) {
            if self.axis(p) == Some(axis) {
                let shown: Vec<usize> = (0..self.children(p).len())
                    .filter(|&j| self.visible(self.children(p)[j].node, &vis))
                    .collect();
                if shown.len() >= 2 {
                    let children = self.children_mut(p);
                    let sum: f64 = shown.iter().map(|&j| children[j].weight).sum();
                    let old = children[i].weight;
                    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 j in shown {
                        children[j].weight = if j == i {
                            new
                        } else {
                            children[j].weight * scale
                        };
                    }
                    return true;
                }
            }
            cur = p;
        }
        false
    }

    /// 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 {
                Rect::new(area.x + area.w / 2.0, area.y, 0.0, area.h)
            };
            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.node, vis)).collect();
        let (start, len) = span(r, axis);
        if let Some(e) = expanded.and_then(|e| children.iter().position(|c| c.node == 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.node, sub, gap, vis, out);
            }
            return;
        }
        let count = shown.iter().filter(|s| **s).count();
        let total: f64 = children
            .iter()
            .zip(&shown)
            .filter(|(_, s)| **s)
            .map(|(c, _)| c.weight)
            .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 * c.weight / total;
                self.place(c.node, 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.node, 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].node, 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].node;
                    if enter && self.axis(sib).is_some() {
                        let end = self.children(sib).len();
                        self.relocate(n, sib, end);
                    } else {
                        let children = self.children_mut(p);
                        children[i].node = sib;
                        children[j].node = n;
                    }
                    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 weight = self.mean_weight(r);
            let at = if dir.forward() {
                self.children(r).len()
            } else {
                0
            };
            self.attach(r, at, n, weight);
        } else {
            let c = self.new_container(dir.axis());
            self.attach(c, 0, r, 1.0);
            let at = if dir.forward() {
                self.children(c).len()
            } else {
                0
            };
            self.attach(c, at, n, 1.0);
            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].node, vis))
        } else {
            (0..i).rev().find(|&j| self.visible(children[j].node, 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].node;
        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].node = 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, 1.0);
            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 weight = self.mean_weight(p);
        let at = if old == p && i < at { at - 1 } else { at };
        self.unlink(old, i);
        self.attach(p, at, n, weight);
        self.normalize(old);
    }

    /// Places `node` among `p`'s children. A container running along `p`'s
    /// axis is dissolved into `p` so axes keep alternating.
    fn attach(&mut self, p: NodeId, at: usize, node: NodeId, weight: f64) {
        if self.axis(node) == self.axis(p) {
            let Some(Node {
                kind: Kind::Container { children, .. },
                ..
            }) = self.nodes.remove(node)
            else {
                unreachable!("only containers have an axis");
            };
            let total: f64 = children.iter().map(|c| c.weight).sum();
            for (k, c) in children.into_iter().enumerate() {
                self.nodes[c.node].parent = Some(p);
                let weight = weight * c.weight / total;
                self.children_mut(p).insert(
                    at + k,
                    Child {
                        node: c.node,
                        weight,
                    },
                );
            }
        } else {
            self.nodes[node].parent = Some(p);
            self.children_mut(p).insert(at, Child { node, weight });
        }
    }

    fn unlink(&mut self, p: NodeId, i: usize) -> Child {
        let Kind::Container {
            children, expanded, ..
        } = &mut self.nodes[p].kind
        else {
            unreachable!("parents are containers");
        };
        let child = children.remove(i);
        if *expanded == Some(child.node) {
            *expanded = None;
        }
        self.nodes[child.node].parent = None;
        child
    }

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

    /// 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))) => {
                let weight = self.unlink_dead(p, i).weight;
                let leaf_like = self.axis(only.node) != self.axis(p);
                self.attach(p, i, only.node, weight);
                if was_expanded
                    && leaf_like
                    && let Kind::Container { expanded, .. } = &mut self.nodes[p].kind
                {
                    *expanded = Some(only.node);
                }
            }
            (Some(only), None) => {
                self.nodes[only.node].parent = None;
                self.root = Some(only.node);
            }
        }
    }

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

    fn new_leaf(&mut self, w: W) -> NodeId {
        let n = self.nodes.insert(Node {
            parent: None,
            kind: Kind::Leaf(w),
        });
        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.node == 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) -> &[Child] {
        match &self.nodes[n].kind {
            Kind::Container { children, .. } => children,
            Kind::Leaf(_) => &[],
        }
    }

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

    fn mean_weight(&self, p: NodeId) -> f64 {
        let children = self.children(p);
        if children.is_empty() {
            1.0
        } else {
            children.iter().map(|c| c.weight).sum::<f64>() / children.len() as f64
        }
    }

    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.node, vis)),
        }
    }

    #[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(_) => 1,
            Kind::Container {
                axis,
                children,
                expanded,
            } => {
                assert!(
                    children.len() >= 2,
                    "container with {} children",
                    children.len()
                );
                if let Some(e) = expanded {
                    assert!(children.iter().any(|c| c.node == *e));
                }
                let mut count = 1;
                for c in children {
                    assert!(c.weight > 0.0 && c.weight.is_finite());
                    assert_eq!(self.nodes[c.node].parent, Some(n));
                    assert_ne!(self.axis(c.node), Some(*axis), "axes must alternate");
                    count += self.check_node(c.node);
                }
                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),
    }
}

1	use monolith_planner::Rect;
2	use slotmap::{SlotMap, new_key_type};
3	use std::collections::HashMap;
4	use std::hash::Hash;
5
6	new_key_type! { pub struct NodeId; }
7
8	#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
9	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
10	#[cfg_attr(feature = "serde", serde(rename_all = "kebab-case"))]
11	pub enum Axis {
12	Horizontal,
13	Vertical,
14	}
15
16	impl Axis {
17	pub fn other(self) -> Self {
18	match self {
19	Self::Horizontal => Self::Vertical,
20	Self::Vertical => Self::Horizontal,
21	}
22	}
23	}
24
25	#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
26	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
27	#[cfg_attr(feature = "serde", serde(rename_all = "kebab-case"))]
28	pub enum Dir {
29	Left,
30	Right,
31	Up,
32	Down,
33	}
34
35	impl Dir {
36	pub fn axis(self) -> Axis {
37	match self {
38	Self::Left \| Self::Right => Axis::Horizontal,
39	Self::Up \| Self::Down => Axis::Vertical,
40	}
41	}
42
43	pub fn forward(self) -> bool {
44	matches!(self, Self::Right \| Self::Down)
45	}
46	}
47
48	const MIN_SHARE: f64 = 0.05;
49
50	#[derive(Clone, Debug)]
51	struct Child {
52	node: NodeId,
53	weight: f64,
54	}
55
56	#[derive(Clone, Debug)]
57	enum Kind<W> {
58	Leaf(W),
59	Container {
60	axis: Axis,
61	children: Vec<Child>,
62	expanded: Option<NodeId>,
63	},
64	}
65
66	#[derive(Clone, Debug)]
67	struct Node<W> {
68	parent: Option<NodeId>,
69	kind: Kind<W>,
70	}
71
72	/// One output's tiling tree. Every tiled window of every tag lives here, the
73	/// caller's visibility filter decides which ones take space.
74	///
75	/// Children run on the axis opposite their parent. Containers hold at least
76	/// two children, hidden ones included, and a container left with one child
77	/// is replaced by it.
78	#[derive(Clone, Debug)]
79	pub struct Tree<W> {
80	nodes: SlotMap<NodeId, Node<W>>,
81	root: Option<NodeId>,
82	leaves: HashMap<W, NodeId>,
83	stack: Axis,
84	}
85
86	impl<W: Copy + Eq + Hash> Default for Tree<W> {
87	fn default() -> Self {
88	Self {
89	nodes: SlotMap::with_key(),
90	root: None,
91	leaves: HashMap::new(),
92	stack: Axis::Vertical,
93	}
94	}
95	}
96
97	impl<W: Copy + Eq + Hash> Tree<W> {
98	/// The axis tag rows stack along.
99	pub fn stack_axis(&self) -> Axis {
100	self.stack
101	}
102
103	pub fn contains(&self, w: W) -> bool {
104	self.leaves.contains_key(&w)
105	}
106
107	pub fn is_empty(&self) -> bool {
108	self.root.is_none()
109	}
110
111	pub fn windows(&self) -> impl Iterator<Item = W> + '_ {
112	self.leaves.keys().copied()
113	}
114
115	/// Inserts `w` as the next sibling of `anchor`, or as a new row if
116	/// `anchor` is not in the tree.
117	pub fn insert_after(&mut self, w: W, anchor: W) {
118	let Some(&a) = self.leaves.get(&anchor) else {
119	return self.insert_row(w);
120	};
121	let n = self.new_leaf(w);
122	match self.position(a) {
123	Some((p, i)) if Some(p) == self.root && self.axis(p) == Some(self.stack) => {
124	let weight = self.unlink(p, i).weight;
125	let c = self.new_container(self.stack.other());
126	self.attach(c, 0, a, 1.0);
127	self.attach(c, 1, n, 1.0);
128	self.attach(p, i, c, weight);
129	}
130	Some((p, i)) => {
131	let weight = self.mean_weight(p);
132	self.attach(p, i + 1, n, weight);
133	}
134	None => {
135	let c = self.new_container(self.stack.other());
136	self.attach(c, 0, a, 1.0);
137	self.attach(c, 1, n, 1.0);
138	self.root = Some(c);
139	}
140	}
141	}
142
143	/// Appends `w` as a row of its own along the stacking axis.
144	pub fn insert_row(&mut self, w: W) {
145	let n = self.new_leaf(w);
146	match self.root {
147	None => self.root = Some(n),
148	Some(r) if self.axis(r) == Some(self.stack) => {
149	let weight = self.mean_weight(r);
150	let end = self.children(r).len();
151	self.attach(r, end, n, weight);
152	}
153	Some(r) => {
154	let c = self.new_container(self.stack);
155	self.attach(c, 0, r, 1.0);
156	self.attach(c, 1, n, 1.0);
157	self.root = Some(c);
158	}
159	}
160	}
161
162	pub fn remove(&mut self, w: W) -> bool {
163	let Some(n) = self.leaves.remove(&w) else {
164	return false;
165	};
166	self.detach(n);
167	self.nodes.remove(n);
168	true
169	}
170
171	pub fn retain(&mut self, mut keep: impl FnMut(W) -> bool) {
172	let gone: Vec<W> = self.windows().filter(\|&w\| !keep(w)).collect();
173	for w in gone {
174	self.remove(w);
175	}
176	}
177
178	/// Moves a window one step in `dir`. Leaves swap slots with the next
179	/// visible sibling, enter a sibling container, or step out beside their
180	/// container. Hidden windows never move.
181	pub fn move_window(&mut self, w: W, dir: Dir, vis: impl Fn(W) -> bool) -> bool {
182	let Some(&n) = self.leaves.get(&w) else {
183	return false;
184	};
185	self.move_node(n, dir, &vis, true)
186	}
187
188	/// Moves the container holding `w` as a rigid block. A window sitting
189	/// directly in the root is its own block.
190	pub fn move_container(&mut self, w: W, dir: Dir, vis: impl Fn(W) -> bool) -> bool {
191	let Some(&n) = self.leaves.get(&w) else {
192	return false;
193	};
194	let block = self.nodes[n]
195	.parent
196	.filter(\|&p\| Some(p) != self.root)
197	.unwrap_or(n);
198	self.move_node(block, dir, &vis, false)
199	}
200
201	/// Moves a window to the end of the next visible lane in `dir` among its
202	/// siblings. A lone window there becomes a stack with it. A window with no
203	/// sibling lane that way leaves its stack as `move_window` would, so it
204	/// takes one press to step out and another to merge.
205	pub fn merge_window(&mut self, w: W, dir: Dir, vis: impl Fn(W) -> bool) -> bool {
206	let Some(&n) = self.leaves.get(&w) else {
207	return false;
208	};
209	if let Some((p, i)) = self.position(n)
210	&& self.axis(p) == Some(dir.axis())
211	&& let Some(j) = self.next_shown(p, i, dir, &vis)
212	{
213	self.join_lane(n, p, j);
214	return true;
215	}
216	self.move_node(n, dir, &vis, true)
217	}
218
219	/// Whether every container above `w` is expanded towards it.
220	pub fn maximized(&self, w: W, vis: impl Fn(W) -> bool) -> bool {
221	let path = self.shown_path(w, &vis);
222	!path.is_empty() && path.iter().all(\|&(p, c)\| self.expanded(p) == Some(c))
223	}
224
225	/// `w`'s ancestry as (container, child) pairs, leaving out containers
226	/// where the child has no visible sibling. Those look like nothing on
227	/// screen, so expanding there would do nothing the user could see.
228	fn shown_path(&self, w: W, vis: &impl Fn(W) -> bool) -> Vec<(NodeId, NodeId)> {
229	let Some(&leaf) = self.leaves.get(&w) else {
230	return Vec::new();
231	};
232	let mut path = Vec::new();
233	let mut cur = leaf;
234	while let Some(p) = self.nodes[cur].parent {
235	let shared = self
236	.children(p)
237	.iter()
238	.any(\|c\| c.node != cur && self.visible(c.node, vis));
239	if shared {
240	path.push((p, cur));
241	}
242	cur = p;
243	}
244	path
245	}
246
247	/// Transposes the whole tree.
248	pub fn flip(&mut self) {
249	self.stack = self.stack.other();
250	for node in self.nodes.values_mut() {
251	if let Kind::Container { axis, .. } = &mut node.kind {
252	*axis = axis.other();
253	}
254	}
255	}
256
257	/// Toggles expansion for `count` levels of `w`'s visible ancestry,
258	/// starting `skip` levels up. Level 0 expands the window inside the
259	/// nearest container where it has a visible sibling.
260	pub fn toggle_expand(
261	&mut self,
262	w: W,
263	skip: usize,
264	count: usize,
265	vis: impl Fn(W) -> bool,
266	) -> bool {
267	let path: Vec<_> = self
268	.shown_path(w, &vis)
269	.into_iter()
270	.skip(skip)
271	.take(count)
272	.collect();
273	if path.is_empty() {
274	return false;
275	}
276	let all = path.iter().all(\|&(p, c)\| self.expanded(p) == Some(c));
277	for (p, c) in path {
278	if let Kind::Container { expanded, .. } = &mut self.nodes[p].kind {
279	*expanded = (!all).then_some(c);
280	}
281	}
282	true
283	}
284
285	/// Grows `w` by `delta`, a fraction of the visible length of the nearest
286	/// container along `axis` where it has a visible sibling. Hidden siblings
287	/// keep their weights, and with them their share.
288	pub fn resize(&mut self, w: W, axis: Axis, delta: f64, vis: impl Fn(W) -> bool) -> bool {
289	let Some(&leaf) = self.leaves.get(&w) else {
290	return false;
291	};
292	let mut cur = leaf;
293	while let Some((p, i)) = self.position(cur) {
294	if self.axis(p) == Some(axis) {
295	let shown: Vec<usize> = (0..self.children(p).len())
296	.filter(\|&j\| self.visible(self.children(p)[j].node, &vis))
297	.collect();
298	if shown.len() >= 2 {
299	let children = self.children_mut(p);
300	let sum: f64 = shown.iter().map(\|&j\| children[j].weight).sum();
301	let old = children[i].weight;
302	let max = 1.0 - MIN_SHARE * (shown.len() - 1) as f64;
303	let new = (old / sum + delta).clamp(MIN_SHARE, max) * sum;
304	let scale = (sum - new) / (sum - old);
305	for j in shown {
306	children[j].weight = if j == i {
307	new
308	} else {
309	children[j].weight * scale
310	};
311	}
312	return true;
313	}
314	}
315	cur = p;
316	}
317	false
318	}
319
320	/// Lays the tree out in `area`. Hidden windows come back as zero-size
321	/// rects on the boundary where they would reappear.
322	pub fn arrange(&self, area: Rect, gap: f64, vis: impl Fn(W) -> bool) -> Vec<(W, Rect)> {
323	let mut out = Vec::with_capacity(self.leaves.len());
324	if let Some(r) = self.root {
325	let area = if self.visible(r, &vis) {
326	area
327	} else {
328	Rect::new(area.x + area.w / 2.0, area.y, 0.0, area.h)
329	};
330	self.place(r, area, gap, &vis, &mut out);
331	}
332	out
333	}
334
335	fn place(
336	&self,
337	n: NodeId,
338	r: Rect,
339	gap: f64,
340	vis: &impl Fn(W) -> bool,
341	out: &mut Vec<(W, Rect)>,
342	) {
343	let (axis, children, expanded) = match &self.nodes[n].kind {
344	Kind::Leaf(w) => return out.push((*w, r)),
345	Kind::Container {
346	axis,
347	children,
348	expanded,
349	} => (axis, children, expanded),
350	};
351	let shown: Vec<bool> = children.iter().map(\|c\| self.visible(c.node, vis)).collect();
352	let (start, len) = span(r, axis);
353	if let Some(e) = expanded.and_then(\|e\| children.iter().position(\|c\| c.node == e))
354	&& shown[e]
355	{
356	for (i, c) in children.iter().enumerate() {
357	let sub = match i.cmp(&e) {
358	std::cmp::Ordering::Equal => r,
359	std::cmp::Ordering::Less => with_span(r, axis, start, 0.0),
360	std::cmp::Ordering::Greater => with_span(r, axis, start + len, 0.0),
361	};
362	self.place(c.node, sub, gap, vis, out);
363	}
364	return;
365	}
366	let count = shown.iter().filter(\|s\| **s).count();
367	let total: f64 = children
368	.iter()
369	.zip(&shown)
370	.filter(\|(_, s)\| **s)
371	.map(\|(c, _)\| c.weight)
372	.sum();
373	let gaps = count.saturating_sub(1) as f64;
374	let gap = if gaps > 0.0 { gap.min(len / gaps) } else { gap };
375	let avail = len - gap * gaps;
376	let last = shown.iter().rposition(\|s\| *s);
377	let mut pos = start;
378	let mut seen = false;
379	for (i, c) in children.iter().enumerate() {
380	if shown[i] {
381	if seen {
382	pos += gap;
383	}
384	let l = avail * c.weight / total;
385	self.place(c.node, with_span(r, axis, pos, l), gap, vis, out);
386	pos += l;
387	seen = true;
388	} else {
389	let between = seen && last.is_some_and(\|l\| l > i);
390	let at = if between { pos + gap / 2.0 } else { pos };
391	self.place(c.node, with_span(r, axis, at, 0.0), gap, vis, out);
392	}
393	}
394	}
395
396	fn move_node(&mut self, n: NodeId, dir: Dir, vis: &impl Fn(W) -> bool, enter: bool) -> bool {
397	let mut cur = n;
398	while let Some((p, i)) = self.position(cur) {
399	if self.axis(p) == Some(dir.axis()) {
400	let hidden_lane = self
401	.adjacent(p, i, dir)
402	.filter(\|&j\| enter && !self.visible(self.children(p)[j].node, vis));
403	if cur != n {
404	if let Some(j) = hidden_lane {
405	self.join_lane(n, p, j);
406	} else {
407	let at = if dir.forward() { i + 1 } else { i };
408	self.relocate(n, p, at);
409	}
410	return true;
411	}
412	if let Some(j) = self.next_shown(p, i, dir, vis) {
413	let sib = self.children(p)[j].node;
414	if enter && self.axis(sib).is_some() {
415	let end = self.children(sib).len();
416	self.relocate(n, sib, end);
417	} else {
418	let children = self.children_mut(p);
419	children[i].node = sib;
420	children[j].node = n;
421	}
422	return true;
423	}
424	if let Some(j) = hidden_lane {
425	self.join_lane(n, p, j);
426	return true;
427	}
428	}
429	cur = p;
430	}
431	if cur == n \|\| self.axis(cur) == Some(dir.axis()) {
432	return false;
433	}
434	let (old, i) = self.position(n).expect("n is below the root");
435	self.unlink(old, i);
436	self.normalize(old);
437	let r = self.root.expect("the rest of the tree survives");
438	if self.axis(r) == Some(dir.axis()) {
439	let weight = self.mean_weight(r);
440	let at = if dir.forward() {
441	self.children(r).len()
442	} else {
443	0
444	};
445	self.attach(r, at, n, weight);
446	} else {
447	let c = self.new_container(dir.axis());
448	self.attach(c, 0, r, 1.0);
449	let at = if dir.forward() {
450	self.children(c).len()
451	} else {
452	0
453	};
454	self.attach(c, at, n, 1.0);
455	self.root = Some(c);
456	}
457	true
458	}
459
460	fn next_shown(&self, p: NodeId, i: usize, dir: Dir, vis: &impl Fn(W) -> bool) -> Option<usize> {
461	let children = self.children(p);
462	if dir.forward() {
463	(i + 1..children.len()).find(\|&j\| self.visible(children[j].node, vis))
464	} else {
465	(0..i).rev().find(\|&j\| self.visible(children[j].node, vis))
466	}
467	}
468
469	fn adjacent(&self, p: NodeId, i: usize, dir: Dir) -> Option<usize> {
470	let j = if dir.forward() {
471	i + 1
472	} else {
473	i.checked_sub(1)?
474	};
475	(j < self.children(p).len()).then_some(j)
476	}
477
478	/// Moves `n` to the end of the lane at `p`'s child `j`. A lone window
479	/// there becomes a lane of its own, perpendicular to `p`.
480	fn join_lane(&mut self, n: NodeId, p: NodeId, j: usize) {
481	let lane = self.children(p)[j].node;
482	let lane = if self.axis(lane).is_some() {
483	lane
484	} else {
485	let c = self.new_container(self.axis(p).expect("p is a container").other());
486	self.children_mut(p)[j].node = c;
487	self.nodes[c].parent = Some(p);
488	if let Kind::Container { expanded, .. } = &mut self.nodes[p].kind
489	&& *expanded == Some(lane)
490	{
491	*expanded = Some(c);
492	}
493	self.attach(c, 0, lane, 1.0);
494	c
495	};
496	let end = self.children(lane).len();
497	self.relocate(n, lane, end);
498	}
499
500	fn relocate(&mut self, n: NodeId, p: NodeId, at: usize) {
501	let (old, i) = self.position(n).expect("relocated nodes have a parent");
502	let weight = self.mean_weight(p);
503	let at = if old == p && i < at { at - 1 } else { at };
504	self.unlink(old, i);
505	self.attach(p, at, n, weight);
506	self.normalize(old);
507	}
508
509	/// Places `node` among `p`'s children. A container running along `p`'s
510	/// axis is dissolved into `p` so axes keep alternating.
511	fn attach(&mut self, p: NodeId, at: usize, node: NodeId, weight: f64) {
512	if self.axis(node) == self.axis(p) {
513	let Some(Node {
514	kind: Kind::Container { children, .. },
515	..
516	}) = self.nodes.remove(node)
517	else {
518	unreachable!("only containers have an axis");
519	};
520	let total: f64 = children.iter().map(\|c\| c.weight).sum();
521	for (k, c) in children.into_iter().enumerate() {
522	self.nodes[c.node].parent = Some(p);
523	let weight = weight * c.weight / total;
524	self.children_mut(p).insert(
525	at + k,
526	Child {
527	node: c.node,
528	weight,
529	},
530	);
531	}
532	} else {
533	self.nodes[node].parent = Some(p);
534	self.children_mut(p).insert(at, Child { node, weight });
535	}
536	}
537
538	fn unlink(&mut self, p: NodeId, i: usize) -> Child {
539	let Kind::Container {
540	children, expanded, ..
541	} = &mut self.nodes[p].kind
542	else {
543	unreachable!("parents are containers");
544	};
545	let child = children.remove(i);
546	if *expanded == Some(child.node) {
547	*expanded = None;
548	}
549	self.nodes[child.node].parent = None;
550	child
551	}
552
553	fn detach(&mut self, n: NodeId) {
554	match self.position(n) {
555	Some((p, i)) => {
556	self.unlink(p, i);
557	self.normalize(p);
558	}
559	None => self.root = None,
560	}
561	}
562
563	/// Repairs a container that lost a child.
564	fn normalize(&mut self, c: NodeId) {
565	if self.children(c).len() >= 2 {
566	return;
567	}
568	let pos = self.position(c);
569	let was_expanded = pos.is_some_and(\|(p, _)\| self.expanded(p) == Some(c));
570	let Some(Node {
571	kind: Kind::Container { children, .. },
572	..
573	}) = self.nodes.remove(c)
574	else {
575	unreachable!("only containers are normalized");
576	};
577	let only = children.into_iter().next();
578	match (only, pos) {
579	(None, Some((p, i))) => {
580	self.unlink_dead(p, i);
581	self.normalize(p);
582	}
583	(None, None) => self.root = None,
584	(Some(only), Some((p, i))) => {
585	let weight = self.unlink_dead(p, i).weight;
586	let leaf_like = self.axis(only.node) != self.axis(p);
587	self.attach(p, i, only.node, weight);
588	if was_expanded
589	&& leaf_like
590	&& let Kind::Container { expanded, .. } = &mut self.nodes[p].kind
591	{
592	*expanded = Some(only.node);
593	}
594	}
595	(Some(only), None) => {
596	self.nodes[only.node].parent = None;
597	self.root = Some(only.node);
598	}
599	}
600	}
601
602	/// Like `unlink`, for a child whose node is already gone.
603	fn unlink_dead(&mut self, p: NodeId, i: usize) -> Child {
604	let Kind::Container {
605	children, expanded, ..
606	} = &mut self.nodes[p].kind
607	else {
608	unreachable!("parents are containers");
609	};
610	let child = children.remove(i);
611	if *expanded == Some(child.node) {
612	*expanded = None;
613	}
614	child
615	}
616
617	fn new_leaf(&mut self, w: W) -> NodeId {
618	let n = self.nodes.insert(Node {
619	parent: None,
620	kind: Kind::Leaf(w),
621	});
622	self.leaves.insert(w, n);
623	n
624	}
625
626	fn new_container(&mut self, axis: Axis) -> NodeId {
627	self.nodes.insert(Node {
628	parent: None,
629	kind: Kind::Container {
630	axis,
631	children: Vec::new(),
632	expanded: None,
633	},
634	})
635	}
636
637	fn position(&self, n: NodeId) -> Option<(NodeId, usize)> {
638	let p = self.nodes[n].parent?;
639	let i = self.children(p).iter().position(\|c\| c.node == n)?;
640	Some((p, i))
641	}
642
643	fn axis(&self, n: NodeId) -> Option<Axis> {
644	match &self.nodes[n].kind {
645	Kind::Container { axis, .. } => Some(*axis),
646	Kind::Leaf(_) => None,
647	}
648	}
649
650	fn expanded(&self, n: NodeId) -> Option<NodeId> {
651	match &self.nodes[n].kind {
652	Kind::Container { expanded, .. } => *expanded,
653	Kind::Leaf(_) => None,
654	}
655	}
656
657	fn children(&self, n: NodeId) -> &[Child] {
658	match &self.nodes[n].kind {
659	Kind::Container { children, .. } => children,
660	Kind::Leaf(_) => &[],
661	}
662	}
663
664	fn children_mut(&mut self, n: NodeId) -> &mut Vec<Child> {
665	match &mut self.nodes[n].kind {
666	Kind::Container { children, .. } => children,
667	Kind::Leaf(_) => unreachable!("leaves have no children"),
668	}
669	}
670
671	fn mean_weight(&self, p: NodeId) -> f64 {
672	let children = self.children(p);
673	if children.is_empty() {
674	1.0
675	} else {
676	children.iter().map(\|c\| c.weight).sum::<f64>() / children.len() as f64
677	}
678	}
679
680	fn visible(&self, n: NodeId, vis: &impl Fn(W) -> bool) -> bool {
681	match &self.nodes[n].kind {
682	Kind::Leaf(w) => vis(*w),
683	Kind::Container { children, .. } => children.iter().any(\|c\| self.visible(c.node, vis)),
684	}
685	}
686
687	#[cfg(test)]
688	pub(crate) fn check(&self) {
689	let reachable = match self.root {
690	Some(r) => {
691	assert!(self.nodes[r].parent.is_none());
692	self.check_node(r)
693	}
694	None => 0,
695	};
696	assert_eq!(reachable, self.nodes.len(), "orphaned nodes");
697	for (&w, &n) in &self.leaves {
698	assert!(matches!(self.nodes[n].kind, Kind::Leaf(x) if x == w));
699	}
700	}
701
702	#[cfg(test)]
703	fn check_node(&self, n: NodeId) -> usize {
704	match &self.nodes[n].kind {
705	Kind::Leaf(_) => 1,
706	Kind::Container {
707	axis,
708	children,
709	expanded,
710	} => {
711	assert!(
712	children.len() >= 2,
713	"container with {} children",
714	children.len()
715	);
716	if let Some(e) = expanded {
717	assert!(children.iter().any(\|c\| c.node == *e));
718	}
719	let mut count = 1;
720	for c in children {
721	assert!(c.weight > 0.0 && c.weight.is_finite());
722	assert_eq!(self.nodes[c.node].parent, Some(n));
723	assert_ne!(self.axis(c.node), Some(*axis), "axes must alternate");
724	count += self.check_node(c.node);
725	}
726	count
727	}
728	}
729	}
730	}
731
732	fn span(r: Rect, axis: Axis) -> (f64, f64) {
733	match axis {
734	Axis::Horizontal => (r.x, r.w),
735	Axis::Vertical => (r.y, r.h),
736	}
737	}
738
739	fn with_span(r: Rect, axis: Axis, start: f64, len: f64) -> Rect {
740	match axis {
741	Axis::Horizontal => Rect::new(start, r.y, len, r.h),
742	Axis::Vertical => Rect::new(r.x, start, r.w, len),
743	}
744	}