# Static implementation of the quadtree structure
#
# You need to specify a zone when creating the quadtree,
# which will be the zone corresponding to the root node.
# Each subdivision cut the space in 4 equal regions from
# the center of the parent node.
class SQuadTree[E: Boxed[Numeric]]
	super QuadTree[E]

	# Width of this node of the QuadTree
	var width: Numeric

	# Height of this node of the QuadTree
	var height: Numeric

	init
	do
		center = new Point[Numeric](width.div(2), height.div(2))
	end

	# Create a child node to `parent`
	init with_parent(l: Int, c: Point[Numeric], w, h: Numeric, parent: QuadTree[E])
	do
		init(l, w, h)
		center = c
		self.parent_node = parent
	end

	redef fun subdivide
	do
		var center = center
		assert center != null

		children[0] = new SQuadTree[E].with_parent(self.item_limit, new Point[Numeric](center.x.div(2), center.y.div(2)), self.width.div(2), self.height.div(2), self)
		children[1] = new SQuadTree[E].with_parent(self.item_limit, new Point[Numeric](center.x.div(2), (center.y.mul(3)).div(2)), self.width.div(2), self.height.div(2), self)
		children[2] = new SQuadTree[E].with_parent(self.item_limit, new Point[Numeric]((center.x.mul(3)).div(2), (center.y.mul(3)).div(2)), self.width.div(2), self.height.div(2), self)
		children[3] = new SQuadTree[E].with_parent(self.item_limit, new Point[Numeric]((center.x.mul(3)).div(2), center.y.div(2)), self.width.div(2), self.height.div(2), self)
	end

	redef fun to_s
	do
		var s = "center : {center or else "null"}\n"
		for d in data do s += d.to_s

		if children.not_empty then
			s += "\n   children[0]: {children[0]}\n"
			s += "   children[1]: {children[1]}\n"
			s += "   children[2]: {children[2]}\n"
			s += "   children[3]: {children[3]}\n"
		end
		return s
	end
end