// 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) 2018 by via donau
//   – Österreichische Wasserstraßen-Gesellschaft mbH
// Software engineering by Intevation GmbH
//
// Author(s):
//  * Sascha L. Teichmann <sascha.teichmann@intevation.de>

package octree

import (
	"bytes"
	"encoding/binary"
	"io"
	"log"

	"github.com/golang/snappy"
)

// Builder is used to turn a TIN into an Octree.
type Builder struct {
	t      *Tin
	nodes  int
	leaves int
	index  []int32
}

var cubes = [8][2]Vertex{
	makeCube(0),
	makeCube(1),
	makeCube(2),
	makeCube(3),
	makeCube(4),
	makeCube(5),
	makeCube(6),
	makeCube(7),
}

func makeCube(i int) [2]Vertex {
	var d Vertex
	if i&1 == 1 {
		d.X = 0.5
	}
	if i&2 == 2 {
		d.Y = 0.5
	}
	if i&4 == 4 {
		d.Z = 0.5
	}
	return [2]Vertex{
		Vertex{0.0, 0.0, 0.0}.Add(d),
		Vertex{0.5, 0.5, 0.5}.Add(d),
	}
}

// NewBuilder creates a new Builder for a TIN.
func NewBuilder(t *Tin) *Builder {
	return &Builder{t: t}
}

// Build builds the Octree.
func (tb *Builder) Build() {

	triangles := make([]int32, len(tb.t.Triangles))
	for i := range triangles {
		triangles[i] = int32(i)
	}

	tb.index = append(tb.index, 0)

	tb.buildRecursive(triangles, tb.t.Min, tb.t.Max, 0)
	tb.index[0] = int32(len(tb.index))
	log.Printf("info: num nodes: %d\n", tb.index[0])

	log.Printf("info: nodes: %d leaves: %d index %d\n",
		tb.nodes, tb.leaves, tb.index[0])
}

func (tb *Builder) buildRecursive(
	triangles []int32,
	min, max Vertex,
	depth int,
) int32 {
	if len(triangles) <= 16 || depth > 8 {
		pos := len(tb.index)
		tb.index = append(tb.index, int32(len(triangles)))
		tb.index = append(tb.index, triangles...)
		//log.Printf("leaf entries: %d (%d)\n", len(triangles), depth)
		tb.leaves++
		return int32(-(pos + 1))
	}

	pos := len(tb.index)
	tb.index = append(tb.index,
		0, 0, 0, 0,
		0, 0, 0, 0)

	bbox := Interpolate(min, max)

	bboxes := make([][2]Vertex, len(cubes))

	for i := range cubes {
		bboxes[i] = [2]Vertex{
			bbox(cubes[i][0]),
			bbox(cubes[i][1]),
		}
	}

	var quandrants [8][]int32

	for _, tri := range triangles {
		triangle := tb.t.Triangles[tri]
		v0 := tb.t.Vertices[triangle[0]]
		v1 := tb.t.Vertices[triangle[1]]
		v2 := tb.t.Vertices[triangle[2]]

		l := v0
		l.Minimize(v1)
		l.Minimize(v2)

		h := v0
		h.Maximize(v1)
		h.Maximize(v2)

		for i := range bboxes {
			if !(h.Less(bboxes[i][0]) || bboxes[i][1].Less(l)) {
				quandrants[i] = append(quandrants[i], tri)
			}
		}
	}

	for i := range quandrants {
		if len(quandrants[i]) > 0 {
			child := tb.buildRecursive(
				quandrants[i],
				bboxes[i][0], bboxes[i][1],
				depth+1)
			tb.index[pos+i] = child
		}
	}
	tb.nodes++
	return int32(pos)
}

func (tb *Builder) serialize(w io.Writer) error {
	var buf [binary.MaxVarintLen32]byte

	if err := binary.Write(w, binary.LittleEndian, tb.index[0]); err != nil {
		return err
	}

	var last int32
	var written int

	for _, x := range tb.index[1:] {
		delta := x - last
		n := binary.PutVarint(buf[:], int64(delta))
		for p := buf[:n]; len(p) > 0; p = p[n:] {
			var err error
			if n, err = w.Write(p); err != nil {
				return err
			}
			written += n
		}

		last = x
	}
	log.Printf("info: compressed octree index in bytes: %d (%d)\n",
		written, 4*len(tb.index))

	return nil
}

func (tb *Builder) writeTo(w io.Writer) error {
	out := snappy.NewBufferedWriter(w)
	if err := tb.t.serialize(out); err != nil {
		return err
	}
	if err := tb.serialize(out); err != nil {
		return err
	}
	return out.Flush()
}

// Bytes serializes an Octree into a byte slice.
func (tb *Builder) Bytes() ([]byte, error) {
	var buf bytes.Buffer
	if err := tb.writeTo(&buf); err != nil {
		return nil, err
	}
	return buf.Bytes(), nil
}

// Tree returns an Octree from the Builder.
func (tb *Builder) Tree() *Tree {
	return &Tree{
		EPSG:      tb.t.EPSG,
		vertices:  tb.t.Vertices,
		triangles: tb.t.Triangles,
		index:     tb.index,
		Min:       tb.t.Min,
		Max:       tb.t.Max,
	}
}