diff options
Diffstat (limited to 'chromium/ui/gfx/geometry/r_tree.h')
| -rw-r--r-- | chromium/ui/gfx/geometry/r_tree.h | 182 |
1 files changed, 182 insertions, 0 deletions
diff --git a/chromium/ui/gfx/geometry/r_tree.h b/chromium/ui/gfx/geometry/r_tree.h new file mode 100644 index 00000000000..53fd5c9f900 --- /dev/null +++ b/chromium/ui/gfx/geometry/r_tree.h @@ -0,0 +1,182 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +// Defines a hierarchical bounding rectangle data structure for Rect objects, +// associated with a generic unique key K for efficient spatial queries. The +// R*-tree algorithm is used to build the trees. Based on the papers: +// +// A Guttman 'R-trees: a dynamic index structure for spatial searching', Proc +// ACM SIGMOD Int Conf on Management of Data, 47-57, 1984 +// +// N Beckmann, H-P Kriegel, R Schneider, B Seeger 'The R*-tree: an efficient and +// robust access method for points and rectangles', Proc ACM SIGMOD Int Conf on +// Management of Data, 322-331, 1990 + +#ifndef UI_GFX_GEOMETRY_R_TREE_H_ +#define UI_GFX_GEOMETRY_R_TREE_H_ + +#include "r_tree_base.h" + +namespace gfx { + +template <typename Key> +class RTree : public RTreeBase { + public: + typedef base::hash_set<Key> Matches; + + // RTrees organize pairs of keys and rectangles in a hierarchical bounding + // box structure. This allows for queries of the tree within logarithmic time. + // |min_children| and |max_children| allows for adjustment of the average size + // of the nodes within RTree, which adjusts the base of the logarithm in the + // algorithm runtime. Some parts of insertion and deletion are polynomial + // in the size of the individual node, so the trade-off with larger nodes is + // potentially faster queries but slower insertions and deletions. Generally + // it is worth considering how much overlap between rectangles of different + // keys will occur in the tree, and trying to set |max_children| as a + // reasonable upper bound to the number of overlapping rectangles expected. + // Then |min_children| can bet set to a quantity slightly less than half of + // that. + RTree(size_t min_children, size_t max_children); + ~RTree(); + + // Insert a new rect into the tree, associated with provided key. Note that if + // |rect| is empty, the |key| will not actually be inserted. Duplicate keys + // overwrite old entries. + void Insert(const Rect& rect, Key key); + + // If present, remove the supplied |key| from the tree. + void Remove(Key key); + + // Fills |matches_out| with all keys having bounding rects intersecting + // |query_rect|. + void AppendIntersectingRecords(const Rect& query_rect, + Matches* matches_out) const; + + void Clear(); + + private: + friend class RTreeTest; + friend class RTreeNodeTest; + + class Record : public RecordBase { + public: + Record(const Rect& rect, const Key& key); + virtual ~Record(); + const Key& key() const { return key_; } + + private: + Key key_; + + DISALLOW_COPY_AND_ASSIGN(Record); + }; + + // A map of supplied keys to their Node representation within the RTree, for + // efficient retrieval of keys without requiring a bounding rect. + typedef base::hash_map<Key, Record*> RecordMap; + RecordMap record_map_; + + DISALLOW_COPY_AND_ASSIGN(RTree); +}; + +template <typename Key> +RTree<Key>::RTree(size_t min_children, size_t max_children) + : RTreeBase(min_children, max_children) { +} + +template <typename Key> +RTree<Key>::~RTree() { +} + +template <typename Key> +void RTree<Key>::Insert(const Rect& rect, Key key) { + scoped_ptr<NodeBase> record; + // Check if this key is already present in the tree. + typename RecordMap::iterator it(record_map_.find(key)); + + if (it != record_map_.end()) { + // We will re-use this node structure, regardless of re-insert or return. + Record* existing_record = it->second; + // If the new rect and the current rect are identical we can skip the rest + // of Insert() as nothing has changed. + if (existing_record->rect() == rect) + return; + + // Remove the node from the tree in its current position. + record = RemoveNode(existing_record); + + PruneRootIfNecessary(); + + // If we are replacing this key with an empty rectangle we just remove the + // old node from the list and return, thus preventing insertion of empty + // rectangles into our spatial database. + if (rect.IsEmpty()) { + record_map_.erase(it); + return; + } + + // Reset the rectangle to the new value. + record->set_rect(rect); + } else { + if (rect.IsEmpty()) + return; + + record.reset(new Record(rect, key)); + record_map_.insert(std::make_pair(key, static_cast<Record*>(record.get()))); + } + + int highest_reinsert_level = -1; + InsertNode(record.Pass(), &highest_reinsert_level); +} + +template <typename Key> +void RTree<Key>::Clear() { + record_map_.clear(); + ResetRoot(); +} + +template <typename Key> +void RTree<Key>::Remove(Key key) { + // Search the map for the leaf parent that has the provided record. + typename RecordMap::iterator it = record_map_.find(key); + if (it == record_map_.end()) + return; + + Record* record = it->second; + record_map_.erase(it); + RemoveNode(record); + + // Lastly check the root. If it has only one non-leaf child, delete it and + // replace it with its child. + PruneRootIfNecessary(); +} + +template <typename Key> +void RTree<Key>::AppendIntersectingRecords( + const Rect& query_rect, Matches* matches_out) const { + RTreeBase::Records matching_records; + root()->AppendIntersectingRecords(query_rect, &matching_records); + for (RTreeBase::Records::const_iterator it = matching_records.begin(); + it != matching_records.end(); + ++it) { + const Record* record = static_cast<const Record*>(*it); + matches_out->insert(record->key()); + } +} + + +// RTree::Record -------------------------------------------------------------- + +template <typename Key> +RTree<Key>::Record::Record(const Rect& rect, const Key& key) + : RecordBase(rect), + key_(key) { +} + +template <typename Key> +RTree<Key>::Record::~Record() { +} + +} // namespace gfx + +#endif // UI_GFX_GEOMETRY_R_TREE_H_ |