# Abstract QuadTree implementing the basic functions and data
abstract class QuadTree[E: Boxed[Numeric]]
	super BoxedCollection[E]

	# Center coordinate of the children
	protected var center: nullable Point[Numeric] = null

	# Items in this node
	protected var data = new Array[E]

	# Children nodes, if not `is_leaf`
	#
	# ~~~raw
	# ________________
	# |       |       |
	# |   1   |   2   |
	# |-------|-------|
	# |   0   |   3   |
	# |_______|_______|
	# ~~~
	protected var children = new Array[QuadTree[E]]

	# Maximum number of items in this node before subdividing
	protected var item_limit: Int

	# Parent node in the tree
	protected var parent_node: nullable QuadTree[E] = null

	# Create a child node to `parent`
	init with_parent(limit: Int, parent: QuadTree[E])
	do
		init(limit)
		self.parent_node = parent
	end

	redef fun items_overlapping(region): SimpleCollection[E] do
		var res = new Array[E]
		items_overlapping_in(region,res)
		return res
	end

	# Add `item` to the tree, create children if `item_limit` is reached
	redef fun add(item) do if self.is_leaf then self.data.add(item) else add_to_children(item)

	private fun add_to_children(item: Boxed[Numeric])
	do
		if children.not_empty then
			var center = center
			assert center != null
			if center.x > item.right then
				if center.y > item.top then
					children[0].add(item)
				else if center.y < item.bottom then
					children[1].add(item)
				else
					self.data.add(item)
				end
			else if center.x < item.left then
				if center.y > item.top then
					children[3].add(item)
				else if center.y < item.bottom then
					children[2].add(item)
				else
					self.data.add(item)
				end
			else if center.y > item.top then
				self.data.add(item)
			else if center.y < item.bottom then
				self.data.add(item)
			else
				self.data.add(item)
			end
		end
	end

	redef fun is_empty
	do
		if is_leaf then return data.is_empty

		assert children.length >= 4
		return data.is_empty and children[0].is_empty and children[1].is_empty and children[2].is_empty and children[3].is_empty
	end

	# Return whether or not the Node is a leaf of the tree
	fun is_leaf: Bool do return children.is_empty

	#     var dquadtree = new DQuadTree[Point[Int]](2)
	#     var p1 = new Point[Int](0,0)
	#     var p2 = new Point[Int](0,9)
	#     var p3 = new Point[Int](9,0)
	#     dquadtree.add(p1)
	#     dquadtree.add(p2)
	#     dquadtree.add(p3)
	#     var result = dquadtree.items_overlapping(p3)
	#     assert result.length == 1
	#     result.clear
	#     var p4 = new Point[Int](9,9)
	#     result = dquadtree.items_overlapping(p4)
	#     assert result.length == 0
	#     result = dquadtree.items_overlapping(p4.padded(10))
	#     assert result.length == 3
	private fun items_overlapping_in(region: Boxed[Numeric], mdata: SimpleCollection[E])
	do
		if self.is_leaf and data.length >= item_limit then
			subdivide
			var data_copy = data
			data = new Array[E]
			#add to the right Node
			for d in data_copy do
				add_to_children(d)
			end
		end
		for i in data do if i.intersects(region) then mdata.add(i)

		if children.not_empty then
			var center = center
			assert center != null
			if center.x > region.right then
				if center.y > region.top then
					children[0].items_overlapping_in(region, mdata)
				else if center.y < region.bottom then
					children[1].items_overlapping_in(region, mdata)
				else
					children[0].items_overlapping_in(region,mdata)
					children[1].items_overlapping_in(region, mdata)
				end
			else if center.x < region.left then
				if center.y > region.top then
					children[3].items_overlapping_in(region, mdata)
				else if center.y < region.bottom then
					children[2].items_overlapping_in(region, mdata)
				else
					children[3].items_overlapping_in(region, mdata)
					children[2].items_overlapping_in(region, mdata)
				end
			else if center.y > region.top then
				children[0].items_overlapping_in(region, mdata)
				children[3].items_overlapping_in(region, mdata)
			else if center.y < region.bottom then
				children[1].items_overlapping_in(region, mdata)
				children[2].items_overlapping_in(region, mdata)
			else
				children[0].items_overlapping_in(region, mdata)
				children[1].items_overlapping_in(region, mdata)
				children[2].items_overlapping_in(region, mdata)
				children[3].items_overlapping_in(region, mdata)
			end
		end
	end

	# Create children nodes, depends on the concrete implementation
	protected fun subdivide is abstract

	redef fun iterator
	do
		if is_leaf then return data.iterator

		assert children.length >= 4
		return data.iterator + children[0].iterator + children[1].iterator + children[2].iterator + children[3].iterator
	end
end