package main

// Guillotine-cut rectangle packing, integer only.
//
// Every monitor's logical work area starts life as one free rectangle. Placing
// a pane consumes the top-left corner of the chosen free rectangle; what is
// left is divided by a single straight cut that runs the full width or the
// full height of that free rectangle. That is what makes the packing a true
// guillotine packing: every region on screen can be produced by a sequence of
// edge-to-edge cuts, which is exactly the structure a tiling window manager
// can realise with nested splits.

// rect is an axis-aligned rectangle in logical pixels, relative to the origin
// of a monitor's work area.
type rect struct {
	X int `json:"x"`
	Y int `json:"y"`
	W int `json:"w"`
	H int `json:"h"`
}

func (r rect) area() int64 { return int64(r.W) * int64(r.H) }

// placement is where the packer put one unit.
type placement struct {
	Mon int
	R   rect
}

// packer holds the free-rectangle list for each monitor.
type packer struct {
	free [][]rect
}

func newPacker(mons []logicalMon) *packer {
	p := &packer{free: make([][]rect, len(mons))}
	for i, m := range mons {
		if m.W > 0 && m.H > 0 {
			p.free[i] = []rect{{X: 0, Y: 0, W: m.W, H: m.H}}
		}
	}
	return p
}

// place inserts a w x h rectangle using BEST AREA FIT: among all free
// rectangles that can hold it, take the one with the smallest area, so that
// large free regions are preserved for large panes. Ties are broken by lowest
// monitor index, then lowest y, then lowest x - never by map order - so the
// packer is fully deterministic.
func (p *packer) place(w, h int) (placement, bool) {
	if w <= 0 || h <= 0 {
		return placement{}, false
	}
	bestMon, bestIdx := -1, -1
	var bestArea int64
	var bestR rect
	for mi := range p.free {
		for ri, f := range p.free[mi] {
			if f.W < w || f.H < h {
				continue
			}
			a := f.area()
			better := false
			switch {
			case bestMon < 0:
				better = true
			case a < bestArea:
				better = true
			case a == bestArea:
				// same monitor (earlier monitors already win by iteration order)
				if mi == bestMon {
					if f.Y < bestR.Y || (f.Y == bestR.Y && f.X < bestR.X) {
						better = true
					}
				}
			}
			if better {
				bestMon, bestIdx, bestArea, bestR = mi, ri, a, f
			}
		}
	}
	if bestMon < 0 {
		return placement{}, false
	}
	used := rect{X: bestR.X, Y: bestR.Y, W: w, H: h}

	// Guillotine split of the remainder. The cut runs along whichever axis
	// leaves the SHORTER leftover strip, which keeps the surviving free
	// rectangles as chunky as possible (split-longer-leftover-axis rule).
	leftoverW := bestR.W - w
	leftoverH := bestR.H - h
	var a, b rect
	if leftoverW > leftoverH {
		// vertical cut: the full-height strip on the right survives whole
		a = rect{X: bestR.X + w, Y: bestR.Y, W: leftoverW, H: bestR.H}
		b = rect{X: bestR.X, Y: bestR.Y + h, W: w, H: leftoverH}
	} else {
		// horizontal cut: the full-width strip below survives whole
		a = rect{X: bestR.X + w, Y: bestR.Y, W: leftoverW, H: h}
		b = rect{X: bestR.X, Y: bestR.Y + h, W: bestR.W, H: leftoverH}
	}

	list := p.free[bestMon]
	list = append(list[:bestIdx], list[bestIdx+1:]...)
	if a.W > 0 && a.H > 0 {
		list = append(list, a)
	}
	if b.W > 0 && b.H > 0 {
		list = append(list, b)
	}
	p.free[bestMon] = list
	return placement{Mon: bestMon, R: used}, true
}

// freeArea reports the unused logical area left on each monitor.
func (p *packer) freeArea() []int64 {
	out := make([]int64, len(p.free))
	for i, l := range p.free {
		var s int64
		for _, f := range l {
			s += f.area()
		}
		out[i] = s
	}
	return out
}

// isqrt is an integer square root by Newton's method. Used so pane geometry
// can be derived from an ideal AREA without ever touching a float.
func isqrt(n int64) int64 {
	if n <= 0 {
		return 0
	}
	if n < 4 {
		return 1
	}
	x := n
	y := (x + 1) / 2
	for y < x {
		x = y
		y = (x + n/x) / 2
	}
	return x
}

// idealDims turns an ideal AREA plus a minimum size into concrete integer
// dimensions. The pane's preferred aspect ratio is taken to be its minimum
// aspect ratio (minWidth:minHeight), so a wide chart stays wide and a tall
// terminal stays tall as the area grows.
//
//	w / h = minW / minH   and   w * h = area   =>   w = sqrt(area * minW / minH)
func idealDims(minW, minH int, area int64) (int, int) {
	if minW < 1 {
		minW = 1
	}
	if minH < 1 {
		minH = 1
	}
	floor := int64(minW) * int64(minH)
	if area < floor {
		area = floor
	}
	w := isqrt(area * int64(minW) / int64(minH))
	if w < int64(minW) {
		w = int64(minW)
	}
	h := area / w
	if h < int64(minH) {
		h = int64(minH)
		w = area / h
		if w < int64(minW) {
			w = int64(minW)
		}
	}
	return int(w), int(h)
}