package main

import (
	"fmt"
	"sort"
)

// ---------------------------------------------------------------------------
// The solver
//
// Turning a tree of weighted splits into exact integer rectangles.
//
// Two rectangles are produced for every zone:
//
//	Cell   the slice of the parent the zone owns. Sibling cells plus the gap
//	       strips between them exactly cover the parent, with no overlap and
//	       nothing left over. With gap 0 the cells tile the parent exactly.
//	Frame  the rectangle a window actually gets: the cell shrunk by the zone's
//	       own padding.
//
// All arithmetic below is integer. Leftover pixels from a weighted split are
// handed out by largestRemainder, so a row of five zones on a 1439 px screen
// still sums to exactly 1439 px and the error never accumulates rightwards.
// ---------------------------------------------------------------------------

// Issue is one problem found while solving or checking.
type Issue struct {
	Severity string `json:"severity"` // "error" or "warning"
	Code     string `json:"code"`
	Monitor  string `json:"monitor,omitempty"`
	Zone     string `json:"zone,omitempty"`
	Path     string `json:"path,omitempty"`
	Message  string `json:"message"`
}

func (i Issue) String() string { return i.Message }

// Placement is one solved zone.
type Placement struct {
	Monitor   string   `json:"monitor"`
	Rank      int      `json:"monitor_rank"`
	Zone      string   `json:"zone"`
	Path      string   `json:"path"`
	Cell      Rect     `json:"cell"`
	Frame     Rect     `json:"frame"`
	LogicalW  int      `json:"logical_w"`
	LogicalH  int      `json:"logical_h"`
	MinW      int      `json:"min_w_device,omitempty"`
	MinH      int      `json:"min_h_device,omitempty"`
	WindowIDs []string `json:"window_ids,omitempty"`
	Apps      []string `json:"apps,omitempty"`
}

// MonitorPlan is the per-monitor summary of a solve.
type MonitorPlan struct {
	ID        string   `json:"id"`
	Label     string   `json:"label,omitempty"`
	Rank      int      `json:"rank"`
	Primary   bool     `json:"primary"`
	Bounds    Rect     `json:"bounds"`
	Work      Rect     `json:"work_area"`
	Scale     string   `json:"scale"`
	ScalePM   int      `json:"scale_permille"`
	LogicalW  int      `json:"logical_w"`
	LogicalH  int      `json:"logical_h"`
	HasLayout bool     `json:"has_layout"`
	FoldedIn  []string `json:"folded_in,omitempty"`
	Zones     int      `json:"zones"`
}

// SolveResult is everything a solve produced.
type SolveResult struct {
	LayoutName   string        `json:"layout"`
	TopologyName string        `json:"topology"`
	Monitors     []MonitorPlan `json:"monitors"`
	Placements   []Placement   `json:"placements"`
	Assignments  []Assignment  `json:"assignments"`
	Issues       []Issue       `json:"issues,omitempty"`

	byZone map[string]int // zone name -> index into Placements
}

// Errors returns only the error-severity issues.
func (r *SolveResult) Errors() []Issue {
	var out []Issue
	for _, i := range r.Issues {
		if i.Severity == "error" {
			out = append(out, i)
		}
	}
	return out
}

// Warnings returns only the warning-severity issues.
func (r *SolveResult) Warnings() []Issue {
	var out []Issue
	for _, i := range r.Issues {
		if i.Severity == "warning" {
			out = append(out, i)
		}
	}
	return out
}

// Zone returns the placement for a zone name.
func (r *SolveResult) Zone(name string) (Placement, bool) {
	i, ok := r.byZone[name]
	if !ok {
		return Placement{}, false
	}
	return r.Placements[i], true
}

type solver struct {
	res     *SolveResult
	monitor Monitor
	rank    int
	defGap  int
}

// Solve computes the rectangles for every zone of lay on topo.
//
// Structural failures (a split that cannot fit its children, a monitor the
// topology does not have, a violated minimum size) are collected as Issues
// rather than aborting, so one run reports every problem at once. Callers
// decide what to do with an error-severity result; plan and check both exit 1.
func Solve(lay *Layout, topo *Topology) *SolveResult {
	res := &SolveResult{
		LayoutName:   lay.Name,
		TopologyName: topo.Name,
		byZone:       map[string]int{},
	}

	order := RankOrder(topo)
	claimed := map[string]bool{}

	for rank, mi := range order {
		mon := topo.Monitors[mi]
		lm := lay.MonitorLayout(mon.ID)
		mp := MonitorPlan{
			ID:       mon.ID,
			Label:    mon.Label,
			Rank:     rank,
			Primary:  mon.Primary,
			Bounds:   mon.Bounds,
			Work:     mon.Work,
			Scale:    mon.ScaleString(),
			ScalePM:  mon.ScalePermille,
			LogicalW: mon.LogicalW(),
			LogicalH: mon.LogicalH(),
		}
		if lm == nil {
			res.addIssue(Issue{
				Severity: "warning", Code: "monitor-unused", Monitor: mon.ID,
				Message: fmt.Sprintf("monitor %q is in the topology but the layout has no block for it; it will be left empty", mon.ID),
			})
			res.Monitors = append(res.Monitors, mp)
			continue
		}
		claimed[mon.ID] = true
		mp.HasLayout = true

		s := &solver{res: res, monitor: mon, rank: rank, defGap: lm.Gap}
		start := len(res.Placements)
		root := insetAll(mon.Work, lm.Padding)
		if root.Empty() {
			res.addIssue(Issue{
				Severity: "error", Code: "no-room", Monitor: mon.ID,
				Message: fmt.Sprintf("monitor %q: padding %d px leaves a %dx%d work area; nothing fits",
					mon.ID, lm.Padding, root.W, root.H),
			})
			res.Monitors = append(res.Monitors, mp)
			continue
		}
		s.node(lm.Root, root, "root")
		mp.Zones = len(res.Placements) - start
		res.Monitors = append(res.Monitors, mp)
	}

	// Layout blocks that name a monitor this topology does not have.
	for _, lm := range lay.Monitors {
		if !claimed[lm.Monitor] {
			res.addIssue(Issue{
				Severity: "error", Code: "monitor-missing", Monitor: lm.Monitor,
				Message: fmt.Sprintf("layout targets monitor %q, which is not in topology %q; use `%s refit` to move this layout onto a different set of screens",
					lm.Monitor, topo.Name, appName),
			})
		}
	}

	for i, p := range res.Placements {
		res.byZone[p.Zone] = i
	}

	assignWindowsToPlacements(lay, res)
	sortIssues(res)
	return res
}

func (r *SolveResult) addIssue(i Issue) { r.Issues = append(r.Issues, i) }

// node lays out one subtree inside cell.
func (s *solver) node(n *Node, cell Rect, path string) {
	inner := insetAll(cell, n.Padding)

	if n.isLeaf() {
		p := Placement{
			Monitor:  s.monitor.ID,
			Rank:     s.rank,
			Zone:     n.Zone,
			Path:     path,
			Cell:     cell,
			Frame:    inner,
			LogicalW: toLogical(inner.W, s.monitor.ScalePermille),
			LogicalH: toLogical(inner.H, s.monitor.ScalePermille),
		}
		if n.MinWidth > 0 {
			p.MinW = toDevice(n.MinWidth, s.monitor.ScalePermille)
		}
		if n.MinHeight > 0 {
			p.MinH = toDevice(n.MinHeight, s.monitor.ScalePermille)
		}
		if inner.Empty() {
			s.res.addIssue(Issue{
				Severity: "error", Code: "zone-empty", Monitor: s.monitor.ID, Zone: n.Zone, Path: path,
				Message: fmt.Sprintf("zone %q on %q collapses to %dx%d after %d px padding; reduce the padding or give the zone more weight",
					n.Zone, s.monitor.ID, inner.W, inner.H, n.Padding),
			})
		} else {
			if p.MinW > 0 && inner.W < p.MinW {
				s.res.addIssue(Issue{
					Severity: "error", Code: "min-width", Monitor: s.monitor.ID, Zone: n.Zone, Path: path,
					Message: fmt.Sprintf("zone %q on %q is %d px wide but requires minWidth %d logical px (= %d device px at %s); short by %d px",
						n.Zone, s.monitor.ID, inner.W, n.MinWidth, p.MinW, s.monitor.ScaleString(), p.MinW-inner.W),
				})
			}
			if p.MinH > 0 && inner.H < p.MinH {
				s.res.addIssue(Issue{
					Severity: "error", Code: "min-height", Monitor: s.monitor.ID, Zone: n.Zone, Path: path,
					Message: fmt.Sprintf("zone %q on %q is %d px tall but requires minHeight %d logical px (= %d device px at %s); short by %d px",
						n.Zone, s.monitor.ID, inner.H, n.MinHeight, p.MinH, s.monitor.ScaleString(), p.MinH-inner.H),
				})
			}
		}
		s.res.Placements = append(s.res.Placements, p)
		return
	}

	if inner.Empty() {
		s.res.addIssue(Issue{
			Severity: "error", Code: "no-room", Monitor: s.monitor.ID, Path: path,
			Message: fmt.Sprintf("node %s on %q collapses to %dx%d after %d px padding",
				path, s.monitor.ID, inner.W, inner.H, n.Padding),
		})
		return
	}

	gap := s.defGap
	if n.Gap != nil {
		gap = *n.Gap
	}
	nChildren := len(n.Children)
	weights := make([]int, nChildren)
	for i, c := range n.Children {
		weights[i] = c.weight()
	}

	axis := "width"
	total := inner.W
	if n.Split == splitRows {
		axis, total = "height", inner.H
	}
	avail := total - gap*(nChildren-1)
	if avail < nChildren {
		s.res.addIssue(Issue{
			Severity: "error", Code: "split-too-small", Monitor: s.monitor.ID, Path: path,
			Message: fmt.Sprintf("node %s on %q cannot fit %d children: %d px of %s minus %d gaps of %d px leaves %d px, under 1 px each",
				path, s.monitor.ID, nChildren, total, axis, nChildren-1, gap, avail),
		})
		return
	}
	sizes, err := largestRemainder(avail, weights)
	if err != nil {
		s.res.addIssue(Issue{
			Severity: "error", Code: "bad-weights", Monitor: s.monitor.ID, Path: path,
			Message: fmt.Sprintf("node %s on %q: %v", path, s.monitor.ID, err),
		})
		return
	}

	pos := inner.X
	if n.Split == splitRows {
		pos = inner.Y
	}
	for i, c := range n.Children {
		var childCell Rect
		if n.Split == splitRows {
			childCell = Rect{X: inner.X, Y: pos, W: inner.W, H: sizes[i]}
		} else {
			childCell = Rect{X: pos, Y: inner.Y, W: sizes[i], H: inner.H}
		}
		pos += sizes[i] + gap
		s.node(c, childCell, fmt.Sprintf("%s/%s[%d]", path, n.Split, i))
	}

	// Belt and braces: verify the invariant the solver is supposed to hold.
	// This costs nothing and turns a silent geometry bug into a reported one.
	end := pos - gap
	wantEnd := inner.X + inner.W
	if n.Split == splitRows {
		wantEnd = inner.Y + inner.H
	}
	if end != wantEnd {
		s.res.addIssue(Issue{
			Severity: "error", Code: "tiling-drift", Monitor: s.monitor.ID, Path: path,
			Message: fmt.Sprintf("internal: node %s on %q ends at %d but its parent ends at %d (%d px of drift)",
				path, s.monitor.ID, end, wantEnd, wantEnd-end),
		})
	}
}

// assignWindowsToPlacements runs the rules and attaches windows to zones.
func assignWindowsToPlacements(lay *Layout, res *SolveResult) {
	res.Assignments = AssignWindows(lay.Rules, lay.Windows)
	for _, a := range res.Assignments {
		if a.Zone == "" {
			res.addIssue(Issue{
				Severity: "warning", Code: "window-unmatched",
				Message: fmt.Sprintf("window %s (app %q, title %q) matches no rule and will not be placed",
					a.Window.ID, a.Window.App, a.Window.Title),
			})
			continue
		}
		i, ok := res.byZone[a.Zone]
		if !ok {
			res.addIssue(Issue{
				Severity: "error", Code: "zone-unknown", Zone: a.Zone,
				Message: fmt.Sprintf("window %s is assigned to zone %q, which no monitor in this plan provides",
					a.Window.ID, a.Zone),
			})
			continue
		}
		res.Placements[i].WindowIDs = append(res.Placements[i].WindowIDs, a.Window.ID)
		res.Placements[i].Apps = append(res.Placements[i].Apps, a.Window.App)
	}
}

// sortIssues puts errors before warnings and is otherwise stable, so output is
// reproducible byte for byte.
func sortIssues(res *SolveResult) {
	sort.SliceStable(res.Issues, func(i, j int) bool {
		return res.Issues[i].Severity == "error" && res.Issues[j].Severity != "error"
	})
}

// VerifyTiling independently re-checks a solved result: no two cells on the
// same monitor may overlap, and every frame must lie inside its monitor's work
// area. It does not trust the solver; it measures what the solver produced.
// Returned issues are appended to the caller's list by check.
func VerifyTiling(res *SolveResult) []Issue {
	var out []Issue
	byMon := map[string][]Placement{}
	for _, p := range res.Placements {
		byMon[p.Monitor] = append(byMon[p.Monitor], p)
	}
	work := map[string]Rect{}
	for _, m := range res.Monitors {
		work[m.ID] = m.Work
	}
	ids := make([]string, 0, len(byMon))
	for id := range byMon {
		ids = append(ids, id)
	}
	sort.Strings(ids)

	for _, id := range ids {
		ps := byMon[id]
		for i := 0; i < len(ps); i++ {
			if wa, ok := work[id]; ok && !containsRect(wa, ps[i].Frame) {
				out = append(out, Issue{
					Severity: "error", Code: "out-of-bounds", Monitor: id, Zone: ps[i].Zone,
					Message: fmt.Sprintf("zone %q frame %s is not inside the work area %s of monitor %q",
						ps[i].Zone, ps[i].Frame, wa, id),
				})
			}
			for j := i + 1; j < len(ps); j++ {
				if ov := intersect(ps[i].Cell, ps[j].Cell); !ov.Empty() {
					out = append(out, Issue{
						Severity: "error", Code: "overlap", Monitor: id,
						Message: fmt.Sprintf("zones %q %s and %q %s overlap over %s on monitor %q",
							ps[i].Zone, ps[i].Cell, ps[j].Zone, ps[j].Cell, ov, id),
					})
				}
			}
		}
		// Area accounting: cells plus gap strips must account for the whole
		// padded work area. Any shortfall other than declared gaps is a hole.
		if wa, ok := work[id]; ok {
			var covered int64
			for _, p := range ps {
				covered += p.Cell.Area()
			}
			if covered > wa.Area() {
				out = append(out, Issue{
					Severity: "error", Code: "over-cover", Monitor: id,
					Message: fmt.Sprintf("zone cells on monitor %q cover %d px^2 of a %d px^2 work area",
						id, covered, wa.Area()),
				})
			}
		}
	}
	return out
}