ui/gfx/geometry/r_tree.h

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // Defines a hierarchical bounding rectangle data structure for Rect objects,
   6 // associated with a generic unique key K for efficient spatial queries. The
   7 // R*-tree algorithm is used to build the trees. Based on the papers:
   8 //
   9 // A Guttman 'R-trees:  a dynamic index structure for spatial searching', Proc
  10 // ACM SIGMOD Int Conf on Management of Data, 47-57, 1984
  11 //
  12 // N Beckmann, H-P Kriegel, R Schneider, B Seeger 'The R*-tree: an efficient and
  13 // robust access method for points and rectangles', Proc ACM SIGMOD Int Conf on
  14 // Management of Data, 322-331, 1990
  15
  16 #ifndef UI_GFX_GEOMETRY_R_TREE_H_
  17 #define UI_GFX_GEOMETRY_R_TREE_H_
  18
  19 #include "r_tree_base.h"
  20
  21 namespace gfx {
  22
  23 template <typename Key>
  24 class RTree : public RTreeBase {
  25  public:
  26   typedef base::hash_set<Key> Matches;
  27
  28   // RTrees organize pairs of keys and rectangles in a hierarchical bounding
  29   // box structure. This allows for queries of the tree within logarithmic time.
  30   // |min_children| and |max_children| allows for adjustment of the average size
  31   // of the nodes within RTree, which adjusts the base of the logarithm in the
  32   // algorithm runtime. Some parts of insertion and deletion are polynomial
  33   // in the size of the individual node, so the trade-off with larger nodes is
  34   // potentially faster queries but slower insertions and deletions. Generally
  35   // it is worth considering how much overlap between rectangles of different
  36   // keys will occur in the tree, and trying to set |max_children| as a
  37   // reasonable upper bound to the number of overlapping rectangles expected.
  38   // Then |min_children| can bet set to a quantity slightly less than half of
  39   // that.
  40   RTree(size_t min_children, size_t max_children);
  41   ~RTree();
  42
  43   // Insert a new rect into the tree, associated with provided key. Note that if
  44   // |rect| is empty, the |key| will not actually be inserted. Duplicate keys
  45   // overwrite old entries.
  46   void Insert(const Rect& rect, Key key);
  47
  48   // If present, remove the supplied |key| from the tree.
  49   void Remove(Key key);
  50
  51   // Fills |matches_out| with all keys having bounding rects intersecting
  52   // |query_rect|.
  53   void AppendIntersectingRecords(const Rect& query_rect,
  54                                  Matches* matches_out) const;
  55
  56   void Clear();
  57
  58  private:
  59   friend class RTreeTest;
  60   friend class RTreeNodeTest;
  61
  62   class Record : public RecordBase {
  63    public:
  64     Record(const Rect& rect, const Key& key);
  65     virtual ~Record();
  66     const Key& key() const { return key_; }
  67
  68    private:
  69     Key key_;
  70
  71     DISALLOW_COPY_AND_ASSIGN(Record);
  72   };
  73
  74   // A map of supplied keys to their Node representation within the RTree, for
  75   // efficient retrieval of keys without requiring a bounding rect.
  76   typedef base::hash_map<Key, Record*> RecordMap;
  77   RecordMap record_map_;
  78
  79   DISALLOW_COPY_AND_ASSIGN(RTree);
  80 };
  81
  82 template <typename Key>
  83 RTree<Key>::RTree(size_t min_children, size_t max_children)
  84     : RTreeBase(min_children, max_children) {
  85 }
  86
  87 template <typename Key>
  88 RTree<Key>::~RTree() {
  89 }
  90
  91 template <typename Key>
  92 void RTree<Key>::Insert(const Rect& rect, Key key) {
  93   scoped_ptr<NodeBase> record;
  94   // Check if this key is already present in the tree.
  95   typename RecordMap::iterator it(record_map_.find(key));
  96
  97   if (it != record_map_.end()) {
  98     // We will re-use this node structure, regardless of re-insert or return.
  99     Record* existing_record = it->second;
 100     // If the new rect and the current rect are identical we can skip the rest
 101     // of Insert() as nothing has changed.
 102     if (existing_record->rect() == rect)
 103       return;
 104
 105     // Remove the node from the tree in its current position.
 106     record = RemoveNode(existing_record);
 107
 108     PruneRootIfNecessary();
 109
 110     // If we are replacing this key with an empty rectangle we just remove the
 111     // old node from the list and return, thus preventing insertion of empty
 112     // rectangles into our spatial database.
 113     if (rect.IsEmpty()) {
 114       record_map_.erase(it);
 115       return;
 116     }
 117
 118     // Reset the rectangle to the new value.
 119     record->set_rect(rect);
 120   } else {
 121     if (rect.IsEmpty())
 122       return;
 123
 124     record.reset(new Record(rect, key));
 125     record_map_.insert(std::make_pair(key, static_cast<Record*>(record.get())));
 126   }
 127
 128   int highest_reinsert_level = -1;
 129   InsertNode(record.Pass(), &highest_reinsert_level);
 130 }
 131
 132 template <typename Key>
 133 void RTree<Key>::Clear() {
 134   record_map_.clear();
 135   ResetRoot();
 136 }
 137
 138 template <typename Key>
 139 void RTree<Key>::Remove(Key key) {
 140   // Search the map for the leaf parent that has the provided record.
 141   typename RecordMap::iterator it = record_map_.find(key);
 142   if (it == record_map_.end())
 143     return;
 144
 145   Record* record = it->second;
 146   record_map_.erase(it);
 147   RemoveNode(record);
 148
 149   // Lastly check the root. If it has only one non-leaf child, delete it and
 150   // replace it with its child.
 151   PruneRootIfNecessary();
 152 }
 153
 154 template <typename Key>
 155 void RTree<Key>::AppendIntersectingRecords(
 156       const Rect& query_rect, Matches* matches_out) const {
 157   RTreeBase::Records matching_records;
 158   root()->AppendIntersectingRecords(query_rect, &matching_records);
 159   for (RTreeBase::Records::const_iterator it = matching_records.begin();
 160        it != matching_records.end();
 161        ++it) {
 162     const Record* record = static_cast<const Record*>(*it);
 163     matches_out->insert(record->key());
 164   }
 165 }
 166
 167
 168 // RTree::Record --------------------------------------------------------------
 169
 170 template <typename Key>
 171 RTree<Key>::Record::Record(const Rect& rect, const Key& key)
 172     : RecordBase(rect),
 173       key_(key) {
 174 }
 175
 176 template <typename Key>
 177 RTree<Key>::Record::~Record() {
 178 }
 179
 180 }  // namespace gfx
 181
 182 #endif  // UI_GFX_GEOMETRY_R_TREE_H_