term_wm_layout_engine/
node.rs

1use crate::rect::{LayoutError, LayoutRect, Orientation, Ratio, SizeConstraints};
2use crate::snap::InsertPosition;
3use crate::split;
4
5/// A strict binary (BSP) split tree.
6///
7/// Each `Split` node divides its area into two children using an integer
8/// ratio.  Remainder isolation guarantees no dead zones:
9/// `sum(child widths) == parent width`.
10#[derive(Debug, Clone)]
11pub enum BspNode<Id: Copy + Eq + Ord> {
12    Leaf(Id),
13    Split {
14        orientation: Orientation,
15        left: Box<BspNode<Id>>,
16        right: Box<BspNode<Id>>,
17        ratio: Ratio,
18    },
19}
20
21impl<Id: Copy + Eq + Ord> BspNode<Id> {
22    pub fn leaf(id: Id) -> Self {
23        Self::Leaf(id)
24    }
25
26    pub fn is_leaf(&self) -> bool {
27        matches!(self, Self::Leaf(_))
28    }
29
30    pub fn unwrap_leaf(&self) -> Option<Id> {
31        match self {
32            Self::Leaf(id) => Some(*id),
33            _ => None,
34        }
35    }
36
37    pub fn subtree_any(&self, predicate: &mut impl FnMut(Id) -> bool) -> bool {
38        match self {
39            Self::Leaf(id) => predicate(*id),
40            Self::Split { left, right, .. } => {
41                left.subtree_any(predicate) || right.subtree_any(predicate)
42            }
43        }
44    }
45
46    pub fn all_leaf_ids(&self) -> Vec<Id> {
47        let mut ids = Vec::new();
48        self.collect_ids(&mut ids);
49        ids
50    }
51
52    fn collect_ids(&self, ids: &mut Vec<Id>) {
53        match self {
54            Self::Leaf(id) => ids.push(*id),
55            Self::Split { left, right, .. } => {
56                left.collect_ids(ids);
57                right.collect_ids(ids);
58            }
59        }
60    }
61
62    pub fn layout(&self, area: LayoutRect) -> Vec<(Id, LayoutRect)> {
63        let mut regions = Vec::new();
64        self.layout_recursive(area, &mut regions);
65        regions
66    }
67
68    fn layout_recursive(&self, area: LayoutRect, regions: &mut Vec<(Id, LayoutRect)>) {
69        match self {
70            Self::Leaf(id) => {
71                regions.push((*id, area));
72            }
73            Self::Split {
74                orientation,
75                left,
76                right,
77                ratio,
78            } => {
79                let (left_area, right_area) = split::split_rect_bsp(area, *orientation, *ratio);
80                left.layout_recursive(left_area, regions);
81                right.layout_recursive(right_area, regions);
82            }
83        }
84    }
85
86    pub fn insert_leaf(
87        &mut self,
88        target: Id,
89        insert: Id,
90        position: InsertPosition,
91        area: LayoutRect,
92        constraints: &SizeConstraints,
93    ) -> Result<(), LayoutError> {
94        match self {
95            Self::Leaf(current) => {
96                if *current != target {
97                    return Err(LayoutError::NotFound);
98                }
99                let (orientation, left_child, right_child) = match position {
100                    InsertPosition::Left => (
101                        Orientation::Horizontal,
102                        Self::leaf(insert),
103                        Self::leaf(*current),
104                    ),
105                    InsertPosition::Right => (
106                        Orientation::Horizontal,
107                        Self::leaf(*current),
108                        Self::leaf(insert),
109                    ),
110                    InsertPosition::Top => (
111                        Orientation::Vertical,
112                        Self::leaf(insert),
113                        Self::leaf(*current),
114                    ),
115                    InsertPosition::Bottom => (
116                        Orientation::Vertical,
117                        Self::leaf(*current),
118                        Self::leaf(insert),
119                    ),
120                    // Corners: use vertical split (top portion for new window)
121                    InsertPosition::TopLeft | InsertPosition::TopRight => (
122                        Orientation::Vertical,
123                        Self::leaf(insert),
124                        Self::leaf(*current),
125                    ),
126                    InsertPosition::BottomLeft | InsertPosition::BottomRight => (
127                        Orientation::Vertical,
128                        Self::leaf(*current),
129                        Self::leaf(insert),
130                    ),
131                };
132                let half_dim = match orientation {
133                    Orientation::Horizontal => area.width / 2,
134                    Orientation::Vertical => area.height / 2,
135                };
136                if orientation == Orientation::Horizontal {
137                    if half_dim < constraints.min_width {
138                        return Err(LayoutError::ConstraintViolated(*constraints));
139                    }
140                    if area.height < constraints.min_height {
141                        return Err(LayoutError::ConstraintViolated(*constraints));
142                    }
143                } else {
144                    if half_dim < constraints.min_height {
145                        return Err(LayoutError::ConstraintViolated(*constraints));
146                    }
147                    if area.width < constraints.min_width {
148                        return Err(LayoutError::ConstraintViolated(*constraints));
149                    }
150                }
151                *self = Self::Split {
152                    orientation,
153                    left: Box::new(left_child),
154                    right: Box::new(right_child),
155                    ratio: Ratio::half(),
156                };
157                Ok(())
158            }
159            Self::Split {
160                orientation,
161                left,
162                right,
163                ratio,
164            } => {
165                let (left_area, right_area) = split::split_rect_bsp(area, *orientation, *ratio);
166                left.insert_leaf(target, insert, position, left_area, constraints)
167                    .or_else(|_| {
168                        right.insert_leaf(target, insert, position, right_area, constraints)
169                    })
170            }
171        }
172    }
173
174    pub fn apply_drag(
175        &mut self,
176        area: LayoutRect,
177        path: &[bool],
178        orientation: Orientation,
179        delta: i16,
180        constraints: &SizeConstraints,
181    ) -> bool {
182        if path.is_empty() {
183            return false;
184        }
185        match self {
186            Self::Split {
187                orientation: split_orient,
188                left,
189                right,
190                ratio,
191            } => {
192                if path.len() == 1 {
193                    if *split_orient != orientation {
194                        return false;
195                    }
196                    let total = match orientation {
197                        Orientation::Horizontal => u32::from(area.width),
198                        Orientation::Vertical => u32::from(area.height),
199                    };
200                    if total == 0 {
201                        return false;
202                    }
203                    let min_first = match orientation {
204                        Orientation::Horizontal => u32::from(constraints.min_width),
205                        Orientation::Vertical => u32::from(constraints.min_height),
206                    };
207                    let min_second = min_first;
208                    let current =
209                        u32::from(ratio.left_part()) * total / u32::from(ratio.total()).max(1);
210                    let new_pos = (current as i32).saturating_add(i32::from(delta));
211                    let new_pos = new_pos.max(i32::from(min_first as u16));
212                    let bound = (total as i32).saturating_sub(i32::from(min_second as u16));
213                    let new_pos = new_pos.min(bound) as u32;
214                    let new_ratio_left = new_pos * u32::from(ratio.total()).max(1) / total.max(1);
215                    let new_ratio_left = new_ratio_left.max(1) as u16;
216                    let new_ratio_total = ratio.total().max(1);
217                    *ratio = Ratio(new_ratio_left, new_ratio_total);
218                    true
219                } else {
220                    let (left_area, right_area) =
221                        split::split_rect_bsp(area, *split_orient, *ratio);
222                    let rest = &path[1..];
223                    if !path[0] {
224                        left.apply_drag(left_area, rest, orientation, delta, constraints)
225                    } else {
226                        right.apply_drag(right_area, rest, orientation, delta, constraints)
227                    }
228                }
229            }
230            Self::Leaf(_) => false,
231        }
232    }
233
234    pub fn remove_leaf(&mut self, id: Id) -> Result<(), LayoutError> {
235        match self {
236            Self::Leaf(current) => {
237                if *current == id {
238                    return Err(LayoutError::NotFound);
239                }
240                Err(LayoutError::NotFound)
241            }
242            Self::Split { left, right, .. } => {
243                let left_is_target = left.as_ref().unwrap_leaf() == Some(id);
244                let right_is_target = right.as_ref().unwrap_leaf() == Some(id);
245
246                if left_is_target {
247                    *self = *right.clone();
248                    return Ok(());
249                }
250                if right_is_target {
251                    *self = *left.clone();
252                    return Ok(());
253                }
254
255                left.remove_leaf(id).or_else(|_| right.remove_leaf(id))?;
256
257                if left.is_leaf() && right.is_leaf() {
258                    return Ok(());
259                }
260
261                Ok(())
262            }
263        }
264    }
265
266    pub fn find_path(&self, target: Id) -> Option<Vec<bool>> {
267        match self {
268            Self::Leaf(id) => {
269                if *id == target {
270                    Some(Vec::new())
271                } else {
272                    None
273                }
274            }
275            Self::Split { left, right, .. } => {
276                if let Some(mut path) = left.find_path(target) {
277                    path.insert(0, false);
278                    return Some(path);
279                }
280                if let Some(mut path) = right.find_path(target) {
281                    path.insert(0, true);
282                    return Some(path);
283                }
284                None
285            }
286        }
287    }
288}
289
290#[derive(Debug, Clone)]
291pub enum NaryNode<Id: Copy + Eq + Ord> {
292    Leaf(Id),
293    Container {
294        orientation: Orientation,
295        children: Vec<NaryNode<Id>>,
296        weights: Vec<u16>,
297    },
298}
299
300impl<Id: Copy + Eq + Ord> NaryNode<Id> {
301    pub fn leaf(id: Id) -> Self {
302        Self::Leaf(id)
303    }
304
305    pub fn is_leaf(&self) -> bool {
306        matches!(self, Self::Leaf(_))
307    }
308
309    pub fn unwrap_leaf(&self) -> Option<Id> {
310        match self {
311            Self::Leaf(id) => Some(*id),
312            _ => None,
313        }
314    }
315
316    pub fn all_leaf_ids(&self) -> Vec<Id> {
317        let mut ids = Vec::new();
318        self.collect_ids(&mut ids);
319        ids
320    }
321
322    fn collect_ids(&self, ids: &mut Vec<Id>) {
323        match self {
324            Self::Leaf(id) => ids.push(*id),
325            Self::Container { children, .. } => {
326                for child in children {
327                    child.collect_ids(ids);
328                }
329            }
330        }
331    }
332
333    pub fn subtree_any(&self, predicate: &mut impl FnMut(Id) -> bool) -> bool {
334        match self {
335            Self::Leaf(id) => predicate(*id),
336            Self::Container { children, .. } => children.iter().any(|c| c.subtree_any(predicate)),
337        }
338    }
339
340    pub fn layout(&self, area: LayoutRect) -> Vec<(Id, LayoutRect)> {
341        let mut regions = Vec::new();
342        self.layout_recursive(area, &mut regions);
343        regions
344    }
345
346    fn layout_recursive(&self, area: LayoutRect, regions: &mut Vec<(Id, LayoutRect)>) {
347        match self {
348            Self::Leaf(id) => {
349                regions.push((*id, area));
350            }
351            Self::Container {
352                orientation,
353                children,
354                weights,
355            } => {
356                let sub_rects =
357                    split::split_rects_nary(area, *orientation, weights, children.len());
358                for (child, sub) in children.iter().zip(sub_rects) {
359                    child.layout_recursive(sub, regions);
360                }
361            }
362        }
363    }
364
365    pub fn find_path(&self, target: Id) -> Option<Vec<usize>> {
366        match self {
367            Self::Leaf(id) => {
368                if *id == target {
369                    Some(Vec::new())
370                } else {
371                    None
372                }
373            }
374            Self::Container { children, .. } => {
375                for (i, child) in children.iter().enumerate() {
376                    if let Some(mut path) = child.find_path(target) {
377                        path.insert(0, i);
378                        return Some(path);
379                    }
380                }
381                None
382            }
383        }
384    }
385
386    pub fn node_at_path(&self, path: &[usize]) -> Option<&Self> {
387        let mut node = self;
388        for &idx in path {
389            match node {
390                Self::Container { children, .. } => {
391                    node = children.get(idx)?;
392                }
393                _ => return None,
394            }
395        }
396        Some(node)
397    }
398
399    pub fn node_at_path_mut(&mut self, path: &[usize]) -> Option<&mut Self> {
400        let mut node = self;
401        for &idx in path {
402            match node {
403                Self::Container { children, .. } => {
404                    node = children.get_mut(idx)?;
405                }
406                _ => return None,
407            }
408        }
409        Some(node)
410    }
411
412    pub fn layout_with_gaps(&self, area: LayoutRect, gap: u16) -> Vec<(Id, LayoutRect)> {
413        let mut regions = Vec::new();
414        self.layout_with_gaps_recursive(area, gap, &mut regions);
415        regions
416    }
417
418    fn layout_with_gaps_recursive(
419        &self,
420        area: LayoutRect,
421        gap: u16,
422        regions: &mut Vec<(Id, LayoutRect)>,
423    ) {
424        match self {
425            Self::Leaf(id) => {
426                regions.push((*id, area));
427            }
428            Self::Container {
429                orientation,
430                children,
431                weights,
432            } => {
433                let (sub_rects, _gap_rects) =
434                    split::split_rects_with_gaps(area, *orientation, weights, children.len(), gap);
435                for (child, sub) in children.iter().zip(sub_rects) {
436                    child.layout_with_gaps_recursive(sub, gap, regions);
437                }
438            }
439        }
440    }
441
442    pub fn split_area_for_path(&self, area: LayoutRect, path: &[usize]) -> Option<LayoutRect> {
443        let mut current_area = area;
444        let mut node = self;
445        for &idx in path {
446            match node {
447                Self::Container {
448                    orientation,
449                    children,
450                    weights,
451                } => {
452                    let rects = split::split_rects_nary(
453                        current_area,
454                        *orientation,
455                        weights,
456                        children.len(),
457                    );
458                    let sub_area = rects.get(idx).copied()?;
459                    current_area = sub_area;
460                    node = children.get(idx)?;
461                }
462                _ => return None,
463            }
464        }
465        Some(current_area)
466    }
467
468    pub fn insert_leaf(
469        &mut self,
470        target: Id,
471        insert: Id,
472        position: InsertPosition,
473        area: LayoutRect,
474        constraints: &SizeConstraints,
475    ) -> Result<(), LayoutError> {
476        match self {
477            Self::Leaf(current) => {
478                if *current != target {
479                    return Err(LayoutError::NotFound);
480                }
481                let (orientation, left_child, right_child) = match position {
482                    InsertPosition::Left => (
483                        Orientation::Horizontal,
484                        Self::leaf(insert),
485                        Self::leaf(*current),
486                    ),
487                    InsertPosition::Right => (
488                        Orientation::Horizontal,
489                        Self::leaf(*current),
490                        Self::leaf(insert),
491                    ),
492                    InsertPosition::Top => (
493                        Orientation::Vertical,
494                        Self::leaf(insert),
495                        Self::leaf(*current),
496                    ),
497                    InsertPosition::Bottom => (
498                        Orientation::Vertical,
499                        Self::leaf(*current),
500                        Self::leaf(insert),
501                    ),
502                    // Corners: use vertical split (top portion for new window)
503                    InsertPosition::TopLeft | InsertPosition::TopRight => (
504                        Orientation::Vertical,
505                        Self::leaf(insert),
506                        Self::leaf(*current),
507                    ),
508                    InsertPosition::BottomLeft | InsertPosition::BottomRight => (
509                        Orientation::Vertical,
510                        Self::leaf(*current),
511                        Self::leaf(insert),
512                    ),
513                };
514                let half_dim = match orientation {
515                    Orientation::Horizontal => area.width / 2,
516                    Orientation::Vertical => area.height / 2,
517                };
518                if orientation == Orientation::Horizontal {
519                    if half_dim < constraints.min_width {
520                        return Err(LayoutError::ConstraintViolated(*constraints));
521                    }
522                    if area.height < constraints.min_height {
523                        return Err(LayoutError::ConstraintViolated(*constraints));
524                    }
525                } else {
526                    if half_dim < constraints.min_height {
527                        return Err(LayoutError::ConstraintViolated(*constraints));
528                    }
529                    if area.width < constraints.min_width {
530                        return Err(LayoutError::ConstraintViolated(*constraints));
531                    }
532                }
533                *self = Self::Container {
534                    orientation,
535                    children: vec![left_child, right_child],
536                    weights: vec![1, 1],
537                };
538                Ok(())
539            }
540            Self::Container {
541                orientation: node_orient,
542                children,
543                weights,
544            } => {
545                let sub_rects =
546                    split::split_rects_nary(area, *node_orient, weights, children.len());
547                for (child, sub) in children.iter_mut().zip(sub_rects) {
548                    if child
549                        .insert_leaf(target, insert, position, sub, constraints)
550                        .is_ok()
551                    {
552                        return Ok(());
553                    }
554                }
555                Err(LayoutError::NotFound)
556            }
557        }
558    }
559
560    pub fn apply_drag(
561        &mut self,
562        area: LayoutRect,
563        path: &[usize],
564        index: usize,
565        orientation: Orientation,
566        delta: i16,
567        constraints: &SizeConstraints,
568    ) -> bool {
569        match self {
570            Self::Container {
571                orientation: cont_orient,
572                children,
573                weights,
574            } => {
575                if path.is_empty() {
576                    if *cont_orient != orientation {
577                        return false;
578                    }
579                    if index >= weights.len().saturating_sub(1) || weights.is_empty() {
580                        return false;
581                    }
582                    let total = match orientation {
583                        Orientation::Horizontal => u32::from(area.width),
584                        Orientation::Vertical => u32::from(area.height),
585                    };
586                    if total == 0 {
587                        return false;
588                    }
589                    let total_weight: u32 =
590                        weights.iter().map(|w| u32::from(*w)).sum::<u32>().max(1);
591                    let current0 = u32::from(weights[index]);
592                    let current1 = u32::from(weights[index + 1]);
593                    let min_weight = 1u16;
594                    let new0 = (current0 as i32)
595                        .saturating_add(i32::from(delta))
596                        .max(i32::from(min_weight));
597                    let new1 = (current1 as i32)
598                        .saturating_sub(i32::from(delta))
599                        .max(i32::from(min_weight));
600                    let sum_before = current0.saturating_add(current1);
601                    let sum_after = (new0 as u32).saturating_add(new1 as u32);
602                    if sum_before != sum_after {
603                        let diff = sum_before.saturating_sub(sum_after);
604                        weights[index] = new0 as u16;
605                        weights[index + 1] = (new1 as u32).saturating_add(diff) as u16;
606                    } else {
607                        weights[index] = new0 as u16;
608                        weights[index + 1] = new1 as u16;
609                    }
610                    let min_first = match orientation {
611                        Orientation::Horizontal => u32::from(constraints.min_width),
612                        Orientation::Vertical => u32::from(constraints.min_height),
613                    };
614                    let child_frac = u32::from(weights[index]) * total / total_weight;
615                    if child_frac < min_first {
616                        let correction = min_first.saturating_sub(child_frac) as u16;
617                        weights[index] = weights[index].saturating_add(correction);
618                        weights[index + 1] = weights[index + 1]
619                            .saturating_sub(correction)
620                            .max(min_weight);
621                    }
622                    return true;
623                }
624                let idx = path[0];
625                if idx >= children.len() {
626                    return false;
627                }
628                let sub_rects =
629                    split::split_rects_nary(area, *cont_orient, weights, children.len());
630                if let Some(sub) = sub_rects.get(idx) {
631                    children[idx].apply_drag(
632                        *sub,
633                        &path[1..],
634                        index,
635                        orientation,
636                        delta,
637                        constraints,
638                    )
639                } else {
640                    false
641                }
642            }
643            Self::Leaf(_) => false,
644        }
645    }
646
647    pub fn remove_leaf(&mut self, id: Id) -> Result<(), LayoutError> {
648        match self {
649            Self::Leaf(_) => Err(LayoutError::NotFound),
650            Self::Container {
651                children, weights, ..
652            } => {
653                let pos = children.iter().position(|c| c.unwrap_leaf() == Some(id));
654                if let Some(idx) = pos {
655                    children.remove(idx);
656                    if idx < weights.len() {
657                        weights.remove(idx);
658                    }
659                    if children.len() == 1 {
660                        let only = children.remove(0);
661                        *self = only;
662                    }
663                    return Ok(());
664                }
665
666                for child in children.iter_mut() {
667                    if child.remove_leaf(id).is_ok() {
668                        let empty_container =
669                            matches!(child, Self::Container { children: c, .. } if c.is_empty());
670                        if empty_container {
671                            let idx = children.iter().position(|c| c.unwrap_leaf().is_none() && matches!(c, Self::Container { children: cc, .. } if cc.is_empty()));
672                            if let Some(idx) = idx {
673                                children.remove(idx);
674                                if idx < weights.len() {
675                                    weights.remove(idx);
676                                }
677                            }
678                        }
679                        if children.len() == 1 {
680                            let only = children.remove(0);
681                            *self = only;
682                        }
683                        return Ok(());
684                    }
685                }
686                Err(LayoutError::NotFound)
687            }
688        }
689    }
690}
691
692#[cfg(test)]
693mod tests {
694    use super::*;
695    use crate::InsertPosition;
696
697    fn default_area() -> LayoutRect {
698        LayoutRect {
699            x: 0,
700            y: 0,
701            width: 80,
702            height: 24,
703        }
704    }
705
706    fn constraints() -> SizeConstraints {
707        SizeConstraints {
708            min_width: 2,
709            min_height: 2,
710        }
711    }
712
713    #[test]
714    fn bsp_insert_and_remove() {
715        let mut node: BspNode<usize> = BspNode::leaf(1);
716        assert!(
717            node.insert_leaf(1, 2, InsertPosition::Right, default_area(), &constraints())
718                .is_ok()
719        );
720        assert_eq!(node.all_leaf_ids(), vec![1, 2]);
721        assert!(node.remove_leaf(2).is_ok());
722        assert_eq!(node.unwrap_leaf(), Some(1));
723    }
724
725    #[test]
726    fn nary_insert_and_remove() {
727        let mut node: NaryNode<usize> = NaryNode::leaf(1);
728        assert!(
729            node.insert_leaf(1, 2, InsertPosition::Right, default_area(), &constraints())
730                .is_ok()
731        );
732        assert!(
733            node.insert_leaf(1, 3, InsertPosition::Left, default_area(), &constraints())
734                .is_ok()
735        );
736        assert!(node.remove_leaf(2).is_ok());
737        assert!(node.remove_leaf(3).is_ok());
738        assert_eq!(node.unwrap_leaf(), Some(1));
739    }
740
741    #[test]
742    fn bsp_insert_nonexistent_target_returns_not_found() {
743        let mut node: BspNode<usize> = BspNode::leaf(1);
744        assert_eq!(
745            node.insert_leaf(99, 2, InsertPosition::Right, default_area(), &constraints()),
746            Err(LayoutError::NotFound)
747        );
748    }
749
750    #[test]
751    fn bsp_insert_constraints_too_small() {
752        let mut node: BspNode<usize> = BspNode::leaf(1);
753        let small_area = LayoutRect {
754            x: 0,
755            y: 0,
756            width: 1,
757            height: 1,
758        };
759        let tight = SizeConstraints {
760            min_width: 10,
761            min_height: 10,
762        };
763        assert_eq!(
764            node.insert_leaf(1, 2, InsertPosition::Right, small_area, &tight),
765            Err(LayoutError::ConstraintViolated(tight))
766        );
767    }
768
769    #[test]
770    fn bsp_layout_returns_all_ids() {
771        let mut node: BspNode<&str> = BspNode::leaf("a");
772        node.insert_leaf(
773            "a",
774            "b",
775            InsertPosition::Right,
776            default_area(),
777            &constraints(),
778        )
779        .unwrap();
780        node.insert_leaf(
781            "b",
782            "c",
783            InsertPosition::Top,
784            default_area(),
785            &constraints(),
786        )
787        .unwrap();
788
789        let area = default_area();
790        let regions = node.layout(area);
791        let ids: Vec<&&str> = regions.iter().map(|(id, _)| id).collect();
792        assert_eq!(ids, vec![&"a", &"c", &"b"]);
793    }
794
795    #[test]
796    fn bsp_find_path_returns_correct_route() {
797        let mut node: BspNode<usize> = BspNode::leaf(1);
798        node.insert_leaf(1, 2, InsertPosition::Right, default_area(), &constraints())
799            .unwrap();
800
801        assert_eq!(node.find_path(1), Some(vec![false]));
802        assert_eq!(node.find_path(2), Some(vec![true]));
803    }
804
805    #[test]
806    fn bsp_apply_drag_adjusts_ratio() {
807        let mut node: BspNode<usize> = BspNode::leaf(1);
808        node.insert_leaf(1, 2, InsertPosition::Right, default_area(), &constraints())
809            .unwrap();
810        let path = vec![false];
811        let result = node.apply_drag(
812            default_area(),
813            &path,
814            Orientation::Horizontal,
815            10,
816            &constraints(),
817        );
818        assert!(result);
819        let regions = node.layout(default_area());
820        let (left_id, left) = regions.iter().find(|(id, _)| *id == 1).unwrap();
821        assert!(*left_id == 1);
822        // delta=10 rightward → left shrinks from 40 to ~26
823        assert!(left.width < 40);
824    }
825
826    #[test]
827    fn bsp_apply_drag_wrong_orientation_returns_false() {
828        let mut node: BspNode<usize> = BspNode::leaf(1);
829        node.insert_leaf(1, 2, InsertPosition::Right, default_area(), &constraints())
830            .unwrap();
831        let result = node.apply_drag(
832            default_area(),
833            &[false],
834            Orientation::Vertical,
835            10,
836            &constraints(),
837        );
838        assert!(!result);
839    }
840
841    #[test]
842    fn nary_subtree_any() {
843        let mut node: NaryNode<usize> = NaryNode::leaf(1);
844        node.insert_leaf(1, 2, InsertPosition::Right, default_area(), &constraints())
845            .unwrap();
846        assert!(node.subtree_any(&mut |id| id == 2));
847        assert!(!node.subtree_any(&mut |id| id == 99));
848    }
849
850    #[test]
851    fn nary_find_path_and_node_at_path() {
852        let mut node: NaryNode<usize> = NaryNode::leaf(1);
853        node.insert_leaf(1, 2, InsertPosition::Right, default_area(), &constraints())
854            .unwrap();
855        node.insert_leaf(2, 3, InsertPosition::Bottom, default_area(), &constraints())
856            .unwrap();
857
858        let path = node.find_path(3);
859        assert!(path.is_some());
860        let p = path.unwrap();
861        let found = node.node_at_path(&p);
862        assert!(found.is_some());
863        assert_eq!(found.unwrap().unwrap_leaf(), Some(3));
864    }
865
866    #[test]
867    fn nary_insert_constraints_too_small() {
868        let mut node: NaryNode<usize> = NaryNode::leaf(1);
869        let small_area = LayoutRect {
870            x: 0,
871            y: 0,
872            width: 1,
873            height: 1,
874        };
875        let tight = SizeConstraints {
876            min_width: 10,
877            min_height: 10,
878        };
879        assert_eq!(
880            node.insert_leaf(1, 2, InsertPosition::Right, small_area, &tight),
881            Err(LayoutError::ConstraintViolated(tight))
882        );
883    }
884
885    #[test]
886    fn nary_apply_drag_adjusts_weights() {
887        let mut node: NaryNode<usize> = NaryNode::leaf(1);
888        node.insert_leaf(1, 2, InsertPosition::Right, default_area(), &constraints())
889            .unwrap();
890        let path: Vec<usize> = Vec::new();
891        let result = node.apply_drag(
892            default_area(),
893            &path,
894            0,
895            Orientation::Horizontal,
896            5,
897            &constraints(),
898        );
899        assert!(result);
900        if let NaryNode::Container { weights, .. } = &node {
901            assert_eq!(weights[0], 6);
902            assert_eq!(weights[1], 1);
903        } else {
904            panic!("Expected Container");
905        }
906    }
907
908    #[test]
909    fn nary_layout_with_gaps_includes_gap() {
910        let mut node: NaryNode<usize> = NaryNode::leaf(1);
911        node.insert_leaf(1, 2, InsertPosition::Right, default_area(), &constraints())
912            .unwrap();
913        let regions = node.layout_with_gaps(default_area(), 2);
914        assert_eq!(regions.len(), 2);
915        let total_w: u16 = regions.iter().map(|(_, r)| r.width).sum();
916        assert!(total_w < 80);
917    }
918
919    #[test]
920    fn nary_split_area_for_path() {
921        let mut node: NaryNode<usize> = NaryNode::leaf(1);
922        node.insert_leaf(1, 2, InsertPosition::Right, default_area(), &constraints())
923            .unwrap();
924        let sub = node.split_area_for_path(default_area(), &[0]);
925        assert!(sub.is_some());
926        assert_eq!(sub.unwrap().width, 40);
927    }
928
929    #[cfg(feature = "std")]
930    mod proptests {
931        use super::*;
932        use proptest::prelude::*;
933
934        proptest! {
935            #[test]
936            fn bsp_layout_sum_equals_area(
937                id1 in 0u8..10u8,
938                id2 in 10u8..20u8,
939                w in 4u16..200u16,
940                h in 4u16..200u16,
941            ) {
942                prop_assume!(id1 != id2);
943                let constraints = SizeConstraints { min_width: 2, min_height: 2 };
944                let area = LayoutRect { x: 0, y: 0, width: w, height: h };
945                let mut node: BspNode<u8> = BspNode::leaf(id1);
946                let _ = node.insert_leaf(id1, id2, InsertPosition::Right, area, &constraints);
947                let regions = node.layout(area);
948                let mut sum_w = 0u16;
949                for (_, r) in &regions {
950                    sum_w = sum_w.saturating_add(r.width);
951                    // In a horizontal split all children share the parent height.
952                    prop_assert_eq!(r.height, h);
953                }
954                prop_assert_eq!(sum_w, w, "sum of child widths must equal parent width");
955            }
956        }
957    }
958}
term_wm_layout_engine/node.rs

term_wm_layout_engine/
node.rs
