--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/engine/core/model/structures/instancetree.cpp	Sun Jun 29 18:44:17 2008 +0000
@@ -0,0 +1,106 @@
+/***************************************************************************
+ *   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              *
+ ***************************************************************************/
+
+// Standard C++ library includes
+
+// 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 directory
+// Second block: files included from the same folder
+#include "model/structures/instance.h"
+#include "util/structures/rect.h"
+
+#include "instancetree.h"
+
+
+namespace FIFE {
+
+	InstanceTree::InstanceTree(): FifeClass() {
+	}
+
+	InstanceTree::~InstanceTree() {
+	}
+
+	bool InstanceTree::addInstance(Instance* instance) {
+		ModelCoordinate coords = instance->getLocationRef().getLayerCoordinates();
+		InstanceList& list = m_tree.find_container(coords.x,coords.y,0,0)->data();
+		list.push_back(instance);
+		return true;
+	}
+
+	bool InstanceTree::removeInstance(Instance* instance) {
+		ModelCoordinate coords = instance->getLocationRef().getLayerCoordinates();
+		InstanceList& list = m_tree.find_container(coords.x,coords.y, 0, 0)->data();
+
+		for(InstanceList::iterator i = list.begin(); i != list.end(); ++i) {
+			if((*i) == instance) {
+				list.erase(i);
+				return true;
+			}
+		}
+
+		return false;
+	}
+
+	class InstanceListCollector {
+		public:
+			InstanceTree::InstanceList& instanceList;
+			Rect searchRect;
+			InstanceListCollector(InstanceTree::InstanceList& a_instanceList, const Rect& rect)
+			: instanceList(a_instanceList), searchRect(rect) {
+			}
+			bool visit(InstanceTree::InstanceTreeNode* node, int d);
+	};
+
+	bool InstanceListCollector::visit(InstanceTree::InstanceTreeNode* node, int d) {
+		InstanceTree::InstanceList& list = node->data();
+		for(InstanceTree::InstanceList::const_iterator it(list.begin()); it != list.end(); ++it) {
+			ModelCoordinate coords = (*it)->getLocationRef().getLayerCoordinates();
+			if( searchRect.contains(Point(coords.x,coords.y)) ) {
+				instanceList.push_back(*it);
+			}
+		}
+		return true;
+	}
+
+	void InstanceTree::findInstances(const ModelCoordinate& point, int w, int h, InstanceTree::InstanceList& list) {
+		InstanceTreeNode * node = m_tree.find_container(point.x, point.y, w, h);
+		Rect rect(point.x, point.y, w, h);
+		InstanceListCollector collector(list,rect);
+
+		node->apply_visitor(collector);
+
+		node = node->parent();
+		while( node ) {
+			for(InstanceList::const_iterator it(node->data().begin()); it != node->data().end(); ++it) {
+				ModelCoordinate coords = (*it)->getLocationRef().getLayerCoordinates();
+				if( rect.contains(Point(coords.x,coords.y)) ) {
+					list.push_back(*it);
+				}
+			}
+			node = node->parent();
+		}
+	}
+
+}