package octree

import (
	"math"
)

type Tree struct {
	EPSG uint32

	vertices  []Vertex
	triangles [][]int32
	index     []int32

	Min Vertex
	Max Vertex
}

func (ot *Tree) Horizontal(h float64, fn func(*Triangle)) {

	type frame struct {
		pos int32
		min float64
		max float64
	}

	if h < ot.Min.Z || ot.Max.Z < h {
		return
	}

	stack := []frame{{1, ot.Min.Z, ot.Max.Z}}

	dupes := map[int32]struct{}{}

	for len(stack) > 0 {
		top := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		pos := top.pos
		if pos == 0 {
			continue
		}
		min, max := top.min, top.max

		if pos > 0 { // node
			if mid := (max-min)*0.5 + min; h >= mid {
				pos += 4 // nodes with z-bit set
				min = mid
			} else {
				max = mid
			}
			stack = append(stack,
				frame{ot.index[pos+0], min, max},
				frame{ot.index[pos+1], min, max},
				frame{ot.index[pos+2], min, max},
				frame{ot.index[pos+3], min, max})
		} else { // leaf
			pos = -pos - 1
			n := ot.index[pos]
			//log.Printf("%d %d %d\n", pos, n, len(ot.index))
			indices := ot.index[pos+1 : pos+1+n]

			for _, idx := range indices {
				if _, found := dupes[idx]; found {
					continue
				}
				tri := ot.triangles[idx]
				t := Triangle{
					ot.vertices[tri[0]],
					ot.vertices[tri[1]],
					ot.vertices[tri[2]],
				}

				if !(math.Min(t[0].Z, math.Min(t[1].Z, t[2].Z)) > h ||
					math.Max(t[0].Z, math.Max(t[1].Z, t[2].Z)) < h) {
					dupes[idx] = struct{}{}
					fn(&t)
				}
			}
		}
	}
}