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
21namespace gfx {
22
23template <typename Key>
24class 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
82template <typename Key>
83RTree<Key>::RTree(size_t min_children, size_t max_children)
84    : RTreeBase(min_children, max_children) {
85}
86
87template <typename Key>
88RTree<Key>::~RTree() {
89}
90
91template <typename Key>
92void 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
132template <typename Key>
133void RTree<Key>::Clear() {
134  record_map_.clear();
135  ResetRoot();
136}
137
138template <typename Key>
139void 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
154template <typename Key>
155void 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
170template <typename Key>
171RTree<Key>::Record::Record(const Rect& rect, const Key& key)
172    : RecordBase(rect),
173      key_(key) {
174}
175
176template <typename Key>
177RTree<Key>::Record::~Record() {
178}
179
180}  // namespace gfx
181
182#endif  // UI_GFX_GEOMETRY_R_TREE_H_
183