package main

import (
	"fmt"
	"sort"
	"strings"
)

// ---------------------------------------------------------------------------
// Scoring constants. Everything is integer; satisfaction is per-mille.
// ---------------------------------------------------------------------------

const (
	// satFull is full satisfaction, expressed per-mille.
	satFull int64 = 1000
	// tabFactor is the delivered value of a pane that is present but sitting
	// behind a tab rather than being visible at a glance. A stacked pane is
	// therefore always worth more than a dropped one (700 > 0) and always
	// worth less than a pane you can see (700 < 1000).
	tabFactor int64 = 700
	// maxConfigs bounds the stack-configuration enumeration.
	maxConfigs = 4096
	// maxImproveRounds bounds the local-search loop.
	maxImproveRounds = 200
)

// shrinkLevels is the uniform shrink schedule, in percent of ideal linear
// size. Level 0 means "everything at its stated minimum".
var shrinkLevels = []int{100, 95, 90, 85, 80, 75, 70, 65, 60, 55, 50, 45, 40, 35, 30, 25, 20, 15, 10, 0}

// ---------------------------------------------------------------------------
// Units: what the packer actually places
// ---------------------------------------------------------------------------

// A unit is one rectangle to be placed: either a single pane, or a tab stack
// of two or more panes from the same stack group that share one rectangle.
type unit struct {
	key       string
	members   []int // pane indices, front tab first
	group     string
	minW      int
	minH      int
	idealW    int
	idealH    int
	idealArea int64
	required  bool
	priority  int
	fullValue int64 // value if placed at ideal size
}

func (u unit) minArea() int64 { return int64(u.minW) * int64(u.minH) }

func unitSize(u unit, level int) (int, int) {
	w := u.idealW * level / 100
	h := u.idealH * level / 100
	if w < u.minW {
		w = u.minW
	}
	if h < u.minH {
		h = u.minH
	}
	return w, h
}

func satPerMille(area, idealArea int64) int64 {
	if idealArea <= 0 {
		return satFull
	}
	s := satFull * area / idealArea
	if s > satFull {
		s = satFull
	}
	if s < 0 {
		s = 0
	}
	return s
}

func makeUnit(sc Scene, members []int) unit {
	u := unit{members: append([]int(nil), members...)}
	ids := make([]string, 0, len(members))
	for k, i := range members {
		p := sc.Panes[i]
		ids = append(ids, p.ID)
		if p.MinWidth > u.minW {
			u.minW = p.MinWidth
		}
		if p.MinHeight > u.minH {
			u.minH = p.MinHeight
		}
		if p.IdealArea > u.idealArea {
			u.idealArea = p.IdealArea
		}
		if p.Required {
			u.required = true
		}
		if p.Priority > u.priority {
			u.priority = p.Priority
		}
		if k == 0 {
			u.group = p.StackGroup
		}
		f := satFull
		if k > 0 {
			f = tabFactor
		}
		u.fullValue += int64(p.Priority) * satFull * f / 1000
	}
	if len(members) < 2 {
		u.group = ""
	}
	u.idealW, u.idealH = idealDims(u.minW, u.minH, u.idealArea)
	u.key = strings.Join(ids, "+")
	return u
}

// ---------------------------------------------------------------------------
// Stack configurations
// ---------------------------------------------------------------------------

type groupSpec struct {
	name    string
	members []int
}

// stackGroups returns the stackable groups of a scene, each with its members
// ordered by descending priority (ties by pane id) so that the highest
// priority pane is the front tab.
func stackGroups(sc Scene) []groupSpec {
	byName := map[string][]int{}
	for i, p := range sc.Panes {
		if p.Stackable && p.StackGroup != "" {
			byName[p.StackGroup] = append(byName[p.StackGroup], i)
		}
	}
	names := make([]string, 0, len(byName))
	for n := range byName {
		names = append(names, n)
	}
	sort.Strings(names)
	out := make([]groupSpec, 0, len(names))
	for _, n := range names {
		ms := byName[n]
		sort.SliceStable(ms, func(a, b int) bool {
			pa, pb := sc.Panes[ms[a]], sc.Panes[ms[b]]
			if pa.Priority != pb.Priority {
				return pa.Priority > pb.Priority
			}
			return pa.ID < pb.ID
		})
		out = append(out, groupSpec{name: n, members: ms})
	}
	return out
}

// buildUnits turns a scene plus one stack configuration into a unit list.
// splits[g] = s means: the top s panes of group g (by priority) get their own
// rectangle, and the remaining panes share a single tab stack.
func buildUnits(sc Scene, groups []groupSpec, splits []int) []unit {
	inGroup := map[int]bool{}
	var units []unit
	for gi, g := range groups {
		s := splits[gi]
		if s > len(g.members) {
			s = len(g.members)
		}
		for _, m := range g.members {
			inGroup[m] = true
		}
		for _, m := range g.members[:s] {
			units = append(units, makeUnit(sc, []int{m}))
		}
		rest := g.members[s:]
		switch {
		case len(rest) == 0:
		case len(rest) == 1:
			units = append(units, makeUnit(sc, rest))
		default:
			units = append(units, makeUnit(sc, rest))
		}
	}
	for i := range sc.Panes {
		if !inGroup[i] {
			units = append(units, makeUnit(sc, []int{i}))
		}
	}
	sort.SliceStable(units, func(a, b int) bool { return units[a].key < units[b].key })
	return units
}

// enumerateConfigs lists the stack configurations to search. For g groups of
// sizes k1..kg the full space is (k1+1)*...*(kg+1); if that exceeds
// maxConfigs the search falls back to the two extremes per group
// (all-stacked / all-separate), and then to all-stacked alone.
func enumerateConfigs(groups []groupSpec) ([][]int, string) {
	if len(groups) == 0 {
		return [][]int{{}}, "exhaustive"
	}
	total := 1
	for _, g := range groups {
		total *= len(g.members) + 1
		if total > maxConfigs {
			break
		}
	}
	choices := make([][]int, len(groups))
	mode := "exhaustive"
	if total <= maxConfigs && total > 0 {
		for i, g := range groups {
			c := make([]int, 0, len(g.members)+1)
			for s := 0; s <= len(g.members); s++ {
				c = append(c, s)
			}
			choices[i] = c
		}
	} else {
		mode = "extremes"
		ext := 1
		for i, g := range groups {
			choices[i] = []int{0, len(g.members)}
			ext *= 2
		}
		if ext > maxConfigs {
			mode = "all-stacked"
			for i := range groups {
				choices[i] = []int{0}
			}
		}
	}
	var out [][]int
	cur := make([]int, len(groups))
	var rec func(i int)
	rec = func(i int) {
		if i == len(groups) {
			out = append(out, append([]int(nil), cur...))
			return
		}
		for _, v := range choices[i] {
			cur[i] = v
			rec(i + 1)
		}
	}
	rec(0)
	return out, mode
}

// ---------------------------------------------------------------------------
// Packing a chosen set of units
// ---------------------------------------------------------------------------

type solution struct {
	active []bool
	level  int
	places []placement
	score  int64
	ok     bool
}

func fitsSomewhere(u unit, mons []logicalMon) bool {
	for _, m := range mons {
		if m.W >= u.minW && m.H >= u.minH {
			return true
		}
	}
	return false
}

// packOrder places the largest rectangles first (decreasing-area heuristic),
// with priority and then key as deterministic tie-breaks.
func packOrder(units []unit, active []bool, level int) []int {
	var idx []int
	for i := range units {
		if active[i] {
			idx = append(idx, i)
		}
	}
	sort.SliceStable(idx, func(a, b int) bool {
		ua, ub := units[idx[a]], units[idx[b]]
		wa, ha := unitSize(ua, level)
		wb, hb := unitSize(ub, level)
		aa, ab := int64(wa)*int64(ha), int64(wb)*int64(hb)
		if aa != ab {
			return aa > ab
		}
		if ua.priority != ub.priority {
			return ua.priority > ub.priority
		}
		return ua.key < ub.key
	})
	return idx
}

// tryPack finds the largest shrink level at which every active unit can be
// guillotine-packed onto the monitors.
func tryPack(units []unit, active []bool, mons []logicalMon) (int, []placement, bool) {
	for _, level := range shrinkLevels {
		p := newPacker(mons)
		places := make([]placement, len(units))
		good := true
		for _, ui := range packOrder(units, active, level) {
			w, h := unitSize(units[ui], level)
			pl, ok := p.place(w, h)
			if !ok {
				good = false
				break
			}
			places[ui] = pl
		}
		if good {
			return level, places, true
		}
	}
	return 0, nil, false
}

func scoreSolution(sc Scene, units []unit, active []bool, level int) int64 {
	var total int64
	for i, u := range units {
		if !active[i] {
			continue
		}
		w, h := unitSize(u, level)
		area := int64(w) * int64(h)
		for k, mi := range u.members {
			p := sc.Panes[mi]
			f := satFull
			if k > 0 {
				f = tabFactor
			}
			total += int64(p.Priority) * satPerMille(area, p.IdealArea) * f / 1000
		}
	}
	return total
}

func evaluate(sc Scene, units []unit, mons []logicalMon, active []bool) solution {
	level, places, ok := tryPack(units, active, mons)
	if !ok {
		return solution{active: append([]bool(nil), active...)}
	}
	return solution{
		active: append([]bool(nil), active...),
		level:  level,
		places: places,
		score:  scoreSolution(sc, units, active, level),
		ok:     true,
	}
}

// dominates reports whether unit a can be dropped into any slot unit b fits,
// at every shrink level. Because unitSize is monotone in both min and ideal
// dimensions, componentwise domination of both is sufficient.
func dominates(a, b unit) bool {
	return a.minW <= b.minW && a.minH <= b.minH && a.idealW <= b.idealW && a.idealH <= b.idealH
}

// dropStrategy decides which unit to sacrifice next when the chosen set does
// not pack. Different scenes reward different instincts, so the optimiser runs
// every strategy as an independent seed and keeps the best result. The final
// tie-break is the unit key, so every strategy is fully deterministic.
type dropStrategy struct {
	name  string
	worse func(a, b unit) bool // true when a is a better thing to lose than b
}

// valueDensity is priority-weighted value per pixel of the unit's minimum
// footprint, scaled by 1000 to stay integral.
func valueDensity(u unit) int64 {
	a := u.minArea()
	if a <= 0 {
		return u.fullValue * 1000
	}
	return u.fullValue * 1000 / a
}

var dropStrategies = []dropStrategy{
	{"least-value", func(a, b unit) bool {
		if a.fullValue != b.fullValue {
			return a.fullValue < b.fullValue
		}
		if a.minArea() != b.minArea() {
			return a.minArea() > b.minArea()
		}
		return a.key < b.key
	}},
	{"least-value-per-pixel", func(a, b unit) bool {
		da, db := valueDensity(a), valueDensity(b)
		if da != db {
			return da < db
		}
		if a.fullValue != b.fullValue {
			return a.fullValue < b.fullValue
		}
		return a.key < b.key
	}},
	{"largest-footprint", func(a, b unit) bool {
		if a.minArea() != b.minArea() {
			return a.minArea() > b.minArea()
		}
		if a.fullValue != b.fullValue {
			return a.fullValue < b.fullValue
		}
		return a.key < b.key
	}},
}

// solveConfig runs the selection optimiser for one stack configuration.
// It seeds a greedy descent from each drop strategy in turn, improves each
// seed with priority repair and local search, and keeps the best answer:
//
//  1. discard units whose minimum cannot fit any monitor at all;
//  2. greedy descent - while the set does not pack, drop the non-required unit
//     the current strategy likes least;
//  3. priority repair - if a dropped unit outranks a placed unit it dominates
//     in size, swap them (always feasible, never a loss);
//  4. local search - try adding each dropped unit back, and try every
//     improving drop/add swap, accepting only strict score increases.
//
// Returns ok=false when the required units alone cannot be packed.
func solveConfig(sc Scene, units []unit, mons []logicalMon) (solution, bool) {
	base := make([]bool, len(units))
	for i := range base {
		base[i] = true
	}
	for i, u := range units {
		if !fitsSomewhere(u, mons) {
			if u.required {
				return solution{}, false
			}
			base[i] = false
		}
	}
	var best solution
	found := false
	for _, st := range dropStrategies {
		sol, ok := solveFrom(sc, units, mons, base, st)
		if !ok {
			return solution{}, false
		}
		if !found || sol.score > best.score ||
			(sol.score == best.score && countPlaced(sol.active) > countPlaced(best.active)) ||
			(sol.score == best.score && countPlaced(sol.active) == countPlaced(best.active) && sol.level > best.level) {
			best, found = sol, true
		}
	}
	if !found {
		return solution{}, false
	}
	return best, true
}

func solveFrom(sc Scene, units []unit, mons []logicalMon, base []bool, st dropStrategy) (solution, bool) {
	active := append([]bool(nil), base...)

	// Step 2: greedy descent under this strategy.
	for {
		if _, _, ok := tryPack(units, active, mons); ok {
			break
		}
		victim := -1
		for i, u := range units {
			if !active[i] || u.required {
				continue
			}
			if victim < 0 || st.worse(u, units[victim]) {
				victim = i
			}
		}
		if victim < 0 {
			return solution{}, false
		}
		active[victim] = false
	}

	best := evaluate(sc, units, mons, active)
	if !best.ok {
		return solution{}, false
	}

	// Step 3: priority repair to a fixpoint.
	for round := 0; round < maxImproveRounds; round++ {
		swapped := false
		for d := range units {
			if best.active[d] {
				continue
			}
			for p := range units {
				if !best.active[p] || units[p].required {
					continue
				}
				if units[d].fullValue <= units[p].fullValue {
					continue
				}
				if !dominates(units[d], units[p]) {
					continue
				}
				trial := append([]bool(nil), best.active...)
				trial[d], trial[p] = true, false
				cand := evaluate(sc, units, mons, trial)
				if cand.ok && cand.score >= best.score {
					best = cand
					swapped = true
					break
				}
			}
			if swapped {
				break
			}
		}
		if !swapped {
			break
		}
	}

	// Step 4: local search on strict score improvement.
	for round := 0; round < maxImproveRounds; round++ {
		order := improveOrder(units, best.active, false)
		improved := false
		for _, d := range order {
			trial := append([]bool(nil), best.active...)
			trial[d] = true
			cand := evaluate(sc, units, mons, trial)
			if cand.ok && cand.score > best.score {
				best = cand
				improved = true
				break
			}
		}
		if improved {
			continue
		}
		placedOrder := improveOrder(units, best.active, true)
		for _, d := range order {
			for _, p := range placedOrder {
				if units[p].required || units[d].fullValue <= units[p].fullValue {
					continue
				}
				trial := append([]bool(nil), best.active...)
				trial[d], trial[p] = true, false
				cand := evaluate(sc, units, mons, trial)
				if cand.ok && cand.score > best.score {
					best = cand
					improved = true
					break
				}
			}
			if improved {
				break
			}
		}
		if !improved {
			break
		}
	}
	return best, true
}

// improveOrder lists dropped units best-first (placed=false) or placed units
// worst-first (placed=true), deterministically.
func improveOrder(units []unit, active []bool, placed bool) []int {
	var idx []int
	for i := range units {
		if active[i] == placed {
			idx = append(idx, i)
		}
	}
	sort.SliceStable(idx, func(a, b int) bool {
		ua, ub := units[idx[a]], units[idx[b]]
		if ua.fullValue != ub.fullValue {
			if placed {
				return ua.fullValue < ub.fullValue
			}
			return ua.fullValue > ub.fullValue
		}
		return ua.key < ub.key
	})
	return idx
}

// ---------------------------------------------------------------------------
// Public result types
// ---------------------------------------------------------------------------

// PaneOutcome is what happened to one pane, and the JSON shape of --json.
type PaneOutcome struct {
	ID           string   `json:"id"`
	Label        string   `json:"label"`
	Priority     int      `json:"priority"`
	Required     bool     `json:"required"`
	Outcome      string   `json:"outcome"`
	Monitor      string   `json:"monitor,omitempty"`
	Rect         *rect    `json:"rect,omitempty"`
	MinWidth     int      `json:"min_width"`
	MinHeight    int      `json:"min_height"`
	IdealWidth   int      `json:"ideal_width"`
	IdealHeight  int      `json:"ideal_height"`
	ScalePercent int      `json:"scale_percent"`
	AreaPercent  int      `json:"area_percent"`
	StackGroup   string   `json:"stack_group,omitempty"`
	StackedWith  []string `json:"stacked_with,omitempty"`
	StackFront   bool     `json:"stack_front,omitempty"`
	Satisfaction int64    `json:"satisfaction_per_mille"`
	Contribution int64    `json:"contribution"`
	Reason       string   `json:"reason"`
}

// MonitorOutcome summarises occupancy of one monitor.
type MonitorOutcome struct {
	ID            string   `json:"id"`
	Scale         int      `json:"scale_percent"`
	LogicalWidth  int      `json:"logical_width"`
	LogicalHeight int      `json:"logical_height"`
	LogicalArea   int64    `json:"logical_area"`
	UsedArea      int64    `json:"used_area"`
	FreeArea      int64    `json:"free_area"`
	UsedPercent   int      `json:"used_percent"`
	Panes         []string `json:"panes"`
}

// FitResult is the whole answer for one scene on one topology.
type FitResult struct {
	Scene           string           `json:"scene"`
	SceneSource     string           `json:"scene_source,omitempty"`
	Topology        string           `json:"topology"`
	Feasible        bool             `json:"feasible"`
	Infeasible      string           `json:"infeasible_reason,omitempty"`
	FullFit         bool             `json:"full_fit"`
	Score           int64            `json:"score"`
	MaxScore        int64            `json:"max_score"`
	FitPerMille     int64            `json:"fit_per_mille"`
	PanesTotal      int              `json:"panes_total"`
	CountFull       int              `json:"panes_full"`
	CountShrunk     int              `json:"panes_shrunk"`
	CountStacked    int              `json:"panes_stacked"`
	CountDropped    int              `json:"panes_dropped"`
	ShrinkLevel     int              `json:"shrink_level_percent"`
	ConfigsSearched int              `json:"configs_searched"`
	SearchMode      string           `json:"search_mode"`
	Panes           []PaneOutcome    `json:"panes"`
	Monitors        []MonitorOutcome `json:"monitors"`
	Algorithm       string           `json:"algorithm"`
}

const algorithmName = "guillotine best-area-fit packing + greedy descent with priority repair and local search"

// ---------------------------------------------------------------------------
// fitScene: the entry point
// ---------------------------------------------------------------------------

func fitScene(sc Scene, top Topology) FitResult {
	mons := top.logical()
	groups := stackGroups(sc)
	configs, mode := enumerateConfigs(groups)

	var maxScore int64
	for _, p := range sc.Panes {
		maxScore += int64(p.Priority) * satFull
	}

	res := FitResult{
		Scene:           sc.Name,
		Topology:        top.Name,
		MaxScore:        maxScore,
		PanesTotal:      len(sc.Panes),
		ConfigsSearched: len(configs),
		SearchMode:      mode,
		Algorithm:       algorithmName,
	}

	// Hard infeasibility: a required pane whose minimum exceeds every monitor.
	maxW, maxH := 0, 0
	for _, m := range mons {
		if m.W > maxW {
			maxW = m.W
		}
		if m.H > maxH {
			maxH = m.H
		}
	}
	for _, p := range sc.Panes {
		if !p.Required {
			continue
		}
		if p.MinWidth > maxW || p.MinHeight > maxH {
			res.Feasible = false
			res.Infeasible = fmt.Sprintf(
				"required pane %q needs at least %dx%d logical px, but the largest monitor work area is only %dx%d logical px",
				p.ID, p.MinWidth, p.MinHeight, maxW, maxH)
			res.Panes = infeasiblePanes(sc)
			res.Monitors = emptyMonitors(mons)
			res.CountDropped = len(sc.Panes)
			return res
		}
	}

	var bestSol solution
	var bestUnits []unit
	found := false
	var bestSig string
	for _, cfg := range configs {
		units := buildUnits(sc, groups, cfg)
		sol, ok := solveConfig(sc, units, mons)
		if !ok {
			continue
		}
		sig := configSig(units)
		better := false
		switch {
		case !found:
			better = true
		case sol.score != bestSol.score:
			better = sol.score > bestSol.score
		case countPlaced(sol.active) != countPlaced(bestSol.active):
			better = countPlaced(sol.active) > countPlaced(bestSol.active)
		case sol.level != bestSol.level:
			better = sol.level > bestSol.level
		default:
			better = sig < bestSig
		}
		if better {
			bestSol, bestUnits, bestSig, found = sol, units, sig, true
		}
	}

	if !found {
		res.Feasible = false
		res.Infeasible = "the panes marked required cannot all be placed at their minimum sizes on this display topology"
		res.Panes = infeasiblePanes(sc)
		res.Monitors = emptyMonitors(mons)
		res.CountDropped = len(sc.Panes)
		return res
	}

	res.Feasible = true
	res.Score = bestSol.score
	if maxScore > 0 {
		res.FitPerMille = 1000 * bestSol.score / maxScore
	}
	res.ShrinkLevel = bestSol.level
	res.Panes, res.Monitors = describe(sc, bestUnits, bestSol, mons)
	for _, p := range res.Panes {
		switch p.Outcome {
		case "full":
			res.CountFull++
		case "shrunk":
			res.CountShrunk++
		case "stacked":
			res.CountStacked++
		case "dropped":
			res.CountDropped++
		}
	}
	res.FullFit = res.CountFull == len(sc.Panes)
	return res
}

func countPlaced(active []bool) int {
	n := 0
	for _, a := range active {
		if a {
			n++
		}
	}
	return n
}

func configSig(units []unit) string {
	keys := make([]string, len(units))
	for i, u := range units {
		keys[i] = u.key
	}
	sort.Strings(keys)
	return strings.Join(keys, "|")
}

func emptyMonitors(mons []logicalMon) []MonitorOutcome {
	out := make([]MonitorOutcome, 0, len(mons))
	for _, m := range mons {
		out = append(out, MonitorOutcome{
			ID: m.ID, Scale: m.Scale,
			LogicalWidth: m.W, LogicalHeight: m.H,
			LogicalArea: int64(m.W) * int64(m.H),
			FreeArea:    int64(m.W) * int64(m.H),
			Panes:       []string{},
		})
	}
	return out
}

func infeasiblePanes(sc Scene) []PaneOutcome {
	out := make([]PaneOutcome, 0, len(sc.Panes))
	for _, p := range sc.Panes {
		iw, ih := idealDims(p.MinWidth, p.MinHeight, p.IdealArea)
		out = append(out, PaneOutcome{
			ID: p.ID, Label: p.Label, Priority: p.Priority, Required: p.Required,
			Outcome: "dropped", MinWidth: p.MinWidth, MinHeight: p.MinHeight,
			IdealWidth: iw, IdealHeight: ih,
			StackGroup: p.StackGroup,
			Reason:     "scene is infeasible on this topology; no variant was produced",
		})
	}
	return out
}

// describe turns the winning solution into per-pane and per-monitor reports
// with a plain-English reason for every degradation.
func describe(sc Scene, units []unit, sol solution, mons []logicalMon) ([]PaneOutcome, []MonitorOutcome) {
	byPane := make([]PaneOutcome, len(sc.Panes))
	used := make([]int64, len(mons))
	monPanes := make([][]string, len(mons))

	placedUnits := 0
	for i := range units {
		if sol.active[i] {
			placedUnits++
		}
	}

	for ui, u := range units {
		w, h := unitSize(u, sol.level)
		area := int64(w) * int64(h)
		names := make([]string, len(u.members))
		for k, mi := range u.members {
			names[k] = sc.Panes[mi].Label
		}
		for k, mi := range u.members {
			p := sc.Panes[mi]
			iw, ih := idealDims(p.MinWidth, p.MinHeight, p.IdealArea)
			po := PaneOutcome{
				ID: p.ID, Label: p.Label, Priority: p.Priority, Required: p.Required,
				MinWidth: p.MinWidth, MinHeight: p.MinHeight,
				IdealWidth: iw, IdealHeight: ih,
				StackGroup: p.StackGroup,
			}
			if !sol.active[ui] {
				po.Outcome = "dropped"
				po.Reason = dropReason(u, p, mons)
				byPane[mi] = po
				continue
			}
			pl := sol.places[ui]
			m := mons[pl.Mon]
			r := pl.R
			po.Monitor = m.ID
			po.Rect = &r
			po.ScalePercent = 100 * w / iw
			if po.ScalePercent > 100 {
				po.ScalePercent = 100
			}
			po.Satisfaction = satPerMille(area, p.IdealArea)
			po.AreaPercent = int(po.Satisfaction / 10)
			f := satFull
			if k > 0 {
				f = tabFactor
			}
			po.Contribution = int64(p.Priority) * po.Satisfaction * f / 1000

			switch {
			case len(u.members) > 1:
				po.Outcome = "stacked"
				po.StackFront = k == 0
				po.StackedWith = others(names, k)
				if k == 0 {
					po.Reason = fmt.Sprintf(
						"front tab of a %d-pane stack in group %q shared with %s: the topology had room for one %dx%d rectangle here, not %d of them",
						len(u.members), u.group, strings.Join(others(names, k), ", "), w, h, len(u.members))
				} else {
					po.Reason = fmt.Sprintf(
						"stacked behind %s in group %q: only one %dx%d rectangle was available for the %d panes of this group, so they share it as tabs (worth %d%% of a visible pane)",
						names[0], u.group, w, h, len(u.members), tabFactor/10)
				}
			case w == iw && h == ih:
				po.Outcome = "full"
				po.Reason = fmt.Sprintf("placed at its ideal %dx%d on %s", w, h, m.ID)
			default:
				po.Outcome = "shrunk"
				po.Reason = fmt.Sprintf(
					"shrunk to %d%% of ideal width (%dx%d instead of %dx%d, %d%% of ideal area) so that all %d placed rectangles fit; still at or above its %dx%d minimum",
					po.ScalePercent, w, h, iw, ih, po.AreaPercent, placedUnits, p.MinWidth, p.MinHeight)
			}
			byPane[mi] = po
		}
		if sol.active[ui] {
			pl := sol.places[ui]
			used[pl.Mon] += area
			monPanes[pl.Mon] = append(monPanes[pl.Mon], u.key)
		}
	}

	outMons := make([]MonitorOutcome, 0, len(mons))
	for i, m := range mons {
		total := int64(m.W) * int64(m.H)
		mo := MonitorOutcome{
			ID: m.ID, Scale: m.Scale,
			LogicalWidth: m.W, LogicalHeight: m.H,
			LogicalArea: total, UsedArea: used[i], FreeArea: total - used[i],
			Panes: monPanes[i],
		}
		if mo.Panes == nil {
			mo.Panes = []string{}
		}
		if total > 0 {
			mo.UsedPercent = int(100 * used[i] / total)
		}
		outMons = append(outMons, mo)
	}
	return byPane, outMons
}

func others(names []string, k int) []string {
	out := make([]string, 0, len(names)-1)
	for i, n := range names {
		if i != k {
			out = append(out, n)
		}
	}
	return out
}

func dropReason(u unit, p Pane, mons []logicalMon) string {
	if !fitsSomewhere(u, mons) {
		maxW, maxH := 0, 0
		for _, m := range mons {
			if m.W > maxW {
				maxW = m.W
			}
			if m.H > maxH {
				maxH = m.H
			}
		}
		return fmt.Sprintf(
			"dropped: its %dx%d minimum does not fit inside any monitor work area (the largest is %dx%d logical px), so it could never be shown usefully",
			p.MinWidth, p.MinHeight, maxW, maxH)
	}
	if len(u.members) > 1 {
		return fmt.Sprintf(
			"dropped with the rest of stack %q: at priority %d the whole stack bought less weighted satisfaction than the panes that were kept, and there was no %dx%d hole left for it",
			u.group, p.Priority, u.minW, u.minH)
	}
	return fmt.Sprintf(
		"dropped: at priority %d it was the cheapest thing to lose, and after the kept panes were packed no free rectangle of %dx%d (its minimum) remained",
		p.Priority, p.MinWidth, p.MinHeight)
}