//=============================================================================
//     _   _                               ____                _  _          
//    | | | |  __ _  _ __   _ __   _   _  / ___|  _ __   _ __ (_)| |_   ___ 
//    | |_| | / _` || '_ \ | '_ \ | | | | \___ \ | '_ \ | '__|| || __| / _ \
//    |  _  || (_| || |_) || |_) || |_| |  ___) || |_) || |   | || |_ |  __/
//    |_| |_| \__,_|| .__/ | .__/  \__, | |____/ | .__/ |_|   |_| \__| \___|
//                  |_|    |_|     |___/         |_|                         
//
//                     HappySprite - We make sprites happy
//
// Copyright (c) 2006 by Tank Monkey Games
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//=============================================================================

using System;
using System.Drawing;
using System.Collections.Generic;

namespace HappySprite.Collisions
{
	public class QuadTree<T>
	{
		#region Private Properties
		int _depth;
		RectangleF _rect;
		List<T> _objects = null;

		private QuadTree<T> _topLeftChild = null;
        private QuadTree<T> _topRightChild = null;
        private QuadTree<T> _bottomLeftChild = null;
        private QuadTree<T> _bottomRightChild = null;
		#endregion
	
		#region Public Properties
		public RectangleF Rect
		{
			get { return _rect; }
		}

		public QuadTree<T> TopLeftChild
		{
			get { return _topLeftChild; }
		}

        public QuadTree<T> TopRightChild
		{
			get { return _topRightChild; }
		}

        public QuadTree<T> BottomLeftChild
		{
			get { return _bottomLeftChild; }
		}

        public QuadTree<T> BottomRightChild
		{
			get { return _bottomRightChild; }
		}
		#endregion

		private void Add(T obj)
		{
			if (_objects == null)
				_objects = new List<T>();

			_objects.Add(obj);
		}

		private void Remove(T obj)
		{
			if (_objects.Contains(obj))
				_objects.Remove(obj);
		}


		public QuadTree(RectangleF rect, int depth)
		{
			_rect = rect;
			_depth = depth;
		}

		public void Insert(RectangleF rect, T obj)
		{
			// if no intersection quit
			if (RectangleF.Intersect(_rect, rect).IsEmpty)
				return;

			if (_depth == 0)
			{
				Add(obj);
				return;
			}
		
			// if we have no children create some
			if (_topLeftChild == null)
			{
				float childWidth = _rect.Width / 2;
				float childHeight = _rect.Height / 2;

				_topLeftChild = new QuadTree<T>(new RectangleF(_rect.X, _rect.Y, childWidth, childHeight), _depth -1);
                _topRightChild = new QuadTree<T>(new RectangleF(_rect.X + childWidth, _rect.Y, childWidth, childHeight), _depth - 1);
                _bottomLeftChild = new QuadTree<T>(new RectangleF(_rect.X, _rect.Y + childHeight, childWidth, childHeight), _depth - 1);
                _bottomRightChild = new QuadTree<T>(new RectangleF(_rect.X + childWidth, _rect.Y + childHeight, childWidth, childHeight), _depth - 1);
			}

			// insert the object in our children
			_topLeftChild.Insert(rect, obj);
			_topRightChild.Insert(rect, obj);
			_bottomLeftChild.Insert(rect, obj);
			_bottomRightChild.Insert(rect, obj);
		}

		public void Remove(RectangleF rect, T obj)
		{
			if (_depth == 0)
			{
				Remove(obj);
			}
			else if (_topLeftChild != null)
			{
				_topLeftChild.Remove(rect, obj);
				_topRightChild.Remove(rect, obj);
				_bottomLeftChild.Remove(rect, obj);
				_bottomLeftChild.Remove(rect, obj);
			}
		}

		public void Clear()
		{
			if (_depth == 0 && _objects != null)
			{
				_objects.Clear();
			}
			else if (_topLeftChild != null)
			{
				_topLeftChild.Clear();
				_topRightChild.Clear();
				_bottomLeftChild.Clear();
				_bottomRightChild.Clear();
			}
		}

		public List<T> Get(RectangleF rect)
		{
			// if it doesn't intersect us then it's not going to intersect our children either
			if (RectangleF.Intersect(_rect, rect).IsEmpty)
				return null;

			// are there children to test?
			if (_topLeftChild == null)
			{
				if (_objects == null || _objects.Count == 0)
					return null;
				else
					return _objects;
			}

			List<T> topLeftChildObjects = _topLeftChild.Get(rect);
            List<T> topRightChildObjects = _topRightChild.Get(rect);
            List<T> bottomLeftChildObjects = _bottomLeftChild.Get(rect);
            List<T> bottomRightChildObjects = _bottomRightChild.Get(rect);

            List<T> results = new List<T>();

			if(topLeftChildObjects != null)
				foreach(T o in topLeftChildObjects)
					if( ! results.Contains(o) )
						results.Add(o);

			if(topRightChildObjects != null)
				foreach(T o in topRightChildObjects)
					if( ! results.Contains(o) )
						results.Add(o);

			if(bottomLeftChildObjects != null)
				foreach(T o in bottomLeftChildObjects)
					if( ! results.Contains(o) )
						results.Add(o);

			if(bottomRightChildObjects != null)
				foreach(T o in bottomRightChildObjects)
					if( ! results.Contains(o) )
						results.Add(o);

			return results;
		}
	}
}