# A dynamic implementation of the quadtree data structure
#
# The center of the parent node is determined by the average
# values of the data it contains when `item_limit` is reached.
class DQuadTree[E: Boxed[Numeric]]
	super QuadTree[E]

	redef fun subdivide
	do
		self.center = new Point[Numeric](average_x, average_y)
		children[0] = new DQuadTree[E].with_parent(self.item_limit, self)
		children[1] = new DQuadTree[E].with_parent(self.item_limit, self)
		children[2] = new DQuadTree[E].with_parent(self.item_limit, self)
		children[3] = new DQuadTree[E].with_parent(self.item_limit, self)
	end

	# Average X coordinate of the items in this node
	fun average_x: Numeric
	do
		var x_total = data.first.left.zero
		for data in self.data do
			x_total += (data.left + data.right)/x_total.value_of(2)
		end
		return x_total/x_total.value_of(self.data.length)
	end

	# Average Y coordinate of the items in this node
	fun average_y: Numeric
	do
		var y_total = data.first.left.zero
		for data in self.data do
			y_total += (data.left + data.right)/y_total.value_of(2)
		end
		return y_total/y_total.value_of(self.data.length)
	end
end