include/storage/RTree.h

   1 /** Aesalon, a tool to visualize program behaviour in real time.
   2         Copyright (C) 2009-2011, Aesalon development team.
   3
   4         Aesalon is distributed under the terms of the GNU GPLv3. See
   5         the included file LICENSE for more information.
   6
   7         @file include/storage/RTree.h
   8 */
   9
  10 #ifndef AesalonStorage_RTree_H
  11 #define AesalonStorage_RTree_H
  12
  13 #include <stdarg.h>
  14 #include "Config.h"
  15
  16 #include "util/MessageSystem.h"
  17 #include "Mempool.h"
  18
  19 namespace Storage {
  20
  21 /** An n-dimensional R-tree.
  22         Notes:
  23         - Key must support a basic assignment specifier and also the element zero, plus all the usual arithmetic operators.
  24                 Using an elementary type is a very good idea.
  25         - Value must be either a basic type or a pointer.
  26         - Minimum <= Maximum/2. (Logic in code assumes this.)
  27         - Maximum <= some reasonable number. Many linear searches through lists of this size take place.
  28                 A reasonable size is sixteen.
  29         - Dimensions should be as small as possible; many linear operations take place on this number.
  30                 Six is a reasonable upper bound.
  31         - FloatKey should be a version of Key that supports floating-point arithmetic (or at least non-integer division).
  32         Unless otherwise noted, all algorithms are from
  33                 A Guttman, R-Trees: A Dynamic Index Structure for Spatial Searching, 1984.
  34
  35         @todo Improve condenseTree's handling of non-leaf nodes.
  36 */
  37
  38 #define RTreeTemplate \
  39         template< RTreeTemplateItems >
  40 #define RTreeTemplateItems \
  41         typename Key, typename Value, int Dimensions, int Maximum, int Minimum, typename FloatKey
  42 #define RTreeScope \
  43         RTree<Key, Value, Dimensions, Maximum, Minimum, FloatKey>
  44
  45 template<typename Key, typename Value, int Dimensions, int Maximum, int Minimum, typename FloatKey=Key>
  46 class RTree {
  47 public:
  48         class Bound {
  49         private:
  50                 Key m_bounds[Dimensions][2];
  51         public:
  52                 Bound() {
  53                         for(int i = 1; i < Dimensions; i ++) {
  54                                 m_bounds[i][0] = m_bounds[i][1] = 0.0;
  55                         }
  56                 }
  57                 Bound(Key d1_start, Key d1_end, ...) {
  58                         va_list ap;
  59                         va_start(ap, d1_end);
  60
  61                         m_bounds[0][0] = d1_start, m_bounds[0][1] = d1_end;
  62
  63                         for(int i = 1; i < Dimensions; i ++) {
  64                                 m_bounds[i][0] = va_arg(ap, Key);
  65                                 m_bounds[i][1] = va_arg(ap, Key);
  66                         }
  67
  68                         va_end(ap);
  69                 }
  70
  71                 Key start(int dimension) const { return m_bounds[dimension][0]; }
  72                 Key end(int dimension) const { return m_bounds[dimension][1]; }
  73
  74                 bool overlaps(const Bound &other) const {
  75                         for(int i = 0; i < Dimensions; i ++) {
  76                                 if(m_bounds[i][0] > other.m_bounds[i][1] ||
  77                                         m_bounds[i][1] < other.m_bounds[i][0]) return false;
  78                         }
  79                         return true;
  80                 }
  81
  82                 Key toCover(const Bound &other) {
  83                         Key volume = 0;
  84                         Key bounds[Dimensions][2];
  85                         Key sizes[Dimensions];
  86
  87                         for(int i = 0; i < Dimensions; i ++) {
  88                                 bounds[i][0] = m_bounds[i][0];
  89                                 bounds[i][1] = m_bounds[i][1];
  90                                 sizes[i] = m_bounds[i][1] - m_bounds[i][0];
  91                         }
  92
  93                         for(int i = 0; i < Dimensions; i ++) {
  94                                 Key delta = 0;
  95                                 if(other.m_bounds[i][0] < bounds[i][0]) delta += bounds[i][0] - other.m_bounds[i][0];
  96                                 if(other.m_bounds[i][1] > bounds[i][1]) delta += other.m_bounds[i][1] - bounds[i][1];
  97                                 sizes[i] += delta;
  98
  99                                 for(int i = 0; i < Dimensions; i ++) {
 100                                         volume += delta*sizes[i];
 101                                 }
 102                         }
 103                 }
 104
 105                 void cover(const Bound &other) {
 106                         for(int i = 0; i < Dimensions; i ++) {
 107                                 m_bounds[i][0] = std::min(m_bounds[i][0], other.m_bounds[i][0]);
 108                                 m_bounds[i][1] = std::max(m_bounds[i][1], other.m_bounds[i][1]);
 109                         }
 110                 }
 111         };
 112
 113         class Callback {
 114         public:
 115                 virtual ~Callback() {}
 116
 117                 /** Handle a search result.
 118                         @return True if the search should continue.
 119                 */
 120                 virtual bool handle(const Bound &bound, Value &value) = 0;
 121         };
 122 protected:
 123         class Node {
 124         private:
 125                 Bound m_bound;
 126                 int m_depth;
 127                 int m_branches;
 128                 Node *m_parent;
 129
 130                 union Branch {
 131                         Value value;
 132                         Node *child;
 133                 };
 134                 Branch m_branch[Maximum];
 135         public:
 136                 Node(int depth) : m_depth(depth) {}
 137
 138                 Bound &bound() { return m_bound; }
 139                 const Bound &bound() const { return m_bound; }
 140
 141                 int depth() const { return m_depth; }
 142                 bool isLeaf() const { return m_depth == 0; }
 143
 144                 bool isFull() const { return m_branches == Maximum; }
 145                 int branches() const { return m_branches; }
 146
 147                 void addBranch(const Bound &bound, Value value) {
 148                         m_branch[m_branches].item.bound = bound;
 149                         m_branch[m_branches++].item.value= value;
 150                 }
 151                 void addBranch(Node *child) {
 152
 153                 }
 154
 155                 Node *parent() const { return m_parent; }
 156                 void setParent(Node *parent) { m_parent = parent; }
 157         };
 158 private:
 159         Node *m_root;
 160 public:
 161         RTree();
 162         ~RTree();
 163
 164         void search(const Bound &bound, Callback *callback);
 165         void insert(const Bound &bound, const Value &value);
 166 private:
 167         bool search(Node *node, const Bound &bound, Callback *callback);
 168         Node *split(Node *node, Node *toInsert);
 169 };
 170
 171 RTreeTemplate
 172 RTreeScope::RTree() {
 173         m_root = NULL;
 174 }
 175
 176 RTreeTemplate
 177 RTreeScope::~RTree() {
 178
 179 }
 180
 181 RTreeTemplate
 182 void RTreeScope::search(const RTreeScope::Bound &bound, RTreeScope::Callback *callback) {
 183         search(m_root, bound, callback);
 184 }
 185
 186 RTreeTemplate
 187 void RTreeScope::insert(const RTreeScope::Bound &bound, const Value &value) {
 188         Node *toInsert;
 189         AesalonPoolAlloc(Node, toInsert, Node(bound, value, NULL));
 190
 191
 192 }
 193
 194 RTreeTemplate
 195 bool RTreeScope::search(RTreeScope::Node *node, const RTreeScope::Bound &bound, RTreeScope::Callback *callback) {
 196         if(node == NULL) return;
 197
 198         Message(Debug, "**** Beginning search.");
 199
 200         Node *n = node;
 201         while(n != NULL) {
 202                 Message(Debug, "Searching node . . .");
 203                 if(bound.overlaps(n->bound())) {
 204                         Message(Debug, "\tBound overlaps!");
 205                         if(node->isLeaf()) {
 206                                 if(!callback->handle(n->bound(), n->value())) return false;
 207                         }
 208                         else {
 209                                 if(!search(n, bound, callback)) return false;
 210                         }
 211                 }
 212                 n = n->next();
 213         }
 214         return true;
 215 }
 216
 217 RTreeTemplate
 218 typename RTreeScope::Node *RTreeScope::split(RTreeScope::Node *node, RTreeScope::Node *toInsert) {
 219         Node *s;
 220         AesalonPoolAlloc(Node, s, Node(node->depth(), NULL));
 221
 222
 223         Message(Fatal, "Splitting NYI.");
 224
 225         toInsert = toInsert;
 226
 227         return s;
 228 }
 229
 230 } // namespace Storage
 231
 232 #endif