// This is Free Software under GNU Affero General Public License v >= 3.0
// without warranty, see README.md and license for details.
//
// SPDX-License-Identifier: AGPL-3.0-or-later
// License-Filename: LICENSES/AGPL-3.0.txt
//
// Copyright (C) 2024 by via donau
//   – Österreichische Wasserstraßen-Gesellschaft mbH
// Software engineering by Intevation GmbH
//
// Author(s):
//  * Sascha L. Teichmann <sascha.teichmann@intevation.de>

package mesh

import (
	"cmp"
	"math"
	"slices"
	"sort"
)

func (s *STRTree) optimizeForSerializationV2() {
	s.removeUnusedTriangles()
	s.sortVertices()
	s.sortIndices()
}

// removeUnusedTriangles removes all triangles from the
// TIN that are not registered in the spatial index.
func (s *STRTree) removeUnusedTriangles() {
	used := make([]bool, len(s.tin.Triangles))
	unused := len(used)
	s.allTriangleIndices(func(indices []int32) {
		for _, idx := range indices {
			used[idx] = true
			unused-- // They only occur once in the spatial index.
		}
	})
	if unused <= 0 {
		return
	}
	newTris := make([][]int32, 0, len(s.tin.Triangles)-unused)
	remap := map[int32]int32{}
	for idx, tri := range s.tin.Triangles {
		if used[idx] {
			remap[int32(idx)] = int32(len(newTris))
			newTris = append(newTris, tri)
		}
	}
	s.tin.Triangles = newTris
	// Update the spatial index as the gaps are now closed.
	s.allTriangleIndices(func(indices []int32) {
		for i, idx := range indices {
			indices[i] = remap[idx]
		}
	})
}

// sortVertices so that the deltas between neighbors are minimized.
func (s *STRTree) sortVertices() {
	vertices := s.tin.Vertices
	indices := make([]int32, len(vertices))
	for i := range len(indices) {
		indices[i] = int32(i)
	}

	slices.SortFunc(indices, func(a, b int32) int {
		return cmp.Compare(vertices[a].X, vertices[b].X)
	})

	n := int(math.Sqrt(float64(len(vertices))))
	m := len(vertices) / n

	var (
		up   = func(a, b int32) int { return cmp.Compare(vertices[a].Y, vertices[b].Y) }
		down = func(a, b int32) int { return cmp.Compare(vertices[b].Y, vertices[a].Y) }
	)
	for p := indices; len(p) > 0; up, down = down, up {
		l := min(len(p), m)
		slices.SortStableFunc(p[:l], down)
		p = p[l:]
	}

	// We really need to to sort the vertices actually, too.
	sort.Slice(vertices, func(i, j int) bool { return indices[i] < indices[j] })

	reindices := make([]int32, len(indices))
	for i, idx := range indices {
		reindices[idx] = int32(i)
	}

	// Update the indices in the triangles.
	for _, tri := range s.tin.Triangles {
		for i, idx := range tri {
			tri[i] = reindices[idx]
		}
	}
}