/// <summary>
/// The CollisionTreeNode class replaces the OctreeNode class in a CollisionTree. In addition to the 
/// spatial definition of the OctreeNode, the CollisionTreeNode stores a list of CollideableElements
/// which are at least partially inside the space of this node. This allows the tree to be quickly searched
/// for CollideableElements by their spatial locations. 
/// </summary>
public class CollisionTreeNode : OctreeNode
{
	/*
	 * CLASS PROPERTIES
	 */
	/// <summary>
	/// list with elements included in the node (only created on leaf nodes) 
	/// </summary>
	private List<CollideableElement> elems;

	/*
	 * CONSTRUCTOR
	 */
	/// <summary>
	/// Recursive constructor to create a new
	/// collision tree node and children.
	/// </summary>
	/// <param name="newTree">A collision tree object that is the root of the tree</param>
	/// <param name="newParent">the collision tree node that is the parent to this one</param>
	/// <param name="newGame">the TwelveCylinderGame object</param>
	/// <param name="collisionBox">the collision box that defines the new tree node</param>
	/// <param name="possibleElems">an array of bools indicating if each element in the newElems array was contained by the parent tree node</param>
	/// <param name="newElems">the collideable element array that is contained by this tree</param>
	/// <param name="depth">the current depth in the tree of this node</param>
	/// <param name="maxDivisions">the subdivision level of the new tree node where 0 is a leaf node</param>
	public CollisionTreeNode(Octree newTree, OctreeNode newParent, TwelveCylinderGame newGame, Bounds box,
		bool[] possibleElems, CollideableElement[] newElems, uint depth, uint maxDivisions)
		: base(newTree, newParent, newGame, box, depth)
	{
		uint numElements = 0;

		// if subdivision needed
		if (depth < maxDivisions)
		{
			bool[] contained = new bool[newElems.Length];
			for (int i = 0; i < newElems.Length; i++)
			{
				if (!possibleElems[i])
					contained[i] = false; //parent doesn't contain the element
				else if (newElems[i].box.BoxOverlap(box))
				{
					contained[i] = true; //this tree node contains the element
					numElements++;
				}
				else
					contained[i] = false; //this tree node does not contain the element
			}
			// if collision tree node contains one or zero
			// collideable elements we can stop subdivision
			if (numElements == 1)
			{
				for (int i = 0; i < contained.Length; i++)
					if (contained[i])
					{
						this.AddElement(newElems[i]); //add the one element and stop
						return;
					}
			}
			else if (numElements == 0)
				return; //no elements in the node, we can stop

			subdivide(contained, newElems, maxDivisions);
		}
		else
		{
			//add collideable elements to leaf node
			for (int i = 0; i < newElems.Length; i++)
			{
				if (possibleElems[i])
					this.AddElement(newElems[i]);
			}
		}
	}

	/*
	 * METHODS
	 */
	/// <summary>
	/// subdivides this collision octree node into 8 children
	/// </summary>
	/// <param name="possibleElems">the array of bools that describe which collideable elements are contained by this tree node1</param>
	/// <param name="newElems">the elements being added to the tree</param>
	/// <param name="maxDivisions">the maximum subdivision level to drill down to</param>
	public virtual void subdivide(bool[] possibleElems, CollideableElement[] newElems, uint maxDivisions)
	{
		uint childDepth = treeLevel + 1;
		// create the 8 children
		children = new CollisionTreeNode[NUM_TREE_CHILDREN];
		//octree subdivisons
		Bounds[] childrenBox = getChildNodeBounds();
		// increment subdivision level and create new tree nodes
		for (uint i = 0; i < NUM_TREE_CHILDREN; i++)
			children[i] = new CollisionTreeNode(curTree, this, curGame, childrenBox[i],
										possibleElems, newElems, childDepth, maxDivisions);
	}

	/*
	 * COLLIDABLE ELEMENT LIST
	 */
	/// <summary>
	/// recursive method to add a collidable element to the tree
	/// </summary>
	/// <param name="newElem">the collideable element to add to the tree</param>
	public void AddElement(CollideableElement newElem)
	{
		// if element do not intersect node, return
		if (newElem.box.BoxOverlap(box) == false)
			return;

		if (children == null)
		{
			//only add collidable elements to leaf nodes...
			if (elems == null) //if no elements list, add one
				elems = new List<CollideableElement>();

			// add element to list
			elems.Add(newElem);
			newElem.AddTreeNode(this);
		}
		else
		{
			// if not a leaf recurse to all its children
			foreach (CollisionTreeNode child in children)
				child.AddElement(newElem);
		}
	}

	/// <summary>
	/// removes a collidable element from this node
	/// </summary>
	/// <param name="e">the collideable element to remove</param>
	public void RemoveElement(CollideableElement e)
	{
		if (elems != null)
			elems.Remove(e);
	}

	/// <summary>
	/// Recursive function to get all elements 
	/// that intersect the specified bounding box.
	/// </summary>
	/// <param name="elemList">the output list of elements with intersecting bounding boxes</param>
	/// <param name="testBox">the bounding box to test for intersection</param>
	/// <param name="searchCount">the ID representing the current iteration of the element search function. It prevents redudant entries in the element list</param>
	public void GetElements(Bounds testBox, ref List<CollideableElement> elemList, uint searchCount)
	{
		// if selection box does not intersect node box, return
		if (!testBox.BoxOverlap(box))
			return; //test box does not overlap with tree node's box

		if (elems != null)
		{
			//leaf node that contains elements
			foreach (CollideableElement elem in elems)
			{
				// elements can be repeated in many nodes
				// only add element to selection list if not already 
				// added by another node in this same recursion
				if (elem.LastSearchId < searchCount)
				{
					// if selection box intersect the element box
					if (elem.box.BoxOverlap(testBox))
						elemList.Add(elem);  // add element to selection list

					// set this recuse id to prevent duplicate results
					elem.LastSearchId = searchCount;
				}
			}
		}
		else if (children != null)
		{
			// if not a leaf node, recurse to all children
			foreach (CollisionTreeNode child in children)
				child.GetElements(testBox, ref elemList, searchCount);
		}
	}

	/// <summary>
	/// recursively gets all elements in the tree
	/// </summary>
	/// <param name="elemList">the output list of elements</param>
	/// <param name="searchCount">the recusion search id</param>
	public void GetAllElements(ref List<CollideableElement> elemList, uint searchCount)
	{
		if (elems != null)
		{
			//leaf node that contains elements
			foreach (CollideableElement elem in elems)
			{
				// elements can be repeated in many nodes
				// only add element to selection list if not already 
				// added by another node in this same recursion
				if (elem.LastSearchId < searchCount)
				{
					elemList.Add(elem);  // add element to selection list
					// set this recuse id to prevent duplicate results
					elem.LastSearchId = searchCount;
				}
			}
		}
		else if (children != null)
		{
			// if not a leaf node, recurse to all children
			foreach (CollisionTreeNode child in children)
				child.GetAllElements(ref elemList, searchCount);
		}
	}
}