using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using Chernobyl.Collections.Generic;
using Chernobyl.Collections.Generic.Hierarchy;
using Chernobyl.Event;
using Chernobyl.Mathematics.Geometry;
using Chernobyl.Mathematics.Movement;
using Enumerable = System.Linq.Enumerable;

namespace Chernobyl.Mathematics.Collision
{
    /// <summary>
    /// An <see cref="ICollidableCollection{TContainedCollidable, TCollider}"/>
    /// that builds a 2D collision graph using 2D quads that are organized into
    /// a tree structure.
    /// </summary>
    /// <typeparam name="TContainedCollidable">The type of
    /// <see cref="ICollidable"/> being held within this
    /// <see cref="ICollidableCollection{TContainedCollidable, TCollider}"/>.
    /// This <see cref="ICollidable"/> type must implement
    /// <see cref="IExtendedCollidable{TCollider}"/> and
    /// <see cref="IExtendedCollidable{Rectangle}"/></typeparam>
    /// <typeparam name="TCollider">The <see cref="ICollidable"/> type that will
    /// be passed in to check for collisions against the
    /// <typeparamref name="TContainedCollidable"/>s contained within this
    /// <see cref="ICollection{T}"/>. This type must implement
    /// <see cref="IExtendedCollidable{Rectangle}"/></typeparam>
    public class QuadTree<TContainedCollidable, TCollider>
        : ShapeDecorator, ICollidableCollection<TContainedCollidable, TCollider>,
        ITreeEnumerable<QuadTree<TContainedCollidable, TCollider>>
        where TContainedCollidable : IExtendedCollidable<TCollider>
        where TCollider : IExtendedCollidable<Rectangle>
    {
        /// <summary>
        /// Constructor.
        /// </summary>
        /// <param name="area">The area this
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> covers.
        /// This is the area where <typeparamref name="TContainedCollidable"/>
        /// can be placed for collision detection. This
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> can not
        /// handle collision detection outside of this area.</param>
        public QuadTree(Rectangle area)
            : this(area, DefaultMaxCollidablesPerNode)
        {}

        /// <summary>
        /// Constructor.
        /// </summary>
        /// <param name="area">The area this
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> covers.
        /// This is the area where <typeparamref name="TContainedCollidable"/>
        /// can be placed for collision detection. This
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> can not
        /// handle collision detection outside of this area.</param>
        /// <param name="maxCollidablesPerNode">The maximum number of
        /// <typeparamref name="TContainedCollidable"/> that can be included in
        /// a single node of a
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> before that
        /// node is split and gains children nodes. By default, this value is
        /// specified by the field <see cref="DefaultMaxCollidablesPerNode"/>.</param>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when the value
        /// of <paramref name="maxCollidablesPerNode"/> is zero. Each node can
        /// hold 1 or more <typeparamref name="TContainedCollidable"/>s per
        /// node.</exception>
        public QuadTree(Rectangle area, uint maxCollidablesPerNode)
        {
            _volume = area;
            MaxCollidablesPerNode = maxCollidablesPerNode;
            Collidables = new List<TContainedCollidable>((int)MaxCollidablesPerNode);
            DirtyCollidables = new List<TContainedCollidable>();
            Children = new QuadTree<TContainedCollidable, TCollider>[ChildrenCount];
        }

        /// <summary>
        /// Adds an <typeparamref name="TContainedCollidable"/> object to this
        /// <see cref="ICollidableCollection{TContainedCollidable, TCollider}"/>.
        /// The object added to this list will be sorted into the collision
        /// graph of this
        /// <see cref="ICollidableCollection{TContainedCollidable, TCollider}"/>.
        /// </summary>
        /// <param name="item">The <typeparamref name="TContainedCollidable"/>
        /// object to add.</param>
        /// <exception cref="Exception">Thrown if the add failed because the
        /// item could not be completely contained within this
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/>.</exception>
        public void Add(TContainedCollidable item)
        {
            if (TryAdd(item) == false)
                throw new ArgumentException("Failed to add the item \"" + item  +
                    "\" to the QuadTree<TContainedCollidable, TCollider> \"" +
                    this + "\". The item could not be entirely contained within " +
                    "the QuadTree<TContainedCollidable, TCollider>. Please expand " +
                    "the size of the QuadTree<TContainedCollidable, TCollider> " +
                    "to allow the item to fit.", "item");
        }

        /// <summary>
        /// Attempts to add the specified <typeparamref name="TContainedCollidable"/>
        /// object to this
        /// <see cref="ICollidableCollection{TContainedCollidable, TCollider}"/>.
        /// If the add is successful then the object will have been sorted into
        /// the collision graph of this
        /// <see cref="ICollidableCollection{TContainedCollidable, TCollider}"/>.
        /// </summary>
        /// <param name="item">The <typeparamref name="TContainedCollidable"/>
        /// object to add.</param>
        /// <returns>True if the add was successful, false if the add could not
        /// be completed because the item could not be completely contained
        /// within this <see cref="QuadTree{TContainedCollidable, TCollider}"/>.</returns>
        public bool TryAdd(TContainedCollidable item)
        {
            bool result = false;

            if(_volume.Encloses(item) == true)
            {
                // either we will take the new item, or one of our children will
                result = true;
                ++_count;

                // if we haven't reached our max number of collidables, then
                // we can just add this to our collidables list
                if (Collidables.Count < MaxCollidablesPerNode)
                {
                    Collidables.Add(item);
                    item.TransformDirtied += OnCollidableTransformDirtied;
                }
                else
                {
                    // if we don't have children, we will have to create them
                    // and attempt to give them our children nodes
                    if(HasChildren == false)
                    {
                        uint childrenCount = 0;
                        Children[childrenCount++] = new QuadTree<TContainedCollidable, TCollider>(_volume.NorthWestQuadrant, MaxCollidablesPerNode);
                        Children[childrenCount++] = new QuadTree<TContainedCollidable, TCollider>(_volume.NorthEastQuadrant, MaxCollidablesPerNode);
                        Children[childrenCount++] = new QuadTree<TContainedCollidable, TCollider>(_volume.SouthWestQuadrant, MaxCollidablesPerNode);
                        Children[childrenCount++] = new QuadTree<TContainedCollidable, TCollider>(_volume.SouthEastQuadrant, MaxCollidablesPerNode);

                        // we create only four children because that's all we can
                        // with a Rectangle, but if the ChildrenCount says
                        // otherwise, we've got problems.
                        if (ChildrenCount != childrenCount)
                            throw new Exception("The number of children specified " +
                            "in ChildrenCount was greater than the number of children " +
                            "created. Please contact Lokas Gate if you see this exception." +
                            "Include the exception information in your correspondence.");

                        foreach (QuadTree<TContainedCollidable, TCollider> child in Children)
                        {
                            // subscribe to this child's OnCollision event
                            child.OnCollisionStarted += OnChildQuadTreeCollision;
                            child.TreeDirtied += OnChildTreeDirtied;
                            child.CollidableMovedOut += OnChildCollidableMovedOut;

                            // attempt to add our Collidables to our new children,
                            // if we succeed for any one of them, than that collidable
                            // now belongs to our children
                            for (int i = 0; i < Collidables.Count; i++)
                            {
                                TContainedCollidable collidable = Collidables[i];

                                if (child.TryAdd(collidable) == true)
                                {
                                    collidable.TransformDirtied -= OnCollidableTransformDirtied;
                                    Collidables.RemoveAt(i);
                                }
                            }
                        }
                    }

                    // try to add the new item to one of our children, if none
                    // of our children will take it, we will.
                    if (Children.Any(quad => quad.TryAdd(item)) == false)
                    {
                        Collidables.Add(item);
                        item.TransformDirtied += OnCollidableTransformDirtied;
                    }
                }
            }

            return result;
        }

        /// <summary>
        /// Removes the specified <typeparamref name="TContainedCollidable"/>
        /// object from this
        /// <see cref="ICollidableCollection{TContainedCollidable, TCollider}"/>.
        /// </summary>
        /// <param name="item">The <typeparamref name="TContainedCollidable"/>
        /// object to remove from this
        /// <see cref="ICollidableCollection{TContainedCollidable, TCollider}"/>.</param>
        /// <returns>True if <paramref name="item"/> was successfully removed
        /// from this <see cref="ICollidableCollection{TContainedCollidable, TCollider}"/>,
        /// otherwise false. This method also returns false if
        /// <paramref name="item"/> could not be found within this
        /// <see cref="ICollidableCollection{TContainedCollidable, TCollider}"/>.</returns>
        public bool Remove(TContainedCollidable item)
        {
            bool result = false;

            // make sure we've resorted dirty collidables first
            Clean();

            // ensure the collidable is inside the volume
            if (_count != 0 && _volume.Encloses(item) == true)
            {
                result = Collidables.Remove(item);
                if (result == false)
                {
                    uint numChildrenWithoutCollidables = 0;

                    // the item is probably in a child, if we have one
                    if (HasChildren == true)
                    {
                        foreach (QuadTree<TContainedCollidable, TCollider> child in Children)
                        {
                            // if our children no longer have collidables, they
                            // will be pruned to save memory.
                            if (result == false)
                            {
                                if (child.Remove(item) == true)
                                {
                                    result = true;
                                    --_count;
                                }
                            }

                            // if our children no longer have collidables, they
                            // will be pruned to save memory.
                            if (child.Count == 0)
                                ++numChildrenWithoutCollidables;
                        }

                        // prune our children if they contain no collidables
                        if (numChildrenWithoutCollidables == Children.Length)
                            ClearChildren();
                    }
                }
                else
                {
                    item.TransformDirtied -= OnCollidableTransformDirtied;
                    --_count;
                }
            }

            return result;
        }

        /// <summary>
        /// Removes all <typeparamref name="TContainedCollidable"/> objects
        /// from this quad tree and all children quad trees.
        /// </summary>
        public void Clear()
        {
            Collidables.Clear();
            ClearChildren();
            _count = 0;
        }

        /// <summary>
        /// Checks if the item passed in is located within the quad tree.
        /// </summary>
        /// <param name="item">The <typeparamref name="TContainedCollidable"/>
        /// object to look for.</param>
        /// <returns>True if the <paramref name="item"/> is contained within this
        ///quad tree, false if otherwise.</returns>
        public bool Contains(TContainedCollidable item)
        {
            // make sure we've resorted dirty collidables first
            Clean();

            bool result = false;

            if(_volume.Encloses(item) == true)
            {
                result = Collidables.Contains(item) ||
                         (HasChildren == true &&
                         Children.Any(child => child.Contains(item)));
            }

            return result;
        }

        /// <summary>
        /// Copies the contents of this quad tree into an array of
        /// <typeparamref name="TContainedCollidable"/> objects.
        /// </summary>
        /// <param name="array">The array that is the destination for all of the
        /// <typeparamref name="TContainedCollidable"/> objects copied from this quad tree.</param>
        /// <param name="arrayIndex">The zero based index at which copying begins.</param>
        public void CopyTo(TContainedCollidable[] array, int arrayIndex)
        {
            // make sure we've resorted dirty collidables first
            Clean();

            if(array == null)
                throw new ArgumentNullException("array", "The array to copy into " +
                    "is null. It must be set to a valid array.");

            if (arrayIndex < 0)
                throw new ArgumentOutOfRangeException("arrayIndex", "index at " +
                    "which to begin copying is less than 0. Cannot begin copying " +
                    "at a negative number.");

            if(_count > (array.Length - arrayIndex))
                throw new ArgumentException("The number of elements in this " +
                "ICollection<T> is greater than the available space from " +
                "arrayIndex to the end of the destination array", "arrayIndex");

            if(Collidables.Count != 0)
            {
                Collidables.CopyTo(array, arrayIndex);
                arrayIndex += Collidables.Count;
            }

            if (HasChildren == true)
            {
                for (int i = 0; i < Children.Length && arrayIndex < array.Length; i++)
                {
                    QuadTree<TContainedCollidable, TCollider> child = Children[i];
                    child.CopyTo(array, arrayIndex);

                    arrayIndex += child.Count;
                }
            }
        }

        /// <summary>
        /// Returns the number of <typeparamref name="TContainedCollidable"/>
        /// instances within this <see cref="QuadTree{TContainedCollidable, TCollider}"/>
        /// and all children <see cref="QuadTree{TContainedCollidable, TCollider}"/>s.
        /// </summary>
        public int Count
        {
            get
            {
                // make sure we've resorted dirty collidables first
                Clean();

                return _count;
            }
            private set { _count = value; }
        }

        /// <summary>
        /// True if this quad tree cannot be modified, false if otherwise.
        /// </summary>
        public bool IsReadOnly
        {
            get { return false; }
        }

        /// <summary>
        /// Returns an <see cref="IEnumerable{T}"/> that can be iterated
        /// over to collect the objects that are colliding with the passed in
        /// <paramref name="collider"/>. Note this method should never
        /// pre-compute the collisions. It should return an
        /// <see cref="IEnumerable{T}"/> that returns an
        /// <see cref="IEnumerator{T}"/> that checks for collisions as it
        /// iterates.
        /// </summary>
        /// <param name="collider">The <typeparamref name="TCollider"/> to check
        /// against for collisions.</param>
        /// <returns>The <see cref="IEnumerable{T}"/> that can be iterated over
        /// to get the <see cref="ICollidable2D"/>s that are being collided
        /// against.</returns>
        public IEnumerable<TContainedCollidable> GetCollidables(TCollider collider)
        {
            // TODO: see if this method can be made faster

            // make sure we've resorted dirty collidables first
            Clean();

            // make sure this quad tree collides with our volume first
            if (collider.IsColliding(_volume) == true)
            {
                // check our collidables for potential collisions
                foreach (TContainedCollidable collidable in
                    Collidables.Where(collidable => collidable.IsColliding(collider) == true))
                {
                    yield return collidable;
                }

                // ask the children for their collidables
                if (HasChildren == true)
                {
                    foreach (TContainedCollidable collidable in
                       Children.SelectMany(child => child.GetCollidables(collider)))
                    {
                        yield return collidable;
                    }
                }
            }
        }

        /// <summary>
        /// Returns an enumerator that iterates through the
        /// <typeparamref name="TContainedCollidable"/> objects contained within this quad tree.
        /// </summary>
        /// <returns>The enumerator to the held <typeparamref name="TContainedCollidable"/>
        /// objects.</returns>
        public IEnumerator<TContainedCollidable> GetEnumerator()
        {
            return ((IEnumerable<QuadTree<TContainedCollidable, TCollider>>)this).SelectMany(quadTrees => quadTrees.Collidables).GetEnumerator();
        }

        /// <summary>
        /// Returns an enumerator that iterates through the
        /// <typeparamref name="TContainedCollidable"/> objects contained within this quad tree.
        /// </summary>
        /// <returns>The enumerator to the held <typeparamref name="TContainedCollidable"/>
        /// objects.</returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        /// <summary>
        /// Returns an enumerator that iterates through the collection.
        /// </summary>
        /// <returns>A <see cref="IEnumerator{T}"/> that can be used to iterate
        /// through the collection.</returns>
        IEnumerator<QuadTree<TContainedCollidable, TCollider>> IEnumerable<QuadTree<TContainedCollidable, TCollider>>.GetEnumerator()
        {
            return BreadthFirst.GetEnumerator();
        }

        /// <summary>
        /// An event that is raised when a collidable has started colliding with
        /// this collidable. When the collision has ended,
        /// <see cref="OnCollisionEnded"/> will be raised.
        /// </summary>
        public event EventHandler OnCollisionStarted;

        /// <summary>
        /// An event that is raised when the collision with a collidable has
        /// ended. This will event will be raised after the invocation of
        /// <see cref="OnCollisionStarted"/>.
        /// </summary>
        public event EventHandler OnCollisionEnded;

        /// <summary>
        /// Checks for a collision between this quad tree and the
        /// <typeparamref name="TCollider"/> passed in.
        /// </summary>
        /// <param name="collider">The <typeparamref name="TCollider"/> to check
        /// for a collision against.</param>
        /// <returns>True if there was a collision against a
        /// <typeparamref name="TContainedCollidable"/> within this
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/>, false if
        /// otherwise.</returns>
        public bool IsColliding(TCollider collider)
        {
            bool result = false;

            // make sure we've resorted dirty collidables first
            Clean();

            if (collider.IsColliding(_volume) == true)
            {
                // first check against our collidables if we have collidables
                result = Collidables.Any(coll => coll.IsColliding(collider));

                // now check against our children, if we have children and
                // if necessary
                if (result == false && HasChildren == true)
                    result = Children.Any(child => child.IsColliding(collider));
            }

            return result;
        }

        /// <summary>
        /// Called when this collidable has collided with another collidable.
        /// This QuadTree just invokes its OnCollision instance when this method
        /// is invoked.
        /// </summary>
        /// <param name="collider">The object that was just hit.</param>
        public void HandleCollisionStarted(ICollidable collider)
        {
            if (OnCollisionStarted != null)
                OnCollisionStarted(this, EventArgs.Empty);
        }

        /// <summary>
        /// Called when this collidable has stopped colliding with another
        /// collidable.
        /// </summary>
        /// <param name="collider">The object that was just hit.</param>
        public void HandleCollisionEnded(ICollidable collider)
        {
            if (OnCollisionEnded != null)
                OnCollisionEnded(this, EventArgs.Empty);
        }

        /// <summary>
        /// The maximum number of <typeparamref name="TContainedCollidable"/>
        /// that can be included in a single node of a
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> before that
        /// node is split and gains children nodes. By default, this value is
        /// specified by the field <see cref="DefaultMaxCollidablesPerNode"/>.
        /// </summary>
        /// <exception cref="ArgumentOutOfRangeException">Thrown when the value
        /// set on this property is zero. Each node can hold 1 or more
        /// <typeparamref name="TContainedCollidable"/>s per node.</exception>
        public uint MaxCollidablesPerNode
        {
            get { return _maxCollidablesPerNode; }
            private set
            {
                if(value == 0)
                    throw new ArgumentOutOfRangeException("value", value, "The " +
                    "value of MaxCollidablesPerNode cannot be zero. Each " +
                    "node can only hold 1 or more collidables per node.");

                _maxCollidablesPerNode = value;
            }
        }

        /// <summary>
        /// The default value for the <see cref="MaxCollidablesPerNode"/>
        /// property. The value of this field is 4.
        /// </summary>
        public const uint DefaultMaxCollidablesPerNode = 4;

        /// <summary>
        /// An <see cref="IEnumerable{T}"/> that iterates over an
        /// <see cref="ITreeEnumerable{T}"/> in depth first order (see
        /// http://en.wikipedia.org/wiki/Depth-first_search for more information).
        /// </summary>
        /// <value></value>
        public IEnumerable<QuadTree<TContainedCollidable, TCollider>> DepthFirst
        {
            get
            {
                return new EnumeratorFactory<QuadTree<TContainedCollidable, TCollider>>(
                    () => new DepthFirstEnumerator<QuadTree<TContainedCollidable, TCollider>>(this, GetChildQuadTreeEnumerator));
            }
        }

        /// <summary>
        /// An <see cref="IEnumerable{T}"/> that iterates over an
        /// <see cref="ITreeEnumerable{T}"/> in breadth first order (see
        /// http://en.wikipedia.org/wiki/Breadth-first_search for more information).
        /// </summary>
        /// <value></value>
        public IEnumerable<QuadTree<TContainedCollidable, TCollider>> BreadthFirst
        {
            get
            {
                return new EnumeratorFactory<QuadTree<TContainedCollidable, TCollider>>(
                    () => new BreadthFirstEnumerator<QuadTree<TContainedCollidable, TCollider>>(this, GetChildQuadTreeEnumerator));
            }
        }

        /// <summary>
        /// Returns a <see cref="String"/> that represents this instance.
        /// </summary>
        /// <returns>
        /// A <see cref="String"/> that represents this instance.
        /// </returns>
        public override string ToString()
        {
            return "{Name=\"" + Name + "\", Volume:" + _volume + "}";
        }

        /// <summary>
        /// Cleans the instance by re-adding any dirty (translated, scaled,
        /// rotated, etc) <typeparamref name="TContainedCollidable"/>s, if
        /// possible. If not possible, the
        /// <typeparamref name="TContainedCollidable"/> is removed and the
        /// <see cref="CollidableMovedOut"/> event is raised. This method also
        /// invokes <see cref="Clean()"/> on the children
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> of this
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/>. Note that
        /// it is not required that you call this method. The
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> will call it
        /// whenever it is necessary (such as when you access the number of
        /// <typeparamref name="TContainedCollidable"/>s contained within this
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> using the
        /// <see cref="Count"/> property). You may need it, however, in cases
        /// where you want the <see cref="CollidableMovedOut"/> event called
        /// early (if it needs to be called).
        /// </summary>
        public void Clean()
        {
            if (IsTreeDirty == true)
            {
                if (DirtyCollidables.Count != 0)
                {
                    // attempt to re-add the dirty collidables to this QuadTree.
                    // If they cannot be re-added, those who need to know will be
                    // notified and the collidable will be removed from this QuadTree.
                    foreach (TContainedCollidable collidable in DirtyCollidables)
                    {
                        // we'll assume we are removing all of the dirty
                        // collidables from this QuadTree. If a re-add is successful
                        // the TryAdd method we'll increment the Count as appropriate
                        _count--;

                        if (TryAdd(collidable) == false)
                        {
                            if (CollidableMovedOut != null)
                                CollidableMovedOut(this, new EventArgs<TContainedCollidable>(collidable));
                        }
                    }

                    DirtyCollidables.Clear();
                }

                // clean the rest of the tree below this one
                if (HasChildren == true)
                {
                    foreach (QuadTree<TContainedCollidable, TCollider> child in Children)
                        child.Clean();
                }

                IsTreeDirty = false;
            }
        }

        /// <summary>
        /// The children of this <see cref="QuadTree{TContainedCollidable, TCollider}"/>;
        /// each <see cref="QuadTree{TContainedCollidable, TCollider}"/> has the
        /// number of children specified by <see cref="ChildrenCount"/>. The
        /// children (items in the array not the array itself) may be set to a
        /// NULL value if this <see cref="QuadTree{TContainedCollidable, TCollider}"/>
        /// has no children.
        /// </summary>
        public QuadTree<TContainedCollidable, TCollider>[] Children { get; private set; }

        /// <summary>
        /// The number of children each
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> is given.
        /// The value of this field is 4.
        /// </summary>
        public const uint ChildrenCount = 4;

        /// <summary>
        /// An event that is raised after a
        /// <typeparamref name="TContainedCollidable"/> contained within this
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> or a
        /// descendant <see cref="QuadTree{TContainedCollidable, TCollider}"/>
        /// has had its transform dirtied. In this case, the
        /// <typeparamref name="TContainedCollidable"/> may no longer fit in this
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> and will
        /// need to be resorted upwards in the tree. Note that this event is
        /// only invoked once <typeparamref name="TContainedCollidable"/>. After
        /// it has been invoked, the
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> must be
        /// cleaned by calling <see cref="Clean()"/> for it to be invoked again.
        /// </summary>
        public event EventHandler TreeDirtied;

        /// <summary>
        /// An event that is raised after a
        /// <typeparamref name="TContainedCollidable"/> that was previously
        /// contained within this
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> has been
        /// removed because it has translated, rotated, and/or scaled and can no
        /// longer be contained within this
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/>. Note that
        /// this event is only invoked if the
        ///  <see cref="QuadTree{TContainedCollidable, TCollider}"/> is cleaned
        ///  using the <see cref="Clean()"/> method.
        /// </summary>
        public event EventHandler<EventArgs<TContainedCollidable>> CollidableMovedOut;

        /// <summary>
        /// True if this <see cref="QuadTree{TContainedCollidable, TCollider}"/>
        /// contains <typeparamref name="TContainedCollidable"/>s that need to
        /// be resorted upwards in the tree because their
        /// <see cref="ITransform"/>s were dirtied (they moved or scaled). If
        /// the value of the property is false and true is set on this property
        /// the <see cref="TreeDirtied"/> will be invoked (provided there are
        /// subscribers).
        /// </summary>
        protected bool IsTreeDirty
        {
            get { return _isTreeDirty; }
            private set
            {
                bool previousValue = _isTreeDirty;
                _isTreeDirty = value;

                if (value == true && previousValue == false && TreeDirtied != null)
                    TreeDirtied(this, EventArgs.Empty);
            }
        }

        /// <summary>
        /// The <see cref="IShape"/> instance that implements the
        /// <see cref="IShape"/> functionality.
        /// </summary>
        protected override IShape DecoratedShape
        {
            get { return _volume; }
        }

        /// <summary>
        /// The transform that provides this transforms capabilities.
        /// </summary>
        protected override ITransform DecoratedTransform
        {
            get { return _volume; }
        }

        /// <summary>
        /// A event handler that invokes the <see cref="OnCollisionStarted"/>
        /// event when a child
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/>'s
        /// <typeparamref name="TContainedCollidable"/> is collided against.
        /// </summary>
        /// <param name="sender">The sender of the event.</param>
        /// <param name="e">The arguments to the event.</param>
        void OnChildQuadTreeCollision(object sender, EventArgs e)
        {
            if (OnCollisionStarted != null)
                OnCollisionStarted(this, e);
        }

        /// <summary>
        /// An event handler that is invoked when a child
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> has been
        /// dirtied (it's <see cref="TreeDirtied"/> event has been invoked).
        /// </summary>
        /// <param name="sender">The instance that generated the event.</param>
        /// <param name="e">The <see cref="System.EventArgs"/> instance containing the event data.</param>
        void OnChildTreeDirtied(object sender, EventArgs e)
        {
            IsTreeDirty = true;
        }

        /// <summary>
        /// An event that is raised when a
        /// <typeparamref name="TContainedCollidable"/> contained within this
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> is dirtied
        /// (translated, scaled, etc) and needs to be resorted up into the tree.
        /// </summary>
        /// <param name="sender">The source of the event.</param>
        /// <param name="e">The <see cref="EventArgs"/> instance containing
        ///  the event data.</param>
        void OnCollidableTransformDirtied(object sender, EventArgs e)
        {
            // we remove by index for performance reasons: to prevent having
            // to cast the sender and to prevent having to search the entire
            // list with the List<T>.RemoveAll(Predicate<T>) method.
            int index = Collidables.FindIndex(coll => ReferenceEquals(coll, sender));
            if (index != -1)
            {
                DirtyCollidables.Add(Collidables[index]);
                Collidables.RemoveAt(index);
                IsTreeDirty = true;
            }
        }

        /// <summary>
        /// An event handler that is invoked by a child when it can no longer
        /// contain a <typeparamref name="TContainedCollidable"/> (the child
        /// invoked it's <see cref="CollidableMovedOut"/> event). This method
        /// will attempt to re-add the collidable. If the re-add fails, this
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/>'s
        /// <see cref="CollidableMovedOut"/> event will be raised.
        /// </summary>
        /// <param name="sender">The instance that generated the event.</param>
        /// <param name="e">The <see cref="EventArgs{TContainedCollidable}"/>
        ///  instance containing the event data.</param>
        void OnChildCollidableMovedOut(object sender, EventArgs<TContainedCollidable> e)
        {
            // one of our children has rejected a collidable because the
            // collidable no longer fit within its bounds. We are going to
            // reduce the count because of this and attempt to re-add the
            // collidable. If the add succeeds then the TryAdd will increment
            // the count back up.
            _count--;

            if (TryAdd(e.Value) == false && CollidableMovedOut != null)
                CollidableMovedOut(this, e);
        }

        /// <summary>
        /// A helper method that gets rid of our children.
        /// </summary>
        void ClearChildren()
        {
            for (int i = 0; i < Children.Length; i++)
            {
                // in case someone else has a reference to our child
                // we will remove ourself from the OnCollisionStarted
                // event even though we get rid of the child.
                Children[i].OnCollisionStarted -= OnChildQuadTreeCollision;
                Children[i].TreeDirtied -= OnChildTreeDirtied;
                Children[i].CollidableMovedOut -= OnChildCollidableMovedOut;
                Children[i] = null;
            }
        }

        /// <summary>
        /// True if this <see cref="QuadTree{TContainedCollidable, TCollider}"/>
        /// has children, false if otherwise.
        /// </summary>
        bool HasChildren { get { return Children[0] != null; } }

        /// <summary>
        /// Retrieves the <see cref="IEnumerator{T}"/> for the Children list of
        /// a <see cref="QuadTree{TContainedCollidable, TCollider}"/>. This
        /// method is special in that it checks to see if the Children list
        /// is empty (i.e., all the children are set to null) and, if so,
        /// returns an <see cref="IEnumerator{T}"/> from an empty
        /// <see cref="IEnumerable{T}"/>.
        /// </summary>
        /// <param name="quadTree">The
        /// <see cref="QuadTree{TContainedCollidable, TCollider}"/> whose
        /// children <see cref="IEnumerator{T}"/> is to be retrieved.</param>
        /// <returns>The <see cref="IEnumerator{T}"/> to the
        /// <see cref="Children"/> list or an <see cref="IEnumerator{T}"/> from
        /// an empty <see cref="IEnumerable{T}"/>.</returns>
        static IEnumerator<QuadTree<TContainedCollidable, TCollider>> GetChildQuadTreeEnumerator(QuadTree<TContainedCollidable, TCollider> quadTree)
        {
            return quadTree.HasChildren == true ?
                   ((IEnumerable<QuadTree<TContainedCollidable, TCollider>>)quadTree.Children).GetEnumerator() :
                   Enumerable.Empty<QuadTree<TContainedCollidable, TCollider>>().GetEnumerator();
        }

        /// <summary>
        /// The collidables that are located in this quad tree. If this quad
        /// tree has children, then the collidables will be moved to them, if
        /// possible.
        /// </summary>
        List<TContainedCollidable> Collidables { get; set; }

        /// <summary>
        /// The <typeparamref name="TContainedCollidable"/>s whose transforms
        /// were dirtied because they had been translated, rotated, scaled, etc.
        /// These <typeparamref name="TContainedCollidable"/>s need to be
        /// resorted upwards in the tree.
        /// </summary>
        List<TContainedCollidable> DirtyCollidables { get; set; }

        /// <summary>
        /// The bounding volume for the quad tree.
        /// </summary>
        Rectangle _volume;

        /// <summary>
        /// The backing field to <see cref="MaxCollidablesPerNode"/>
        /// </summary>
        uint _maxCollidablesPerNode;

        /// <summary>
        /// The backing field to <see cref="IsTreeDirty"/>.
        /// </summary>
        bool _isTreeDirty;

        /// <summary>
        /// The backing field to <see cref="Count"/>.
        /// </summary>
        int _count;
    }
}