package quadtree

import "fmt"

// coordinate type storing a position
type Coord struct {
	x float64
	y float64
}

// BoundingBox defines a single cell in the Quadtree
type BoundingBox struct {
	center        Coord
	halfDimension float64
}

// Quadtree defining the whole Quadtree and a node in itself (recursively)
type Quadtree struct {
	// general information (node capacity, spacial outreach)
	nodeCapacity int
	boundary     BoundingBox

	// slice storing the star coordinates
	pointsSlice []Coord

	// the Quadtree leaves
	northWest *Quadtree
	northEast *Quadtree
	southWest *Quadtree
	southEast *Quadtree

	depth int
}

// newCoord returns a new coordinate using the given values
func NewCoord(x float64, y float64) Coord {
	return Coord{x, y}
}

// NewBoundingBox returns a new bounding with the given struct elements
func NewBoundingBox(inCenter Coord, inHalfDimension float64) BoundingBox {
	return BoundingBox{
		center:        inCenter,
		halfDimension: inHalfDimension,
	}
}

func (point Coord) InsideOf(quadtreeCell *Quadtree) bool {
	// define the bounds
	var lowerXBound = quadtreeCell.boundary.center.x - quadtreeCell.boundary.halfDimension
	var upperXBound = quadtreeCell.boundary.center.x + quadtreeCell.boundary.halfDimension
	var lowerYBound = quadtreeCell.boundary.center.y - quadtreeCell.boundary.halfDimension
	var upperYBound = quadtreeCell.boundary.center.y + quadtreeCell.boundary.halfDimension

	// if the point is in the right x range
	if point.x < upperXBound && point.x > lowerXBound {

		// test if the point is in the right y range
		if point.y < upperYBound && point.y > lowerYBound {

			// the star is within the bounds: return true
			return true
		}
	}

	// the star is outside of the bounds: return false
	return false
}

// NewQuadtree returns a new Quadtree
func NewQuadtree(boundary BoundingBox, depth int) *Quadtree {
	return &Quadtree{
		nodeCapacity: 0,
		boundary:     boundary,
		pointsSlice:  nil,
		northWest:    nil,
		northEast:    nil,
		southWest:    nil,
		southEast:    nil,
		depth:        depth,
	}
}

func (quadtree *Quadtree) subdivide() {

	// Create the new NorthWest boundingbox
	var newCellBoundingNorthWest = BoundingBox{
		center: Coord{
			x: quadtree.boundary.center.x - quadtree.boundary.halfDimension/2,
			y: quadtree.boundary.center.y + quadtree.boundary.halfDimension/2,
		},
		halfDimension: quadtree.boundary.halfDimension / 2,
	}
	quadtree.northWest = NewQuadtree(newCellBoundingNorthWest, quadtree.depth+1)

	// Create the new NorthWest boundingbox
	var newCellBoundingNorthEast = BoundingBox{
		center: Coord{
			x: quadtree.boundary.center.x + quadtree.boundary.halfDimension/2,
			y: quadtree.boundary.center.y + quadtree.boundary.halfDimension/2,
		},
		halfDimension: quadtree.boundary.halfDimension / 2,
	}
	quadtree.northEast = NewQuadtree(newCellBoundingNorthEast, quadtree.depth+1)

	// Create the new NorthWest boundingbox
	var newCellBoundingSouthWest = BoundingBox{
		center: Coord{
			x: quadtree.boundary.center.x - quadtree.boundary.halfDimension/2,
			y: quadtree.boundary.center.y - quadtree.boundary.halfDimension/2,
		},
		halfDimension: quadtree.boundary.halfDimension / 2,
	}
	quadtree.southWest = NewQuadtree(newCellBoundingSouthWest, quadtree.depth+1)

	// Create the new NorthWest boundingbox
	var newCellBoundingSouthEast = BoundingBox{
		center: Coord{
			x: quadtree.boundary.center.x + quadtree.boundary.halfDimension/2,
			y: quadtree.boundary.center.y - quadtree.boundary.halfDimension/2,
		},
		halfDimension: quadtree.boundary.halfDimension / 2,
	}
	quadtree.southEast = NewQuadtree(newCellBoundingSouthEast, quadtree.depth+1)
}

// Insert inserts the given point into the Quadtree the method is applied on
// it returns an error incase the point is not in bounds
func (quadtree *Quadtree) Insert(point Coord) {

	// subdivide the Quadtree into four new cells
	quadtree.subdivide()

	// if the maxDepth is not reached...
	if quadtree.depth < 4 {
		// ... test if the given point is inside the one of the cells
		// and add Insert it to that specific cell
		if point.InsideOf(quadtree.northWest) {
			quadtree.northWest.Insert(point)
		}
		if point.InsideOf(quadtree.northEast) {
			quadtree.northEast.Insert(point)
		}
		if point.InsideOf(quadtree.southWest) {
			quadtree.southWest.Insert(point)
		}
		if point.InsideOf(quadtree.southEast) {
			quadtree.southEast.Insert(point)
		}
	}

	// if the maximal depth of the tree has been reached:
	// Insert the point into the slice
	quadtree.pointsSlice = append(quadtree.pointsSlice, point)
}

// Print() is a method that can be used on a quadtree.
// It prints all the root nodes of the quadtree recursively
// The tree is printed from the bottom up in the following order: NW, NE, SW, SE
func (quadtree *Quadtree) Print() {
	// Define an end condition: if the quadtree-leaf is nil, the root does not continue
	if quadtree.northWest != nil {
		quadtree.northWest.Print()
	}
	if quadtree.northEast != nil {
		quadtree.northEast.Print()
	}
	if quadtree.southWest != nil {
		quadtree.southWest.Print()
	}
	if quadtree.southEast != nil {
		quadtree.southEast.Print()
	}
	fmt.Println(quadtree)
}