// 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"
	"runtime"
	"sync"
	"sync/atomic"

	"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

	mu sync.Mutex
}

type buildStep func(chan buildStep)

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

func makeCube(i int) Box {
	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 Box{
		Vertex{0.0, 0.0, 0.0}.Add(d),
		Vertex{0.5, 0.5, 0.5}.Add(d),
	}
}

func twoElseOne(b bool) int {
	if b {
		return 2
	}
	return 1
}

// 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(removed map[int32]struct{}) {

	var triangles []int32

	if len(removed) > 0 {
		triangles = make([]int32, len(tb.t.Triangles)-len(removed))
		idx := 0
		for i := range tb.t.Triangles {
			if _, found := removed[int32(i)]; !found {
				triangles[idx] = int32(i)
				idx++
			}
		}
	} else {
		triangles = make([]int32, len(tb.t.Triangles))
		for i := range triangles {
			triangles[i] = int32(i)
		}
	}

	n := runtime.NumCPU()

	steps := make(chan buildStep)

	var wg sync.WaitGroup
	for i := 0; i < n; i++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for step := range steps {
				step(steps)
			}
		}()
	}

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

	root := func(int32) {
		close(steps)
	}

	steps <- tb.buildConcurrent(
		triangles,
		tb.t.Min, tb.t.Max,
		0,
		root)

	wg.Wait()

	/*
		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) buildConcurrent(
	triangles []int32,
	min, max Vertex,
	depth int,
	parent func(int32),
) buildStep {

	return func(steps chan buildStep) {

		// none concurrent for small parts.
		if len(triangles) <= 1024 || depth > 8 {
			parent(tb.buildRecursive(triangles, min, max, depth))
			return
		}
		box := Box{min, max}

		xLimit := twoElseOne(box.HasX())
		yLimit := twoElseOne(box.HasY())
		zLimit := twoElseOne(box.HasZ())

		indices := make([]byte, 0, 8)

		bbox := box.Interpolate()

		var bboxes [8]Box

		for x := 0; x < xLimit; x++ {
			for y := 0; y < yLimit; y++ {
				for z := 0; z < zLimit; z++ {
					idx := byte(z<<2 | y<<1 | x)
					bboxes[idx] = Box{
						bbox(cubes[idx][0]),
						bbox(cubes[idx][1]),
					}
					indices = append(indices, idx)
				}
			}
		}

		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 indices {
				if !(h.Less(bboxes[i][0]) || bboxes[i][1].Less(l)) {
					quandrants[i] = append(quandrants[i], tri)
				}
			}
		}

		used := new(int32)
		for _, i := range indices {
			if len(quandrants[i]) > 0 {
				*used++
			}
		}

		pos := tb.allocNode()

		if *used == 0 {
			parent(pos)
			return
		}

		for _, i := range indices {
			if len(quandrants[i]) > 0 {
				j := int32(i)
				parent := func(v int32) {
					tb.index[pos+j] = v
					if atomic.AddInt32(used, -1) == 0 {
						parent(pos)
					}
				}
				step := tb.buildConcurrent(
					quandrants[i],
					bboxes[i][0], bboxes[i][1],
					depth+1,
					parent)
				select {
				case steps <- step:
				default:
					// all slots busy -> execute directly.
					step(steps)
				}
			}
		}
	}
}

func (tb *Builder) allocNode() int32 {
	tb.mu.Lock()
	pos := int32(len(tb.index))
	tb.index = append(tb.index,
		0, 0, 0, 0,
		0, 0, 0, 0)
	tb.nodes++
	tb.mu.Unlock()
	return pos
}

func (tb *Builder) buildRecursive(
	triangles []int32,
	min, max Vertex,
	depth int,
) int32 {
	if len(triangles) <= 16 || depth > 8 {
		tb.mu.Lock()
		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++
		tb.mu.Unlock()
		return int32(-(pos + 1))
	}

	box := Box{min, max}

	xLimit := twoElseOne(box.HasX())
	yLimit := twoElseOne(box.HasY())
	zLimit := twoElseOne(box.HasZ())

	indices := make([]byte, 0, 8)

	bbox := box.Interpolate()

	var bboxes [8]Box

	for x := 0; x < xLimit; x++ {
		for y := 0; y < yLimit; y++ {
			for z := 0; z < zLimit; z++ {
				idx := byte(z<<2 | y<<1 | x)
				bboxes[idx] = Box{
					bbox(cubes[idx][0]),
					bbox(cubes[idx][1]),
				}
				indices = append(indices, idx)
			}
		}
	}

	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 indices {
			if !(h.Less(bboxes[i][0]) || bboxes[i][1].Less(l)) {
				quandrants[i] = append(quandrants[i], tri)
			}
		}
	}

	pos := tb.allocNode()

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

	return 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,
	}
}