--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/engine/core/model/structures/instancetree.h	Sun Jun 29 18:44:17 2008 +0000
@@ -0,0 +1,102 @@
+/***************************************************************************
+ *   Copyright (C) 2005-2008 by the FIFE team                              *
+ *   http://www.fifengine.de                                               *
+ *   This file is part of FIFE.                                            *
+ *                                                                         *
+ *   FIFE is free software; you can redistribute it and/or modify          *
+ *   it under the terms of the GNU General Public License as published by  *
+ *   the Free Software Foundation; either version 2 of the License, or     *
+ *   (at your option) any later version.                                   *
+ *                                                                         *
+ *   This program 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 General Public License for more details.                          *
+ *                                                                         *
+ *   You should have received a copy of the GNU General Public License     *
+ *   along with this program; if not, write to the                         *
+ *   Free Software Foundation, Inc.,                                       *
+ *   51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA              *
+ ***************************************************************************/
+
+#ifndef FIFE_INSTANCETREE_H
+#define FIFE_INSTANCETREE_H
+
+// Standard C++ library includes
+#include <list>
+
+// 3rd party library includes
+
+// FIFE includes
+// These includes are split up in two parts, separated by one empty line
+// First block: files included from the FIFE root src
+#include "util/base/fifeclass.h"
+
+#include "util/structures/quadtree.h"
+#include "model/metamodel/modelcoords.h"
+
+namespace FIFE {
+
+	class Instance;
+
+	class InstanceTree: public FifeClass {
+		static const int kTreeDepth = 2;
+	public:
+		typedef std::list<Instance*> InstanceList;
+		typedef QuadTree< InstanceList, kTreeDepth > InstanceQuadTree;
+		typedef InstanceQuadTree::Node InstanceTreeNode;
+
+		/** Constructor
+		 *
+		 */
+		InstanceTree();
+
+		/** Destructor
+		 *
+		 */
+		virtual ~InstanceTree();
+
+		/** Adds an instance to the quad tree.
+		 *
+		 * Adds an instance to the quad tree based upon it's location on the layer and it's
+		 * area.
+		 *
+		 * @param instance A pointer to the instance to add.
+		 */
+		bool addInstance(Instance* instance);
+
+		/** Removes an instance from the quad tree.
+		 *
+		 * Locates an instance in the quad tree then removes it.
+		 *
+		 * @param instance A pointer to the instance to find and remove.
+		 */
+		bool removeInstance(Instance* instance);
+
+		/** Find all instances in a given area.
+		 *
+		 * Takes a box as an area then returns a vector filled with all instances that intersect
+		 * with that box.
+		 *
+		 * @param point A ModelCoordinate representing the upper left part of the search area.
+		 * @param w The width of the search area in Model Units.
+		 * @param h The height of the search area in Model Units.
+		 * @param lst vector reference that will be filled with all instances within that space.
+		 */
+		void findInstances(const ModelCoordinate& point, int w, int h, InstanceList& lst);
+		
+		/** See QuadNode::apply_visitor
+		 */
+		template<typename Visitor> void applyVisitor(Visitor& visitor) {
+			m_tree.apply_visitor(visitor);
+		}
+
+
+	private:
+		InstanceQuadTree m_tree;
+
+	};
+
+}
+
+#endif