guise/panegroup/
tree.rs

1//! Binary split tree of panes.
2
3use crate::SplitDirection;
4use super::id::{PaneId, SplitId};
5
6pub const MIN_RATIO: f32 = 0.1;
7pub const MAX_RATIO: f32 = 0.9;
8
9/// Clamp a split ratio into the allowed `0.1..=0.9` range.
10pub fn clamp_ratio(ratio: f32) -> f32 {
11    ratio.clamp(MIN_RATIO, MAX_RATIO)
12}
13
14#[derive(Debug, Clone, PartialEq)]
15pub enum Node {
16    Leaf(PaneId),
17    Split {
18        id: SplitId,
19        axis: SplitDirection,
20        /// Fraction of the available space given to `first`. Always clamped.
21        ratio: f32,
22        first: Box<Node>,
23        second: Box<Node>,
24    },
25}
26
27/// A tree of panes. Always contains at least one pane.
28#[derive(Debug, Clone, PartialEq)]
29pub struct PaneTree {
30    root: Node,
31    splits: u64,
32}
33
34impl PaneTree {
35    pub fn new(root: PaneId) -> Self {
36        Self {
37            root: Node::Leaf(root),
38            splits: 0,
39        }
40    }
41
42    pub fn root(&self) -> &Node {
43        &self.root
44    }
45
46    /// Split the leaf holding `target`, placing `new_pane` beside it.
47    /// `new_first` puts the new pane left/top. Ratio starts at 0.5.
48    /// Returns the id of the created split, or `None` if `target` is absent
49    /// or `new_pane` is already present.
50    pub fn split(
51        &mut self,
52        target: PaneId,
53        axis: SplitDirection,
54        new_pane: PaneId,
55        new_first: bool,
56    ) -> Option<SplitId> {
57        if !self.contains(target) || self.contains(new_pane) {
58            return None;
59        }
60        self.splits += 1;
61        let id = SplitId(self.splits);
62        splitnode(&mut self.root, target, axis, new_pane, new_first, id);
63        Some(id)
64    }
65
66    /// Split the leaf holding `target`, placing an entire `subtree` beside it
67    /// (used when a whole tab — possibly itself split — is dropped onto a pane).
68    /// `subtree`'s `SplitId`s are renumbered into this tree so they can't clash.
69    /// `false` if `target` is absent or `subtree` shares a pane with this tree.
70    pub fn split_subtree(
71        &mut self,
72        target: PaneId,
73        axis: SplitDirection,
74        mut subtree: Node,
75        new_first: bool,
76    ) -> bool {
77        if !self.contains(target) {
78            return false;
79        }
80        let mut sub_panes = Vec::new();
81        leaves(&subtree, &mut sub_panes);
82        if sub_panes.iter().any(|p| self.contains(*p)) {
83            return false;
84        }
85        renumber(&mut subtree, &mut self.splits);
86        self.splits += 1;
87        let id = SplitId(self.splits);
88        splitsubnode(&mut self.root, target, axis, subtree, new_first, id).is_ok()
89    }
90
91    /// Remove a pane, collapsing its parent split into the sibling subtree.
92    /// Returns `false` if the pane is absent or is the last pane.
93    pub fn remove(&mut self, pane: PaneId) -> bool {
94        removenode(&mut self.root, pane)
95    }
96
97    /// Set a divider's ratio (clamped to `0.1..=0.9`). `false` if `split` is absent.
98    pub fn set_ratio(&mut self, split: SplitId, ratio: f32) -> bool {
99        setrationode(&mut self.root, split, clamp_ratio(ratio))
100    }
101
102    /// Current ratio of a split, if it exists.
103    pub fn ratio(&self, split: SplitId) -> Option<f32> {
104        rationode(&self.root, split)
105    }
106
107    /// The nearest ancestor split of `pane` whose divider runs along `axis`.
108    /// Used to resize the split adjacent to the focused pane in a direction.
109    pub fn nearest_split(&self, pane: PaneId, axis: SplitDirection) -> Option<SplitId> {
110        nearestnode(&self.root, pane, axis)
111    }
112
113    /// All dividers in layout order (depth first, parent before children).
114    pub fn list_dividers(&self) -> Vec<(SplitId, SplitDirection)> {
115        let mut out = Vec::new();
116        dividers(&self.root, &mut out);
117        out
118    }
119
120    /// All panes in layout order (left/top before right/bottom).
121    pub fn panes(&self) -> Vec<PaneId> {
122        let mut out = Vec::new();
123        leaves(&self.root, &mut out);
124        out
125    }
126
127    pub fn contains(&self, pane: PaneId) -> bool {
128        containsnode(&self.root, pane)
129    }
130}
131
132/// Renumber every split in `node` using `counter` (incremented per split), so a
133/// subtree lifted from another tree gets ids unique to its new home.
134fn renumber(node: &mut Node, counter: &mut u64) {
135    if let Node::Split { id, first, second, .. } = node {
136        *counter += 1;
137        *id = SplitId(*counter);
138        renumber(first, counter);
139        renumber(second, counter);
140    }
141}
142
143/// Like [`splitnode`] but inserts a whole `subtree`. Threads the subtree back
144/// via `Err` when a branch doesn't hold `target`, so it's only moved once.
145fn splitsubnode(
146    node: &mut Node,
147    target: PaneId,
148    axis: SplitDirection,
149    subtree: Node,
150    new_first: bool,
151    id: SplitId,
152) -> Result<(), Node> {
153    match node {
154        Node::Leaf(pane) if *pane == target => {
155            let kept = Node::Leaf(target);
156            let (first, second) = if new_first {
157                (subtree, kept)
158            } else {
159                (kept, subtree)
160            };
161            *node = Node::Split {
162                id,
163                axis,
164                ratio: 0.5,
165                first: Box::new(first),
166                second: Box::new(second),
167            };
168            Ok(())
169        }
170        Node::Leaf(_) => Err(subtree),
171        Node::Split { first, second, .. } => {
172            match splitsubnode(first, target, axis, subtree, new_first, id) {
173                Ok(()) => Ok(()),
174                Err(subtree) => splitsubnode(second, target, axis, subtree, new_first, id),
175            }
176        }
177    }
178}
179
180fn splitnode(
181    node: &mut Node,
182    target: PaneId,
183    axis: SplitDirection,
184    new_pane: PaneId,
185    new_first: bool,
186    id: SplitId,
187) -> bool {
188    match node {
189        Node::Leaf(pane) if *pane == target => {
190            let (first, second) = if new_first {
191                (Node::Leaf(new_pane), Node::Leaf(target))
192            } else {
193                (Node::Leaf(target), Node::Leaf(new_pane))
194            };
195            *node = Node::Split {
196                id,
197                axis,
198                ratio: 0.5,
199                first: Box::new(first),
200                second: Box::new(second),
201            };
202            true
203        }
204        Node::Leaf(_) => false,
205        Node::Split { first, second, .. } => {
206            splitnode(first, target, axis, new_pane, new_first, id)
207                || splitnode(second, target, axis, new_pane, new_first, id)
208        }
209    }
210}
211
212fn removenode(node: &mut Node, pane: PaneId) -> bool {
213    let Node::Split { first, second, .. } = node else {
214        return false;
215    };
216    let in_first = matches!(first.as_ref(), Node::Leaf(p) if *p == pane);
217    let in_second = matches!(second.as_ref(), Node::Leaf(p) if *p == pane);
218    if in_first || in_second {
219        let keep = if in_first { second } else { first };
220        *node = std::mem::replace(keep.as_mut(), Node::Leaf(pane));
221        return true;
222    }
223    removenode(first, pane) || removenode(second, pane)
224}
225
226fn setrationode(node: &mut Node, split: SplitId, clamped: f32) -> bool {
227    let Node::Split {
228        id,
229        ratio,
230        first,
231        second,
232        ..
233    } = node
234    else {
235        return false;
236    };
237    if *id == split {
238        *ratio = clamped;
239        return true;
240    }
241    setrationode(first, split, clamped) || setrationode(second, split, clamped)
242}
243
244fn nearestnode(node: &Node, pane: PaneId, axis: SplitDirection) -> Option<SplitId> {
245    let Node::Split {
246        id,
247        axis: a,
248        first,
249        second,
250        ..
251    } = node
252    else {
253        return None;
254    };
255    let child: &Node = if containsnode(first, pane) {
256        first
257    } else if containsnode(second, pane) {
258        second
259    } else {
260        return None;
261    };
262    nearestnode(child, pane, axis).or(if *a == axis { Some(*id) } else { None })
263}
264
265fn rationode(node: &Node, split: SplitId) -> Option<f32> {
266    let Node::Split {
267        id,
268        ratio,
269        first,
270        second,
271        ..
272    } = node
273    else {
274        return None;
275    };
276    if *id == split {
277        return Some(*ratio);
278    }
279    rationode(first, split).or_else(|| rationode(second, split))
280}
281
282fn dividers(node: &Node, out: &mut Vec<(SplitId, SplitDirection)>) {
283    if let Node::Split {
284        id,
285        axis,
286        first,
287        second,
288        ..
289    } = node
290    {
291        out.push((*id, *axis));
292        dividers(first, out);
293        dividers(second, out);
294    }
295}
296
297fn leaves(node: &Node, out: &mut Vec<PaneId>) {
298    match node {
299        Node::Leaf(pane) => out.push(*pane),
300        Node::Split { first, second, .. } => {
301            leaves(first, out);
302            leaves(second, out);
303        }
304    }
305}
306
307fn containsnode(node: &Node, pane: PaneId) -> bool {
308    match node {
309        Node::Leaf(p) => *p == pane,
310        Node::Split { first, second, .. } => {
311            containsnode(first, pane) || containsnode(second, pane)
312        }
313    }
314}
guise/panegroup/tree.rs

guise/panegroup/
tree.rs
