Debian Codegraph @

engine/core/model/structures/instancetree.h

raw
1 /***************************************************************************
2 * Copyright (C) 2005-2019 by the FIFE team *
3 * http://www.fifengine.net *
4 * This file is part of FIFE. *
5 * *
6 * FIFE is free software; you can redistribute it and/or *
7 * modify it under the terms of the GNU Lesser General Public *
8 * License as published by the Free Software Foundation; either *
9 * version 2.1 of the License, or (at your option) any later version. *
10 * *
11 * This library 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 GNU *
14 * Lesser General Public License for more details. *
15 * *
16 * You should have received a copy of the GNU Lesser General Public *
17 * License along with this library; if not, write to the *
18 * Free Software Foundation, Inc., *
19 * 51 Franklin Street, 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 public:
44 static const int32_t MIN_TREE_SIZE = 2;
45
46 typedef std::list<Instance*> InstanceList;
47 typedef QuadTree< InstanceList, MIN_TREE_SIZE > InstanceQuadTree;
48 typedef InstanceQuadTree::Node InstanceTreeNode;
49
50 /** Constructor
51 *
52 */
53 InstanceTree();
54
55 /** Destructor
56 *
57 */
58 virtual ~InstanceTree();
59
60 /** Adds an instance to the quad tree.
61 *
62 * Adds an instance to the quad tree based upon it's location on the layer and it's
63 * area.
64 *
65 * @param instance A pointer to the instance to add.
66 * @note In case you added the instance before this will throw.
67 */
68 void addInstance(Instance* instance);
69
70 /** Removes an instance from the quad tree.
71 *
72 * Locates an instance in the quad tree then removes it.
73 *
74 * @param instance A pointer to the instance to find and remove.
75 * @note In case you did @b not add the instance before this will throw.
76 */
77 void removeInstance(Instance* instance);
78
79 /** Find all instances in a given area.
80 *
81 * Takes a box as an area then returns a vector filled with all instances that intersect
82 * with that box.
83 *
84 * @param point A ModelCoordinate representing the upper left part of the search area.
85 * @param w The width of the search area in Model Units.
86 * @param h The height of the search area in Model Units.
87 * @param list vector reference that will be filled with all instances within that space.
88 */
89 void findInstances(const ModelCoordinate& point, int32_t w, int32_t h, InstanceList& list);
90
91 /** See QuadNode::apply_visitor
92 */
93 template<typename Visitor> void applyVisitor(Visitor& visitor) {
94 m_tree.apply_visitor(visitor);
95 }
96
97
98 private:
99 InstanceQuadTree m_tree;
100 std::map<Instance*,InstanceTreeNode*> m_reverse;
101 };
102
103 }
104
105 #endif