/// <summary>
/// A simple node in an Octree. 
/// </summary>
public class OctreeNode : Node
{
	/*
	 * CONSTANTS
	 */
	/// <summary>
	/// the number of children in an octree is 8.
	/// I made this a constant in case the fundemental nature
	/// of three dimensional space changes one day and I needed
	/// to change it.
	/// </summary>
	public const int NUM_TREE_CHILDREN = 8;

	/*
	 * CLASS PROPERTIES
	 */
	/// <summary>
	/// the parent of this tree node
	/// </summary>
	protected OctreeNode curParent;
	/// <summary>
	/// the root of this tree node
	/// </summary>
	protected Octree curTree;
	/// <summary>
	/// the box defining this tree node 
	/// </summary>
	protected Bounds box;
	/// <summary>
	/// the node children (if null node is a leaf) 
	/// </summary>
	protected OctreeNode[] children;
	/// <summary>
	/// depth in the tree that this node defines
	/// </summary>
	protected uint treeLevel;

	/*
	 * CONSTRUCTOR
	 */
	/// <summary>
	/// recursive constructor to create a new octree node and children
	/// </summary>
	/// <param name="newTree">an octree object that holds the root of the tree</param>
	/// <param name="newParent">the tree node that is the parent to this one</param>
	/// <param name="newGame">the TwelveCylinder game object</param>
	/// <param name="box">the box that defines the new tree node</param>
	/// <param name="depth">the current depth in the tree of this node</param>
	/// <param name="maxDivisions">the maximum subdivision level of the tree node where 0 is the root node</param>
	public OctreeNode(Octree newTree, OctreeNode newParent, TwelveCylinderGame newGame, Bounds newBox, uint depth, uint maxDivisions)
		: base(newGame, "octree node", NodeType.SceneItem)
	{
		if (newBox == null)
			throw new ArgumentNullException("Octree node requires non-null bounds.");

		curTree = newTree;      //parent octree
		curParent = newParent;  //parent tree node

		//tree node bounds
		box = newBox;
		treeLevel = depth;

		// if subdivision still needed
		if (depth < maxDivisions)
			subdivide(maxDivisions);
		else
			curTree.addLeafNode(this);
	}

	//additional constructors omitted

	/*
	 * UNLOADING
	 */
	/// <summary>
	/// unloads this collision tree node and it's children
	/// </summary>
	/// <param name="disposeResources"></param>
	public override void unload(bool disposeResources)
	{
		base.unload(disposeResources);
		curParent = null;
		curTree = null;
		box = null;
		if (children != null)
		{
			for (int i = 0; i < OctreeNode.NUM_TREE_CHILDREN; i++)
				children[i].unload(disposeResources);
			children = null;
		}
	}

	/*
	 * METHODS
	 */
	/// <summary>
	/// recursive method to get the leaf nodes which intersect with the specified bound box
	/// </summary>
	/// <param name="b">a bounding box to test</param>
	/// <param name="leafNodes">the output list of leaf nodes that intersect with the bounds</param>
	public void GetIntersectedLeafNodes(Bounds b, ref List<OctreeNode> leafNodes)
	{
		if (!b.BoxOverlap(box))
			return; //test box does not overlap with tree node's box

		if (children != null)
		{
			// if not a leaf node, recurse to all children
			foreach (OctreeNode child in children)
				child.GetIntersectedLeafNodes(b, ref leafNodes);
		}
		else
			leafNodes.Add(this);
	}

	/// <summary>
	/// recursive function to find the octree leaf node that contains
	/// the specified world position
	/// </summary>
	/// <param name="worldPos">a world space coordinate</param>
	/// <returns>the containing leaf node</returns>
	public virtual OctreeNode getContainingLeaf(Vector3 worldPos)
	{
		if (box.PointInside(worldPos))
		{
			if (children == null)
				return this;

			OctreeNode curLeaf = null;
			foreach (OctreeNode node in children)
			{
				curLeaf = node.getContainingLeaf(worldPos);
				if (curLeaf != null)
					return curLeaf;
			}
		}
		return null;
	}

	/// <summary>
	/// recursively gets the maximum depth of this tree branch
	/// </summary>
	/// <returns>the maximum tree depth contained by this branch</returns>
	public virtual uint getMaximumDepth()
	{
		if (children == null)
			return treeLevel;
		else
		{
			uint maxDepth = 0;
			uint curDepth;
			for (int i = 0; i < NUM_TREE_CHILDREN; i++)
			{
				curDepth = children[i].getMaximumDepth();
				if (curDepth > maxDepth)
					maxDepth = curDepth;
			}
			return maxDepth;
		}
	}

	/// <summary>
	/// Gets an array of child Bounds that subdivide
	/// this tree node into 8 equal parts.
	/// </summary>
	/// <returns>an array of 8 Bounds</returns>
	protected virtual Bounds[] getChildNodeBounds()
	{
		Vector3 center = box.Center;
		Bounds[] children = new Bounds[NUM_TREE_CHILDREN];
		Vector3 min = box.Min;
		Vector3 max = box.Max;
		Vector3 center = box.Center;

		children[0] = new Bounds(curGame, min, center);
		children[1] = new Bounds(curGame, new Vector3(center.X, min.Y, min.Z),
											new Vector3(max.X, center.Y, center.Z));
		children[2] = new Bounds(curGame, new Vector3(min.X, center.Y, min.Z),
											new Vector3(center.X, max.Y, center.Z));
		children[3] = new Bounds(curGame, new Vector3(center.X, center.Y, min.Z),
											new Vector3(max.X, max.Y, center.Z));
		children[4] = new Bounds(curGame, new Vector3(min.X, min.Y, center.Z),
										   new Vector3(center.X, center.Y, max.Z));
		children[5] = new Bounds(curGame, new Vector3(center.X, min.Y, center.Z),
											new Vector3(max.X, center.Y, max.Z));
		children[6] = new Bounds(curGame, new Vector3(min.X, center.Y, center.Z),
											new Vector3(center.X, max.Y, max.Z));
		children[7] = new Bounds(curGame, center, max);

		return children;
	}

	/// <summary>
	/// Subdivides this node in the octree into 8 children
	/// and recursively continues octree creation.
	/// </summary>
	protected virtual void subdivide(uint maxDivisions)
	{
		uint childDepth = treeLevel + 1;
		// create the 8 children
		children = new OctreeNode[NUM_TREE_CHILDREN];
		Bounds[] childrenBox = getChildNodeBounds();
		// increment subdivision level and create new tree nodes
		for (uint i = 0; i < NUM_TREE_CHILDREN; i++)
			children[i] = new OctreeNode(curTree, this, curGame, childrenBox[i], childDepth, maxDivisions);
	}

	//encapsulators omitted

	/*
	 * UPDATE
	 */
	public override void update(GameTime gameTime, TwelveCylinder.GameCamera.Camera curCam, Matrix projMatrix, Matrix viewProjection)
	{
		base.update(gameTime, curCam, projMatrix, viewProjection);
		//update octree children nodes
		if (children != null)
			foreach (OctreeNode treeNode in children)
				treeNode.update(gameTime, curCam, projMatrix, viewProjection);
	}

	/*
	 * RENDER
	 */
	/// <summary>
	/// recursively draws the boundaries of this tree node and its children to the specified depth
	/// </summary>
	/// <param name="depth">the maximum depth to drill into this tree and draw bounds</param>
	public virtual void DrawTreeBounds(uint depth)
	{
		box.Render();
		if (children != null && depth > 0)
		{
			depth--;
			for (int i = 0; i < OctreeNode.NUM_TREE_CHILDREN; i++)
				children[i].DrawTreeBounds(depth);
		}
	}
}