package quadtree

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

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

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
}

// boundingBox defines a single cell in the quadtree
type boundingBox struct {
	center        Coord
	halfDimension float64
}

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

// 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
}

// 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)
}