1package layout
2
3import (
4 "errors"
5 "math"
6 "sort"
7
8 "github.com/bnema/vev/internal/domain"
9)
10
11var (
12 ErrNotFound = errors.New("pane not found")
13 ErrTooSmall = errors.New("layout too small")
14 ErrNoPane = errors.New("no pane in direction")
15 ErrNotInSplit = errors.New("pane is not in a split")
16 ErrNotToggleable = errors.New("layout node is not toggleable")
17)
18
19// ResizeFocus changes the focused pane subtree's share in the nearest split on
20// axis. It commits only after the candidate layout solves successfully.
21func (t *Tree) ResizeFocus(axis Axis, delta int, area domain.Rect) error {
22 candidate := t.clone()
23 if candidate == nil || candidate.Root == nil {
24 return ErrNotInSplit
25 }
26 dir, ok := splitDirForAxis(axis)
27 if !ok || !hasMatchingSplit(candidate.Root, candidate.Focus, dir) {
28 return ErrNotInSplit
29 }
30 if _, solved := Solve(candidate.Root, area); !solved {
31 return ErrTooSmall
32 }
33
34 splitNode, splitArea, targetIndex, found := nearestMatchingSplit(candidate.Root, candidate.Focus, dir, area)
35 if !found {
36 return ErrTooSmall
37 }
38 rects, solved := splitChildRects(splitNode, splitArea)
39 if !solved {
40 return ErrTooSmall
41 }
42 extents := make([]int, len(rects))
43 minimums := make([]int, len(rects))
44 for i, rect := range rects {
45 extents[i] = rect.Width
46 if dir == Vertical {
47 extents[i] = rect.Height
48 }
49 minimum, valid := minimumExtent(splitNode.Children[i], dir)
50 if !valid {
51 return ErrTooSmall
52 }
53 minimums[i] = minimum
54 splitNode.Children[i].Weight = float64(extents[i])
55 }
56
57 requested := delta
58 if requested < 0 {
59 if requested == math.MinInt {
60 requested = math.MaxInt
61 } else {
62 requested = -requested
63 }
64 }
65 if requested == 0 {
66 return ErrTooSmall
67 }
68
69 neighbor := -1
70 transfer := 0
71 if delta > 0 {
72 for _, index := range preferredNeighbors(targetIndex, len(extents)) {
73 available := extents[index] - minimums[index]
74 if available <= 0 {
75 continue
76 }
77 neighbor = index
78 transfer = min(requested, available)
79 break
80 }
81 } else {
82 neighbors := preferredNeighbors(targetIndex, len(extents))
83 available := extents[targetIndex] - minimums[targetIndex]
84 if len(neighbors) > 0 && available > 0 {
85 neighbor = neighbors[0]
86 transfer = min(requested, available)
87 }
88 }
89 if neighbor < 0 || transfer == 0 {
90 return ErrTooSmall
91 }
92
93 if delta > 0 {
94 extents[targetIndex] += transfer
95 extents[neighbor] -= transfer
96 } else {
97 extents[targetIndex] -= transfer
98 extents[neighbor] += transfer
99 }
100 splitNode.Children[targetIndex].Weight = float64(extents[targetIndex])
101 splitNode.Children[neighbor].Weight = float64(extents[neighbor])
102 if _, solved := Solve(candidate.Root, area); !solved {
103 return ErrTooSmall
104 }
105 *t = *candidate
106 return nil
107}
108
109// Equalize resets every split's direct child shares to their defaults. The
110// candidate must remain solvable before it is committed.
111func (t *Tree) Equalize(area domain.Rect) error {
112 candidate := t.clone()
113 if candidate == nil || candidate.Root == nil {
114 return ErrTooSmall
115 }
116 clearSplitChildWeights(candidate.Root)
117 if _, ok := Solve(candidate.Root, area); !ok {
118 return ErrTooSmall
119 }
120 *t = *candidate
121 return nil
122}
123
124// CanResize reports whether the focused pane is contained by any split.
125func (t *Tree) CanResize() bool {
126 if t == nil || t.Root == nil {
127 return false
128 }
129 return hasMatchingSplit(t.Root, t.Focus, Horizontal) || hasMatchingSplit(t.Root, t.Focus, Vertical)
130}
131
132func splitDirForAxis(axis Axis) (SplitDir, bool) {
133 switch axis {
134 case Width:
135 return Horizontal, true
136 case Height:
137 return Vertical, true
138 default:
139 return Horizontal, false
140 }
141}
142
143func hasMatchingSplit(n *Node, focus PaneID, dir SplitDir) bool {
144 if n == nil || !containsLeaf(n, focus) {
145 return false
146 }
147 for _, child := range n.Children {
148 if containsLeaf(child, focus) && hasMatchingSplit(child, focus, dir) {
149 return true
150 }
151 }
152 return n.Kind == Split && n.Dir == dir
153}
154
155func nearestMatchingSplit(n *Node, focus PaneID, dir SplitDir, area domain.Rect) (*Node, domain.Rect, int, bool) {
156 if n == nil || !containsLeaf(n, focus) {
157 return nil, domain.Rect{}, 0, false
158 }
159 childAreas := nodeChildAreas(n, area)
160 for i, child := range n.Children {
161 if !containsLeaf(child, focus) {
162 continue
163 }
164 childArea := area
165 if i < len(childAreas) {
166 childArea = childAreas[i]
167 }
168 if match, matchArea, index, ok := nearestMatchingSplit(child, focus, dir, childArea); ok {
169 return match, matchArea, index, true
170 }
171 if n.Kind == Split && n.Dir == dir {
172 return n, area, i, true
173 }
174 return nil, domain.Rect{}, 0, false
175 }
176 return nil, domain.Rect{}, 0, false
177}
178
179func preferredNeighbors(target, count int) []int {
180 neighbors := make([]int, 0, 2)
181 if target+1 < count {
182 neighbors = append(neighbors, target+1)
183 }
184 if target > 0 {
185 neighbors = append(neighbors, target-1)
186 }
187 return neighbors
188}
189
190func clearSplitChildWeights(n *Node) {
191 if n == nil {
192 return
193 }
194 if n.Kind == Split {
195 clearChildWeights(n)
196 }
197 for _, child := range n.Children {
198 clearSplitChildWeights(child)
199 }
200}
201
202// Split adds newID next to target. The after flag controls whether the new pane
203// is placed after target on the chosen axis.
204func (t *Tree) Split(target PaneID, dir Direction, after bool, newID PaneID, area domain.Rect) error {
205 candidate := t.clone()
206 if candidate == nil || candidate.Root == nil || !insertSplit(candidate.Root, target, axisFor(dir), after, newID, area) {
207 return ErrNotFound
208 }
209 candidate.Focus = newID
210 if _, ok := Solve(candidate.Root, area); !ok {
211 return ErrTooSmall
212 }
213 *t = *candidate
214 return nil
215}
216
217func insertSplit(n *Node, target PaneID, axis SplitDir, after bool, newID PaneID, area domain.Rect) bool {
218 if n == nil {
219 return false
220 }
221 childAreas := nodeChildAreas(n, area)
222 for i, child := range n.Children {
223 if child.Kind == Leaf && child.Leaf == target {
224 newLeaf := NewLeaf(newID)
225 if n.Kind == Split && n.Dir == axis {
226 normalizeChildWeightsFromArea(n, area)
227 at := i
228 if after {
229 at++
230 }
231 n.Children = append(n.Children, nil)
232 copy(n.Children[at+1:], n.Children[at:])
233 n.Children[at] = newLeaf
234 return true
235 }
236 if n.Kind == Stack {
237 weight := n.Weight
238 stack := n.clone()
239 stack.Weight = 0
240 clearChildWeights(stack)
241 children := []*Node{stack, newLeaf}
242 if !after {
243 children = []*Node{newLeaf, stack}
244 }
245 *n = Node{Kind: Split, Dir: axis, Children: children, Weight: weight}
246 return true
247 }
248 weight := child.Weight
249 child.Weight = 0
250 children := []*Node{child, newLeaf}
251 if !after {
252 children = []*Node{newLeaf, child}
253 }
254 n.Children[i] = &Node{Kind: Split, Dir: axis, Children: children, Weight: weight}
255 return true
256 }
257 childArea := area
258 if i < len(childAreas) {
259 childArea = childAreas[i]
260 }
261 if insertSplit(child, target, axis, after, newID, childArea) {
262 return true
263 }
264 }
265 if n.Kind == Leaf && n.Leaf == target {
266 weight := n.Weight
267 existing := n.clone()
268 existing.Weight = 0
269 children := []*Node{existing, NewLeaf(newID)}
270 if !after {
271 children = []*Node{NewLeaf(newID), existing}
272 }
273 *n = Node{Kind: Split, Dir: axis, Children: children, Weight: weight}
274 return true
275 }
276 return false
277}
278
279func nodeChildAreas(n *Node, area domain.Rect) []domain.Rect {
280 if n.Kind == Split {
281 rects, ok := splitChildRects(n, area)
282 if ok {
283 return rects
284 }
285 }
286 areas := make([]domain.Rect, len(n.Children))
287 for i := range areas {
288 areas[i] = area
289 }
290 return areas
291}
292
293func normalizeChildWeightsFromArea(n *Node, area domain.Rect) {
294 rects, ok := splitChildRects(n, area)
295 if !ok || len(rects) == 0 {
296 return
297 }
298 for i, rect := range rects {
299 extent := rect.Width
300 if n.Dir == Vertical {
301 extent = rect.Height
302 }
303 n.Children[i].Weight = float64(extent)
304 }
305}
306
307func clearChildWeights(n *Node) {
308 for _, child := range n.Children {
309 child.Weight = 0
310 }
311}
312
313// StackNew puts newID in target's stack, creating one if target is not stacked.
314func (t *Tree) StackNew(target, newID PaneID, area domain.Rect) error {
315 candidate := t.clone()
316 if candidate == nil || !stackNew(candidate.Root, target, newID) {
317 return ErrNotFound
318 }
319 candidate.Focus = newID
320 if _, ok := Solve(candidate.Root, area); !ok {
321 return ErrTooSmall
322 }
323 *t = *candidate
324 return nil
325}
326
327func stackNew(n *Node, target, newID PaneID) bool {
328 if n == nil {
329 return false
330 }
331 if n.Kind == Stack {
332 for _, child := range n.Children {
333 if child.Kind == Leaf && child.Leaf == target {
334 n.Children = append(n.Children, NewLeaf(newID))
335 n.Expanded = newID
336 clearChildWeights(n)
337 return true
338 }
339 }
340 }
341 for i, child := range n.Children {
342 if child.Kind == Leaf && child.Leaf == target {
343 weight := child.Weight
344 child.Weight = 0
345 n.Children[i] = &Node{Kind: Stack, Children: []*Node{child, NewLeaf(newID)}, Expanded: newID, Weight: weight}
346 return true
347 }
348 if stackNew(child, target, newID) {
349 return true
350 }
351 }
352 if n.Kind == Leaf && n.Leaf == target {
353 weight := n.Weight
354 *n = Node{Kind: Stack, Children: []*Node{NewLeaf(target), NewLeaf(newID)}, Expanded: newID, Weight: weight}
355 return true
356 }
357 return false
358}
359
360// ToggleStack converts a stack back to a vertical split. For an unstacked leaf in
361// a two-child split, it converts that split to a stack.
362func (t *Tree) ToggleStack(target PaneID, area domain.Rect) error {
363 candidate := t.clone()
364 result := toggleStack(candidate.Root, target)
365 switch result {
366 case toggleNotFound:
367 return ErrNotFound
368 case toggleNotToggleable:
369 return ErrNotToggleable
370 }
371 if _, ok := Solve(candidate.Root, area); !ok {
372 return ErrTooSmall
373 }
374 *t = *candidate
375 return nil
376}
377
378type toggleResult int
379
380const (
381 toggleNotFound toggleResult = iota
382 toggleToggled
383 toggleNotToggleable
384)
385
386func toggleStack(n *Node, target PaneID) toggleResult {
387 if n == nil {
388 return toggleNotFound
389 }
390 for _, child := range n.Children {
391 if child.Kind == Leaf || !containsLeaf(child, target) {
392 continue
393 }
394 result := toggleStack(child, target)
395 if result != toggleNotFound {
396 return result
397 }
398 }
399 if !containsLeaf(n, target) {
400 return toggleNotFound
401 }
402 if n.Kind == Stack {
403 if stackDirectLeafIndex(n, target) < 0 {
404 return toggleNotToggleable
405 }
406 n.Kind = Split
407 n.Dir = Vertical
408 n.Expanded = ""
409 clearChildWeights(n)
410 return toggleToggled
411 }
412 if n.Kind == Split && len(n.Children) == 2 && splitDirectLeavesContain(n, target) {
413 n.Kind = Stack
414 n.Expanded = target
415 clearChildWeights(n)
416 return toggleToggled
417 }
418 return toggleNotToggleable
419}
420
421func stackDirectLeafIndex(n *Node, target PaneID) int {
422 for i, child := range n.Children {
423 if child.Kind == Leaf && child.Leaf == target {
424 return i
425 }
426 }
427 return -1
428}
429
430func splitDirectLeavesContain(n *Node, target PaneID) bool {
431 for _, child := range n.Children {
432 if child.Kind != Leaf {
433 return false
434 }
435 }
436 return n.Children[0].Leaf == target || n.Children[1].Leaf == target
437}
438
439// Close removes target and dissolves single-child containers.
440func (t *Tree) Close(target PaneID) error {
441 candidate := t.clone()
442 if candidate == nil || candidate.Root == nil || !containsLeaf(candidate.Root, target) {
443 return ErrNotFound
444 }
445 if candidate.Root.Kind == Leaf && candidate.Root.Leaf == target {
446 candidate.Root = nil
447 candidate.Focus = ""
448 *t = *candidate
449 return nil
450 }
451 refocus := closeRefocusCandidate(candidate.Root, target)
452 root, removed := closeNode(candidate.Root, target)
453 if !removed {
454 return ErrNotFound
455 }
456 candidate.Root = root
457 if candidate.Focus == target {
458 if refocus != "" && containsLeaf(candidate.Root, refocus) {
459 candidate.Focus = refocus
460 } else {
461 ids := leafIDs(candidate.Root)
462 if len(ids) > 0 {
463 candidate.Focus = ids[0]
464 } else {
465 candidate.Focus = ""
466 }
467 }
468 setExpanded(candidate.Root, candidate.Focus)
469 }
470 *t = *candidate
471 return nil
472}
473
474func closeNode(n *Node, target PaneID) (*Node, bool) {
475 if n.Kind == Leaf {
476 if n.Leaf == target {
477 return nil, true
478 }
479 return n, false
480 }
481 removed := false
482 children := n.Children[:0]
483 for _, child := range n.Children {
484 newChild, didRemove := closeNode(child, target)
485 removed = removed || didRemove
486 if newChild != nil {
487 children = append(children, newChild)
488 }
489 }
490 n.Children = children
491 if !removed {
492 return n, false
493 }
494 if n.Kind == Stack && n.Expanded == target && len(n.Children) > 0 {
495 n.Expanded = firstLeaf(n.Children[0])
496 }
497 if (n.Kind == Stack || n.Kind == Split) && len(n.Children) == 1 {
498 promoted := n.Children[0]
499 promoted.Weight = n.Weight
500 return promoted, true
501 }
502 return n, true
503}
504
505func closeRefocusCandidate(n *Node, target PaneID) PaneID {
506 if n == nil || n.Kind == Leaf {
507 return ""
508 }
509 for i, child := range n.Children {
510 if !containsLeaf(child, target) {
511 continue
512 }
513 if child.Kind == Leaf && child.Leaf == target {
514 if i > 0 {
515 return lastLeaf(n.Children[i-1])
516 }
517 if i+1 < len(n.Children) {
518 return firstLeaf(n.Children[i+1])
519 }
520 return ""
521 }
522 if id := closeRefocusCandidate(child, target); id != "" {
523 return id
524 }
525 if i > 0 {
526 return lastLeaf(n.Children[i-1])
527 }
528 if i+1 < len(n.Children) {
529 return firstLeaf(n.Children[i+1])
530 }
531 return ""
532 }
533 return ""
534}
535
536// ContainsLeaf reports whether n contains a leaf with id.
537func ContainsLeaf(n *Node, id PaneID) bool { return containsLeaf(n, id) }
538
539func containsLeaf(n *Node, id PaneID) bool {
540 if n == nil {
541 return false
542 }
543 if n.Kind == Leaf {
544 return n.Leaf == id
545 }
546 for _, child := range n.Children {
547 if containsLeaf(child, id) {
548 return true
549 }
550 }
551 return false
552}
553
554func firstLeaf(n *Node) PaneID {
555 if n.Kind == Leaf {
556 return n.Leaf
557 }
558 for _, child := range n.Children {
559 if id := firstLeaf(child); id != "" {
560 return id
561 }
562 }
563 return ""
564}
565
566func lastLeaf(n *Node) PaneID {
567 if n.Kind == Leaf {
568 return n.Leaf
569 }
570 for i := len(n.Children) - 1; i >= 0; i-- {
571 if id := lastLeaf(n.Children[i]); id != "" {
572 return id
573 }
574 }
575 return ""
576}
577
578func setExpanded(n *Node, id PaneID) bool {
579 if n == nil {
580 return false
581 }
582 if n.Kind == Stack && stackDirectLeafIndex(n, id) >= 0 {
583 n.Expanded = id
584 return true
585 }
586 for _, child := range n.Children {
587 if setExpanded(child, id) {
588 return true
589 }
590 }
591 return false
592}
593
594// LeafIDs returns the leaf ids under n in layout order.
595func LeafIDs(n *Node) []PaneID { return leafIDs(n) }
596
597func leafIDs(n *Node) []PaneID {
598 if n == nil {
599 return nil
600 }
601 if n.Kind == Leaf {
602 return []PaneID{n.Leaf}
603 }
604 var ids []PaneID
605 for _, child := range n.Children {
606 ids = append(ids, leafIDs(child)...)
607 }
608 return ids
609}
610
611// FocusSpan returns the solved focus rectangle of the focused pane.
612func (t *Tree) FocusSpan(area domain.Rect) (domain.Rect, error) {
613 if t == nil || t.Root == nil {
614 return domain.Rect{}, ErrNotFound
615 }
616 placements, ok := Solve(t.Root, area)
617 if !ok {
618 return domain.Rect{}, ErrTooSmall
619 }
620 for _, placement := range placements {
621 if placement.ID == t.Focus {
622 return focusRect(placement), nil
623 }
624 }
625 return domain.Rect{}, ErrNotFound
626}
627
628// EntryPane returns the pane on the facing edge that best preserves span on
629// the perpendicular axis. It does not mutate the tree.
630func (t *Tree) EntryPane(dir Direction, span, area domain.Rect) (PaneID, error) {
631 if t == nil || t.Root == nil {
632 return "", ErrNotFound
633 }
634 placements, ok := Solve(t.Root, area)
635 if !ok {
636 return "", ErrTooSmall
637 }
638
639 outside := span
640 switch dir {
641 case Left:
642 outside.X = area.X + area.Width
643 case Right:
644 outside.X = area.X - span.Width
645 case Up:
646 outside.Y = area.Y + area.Height
647 case Down:
648 outside.Y = area.Y - span.Height
649 default:
650 return "", ErrNoPane
651 }
652
653 return selectFacingCandidate(placements, outside, dir, facingGapFirst)
654}
655
656// FocusEnter focuses the best pane on the facing edge and expands it when it
657// is a collapsed stack member.
658func (t *Tree) FocusEnter(dir Direction, span, area domain.Rect) error {
659 id, err := t.EntryPane(dir, span, area)
660 if err != nil {
661 return err
662 }
663 t.Focus = id
664 setExpanded(t.Root, id)
665 return nil
666}
667
668// FocusDir moves focus in dir. Vertical movement within a stack walks stack
669// members before falling back to geometric focus.
670func (t *Tree) FocusDir(dir Direction, area domain.Rect) error {
671 if t.Root == nil {
672 return ErrNotFound
673 }
674 if (dir == Up || dir == Down) && focusStackLocal(t.Root, t.Focus, dir, &t.Focus) {
675 return nil
676 }
677 placements, ok := Solve(t.Root, area)
678 if !ok {
679 return ErrTooSmall
680 }
681 currentIdx := -1
682 for i, p := range placements {
683 if p.ID == t.Focus {
684 currentIdx = i
685 break
686 }
687 }
688 if currentIdx < 0 {
689 return ErrNotFound
690 }
691 current := focusRect(placements[currentIdx])
692 candidate, err := selectFacingCandidate(placements, current, dir, facingOverlapFirst)
693 if err != nil {
694 return err
695 }
696 t.Focus = candidate
697 setExpanded(t.Root, t.Focus)
698 return nil
699}
700
701type facingMetricPriority uint8
702
703const (
704 facingGapFirst facingMetricPriority = iota
705 facingOverlapFirst
706)
707
708type facingCandidate struct {
709 id PaneID
710 gap int
711 overlap int
712}
713
714func selectFacingCandidate(placements []Placement, from domain.Rect, dir Direction, priority facingMetricPriority) (PaneID, error) {
715 candidates := make([]facingCandidate, 0, len(placements))
716 for _, placement := range placements {
717 if facing, gap, perpendicularOverlap := sideGapOverlap(from, focusRect(placement), dir); facing {
718 candidates = append(candidates, facingCandidate{id: placement.ID, gap: gap, overlap: perpendicularOverlap})
719 }
720 }
721 if len(candidates) == 0 {
722 return "", ErrNoPane
723 }
724 sort.Slice(candidates, func(i, j int) bool {
725 if priority == facingGapFirst {
726 if candidates[i].gap != candidates[j].gap {
727 return candidates[i].gap < candidates[j].gap
728 }
729 if candidates[i].overlap != candidates[j].overlap {
730 return candidates[i].overlap > candidates[j].overlap
731 }
732 } else {
733 if candidates[i].overlap != candidates[j].overlap {
734 return candidates[i].overlap > candidates[j].overlap
735 }
736 if candidates[i].gap != candidates[j].gap {
737 return candidates[i].gap < candidates[j].gap
738 }
739 }
740 return candidates[i].id < candidates[j].id
741 })
742 return candidates[0].id, nil
743}
744
745func focusStackLocal(n *Node, id PaneID, dir Direction, focus *PaneID) bool {
746 if n.Kind == Stack {
747 idx := stackDirectLeafIndex(n, id)
748 if idx >= 0 {
749 if next := adjacentStackLeaf(n, idx, dir); next != "" {
750 n.Expanded = next
751 *focus = next
752 return true
753 }
754 return false
755 }
756 }
757 for _, child := range n.Children {
758 if focusStackLocal(child, id, dir, focus) {
759 return true
760 }
761 }
762 return false
763}
764
765func adjacentStackLeaf(n *Node, idx int, dir Direction) PaneID {
766 step := 0
767 switch dir {
768 case Up:
769 step = -1
770 case Down:
771 step = 1
772 default:
773 return ""
774 }
775 for i := idx + step; i >= 0 && i < len(n.Children); i += step {
776 if n.Children[i].Kind == Leaf {
777 return n.Children[i].Leaf
778 }
779 }
780 return ""
781}
782
783func focusRect(p Placement) domain.Rect {
784 if p.TitleBar.Height == 0 {
785 return p.Content
786 }
787 if p.Content.Height == 0 {
788 return p.TitleBar
789 }
790 y := p.TitleBar.Y
791 height := p.Content.Y + p.Content.Height - y
792 return domain.Rect{X: p.TitleBar.X, Y: y, Width: p.TitleBar.Width, Height: height}
793}
794
795func sideGapOverlap(a, b domain.Rect, dir Direction) (bool, int, int) {
796 ar, ab := a.X+a.Width, a.Y+a.Height
797 br, bb := b.X+b.Width, b.Y+b.Height
798 switch dir {
799 case Left:
800 if br > a.X {
801 return false, 0, 0
802 }
803 return true, a.X - br, overlap(a.Y, ab, b.Y, bb)
804 case Right:
805 if b.X < ar {
806 return false, 0, 0
807 }
808 return true, b.X - ar, overlap(a.Y, ab, b.Y, bb)
809 case Up:
810 if bb > a.Y {
811 return false, 0, 0
812 }
813 return true, a.Y - bb, overlap(a.X, ar, b.X, br)
814 case Down:
815 if b.Y < ab {
816 return false, 0, 0
817 }
818 return true, b.Y - ab, overlap(a.X, ar, b.X, br)
819 default:
820 return false, 0, 0
821 }
822}
823
824func overlap(a0, a1, b0, b1 int) int {
825 lo := max(a0, b0)
826 hi := min(a1, b1)
827 if hi <= lo {
828 return 0
829 }
830 return hi - lo
831}