Mercurial > fife-parpg

comparison engine/core/model/structures/instancetree.h @ 0:4a0efb7baf70

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
* Datasets becomes the new trunk and retires after that :-)
author mvbarracuda@33b003aa-7bff-0310-803a-e67f0ece8222
date Sun, 29 Jun 2008 18:44:17 +0000
parents
children 90005975cdbb
comparison
equal deleted inserted replaced
-1:000000000000 0:4a0efb7baf70
1 /***************************************************************************
2 * Copyright (C) 2005-2008 by the FIFE team *
3 * http://www.fifengine.de *
4 * This file is part of FIFE. *
5 * *
6 * FIFE is free software; you can redistribute it and/or modify *
7 * it under the terms of the GNU General Public License as published by *
8 * the Free Software Foundation; either version 2 of the License, or *
9 * (at your option) any later version. *
10 * *
11 * This program is distributed in the hope that it will be useful, *
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
14 * GNU General Public License for more details. *
15 * *
16 * You should have received a copy of the GNU General Public License *
17 * along with this program; if not, write to the *
18 * Free Software Foundation, Inc., *
19 * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA *
20 ***************************************************************************/
21
22 #ifndef FIFE_INSTANCETREE_H
23 #define FIFE_INSTANCETREE_H
24
25 // Standard C++ library includes
26 #include <list>
27
28 // 3rd party library includes
29
30 // FIFE includes
31 // These includes are split up in two parts, separated by one empty line
32 // First block: files included from the FIFE root src
33 #include "util/base/fifeclass.h"
34
35 #include "util/structures/quadtree.h"
36 #include "model/metamodel/modelcoords.h"
37
38 namespace FIFE {
39
40 class Instance;
41
42 class InstanceTree: public FifeClass {
43 static const int kTreeDepth = 2;
44 public:
45 typedef std::list<Instance*> InstanceList;
46 typedef QuadTree< InstanceList, kTreeDepth > InstanceQuadTree;
47 typedef InstanceQuadTree::Node InstanceTreeNode;
48
49 /** Constructor
50 *
51 */
52 InstanceTree();
53
54 /** Destructor
55 *
56 */
57 virtual ~InstanceTree();
58
59 /** Adds an instance to the quad tree.
60 *
61 * Adds an instance to the quad tree based upon it's location on the layer and it's
62 * area.
63 *
64 * @param instance A pointer to the instance to add.
65 */
66 bool addInstance(Instance* instance);
67
68 /** Removes an instance from the quad tree.
69 *
70 * Locates an instance in the quad tree then removes it.
71 *
72 * @param instance A pointer to the instance to find and remove.
73 */
74 bool removeInstance(Instance* instance);
75
76 /** Find all instances in a given area.
77 *
78 * Takes a box as an area then returns a vector filled with all instances that intersect
79 * with that box.
80 *
81 * @param point A ModelCoordinate representing the upper left part of the search area.
82 * @param w The width of the search area in Model Units.
83 * @param h The height of the search area in Model Units.
84 * @param lst vector reference that will be filled with all instances within that space.
85 */
86 void findInstances(const ModelCoordinate& point, int w, int h, InstanceList& lst);
87
88 /** See QuadNode::apply_visitor
89 */
90 template<typename Visitor> void applyVisitor(Visitor& visitor) {
91 m_tree.apply_visitor(visitor);
92 }
93
94
95 private:
96 InstanceQuadTree m_tree;
97
98 };
99
100 }
101
102 #endif