| 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 #include "ui/gfx/geometry/r_tree_base.h" | |
| 6 | |
| 7 #include <algorithm> | |
| 8 | |
| 9 #include "base/logging.h" | |
| 10 | |
| 11 | |
| 12 // Helpers -------------------------------------------------------------------- | |
| 13 | |
| 14 namespace { | |
| 15 | |
| 16 // Returns a Vector2d to allow us to do arithmetic on the result such as | |
| 17 // computing distances between centers. | |
| 18 gfx::Vector2d CenterOfRect(const gfx::Rect& rect) { | |
| 19 return rect.OffsetFromOrigin() + | |
| 20 gfx::Vector2d(rect.width() / 2, rect.height() / 2); | |
| 21 } | |
| 22 | |
| 23 } | |
| 24 | |
| 25 namespace gfx { | |
| 26 | |
| 27 | |
| 28 // RTreeBase::NodeBase -------------------------------------------------------- | |
| 29 | |
| 30 RTreeBase::NodeBase::~NodeBase() { | |
| 31 } | |
| 32 | |
| 33 void RTreeBase::NodeBase::RecomputeBoundsUpToRoot() { | |
| 34 RecomputeLocalBounds(); | |
| 35 if (parent_) | |
| 36 parent_->RecomputeBoundsUpToRoot(); | |
| 37 } | |
| 38 | |
| 39 RTreeBase::NodeBase::NodeBase(const Rect& rect, NodeBase* parent) | |
| 40 : rect_(rect), | |
| 41 parent_(parent) { | |
| 42 } | |
| 43 | |
| 44 void RTreeBase::NodeBase::RecomputeLocalBounds() { | |
| 45 } | |
| 46 | |
| 47 // RTreeBase::RecordBase ------------------------------------------------------ | |
| 48 | |
| 49 RTreeBase::RecordBase::RecordBase(const Rect& rect) : NodeBase(rect, NULL) { | |
| 50 } | |
| 51 | |
| 52 RTreeBase::RecordBase::~RecordBase() { | |
| 53 } | |
| 54 | |
| 55 void RTreeBase::RecordBase::AppendIntersectingRecords( | |
| 56 const Rect& query_rect, Records* matches_out) const { | |
| 57 if (rect().Intersects(query_rect)) | |
| 58 matches_out->push_back(this); | |
| 59 } | |
| 60 | |
| 61 void RTreeBase::RecordBase::AppendAllRecords(Records* matches_out) const { | |
| 62 matches_out->push_back(this); | |
| 63 } | |
| 64 | |
| 65 scoped_ptr<RTreeBase::NodeBase> | |
| 66 RTreeBase::RecordBase::RemoveAndReturnLastChild() { | |
| 67 return scoped_ptr<NodeBase>(); | |
| 68 } | |
| 69 | |
| 70 int RTreeBase::RecordBase::Level() const { | |
| 71 return -1; | |
| 72 } | |
| 73 | |
| 74 | |
| 75 // RTreeBase::Node ------------------------------------------------------------ | |
| 76 | |
| 77 RTreeBase::Node::Node() : NodeBase(Rect(), NULL), level_(0) { | |
| 78 } | |
| 79 | |
| 80 RTreeBase::Node::~Node() { | |
| 81 } | |
| 82 | |
| 83 scoped_ptr<RTreeBase::Node> RTreeBase::Node::ConstructParent() { | |
| 84 DCHECK(!parent()); | |
| 85 scoped_ptr<Node> new_parent(new Node(level_ + 1)); | |
| 86 new_parent->AddChild(scoped_ptr<NodeBase>(this)); | |
| 87 return new_parent.Pass(); | |
| 88 } | |
| 89 | |
| 90 void RTreeBase::Node::AppendIntersectingRecords( | |
| 91 const Rect& query_rect, Records* matches_out) const { | |
| 92 // Check own bounding box for intersection, can cull all children if no | |
| 93 // intersection. | |
| 94 if (!rect().Intersects(query_rect)) | |
| 95 return; | |
| 96 | |
| 97 // Conversely if we are completely contained within the query rect we can | |
| 98 // confidently skip all bounds checks for ourselves and all our children. | |
| 99 if (query_rect.Contains(rect())) { | |
| 100 AppendAllRecords(matches_out); | |
| 101 return; | |
| 102 } | |
| 103 | |
| 104 // We intersect the query rect but we are not are not contained within it. | |
| 105 // We must query each of our children in turn. | |
| 106 for (Nodes::const_iterator i = children_.begin(); i != children_.end(); ++i) | |
| 107 (*i)->AppendIntersectingRecords(query_rect, matches_out); | |
| 108 } | |
| 109 | |
| 110 void RTreeBase::Node::AppendAllRecords(Records* matches_out) const { | |
| 111 for (Nodes::const_iterator i = children_.begin(); i != children_.end(); ++i) | |
| 112 (*i)->AppendAllRecords(matches_out); | |
| 113 } | |
| 114 | |
| 115 void RTreeBase::Node::RemoveNodesForReinsert(size_t number_to_remove, | |
| 116 Nodes* nodes) { | |
| 117 DCHECK_LE(number_to_remove, children_.size()); | |
| 118 | |
| 119 std::partial_sort(children_.begin(), | |
| 120 children_.begin() + number_to_remove, | |
| 121 children_.end(), | |
| 122 &RTreeBase::Node::CompareCenterDistanceFromParent); | |
| 123 | |
| 124 // Move the lowest-distance nodes to the returned vector. | |
| 125 nodes->insert( | |
| 126 nodes->end(), children_.begin(), children_.begin() + number_to_remove); | |
| 127 children_.weak_erase(children_.begin(), children_.begin() + number_to_remove); | |
| 128 } | |
| 129 | |
| 130 scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::RemoveChild( | |
| 131 NodeBase* child_node, Nodes* orphans) { | |
| 132 DCHECK_EQ(this, child_node->parent()); | |
| 133 | |
| 134 scoped_ptr<NodeBase> orphan(child_node->RemoveAndReturnLastChild()); | |
| 135 while (orphan) { | |
| 136 orphans->push_back(orphan.release()); | |
| 137 orphan = child_node->RemoveAndReturnLastChild(); | |
| 138 } | |
| 139 | |
| 140 Nodes::iterator i = std::find(children_.begin(), children_.end(), child_node); | |
| 141 DCHECK(i != children_.end()); | |
| 142 children_.weak_erase(i); | |
| 143 | |
| 144 return scoped_ptr<NodeBase>(child_node); | |
| 145 } | |
| 146 | |
| 147 scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::RemoveAndReturnLastChild() { | |
| 148 if (children_.empty()) | |
| 149 return scoped_ptr<NodeBase>(); | |
| 150 | |
| 151 scoped_ptr<NodeBase> last_child(children_.back()); | |
| 152 children_.weak_erase(children_.end() - 1); | |
| 153 last_child->set_parent(NULL); | |
| 154 return last_child.Pass(); | |
| 155 } | |
| 156 | |
| 157 RTreeBase::Node* RTreeBase::Node::ChooseSubtree(NodeBase* node) { | |
| 158 DCHECK(node); | |
| 159 // Should never be called on a node at equal or lower level in the tree than | |
| 160 // the node to insert. | |
| 161 DCHECK_GT(level_, node->Level()); | |
| 162 | |
| 163 // If we are a parent of nodes on the provided node level, we are done. | |
| 164 if (level_ == node->Level() + 1) | |
| 165 return this; | |
| 166 | |
| 167 // Precompute a vector of expanded rects, used by both LeastOverlapIncrease | |
| 168 // and LeastAreaEnlargement. | |
| 169 Rects expanded_rects; | |
| 170 expanded_rects.reserve(children_.size()); | |
| 171 for (Nodes::iterator i = children_.begin(); i != children_.end(); ++i) | |
| 172 expanded_rects.push_back(UnionRects(node->rect(), (*i)->rect())); | |
| 173 | |
| 174 Node* best_candidate = NULL; | |
| 175 // For parents of leaf nodes, we pick the node that will cause the least | |
| 176 // increase in overlap by the addition of this new node. This may detect a | |
| 177 // tie, in which case it will return NULL. | |
| 178 if (level_ == 1) | |
| 179 best_candidate = LeastOverlapIncrease(node->rect(), expanded_rects); | |
| 180 | |
| 181 // For non-parents of leaf nodes, or for parents of leaf nodes with ties in | |
| 182 // overlap increase, we choose the subtree with least area enlargement caused | |
| 183 // by the addition of the new node. | |
| 184 if (!best_candidate) | |
| 185 best_candidate = LeastAreaEnlargement(node->rect(), expanded_rects); | |
| 186 | |
| 187 DCHECK(best_candidate); | |
| 188 return best_candidate->ChooseSubtree(node); | |
| 189 } | |
| 190 | |
| 191 size_t RTreeBase::Node::AddChild(scoped_ptr<NodeBase> node) { | |
| 192 DCHECK(node); | |
| 193 // Sanity-check that the level of the child being added is one less than ours. | |
| 194 DCHECK_EQ(level_ - 1, node->Level()); | |
| 195 node->set_parent(this); | |
| 196 set_rect(UnionRects(rect(), node->rect())); | |
| 197 children_.push_back(node.release()); | |
| 198 return children_.size(); | |
| 199 } | |
| 200 | |
| 201 scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::Split(size_t min_children, | |
| 202 size_t max_children) { | |
| 203 // We should have too many children to begin with. | |
| 204 DCHECK_EQ(max_children + 1, children_.size()); | |
| 205 | |
| 206 // Determine if we should split along the horizontal or vertical axis. | |
| 207 std::vector<NodeBase*> vertical_sort(children_.get()); | |
| 208 std::vector<NodeBase*> horizontal_sort(children_.get()); | |
| 209 std::sort(vertical_sort.begin(), | |
| 210 vertical_sort.end(), | |
| 211 &RTreeBase::Node::CompareVertical); | |
| 212 std::sort(horizontal_sort.begin(), | |
| 213 horizontal_sort.end(), | |
| 214 &RTreeBase::Node::CompareHorizontal); | |
| 215 | |
| 216 Rects low_vertical_bounds; | |
| 217 Rects low_horizontal_bounds; | |
| 218 BuildLowBounds(vertical_sort, | |
| 219 horizontal_sort, | |
| 220 &low_vertical_bounds, | |
| 221 &low_horizontal_bounds); | |
| 222 | |
| 223 Rects high_vertical_bounds; | |
| 224 Rects high_horizontal_bounds; | |
| 225 BuildHighBounds(vertical_sort, | |
| 226 horizontal_sort, | |
| 227 &high_vertical_bounds, | |
| 228 &high_horizontal_bounds); | |
| 229 | |
| 230 // Choose |end_index| such that both Nodes after the split will have | |
| 231 // min_children <= children_.size() <= max_children. | |
| 232 size_t end_index = std::min(max_children, children_.size() - min_children); | |
| 233 bool is_vertical_split = | |
| 234 SmallestMarginSum(min_children, | |
| 235 end_index, | |
| 236 low_horizontal_bounds, | |
| 237 high_horizontal_bounds) < | |
| 238 SmallestMarginSum(min_children, | |
| 239 end_index, | |
| 240 low_vertical_bounds, | |
| 241 high_vertical_bounds); | |
| 242 | |
| 243 // Choose split index along chosen axis and perform the split. | |
| 244 const Rects& low_bounds( | |
| 245 is_vertical_split ? low_vertical_bounds : low_horizontal_bounds); | |
| 246 const Rects& high_bounds( | |
| 247 is_vertical_split ? high_vertical_bounds : high_horizontal_bounds); | |
| 248 size_t split_index = | |
| 249 ChooseSplitIndex(min_children, end_index, low_bounds, high_bounds); | |
| 250 | |
| 251 const std::vector<NodeBase*>& sort( | |
| 252 is_vertical_split ? vertical_sort : horizontal_sort); | |
| 253 return DivideChildren(low_bounds, high_bounds, sort, split_index); | |
| 254 } | |
| 255 | |
| 256 int RTreeBase::Node::Level() const { | |
| 257 return level_; | |
| 258 } | |
| 259 | |
| 260 RTreeBase::Node::Node(int level) : NodeBase(Rect(), NULL), level_(level) { | |
| 261 } | |
| 262 | |
| 263 // static | |
| 264 bool RTreeBase::Node::CompareVertical(const NodeBase* a, const NodeBase* b) { | |
| 265 const Rect& a_rect = a->rect(); | |
| 266 const Rect& b_rect = b->rect(); | |
| 267 return (a_rect.y() < b_rect.y()) || | |
| 268 ((a_rect.y() == b_rect.y()) && (a_rect.height() < b_rect.height())); | |
| 269 } | |
| 270 | |
| 271 // static | |
| 272 bool RTreeBase::Node::CompareHorizontal(const NodeBase* a, const NodeBase* b) { | |
| 273 const Rect& a_rect = a->rect(); | |
| 274 const Rect& b_rect = b->rect(); | |
| 275 return (a_rect.x() < b_rect.x()) || | |
| 276 ((a_rect.x() == b_rect.x()) && (a_rect.width() < b_rect.width())); | |
| 277 } | |
| 278 | |
| 279 // static | |
| 280 bool RTreeBase::Node::CompareCenterDistanceFromParent(const NodeBase* a, | |
| 281 const NodeBase* b) { | |
| 282 const NodeBase* p = a->parent(); | |
| 283 | |
| 284 DCHECK(p); | |
| 285 DCHECK_EQ(p, b->parent()); | |
| 286 | |
| 287 Vector2d p_center = CenterOfRect(p->rect()); | |
| 288 Vector2d a_center = CenterOfRect(a->rect()); | |
| 289 Vector2d b_center = CenterOfRect(b->rect()); | |
| 290 | |
| 291 // We don't bother with square roots because we are only comparing the two | |
| 292 // values for sorting purposes. | |
| 293 return (a_center - p_center).LengthSquared() < | |
| 294 (b_center - p_center).LengthSquared(); | |
| 295 } | |
| 296 | |
| 297 // static | |
| 298 void RTreeBase::Node::BuildLowBounds( | |
| 299 const std::vector<NodeBase*>& vertical_sort, | |
| 300 const std::vector<NodeBase*>& horizontal_sort, | |
| 301 Rects* vertical_bounds, | |
| 302 Rects* horizontal_bounds) { | |
| 303 Rect vertical_bounds_rect; | |
| 304 vertical_bounds->reserve(vertical_sort.size()); | |
| 305 for (std::vector<NodeBase*>::const_iterator i = vertical_sort.begin(); | |
| 306 i != vertical_sort.end(); | |
| 307 ++i) { | |
| 308 vertical_bounds_rect.Union((*i)->rect()); | |
| 309 vertical_bounds->push_back(vertical_bounds_rect); | |
| 310 } | |
| 311 | |
| 312 Rect horizontal_bounds_rect; | |
| 313 horizontal_bounds->reserve(horizontal_sort.size()); | |
| 314 for (std::vector<NodeBase*>::const_iterator i = horizontal_sort.begin(); | |
| 315 i != horizontal_sort.end(); | |
| 316 ++i) { | |
| 317 horizontal_bounds_rect.Union((*i)->rect()); | |
| 318 horizontal_bounds->push_back(horizontal_bounds_rect); | |
| 319 } | |
| 320 } | |
| 321 | |
| 322 // static | |
| 323 void RTreeBase::Node::BuildHighBounds( | |
| 324 const std::vector<NodeBase*>& vertical_sort, | |
| 325 const std::vector<NodeBase*>& horizontal_sort, | |
| 326 Rects* vertical_bounds, | |
| 327 Rects* horizontal_bounds) { | |
| 328 Rect vertical_bounds_rect; | |
| 329 vertical_bounds->reserve(vertical_sort.size()); | |
| 330 for (std::vector<NodeBase*>::const_reverse_iterator i = | |
| 331 vertical_sort.rbegin(); | |
| 332 i != vertical_sort.rend(); | |
| 333 ++i) { | |
| 334 vertical_bounds_rect.Union((*i)->rect()); | |
| 335 vertical_bounds->push_back(vertical_bounds_rect); | |
| 336 } | |
| 337 std::reverse(vertical_bounds->begin(), vertical_bounds->end()); | |
| 338 | |
| 339 Rect horizontal_bounds_rect; | |
| 340 horizontal_bounds->reserve(horizontal_sort.size()); | |
| 341 for (std::vector<NodeBase*>::const_reverse_iterator i = | |
| 342 horizontal_sort.rbegin(); | |
| 343 i != horizontal_sort.rend(); | |
| 344 ++i) { | |
| 345 horizontal_bounds_rect.Union((*i)->rect()); | |
| 346 horizontal_bounds->push_back(horizontal_bounds_rect); | |
| 347 } | |
| 348 std::reverse(horizontal_bounds->begin(), horizontal_bounds->end()); | |
| 349 } | |
| 350 | |
| 351 size_t RTreeBase::Node::ChooseSplitIndex(size_t start_index, | |
| 352 size_t end_index, | |
| 353 const Rects& low_bounds, | |
| 354 const Rects& high_bounds) { | |
| 355 DCHECK_EQ(low_bounds.size(), high_bounds.size()); | |
| 356 | |
| 357 int smallest_overlap_area = UnionRects( | |
| 358 low_bounds[start_index], high_bounds[start_index]).size().GetArea(); | |
| 359 int smallest_combined_area = low_bounds[start_index].size().GetArea() + | |
| 360 high_bounds[start_index].size().GetArea(); | |
| 361 size_t optimal_split_index = start_index; | |
| 362 for (size_t p = start_index + 1; p < end_index; ++p) { | |
| 363 const int overlap_area = | |
| 364 UnionRects(low_bounds[p], high_bounds[p]).size().GetArea(); | |
| 365 const int combined_area = | |
| 366 low_bounds[p].size().GetArea() + high_bounds[p].size().GetArea(); | |
| 367 if ((overlap_area < smallest_overlap_area) || | |
| 368 ((overlap_area == smallest_overlap_area) && | |
| 369 (combined_area < smallest_combined_area))) { | |
| 370 smallest_overlap_area = overlap_area; | |
| 371 smallest_combined_area = combined_area; | |
| 372 optimal_split_index = p; | |
| 373 } | |
| 374 } | |
| 375 | |
| 376 // optimal_split_index currently points at the last element in the first set, | |
| 377 // so advance it by 1 to point at the first element in the second set. | |
| 378 return optimal_split_index + 1; | |
| 379 } | |
| 380 | |
| 381 // static | |
| 382 int RTreeBase::Node::SmallestMarginSum(size_t start_index, | |
| 383 size_t end_index, | |
| 384 const Rects& low_bounds, | |
| 385 const Rects& high_bounds) { | |
| 386 DCHECK_EQ(low_bounds.size(), high_bounds.size()); | |
| 387 DCHECK_LT(start_index, low_bounds.size()); | |
| 388 DCHECK_LE(start_index, end_index); | |
| 389 DCHECK_LE(end_index, low_bounds.size()); | |
| 390 Rects::const_iterator i(low_bounds.begin() + start_index); | |
| 391 Rects::const_iterator j(high_bounds.begin() + start_index); | |
| 392 int smallest_sum = i->width() + i->height() + j->width() + j->height(); | |
| 393 for (; i != (low_bounds.begin() + end_index); ++i, ++j) { | |
| 394 smallest_sum = std::min( | |
| 395 smallest_sum, i->width() + i->height() + j->width() + j->height()); | |
| 396 } | |
| 397 | |
| 398 return smallest_sum; | |
| 399 } | |
| 400 | |
| 401 void RTreeBase::Node::RecomputeLocalBounds() { | |
| 402 Rect bounds; | |
| 403 for (size_t i = 0; i < children_.size(); ++i) | |
| 404 bounds.Union(children_[i]->rect()); | |
| 405 | |
| 406 set_rect(bounds); | |
| 407 } | |
| 408 | |
| 409 int RTreeBase::Node::OverlapIncreaseToAdd(const Rect& rect, | |
| 410 const NodeBase* candidate_node, | |
| 411 const Rect& expanded_rect) const { | |
| 412 DCHECK(candidate_node); | |
| 413 | |
| 414 // Early-out when |rect| is contained completely within |candidate|. | |
| 415 if (candidate_node->rect().Contains(rect)) | |
| 416 return 0; | |
| 417 | |
| 418 int total_original_overlap = 0; | |
| 419 int total_expanded_overlap = 0; | |
| 420 | |
| 421 // Now calculate overlap with all other rects in this node. | |
| 422 for (Nodes::const_iterator it = children_.begin(); | |
| 423 it != children_.end(); ++it) { | |
| 424 // Skip calculating overlap with the candidate rect. | |
| 425 if ((*it) == candidate_node) | |
| 426 continue; | |
| 427 NodeBase* overlap_node = (*it); | |
| 428 total_original_overlap += IntersectRects( | |
| 429 candidate_node->rect(), overlap_node->rect()).size().GetArea(); | |
| 430 Rect expanded_overlap_rect = expanded_rect; | |
| 431 expanded_overlap_rect.Intersect(overlap_node->rect()); | |
| 432 total_expanded_overlap += expanded_overlap_rect.size().GetArea(); | |
| 433 } | |
| 434 | |
| 435 return total_expanded_overlap - total_original_overlap; | |
| 436 } | |
| 437 | |
| 438 scoped_ptr<RTreeBase::NodeBase> RTreeBase::Node::DivideChildren( | |
| 439 const Rects& low_bounds, | |
| 440 const Rects& high_bounds, | |
| 441 const std::vector<NodeBase*>& sorted_children, | |
| 442 size_t split_index) { | |
| 443 DCHECK_EQ(low_bounds.size(), high_bounds.size()); | |
| 444 DCHECK_EQ(low_bounds.size(), sorted_children.size()); | |
| 445 DCHECK_LT(split_index, low_bounds.size()); | |
| 446 DCHECK_GT(split_index, 0U); | |
| 447 | |
| 448 scoped_ptr<Node> sibling(new Node(level_)); | |
| 449 sibling->set_parent(parent()); | |
| 450 set_rect(low_bounds[split_index - 1]); | |
| 451 sibling->set_rect(high_bounds[split_index]); | |
| 452 | |
| 453 // Our own children_ vector is unsorted, so we wipe it out and divide the | |
| 454 // sorted bounds rects between ourselves and our sibling. | |
| 455 children_.weak_clear(); | |
| 456 children_.insert(children_.end(), | |
| 457 sorted_children.begin(), | |
| 458 sorted_children.begin() + split_index); | |
| 459 sibling->children_.insert(sibling->children_.end(), | |
| 460 sorted_children.begin() + split_index, | |
| 461 sorted_children.end()); | |
| 462 | |
| 463 for (size_t i = 0; i < sibling->children_.size(); ++i) | |
| 464 sibling->children_[i]->set_parent(sibling.get()); | |
| 465 | |
| 466 return sibling.PassAs<NodeBase>(); | |
| 467 } | |
| 468 | |
| 469 RTreeBase::Node* RTreeBase::Node::LeastOverlapIncrease( | |
| 470 const Rect& node_rect, | |
| 471 const Rects& expanded_rects) { | |
| 472 NodeBase* best_node = children_.front(); | |
| 473 int least_overlap_increase = | |
| 474 OverlapIncreaseToAdd(node_rect, children_[0], expanded_rects[0]); | |
| 475 for (size_t i = 1; i < children_.size(); ++i) { | |
| 476 int overlap_increase = | |
| 477 OverlapIncreaseToAdd(node_rect, children_[i], expanded_rects[i]); | |
| 478 if (overlap_increase < least_overlap_increase) { | |
| 479 least_overlap_increase = overlap_increase; | |
| 480 best_node = children_[i]; | |
| 481 } else if (overlap_increase == least_overlap_increase) { | |
| 482 // If we are tied at zero there is no possible better overlap increase, | |
| 483 // so we can report a tie early. | |
| 484 if (overlap_increase == 0) | |
| 485 return NULL; | |
| 486 | |
| 487 best_node = NULL; | |
| 488 } | |
| 489 } | |
| 490 | |
| 491 // Ensure that our children are always Nodes and not Records. | |
| 492 DCHECK_GE(level_, 1); | |
| 493 return static_cast<Node*>(best_node); | |
| 494 } | |
| 495 | |
| 496 RTreeBase::Node* RTreeBase::Node::LeastAreaEnlargement( | |
| 497 const Rect& node_rect, | |
| 498 const Rects& expanded_rects) { | |
| 499 DCHECK(!children_.empty()); | |
| 500 DCHECK_EQ(children_.size(), expanded_rects.size()); | |
| 501 | |
| 502 NodeBase* best_node = children_.front(); | |
| 503 int least_area_enlargement = | |
| 504 expanded_rects[0].size().GetArea() - best_node->rect().size().GetArea(); | |
| 505 for (size_t i = 1; i < children_.size(); ++i) { | |
| 506 NodeBase* candidate_node = children_[i]; | |
| 507 int area_change = expanded_rects[i].size().GetArea() - | |
| 508 candidate_node->rect().size().GetArea(); | |
| 509 DCHECK_GE(area_change, 0); | |
| 510 if (area_change < least_area_enlargement) { | |
| 511 best_node = candidate_node; | |
| 512 least_area_enlargement = area_change; | |
| 513 } else if (area_change == least_area_enlargement && | |
| 514 candidate_node->rect().size().GetArea() < | |
| 515 best_node->rect().size().GetArea()) { | |
| 516 // Ties are broken by choosing the entry with the least area. | |
| 517 best_node = candidate_node; | |
| 518 } | |
| 519 } | |
| 520 | |
| 521 // Ensure that our children are always Nodes and not Records. | |
| 522 DCHECK_GE(level_, 1); | |
| 523 return static_cast<Node*>(best_node); | |
| 524 } | |
| 525 | |
| 526 | |
| 527 // RTreeBase ------------------------------------------------------------------ | |
| 528 | |
| 529 RTreeBase::RTreeBase(size_t min_children, size_t max_children) | |
| 530 : root_(new Node()), | |
| 531 min_children_(min_children), | |
| 532 max_children_(max_children) { | |
| 533 DCHECK_GE(min_children_, 2U); | |
| 534 DCHECK_LE(min_children_, max_children_ / 2U); | |
| 535 } | |
| 536 | |
| 537 RTreeBase::~RTreeBase() { | |
| 538 } | |
| 539 | |
| 540 void RTreeBase::InsertNode( | |
| 541 scoped_ptr<NodeBase> node, int* highest_reinsert_level) { | |
| 542 // Find the most appropriate parent to insert node into. | |
| 543 Node* parent = root_->ChooseSubtree(node.get()); | |
| 544 DCHECK(parent); | |
| 545 // Verify ChooseSubtree returned a Node at the correct level. | |
| 546 DCHECK_EQ(parent->Level(), node->Level() + 1); | |
| 547 Node* insert_parent = static_cast<Node*>(parent); | |
| 548 NodeBase* needs_bounds_recomputed = insert_parent->parent(); | |
| 549 Nodes reinserts; | |
| 550 // Attempt to insert the Node, if this overflows the Node we must handle it. | |
| 551 while (insert_parent && | |
| 552 insert_parent->AddChild(node.Pass()) > max_children_) { | |
| 553 // If we have yet to re-insert nodes at this level during this data insert, | |
| 554 // and we're not at the root, R*-Tree calls for re-insertion of some of the | |
| 555 // nodes, resulting in a better balance on the tree. | |
| 556 if (insert_parent->parent() && | |
| 557 insert_parent->Level() > *highest_reinsert_level) { | |
| 558 insert_parent->RemoveNodesForReinsert(max_children_ / 3, &reinserts); | |
| 559 // Adjust highest_reinsert_level to this level. | |
| 560 *highest_reinsert_level = insert_parent->Level(); | |
| 561 // RemoveNodesForReinsert() does not recompute bounds, so mark it. | |
| 562 needs_bounds_recomputed = insert_parent; | |
| 563 break; | |
| 564 } | |
| 565 | |
| 566 // Split() will create a sibling to insert_parent both of which will have | |
| 567 // valid bounds, but this invalidates their parent's bounds. | |
| 568 node = insert_parent->Split(min_children_, max_children_); | |
| 569 insert_parent = static_cast<Node*>(insert_parent->parent()); | |
| 570 needs_bounds_recomputed = insert_parent; | |
| 571 } | |
| 572 | |
| 573 // If we have a Node to insert, and we hit the root of the current tree, | |
| 574 // we create a new root which is the parent of the current root and the | |
| 575 // insert_node. Note that we must release() the |root_| since | |
| 576 // ConstructParent() will take ownership of it. | |
| 577 if (!insert_parent && node) { | |
| 578 root_ = root_.release()->ConstructParent(); | |
| 579 root_->AddChild(node.Pass()); | |
| 580 } | |
| 581 | |
| 582 // Recompute bounds along insertion path. | |
| 583 if (needs_bounds_recomputed) | |
| 584 needs_bounds_recomputed->RecomputeBoundsUpToRoot(); | |
| 585 | |
| 586 // Complete re-inserts, if any. The algorithm only allows for one invocation | |
| 587 // of RemoveNodesForReinsert() per level of the tree in an overall call to | |
| 588 // Insert(). | |
| 589 while (!reinserts.empty()) { | |
| 590 Nodes::iterator last_element = reinserts.end() - 1; | |
| 591 NodeBase* temp_ptr(*last_element); | |
| 592 reinserts.weak_erase(last_element); | |
| 593 InsertNode(make_scoped_ptr(temp_ptr), highest_reinsert_level); | |
| 594 } | |
| 595 } | |
| 596 | |
| 597 scoped_ptr<RTreeBase::NodeBase> RTreeBase::RemoveNode(NodeBase* node) { | |
| 598 // We need to remove this node from its parent. | |
| 599 Node* parent = static_cast<Node*>(node->parent()); | |
| 600 // Record nodes are never allowed as the root, so we should always have a | |
| 601 // parent. | |
| 602 DCHECK(parent); | |
| 603 // Should always be a leaf that had the record. | |
| 604 DCHECK_EQ(0, parent->Level()); | |
| 605 | |
| 606 Nodes orphans; | |
| 607 scoped_ptr<NodeBase> removed_node(parent->RemoveChild(node, &orphans)); | |
| 608 | |
| 609 // It's possible that by removing |node| from |parent| we have made |parent| | |
| 610 // have less than the minimum number of children, in which case we will need | |
| 611 // to remove and delete |parent| while reinserting any other children that it | |
| 612 // had. We traverse up the tree doing this until we remove a child from a | |
| 613 // parent that still has greater than or equal to the minimum number of Nodes. | |
| 614 while (parent->count() < min_children_) { | |
| 615 NodeBase* child = parent; | |
| 616 parent = static_cast<Node*>(parent->parent()); | |
| 617 | |
| 618 // If we've hit the root, stop. | |
| 619 if (!parent) | |
| 620 break; | |
| 621 | |
| 622 parent->RemoveChild(child, &orphans); | |
| 623 } | |
| 624 | |
| 625 // If we stopped deleting nodes up the tree before encountering the root, | |
| 626 // we'll need to fix up the bounds from the first parent we didn't delete | |
| 627 // up to the root. | |
| 628 if (parent) | |
| 629 parent->RecomputeBoundsUpToRoot(); | |
| 630 else | |
| 631 root_->RecomputeBoundsUpToRoot(); | |
| 632 | |
| 633 while (!orphans.empty()) { | |
| 634 Nodes::iterator last_element = orphans.end() - 1; | |
| 635 NodeBase* temp_ptr(*last_element); | |
| 636 orphans.weak_erase(last_element); | |
| 637 int starting_level = -1; | |
| 638 InsertNode(make_scoped_ptr(temp_ptr), &starting_level); | |
| 639 } | |
| 640 | |
| 641 return removed_node.Pass(); | |
| 642 } | |
| 643 | |
| 644 void RTreeBase::PruneRootIfNecessary() { | |
| 645 if (root()->count() == 1 && root()->Level() > 0) { | |
| 646 // Awkward reset(cast(release)) pattern here because there's no better way | |
| 647 // to downcast the scoped_ptr from RemoveAndReturnLastChild() from NodeBase | |
| 648 // to Node. | |
| 649 root_.reset( | |
| 650 static_cast<Node*>(root_->RemoveAndReturnLastChild().release())); | |
| 651 } | |
| 652 } | |
| 653 | |
| 654 void RTreeBase::ResetRoot() { | |
| 655 root_.reset(new Node()); | |
| 656 } | |
| 657 | |
| 658 } // namespace gfx | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 338833004:
Revert 276827 "readability review for luken" (Closed)
Base URL: svn://svn.chromium.org/chrome/