1package layout
2
3import (
4 "math"
5 "sort"
6
7 "github.com/bnema/vev/internal/domain"
8)
9
10// Solve returns deterministic pane placements for root inside area.
11func Solve(root *Node, area domain.Rect) ([]Placement, bool) {
12 placements, _, ok := solveArea(root, area, false)
13 return placements, ok
14}
15
16// solveArea is the single geometry traversal behind Solve and
17// SolveWithDividers. Divider gaps are collected only when withDividers is set,
18// so both callers share one weight- and minimum-aware pass and cannot drift.
19func solveArea(root *Node, area domain.Rect, withDividers bool) ([]Placement, []Divider, bool) {
20 if root == nil || area.Width <= 0 || area.Height <= 0 {
21 return nil, nil, false
22 }
23 minWidth, ok := minimumExtent(root, Horizontal)
24 if !ok || area.Width < minWidth {
25 return nil, nil, false
26 }
27 minHeight, ok := minimumExtent(root, Vertical)
28 if !ok || area.Height < minHeight {
29 return nil, nil, false
30 }
31 var out []Placement
32 var dividers *[]Divider
33 if withDividers {
34 dividers = new([]Divider)
35 }
36 if !solve(root, area, &out, dividers) {
37 return nil, nil, false
38 }
39 if dividers == nil {
40 return out, nil, true
41 }
42 return out, *dividers, true
43}
44
45// solve appends the placements for n inside r. divs is nil when the caller does
46// not need divider geometry.
47func solve(n *Node, r domain.Rect, out *[]Placement, divs *[]Divider) bool {
48 switch n.Kind {
49 case Leaf:
50 if r.Width < MinPaneCols || r.Height < MinPaneRows {
51 return false
52 }
53 *out = append(*out, Placement{ID: n.Leaf, Content: r})
54 return true
55 case Split:
56 return solveSplit(n, r, out, divs)
57 case Stack:
58 return solveStack(n, r, out)
59 default:
60 return false
61 }
62}
63
64func solveSplit(n *Node, r domain.Rect, out *[]Placement, divs *[]Divider) bool {
65 rects, ok := splitChildRects(n, r)
66 if !ok {
67 return false
68 }
69 for i, child := range n.Children {
70 if i > 0 && divs != nil {
71 *divs = append(*divs, dividerBetween(n.Dir, r, rects[i-1]))
72 }
73 if !solve(child, rects[i], out, divs) {
74 return false
75 }
76 }
77 return true
78}
79
80func splitChildRects(n *Node, r domain.Rect) ([]domain.Rect, bool) {
81 count := len(n.Children)
82 if count == 0 {
83 return nil, false
84 }
85 if count == 1 {
86 return []domain.Rect{r}, true
87 }
88
89 total := r.Width
90 if n.Dir == Vertical {
91 total = r.Height
92 }
93 usable := total - (count - 1)
94 minimums := make([]int, count)
95 weights := make([]float64, count)
96 for i, child := range n.Children {
97 minimum, ok := minimumExtent(child, n.Dir)
98 if !ok {
99 return nil, false
100 }
101 minimums[i] = minimum
102 weights[i] = effectiveWeight(child.Weight)
103 }
104 extents, ok := distribute(usable, minimums, weights)
105 if !ok {
106 return nil, false
107 }
108
109 rects := make([]domain.Rect, count)
110 x, y := r.X, r.Y
111 for i, extent := range extents {
112 if n.Dir == Horizontal {
113 rects[i] = domain.Rect{X: x, Y: r.Y, Width: extent, Height: r.Height}
114 x += extent + 1
115 continue
116 }
117 rects[i] = domain.Rect{X: r.X, Y: y, Width: r.Width, Height: extent}
118 y += extent + 1
119 }
120 return rects, true
121}
122
123func effectiveWeight(weight float64) float64 {
124 if weight <= 0 || math.IsNaN(weight) || math.IsInf(weight, 0) {
125 return 1
126 }
127 return weight
128}
129
130func minimumExtent(n *Node, axis SplitDir) (int, bool) {
131 if n == nil {
132 return 0, false
133 }
134 switch n.Kind {
135 case Leaf:
136 if axis == Horizontal {
137 return MinPaneCols, true
138 }
139 return MinPaneRows, true
140 case Stack:
141 if len(n.Children) == 0 {
142 return 0, false
143 }
144 for _, child := range n.Children {
145 if child == nil || child.Kind != Leaf {
146 return 0, false
147 }
148 }
149 if axis == Horizontal {
150 return MinPaneCols, true
151 }
152 return len(n.Children) + 1, true
153 case Split:
154 if len(n.Children) == 0 {
155 return 0, false
156 }
157 if n.Dir == axis {
158 total := len(n.Children) - 1
159 for _, child := range n.Children {
160 minimum, ok := minimumExtent(child, axis)
161 if !ok {
162 return 0, false
163 }
164 total += minimum
165 }
166 return total, true
167 }
168 largest := 0
169 for _, child := range n.Children {
170 minimum, ok := minimumExtent(child, axis)
171 if !ok {
172 return 0, false
173 }
174 largest = max(largest, minimum)
175 }
176 return largest, true
177 default:
178 return 0, false
179 }
180}
181
182// distribute allocates total integer cells proportionally while respecting each
183// child's minimum. It uses stable largest-remainder rounding after all
184// constrained children have been pinned.
185func distribute(total int, minimums []int, weights []float64) ([]int, bool) {
186 if total < 0 || len(minimums) == 0 || len(minimums) != len(weights) {
187 return nil, false
188 }
189 minimumTotal := 0
190 for _, minimum := range minimums {
191 if minimum < 0 {
192 return nil, false
193 }
194 minimumTotal += minimum
195 }
196 if minimumTotal > total {
197 return nil, false
198 }
199
200 allocations := make([]int, len(minimums))
201 active := make([]bool, len(minimums))
202 for i := range active {
203 active[i] = true
204 }
205 remaining := total
206
207 for {
208 largest, sum := activeWeightScale(weights, active)
209 var pinned []int
210 for i := range active {
211 if !active[i] {
212 continue
213 }
214 quota := float64(remaining) * (effectiveWeight(weights[i]) / largest) / sum
215 if quota < float64(minimums[i]) {
216 pinned = append(pinned, i)
217 }
218 }
219 if len(pinned) == 0 {
220 break
221 }
222 for _, i := range pinned {
223 allocations[i] = minimums[i]
224 remaining -= minimums[i]
225 active[i] = false
226 }
227 }
228
229 largest, sum := activeWeightScale(weights, active)
230 type remainder struct {
231 index int
232 fraction float64
233 }
234 remainders := make([]remainder, 0, len(weights))
235 allocated := total - remaining
236 for i := range active {
237 if !active[i] {
238 continue
239 }
240 quota := float64(remaining) * (effectiveWeight(weights[i]) / largest) / sum
241 whole := int(math.Floor(quota))
242 allocations[i] = whole
243 allocated += whole
244 remainders = append(remainders, remainder{index: i, fraction: quota - float64(whole)})
245 }
246 sort.SliceStable(remainders, func(i, j int) bool {
247 return remainders[i].fraction > remainders[j].fraction
248 })
249 for cells, i := total-allocated, 0; cells > 0; cells, i = cells-1, i+1 {
250 allocations[remainders[i%len(remainders)].index]++
251 }
252 return allocations, true
253}
254
255func activeWeightScale(weights []float64, active []bool) (float64, float64) {
256 largest := 0.0
257 for i, weight := range weights {
258 if active[i] {
259 largest = math.Max(largest, effectiveWeight(weight))
260 }
261 }
262 sum := 0.0
263 for i, weight := range weights {
264 if active[i] {
265 sum += effectiveWeight(weight) / largest
266 }
267 }
268 return largest, sum
269}
270
271func solveStack(n *Node, r domain.Rect, out *[]Placement) bool {
272 count := len(n.Children)
273 if count == 0 || r.Width < MinPaneCols || r.Height < count+1 {
274 return false
275 }
276 idx := -1
277 for i, child := range n.Children {
278 if child.Kind != Leaf {
279 return false
280 }
281 if child.Leaf == n.Expanded {
282 idx = i
283 }
284 }
285 if idx < 0 {
286 return false
287 }
288 contentRows := r.Height - (count - 1)
289 for i, child := range n.Children {
290 if i < idx {
291 titleY := r.Y + i
292 *out = append(*out, Placement{ID: child.Leaf, TitleBar: domain.Rect{X: r.X, Y: titleY, Width: r.Width, Height: 1}, Collapsed: true, InStack: true})
293 continue
294 }
295 if i == idx {
296 *out = append(*out, Placement{
297 ID: child.Leaf,
298 Content: domain.Rect{X: r.X, Y: r.Y + idx, Width: r.Width, Height: contentRows},
299 InStack: true,
300 })
301 continue
302 }
303 titleY := r.Y + idx + contentRows + (i - idx - 1)
304 *out = append(*out, Placement{ID: child.Leaf, TitleBar: domain.Rect{X: r.X, Y: titleY, Width: r.Width, Height: 1}, Collapsed: true, InStack: true})
305 }
306 return true
307}