Adds an RTree data structure to gfx/geometry

ui/gfx/geometry/r_tree.h

+// Copyright (c) 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.
+
+#ifndef UI_GFX_GEOMETRY_R_TREE_H_
+#define UI_GFX_GEOMETRY_R_TREE_H_
+
+#include <list>
+#include <map>
+#include <set>
+#include <vector>
+
+#include "base/containers/linked_list.h"
+#include "base/macros.h"
+#include "ui/gfx/geometry/rect.h"
+#include "ui/gfx/gfx_export.h"
+
+namespace gfx {
+
+// Defines a heirarchical 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
+class GFX_EXPORT RTree {
+ public:
+  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, this rect will not actually be inserted. Duplicate keys
+  // overwrite old entries.
+  void Insert(const Rect& rect, void* key);
+
+  // If present, remove the supplied key from the tree.
+  void Remove(void* key);
+
+  // Fills a supplied list matches_out with all keys having bounding rects
+  // intersecting query_rect.
+  void Query(const Rect& query_rect, std::set<void*>* matches_out) const;

[piman, 2014/04/21 23:59:31]

Why returning a set here?
Is seems like returning a vector should be more efficient. At the very least, a
hash_set should be strictly more efficient (since we don't care about ordering
between keys).

[luken, 2014/04/28 01:33:34]

The hashing containers need to be able to hash their key, and complain when
given a void*. There's even a comment at the top of base::hash_table to that
effect. I want something with better than linear membership query, so a std::set
seemed the best compromise.

[piman, 2014/04/28 18:24:28]

hash_set gives you O(1) (much better than linear).

You just have to add a hash function (cast to intptr_t, use the int hash
function).
Or, you could use intptr_t as the key since you don't actually care about it
being a pointer.

[luken, 2014/04/29 21:01:04]

Done.

+
+  // Removes all objects from the tree.
+  void Clear();
+
+  // Validates the internal state of the tree and returns false should there be
+  // any problem.
+  bool Validate() const;
+
+ private:
+  // Private data structure class for storing internal nodes or leaves with keys
+  // of R-Trees. Note that "leaf" nodes can still have children, the children
+  // will all be Nodes with non-NULL record pointers.
+  class Node : public base::LinkNode<Node> {
+   public:
+    // Level counts from -1 for "record" Nodes, that is Nodes that wrap key
+    // values, to 0 for leaf Nodes, that is Nodes that only have record
+    // children, up to the root Node, which has level equal to the height of the
+    // tree.
+    Node(int level);

[piman, 2014/04/21 23:59:31]

nit: explicit

[luken, 2014/04/28 01:33:34]

Done.

+
+    // Builds a new record Node.
+    Node(const Rect& rect, void* key);
+
+    virtual ~Node();
+
+    // Deletes all children and any attached record.
+    void Clear();
+
+    // Recursive call to build a list of rects that intersect the query_rect.
+    void Query(const Rect& query_rect, std::set<void*>* matches_out) const;

[piman, 2014/04/21 23:59:31]

hash_set?

[luken, 2014/04/28 01:33:34]

Not on void*. See above.

+
+    // Recompute our bounds by taking the union of all children rects. Will then
+    // call RecomputeBounds() on our parent for recursive bounds recalculation
+    // up to the root.
+    void RecomputeBounds();
+
+    // Removes number_to_remove nodes from this Node, and appends them to the
+    // supplied list. Does not repair bounds upon completion.
+    void RemoveNodesForReinsert(size_t number_to_remove,
+                                std::list<Node*>* nodes);
+
+    // Given a pointer to a child node within this Node, remove it from our
+    // list. If that child had any children, append them to the supplied orphan
+    // list. Returns the new count of this node after removal. Does not
+    // recompute bounds, as this node itself may be removed if it now has too
+    // few children.
+    size_t RemoveChild(Node* child_node, std::list<Node*>* orphans);
+
+    // Does what it says on the tin. Returns NULL if no children. Does not
+    // recompute bounds.
+    Node* RemoveAndReturnFirstChild();
+
+    // Given a node, returns the best fit node for insertion of that node at
+    // the nodes level().
+    Node* ChooseSubtree(Node* node);
+
+    // Adds the provided node to this Node. Returns the new count of records
+    // stored in the Node. Will recompute the bounds of this node after
+    // addition.
+    size_t AddNode(Node* node);
+
+    // Returns a sibling to this Node with at least min_children and no greater
+    // than max_children of this Node's children assigned to it, and having the
+    // same parent. Bounds will be valid on both Nodes after this call.
+    Node* Split(size_t min_children, size_t max_children);
+
+    // For record nodes only, to support re-insert, allows setting the rect.
+    void SetRect(const Rect& rect);
+
+    // Returns a pointer to the parent of this Node, or NULL if no parent.
+    Node* parent() const;

[piman, 2014/04/21 23:59:31]

nit: inline

[luken, 2014/04/28 01:33:34]

Done.

+
+    // 0 level() would mean that this Node is a leaf. 1 would mean that this
+    // Node has children that are leaves. Calling level() on root_ returns the
+    // height of the tree - 1. A level of -1 means that this is a Record node.
+    int level() const;

[piman, 2014/04/21 23:59:31]

nit: inline

[luken, 2014/04/28 01:33:34]

Done.

+
+    const Rect& rect() const;

[piman, 2014/04/21 23:59:31]

nit: inline

[luken, 2014/04/28 01:33:34]

Done.

+
+    size_t count() const;

[piman, 2014/04/21 23:59:31]

nit: inline

[luken, 2014/04/28 01:33:34]

Done.

+
+    bool Validate(size_t min_children, size_t max_children) const;
+
+   private:
+    // Returns all records stored in this node and its children.
+    void GetAllValues(std::set<void*>* matches_out) const;

[piman, 2014/04/21 23:59:31]

hash_set?

[luken, 2014/04/28 01:33:34]

Not on void*. See above.

+
+    // Returns the increase in area of bounds if bounds were to be expanded to
+    // contain rect.
+    static int AreaChangeToAdd(const Rect& bounds, const Rect& rect);
+
+    // Used for sorting Nodes along vertical and horizontal axes
+    static bool CompareVertical(Node* a, Node* b);
+
+    static bool CompareHorizontal(Node* a, Node* b);
+
+    static bool CompareCenterDistanceFromParent(Node* a, Node* b);
+
+    // Used by SplitNode to calculate optimal index of split, after determening
+    // along which axis to sort and split the children rectangles.
+    size_t CalculateOptimalSplitIndex(size_t min_children,
+                                      size_t max_children,
+                                      const std::vector<Rect>* low_bounds,
+                                      const std::vector<Rect>* high_bounds);
+
+    // Bounds recomputation without calling parents to do the same.
+    void RecomputeBoundsNoParents();
+
+    // This Node's bounding rectangle.
+    Rect rect_;
+
+    // The height of the node in the tree, counting from -1 at the record node
+    // to 0 at the leaf up to the root node which has level equal to the height
+    // of the tree.
+    int level_;
+
+    // A linked list of all of our children Nodes.
+    base::LinkedList<Node> children_;

[piman, 2014/04/21 23:59:31]

What's the tradeoff here vs a std::vector? We expect the structure to be fairy
static, don't we? Shouldn't a std::vector be more efficient?

[piman, 2014/04/21 23:59:31]

Also, it'd be nice to use the scoped types (ScopedVector? scoped_ptr?
linked_ptr?) to not have to manage memory manually.

[luken, 2014/04/28 01:33:34]

Done.

[luken, 2014/04/28 01:33:34]

Done.

+
+    // The number of Nodes within children_, as this is not countable in
+    // constant time.
+    size_t count_;
+
+    // A pointer to our parent Node in the RTree. The root node will have a NULL
+    // value for parent_.
+    Node* parent_;
+
+    // If this is a record Node, then key_ will be non-NULL and will contain the
+    // key data. Otherwise, NULL.
+    void* key_;
+
+    DISALLOW_COPY_AND_ASSIGN(Node);
+  };
+
+  // Private Insert to support re-insertion of Nodes based on the strategies
+  // outlined in Beckmann et al.
+  void Insert(Node* node, int* highset_reinsert_level);

[piman, 2014/04/21 23:59:31]

nit: no overloading. InsertNode?

[luken, 2014/04/28 01:33:34]

Done.

+  // Private Remove to support removal of nodes for tree without deletion.
+  void Remove(Node* node);

[piman, 2014/04/21 23:59:31]

nit: no overloading. RemoveNode?

[luken, 2014/04/28 01:33:34]

Done.

+
+  // A pointer to the root node in the RTree, or NULL if the tree is empty.
+  Node* root_;
+
+  // The parameters used to define the shape of the RTree.
+  size_t min_children_;
+  size_t max_children_;
+
+  // A map of supplied keys to their Node representation within the RTree, for
+  // efficient retrieval of keys without requiring a bounding rect.
+  std::map<void*, Node*> record_map_;

[piman, 2014/04/21 23:59:31]

Why not using a hash_map here? it should be more efficient generally.

[luken, 2014/04/28 01:33:34]

Because I don't know a good way to hash void*.

+
+  DISALLOW_COPY_AND_ASSIGN(RTree);
+};
+
+}  // namespace gfx
+
+#endif  // UI_GFX_GEOMETRY_R_TREE_H_