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