| OLD | NEW |
|---|
| (Empty) |
| 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 // Provides an implementation the parts of the RTree data structure that don't | |
| 6 // require knowledge of the generic key type. Don't use these objects directly, | |
| 7 // rather specialize the RTree<> object in r_tree.h. This file defines the | |
| 8 // internal objects of an RTree, namely Nodes (internal nodes of the tree) and | |
| 9 // Records, which hold (key, rectangle) pairs. | |
| 10 | |
| 11 #ifndef UI_GFX_GEOMETRY_R_TREE_BASE_H_ | |
| 12 #define UI_GFX_GEOMETRY_R_TREE_BASE_H_ | |
| 13 | |
| 14 #include <list> | |
| 15 #include <vector> | |
| 16 | |
| 17 #include "base/containers/hash_tables.h" | |
| 18 #include "base/macros.h" | |
| 19 #include "base/memory/scoped_ptr.h" | |
| 20 #include "base/memory/scoped_vector.h" | |
| 21 #include "ui/gfx/geometry/rect.h" | |
| 22 #include "ui/gfx/gfx_export.h" | |
| 23 | |
| 24 namespace gfx { | |
| 25 | |
| 26 class GFX_EXPORT RTreeBase { | |
| 27 protected: | |
| 28 class NodeBase; | |
| 29 class RecordBase; | |
| 30 | |
| 31 typedef std::vector<const RecordBase*> Records; | |
| 32 typedef ScopedVector<NodeBase> Nodes; | |
| 33 | |
| 34 RTreeBase(size_t min_children, size_t max_children); | |
| 35 ~RTreeBase(); | |
| 36 | |
| 37 // Protected data structure class for storing internal Nodes or leaves with | |
| 38 // Records. | |
| 39 class GFX_EXPORT NodeBase { | |
| 40 public: | |
| 41 virtual ~NodeBase(); | |
| 42 | |
| 43 // Appends to |records_out| the set of Records in this subtree with rects | |
| 44 // that intersect |query_rect|. Avoids clearing |records_out| so that it | |
| 45 // can be called recursively. | |
| 46 virtual void AppendIntersectingRecords(const Rect& query_rect, | |
| 47 Records* records_out) const = 0; | |
| 48 | |
| 49 // Returns all records stored in the subtree rooted at this node. Appends to | |
| 50 // |matches_out| without clearing. | |
| 51 virtual void AppendAllRecords(Records* records_out) const = 0; | |
| 52 | |
| 53 // Returns NULL if no children. Does not recompute bounds. | |
| 54 virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() = 0; | |
| 55 | |
| 56 // Returns -1 for Records, or the height of this subtree for Nodes. The | |
| 57 // height of a leaf Node (a Node containing only Records) is 0, a leaf's | |
| 58 // parent is 1, etc. Note that in an R*-Tree, all branches from the root | |
| 59 // Node will be the same height. | |
| 60 virtual int Level() const = 0; | |
| 61 | |
| 62 // Recomputes our bounds by taking the union of all child rects, then calls | |
| 63 // recursively on our parent so that ultimately all nodes up to the root | |
| 64 // recompute their bounds. | |
| 65 void RecomputeBoundsUpToRoot(); | |
| 66 | |
| 67 NodeBase* parent() { return parent_; } | |
| 68 const NodeBase* parent() const { return parent_; } | |
| 69 void set_parent(NodeBase* parent) { parent_ = parent; } | |
| 70 const Rect& rect() const { return rect_; } | |
| 71 void set_rect(const Rect& rect) { rect_ = rect; } | |
| 72 | |
| 73 protected: | |
| 74 NodeBase(const Rect& rect, NodeBase* parent); | |
| 75 | |
| 76 // Bounds recomputation without calling parents to do the same. | |
| 77 virtual void RecomputeLocalBounds(); | |
| 78 | |
| 79 private: | |
| 80 friend class RTreeTest; | |
| 81 friend class RTreeNodeTest; | |
| 82 | |
| 83 // This Node's bounding rectangle. | |
| 84 Rect rect_; | |
| 85 | |
| 86 // A weak pointer to our parent Node in the RTree. The root node will have a | |
| 87 // NULL value for |parent_|. | |
| 88 NodeBase* parent_; | |
| 89 | |
| 90 DISALLOW_COPY_AND_ASSIGN(NodeBase); | |
| 91 }; | |
| 92 | |
| 93 class GFX_EXPORT RecordBase : public NodeBase { | |
| 94 public: | |
| 95 explicit RecordBase(const Rect& rect); | |
| 96 virtual ~RecordBase(); | |
| 97 | |
| 98 virtual void AppendIntersectingRecords(const Rect& query_rect, | |
| 99 Records* records_out) const OVERRIDE; | |
| 100 virtual void AppendAllRecords(Records* records_out) const OVERRIDE; | |
| 101 virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE; | |
| 102 virtual int Level() const OVERRIDE; | |
| 103 | |
| 104 private: | |
| 105 friend class RTreeTest; | |
| 106 friend class RTreeNodeTest; | |
| 107 | |
| 108 DISALLOW_COPY_AND_ASSIGN(RecordBase); | |
| 109 }; | |
| 110 | |
| 111 class GFX_EXPORT Node : public NodeBase { | |
| 112 public: | |
| 113 // Constructs an empty Node with |level_| of 0. | |
| 114 Node(); | |
| 115 virtual ~Node(); | |
| 116 | |
| 117 virtual void AppendIntersectingRecords(const Rect& query_rect, | |
| 118 Records* records_out) const OVERRIDE; | |
| 119 virtual scoped_ptr<NodeBase> RemoveAndReturnLastChild() OVERRIDE; | |
| 120 virtual int Level() const OVERRIDE; | |
| 121 virtual void AppendAllRecords(Records* matches_out) const OVERRIDE; | |
| 122 | |
| 123 // Constructs a new Node that is the parent of this Node and already has | |
| 124 // this Node as its sole child. Valid to call only on root Nodes, meaning | |
| 125 // Nodes with |parent_| NULL. Note that ownership of this Node is | |
| 126 // transferred to the parent returned by this function. | |
| 127 scoped_ptr<Node> ConstructParent(); | |
| 128 | |
| 129 // Removes |number_to_remove| children from this Node, and appends them to | |
| 130 // the supplied list. Does not repair bounds upon completion. Nodes are | |
| 131 // selected in the manner suggested in the Beckmann et al. paper, which | |
| 132 // suggests that the children should be sorted by the distance from the | |
| 133 // center of their bounding rectangle to their parent's bounding rectangle, | |
| 134 // and then the n closest children should be removed for re-insertion. This | |
| 135 // removal occurs at most once on each level of the tree when overflowing | |
| 136 // nodes that have exceeded the maximum number of children during an Insert. | |
| 137 void RemoveNodesForReinsert(size_t number_to_remove, Nodes* nodes); | |
| 138 | |
| 139 // Given a pointer to a child node within this Node, removes it from our | |
| 140 // list. If that child had any children, appends them to the supplied orphan | |
| 141 // list. Returns the removed child. Does not recompute bounds, as the caller | |
| 142 // might subsequently remove this node as well, meaning the recomputation | |
| 143 // would be wasted work. | |
| 144 scoped_ptr<NodeBase> RemoveChild(NodeBase* child_node, Nodes* orphans); | |
| 145 | |
| 146 // Returns the best parent for insertion of the provided |node| as a child. | |
| 147 Node* ChooseSubtree(NodeBase* node); | |
| 148 | |
| 149 // Adds |node| as a child of this Node, and recomputes the bounds of this | |
| 150 // node after the addition of the child. Returns the new count of children | |
| 151 // stored in this Node. This node becomes the owner of |node|. | |
| 152 size_t AddChild(scoped_ptr<NodeBase> node); | |
| 153 | |
| 154 // Returns a sibling to this Node with at least min_children and no greater | |
| 155 // than max_children of this Node's children assigned to it, and having the | |
| 156 // same parent. Bounds will be valid on both Nodes after this call. | |
| 157 scoped_ptr<NodeBase> Split(size_t min_children, size_t max_children); | |
| 158 | |
| 159 size_t count() const { return children_.size(); } | |
| 160 const NodeBase* child(size_t i) const { return children_[i]; } | |
| 161 NodeBase* child(size_t i) { return children_[i]; } | |
| 162 | |
| 163 private: | |
| 164 typedef std::vector<Rect> Rects; | |
| 165 | |
| 166 explicit Node(int level); | |
| 167 | |
| 168 // Given two arrays of bounds rectangles as computed by BuildLowBounds() | |
| 169 // and BuildHighBounds(), returns the index of the element in those arrays | |
| 170 // along which a split of the arrays would result in a minimum amount of | |
| 171 // overlap (area of intersection) in the two groups. | |
| 172 static size_t ChooseSplitIndex(size_t start_index, | |
| 173 size_t end_index, | |
| 174 const Rects& low_bounds, | |
| 175 const Rects& high_bounds); | |
| 176 | |
| 177 // R*-Tree attempts to keep groups of rectangles that are roughly square | |
| 178 // in shape. It does this by comparing the "margins" of different bounding | |
| 179 // boxes, where margin is defined as the sum of the length of all four sides | |
| 180 // of a rectangle. For two rectangles of equal area, the one with the | |
| 181 // smallest margin will be the rectangle whose width and height differ the | |
| 182 // least. When splitting we decide to split along an axis chosen from the | |
| 183 // rectangles either sorted vertically or horizontally by finding the axis | |
| 184 // that would result in the smallest sum of margins between the two bounding | |
| 185 // boxes of the resulting split. Returns the smallest sum computed given the | |
| 186 // sorted bounding boxes and a range to look within. | |
| 187 static int SmallestMarginSum(size_t start_index, | |
| 188 size_t end_index, | |
| 189 const Rects& low_bounds, | |
| 190 const Rects& high_bounds); | |
| 191 | |
| 192 // Sorts nodes primarily by increasing y coordinates, and secondarily by | |
| 193 // increasing height. | |
| 194 static bool CompareVertical(const NodeBase* a, const NodeBase* b); | |
| 195 | |
| 196 // Sorts nodes primarily by increasing x coordinates, and secondarily by | |
| 197 // increasing width. | |
| 198 static bool CompareHorizontal(const NodeBase* a, const NodeBase* b); | |
| 199 | |
| 200 // Sorts nodes by the distance of the center of their rectangles to the | |
| 201 // center of their parent's rectangles. | |
| 202 static bool CompareCenterDistanceFromParent( | |
| 203 const NodeBase* a, const NodeBase* b); | |
| 204 | |
| 205 // Given two vectors of Nodes sorted by vertical or horizontal bounds, | |
| 206 // populates two vectors of Rectangles in which the ith element is the union | |
| 207 // of all bounding rectangles [0,i] in the associated sorted array of Nodes. | |
| 208 static void BuildLowBounds(const std::vector<NodeBase*>& vertical_sort, | |
| 209 const std::vector<NodeBase*>& horizontal_sort, | |
| 210 Rects* vertical_bounds, | |
| 211 Rects* horizontal_bounds); | |
| 212 | |
| 213 // Given two vectors of Nodes sorted by vertical or horizontal bounds, | |
| 214 // populates two vectors of Rectangles in which the ith element is the | |
| 215 // union of all bounding rectangles [i, count()) in the associated sorted | |
| 216 // array of Nodes. | |
| 217 static void BuildHighBounds(const std::vector<NodeBase*>& vertical_sort, | |
| 218 const std::vector<NodeBase*>& horizontal_sort, | |
| 219 Rects* vertical_bounds, | |
| 220 Rects* horizontal_bounds); | |
| 221 | |
| 222 virtual void RecomputeLocalBounds() OVERRIDE; | |
| 223 | |
| 224 // Returns the increase in overlap value, as defined in Beckmann et al. as | |
| 225 // the sum of the areas of the intersection of all child rectangles | |
| 226 // (excepting the candidate child) with the argument rectangle. Here the | |
| 227 // |candidate_node| is one of our |children_|, and |expanded_rect| is the | |
| 228 // already-computed union of the candidate's rect and |rect|. | |
| 229 int OverlapIncreaseToAdd(const Rect& rect, | |
| 230 const NodeBase* candidate_node, | |
| 231 const Rect& expanded_rect) const; | |
| 232 | |
| 233 // Returns a new node containing children [split_index, count()) within | |
| 234 // |sorted_children|. Children before |split_index| remain with |this|. | |
| 235 scoped_ptr<NodeBase> DivideChildren( | |
| 236 const Rects& low_bounds, | |
| 237 const Rects& high_bounds, | |
| 238 const std::vector<NodeBase*>& sorted_children, | |
| 239 size_t split_index); | |
| 240 | |
| 241 // Returns a pointer to the child node that will result in the least overlap | |
| 242 // increase with the addition of node_rect, or NULL if there's a tie found. | |
| 243 // Requires a precomputed vector of expanded rectangles where the ith | |
| 244 // rectangle in the vector is the union of |children_|[i] and node_rect. | |
| 245 // Overlap is defined in Beckmann et al. as the sum of the areas of | |
| 246 // intersection of all child rectangles with the |node_rect| argument | |
| 247 // rectangle. This heuristic attempts to choose the node for which adding | |
| 248 // the new rectangle to their bounding box will result in the least overlap | |
| 249 // with the other rectangles, thus trying to preserve the usefulness of the | |
| 250 // bounding rectangle by keeping it from covering too much redundant area. | |
| 251 Node* LeastOverlapIncrease(const Rect& node_rect, | |
| 252 const Rects& expanded_rects); | |
| 253 | |
| 254 // Returns a pointer to the child node that will result in the least area | |
| 255 // enlargement if the argument node rectangle were to be added to that | |
| 256 // node's bounding box. Requires a precomputed vector of expanded rectangles | |
| 257 // where the ith rectangle in the vector is the union of children_[i] and | |
| 258 // |node_rect|. | |
| 259 Node* LeastAreaEnlargement(const Rect& node_rect, | |
| 260 const Rects& expanded_rects); | |
| 261 | |
| 262 const int level_; | |
| 263 | |
| 264 Nodes children_; | |
| 265 | |
| 266 friend class RTreeTest; | |
| 267 friend class RTreeNodeTest; | |
| 268 | |
| 269 DISALLOW_COPY_AND_ASSIGN(Node); | |
| 270 }; | |
| 271 | |
| 272 // Inserts |node| into the tree. The |highest_reinsert_level| supports | |
| 273 // re-insertion as described by Beckmann et al. As Node overflows progagate | |
| 274 // up the tree the algorithm performs a reinsertion of the overflow Nodes | |
| 275 // (instead of a split) at most once per level of the tree. A starting value | |
| 276 // of -1 for |highest_reinsert_level| means that reinserts are permitted for | |
| 277 // every level of the tree. This should always be set to -1 except by | |
| 278 // recursive calls from within InsertNode(). | |
| 279 void InsertNode(scoped_ptr<NodeBase> node, int* highest_reinsert_level); | |
| 280 | |
| 281 // Removes |node| from the tree without deleting it. | |
| 282 scoped_ptr<NodeBase> RemoveNode(NodeBase* node); | |
| 283 | |
| 284 // If |root_| has only one child, deletes the |root_| Node and replaces it | |
| 285 // with its only descendant child. Otherwise does nothing. | |
| 286 void PruneRootIfNecessary(); | |
| 287 | |
| 288 // Deletes the entire current tree and replaces it with an empty Node. | |
| 289 void ResetRoot(); | |
| 290 | |
| 291 const Node* root() const { return root_.get(); } | |
| 292 | |
| 293 private: | |
| 294 friend class RTreeTest; | |
| 295 friend class RTreeNodeTest; | |
| 296 | |
| 297 // A pointer to the root node in the RTree. | |
| 298 scoped_ptr<Node> root_; | |
| 299 | |
| 300 // The parameters used to define the shape of the RTree. | |
| 301 const size_t min_children_; | |
| 302 const size_t max_children_; | |
| 303 | |
| 304 DISALLOW_COPY_AND_ASSIGN(RTreeBase); | |
| 305 }; | |
| 306 | |
| 307 } // namespace gfx | |
| 308 | |
| 309 #endif // UI_GFX_GEOMETRY_R_TREE_BASE_H_ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 338833004:
Revert 276827 "readability review for luken" (Closed)
Base URL: svn://svn.chromium.org/chrome/