1/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ 2/************************************************************************* 3 * 4 * Copyright (c) 2018 Kohei Yoshida 5 * 6 * Permission is hereby granted, free of charge, to any person 7 * obtaining a copy of this software and associated documentation 8 * files (the "Software"), to deal in the Software without 9 * restriction, including without limitation the rights to use, 10 * copy, modify, merge, publish, distribute, sublicense, and/or sell 11 * copies of the Software, and to permit persons to whom the 12 * Software is furnished to do so, subject to the following 13 * conditions: 14 * 15 * The above copyright notice and this permission notice shall be 16 * included in all copies or substantial portions of the Software. 17 * 18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 20 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 22 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 23 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 24 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 25 * OTHER DEALINGS IN THE SOFTWARE. 26 * 27 ************************************************************************/ 28 29#include "mdds/global.hpp" 30 31#include <stdexcept> 32#include <iostream> 33#include <sstream> 34#include <memory> 35#include <cassert> 36#include <algorithm> 37#include <cmath> 38 39namespace mdds { 40 41namespace detail { namespace rtree { 42 43template<typename T> 44using remove_cvref_t = typename std::remove_cv<typename std::remove_reference<T>::type>::type; 45 46inline const char* to_string(node_type nt) 47{ 48 switch (nt) 49 { 50 case node_type::unspecified: 51 return "unspecified"; 52 case node_type::directory_leaf: 53 return "directory-leaf"; 54 case node_type::directory_nonleaf: 55 return "directory-nonleaf"; 56 case node_type::value: 57 return "value"; 58 } 59 60 return "???"; 61} 62 63inline size_t calc_optimal_segment_size_for_pack(size_t init_size, size_t min_size, size_t max_size, size_t value_count) 64{ 65 // Keep increasing the size until the remainder becomes at least the min size. 66 size_t final_size = init_size; 67 for (; final_size < max_size; ++final_size) 68 { 69 size_t mod = value_count % final_size; 70 if (!mod || mod >= min_size) 71 return final_size; 72 } 73 74 // If increasing the size doesn't work, then decrease it. 75 final_size = init_size; 76 for (--final_size; min_size < final_size; --final_size) 77 { 78 size_t mod = value_count % final_size; 79 if (!mod || mod >= min_size) 80 return final_size; 81 } 82 83 // Nothing has worked. Use the original value. 84 return init_size; 85} 86 87template<typename _Extent> 88auto calc_linear_intersection(size_t dim, const _Extent& bb1, const _Extent& bb2) -> remove_cvref_t<decltype(bb1.start.d[0])> 89{ 90 using key_type = remove_cvref_t<decltype(bb1.start.d[0])>; 91 92 key_type start1 = bb1.start.d[dim], end1 = bb1.end.d[dim]; 93 key_type start2 = bb2.start.d[dim], end2 = bb2.end.d[dim]; 94 95 // Ensure that start1 < start2. 96 97 if (start1 > start2) 98 { 99 std::swap(start1, start2); 100 std::swap(end1, end2); 101 } 102 103 assert(start1 <= start2); 104 105 if (end1 < start2) 106 { 107 // 1 : |------| 108 // 2 : |-------| 109 110 // These two are not intersected at all. Bail out. 111 return key_type(); 112 } 113 114 if (end1 < end2) 115 { 116 // 1 : |---------| 117 // 2 : |----------| 118 119 return end1 - start2; 120 } 121 122 // 1 : |--------------| 123 // 2 : |-----| 124 125 return end2 - start2; 126} 127 128template<typename _Extent> 129bool intersects(const _Extent& bb1, const _Extent& bb2) 130{ 131 constexpr size_t dim_size = sizeof(bb1.start.d) / sizeof(bb1.start.d[0]); 132 using key_type = remove_cvref_t<decltype(bb1.start.d[0])>; 133 134 for (size_t dim = 0; dim < dim_size; ++dim) 135 { 136 key_type start1 = bb1.start.d[dim], end1 = bb1.end.d[dim]; 137 key_type start2 = bb2.start.d[dim], end2 = bb2.end.d[dim]; 138 139 // Ensure that start1 <= start2. 140 141 if (start1 > start2) 142 { 143 std::swap(start1, start2); 144 std::swap(end1, end2); 145 } 146 147 assert(start1 <= start2); 148 149 if (end1 < start2) 150 { 151 // 1 : |------| 152 // 2 : |-------| 153 154 // These two are not intersected at all. Bail out. 155 return false; 156 } 157 } 158 159 return true; 160} 161 162template<typename _Extent> 163auto calc_intersection(const _Extent& bb1, const _Extent& bb2) -> remove_cvref_t<decltype(bb1.start.d[0])> 164{ 165 constexpr size_t dim_size = sizeof(bb1.start.d) / sizeof(bb1.start.d[0]); 166 static_assert(dim_size > 0, "Dimension cannot be zero."); 167 using key_type = remove_cvref_t<decltype(bb1.start.d[0])>; 168 169 key_type total_volume = calc_linear_intersection<_Extent>(0, bb1, bb2); 170 if (!total_volume) 171 return key_type(); 172 173 for (size_t dim = 1; dim < dim_size; ++dim) 174 { 175 key_type segment_len = calc_linear_intersection<_Extent>(dim, bb1, bb2); 176 if (!segment_len) 177 return key_type(); 178 179 total_volume *= segment_len; 180 } 181 182 return total_volume; 183} 184 185template<typename _Extent> 186bool enlarge_extent_to_fit(_Extent& parent, const _Extent& child) 187{ 188 constexpr size_t dim_size = sizeof(parent.start.d) / sizeof(parent.start.d[0]); 189 static_assert(dim_size > 0, "Dimension cannot be zero."); 190 bool enlarged = false; 191 192 for (size_t dim = 0; dim < dim_size; ++dim) 193 { 194 if (child.start.d[dim] < parent.start.d[dim]) 195 { 196 parent.start.d[dim] = child.start.d[dim]; 197 enlarged = true; 198 } 199 200 if (parent.end.d[dim] < child.end.d[dim]) 201 { 202 parent.end.d[dim] = child.end.d[dim]; 203 enlarged = true; 204 } 205 } 206 207 return enlarged; 208} 209 210template<typename _Extent> 211auto calc_area(const _Extent& bb) -> remove_cvref_t<decltype(bb.start.d[0])> 212{ 213 constexpr size_t dim_size = sizeof(bb.start.d) / sizeof(bb.start.d[0]); 214 static_assert(dim_size > 0, "Dimension cannot be zero."); 215 using key_type = remove_cvref_t<decltype(bb.start.d[0])>; 216 217 key_type area = bb.end.d[0] - bb.start.d[0]; 218 for (size_t dim = 1; dim < dim_size; ++dim) 219 area *= bb.end.d[dim] - bb.start.d[dim]; 220 221 return area; 222} 223 224template<typename _Pt> 225auto calc_square_distance(const _Pt& pt1, const _Pt& pt2) -> remove_cvref_t<decltype(pt1.d[0])> 226{ 227 constexpr size_t dim_size = sizeof(pt1.d) / sizeof(pt1.d[0]); 228 static_assert(dim_size > 0, "Dimension cannot be zero."); 229 using key_type = remove_cvref_t<decltype(pt1.d[0])>; 230 231 key_type dist = key_type(); 232 for (size_t dim = 0; dim < dim_size; ++dim) 233 { 234 key_type v1 = pt1.d[dim], v2 = pt2.d[dim]; 235 236 if (v1 > v2) 237 std::swap(v1, v2); // ensure that v1 <= v2. 238 239 assert(v1 <= v2); 240 241 key_type diff = v2 - v1; 242 dist += diff * diff; 243 } 244 245 return dist; 246} 247 248/** 249 * The margin here is defined as the sum of the lengths of the edges of a 250 * bounding box, per the original paper on R*-tree. It's half-margin 251 * because it only adds one of the two edges in each dimension. 252 */ 253template<typename _Extent> 254auto calc_half_margin(const _Extent& bb) -> remove_cvref_t<decltype(bb.start.d[0])> 255{ 256 constexpr size_t dim_size = sizeof(bb.start.d) / sizeof(bb.start.d[0]); 257 static_assert(dim_size > 0, "Dimension cannot be zero."); 258 using key_type = remove_cvref_t<decltype(bb.start.d[0])>; 259 260 key_type margin = bb.end.d[0] - bb.start.d[0]; 261 for (size_t dim = 1; dim < dim_size; ++dim) 262 margin += bb.end.d[dim] - bb.start.d[dim]; 263 264 return margin; 265} 266 267/** 268 * Area enlargement is calculated by calculating the area of the enlarged 269 * box subtracted by the area of the original box prior to the enlargement. 270 * 271 * @param bb_host bounding box of the area receiving the new object. 272 * @param bb_guest bounding of the new object being inserted. 273 * 274 * @return quantity of the area enlargement. 275 */ 276template<typename _Extent> 277auto calc_area_enlargement(const _Extent& bb_host, const _Extent& bb_guest) -> remove_cvref_t<decltype(bb_host.start.d[0])> 278{ 279 constexpr size_t dim_size = sizeof(bb_host.start.d) / sizeof(bb_host.start.d[0]); 280 static_assert(dim_size > 0, "Dimension cannot be zero."); 281 using key_type = remove_cvref_t<decltype(bb_host.start.d[0])>; 282 using extent = _Extent; 283 284 // Calculate the original area. 285 key_type original_area = calc_area<_Extent>(bb_host); 286 287 // Enlarge the box for the new object if needed. 288 extent bb_host_enlarged = bb_host; // make a copy. 289 bool enlarged = enlarge_extent_to_fit<_Extent>(bb_host_enlarged, bb_guest); 290 if (!enlarged) 291 // Area enlargement did not take place. 292 return key_type(); 293 294 key_type enlarged_area = calc_area<_Extent>(bb_host_enlarged); 295 296 return enlarged_area - original_area; 297} 298 299template<typename _Iter> 300auto calc_extent(_Iter it, _Iter it_end) -> decltype(it->extent) 301{ 302 auto bb = it->extent; 303 for (++it; it != it_end; ++it) 304 enlarge_extent_to_fit(bb, it->extent); 305 306 return bb; 307} 308 309template<typename _Extent> 310auto get_center_point(const _Extent& extent) -> decltype(extent.start) 311{ 312 constexpr size_t dim_size = sizeof(extent.start.d) / sizeof(extent.start.d[0]); 313 static_assert(dim_size > 0, "Dimension cannot be zero."); 314 using point_type = decltype(extent.start); 315 using key_type = decltype(extent.start.d[0]); 316 317 point_type ret; 318 319 static const key_type two = 2; 320 321 for (size_t dim = 0; dim < dim_size; ++dim) 322 ret.d[dim] = (extent.end.d[dim] + extent.start.d[dim]) / two; 323 324 return ret; 325} 326 327template<typename _Key> 328struct min_value_pos 329{ 330 _Key value = _Key(); 331 size_t pos = 0; 332 size_t count = 0; 333 334 void assign(_Key new_value, size_t new_pos) 335 { 336 if (count) 337 { 338 // Assign only if it's less than the current value. 339 if (new_value < value) 340 { 341 value = new_value; 342 pos = new_pos; 343 } 344 } 345 else 346 { 347 // The very first value. Just take it. 348 value = new_value; 349 pos = new_pos; 350 } 351 352 ++count; 353 } 354}; 355 356template<typename _Key> 357struct reinsertion_bucket 358{ 359 using key_type = _Key; 360 361 key_type distance; 362 size_t src_pos; 363}; 364 365template<typename _NodePtrT> 366struct ptr_to_string 367{ 368 using node_ptr_type = _NodePtrT; 369 using node_ptr_map_type = std::unordered_map<node_ptr_type, std::string>; 370 371 node_ptr_map_type node_ptr_map; 372 373 std::string operator() (node_ptr_type np) const 374 { 375 auto it = node_ptr_map.find(np); 376 return (it == node_ptr_map.end()) ? "(*, *)" : it->second; 377 } 378 379 ptr_to_string() 380 { 381 static_assert(std::is_pointer<node_ptr_type>::value, "Node pointer type must be a real pointer type."); 382 } 383 384 ptr_to_string(const ptr_to_string&) = delete; 385 ptr_to_string(ptr_to_string&& other) : node_ptr_map(std::move(other.node_ptr_map)) {} 386}; 387 388}} 389 390template<typename _Key, typename _Value, typename _Trait> 391rtree<_Key,_Value,_Trait>::point_type::point_type() 392{ 393 // Initialize the point values with the key type's default value. 394 key_type* p = d; 395 key_type* p_end = p + trait_type::dimensions; 396 397 for (; p != p_end; ++p) 398 *p = key_type{}; 399} 400 401template<typename _Key, typename _Value, typename _Trait> 402rtree<_Key,_Value,_Trait>::point_type::point_type(std::initializer_list<key_type> vs) 403{ 404 // Initialize the point values with the key type's default value. 405 key_type* dst = d; 406 key_type* dst_end = dst + trait_type::dimensions; 407 408 for (const key_type& v : vs) 409 { 410 if (dst == dst_end) 411 throw std::range_error("number of elements exceeds the dimension size."); 412 413 *dst = v; 414 ++dst; 415 } 416} 417 418template<typename _Key, typename _Value, typename _Trait> 419std::string 420rtree<_Key,_Value,_Trait>::point_type::to_string() const 421{ 422 std::ostringstream os; 423 424 os << "("; 425 for (size_t i = 0; i < trait_type::dimensions; ++i) 426 { 427 if (i > 0) 428 os << ", "; 429 os << d[i]; 430 } 431 os << ")"; 432 433 return os.str(); 434} 435 436template<typename _Key, typename _Value, typename _Trait> 437bool rtree<_Key,_Value,_Trait>::point_type::operator== (const point_type& other) const 438{ 439 const key_type* left = d; 440 const key_type* right = other.d; 441 const key_type* left_end = left + trait_type::dimensions; 442 443 for (; left != left_end; ++left, ++right) 444 { 445 if (*left != *right) 446 return false; 447 } 448 449 return true; 450} 451 452template<typename _Key, typename _Value, typename _Trait> 453bool rtree<_Key,_Value,_Trait>::point_type::operator!= (const point_type& other) const 454{ 455 return !operator== (other); 456} 457 458template<typename _Key, typename _Value, typename _Trait> 459rtree<_Key,_Value,_Trait>::extent_type::extent_type() {} 460 461template<typename _Key, typename _Value, typename _Trait> 462rtree<_Key,_Value,_Trait>::extent_type::extent_type(const point_type& _start, const point_type& _end) : 463 start(_start), end(_end) {} 464 465template<typename _Key, typename _Value, typename _Trait> 466std::string 467rtree<_Key,_Value,_Trait>::extent_type::to_string() const 468{ 469 std::ostringstream os; 470 os << start.to_string(); 471 472 if (!is_point()) 473 os << " - " << end.to_string(); 474 475 return os.str(); 476} 477 478template<typename _Key, typename _Value, typename _Trait> 479bool rtree<_Key,_Value,_Trait>::extent_type::is_point() const 480{ 481 return start == end; 482} 483 484template<typename _Key, typename _Value, typename _Trait> 485bool rtree<_Key,_Value,_Trait>::extent_type::operator== (const extent_type& other) const 486{ 487 return start == other.start && end == other.end; 488} 489 490template<typename _Key, typename _Value, typename _Trait> 491bool rtree<_Key,_Value,_Trait>::extent_type::operator!= (const extent_type& other) const 492{ 493 return !operator== (other); 494} 495 496template<typename _Key, typename _Value, typename _Trait> 497bool rtree<_Key,_Value,_Trait>::extent_type::contains(const point_type& pt) const 498{ 499 for (size_t dim = 0; dim < trait_type::dimensions; ++dim) 500 { 501 if (pt.d[dim] < start.d[dim] || end.d[dim] < pt.d[dim]) 502 return false; 503 } 504 505 return true; 506} 507 508template<typename _Key, typename _Value, typename _Trait> 509bool rtree<_Key,_Value,_Trait>::extent_type::contains(const extent_type& bb) const 510{ 511 for (size_t dim = 0; dim < trait_type::dimensions; ++dim) 512 { 513 if (bb.start.d[dim] < start.d[dim] || end.d[dim] < bb.end.d[dim]) 514 return false; 515 } 516 517 return true; 518} 519 520template<typename _Key, typename _Value, typename _Trait> 521bool rtree<_Key,_Value,_Trait>::extent_type::intersects(const extent_type& bb) const 522{ 523 return detail::rtree::intersects(bb, *this); 524} 525 526template<typename _Key, typename _Value, typename _Trait> 527bool rtree<_Key,_Value,_Trait>::extent_type::contains_at_boundary(const extent_type& bb) const 528{ 529 for (size_t dim = 0; dim < trait_type::dimensions; ++dim) 530 { 531 if (start.d[dim] == bb.start.d[dim] || bb.end.d[dim] == end.d[dim]) 532 return true; 533 } 534 535 return false; 536} 537 538template<typename _Key, typename _Value, typename _Trait> 539rtree<_Key,_Value,_Trait>::node_store::node_store() : 540 type(node_type::unspecified), parent(nullptr), node_ptr(nullptr), count(0), 541 valid_pointer(true) {} 542 543template<typename _Key, typename _Value, typename _Trait> 544rtree<_Key,_Value,_Trait>::node_store::node_store(node_store&& r) : 545 type(r.type), 546 extent(r.extent), 547 parent(r.parent), 548 node_ptr(r.node_ptr), 549 count(r.count), 550 valid_pointer(r.valid_pointer) 551{ 552 r.type = node_type::unspecified; 553 r.extent = extent_type(); 554 r.parent = nullptr; 555 r.node_ptr = nullptr; 556 r.count = 0; 557 r.valid_pointer = true; 558} 559 560template<typename _Key, typename _Value, typename _Trait> 561rtree<_Key,_Value,_Trait>::node_store::node_store(node_type _type, const extent_type& _extent, node* _node_ptr) : 562 type(_type), extent(_extent), parent(nullptr), node_ptr(_node_ptr), count(0), valid_pointer(true) {} 563 564template<typename _Key, typename _Value, typename _Trait> 565rtree<_Key,_Value,_Trait>::node_store::~node_store() 566{ 567 if (node_ptr) 568 { 569 switch (type) 570 { 571 case node_type::directory_leaf: 572 case node_type::directory_nonleaf: 573 delete static_cast<directory_node*>(node_ptr); 574 break; 575 case node_type::value: 576 delete static_cast<value_node*>(node_ptr); 577 break; 578 case node_type::unspecified: 579 default: 580 assert(!"node::~node: unknown node type!"); 581 } 582 } 583} 584 585template<typename _Key, typename _Value, typename _Trait> 586typename rtree<_Key,_Value,_Trait>::node_store 587rtree<_Key,_Value,_Trait>::node_store::clone() const 588{ 589 auto func_copy_dir = [this](node_store& cloned, const directory_node* src) 590 { 591 directory_node* dir = cloned.get_directory_node(); 592 assert(dir); 593 for (const node_store& ns : src->children) 594 dir->children.push_back(ns.clone()); 595 596 cloned.count = count; 597 cloned.extent = extent; 598 }; 599 600 switch (type) 601 { 602 case node_type::directory_leaf: 603 { 604 const directory_node* src = static_cast<const directory_node*>(node_ptr); 605 node_store cloned = create_leaf_directory_node(); 606 func_copy_dir(cloned, src); 607 return cloned; 608 } 609 case node_type::directory_nonleaf: 610 { 611 const directory_node* src = static_cast<const directory_node*>(node_ptr); 612 node_store cloned = create_nonleaf_directory_node(); 613 func_copy_dir(cloned, src); 614 return cloned; 615 } 616 case node_type::value: 617 { 618 const value_node* vn = static_cast<const value_node*>(node_ptr); 619 return create_value_node(extent, vn->value); 620 } 621 case node_type::unspecified: 622 default: 623 assert(!"node::~node: unknown node type!"); 624 } 625} 626 627template<typename _Key, typename _Value, typename _Trait> 628typename rtree<_Key,_Value,_Trait>::node_store 629rtree<_Key,_Value,_Trait>::node_store::create_leaf_directory_node() 630{ 631 node_store ret(node_type::directory_leaf, extent_type(), new directory_node); 632 ret.valid_pointer = false; 633 return ret; 634} 635 636template<typename _Key, typename _Value, typename _Trait> 637typename rtree<_Key,_Value,_Trait>::node_store 638rtree<_Key,_Value,_Trait>::node_store::create_nonleaf_directory_node() 639{ 640 node_store ret(node_type::directory_nonleaf, extent_type(), new directory_node); 641 ret.valid_pointer = false; 642 return ret; 643} 644 645template<typename _Key, typename _Value, typename _Trait> 646typename rtree<_Key,_Value,_Trait>::node_store 647rtree<_Key,_Value,_Trait>::node_store::create_value_node(const extent_type& extent, value_type&& v) 648{ 649 node_store ret(node_type::value, extent, new value_node(std::move(v))); 650 return ret; 651} 652 653template<typename _Key, typename _Value, typename _Trait> 654typename rtree<_Key,_Value,_Trait>::node_store 655rtree<_Key,_Value,_Trait>::node_store::create_value_node(const extent_type& extent, const value_type& v) 656{ 657 node_store ret(node_type::value, extent, new value_node(v)); 658 return ret; 659} 660 661template<typename _Key, typename _Value, typename _Trait> 662typename rtree<_Key,_Value,_Trait>::node_store& 663rtree<_Key,_Value,_Trait>::node_store::operator= (node_store&& other) 664{ 665 node_store tmp(std::move(other)); 666 swap(tmp); 667 return *this; 668} 669 670template<typename _Key, typename _Value, typename _Trait> 671bool rtree<_Key,_Value,_Trait>::node_store::pack() 672{ 673 const directory_node* dir = get_directory_node(); 674 if (!dir) 675 return false; 676 677 const dir_store_type& children = dir->children; 678 if (children.empty()) 679 { 680 // This node has no children. Reset the bounding box to empty. 681 extent_type new_box; 682 bool changed = new_box != extent; 683 extent = new_box; 684 return changed; 685 } 686 687 extent_type new_box = dir->calc_extent(); 688 bool changed = new_box != extent; 689 extent = new_box; // update the bounding box. 690 return changed; 691} 692 693template<typename _Key, typename _Value, typename _Trait> 694void rtree<_Key,_Value,_Trait>::node_store::pack_upward() 695{ 696 bool propagate = true; 697 for (node_store* p = parent; propagate && p; p = p->parent) 698 propagate = p->pack(); 699} 700 701template<typename _Key, typename _Value, typename _Trait> 702bool rtree<_Key,_Value,_Trait>::node_store::is_directory() const 703{ 704 switch (type) 705 { 706 case node_type::directory_leaf: 707 case node_type::directory_nonleaf: 708 return true; 709 default: 710 ; 711 } 712 713 return false; 714} 715 716template<typename _Key, typename _Value, typename _Trait> 717bool rtree<_Key,_Value,_Trait>::node_store::is_root() const 718{ 719 return parent == nullptr; 720} 721 722template<typename _Key, typename _Value, typename _Trait> 723bool rtree<_Key,_Value,_Trait>::node_store::exceeds_capacity() const 724{ 725 if (type != node_type::directory_leaf) 726 return false; 727 728 return count > trait_type::max_node_size; 729} 730 731template<typename _Key, typename _Value, typename _Trait> 732void rtree<_Key,_Value,_Trait>::node_store::swap(node_store& other) 733{ 734 std::swap(type, other.type); 735 std::swap(extent, other.extent); 736 std::swap(parent, other.parent); 737 std::swap(node_ptr, other.node_ptr); 738 std::swap(count, other.count); 739 std::swap(valid_pointer, other.valid_pointer); 740} 741 742template<typename _Key, typename _Value, typename _Trait> 743void rtree<_Key,_Value,_Trait>::node_store::reset_parent_pointers_of_children() 744{ 745 if (valid_pointer) 746 return; 747 748 directory_node* dir = get_directory_node(); 749 if (!dir) 750 return; 751 752 for (node_store& ns : dir->children) 753 { 754 ns.parent = this; 755 ns.reset_parent_pointers_of_children(); 756 } 757 758 valid_pointer = true; 759} 760 761template<typename _Key, typename _Value, typename _Trait> 762void rtree<_Key,_Value,_Trait>::node_store::reset_parent_pointers() 763{ 764 valid_pointer = false; 765 reset_parent_pointers_of_children(); 766} 767 768template<typename _Key, typename _Value, typename _Trait> 769typename rtree<_Key,_Value,_Trait>::directory_node* 770rtree<_Key,_Value,_Trait>::node_store::get_directory_node() 771{ 772 if (!is_directory()) 773 return nullptr; 774 775 return static_cast<directory_node*>(node_ptr); 776} 777 778template<typename _Key, typename _Value, typename _Trait> 779const typename rtree<_Key,_Value,_Trait>::directory_node* 780rtree<_Key,_Value,_Trait>::node_store::get_directory_node() const 781{ 782 if (!is_directory()) 783 return nullptr; 784 785 return static_cast<const directory_node*>(node_ptr); 786} 787 788template<typename _Key, typename _Value, typename _Trait> 789bool rtree<_Key,_Value,_Trait>::node_store::erase_child(const node_store* p) 790{ 791 if (!is_directory()) 792 return false; 793 794 directory_node* dir = static_cast<directory_node*>(node_ptr); 795 bool erased = dir->erase(p); 796 if (erased) 797 --count; 798 799 assert(count == dir->children.size()); 800 return erased; 801} 802 803template<typename _Key, typename _Value, typename _Trait> 804rtree<_Key,_Value,_Trait>::node::node() {} 805 806template<typename _Key, typename _Value, typename _Trait> 807rtree<_Key,_Value,_Trait>::node::~node() {} 808 809template<typename _Key, typename _Value, typename _Trait> 810rtree<_Key,_Value,_Trait>::value_node::value_node(value_type&& _value) : 811 value(std::move(_value)) {} 812 813template<typename _Key, typename _Value, typename _Trait> 814rtree<_Key,_Value,_Trait>::value_node::value_node(const value_type& _value) : 815 value(_value) {} 816 817template<typename _Key, typename _Value, typename _Trait> 818rtree<_Key,_Value,_Trait>::value_node::~value_node() {} 819 820template<typename _Key, typename _Value, typename _Trait> 821rtree<_Key,_Value,_Trait>::directory_node::directory_node() {} 822 823template<typename _Key, typename _Value, typename _Trait> 824rtree<_Key,_Value,_Trait>::directory_node::~directory_node() {} 825 826template<typename _Key, typename _Value, typename _Trait> 827bool rtree<_Key,_Value,_Trait>::directory_node::erase(const node_store* ns) 828{ 829 auto it = std::find_if(children.begin(), children.end(), 830 [ns](const node_store& this_ns) -> bool 831 { 832 return &this_ns == ns; 833 } 834 ); 835 836 if (it == children.end()) 837 return false; 838 839 it = children.erase(it); 840 841 // All nodes that occur after the erased node have their memory addresses 842 // shifted. 843 844 std::for_each(it, children.end(), 845 [](node_store& this_ns) 846 { 847 this_ns.valid_pointer = false; 848 } 849 ); 850 851 return true; 852} 853 854template<typename _Key, typename _Value, typename _Trait> 855typename rtree<_Key,_Value,_Trait>::node_store* 856rtree<_Key,_Value,_Trait>::directory_node::get_child_with_minimal_overlap(const extent_type& bb) 857{ 858 key_type min_overlap = key_type(); 859 key_type min_area_enlargement = key_type(); 860 key_type min_area = key_type(); 861 862 node_store* dst = nullptr; 863 864 for (node_store& ns : children) 865 { 866 directory_node* dir = static_cast<directory_node*>(ns.node_ptr); 867 key_type overlap = dir->calc_overlap_cost(bb); 868 key_type area_enlargement = detail::rtree::calc_area_enlargement<extent_type>(ns.extent, bb); 869 key_type area = detail::rtree::calc_area<extent_type>(ns.extent); 870 871 bool pick_this = false; 872 873 if (!dst) 874 pick_this = true; 875 else if (overlap < min_overlap) 876 // Pick the entry with the smaller overlap cost increase. 877 pick_this = true; 878 else if (area_enlargement < min_area_enlargement) 879 // Pick the entry with the smaller area enlargment. 880 pick_this = true; 881 else if (area < min_area) 882 // Resolve ties by picking the one with on the smaller area 883 // rectangle. 884 pick_this = true; 885 886 if (pick_this) 887 { 888 min_overlap = overlap; 889 min_area_enlargement = area_enlargement; 890 min_area = area; 891 dst = &ns; 892 } 893 } 894 895 return dst; 896} 897 898template<typename _Key, typename _Value, typename _Trait> 899typename rtree<_Key,_Value,_Trait>::node_store* 900rtree<_Key,_Value,_Trait>::directory_node::get_child_with_minimal_area_enlargement(const extent_type& bb) 901{ 902 // Compare the costs of area enlargements. 903 key_type min_cost = key_type(); 904 key_type min_area = key_type(); 905 906 node_store* dst = nullptr; 907 908 for (node_store& ns : children) 909 { 910 key_type cost = detail::rtree::calc_area_enlargement(ns.extent, bb); 911 key_type area = detail::rtree::calc_area(ns.extent); 912 913 bool pick_this = false; 914 915 if (!dst) 916 pick_this = true; 917 else if (cost < min_cost) 918 // Pick the entry with the smaller area enlargment. 919 pick_this = true; 920 else if (area < min_area) 921 // Resolve ties by picking the one with on the smaller area 922 // rectangle. 923 pick_this = true; 924 925 if (pick_this) 926 { 927 min_cost = cost; 928 min_area = area; 929 dst = &ns; 930 } 931 } 932 933 return dst; 934} 935 936template<typename _Key, typename _Value, typename _Trait> 937typename rtree<_Key,_Value,_Trait>::extent_type 938rtree<_Key,_Value,_Trait>::directory_node::calc_extent() const 939{ 940 auto it = children.cbegin(), ite = children.cend(); 941 942 extent_type box; 943 if (it != ite) 944 box = detail::rtree::calc_extent(it, ite); 945 946 return box; 947} 948 949template<typename _Key, typename _Value, typename _Trait> 950typename rtree<_Key,_Value,_Trait>::key_type 951rtree<_Key,_Value,_Trait>::directory_node::calc_overlap_cost(const extent_type& bb) const 952{ 953 key_type overlap_cost = key_type(); 954 955 for (const node_store& ns : children) 956 overlap_cost += detail::rtree::calc_intersection<extent_type>(ns.extent, bb); 957 958 return overlap_cost; 959} 960 961template<typename _Key, typename _Value, typename _Trait> 962bool rtree<_Key,_Value,_Trait>::directory_node::has_leaf_directory() const 963{ 964 for (const auto& ns : children) 965 { 966 if (ns.type == node_type::directory_leaf) 967 return true; 968 } 969 970 return false; 971} 972 973template<typename _Key, typename _Value, typename _Trait> 974template<typename _NS> 975void rtree<_Key,_Value,_Trait>::search_results_base<_NS>::add_node_store( 976 node_store_type* ns, size_t depth) 977{ 978 m_store.emplace_back(ns, depth); 979} 980 981template<typename _Key, typename _Value, typename _Trait> 982template<typename _NS> 983rtree<_Key,_Value,_Trait>::search_results_base<_NS>::entry::entry(node_store_type* _ns, size_t _depth) : 984 ns(_ns), depth(_depth) {} 985 986template<typename _Key, typename _Value, typename _Trait> 987template<typename _SelfIter, typename _StoreIter, typename _ValueT> 988rtree<_Key,_Value,_Trait>::iterator_base<_SelfIter,_StoreIter,_ValueT>::iterator_base(store_iterator_type pos) : 989 m_pos(std::move(pos)) {} 990 991template<typename _Key, typename _Value, typename _Trait> 992template<typename _SelfIter, typename _StoreIter, typename _ValueT> 993bool rtree<_Key,_Value,_Trait>::iterator_base<_SelfIter,_StoreIter,_ValueT>::operator== (const self_iterator_type& other) const 994{ 995 return m_pos == other.m_pos; 996} 997 998template<typename _Key, typename _Value, typename _Trait> 999template<typename _SelfIter, typename _StoreIter, typename _ValueT> 1000bool rtree<_Key,_Value,_Trait>::iterator_base<_SelfIter,_StoreIter,_ValueT>::operator!= (const self_iterator_type& other) const 1001{ 1002 return !operator==(other); 1003} 1004 1005template<typename _Key, typename _Value, typename _Trait> 1006template<typename _SelfIter, typename _StoreIter, typename _ValueT> 1007typename rtree<_Key,_Value,_Trait>::template iterator_base<_SelfIter,_StoreIter,_ValueT>::self_iterator_type& 1008rtree<_Key,_Value,_Trait>::iterator_base<_SelfIter,_StoreIter,_ValueT>::operator++() 1009{ 1010 ++m_pos; 1011 return static_cast<self_iterator_type&>(*this); 1012} 1013 1014template<typename _Key, typename _Value, typename _Trait> 1015template<typename _SelfIter, typename _StoreIter, typename _ValueT> 1016typename rtree<_Key,_Value,_Trait>::template iterator_base<_SelfIter,_StoreIter,_ValueT>::self_iterator_type 1017rtree<_Key,_Value,_Trait>::iterator_base<_SelfIter,_StoreIter,_ValueT>::operator++(int) 1018{ 1019 self_iterator_type ret(m_pos); 1020 ++m_pos; 1021 return ret; 1022} 1023 1024template<typename _Key, typename _Value, typename _Trait> 1025template<typename _SelfIter, typename _StoreIter, typename _ValueT> 1026typename rtree<_Key,_Value,_Trait>::template iterator_base<_SelfIter,_StoreIter,_ValueT>::self_iterator_type& 1027rtree<_Key,_Value,_Trait>::iterator_base<_SelfIter,_StoreIter,_ValueT>::operator--() 1028{ 1029 --m_pos; 1030 return static_cast<self_iterator_type&>(*this); 1031} 1032 1033template<typename _Key, typename _Value, typename _Trait> 1034template<typename _SelfIter, typename _StoreIter, typename _ValueT> 1035typename rtree<_Key,_Value,_Trait>::template iterator_base<_SelfIter,_StoreIter,_ValueT>::self_iterator_type 1036rtree<_Key,_Value,_Trait>::iterator_base<_SelfIter,_StoreIter,_ValueT>::operator--(int) 1037{ 1038 self_iterator_type ret(m_pos); 1039 --m_pos; 1040 return ret; 1041} 1042 1043template<typename _Key, typename _Value, typename _Trait> 1044template<typename _SelfIter, typename _StoreIter, typename _ValueT> 1045const typename rtree<_Key,_Value,_Trait>::extent_type& 1046rtree<_Key,_Value,_Trait>::iterator_base<_SelfIter,_StoreIter,_ValueT>::extent() const 1047{ 1048 return m_pos->ns->extent; 1049} 1050 1051template<typename _Key, typename _Value, typename _Trait> 1052template<typename _SelfIter, typename _StoreIter, typename _ValueT> 1053size_t rtree<_Key,_Value,_Trait>::iterator_base<_SelfIter,_StoreIter,_ValueT>::depth() const 1054{ 1055 return m_pos->depth; 1056} 1057 1058template<typename _Key, typename _Value, typename _Trait> 1059typename rtree<_Key,_Value,_Trait>::const_iterator 1060rtree<_Key,_Value,_Trait>::const_search_results::cbegin() const 1061{ 1062 return const_iterator(m_store.cbegin()); 1063} 1064 1065template<typename _Key, typename _Value, typename _Trait> 1066typename rtree<_Key,_Value,_Trait>::const_iterator 1067rtree<_Key,_Value,_Trait>::const_search_results::cend() const 1068{ 1069 return const_iterator(m_store.cend()); 1070} 1071 1072template<typename _Key, typename _Value, typename _Trait> 1073typename rtree<_Key,_Value,_Trait>::const_iterator 1074rtree<_Key,_Value,_Trait>::const_search_results::begin() const 1075{ 1076 return const_iterator(m_store.cbegin()); 1077} 1078 1079template<typename _Key, typename _Value, typename _Trait> 1080typename rtree<_Key,_Value,_Trait>::const_iterator 1081rtree<_Key,_Value,_Trait>::const_search_results::end() const 1082{ 1083 return const_iterator(m_store.cend()); 1084} 1085 1086template<typename _Key, typename _Value, typename _Trait> 1087typename rtree<_Key,_Value,_Trait>::iterator 1088rtree<_Key,_Value,_Trait>::search_results::begin() 1089{ 1090 return iterator(m_store.begin()); 1091} 1092 1093template<typename _Key, typename _Value, typename _Trait> 1094typename rtree<_Key,_Value,_Trait>::iterator 1095rtree<_Key,_Value,_Trait>::search_results::end() 1096{ 1097 return iterator(m_store.end()); 1098} 1099 1100template<typename _Key, typename _Value, typename _Trait> 1101rtree<_Key,_Value,_Trait>::const_iterator::const_iterator(store_iterator_type pos) : 1102 base_type(std::move(pos)) {} 1103 1104template<typename _Key, typename _Value, typename _Trait> 1105typename rtree<_Key,_Value,_Trait>::const_iterator::value_type& 1106rtree<_Key,_Value,_Trait>::const_iterator::operator*() const 1107{ 1108 return static_cast<const value_node*>(m_pos->ns->node_ptr)->value; 1109} 1110 1111template<typename _Key, typename _Value, typename _Trait> 1112typename rtree<_Key,_Value,_Trait>::const_iterator::value_type* 1113rtree<_Key,_Value,_Trait>::const_iterator::operator->() const 1114{ 1115 return &operator*(); 1116} 1117 1118template<typename _Key, typename _Value, typename _Trait> 1119rtree<_Key,_Value,_Trait>::iterator::iterator(store_iterator_type pos) : 1120 base_type(std::move(pos)) {} 1121 1122template<typename _Key, typename _Value, typename _Trait> 1123typename rtree<_Key,_Value,_Trait>::iterator::value_type& 1124rtree<_Key,_Value,_Trait>::iterator::operator*() 1125{ 1126 return static_cast<value_node*>(m_pos->ns->node_ptr)->value; 1127} 1128 1129template<typename _Key, typename _Value, typename _Trait> 1130typename rtree<_Key,_Value,_Trait>::iterator::value_type* 1131rtree<_Key,_Value,_Trait>::iterator::operator->() 1132{ 1133 return &operator*(); 1134} 1135 1136template<typename _Key, typename _Value, typename _Trait> 1137rtree<_Key,_Value,_Trait>::bulk_loader::bulk_loader() 1138{ 1139} 1140 1141template<typename _Key, typename _Value, typename _Trait> 1142void rtree<_Key,_Value,_Trait>::bulk_loader::insert(const extent_type& extent, value_type&& value) 1143{ 1144 insert_impl(extent, std::move(value)); 1145} 1146 1147template<typename _Key, typename _Value, typename _Trait> 1148void rtree<_Key,_Value,_Trait>::bulk_loader::insert(const extent_type& extent, const value_type& value) 1149{ 1150 insert_impl(extent, value); 1151} 1152 1153template<typename _Key, typename _Value, typename _Trait> 1154void rtree<_Key,_Value,_Trait>::bulk_loader::insert(const point_type& position, value_type&& value) 1155{ 1156 insert_impl(extent_type({position, position}), std::move(value)); 1157} 1158 1159template<typename _Key, typename _Value, typename _Trait> 1160void rtree<_Key,_Value,_Trait>::bulk_loader::insert(const point_type& position, const value_type& value) 1161{ 1162 insert_impl(extent_type({position, position}), value); 1163} 1164 1165template<typename _Key, typename _Value, typename _Trait> 1166void rtree<_Key,_Value,_Trait>::bulk_loader::insert_impl(const extent_type& extent, value_type&& value) 1167{ 1168 node_store ns_value = node_store::create_value_node(extent, std::move(value)); 1169 m_store.emplace_back(std::move(ns_value)); 1170} 1171 1172template<typename _Key, typename _Value, typename _Trait> 1173void rtree<_Key,_Value,_Trait>::bulk_loader::insert_impl(const extent_type& extent, const value_type& value) 1174{ 1175 node_store ns_value = node_store::create_value_node(extent, value); 1176 m_store.emplace_back(std::move(ns_value)); 1177} 1178 1179template<typename _Key, typename _Value, typename _Trait> 1180rtree<_Key,_Value,_Trait> rtree<_Key,_Value,_Trait>::bulk_loader::pack() 1181{ 1182 size_t depth = 0; 1183 for (; m_store.size() > trait_type::max_node_size; ++depth) 1184 pack_level(m_store, depth); 1185 1186 // By this point, the number of directory nodes should have been reduced 1187 // below the max node size. Create a root directory and store them there. 1188 1189 assert(m_store.size() <= trait_type::max_node_size); 1190 1191 node_store root = node_store::create_leaf_directory_node(); 1192 if (depth > 0) 1193 root.type = node_type::directory_nonleaf; 1194 1195 directory_node* dir = root.get_directory_node(); 1196 assert(dir); 1197 dir->children.swap(m_store); 1198 1199 root.count = dir->children.size(); 1200 root.pack(); 1201 1202 rtree tree(std::move(root)); 1203 return tree; 1204} 1205 1206template<typename _Key, typename _Value, typename _Trait> 1207void rtree<_Key,_Value,_Trait>::bulk_loader::pack_level(dir_store_type& store, size_t depth) 1208{ 1209 assert(!store.empty()); 1210 1211 float n_total_node = std::ceil(store.size() / float(trait_type::max_node_size)); 1212 float n_splits_per_dim = std::ceil( 1213 std::pow(n_total_node, 1.0f / float(trait_type::dimensions))); 1214 1215 // The first dimension will start with one segment. 1216 std::vector<dir_store_segment> segments; 1217 segments.emplace_back(store.begin(), store.end(), store.size()); 1218 1219 for (size_t dim = 0; dim < trait_type::dimensions; ++dim) 1220 { 1221 if (segments[0].size <= trait_type::max_node_size) 1222 break; 1223 1224 std::vector<dir_store_segment> next_segments; 1225 1226 for (dir_store_segment& seg : segments) 1227 { 1228 assert(seg.size == size_t(std::distance(seg.begin, seg.end))); 1229 1230 if (seg.size <= trait_type::max_node_size) 1231 { 1232 next_segments.push_back(seg); 1233 continue; 1234 } 1235 1236 // Sort by the current dimension key. 1237 std::sort(seg.begin, seg.end, 1238 [dim](const node_store& left, const node_store& right) -> bool 1239 { 1240 // Compare the middle points. 1241 float left_key = (left.extent.end.d[dim] + left.extent.start.d[dim]) / 2.0f; 1242 float right_key = (right.extent.end.d[dim] + right.extent.start.d[dim]) / 2.0f; 1243 1244 return left_key < right_key; 1245 } 1246 ); 1247 1248 // Size of each segment in this dimension splits. 1249 size_t segment_size = detail::rtree::calc_optimal_segment_size_for_pack( 1250 std::ceil(seg.size / n_splits_per_dim), 1251 trait_type::min_node_size, trait_type::max_node_size, seg.size); 1252 1253 size_t n_cur_segment = 0; 1254 auto begin = seg.begin; 1255 for (auto it = begin; it != seg.end; ++it, ++n_cur_segment) 1256 { 1257 if (n_cur_segment == segment_size) 1258 { 1259 // Push a new segment. 1260 next_segments.emplace_back(begin, it, n_cur_segment); 1261 begin = it; 1262 n_cur_segment = 0; 1263 } 1264 } 1265 1266 if (begin != seg.end) 1267 { 1268 size_t n = std::distance(begin, seg.end); 1269 next_segments.emplace_back(begin, seg.end, n); 1270 } 1271 } 1272 1273#ifdef MDDS_RTREE_DEBUG 1274 size_t test_total = 0; 1275 for (const auto& seg : next_segments) 1276 test_total += seg.size; 1277 1278 if (test_total != store.size()) 1279 throw std::logic_error( 1280 "The total combined segment sizes must equal the size of the inserted values!"); 1281#endif 1282 segments.swap(next_segments); 1283 } 1284 1285#ifdef MDDS_RTREE_DEBUG 1286 // Check the final segment. 1287 size_t test_total = 0; 1288 for (const auto& seg : segments) 1289 test_total += seg.size; 1290 1291 if (test_total != store.size()) 1292 throw std::logic_error( 1293 "The total combined segment sizes must equal the size of the inserted values!"); 1294#endif 1295 1296 assert(!segments.empty()); 1297 1298 // Create a set of directory nodes from the current segments. 1299 dir_store_type next_store; 1300 for (dir_store_segment& seg : segments) 1301 { 1302 node_store ns = node_store::create_leaf_directory_node(); 1303 if (depth > 0) 1304 ns.type = node_type::directory_nonleaf; 1305 1306 directory_node* dir = ns.get_directory_node(); 1307 assert(dir); // this better not be null since we know it's a directory node. 1308 1309 for (auto it = seg.begin; it != seg.end; ++it) 1310 dir->children.push_back(std::move(*it)); 1311 1312 ns.count = dir->children.size(); 1313 ns.pack(); 1314 next_store.push_back(std::move(ns)); 1315 } 1316 1317 store.swap(next_store); 1318} 1319 1320template<typename _Key, typename _Value, typename _Trait> 1321rtree<_Key,_Value,_Trait>::rtree() : m_root(node_store::create_leaf_directory_node()) 1322{ 1323 static_assert(trait_type::min_node_size <= trait_type::max_node_size / 2, 1324 "Minimum node size must be less than half of the maximum node size."); 1325 1326 static_assert(trait_type::reinsertion_size <= (trait_type::max_node_size - trait_type::min_node_size + 1), 1327 "Reinsertion size is too large."); 1328} 1329 1330template<typename _Key, typename _Value, typename _Trait> 1331rtree<_Key,_Value,_Trait>::rtree(rtree&& other) : m_root(std::move(other.m_root)) 1332{ 1333 // The root node must be a valid directory at all times. 1334 other.m_root = node_store::create_leaf_directory_node(); 1335 1336 // Since the moved root has its memory location changed, we need to update 1337 // the parent pointers in its child nodes. 1338 m_root.reset_parent_pointers(); 1339} 1340 1341template<typename _Key, typename _Value, typename _Trait> 1342rtree<_Key,_Value,_Trait>::rtree(const rtree& other) : m_root(other.m_root.clone()) 1343{ 1344 m_root.reset_parent_pointers(); 1345} 1346 1347template<typename _Key, typename _Value, typename _Trait> 1348rtree<_Key,_Value,_Trait>::rtree(node_store&& root) : m_root(std::move(root)) 1349{ 1350 m_root.reset_parent_pointers(); 1351} 1352 1353template<typename _Key, typename _Value, typename _Trait> 1354rtree<_Key,_Value,_Trait>::~rtree() 1355{ 1356} 1357 1358template<typename _Key, typename _Value, typename _Trait> 1359rtree<_Key,_Value,_Trait>& rtree<_Key,_Value,_Trait>::operator= (const rtree& other) 1360{ 1361 rtree tmp(other); 1362 tmp.swap(*this); 1363 return *this; 1364} 1365 1366template<typename _Key, typename _Value, typename _Trait> 1367rtree<_Key,_Value,_Trait>& rtree<_Key,_Value,_Trait>::operator= (rtree&& other) 1368{ 1369 rtree tmp(std::move(other)); 1370 tmp.swap(*this); 1371 return *this; 1372} 1373 1374template<typename _Key, typename _Value, typename _Trait> 1375void rtree<_Key,_Value,_Trait>::insert(const extent_type& extent, value_type&& value) 1376{ 1377 insert_impl(extent.start, extent.end, std::move(value)); 1378} 1379 1380template<typename _Key, typename _Value, typename _Trait> 1381void rtree<_Key,_Value,_Trait>::insert(const extent_type& extent, const value_type& value) 1382{ 1383 insert_impl(extent.start, extent.end, value); 1384} 1385 1386template<typename _Key, typename _Value, typename _Trait> 1387void rtree<_Key,_Value,_Trait>::insert(const point_type& position, value_type&& value) 1388{ 1389 insert_impl(position, position, std::move(value)); 1390} 1391 1392template<typename _Key, typename _Value, typename _Trait> 1393void rtree<_Key,_Value,_Trait>::insert(const point_type& position, const value_type& value) 1394{ 1395 insert_impl(position, position, value); 1396} 1397 1398template<typename _Key, typename _Value, typename _Trait> 1399void rtree<_Key,_Value,_Trait>::insert_impl(const point_type& start, const point_type& end, value_type&& value) 1400{ 1401 extent_type bb(start, end); 1402 node_store new_ns = node_store::create_value_node(bb, std::move(value)); 1403 1404 std::unordered_set<size_t> reinserted_depths; 1405 insert(std::move(new_ns), &reinserted_depths); 1406} 1407 1408template<typename _Key, typename _Value, typename _Trait> 1409void rtree<_Key,_Value,_Trait>::insert_impl(const point_type& start, const point_type& end, const value_type& value) 1410{ 1411 extent_type bb(start, end); 1412 node_store new_ns = node_store::create_value_node(bb, value); 1413 1414 std::unordered_set<size_t> reinserted_depths; 1415 insert(std::move(new_ns), &reinserted_depths); 1416} 1417 1418template<typename _Key, typename _Value, typename _Trait> 1419void rtree<_Key,_Value,_Trait>::insert(node_store&& ns, std::unordered_set<size_t>* reinserted_depths) 1420{ 1421 extent_type ns_box = ns.extent; 1422 1423 insertion_point insert_pt = find_leaf_directory_node_for_insertion(ns_box); 1424 node_store* dir_ns = insert_pt.ns; 1425 size_t depth = insert_pt.depth; 1426 1427 assert(dir_ns); 1428 assert(dir_ns->type == node_type::directory_leaf); 1429 directory_node* dir = static_cast<directory_node*>(dir_ns->node_ptr); 1430 1431 // Insert the new value to this node. 1432 ns.parent = insert_pt.ns; 1433 dir->children.push_back(std::move(ns)); 1434 ++dir_ns->count; 1435 1436 if (dir_ns->exceeds_capacity()) 1437 { 1438 if (trait_type::enable_forced_reinsertion) 1439 { 1440 if (reinserted_depths && !reinserted_depths->count(depth)) 1441 { 1442 // We perform forced re-insertion exactly once per depth level. 1443 reinserted_depths->insert(depth); 1444 perform_forced_reinsertion(dir_ns, *reinserted_depths); 1445 } 1446 else 1447 split_node(dir_ns); 1448 } 1449 else 1450 split_node(dir_ns); 1451 1452 return; 1453 } 1454 1455 if (dir_ns->count == 1) 1456 dir_ns->extent = ns_box; 1457 else 1458 detail::rtree::enlarge_extent_to_fit<extent_type>(dir_ns->extent, ns_box); 1459 1460 extent_type bb = dir_ns->extent; // grab the parent bounding box. 1461 1462 // Propagate the bounding box update up the tree all the way to the root. 1463 for (dir_ns = dir_ns->parent; dir_ns; dir_ns = dir_ns->parent) 1464 { 1465 assert(dir_ns->count > 0); 1466 detail::rtree::enlarge_extent_to_fit<extent_type>(dir_ns->extent, bb); 1467 } 1468} 1469 1470template<typename _Key, typename _Value, typename _Trait> 1471void rtree<_Key,_Value,_Trait>::insert_dir(node_store&& ns, size_t max_depth) 1472{ 1473 assert(ns.is_directory()); 1474 extent_type ns_box = ns.extent; 1475 node_store* dir_ns = find_nonleaf_directory_node_for_insertion(ns_box, max_depth); 1476 assert(dir_ns); 1477 assert(dir_ns->type == node_type::directory_nonleaf); 1478 directory_node* dir = static_cast<directory_node*>(dir_ns->node_ptr); 1479 1480 // Insert the new directory to this node. 1481 ns.parent = dir_ns; 1482 ns.valid_pointer = false; 1483 dir->children.push_back(std::move(ns)); 1484 ++dir_ns->count; 1485 dir->children.back().reset_parent_pointers_of_children(); 1486 1487 if (dir_ns->exceeds_capacity()) 1488 { 1489 split_node(dir_ns); 1490 return; 1491 } 1492 1493 if (dir_ns->count == 1) 1494 dir_ns->extent = ns_box; 1495 else 1496 detail::rtree::enlarge_extent_to_fit<extent_type>(dir_ns->extent, ns_box); 1497 1498 extent_type bb = dir_ns->extent; // grab the parent bounding box. 1499 1500 // Propagate the bounding box update up the tree all the way to the root. 1501 for (dir_ns = dir_ns->parent; dir_ns; dir_ns = dir_ns->parent) 1502 { 1503 assert(dir_ns->count > 0); 1504 detail::rtree::enlarge_extent_to_fit<extent_type>(dir_ns->extent, bb); 1505 } 1506} 1507 1508template<typename _Key, typename _Value, typename _Trait> 1509typename rtree<_Key,_Value,_Trait>::const_search_results 1510rtree<_Key,_Value,_Trait>::search(const point_type& pt, search_type st) const 1511{ 1512 search_condition_type dir_cond, value_cond; 1513 1514 switch (st) 1515 { 1516 case search_type::overlap: 1517 { 1518 dir_cond = [&pt](const node_store& ns) -> bool 1519 { 1520 return ns.extent.contains(pt); 1521 }; 1522 1523 value_cond = dir_cond; 1524 break; 1525 } 1526 case search_type::match: 1527 { 1528 dir_cond = [&pt](const node_store& ns) -> bool 1529 { 1530 return ns.extent.contains(pt); 1531 }; 1532 1533 value_cond = [&pt](const node_store& ns) -> bool 1534 { 1535 return ns.extent.start == pt && ns.extent.end == pt; 1536 }; 1537 1538 break; 1539 } 1540 default: 1541 throw std::runtime_error("Unhandled search type."); 1542 } 1543 1544 const_search_results ret; 1545 search_descend(0, dir_cond, value_cond, m_root, ret); 1546 return ret; 1547} 1548 1549template<typename _Key, typename _Value, typename _Trait> 1550typename rtree<_Key,_Value,_Trait>::search_results 1551rtree<_Key,_Value,_Trait>::search(const point_type& pt, search_type st) 1552{ 1553 search_condition_type dir_cond, value_cond; 1554 1555 switch (st) 1556 { 1557 case search_type::overlap: 1558 { 1559 dir_cond = [&pt](const node_store& ns) -> bool 1560 { 1561 return ns.extent.contains(pt); 1562 }; 1563 1564 value_cond = dir_cond; 1565 break; 1566 } 1567 case search_type::match: 1568 { 1569 dir_cond = [&pt](const node_store& ns) -> bool 1570 { 1571 return ns.extent.contains(pt); 1572 }; 1573 1574 value_cond = [&pt](const node_store& ns) -> bool 1575 { 1576 return ns.extent.start == pt && ns.extent.end == pt; 1577 }; 1578 1579 break; 1580 } 1581 default: 1582 throw std::runtime_error("Unhandled search type."); 1583 } 1584 1585 search_results ret; 1586 search_descend(0, dir_cond, value_cond, m_root, ret); 1587 return ret; 1588} 1589 1590template<typename _Key, typename _Value, typename _Trait> 1591typename rtree<_Key,_Value,_Trait>::const_search_results 1592rtree<_Key,_Value,_Trait>::search(const extent_type& extent, search_type st) const 1593{ 1594 search_condition_type dir_cond, value_cond; 1595 1596 switch (st) 1597 { 1598 case search_type::overlap: 1599 { 1600 dir_cond = [&extent](const node_store& ns) -> bool 1601 { 1602 return ns.extent.intersects(extent); 1603 }; 1604 1605 value_cond = dir_cond; 1606 break; 1607 } 1608 case search_type::match: 1609 { 1610 dir_cond = [&extent](const node_store& ns) -> bool 1611 { 1612 return ns.extent.contains(extent); 1613 }; 1614 1615 value_cond = [&extent](const node_store& ns) -> bool 1616 { 1617 return ns.extent == extent; 1618 }; 1619 1620 break; 1621 } 1622 default: 1623 throw std::runtime_error("Unhandled search type."); 1624 } 1625 1626 const_search_results ret; 1627 search_descend(0, dir_cond, value_cond, m_root, ret); 1628 return ret; 1629} 1630 1631template<typename _Key, typename _Value, typename _Trait> 1632typename rtree<_Key,_Value,_Trait>::search_results 1633rtree<_Key,_Value,_Trait>::search(const extent_type& extent, search_type st) 1634{ 1635 search_condition_type dir_cond, value_cond; 1636 1637 switch (st) 1638 { 1639 case search_type::overlap: 1640 { 1641 dir_cond = [&extent](const node_store& ns) -> bool 1642 { 1643 return ns.extent.intersects(extent); 1644 }; 1645 1646 value_cond = dir_cond; 1647 break; 1648 } 1649 case search_type::match: 1650 { 1651 dir_cond = [&extent](const node_store& ns) -> bool 1652 { 1653 return ns.extent.contains(extent); 1654 }; 1655 1656 value_cond = [&extent](const node_store& ns) -> bool 1657 { 1658 return ns.extent == extent; 1659 }; 1660 1661 break; 1662 } 1663 default: 1664 throw std::runtime_error("Unhandled search type."); 1665 } 1666 1667 search_results ret; 1668 search_descend(0, dir_cond, value_cond, m_root, ret); 1669 return ret; 1670} 1671 1672template<typename _Key, typename _Value, typename _Trait> 1673void rtree<_Key,_Value,_Trait>::erase(const const_iterator& pos) 1674{ 1675 const node_store* ns = pos.m_pos->ns; 1676 size_t depth = pos.m_pos->depth; 1677 erase_impl(ns, depth); 1678} 1679 1680template<typename _Key, typename _Value, typename _Trait> 1681void rtree<_Key,_Value,_Trait>::erase(const iterator& pos) 1682{ 1683 const node_store* ns = pos.m_pos->ns; 1684 size_t depth = pos.m_pos->depth; 1685 erase_impl(ns, depth); 1686} 1687 1688template<typename _Key, typename _Value, typename _Trait> 1689void rtree<_Key,_Value,_Trait>::erase_impl(const node_store* ns, size_t depth) 1690{ 1691 assert(ns->type == node_type::value); 1692 assert(ns->parent); 1693 1694 extent_type bb_erased = ns->extent; 1695 1696 // Move up to the parent and find its stored location. 1697 node_store* dir_ns = ns->parent; 1698 --depth; 1699 assert(dir_ns->type == node_type::directory_leaf); 1700 bool erased = dir_ns->erase_child(ns); 1701 assert(erased); 1702 (void)erased; // to avoid getting a warning on "variable set but not used". 1703 1704 if (dir_ns->is_root()) 1705 { 1706 shrink_tree_upward(dir_ns, bb_erased); 1707 return; 1708 } 1709 1710 if (dir_ns->count >= trait_type::min_node_size) 1711 { 1712 // The parent directory still contains enough nodes. No need to dissolve it. 1713 shrink_tree_upward(dir_ns, bb_erased); 1714 return; 1715 } 1716 1717 // Dissolve the node the erased value node belongs to, and reinsert 1718 // all its siblings. 1719 1720 assert(!dir_ns->is_root()); 1721 assert(dir_ns->count < trait_type::min_node_size); 1722 1723 dir_store_type orphan_value_nodes; 1724 directory_node* dir = static_cast<directory_node*>(dir_ns->node_ptr); 1725 dir->children.swap(orphan_value_nodes); // moves all the rest of the value node entries to the orphan store. 1726 1727 // Move up one level, and remove this directory node from its parent directory node. 1728 node_store* child_ns = dir_ns; 1729 dir_ns = dir_ns->parent; 1730 --depth; 1731 erased = dir_ns->erase_child(child_ns); 1732 assert(erased); 1733 1734 dir_ns->reset_parent_pointers(); 1735 dir_ns->pack(); 1736 1737 orphan_node_entries_type orphan_dir_nodes; 1738 1739 while (!dir_ns->is_root() && dir_ns->count < trait_type::min_node_size) 1740 { 1741 // This directory node is now underfilled. Move all its children out 1742 // for re-insertion and dissolve this node. 1743 dir = static_cast<directory_node*>(dir_ns->node_ptr); 1744 1745 while (!dir->children.empty()) 1746 { 1747 orphan_dir_nodes.emplace_back(); 1748 orphan_dir_nodes.back().ns.swap(dir->children.back()); 1749 orphan_dir_nodes.back().depth = depth + 1; // depth of the children. 1750 dir->children.pop_back(); 1751 } 1752 1753 // Find and remove this node from its parent store. 1754 node_store* dir_ns_child = dir_ns; 1755 dir_ns = dir_ns->parent; 1756 --depth; 1757 erased = dir_ns->erase_child(dir_ns_child); 1758 assert(erased); 1759 dir_ns->reset_parent_pointers_of_children(); 1760 dir_ns->pack(); 1761 } 1762 1763 while (!orphan_dir_nodes.empty()) 1764 { 1765 orphan_node_entry& entry = orphan_dir_nodes.back(); 1766 insert_dir(std::move(entry.ns), entry.depth); 1767 orphan_dir_nodes.pop_back(); 1768 } 1769 1770 while (!orphan_value_nodes.empty()) 1771 { 1772 insert(std::move(orphan_value_nodes.back()), nullptr); 1773 orphan_value_nodes.pop_back(); 1774 } 1775 1776 if (m_root.count == 1) 1777 { 1778 // If the root node only has one child, make that child the new root. 1779 // Be careful not to leak memory here... 1780 1781 dir = static_cast<directory_node*>(m_root.node_ptr); 1782 assert(dir->children.size() == 1); 1783 node_store new_root(std::move(dir->children.back())); 1784 dir->children.clear(); 1785 1786 new_root.parent = nullptr; 1787 m_root.swap(new_root); 1788 m_root.reset_parent_pointers(); 1789 } 1790} 1791 1792template<typename _Key, typename _Value, typename _Trait> 1793const typename rtree<_Key,_Value,_Trait>::extent_type& 1794rtree<_Key,_Value,_Trait>::extent() const 1795{ 1796 return m_root.extent; 1797} 1798 1799template<typename _Key, typename _Value, typename _Trait> 1800bool rtree<_Key,_Value,_Trait>::empty() const 1801{ 1802 return !m_root.count; 1803} 1804 1805template<typename _Key, typename _Value, typename _Trait> 1806size_t rtree<_Key,_Value,_Trait>::size() const 1807{ 1808 size_t n = 0; 1809 descend_with_func( 1810 [&n](const node_properties& np) 1811 { 1812 if (np.type == node_type::value) 1813 ++n; 1814 } 1815 ); 1816 1817 return n; 1818} 1819 1820template<typename _Key, typename _Value, typename _Trait> 1821void rtree<_Key,_Value,_Trait>::swap(rtree& other) 1822{ 1823 m_root.swap(other.m_root); 1824 m_root.reset_parent_pointers(); 1825 other.m_root.reset_parent_pointers(); 1826} 1827 1828template<typename _Key, typename _Value, typename _Trait> 1829void rtree<_Key,_Value,_Trait>::clear() 1830{ 1831 node_store new_root = node_store::create_leaf_directory_node(); 1832 m_root.swap(new_root); 1833} 1834 1835template<typename _Key, typename _Value, typename _Trait> 1836template<typename _Func> 1837void rtree<_Key,_Value,_Trait>::walk(_Func func) const 1838{ 1839 descend_with_func(std::move(func)); 1840} 1841 1842template<typename _Key, typename _Value, typename _Trait> 1843void rtree<_Key,_Value,_Trait>::check_integrity(const integrity_check_properties& props) const 1844{ 1845 auto func_ptr_to_string = build_ptr_to_string_map(); 1846 1847 switch (m_root.type) 1848 { 1849 case node_type::directory_leaf: 1850 case node_type::directory_nonleaf: 1851 // Good. 1852 break; 1853 default: 1854 throw integrity_error("The root node must be a directory node."); 1855 } 1856 1857 if (m_root.parent) 1858 throw integrity_error("The root node should not have a non-null parent."); 1859 1860 std::vector<const node_store*> ns_stack; 1861 1862 std::function<bool(const node_store*, int)> func_descend = [&ns_stack,&func_descend,&func_ptr_to_string,&props](const node_store* ns, int level) -> bool 1863 { 1864 bool valid = true; 1865 1866 std::string indent; 1867 for (int i = 0; i < level; ++i) 1868 indent += " "; 1869 1870 const node_store* parent = nullptr; 1871 extent_type parent_bb; 1872 if (!ns_stack.empty()) 1873 { 1874 parent = ns_stack.back(); 1875 parent_bb = parent->extent; 1876 } 1877 1878 if (!props.throw_on_first_error) 1879 { 1880 std::cout << indent << "node: " << func_ptr_to_string(ns) 1881 << "; parent: " << func_ptr_to_string(ns->parent) 1882 << "; type: " << to_string(ns->type) 1883 << "; extent: " << ns->extent.to_string() << std::endl; 1884 } 1885 1886 if (parent) 1887 { 1888 if (ns->parent != parent) 1889 { 1890 std::ostringstream os; 1891 os << "The parent node pointer does not point to the real parent. (expected: " << parent << "; stored in node: " << ns->parent << ")"; 1892 if (props.throw_on_first_error) 1893 throw integrity_error(os.str()); 1894 std::cout << indent << "* " << os.str() << std::endl; 1895 valid = false; 1896 } 1897 1898 if (!parent_bb.contains(ns->extent)) 1899 { 1900 std::ostringstream os; 1901 os << "The extent of the child " << ns->extent.to_string() << " is not within the extent of the parent " << parent_bb.to_string() << "."; 1902 if (props.throw_on_first_error) 1903 throw integrity_error(os.str()); 1904 std::cout << indent << "* " << os.str() << std::endl; 1905 valid = false; 1906 } 1907 1908 switch (ns->type) 1909 { 1910 case node_type::directory_leaf: 1911 { 1912 if (parent->type != node_type::directory_nonleaf) 1913 { 1914 std::ostringstream os; 1915 os << "Parent of a leaf directory node must be non-leaf."; 1916 if (props.throw_on_first_error) 1917 throw integrity_error(os.str()); 1918 std::cout << indent << "* " << os.str() << std::endl; 1919 valid = false; 1920 } 1921 break; 1922 } 1923 case node_type::directory_nonleaf: 1924 { 1925 if (parent->type != node_type::directory_nonleaf) 1926 { 1927 std::ostringstream os; 1928 os << "Parent of a non-leaf directory node must also be non-leaf."; 1929 if (props.throw_on_first_error) 1930 throw integrity_error(os.str()); 1931 std::cout << indent << "* " << os.str() << std::endl; 1932 valid = false; 1933 } 1934 break; 1935 } 1936 case node_type::value: 1937 { 1938 if (parent->type != node_type::directory_leaf) 1939 { 1940 std::ostringstream os; 1941 os << "Parent of a value node must be a leaf directory node."; 1942 if (props.throw_on_first_error) 1943 throw integrity_error(os.str()); 1944 std::cout << indent << "* " << os.str() << std::endl; 1945 valid = false; 1946 } 1947 break; 1948 } 1949 default: 1950 throw integrity_error("Unexpected node type!"); 1951 } 1952 } 1953 1954 ns_stack.push_back(ns); 1955 1956 switch (ns->type) 1957 { 1958 case node_type::directory_leaf: 1959 case node_type::directory_nonleaf: 1960 { 1961 const directory_node* dir = 1962 static_cast<const directory_node*>(ns->node_ptr); 1963 1964 if (ns->count != dir->children.size()) 1965 { 1966 std::ostringstream os; 1967 os << "Incorrect count of child nodes detected. (expected: " << dir->children.size() << "; actual: " << ns->count << ")"; 1968 1969 if (props.throw_on_first_error) 1970 throw integrity_error(os.str()); 1971 1972 std::cout << indent << "* " << os.str() << std::endl; 1973 valid = false; 1974 } 1975 1976 bool node_underfill_allowed = false; 1977 if (ns->is_root() && ns->type == node_type::directory_leaf) 1978 // If the root directory is a leaf, it's allowed to be underfilled. 1979 node_underfill_allowed = true; 1980 1981 if (!node_underfill_allowed && ns->count < trait_type::min_node_size) 1982 { 1983 std::ostringstream os; 1984 os << "The number of child nodes (" << ns->count << ") is less than the minimum allowed number of " 1985 << trait_type::min_node_size; 1986 1987 if (props.error_on_min_node_size && props.throw_on_first_error) 1988 throw integrity_error(os.str()); 1989 1990 std::cout << indent << "* " << os.str() << std::endl; 1991 1992 if (props.error_on_min_node_size) 1993 valid = false; 1994 } 1995 1996 if (trait_type::max_node_size < ns->count) 1997 { 1998 std::ostringstream os; 1999 os << "The number of child nodes (" << ns->count << ") exceeds the maximum allowed number of " 2000 << trait_type::max_node_size; 2001 2002 if (props.throw_on_first_error) 2003 throw integrity_error(os.str()); 2004 2005 std::cout << indent << "* " << os.str() << std::endl; 2006 valid = false; 2007 } 2008 2009 // Check to make sure the bounding box of the current node is 2010 // tightly packed. 2011 extent_type bb_expected = dir->calc_extent(); 2012 2013 if (bb_expected != ns->extent) 2014 { 2015 std::ostringstream os; 2016 os << "The extent of the node " << ns->extent.to_string() << " does not equal truly tight extent " << bb_expected.to_string(); 2017 2018 if (props.throw_on_first_error) 2019 throw integrity_error(os.str()); 2020 2021 std::cout << indent << "* " << os.str() << std::endl; 2022 valid = false; 2023 } 2024 2025 for (const node_store& ns_child : dir->children) 2026 { 2027 bool valid_subtree = func_descend(&ns_child, level+1); 2028 if (!valid_subtree) 2029 valid = false; 2030 } 2031 2032 break; 2033 } 2034 case node_type::value: 2035 // Do nothing. 2036 break; 2037 default: 2038 throw integrity_error("Unexpected node type!"); 2039 } 2040 2041 ns_stack.pop_back(); 2042 2043 return valid; 2044 }; 2045 2046 bool valid = func_descend(&m_root, 0); 2047 2048 if (!valid) 2049 throw integrity_error("Tree contains one or more errors."); 2050} 2051 2052template<typename _Key, typename _Value, typename _Trait> 2053std::string rtree<_Key,_Value,_Trait>::export_tree(export_tree_type mode) const 2054{ 2055 switch (mode) 2056 { 2057 case export_tree_type::formatted_node_properties: 2058 return export_tree_formatted(); 2059 case export_tree_type::extent_as_obj: 2060 return export_tree_extent_as_obj(); 2061 case export_tree_type::extent_as_svg: 2062 return export_tree_extent_as_svg(); 2063 default: 2064 throw std::runtime_error("unhandled export tree type."); 2065 } 2066} 2067 2068template<typename _Key, typename _Value, typename _Trait> 2069detail::rtree::ptr_to_string<const typename rtree<_Key,_Value,_Trait>::node_store*> 2070rtree<_Key,_Value,_Trait>::build_ptr_to_string_map() const 2071{ 2072 detail::rtree::ptr_to_string<const node_store*> func; 2073 2074 std::function<void(const node_store*, int, int)> func_build_node_ptr = [&func_build_node_ptr,&func](const node_store* ns, int level, int pos) 2075 { 2076 std::ostringstream os; 2077 os << "(" << level << ", " << pos << ")"; 2078 func.node_ptr_map.insert(std::make_pair(ns, os.str())); 2079 2080 switch (ns->type) 2081 { 2082 case node_type::directory_leaf: 2083 case node_type::directory_nonleaf: 2084 { 2085 const directory_node* dir = 2086 static_cast<const directory_node*>(ns->node_ptr); 2087 2088 int child_pos = 0; 2089 for (const node_store& ns_child : dir->children) 2090 func_build_node_ptr(&ns_child, level+1, child_pos++); 2091 2092 break; 2093 } 2094 case node_type::value: 2095 // Do nothing. 2096 break; 2097 default: 2098 throw integrity_error("Unexpected node type!"); 2099 } 2100 }; 2101 2102 func_build_node_ptr(&m_root, 0, 0); 2103 2104 return func; 2105} 2106 2107template<typename _Key, typename _Value, typename _Trait> 2108std::string rtree<_Key,_Value,_Trait>::export_tree_formatted() const 2109{ 2110 auto func_ptr_to_string = build_ptr_to_string_map(); 2111 2112 std::ostringstream os; 2113 2114 std::function<void(const node_store*, int)> func_descend = [&func_descend,&os,&func_ptr_to_string](const node_store* ns, int level) 2115 { 2116 std::string indent; 2117 for (int i = 0; i < level; ++i) 2118 indent += " "; 2119 2120 os << indent << "node: " << func_ptr_to_string(ns) << "; parent: " << func_ptr_to_string(ns->parent) 2121 << "; type: " << to_string(ns->type) << "; extent: " << ns->extent.to_string() << std::endl; 2122 2123 switch (ns->type) 2124 { 2125 case node_type::directory_leaf: 2126 case node_type::directory_nonleaf: 2127 { 2128 const directory_node* dir = 2129 static_cast<const directory_node*>(ns->node_ptr); 2130 2131 for (const node_store& ns_child : dir->children) 2132 func_descend(&ns_child, level+1); 2133 2134 break; 2135 } 2136 case node_type::value: 2137 // Do nothing. 2138 break; 2139 default: 2140 throw integrity_error("Unexpected node type!"); 2141 } 2142 }; 2143 2144 func_descend(&m_root, 0); 2145 2146 return os.str(); 2147} 2148 2149template<typename _Key, typename _Value, typename _Trait> 2150std::string rtree<_Key,_Value,_Trait>::export_tree_extent_as_obj() const 2151{ 2152 if (trait_type::dimensions != 2u) 2153 throw size_error("Only 2-dimensional trees are supported."); 2154 2155 float unit_height = 2156 ((m_root.extent.end.d[0] - m_root.extent.start.d[0]) + 2157 (m_root.extent.end.d[1] - m_root.extent.start.d[1])) / 5.0f; 2158 2159 // Calculate the width to use for point data. 2160 float pt_width = std::min<float>( 2161 m_root.extent.end.d[0] - m_root.extent.start.d[0], 2162 m_root.extent.end.d[1] - m_root.extent.start.d[1]); 2163 pt_width /= 400.0f; 2164 pt_width = std::min<float>(pt_width, 1.0f); 2165 2166 std::ostringstream os; 2167 size_t counter = 0; 2168 2169 std::function<void(const node_store*, int)> func_descend = [&](const node_store* ns, int level) 2170 { 2171 size_t offset = counter * 4; 2172 point_type s = ns->extent.start; 2173 point_type e = ns->extent.end; 2174 if (s == e) 2175 { 2176 s.d[0] -= pt_width; 2177 s.d[1] -= pt_width; 2178 e.d[0] += pt_width; 2179 e.d[1] += pt_width; 2180 } 2181 2182 os << "o extent " << counter << " (level " << level << ") " << s.to_string() << " - " << e.to_string() << std::endl; 2183 os << "v " << s.d[0] << ' ' << (level*unit_height) << ' ' << s.d[1] << std::endl; 2184 os << "v " << s.d[0] << ' ' << (level*unit_height) << ' ' << e.d[1] << std::endl; 2185 os << "v " << e.d[0] << ' ' << (level*unit_height) << ' ' << e.d[1] << std::endl; 2186 os << "v " << e.d[0] << ' ' << (level*unit_height) << ' ' << s.d[1] << std::endl; 2187 os << "f " << (offset+1) << ' ' << (offset+2) << ' ' << (offset+3) << ' ' << (offset+4) << std::endl; 2188 2189 ++counter; 2190 2191 switch (ns->type) 2192 { 2193 case node_type::directory_leaf: 2194 case node_type::directory_nonleaf: 2195 { 2196 const directory_node* dir = 2197 static_cast<const directory_node*>(ns->node_ptr); 2198 2199 for (const node_store& ns_child : dir->children) 2200 func_descend(&ns_child, level+1); 2201 2202 break; 2203 } 2204 case node_type::value: 2205 // Do nothing. 2206 break; 2207 default: 2208 throw integrity_error("Unexpected node type!"); 2209 } 2210 }; 2211 2212 func_descend(&m_root, 0); 2213 2214 return os.str(); 2215} 2216 2217template<typename _Key, typename _Value, typename _Trait> 2218std::string rtree<_Key,_Value,_Trait>::export_tree_extent_as_svg() const 2219{ 2220 if (trait_type::dimensions != 2u) 2221 throw size_error("Only 2-dimensional trees are supported."); 2222 2223 constexpr float min_avg_root_length = 800.0f; 2224 constexpr float max_avg_root_length = 1000.0f; 2225 float root_w = m_root.extent.end.d[0] - m_root.extent.start.d[0]; 2226 float root_h = m_root.extent.end.d[1] - m_root.extent.start.d[1]; 2227 2228 // Adjust zooming for optimal output size. We don't want it to be too 2229 // large or too small. 2230 float zoom_ratio = 1.0; 2231 float root_avg = (root_w + root_h) / 2.0f; 2232 if (root_avg >= max_avg_root_length) 2233 zoom_ratio = max_avg_root_length / root_avg; 2234 if (root_avg <= min_avg_root_length) 2235 zoom_ratio = min_avg_root_length / root_avg; 2236 2237 root_w *= zoom_ratio; 2238 root_h *= zoom_ratio; 2239 float root_x = m_root.extent.start.d[0] * zoom_ratio; 2240 float root_y = m_root.extent.start.d[1] * zoom_ratio; 2241 float r = root_avg / 100.0f * zoom_ratio; 2242 float stroke_w = r / 10.0f; // stroke width 2243 2244 const std::string indent = " "; 2245 2246 // Uniform attributes to use for all drawing objects. 2247 2248 std::string attrs_dir; 2249 { 2250 std::ostringstream os; 2251 os << " stroke=\"#999999\" stroke-width=\"" << stroke_w << "\" fill=\"green\" fill-opacity=\"0.05\""; 2252 attrs_dir = os.str(); 2253 } 2254 2255 std::string attrs_value; 2256 { 2257 std::ostringstream os; 2258 os << " stroke=\"brown\" stroke-width=\"" << stroke_w << "\" fill=\"brown\" fill-opacity=\"0.2\""; 2259 attrs_value = os.str(); 2260 } 2261 2262 std::ostringstream os; 2263 os << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"; 2264 os << "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n"; 2265 2266 std::function<void(const node_store*, int)> func_descend = [&](const node_store* ns, int level) 2267 { 2268 const extent_type& ext = ns->extent; 2269 2270 float w = ext.end.d[0] - ext.start.d[0]; 2271 float h = ext.end.d[1] - ext.start.d[1]; 2272 float x = ext.start.d[0]; 2273 float y = ext.start.d[1]; 2274 w *= zoom_ratio; 2275 h *= zoom_ratio; 2276 x *= zoom_ratio; 2277 y *= zoom_ratio; 2278 x -= root_x; 2279 y -= root_y; 2280 2281 if (level > 0) 2282 { 2283 const char* attrs = (ns->type == node_type::value) ? attrs_value.data() : attrs_dir.data(); 2284 2285 if (ext.is_point()) 2286 { 2287 os << indent << "<circle cx=\"" << x << "\" cy=\"" << y << "\" r=\"" << r << "\"" << attrs << "/>\n"; 2288 } 2289 else 2290 { 2291 os << indent << "<rect x=\"" << x << "\" y=\"" << y << "\" width=\"" << w << "\" height=\"" << h << "\"" 2292 << attrs << "/>\n"; 2293 } 2294 } 2295 2296 switch (ns->type) 2297 { 2298 case node_type::directory_leaf: 2299 case node_type::directory_nonleaf: 2300 { 2301 const directory_node* dir = 2302 static_cast<const directory_node*>(ns->node_ptr); 2303 2304 for (const node_store& ns_child : dir->children) 2305 func_descend(&ns_child, level+1); 2306 2307 break; 2308 } 2309 case node_type::value: 2310 // Do nothing. 2311 break; 2312 default: 2313 throw integrity_error("Unexpected node type!"); 2314 } 2315 }; 2316 2317 os << "<svg version=\"1.2\" width=\"" << root_w << "\" height=\"" << root_h << "\">\n"; 2318 func_descend(&m_root, 0); 2319 os << "</svg>"; 2320 2321 return os.str(); 2322} 2323 2324template<typename _Key, typename _Value, typename _Trait> 2325void rtree<_Key,_Value,_Trait>::split_node(node_store* ns) 2326{ 2327 directory_node* dir = ns->get_directory_node(); 2328 2329 assert(dir); 2330 assert(ns->count == trait_type::max_node_size+1); 2331 2332 dir_store_type& children = dir->children; 2333 2334 sort_dir_store_by_split_dimension(children); 2335 2336 size_t dist = pick_optimal_distribution(children); 2337 distribution dist_picked(dist, children); 2338 2339 // Move the child nodes in group 2 into a brand-new sibling node. 2340 node_store node_g2 = node_store::create_leaf_directory_node(); 2341 node_g2.type = ns->type; 2342 directory_node* dir_sibling = static_cast<directory_node*>(node_g2.node_ptr); 2343 2344 for (auto it = dist_picked.g2.begin; it != dist_picked.g2.end; ++it) 2345 { 2346 assert(!it->valid_pointer); 2347 dir_sibling->children.push_back(std::move(*it)); 2348 } 2349 2350 node_g2.count = dir_sibling->children.size(); 2351 node_g2.pack(); 2352 2353 // Remove the nodes in group 2 from the original node by shrinking the node store. 2354 ns->count = dist_picked.g1.size; 2355 assert(dist_picked.g1.size < dir->children.size()); 2356 dir->children.resize(dist_picked.g1.size); 2357 ns->pack(); // Re-calculate the bounding box. 2358 2359 if (ns->is_root()) 2360 { 2361 // Create a new root node and make it the parent of the original root 2362 // and the new sibling nodes. 2363 assert(ns == &m_root); 2364 node_store node_g1 = node_store::create_nonleaf_directory_node(); 2365 m_root.swap(node_g1); 2366 node_g1.parent = &m_root; 2367 node_g2.parent = &m_root; 2368 directory_node* dir_root = static_cast<directory_node*>(m_root.node_ptr); 2369 dir_root->children.emplace_back(std::move(node_g1)); 2370 dir_root->children.emplace_back(std::move(node_g2)); 2371 m_root.count = 2; 2372 m_root.pack(); 2373 2374 for (node_store& ns_child : dir_root->children) 2375 ns_child.reset_parent_pointers_of_children(); 2376 } 2377 else 2378 { 2379 // Place the new sibling (node_g2) under the same parent as ns. 2380 assert(ns->parent); 2381 node_g2.parent = ns->parent; 2382 node_store* ns_parent = ns->parent; 2383 assert(ns_parent->type == node_type::directory_nonleaf); 2384 directory_node* dir_parent = static_cast<directory_node*>(ns_parent->node_ptr); 2385 dir_parent->children.emplace_back(std::move(node_g2)); 2386 ++ns_parent->count; 2387 bool parent_size_changed = ns_parent->pack(); 2388 2389 // Update the parent pointer of the children _after_ the group 2 node 2390 // has been inserted into the buffer, as the pointer value of the node 2391 // changes after the insertion. 2392 ns->reset_parent_pointers(); 2393 dir_parent->children.back().reset_parent_pointers_of_children(); 2394 2395 if (ns_parent->count > trait_type::max_node_size) 2396 // The parent node is overfilled. Split it and keep working upward. 2397 split_node(ns_parent); 2398 else if (parent_size_changed) 2399 // The extent of the parent node has changed. Propagate the change upward. 2400 ns_parent->pack_upward(); 2401 } 2402} 2403 2404template<typename _Key, typename _Value, typename _Trait> 2405void rtree<_Key,_Value,_Trait>::perform_forced_reinsertion( 2406 node_store* ns, std::unordered_set<size_t>& reinserted_depth) 2407{ 2408 assert(ns->count == trait_type::max_node_size+1); 2409 2410 // Compute the distance between the centers of the value extents and the 2411 // center of the extent of the parent directory. 2412 2413 point_type center_of_dir = detail::rtree::get_center_point(ns->extent); 2414 2415 directory_node* dir = ns->get_directory_node(); 2416 assert(dir); 2417 2418 using buckets_type = std::vector<detail::rtree::reinsertion_bucket<key_type>>; 2419 buckets_type buckets; 2420 buckets.reserve(ns->count); 2421 2422 size_t pos = 0; 2423 for (const node_store& ns_child : dir->children) 2424 { 2425 buckets.emplace_back(); 2426 buckets.back().src_pos = pos++; 2427 2428 point_type center_of_child = detail::rtree::get_center_point(ns_child.extent); 2429 buckets.back().distance = detail::rtree::calc_square_distance(center_of_dir, center_of_child); 2430 } 2431 2432 // Sort the value entries in decreasing order of their distances. 2433 2434 std::sort(buckets.begin(), buckets.end(), 2435 [](const typename buckets_type::value_type& left, const typename buckets_type::value_type& right) -> bool 2436 { 2437 return left.distance < right.distance; 2438 } 2439 ); 2440 2441 assert(trait_type::reinsertion_size < buckets.size()); 2442 2443 // Remove the first set of entries from the parent directory. 2444 std::deque<node_store> nodes_to_reinsert(trait_type::reinsertion_size); 2445 2446 for (size_t i = 0; i < trait_type::reinsertion_size; ++i) 2447 { 2448 size_t this_pos = buckets[i].src_pos; 2449 dir->children[this_pos].swap(nodes_to_reinsert[i]); 2450 } 2451 2452 // Erase the swapped out nodes from the directory. 2453 auto it = std::remove_if(dir->children.begin(), dir->children.end(), 2454 [](const node_store& this_ns) -> bool 2455 { 2456 return this_ns.type == node_type::unspecified; 2457 } 2458 ); 2459 2460 dir->children.erase(it, dir->children.end()); 2461 ns->count -= nodes_to_reinsert.size(); 2462 assert(ns->count == dir->children.size()); 2463 2464 // No need to invalidate pointers since they are all value nodes. 2465 2466 if (ns->pack()) 2467 ns->pack_upward(); 2468 2469 // Re-insert the values from the closest to farthest. 2470 2471 while (!nodes_to_reinsert.empty()) 2472 { 2473 node_store ns_to_reinsert(std::move(nodes_to_reinsert.front())); 2474 nodes_to_reinsert.pop_front(); 2475 2476 insert(std::move(ns_to_reinsert), &reinserted_depth); 2477 } 2478} 2479 2480template<typename _Key, typename _Value, typename _Trait> 2481void rtree<_Key,_Value,_Trait>::sort_dir_store_by_split_dimension(dir_store_type& children) 2482{ 2483 // Store the sum of margins for each dimension axis. 2484 detail::rtree::min_value_pos<key_type> min_margin_dim; 2485 2486 for (size_t dim = 0; dim < trait_type::dimensions; ++dim) 2487 { 2488 // Sort the entries by the lower then by the upper value of their 2489 // bounding boxes. This invalidates the pointers of the child nodes. 2490 sort_dir_store_by_dimension(dim, children); 2491 2492 key_type sum_of_margins = key_type(); // it's actually the sum of half margins. 2493 2494 for (size_t dist = 1; dist <= max_dist_size; ++dist) 2495 { 2496 // The first group contains m-1+dist entries, while the second 2497 // group contains the rest. 2498 2499 auto it = children.begin(); 2500 auto it_end = it; 2501 std::advance(it_end, trait_type::min_node_size - 1 + dist); 2502 2503 extent_type bb1 = detail::rtree::calc_extent(it, it_end); 2504 it = it_end; 2505 it_end = children.end(); 2506 assert(it != it_end); 2507 extent_type bb2 = detail::rtree::calc_extent(it, it_end); 2508 2509 // Compute the half margins of the first and second groups. 2510 key_type margin1 = detail::rtree::calc_half_margin<extent_type>(bb1); 2511 key_type margin2 = detail::rtree::calc_half_margin<extent_type>(bb2); 2512 key_type margins = margin1 + margin2; 2513 2514 sum_of_margins += margins; 2515 } 2516 2517 min_margin_dim.assign(sum_of_margins, dim); 2518 } 2519 2520 // Pick the dimension axis with the lowest sum of margins. 2521 size_t min_dim = min_margin_dim.pos; 2522 2523 sort_dir_store_by_dimension(min_dim, children); 2524} 2525 2526template<typename _Key, typename _Value, typename _Trait> 2527void rtree<_Key,_Value,_Trait>::sort_dir_store_by_dimension(size_t dim, dir_store_type& children) 2528{ 2529 std::sort(children.begin(), children.end(), 2530 [dim](const node_store& a, const node_store& b) -> bool 2531 { 2532 if (a.extent.start.d[dim] != b.extent.start.d[dim]) 2533 return a.extent.start.d[dim] < b.extent.start.d[dim]; 2534 2535 return a.extent.end.d[dim] < b.extent.end.d[dim]; 2536 } 2537 ); 2538 2539 for (node_store& ns : children) 2540 ns.valid_pointer = false; 2541} 2542 2543template<typename _Key, typename _Value, typename _Trait> 2544size_t rtree<_Key,_Value,_Trait>::pick_optimal_distribution(dir_store_type& children) const 2545{ 2546 // Along the chosen dimension axis, pick the distribution with the minimum 2547 // overlap value. 2548 detail::rtree::min_value_pos<key_type> min_overlap_dist; 2549 2550 for (size_t dist = 1; dist <= max_dist_size; ++dist) 2551 { 2552 // The first group contains m-1+dist entries, while the second 2553 // group contains the rest. 2554 distribution dist_data(dist, children); 2555 extent_type bb1 = detail::rtree::calc_extent(dist_data.g1.begin, dist_data.g1.end); 2556 extent_type bb2 = detail::rtree::calc_extent(dist_data.g2.begin, dist_data.g2.end); 2557 2558 key_type overlap = detail::rtree::calc_intersection<extent_type>(bb1, bb2); 2559 min_overlap_dist.assign(overlap, dist); 2560 } 2561 2562 return min_overlap_dist.pos; 2563} 2564 2565template<typename _Key, typename _Value, typename _Trait> 2566typename rtree<_Key,_Value,_Trait>::insertion_point 2567rtree<_Key,_Value,_Trait>::find_leaf_directory_node_for_insertion(const extent_type& bb) 2568{ 2569 insertion_point ret; 2570 ret.ns = &m_root; 2571 2572 for (size_t i = 0; i <= trait_type::max_tree_depth; ++i) 2573 { 2574 if (ret.ns->type == node_type::directory_leaf) 2575 { 2576 ret.depth = i; 2577 return ret; 2578 } 2579 2580 assert(ret.ns->type == node_type::directory_nonleaf); 2581 2582 directory_node* dir = static_cast<directory_node*>(ret.ns->node_ptr); 2583 2584 // If this non-leaf directory contains at least one leaf directory, 2585 // pick the entry with minimum overlap increase. If all of its child 2586 // nodes are non-leaf directories, then pick the entry with minimum 2587 // area enlargement. 2588 2589 if (dir->has_leaf_directory()) 2590 ret.ns = dir->get_child_with_minimal_overlap(bb); 2591 else 2592 ret.ns = dir->get_child_with_minimal_area_enlargement(bb); 2593 } 2594 2595 throw std::runtime_error("Maximum tree depth has been reached."); 2596} 2597 2598template<typename _Key, typename _Value, typename _Trait> 2599typename rtree<_Key,_Value,_Trait>::node_store* 2600rtree<_Key,_Value,_Trait>::find_nonleaf_directory_node_for_insertion( 2601 const extent_type& bb, size_t max_depth) 2602{ 2603 node_store* dst = &m_root; 2604 2605 for (size_t i = 0; i <= trait_type::max_tree_depth; ++i) 2606 { 2607 assert(dst->is_directory()); 2608 2609 if (!dst->count) 2610 // This node has no children. 2611 return dst; 2612 2613 assert(dst->type == node_type::directory_nonleaf); 2614 2615 if (i == max_depth) 2616 return dst; 2617 2618 directory_node* dir = static_cast<directory_node*>(dst->node_ptr); 2619 2620 if (dir->has_leaf_directory()) 2621 return dst; 2622 2623 assert(dst->type == node_type::directory_nonleaf); 2624 dst = dir->get_child_with_minimal_area_enlargement(bb); 2625 assert(dst); 2626 } 2627 2628 throw std::runtime_error("Maximum tree depth has been reached."); 2629} 2630 2631template<typename _Key, typename _Value, typename _Trait> 2632template<typename _Func> 2633void rtree<_Key,_Value,_Trait>::descend_with_func(_Func func) const 2634{ 2635 std::function<void(const node_store*)> func_descend = [&](const node_store* ns) 2636 { 2637 node_properties np; 2638 np.type = ns->type; 2639 np.extent = ns->extent; 2640 func(np); 2641 2642 switch (ns->type) 2643 { 2644 case node_type::directory_leaf: 2645 case node_type::directory_nonleaf: 2646 { 2647 const directory_node* dir = 2648 static_cast<const directory_node*>(ns->node_ptr); 2649 2650 for (const node_store& ns_child : dir->children) 2651 func_descend(&ns_child); 2652 2653 break; 2654 } 2655 case node_type::value: 2656 // Do nothing. 2657 break; 2658 default: 2659 assert(!"The tree should not contain node of this type!"); 2660 } 2661 }; 2662 2663 func_descend(&m_root); 2664} 2665 2666template<typename _Key, typename _Value, typename _Trait> 2667template<typename _ResT> 2668void rtree<_Key,_Value,_Trait>::search_descend( 2669 size_t depth, const search_condition_type& dir_cond, const search_condition_type& value_cond, 2670 typename _ResT::node_store_type& ns, _ResT& results) const 2671{ 2672 switch (ns.type) 2673 { 2674 case node_type::directory_nonleaf: 2675 case node_type::directory_leaf: 2676 { 2677 if (!dir_cond(ns)) 2678 return; 2679 2680 auto* dir_node = ns.get_directory_node(); 2681 for (auto& child : dir_node->children) 2682 search_descend(depth+1, dir_cond, value_cond, child, results); 2683 break; 2684 } 2685 case node_type::value: 2686 { 2687 if (!value_cond(ns)) 2688 return; 2689 2690 results.add_node_store(&ns, depth); 2691 break; 2692 } 2693 case node_type::unspecified: 2694 throw std::runtime_error("unspecified node type."); 2695 } 2696} 2697 2698template<typename _Key, typename _Value, typename _Trait> 2699void rtree<_Key,_Value,_Trait>::shrink_tree_upward(node_store* ns, const extent_type& bb_affected) 2700{ 2701 if (!ns) 2702 return; 2703 2704 // Check if the affected bounding box is at a corner. 2705 if (!ns->extent.contains_at_boundary(bb_affected)) 2706 return; 2707 2708 extent_type original_bb = ns->extent; // Store the original bounding box before the packing. 2709 bool updated = ns->pack(); 2710 2711 if (!updated) 2712 // The extent hasn't changed. There is no point going upward. 2713 return; 2714 2715 shrink_tree_upward(ns->parent, original_bb); 2716} 2717 2718} // namespace mdds 2719 2720/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ 2721 2722