devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++实现R*树_r tree c++

作者：Gausst松鼠会 | 2024-04-23 21:05:24

赞

踩

r tree c++

R*树是对空间数据结构R树的改进

具体见链接中两个文件

链接：https://pan.baidu.com/s/1tq0q0LWUnwWjPl2MxXDmDw?pwd=ff0f 
提取码：ff0f

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <utility>
  5. #include <list>
  6. #include <functional>
  7. #include <stack>
  8. #include <random>
  9. using namespace std;
  10. using namespace std::placeholders;
  11.  
  12. template <typename T>
  13. struct RStarTreeNode
  14. {
  15.     vector<vector<pair<T, T>>> enclosed_rectangle_group;
  16.     vector<RStarTreeNode<T> *> pointer_to_sub_tree;
  17.     RStarTreeNode(const size_t M) :enclosed_rectangle_group(), pointer_to_sub_tree() { enclosed_rectangle_group.reserve(M + 1);  pointer_to_sub_tree.reserve(M + 1); }
  18. };
  19.  
  20. template <typename T>
  21. class Sort_for_interval_and_dimension
  22. {
  23. public:
  24.     bool operator()(const size_t left, const size_t right)
  25.     {
  26.         if (left_point_or_right_point)
  27.         {
  28.             return enclosed_rectangle_group[left][d].first < enclosed_rectangle_group[right][d].first;
  29.         }
  30.         else
  31.         {
  32.             return enclosed_rectangle_group[left][d].second < enclosed_rectangle_group[right][d].second;
  33.         }
  34.     }
  35.     Sort_for_interval_and_dimension(const vector<vector<pair<T, T>>>& e, const size_t d, bool l) :enclosed_rectangle_group(e), d(d), left_point_or_right_point(l) {}
  36. private:
  37.     const vector<vector<pair<T, T>>>& enclosed_rectangle_group;
  38.     const size_t d;
  39.     bool left_point_or_right_point;
  40. };
  41.  
  42. template <typename T>
  43. struct AssistInfo
  44. {
  45.     size_t num;
  46.     T endpoint;
  47.     AssistInfo() = default;
  48.     AssistInfo(size_t n, const T& e) :num(n), endpoint(e) {}
  49. };
  50.  
  51. template <typename T>
  52. class RStarTree
  53. {
  54. public:
  55.     void insertData(vector<pair<T, T>>& be_inserted);
  56.     bool remove(vector<pair<T, T>>& key);
  57.     bool isRTree();
  58.     RStarTree(size_t dm, size_t min, size_t Max, T z, T o, size_t f):d(dm), m(min), M(Max), zero(z), one(o), first_p(f)
  59.     {
  60.         if (dm == 0)
  61.         {
  62.             cout << "ERROR:RStarTree维度无效!" << endl;
  63.             exit(-1);
  64.         }
  65.  
  66.         if (min <= 1 || min > (Max + 1)/2)
  67.         {
  68.             cout << "ERROR:m或M无效!" << endl;
  69.             exit(-1);
  70.         }
  71.  
  72.         if (f == 0 || f > M - m + 1)
  73.         {
  74.             cout << "ERROR:first_p值无效!" << endl;
  75.             exit(-1);
  76.         }
  77.     }
  78. private:
  79.     RStarTreeNode<T>* root = nullptr;
  80.     const size_t d;   //数据维度
  81.     const size_t m;
  82.     const size_t M;
  83.     const T zero;
  84.     const T one;
  85.     const size_t first_p; //first_p在1到M-M/2+1之间，表示重新插入时要删除的条目数目
  86.     size_t height = 0;   //R*树高度
  87.     void insert(vector<pair<T, T>>& be_inserted, RStarTreeNode<T>* be_inserted_pointer, size_t h, vector<bool> &level_has_overflow_process);
  88.     void re_insert(RStarTreeNode<T>* node, size_t h, vector<bool>& level_has_overflow_process, vector<pair<RStarTreeNode<T>*, size_t>>& work_stack, size_t index);
  89.     void find_leaf(vector<pair<T, T>>& key, vector<pair<RStarTreeNode<T>*, size_t>> &work_stack, size_t &index, RStarTreeNode<T>* cur); //vector大小初始化为height
  90.     pair<pair<vector<pair<T, T>>, vector<pair<T, T>>>, RStarTreeNode<T>*> spilit(RStarTreeNode<T>* node);
  91.     size_t chooseSubTree(RStarTreeNode<T>* node, vector<pair<T, T>>& insert);
  92.     void upAdjustRect(vector<pair<RStarTreeNode<T>*, size_t>>& work_stack, vector<pair<T, T>>& cur_rect, size_t index);
  93.     RStarTreeNode<T>* findNodeInSelectedLevel(size_t h, vector<pair<T, T>> &insert, vector<pair<RStarTreeNode<T>*, size_t>> &work_stack);
  94.     bool compute_patial_sort_result(size_t j, vector<size_t>& patial_sort_result_for_different_d, vector<size_t>& sort_result, vector<vector<pair<T, T>>>& enclosed_rectangle_group, bool compare_first);
  95.     bool computeRect(vector<pair<T, T>>& left, vector<pair<T, T>>& right);
  96.     void computeReactAll(vector<pair<T, T>>& left, vector<size_t>& right , size_t l, size_t r, vector<vector<pair<T, T>>>& enclosed_rectangle_group);
  97.     T margin(vector<pair<T, T>>& cur);
  98.     void compute_assist(size_t j, vector<size_t>& patial_sort_result_for_different_d, vector<vector<pair<T, T>>>& enclosed_rectangle_group, vector<vector<AssistInfo<T>>>& assist_info_left, vector<vector<size_t>>& rank_left);
  99.     void compute_assist_right(size_t j, vector<size_t>& patial_sort_result_for_different_d_right, vector<vector<pair<T, T>>>& enclosed_rectangle_group, vector<vector<AssistInfo<T>>>& assist_info_right, vector<vector<size_t>>& rank_right);
  100.     T computeArea(vector<pair<T, T>>& cur);
  101.     bool getInterRect(vector<pair<T, T>>& be_filled, vector<pair<T, T>>& A, vector<pair<T, T>>& B);
  102.     T compute_margin_sum(bool left_left, size_t i, vector<size_t>& sort_result_left, vector<vector<pair<T, T>>>& enclosed_rectangle_group, vector<vector<AssistInfo<T>>>& assist_info_left_left, vector<vector<size_t>>& rank_left_left, vector<vector<AssistInfo<T>>>& assist_info_left_right, vector<vector<size_t>>& rank_left_right,
  103.         vector<pair<vector<pair<T, T>>, vector<pair<T, T>>>>& rect_pair, vector<size_t>& spilit_point_for_every_different_rect_pair);
  104.     void findBestSpilit(vector<size_t>& spilit_point_for_every_different_rect_pair, list<pair<vector<pair<T, T>>, vector<pair<T, T>>>>& best_spilit_react, list<size_t>& best_spilit_point, T& best_inter_area, vector<pair<vector<pair<T, T>>, vector<pair<T, T>>>>& left_rect_pair);
  105.     bool rectEqual(vector<pair<T, T>>& left, vector<pair<T, T>>& right);
  106.     bool rectContain(vector<pair<T, T>>& judge_object, vector<pair<T, T>>& test);
  107.     void computeAndAdjust(vector<pair<RStarTreeNode<T>*, size_t>>& work_stack, vector<vector<pair<T, T>>>& cur, size_t m, size_t index);
  108.     void deleteAndReinsert(size_t index, vector<pair<RStarTreeNode<T>*, size_t>>& work_stack);
  109.     bool checkRTree(RStarTreeNode<T>* cur, bool isRoot, size_t& height, vector<pair<T, T>>& enclosedRect);
  110.     void adjustRect(vector<pair<RStarTreeNode<T>*, size_t>>& work_stack, vector<pair<T, T>>& be_inserted, size_t index);
  111.     T findBestSpilitPlan(list<pair<vector<pair<T, T>>, vector<pair<T, T>>>>& best_spilit_react, list<size_t>& best_spilit_point, size_t& best_spilit_point_value, pair<vector<pair<T, T>>, vector<pair<T, T>>>& best_spilit_react_pair);
  112. };
  113.  
  114. template <typename T>
  115. void RStarTree<T>::find_leaf(vector<pair<T, T>>& key, vector<pair<RStarTreeNode<T>*, size_t>>& work_stack, size_t &index, RStarTreeNode<T>* cur)  //index可用来判断搜索是否成功
  116. {    
  117.     if (cur->pointer_to_sub_tree.empty() == false)
  118.     {
  119.         for (size_t i = 0; i < cur->enclosed_rectangle_group.size(); ++i)
  120.         {
  121.             if (rectContain(key, cur->enclosed_rectangle_group[i]))
  122.             {
  123.                 work_stack[index] = make_pair(cur, i);
  124.                 --index;
  125.                 find_leaf(key, work_stack, index, cur->pointer_to_sub_tree[i]);
  126.                 if (index == 0)
  127.                     return;
  128.             }
  129.         }
  130.     }
  131.     else
  132.     {
  133.         for (size_t i = 0; i < cur->enclosed_rectangle_group.size(); ++i)
  134.         {
  135.             if (rectEqual(key, cur->enclosed_rectangle_group[i]))
  136.             {
  137.                 work_stack[index] = make_pair(cur, i);
  138.                 return;
  139.             }
  140.         }
  141.     }
  142.     ++index;
  143. }
  144.  
  145. template <typename T>
  146. bool RStarTree<T>::rectEqual(vector<pair<T, T>>& left, vector<pair<T, T>>& right)
  147. {
  148.     for (size_t i = 0; i < d; ++i)
  149.     {
  150.         if (left[i].first != right[i].first || left[i].second != right[i].second)
  151.         {
  152.             return false;
  153.         }
  154.     }
  155.     return true;
  156. }
  157.  
  158. template <typename T>
  159. bool RStarTree<T>::rectContain(vector<pair<T, T>>& judge_object, vector<pair<T, T>>& test)
  160. {
  161.     for (size_t i = 0; i < d; ++i)
  162.     {
  163.         if (judge_object[i].first < test[i].first || judge_object[i].second > test[i].second)
  164.         {
  165.             return false;
  166.         }
  167.     }
  168.     return true;
  169. }
  170.  
  171. template <typename T>
  172. bool RStarTree<T>::computeRect(vector<pair<T, T>>& left, vector<pair<T, T>>& right)
  173. {
  174.     bool equal = true;
  175.     for (size_t i = 0; i < d; ++i)
  176.     {
  177.         if (left[i].first > right[i].first)
  178.         {
  179.             left[i].first = right[i].first;
  180.             equal = false;
  181.         }
  182.  
  183.         if (left[i].second < right[i].second)
  184.         {
  185.             left[i].second = right[i].second;
  186.             equal = false;
  187.         }
  188.     }
  189.     return equal;
  190. }
  191.  
  192. template <typename T>
  193. void RStarTree<T>::computeAndAdjust(vector<pair<RStarTreeNode<T>*, size_t>> &work_stack, vector<vector<pair<T, T>>> &cur, size_t m, size_t index)   //
  194. { 
  195.     vector<pair<T, T>> cur_rect = cur[0];
  196.     for (size_t i = 1; i <= m; ++i)
  197.     {
  198.         computeRect(cur_rect, cur[i]);
  199.     }
  200.  
  201.     upAdjustRect(work_stack, cur_rect, index);
  202. }
  203.  
  204. template <typename T>
  205. void RStarTree<T>::deleteAndReinsert(size_t index, vector<pair<RStarTreeNode<T>*, size_t>> &work_stack)
  206. {
  207.     if (index != 0)
  208.     {
  209.         {
  210.             size_t mid = work_stack[0].second;
  211.             vector<bool> level_has_overflow_process(height, false);
  212.             level_has_overflow_process.back() = true;
  213.             for (size_t j = 0; j < work_stack[0].first->enclosed_rectangle_group.size(); ++j)
  214.             {
  215.                 if (j != mid)
  216.                 {
  217.                     insert(work_stack[0].first->enclosed_rectangle_group[j], nullptr, 1, level_has_overflow_process);
  218.                 }
  219.             }
  220.             delete work_stack[0].first;
  221.         }
  222.     }
  223.  
  224.     for (size_t i = 1; i < index; ++i)
  225.     {
  226.         size_t mid = work_stack[i].second;
  227.         vector<bool> level_has_overflow_process(height, false);
  228.         level_has_overflow_process.back() = true;
  229.         for (size_t j = 0; j < work_stack[i].first->enclosed_rectangle_group.size(); ++j)
  230.         {
  231.             if (j != mid)
  232.             {
  233.                 insert(work_stack[i].first->enclosed_rectangle_group[j], work_stack[i].first->pointer_to_sub_tree[j], i + 1, level_has_overflow_process);
  234.             }
  235.         }
  236.         delete work_stack[i].first;
  237.     }
  238. }
  239.  
  240. template <typename T>
  241. bool RStarTree<T>::remove(vector<pair<T, T>>& key)
  242. {
  243.     if (root == nullptr)
  244.         return false;
  245.  
  246.     vector<pair<RStarTreeNode<T>*, size_t>> work_stack(height, pair<RStarTreeNode<T>*, size_t>());
  247.     size_t index = height - 1;    //height
  248.     find_leaf(key, work_stack, index, root);
  249.     if (index == height)
  250.     {
  251.             return false;
  252.     }
  253.  
  254.     index = 0;
  255.     while (true)
  256.     {
  257.         RStarTreeNode<T>* cur = work_stack[index].first;
  258.         if (cur == root || cur->enclosed_rectangle_group.size() > m)
  259.         {
  260.             size_t i = work_stack[index].second;
  261.             cur->enclosed_rectangle_group.erase(cur->enclosed_rectangle_group.begin() + i);
  262.             if (index != 0)
  263.             {
  264.                 cur->pointer_to_sub_tree.erase(cur->pointer_to_sub_tree.begin() + i);
  265.             }
  266.  
  267.             if (cur != root)
  268.             {
  269.                 vector<pair<T, T>>& enclosed_rectangle_cur = work_stack[index + 1].first->enclosed_rectangle_group[work_stack[index + 1].second];
  270.                 computeAndAdjust(work_stack, cur->enclosed_rectangle_group, cur->enclosed_rectangle_group.size() - 1, index + 1);
  271.             }
  272.             else
  273.             {
  274.                 if (height == 1)
  275.                 {
  276.                     if (root->enclosed_rectangle_group.empty())
  277.                     {
  278.                         delete root;
  279.                         root = nullptr;
  280.                         height = 0;
  281.                     }
  282.                     return true;
  283.                 }
  284.                 else
  285.                 {
  286.                     if (root->enclosed_rectangle_group.size() == 1)
  287.                     {
  288.                         root = root->pointer_to_sub_tree.back();
  289.                         delete cur;
  290.                         --height;
  291.                     }
  292.                 }
  293.             }
  294.             deleteAndReinsert(index, work_stack);
  295.             return true;
  296.         }
  297.         else
  298.         {
  299.             ++index;
  300.         }
  301.     }
  302. }
  303.  
  304. template <typename T>
  305. class Sort_for_central_distance
  306. {
  307. public:
  308.     bool operator()(const size_t left, const size_t right)
  309.     {
  310.         return central_distance[left] > central_distance[right];
  311.     }
  312.     Sort_for_central_distance(const vector<T>& e): central_distance(e) {}
  313. private:
  314.     const vector<T>& central_distance;
  315. };
  316.  
  317. template <typename T>
  318. void RStarTree<T>::upAdjustRect(vector<pair<RStarTreeNode<T>*, size_t>>& work_stack, vector<pair<T, T>> &cur_rect, size_t index)
  319. {
  320.     RStarTreeNode<T>* cur = work_stack[index].first;
  321.     enum class need_compute {need, noneed, unknown};
  322.     vector<need_compute> need_compute(d, need_compute::unknown);
  323.  
  324.     while (true)
  325.     {
  326.         vector<vector<pair<T, T>>>& enclosed_rectangle_group = cur->enclosed_rectangle_group;
  327.         size_t i;
  328.         vector<pair<T, T>>& cur_rect_after_change = enclosed_rectangle_group[i = work_stack[index++].second];
  329.  
  330.         bool changed = false;
  331.         for (size_t k = 0; k < d; ++k)
  332.         {
  333.             if (need_compute[k] == need_compute::noneed)
  334.                 continue;
  335.             if (need_compute[k] == need_compute::unknown || need_compute[k] == need_compute::need)
  336.             {
  337.                 if (cur_rect_after_change[k].first != cur_rect[k].first || cur_rect_after_change[k].second != cur_rect[k].second)
  338.                 {
  339.                     cur_rect_after_change[k].first = cur_rect[k].first;
  340.                     cur_rect_after_change[k].second = cur_rect[k].second;
  341.                     need_compute[k] = need_compute::need;
  342.                 }
  343.                 else
  344.                     need_compute[k] = need_compute::noneed;
  345.             }
  346.  
  347.             if (need_compute[k] == need_compute::need)
  348.             {
  349.                 changed = true;
  350.                 for (size_t j = 0; j < enclosed_rectangle_group.size(); ++j)
  351.                 {
  352.                     if (j == i)
  353.                         continue;
  354.                     if (cur_rect[k].first > enclosed_rectangle_group[j][k].first)
  355.                     {
  356.                         cur_rect[k].first = enclosed_rectangle_group[j][k].first;
  357.                     }
  358.  
  359.                     if (cur_rect[k].second < enclosed_rectangle_group[j][k].second)
  360.                     {
  361.                         cur_rect[k].second = enclosed_rectangle_group[j][k].second;
  362.                     }
  363.                 }
  364.             }
  365.         }
  366.  
  367.         if (index == work_stack.size() || changed == false)
  368.             break;
  369.         cur = work_stack[index].first;
  370.     }
  371. }
  372.  
  373. template <typename T>
  374. void RStarTree<T>::re_insert(RStarTreeNode<T>* node, size_t h, vector<bool>& level_has_overflow_process, vector<pair<RStarTreeNode<T>*, size_t>>& work_stack, size_t index)  //重新插入只会重插至非根节点层
  375. {
  376.     vector<vector<pair<T, T>>>& enclosed_rectangle_group = node->enclosed_rectangle_group;
  377.     vector<pair<T, T>>& enclosed_rectangle_parent = work_stack[index].first->enclosed_rectangle_group[work_stack[index].second];   
  378.     vector<size_t> sort_result(M + 1);
  379.     for (size_t j = 0; j <= M; ++j)
  380.     {
  381.         sort_result[j] = j;
  382.     }
  383.     vector<T> central_parent(d);
  384.     for (size_t i = 0; i < d; ++i)
  385.     {
  386.         central_parent[i] = (enclosed_rectangle_parent[i].second + enclosed_rectangle_parent[i].first) / 2;
  387.     }
  388.     vector<T> central_distance(M + 1, zero);
  389.     for (size_t i = 0; i <= M; ++i)
  390.     {
  391.         for (size_t j = 0; j < d; ++j)
  392.         {
  393.             T cental_part = (enclosed_rectangle_group[i][j].second + enclosed_rectangle_group[i][j].first) / 2;
  394.             T t = max(cental_part, central_parent[j]) - min(cental_part, central_parent[j]);
  395.             central_distance[i] += t * t;
  396.         }
  397.     }
  398.     sort(sort_result.begin(), sort_result.end(), Sort_for_central_distance<T>(central_distance));
  399.     vector<vector<pair<T, T>>> first_first_p(first_p);
  400.     for (size_t i = 0; i < first_p; ++i)
  401.     {
  402.         first_first_p[i] = enclosed_rectangle_group[sort_result[i]];
  403.     }
  404.  
  405.     vector<vector<pair<T, T>>> after_first_p(M + 1 - first_p);
  406.     for (size_t i = first_p; i <= M; ++i)
  407.     {
  408.         after_first_p[i - first_p] = enclosed_rectangle_group[sort_result[i]];
  409.     }
  410.  
  411.     computeAndAdjust(work_stack, after_first_p, M - first_p, index);
  412.  
  413.     vector<RStarTreeNode<T>*>& pointer = node->pointer_to_sub_tree;
  414.     if (pointer.empty() == false)
  415.     {
  416.         vector<RStarTreeNode<T>*> first_first_p_p(first_p);
  417.         vector<RStarTreeNode<T>*> after_first_p_p(M + 1 - first_p);
  418.         for (size_t i = 0; i < first_p; ++i)
  419.         {
  420.             first_first_p_p[i] = pointer[sort_result[i]];
  421.         }
  422.  
  423.         for (size_t i = first_p; i <= M; ++i)
  424.         {
  425.             after_first_p_p[i - first_p] = pointer[sort_result[i]];
  426.         }
  427.         pointer = after_first_p_p;
  428.         enclosed_rectangle_group = after_first_p;
  429.         for (size_t i = 0; i < first_p; ++i)
  430.         {
  431.             insert(first_first_p[i], first_first_p_p[i], h, level_has_overflow_process);
  432.         }
  433.     }
  434.     else
  435.     {
  436.         enclosed_rectangle_group = after_first_p;
  437.         for (size_t i = 0; i < first_p; ++i)
  438.         {
  439.             insert(first_first_p[i], nullptr, h, level_has_overflow_process);
  440.         }
  441.     }
  442. }
  443.  
  444. template <typename T>
  445. void RStarTree<T>::insertData(vector<pair<T, T>>& be_inserted)
  446. {
  447.     if (root == nullptr)
  448.     {
  449.         root = new RStarTreeNode<T>(M);
  450.         root->enclosed_rectangle_group.push_back(be_inserted);
  451.         height = 1;
  452.         return;
  453.     }
  454.     vector<bool> level_has_overflow_process(height, false);
  455.     level_has_overflow_process.back() = true;
  456.     insert(be_inserted, nullptr, 1, level_has_overflow_process);
  457. }
  458.  
  459. template<typename T>
  460. void RStarTree<T>::adjustRect(vector<pair<RStarTreeNode<T>*, size_t>> &work_stack, vector<pair<T, T>>& be_inserted, size_t index)
  461. {
  462.     while (index != work_stack.size())
  463.     {
  464.         vector<vector<pair<T, T>>>& enclosed_rectangle_group = work_stack[index].first->enclosed_rectangle_group;
  465.         size_t i = work_stack[index++].second;
  466.         if (computeRect(enclosed_rectangle_group[i], be_inserted))
  467.         {
  468.             return;
  469.         }
  470.     }
  471. }
  472.  
  473. template <typename T>
  474. void RStarTree<T>::insert(vector<pair<T, T>>& be_inserted, RStarTreeNode<T>* be_inserted_pointer, size_t h, vector<bool>& level_has_overflow_process)
  475. {
  476.     vector<pair<RStarTreeNode<T>*, size_t>> work_stack(height - h);
  477.     RStarTreeNode<T>* cur = findNodeInSelectedLevel(h, be_inserted, work_stack);
  478.     size_t run_h = h;
  479.     cur->enclosed_rectangle_group.push_back(be_inserted);
  480.     if (be_inserted_pointer != nullptr)
  481.         cur->pointer_to_sub_tree.push_back(be_inserted_pointer);
  482.     size_t index = 0;
  483.     while (true)
  484.     {
  485.         if (cur->enclosed_rectangle_group.size() <= M)
  486.         {
  487.             adjustRect(work_stack, be_inserted, index);
  488.             return;
  489.         }
  490.  
  491.         if (index != work_stack.size())
  492.         {
  493.             if (level_has_overflow_process[run_h] == false)
  494.             {
  495.                 level_has_overflow_process[run_h] = true;
  496.                 re_insert(cur, run_h, level_has_overflow_process, work_stack, index);
  497.                 return;
  498.             }
  499.         }
  500.  
  501.         pair<pair<vector<pair<T, T>>, vector<pair<T, T>>>, RStarTreeNode<T>*> spilit_result = spilit(cur);
  502.         if (index != work_stack.size())
  503.         {
  504.             vector<vector<pair<T, T>>>& enclosed_rectangle_group = work_stack[index].first->enclosed_rectangle_group;
  505.             enclosed_rectangle_group[work_stack[index].second] = spilit_result.first.first;
  506.             enclosed_rectangle_group.push_back(spilit_result.first.second);   
  507.             vector<RStarTreeNode<T>*>& pointer = work_stack[index].first->pointer_to_sub_tree;
  508.             if (pointer.empty() == false)
  509.                pointer.push_back(spilit_result.second);   
  510.             cur = work_stack[index++].first;
  511.             ++run_h;         
  512.         }
  513.         else
  514.         {
  515.             root = new RStarTreeNode<T>(M);
  516.             root->enclosed_rectangle_group.push_back(spilit_result.first.first);
  517.             root->enclosed_rectangle_group.push_back(spilit_result.first.second);
  518.             root->pointer_to_sub_tree.push_back(cur);
  519.             root->pointer_to_sub_tree.push_back(spilit_result.second);
  520.             ++height;
  521.             level_has_overflow_process.push_back(true);
  522.             return;
  523.         }
  524.     }
  525. }
  526.  
  527. template <typename T>
  528. RStarTreeNode<T>* RStarTree<T>::findNodeInSelectedLevel(size_t h, vector<pair<T, T>>& be_inserted, vector<pair<RStarTreeNode<T>*, size_t>> &work_stack)
  529. {
  530.     if (h == 0)
  531.     {
  532.         cerr << "ERRO0R:无效的高度参数" << endl;
  533.         exit(-1);
  534.     }
  535.  
  536.     if (height == 0)
  537.     {
  538.         cerr << "空树，搜索失败" << endl;
  539.         exit(-1);
  540.     }
  541.     if (h > height)
  542.     {
  543.         cerr << "ERRO0R:无效的高度参数" << endl;
  544.         exit(-1);
  545.     }
  546.  
  547.     RStarTreeNode<T>* p = root;
  548.     size_t stack_index = work_stack.size();
  549.     while (stack_index != 0)
  550.     {
  551.         size_t i = chooseSubTree(p, be_inserted);
  552.         work_stack[--stack_index] = make_pair(p, i);
  553.         p = p->pointer_to_sub_tree[i];
  554.     }
  555.     return p;
  556. }
  557.  
  558. template <typename T>
  559. void updateRelatedInfo(size_t i, size_t min_i, vector<size_t> &min_i_area_diff, vector<T> &min_area, T &min_area_diff, const T &a, const T &area_diff)
  560. {
  561.     if (i == 0 || min_area_diff > area_diff || min_area_diff == area_diff)
  562.     {
  563.         if (i == 0 || min_area_diff > area_diff)
  564.         {
  565.             if (i != 0)
  566.             {
  567.                 min_i_area_diff.clear();
  568.                 min_area.clear();
  569.             }
  570.             min_area_diff = area_diff;
  571.         }
  572.         min_i_area_diff.push_back(min_i);
  573.         min_area.push_back(a);
  574.     }
  575. }
  576. template <typename T>
  577. size_t RStarTree<T>::chooseSubTree(RStarTreeNode<T>* node, vector<pair<T, T>>& insert)
  578. {
  579.     vector<vector<pair<T, T>>>& enclosed_rectangle_group = node->enclosed_rectangle_group;
  580.     vector<size_t> min_i;  min_i.reserve(enclosed_rectangle_group.size());
  581.     vector<size_t> min_i_area_diff;
  582.     vector<T> min_area;
  583.     if (node->pointer_to_sub_tree[0]->pointer_to_sub_tree.empty())
  584.     {
  585.         vector<vector<T>> inter_section_area(enclosed_rectangle_group.size(), vector<T>(enclosed_rectangle_group.size()));
  586.         T min_add_overlap;
  587.         vector<vector<pair<T, T>>> rect_after_insert;  rect_after_insert.reserve(enclosed_rectangle_group.size());
  588.         vector<bool> contain; contain.reserve(enclosed_rectangle_group.size());
  589.         for (size_t i = 0; i < enclosed_rectangle_group.size() - 1; ++i)
  590.         {
  591.             T sum_area_value = zero;
  592.             for (size_t j = i + 1; j < enclosed_rectangle_group.size(); ++j)
  593.             {
  594.                 vector<pair<T, T>> be_filled(d);
  595.                 if (getInterRect(be_filled, enclosed_rectangle_group[i], enclosed_rectangle_group[j]))
  596.                 {
  597.                     T area = computeArea(be_filled);
  598.                     sum_area_value += area;
  599.                     inter_section_area[i][j] = area;
  600.                 }
  601.                 else
  602.                 {
  603.                     inter_section_area[i][j] = zero;
  604.                 }
  605.             }
  606.  
  607.             for (size_t j = 0; j < i; ++j)
  608.             {
  609.                 sum_area_value += inter_section_area[j][i];
  610.             }
  611.  
  612.             vector<pair<T, T>> R = enclosed_rectangle_group[i];
  613.             T add_overlap;
  614.             bool temp;
  615.             if ((temp = computeRect(R, insert)) == false)
  616.             {
  617.                 T sum_area_value_after_insert = zero;
  618.                 for (size_t j = 0; j < enclosed_rectangle_group.size(); ++j)
  619.                 {
  620.                     if (j == i)
  621.                         continue;
  622.                     vector<pair<T, T>> be_filled(d);
  623.                     if (getInterRect(be_filled, enclosed_rectangle_group[j], R))
  624.                         sum_area_value_after_insert += computeArea(be_filled);
  625.                 }
  626.                 add_overlap = sum_area_value_after_insert - sum_area_value;
  627.             }
  628.             else
  629.             {
  630.                 add_overlap = zero;
  631.             }
  632.  
  633.             if (i == 0 || min_add_overlap > add_overlap || min_add_overlap == add_overlap)
  634.             {
  635.                 if (i == 0 || min_add_overlap > add_overlap)
  636.                 {
  637.                     if (i != 0)
  638.                     {
  639.                         min_i.clear();
  640.                         rect_after_insert.clear();
  641.                         contain.clear();
  642.                     }
  643.                     min_add_overlap = add_overlap;
  644.                 }
  645.                 min_i.push_back(i);
  646.                 if (temp == false)
  647.                 {
  648.                     rect_after_insert.push_back(R);
  649.                 }
  650.                 contain.push_back(temp);
  651.             }
  652.         }
  653.  
  654.         size_t j = 0;
  655.         T min_area_diff;
  656.         min_i_area_diff.reserve(min_i.size());
  657.         min_area.reserve(min_i.size());
  658.         for (size_t i = 0; i < min_i.size(); ++i)
  659.         {
  660.             T area_diff;
  661.             T a = computeArea(enclosed_rectangle_group[min_i[i]]);
  662.             if (contain[i] == false)
  663.             {
  664.                 area_diff = computeArea(rect_after_insert[j++]) - a;
  665.             }
  666.             else
  667.             {
  668.                 area_diff = zero;
  669.             }
  670.             updateRelatedInfo(i, min_i[i], min_i_area_diff, min_area, min_area_diff, a, area_diff);
  671.         }
  672.     }
  673.     else
  674.     {
  675.         T min_area_diff;
  676.         min_i_area_diff.reserve(enclosed_rectangle_group.size());
  677.         min_area.reserve(enclosed_rectangle_group.size());
  678.         for (size_t i = 0; i < enclosed_rectangle_group.size(); ++i)
  679.         {
  680.             T area_diff;
  681.             bool temp;
  682.             vector<pair<T, T>> be_filled = enclosed_rectangle_group[i];
  683.             T a;
  684.             if ((temp = computeRect(be_filled, insert)) == false)
  685.             {
  686.                 area_diff = computeArea(be_filled) - (a = computeArea(enclosed_rectangle_group[i]));
  687.             }
  688.             else
  689.             {
  690.                 area_diff = zero;
  691.             }
  692.             updateRelatedInfo(i, i, min_i_area_diff, min_area, min_area_diff, a, area_diff);
  693.         }
  694.     }
  695.     size_t index = min_i_area_diff[0];
  696.     T m_area_value = min_area[0];
  697.     for (size_t i = 1; i < min_i_area_diff.size(); ++i)
  698.     {
  699.         if (m_area_value > min_area[i])
  700.         {
  701.             m_area_value = min_area[i];
  702.             index = min_i_area_diff[i];
  703.         }
  704.     }
  705.     return index;
  706. }
  707.  
  708. template <typename T>
  709. bool RStarTree<T>::compute_patial_sort_result(size_t j, vector<size_t> &patial_sort_result_for_different_d, vector<size_t> &sort_result, vector<vector<pair<T, T>>>& enclosed_rectangle_group, bool compare_first)
  710. {
  711.     patial_sort_result_for_different_d.insert(patial_sort_result_for_different_d.end(), sort_result.begin() + m, sort_result.begin() + M + 1 - m + 1);
  712.    vector<size_t> patial_sort_result_for_after_m(sort_result.begin() + m, sort_result.end());
  713.    sort(patial_sort_result_for_after_m.begin(), patial_sort_result_for_after_m.end(), Sort_for_interval_and_dimension<T>(enclosed_rectangle_group, j, compare_first));
  714.  
  715.    size_t low = 0;
  716.    size_t up = M - m;
  717.    size_t i = 0;
  718.    size_t k;
  719.    if (compare_first)
  720.    {
  721.        sort(patial_sort_result_for_different_d.begin(), patial_sort_result_for_different_d.end(), Sort_for_interval_and_dimension<T>(enclosed_rectangle_group, j, compare_first));
  722.        if (patial_sort_result_for_after_m[low] != patial_sort_result_for_different_d.front())
  723.            return true;
  724.  
  725.      
  726.        for (k = low + 1, ++i; i < patial_sort_result_for_different_d.size(); ++k)
  727.        {
  728.            if (patial_sort_result_for_after_m[k] != patial_sort_result_for_different_d[i])
  729.                break;
  730.            ++i;
  731.        }
  732.    }
  733.    else
  734.    {
  735.        sort(patial_sort_result_for_different_d.begin(), patial_sort_result_for_different_d.end(), bind(Sort_for_interval_and_dimension<T>(enclosed_rectangle_group, j, compare_first),_2, _1));
  736.        if (patial_sort_result_for_after_m[up] != patial_sort_result_for_different_d.front())
  737.            return true;
  738.     
  739.        for (k = up - 1, ++i; i < patial_sort_result_for_different_d.size(); --k)
  740.        {
  741.            if (patial_sort_result_for_after_m[k] != patial_sort_result_for_different_d[i])
  742.                break;
  743.            ++i;
  744.        }
  745.  
  746.    }
  747.    patial_sort_result_for_different_d.erase(patial_sort_result_for_different_d.begin() + i, patial_sort_result_for_different_d.end());
  748.    patial_sort_result_for_different_d.push_back(patial_sort_result_for_after_m[k]);
  749.    if (compare_first)
  750.        reverse(patial_sort_result_for_different_d.begin(), patial_sort_result_for_different_d.end());
  751.    return false;
  752. }
  753.  
  754. template <typename T>
  755. T RStarTree<T>::margin(vector<pair<T, T>>& cur)
  756. {
  757.     T sum = zero;
  758.     for (size_t i = 0; i < d; ++i)
  759.     {
  760.         sum += cur[i].second - cur[i].first;
  761.     }
  762.     return sum;
  763. }
  764. template <typename T>
  765. void RStarTree<T>::computeReactAll(vector<pair<T, T>>& left, vector<size_t>& right, size_t l, size_t r, vector<vector<pair<T, T>>>& enclosed_rectangle_group)
  766. {
  767.     left = enclosed_rectangle_group[right[l]];
  768.     for (size_t i = l + 1; i <= r; ++i)
  769.     {
  770.         computeRect(left, enclosed_rectangle_group[right[i]]);
  771.     }
  772. }
  773.  
  774. template <typename T>
  775. void RStarTree<T>::compute_assist(size_t j, vector<size_t>& patial_sort_result_for_different_d, vector<vector<pair<T, T>>>& enclosed_rectangle_group, vector<vector<AssistInfo<T>>>& assist_info_left, vector<vector<size_t>>& rank_left)
  776. {
  777.     size_t k = 0;
  778.     while (k < patial_sort_result_for_different_d.size())
  779.     {
  780.         assist_info_left[j].push_back(AssistInfo<T>(1, enclosed_rectangle_group[patial_sort_result_for_different_d[k]][j].first));
  781.         while (true)
  782.         {
  783.             rank_left[j][patial_sort_result_for_different_d[k]] = assist_info_left[j].size() - 1;
  784.             
  785.             if (k >= patial_sort_result_for_different_d.size() - 1 || enclosed_rectangle_group[patial_sort_result_for_different_d[k]][j].first != enclosed_rectangle_group[patial_sort_result_for_different_d[k + 1]][j].first)
  786.             {
  787.                 ++k;
  788.                 break;
  789.             }
  790.             ++assist_info_left[j].back().num;
  791.             ++k;
  792.         }
  793.     }
  794. }
  795.  
  796. template <typename T>
  797. void RStarTree<T>::compute_assist_right(size_t j, vector<size_t>& patial_sort_result_for_different_d_right, vector<vector<pair<T, T>>>& enclosed_rectangle_group, vector<vector<AssistInfo<T>>>& assist_info_right, vector<vector<size_t>>& rank_right)
  798. {
  799.     size_t k = 0;
  800.     while (k < patial_sort_result_for_different_d_right.size())
  801.     {
  802.         assist_info_right[j].push_back(AssistInfo<T>(1, enclosed_rectangle_group[patial_sort_result_for_different_d_right[k]][j].second));
  803.         while (true)
  804.         {
  805.             rank_right[j][patial_sort_result_for_different_d_right[k]] = assist_info_right[j].size() - 1;
  806.             if (k >= patial_sort_result_for_different_d_right.size() - 1 || enclosed_rectangle_group[patial_sort_result_for_different_d_right[k]][j].second != enclosed_rectangle_group[patial_sort_result_for_different_d_right[k + 1]][j].second)
  807.             {
  808.                 ++k;
  809.                 break;
  810.             }
  811.             ++assist_info_right[j].back().num;
  812.             ++k;
  813.         }
  814.     }
  815. }
  816.  template <typename T>
  817.  T RStarTree<T>::compute_margin_sum(bool left_left, size_t i, vector<size_t> &sort_result_left, vector<vector<pair<T, T>>>& enclosed_rectangle_group, vector<vector<AssistInfo<T>>> &assist_info_left_left, vector<vector<size_t>> &rank_left_left, vector<vector<AssistInfo<T>>>& assist_info_left_right, vector<vector<size_t>>& rank_left_right,
  818.      vector<pair<vector<pair<T, T>>, vector<pair<T, T>>>> &rect_pair, vector<size_t> &spilit_point_for_every_different_rect_pair)
  819.  {
  820.      vector<pair<T, T>> rect_left;
  821.      computeReactAll(rect_left, sort_result_left, 0, m - 1, enclosed_rectangle_group);
  822.      vector<pair<T, T>> rect_right;
  823.      computeReactAll(rect_right, sort_result_left, m, M, enclosed_rectangle_group);
  824.      T cur_margin_sum_for_rect_pair_left = margin(rect_left);
  825.      T cur_margin_sum_for_rect_pair_right = margin(rect_right);
  826.      T margin_sum_value = cur_margin_sum_for_rect_pair_left + cur_margin_sum_for_rect_pair_right;
  827.      rect_pair.push_back(make_pair(rect_left, rect_right));
  828.      spilit_point_for_every_different_rect_pair.push_back(m - 1);
  829.      T cur_margin_sum_for_rect_pair = margin_sum_value;
  830.      for (size_t j = m; j <= M - m; ++j)
  831.      {
  832.          bool equal_left = computeRect(rect_left, enclosed_rectangle_group[sort_result_left[j]]);
  833.          bool equal_right = true;
  834.          for (size_t q = 0; q < d; ++q)
  835.          {
  836.              if (q == i)
  837.              {
  838.                  if (assist_info_left_left[q].empty())  ///注意
  839.                  {
  840.                      if (left_left && enclosed_rectangle_group[sort_result_left[j]][i].first != enclosed_rectangle_group[sort_result_left[j + 1]][i].first)
  841.                      {
  842.                          rect_right[i].first = enclosed_rectangle_group[sort_result_left[j + 1]][i].first;
  843.                          equal_right = false;
  844.                      }
  845.                      if (assist_info_left_right[q].empty())
  846.                          continue;
  847.                  }
  848.              }
  849.       
  850.              if (assist_info_left_left[q].empty() == false)
  851.              {
  852.                  if (rank_left_left[q][sort_result_left[j]] != M + 1)
  853.                  {
  854.                      --assist_info_left_left[q][rank_left_left[q][sort_result_left[j]]].num;
  855.                      if (enclosed_rectangle_group[sort_result_left[j]][q].first == rect_right[q].first)
  856.                      {
  857.                          if (assist_info_left_left[q][rank_left_left[q][sort_result_left[j]]].num == 0)
  858.                          {
  859.                              size_t z = rank_left_left[q][sort_result_left[j]] + 1;
  860.                              for (; ; ++z)
  861.                              {
  862.                                  if (assist_info_left_left[q][z].num != 0)
  863.                                      break;
  864.                              }
  865.                              rect_right[q].first = assist_info_left_left[q][z].endpoint;
  866.                              equal_right = false;
  867.                          }
  868.                      }
  869.                  }
  870.              }
  871.  
  872.              if (assist_info_left_right[q].empty() == false)
  873.              {
  874.                  if (rank_left_right[q][sort_result_left[j]] != M + 1)
  875.                  {
  876.                      --assist_info_left_right[q][rank_left_right[q][sort_result_left[j]]].num;
  877.                      if (enclosed_rectangle_group[sort_result_left[j]][q].second == rect_right[q].second)
  878.                      {
  879.                          if (assist_info_left_right[q][rank_left_right[q][sort_result_left[j]]].num == 0)
  880.                          {
  881.                              size_t z = rank_left_right[q][sort_result_left[j]] - 1;
  882.                              for (; ; --z)
  883.                              {
  884.                                  if (assist_info_left_left[q][z].num != 0)
  885.                                      break;
  886.                              }
  887.                              rect_right[q].second = assist_info_left_right[q][z].endpoint;
  888.                              equal_right = false;
  889.                          }
  890.                      }
  891.                  }
  892.              }
  893.          }
  894.          if (equal_left)
  895.          {
  896.              if (equal_right == false)
  897.              {
  898.                  cur_margin_sum_for_rect_pair_right = margin(rect_right);
  899.              }
  900.          }
  901.          else
  902.          {
  903.              if (equal_right)
  904.              {
  905.                  cur_margin_sum_for_rect_pair_left = margin(rect_left);
  906.              }
  907.              else
  908.              {
  909.                  cur_margin_sum_for_rect_pair_left = margin(rect_left);
  910.                  cur_margin_sum_for_rect_pair_right = margin(rect_right);
  911.              }
  912.          }
  913.  
  914.          if (equal_left == false || equal_right == false)
  915.          {
  916.              cur_margin_sum_for_rect_pair = cur_margin_sum_for_rect_pair_left + cur_margin_sum_for_rect_pair_right;
  917.              rect_pair.push_back(make_pair(rect_left, rect_right));
  918.              spilit_point_for_every_different_rect_pair.push_back(j);
  919.          }
  920.          margin_sum_value += cur_margin_sum_for_rect_pair;
  921.      }
  922.      return margin_sum_value;
  923.  }
  924.  
  925.  template <typename T>
  926.  pair<size_t, size_t> getIntersection(pair<T, T> l, pair<T, T> j) 
  927.  {
  928.      if (l.second < j.first)
  929.      {
  930.          return { j.first, l.second};
  931.      }
  932.      else if (l.first > j.second)
  933.      {
  934.          return {l.first, j.second};
  935.      }
  936.      if (j.first <= l.first)
  937.      {
  938.          if (j.second < l.second)
  939.              return { l.first, j.second };
  940.          return l;
  941.      }
  942.  
  943.      if (j.second <= l.second)
  944.          return j;
  945.      return { j.first, l.second };
  946.  }
  947.  
  948.  template <typename T>
  949.  T RStarTree<T>::computeArea(vector<pair<T, T>> &cur)
  950.  {
  951.      bool zero_s = true;
  952.      T add_area = one;
  953.      for (size_t i = 0; i < d; ++i)
  954.      {
  955.          if (cur[i].first < cur[i].second)
  956.          {
  957.              add_area *= cur[i].second - cur[i].first;
  958.              zero_s = false;
  959.          }
  960.      }
  961.      if (zero_s)
  962.          return zero;
  963.      return add_area;
  964.  }
  965.  
  966.  template <typename T>
  967.  bool RStarTree<T>::getInterRect(vector<pair<T, T>> &be_filled, vector<pair<T, T>> &A, vector<pair<T, T>> &B)
  968.  {
  969.      for (size_t i = 0; i < d; ++i)
  970.      {
  971.          pair<T, T> inter = getIntersection(A[i], B[i]);
  972.          if (inter.first > inter.second)
  973.              return false;
  974.          be_filled[i] = inter;
  975.      }
  976.      return true;
  977.  }
  978.  
  979.  template <typename T>
  980.  void RStarTree<T>::findBestSpilit(vector<size_t> &spilit_point_for_every_different_rect_pair, list<pair<vector<pair<T, T>>, vector<pair<T, T>>>> &best_spilit_react, list<size_t> &best_spilit_point, T &best_inter_area, vector<pair<vector<pair<T, T>>, vector<pair<T, T>>>> &left_rect_pair)
  981.  {         
  982.      for (size_t i = 0; i < left_rect_pair.size(); ++i)
  983.      {
  984.          vector<pair<T, T>> be_filled(d);
  985.          T area;
  986.          if (getInterRect(be_filled, left_rect_pair[i].first, left_rect_pair[i].second))
  987.          {
  988.              area = computeArea(be_filled);
  989.          }
  990.          else
  991.          {
  992.              area = zero;
  993.          }
  994.  
  995.          if (i == 0 || area < best_inter_area || area == best_inter_area)
  996.          {
  997.              if (i == 0 || area < best_inter_area)
  998.              {
  999.                  if (i != 0)
  1000.                  {
  1001.                      best_spilit_point.clear();
  1002.                      best_spilit_react.clear();
  1003.                  }
  1004.                  best_inter_area = area;
  1005.              }
  1006.              best_spilit_point.push_back(spilit_point_for_every_different_rect_pair[i]);
  1007.              best_spilit_react.push_back(make_pair(left_rect_pair[i].first, left_rect_pair[i].second));
  1008.          }
  1009.      }
  1010.  }
  1011.  
  1012.  template <typename T>
  1013.  T RStarTree<T>::findBestSpilitPlan(list<pair<vector<pair<T, T>>, vector<pair<T, T>>>> &best_spilit_react, list<size_t> &best_spilit_point, size_t &best_spilit_point_value, pair<vector<pair<T, T>>, vector<pair<T, T>>> &best_spilit_react_pair)
  1014.  {
  1015.      T best_area_sum;
  1016.      list<size_t>::iterator run2 = best_spilit_point.begin();
  1017.      typename list<pair<vector<pair<T, T>>, vector<pair<T, T>>>>::iterator run = best_spilit_react.begin();
  1018.  
  1019.      best_area_sum = computeArea(run->first) + computeArea(run->second);
  1020.      best_spilit_point_value = best_spilit_point.front();
  1021.      best_spilit_react_pair = *run;
  1022.      for (++run, ++run2; run != best_spilit_react.end(); ++run, ++run2)
  1023.      {
  1024.          T a = computeArea(run->first) + computeArea(run->second);
  1025.          if (a < best_area_sum)
  1026.          {
  1027.              best_area_sum = a;
  1028.              best_spilit_point_value = *run2;
  1029.              best_spilit_react_pair = *run;
  1030.          }
  1031.      }
  1032.      return best_area_sum;
  1033.  }
  1034.  
  1035. template <typename T>
  1036. pair<pair<vector<pair<T, T>>, vector<pair<T, T>>>, RStarTreeNode<T>*> RStarTree<T>::spilit(RStarTreeNode<T>* node)  //注意该函数中没有删除node节点
  1037. {
  1038.     T d_margin;
  1039.     vector<size_t> sort_result_best_left;
  1040.     vector<size_t> sort_result_best_right;
  1041.     vector<pair<vector<pair<T, T>>, vector<pair<T, T>>>> left_rect_pair;
  1042.     vector<pair<vector<pair<T, T>>, vector<pair<T, T>>>> right_rect_pair;
  1043.     vector<size_t> spilit_point_for_every_different_rect_pair_left_best;
  1044.     vector<size_t> spilit_point_for_every_different_rect_pair_right_best;
  1045.     vector<vector<pair<T, T>>>& enclosed_rectangle_group = node->enclosed_rectangle_group;
  1046.     for (size_t i = 0; i < d; ++i)
  1047.     {
  1048.         vector<size_t> sort_result_left(M + 1);
  1049.         vector<size_t> sort_result_right(M + 1);
  1050.         for (size_t j = 0; j <= M; ++j)
  1051.         {
  1052.             sort_result_left[j] = j;
  1053.             sort_result_right[j] = j;
  1054.         }
  1055.         sort(sort_result_left.begin(), sort_result_left.end(), Sort_for_interval_and_dimension<T>(enclosed_rectangle_group, i, true));
  1056.         sort(sort_result_right.begin(), sort_result_right.end(), Sort_for_interval_and_dimension<T>(enclosed_rectangle_group, i, false));
  1057.  
  1058.         vector<vector<AssistInfo<T>>> assist_info_left_left(d, vector<AssistInfo<T>>());
  1059.         vector<vector<AssistInfo<T>>> assist_info_left_right(d, vector<AssistInfo<T>>());
  1060.         vector<vector<size_t>> rank_left_left(d, vector<size_t>(M + 1, M + 1));
  1061.         vector<vector<size_t>> rank_left_right(d, vector<size_t>(M + 1, M + 1));
  1062.         vector<vector<size_t>> rank_right_left(d, vector<size_t>(M + 1, M + 1));
  1063.         vector<vector<size_t>> rank_right_right(d, vector<size_t>(M + 1, M + 1));
  1064.         vector<vector<AssistInfo<T>>> assist_info_right_left(d, vector<AssistInfo<T>>());
  1065.         vector<vector<AssistInfo<T>>> assist_info_right_right(d, vector<AssistInfo<T>>());
  1066.  
  1067.         for (size_t j = 0; j < d; ++j)
  1068.         {
  1069.             if (j != i)
  1070.             {
  1071.                 vector<size_t> patial_sort_result_for_different_d_left_left;
  1072.                 if (compute_patial_sort_result(j, patial_sort_result_for_different_d_left_left, sort_result_left, enclosed_rectangle_group, true) == false)
  1073.                 {
  1074.                     compute_assist(j, patial_sort_result_for_different_d_left_left, enclosed_rectangle_group, assist_info_left_left, rank_left_left);
  1075.                 }             
  1076.             }
  1077.             vector<size_t> patial_sort_result_for_different_d_left_right;
  1078.             if (compute_patial_sort_result(j, patial_sort_result_for_different_d_left_right, sort_result_left, enclosed_rectangle_group, false) == false)
  1079.                 compute_assist(j, patial_sort_result_for_different_d_left_right, enclosed_rectangle_group, assist_info_left_right, rank_left_right);
  1080.  
  1081.             if (j != i)
  1082.             {
  1083.                 vector<size_t> patial_sort_result_for_different_d_right_right;
  1084.                 if (compute_patial_sort_result(j, patial_sort_result_for_different_d_right_right, sort_result_right, enclosed_rectangle_group, false) == false)
  1085.                     compute_assist_right(j, patial_sort_result_for_different_d_right_right, enclosed_rectangle_group, assist_info_right_right, rank_right_right);
  1086.             }
  1087.             vector<size_t> patial_sort_result_for_different_d_right_left;
  1088.             if (compute_patial_sort_result(j, patial_sort_result_for_different_d_right_left, sort_result_right, enclosed_rectangle_group, true) == false)
  1089.                compute_assist_right(j, patial_sort_result_for_different_d_right_left, enclosed_rectangle_group, assist_info_right_left, rank_right_left);
  1090.         }
  1091.  
  1092.         vector<pair<vector<pair<T, T>>, vector<pair<T, T>>>> left_rect_pair_cur;  left_rect_pair_cur.reserve(M + 2 - 2 * m);
  1093.         vector<pair<vector<pair<T, T>>, vector<pair<T, T>>>> right_rect_pair_cur; right_rect_pair_cur.reserve(M + 2 - 2 * m);
  1094.         vector<size_t> spilit_point_for_every_different_rect_pair_left;   spilit_point_for_every_different_rect_pair_left.reserve(M + 2 - 2 * m);
  1095.         vector<size_t> spilit_point_for_every_different_rect_pair_right;  spilit_point_for_every_different_rect_pair_right.reserve(M + 2 - 2 * m);
  1096.         T margin_sum_value = compute_margin_sum(true, i, sort_result_left, enclosed_rectangle_group, assist_info_left_left, rank_left_left, assist_info_left_right, rank_left_right, left_rect_pair_cur, spilit_point_for_every_different_rect_pair_left);
  1097.         margin_sum_value += compute_margin_sum(false, i, sort_result_right, enclosed_rectangle_group, assist_info_right_left, rank_right_left, assist_info_right_right, rank_right_right, right_rect_pair_cur, spilit_point_for_every_different_rect_pair_right);
  1098.         if (i == 0 || d_margin > margin_sum_value)
  1099.         {
  1100.             d_margin = margin_sum_value;
  1101.             swap(sort_result_best_left, sort_result_left);
  1102.             swap(sort_result_best_right, sort_result_right);
  1103.             swap(left_rect_pair, left_rect_pair_cur);
  1104.             swap(right_rect_pair, right_rect_pair_cur);
  1105.             swap(spilit_point_for_every_different_rect_pair_left_best, spilit_point_for_every_different_rect_pair_left);
  1106.             swap(spilit_point_for_every_different_rect_pair_right_best, spilit_point_for_every_different_rect_pair_right);
  1107.         }
  1108.     }
  1109.  
  1110.     list<pair<vector<pair<T, T>>, vector<pair<T, T>>>> best_spilit_react;
  1111.     list<size_t> best_spilit_point;
  1112.     T best_inter_area;
  1113.     findBestSpilit(spilit_point_for_every_different_rect_pair_left_best, best_spilit_react, best_spilit_point, best_inter_area, left_rect_pair);
  1114.  
  1115.  
  1116.     list<pair<vector<pair<T, T>>, vector<pair<T, T>>>> best_spilit_react_right;
  1117.     list<size_t> best_spilit_point_right;
  1118.     T best_inter_area_right;
  1119.     findBestSpilit(spilit_point_for_every_different_rect_pair_right_best, best_spilit_react_right, best_spilit_point_right, best_inter_area_right, right_rect_pair);
  1120.  
  1121.     size_t best_spilit_point_value;
  1122.     pair<vector<pair<T, T>>, vector<pair<T, T>>> best_spilit_react_pair;
  1123.     vector<size_t> sort_result;
  1124.     if (best_inter_area < best_inter_area_right)
  1125.     {       
  1126.         findBestSpilitPlan(best_spilit_react, best_spilit_point, best_spilit_point_value, best_spilit_react_pair);
  1127.         sort_result = sort_result_best_left;
  1128.     }
  1129.     else if (best_inter_area > best_inter_area_right)
  1130.     {
  1131.         findBestSpilitPlan(best_spilit_react_right, best_spilit_point_right, best_spilit_point_value, best_spilit_react_pair);
  1132.         sort_result = sort_result_best_right;
  1133.     }
  1134.     else
  1135.     {
  1136.         size_t best_spilit_point_value_right;
  1137.         pair<vector<pair<T, T>>, vector<pair<T, T>>> best_spilit_react_pair_right;
  1138.         T a_s_l = findBestSpilitPlan(best_spilit_react, best_spilit_point, best_spilit_point_value, best_spilit_react_pair);
  1139.         T a_s_r = findBestSpilitPlan(best_spilit_react_right, best_spilit_point_right, best_spilit_point_value_right, best_spilit_react_pair_right);
  1140.         if (a_s_r < a_s_l)
  1141.         {
  1142.             best_spilit_point_value = best_spilit_point_value_right;
  1143.             swap(best_spilit_react_pair, best_spilit_react_pair_right);
  1144.             swap(sort_result, sort_result_best_right);
  1145.         }
  1146.         else
  1147.         {
  1148.             swap(sort_result, sort_result_best_left);
  1149.         }
  1150.     }
  1151.  
  1152.     vector<vector<pair<T, T>>> left;
  1153.     vector<RStarTreeNode<T>*> left_p;
  1154.     RStarTreeNode<T>* right = new RStarTreeNode<T>(M);
  1155.     for (size_t i = 0; i <= best_spilit_point_value; ++i)
  1156.     {
  1157.         left.push_back(enclosed_rectangle_group[sort_result[i]]);
  1158.         if (node->pointer_to_sub_tree.empty() == false)
  1159.         {
  1160.             left_p.push_back(node->pointer_to_sub_tree[sort_result[i]]);
  1161.         }
  1162.     }
  1163.  
  1164.     for (size_t i = best_spilit_point_value + 1; i <= M; ++i)
  1165.     {
  1166.         right->enclosed_rectangle_group.push_back(enclosed_rectangle_group[sort_result[i]]);
  1167.         if (node->pointer_to_sub_tree.empty() == false)
  1168.         {
  1169.             right->pointer_to_sub_tree.push_back(node->pointer_to_sub_tree[sort_result[i]]);
  1170.         }
  1171.     }
  1172.     enclosed_rectangle_group = left;
  1173.     node->pointer_to_sub_tree = left_p;
  1174.     return make_pair(best_spilit_react_pair, right);
  1175. }
  1176.  
  1177. template <typename T>
  1178. bool RStarTree<T>::checkRTree(RStarTreeNode<T>* cur, bool isRoot, size_t &height, vector<pair<T, T>> &enclosedRect)
  1179. {
  1180.     if (isRoot)
  1181.     {
  1182.         if (cur == nullptr)
  1183.             return true;
  1184.  
  1185.         if (cur->pointer_to_sub_tree.empty())
  1186.         {
  1187.             if (cur->enclosed_rectangle_group.empty() || cur->enclosed_rectangle_group.size() > M)
  1188.             {
  1189.                 return false;
  1190.             }
  1191.         }
  1192.         else
  1193.         {
  1194.             if (cur->enclosed_rectangle_group.size() < 2 || cur->enclosed_rectangle_group.size() > M)
  1195.             {
  1196.                 return false;
  1197.             }
  1198.         }
  1199.     }
  1200.     else
  1201.     {
  1202.         if (cur->enclosed_rectangle_group.size() < m || cur->enclosed_rectangle_group.size() > M)
  1203.         {
  1204.             cout << "大小越界";
  1205.             system("pause");
  1206.             return false;
  1207.         }
  1208.     }
  1209.  
  1210.     if (cur->pointer_to_sub_tree.empty() == false)
  1211.     {
  1212.         if (cur->enclosed_rectangle_group.size() != cur->pointer_to_sub_tree.size())
  1213.             return false;
  1214.         size_t h;
  1215.         for (size_t i = 0; i < cur->pointer_to_sub_tree.size(); ++i)
  1216.         {
  1217.             if (checkRTree(cur->pointer_to_sub_tree[i], false, h, enclosedRect) == false)
  1218.                 return false;
  1219.  
  1220.             if (i == 0)
  1221.             {
  1222.                 height = h;
  1223.             }
  1224.             else if (h != height)
  1225.             {
  1226.                 cout << "高度不等";
  1227.                 system("pause");
  1228.                 return false;
  1229.             }
  1230.             if (rectEqual(cur->enclosed_rectangle_group[i], enclosedRect) == false)
  1231.             {
  1232.                 cout << "矩形不完全包围";
  1233.                 system("pause");
  1234.                 return false;
  1235.             }
  1236.         }
  1237.     }
  1238.  
  1239.     if (isRoot == false)
  1240.     {
  1241.         if (cur->pointer_to_sub_tree.empty())
  1242.         {
  1243.             enclosedRect = cur->enclosed_rectangle_group.back();
  1244.             height = 0;
  1245.         }
  1246.  
  1247.         for (size_t i = cur->enclosed_rectangle_group.size() - 2; ; --i)
  1248.         {
  1249.             computeRect(enclosedRect, cur->enclosed_rectangle_group[i]);
  1250.             if (i == 0)
  1251.                 break;
  1252.         }
  1253.         ++height;
  1254.     }
  1255.     return true;
  1256. }
  1257. ostream& operator<<(ostream& c, vector<pair<int, int>>& cur)
  1258. {
  1259.     for (size_t i = 0; i < cur.size(); ++i)
  1260.     {
  1261.         cout << "[" << cur[i].first << "," << cur[i].second << "] ";
  1262.     }
  1263.     return c;
  1264. }
  1265. template <typename T>
  1266. bool RStarTree<T>::isRTree()
  1267. {
  1268.     size_t height;
  1269.     vector<pair<T, T>> enclosedRect;
  1270.     return checkRTree(root, true, height, enclosedRect);
  1271. }
  1272. int main()
  1273. {
  1274.     const int N = 20;
  1275.     vector<int> test(N);
  1276.     for (size_t i = 0; i < N; ++i)
  1277.     {
  1278.         test[i] = i + 1;
  1279.     }
  1280.  
  1281.     vector<pair<int, int>> data_rect(N*(N-1)/2);
  1282.     size_t j = 0;
  1283.     for (size_t i = 0; i < test.size() - 1; ++i)
  1284.     {
  1285.         for (size_t k = i + 1; k < test.size(); ++k)
  1286.         {
  1287.             data_rect[j++] = make_pair(test[i], test[k]);
  1288.         }
  1289.     }
  1290.     shuffle(data_rect.begin(), data_rect.end(), default_random_engine());
  1291.     vector<vector<pair<int, int>>> insert(data_rect.size() *(data_rect.size() - 1) / 2, vector<pair<int, int>>(2));
  1292.     j = 0;
  1293.     for (size_t i = 0; i < data_rect.size() - 1; ++i)
  1294.     {
  1295.         for (size_t k = i + 1; k < data_rect.size(); ++k)
  1296.         {
  1297.             insert[j][0] = data_rect[i];
  1298.             insert[j++][1] = data_rect[k];
  1299.         }
  1300.     }
  1301.  
  1302.     RStarTree<int> obj(2, 2, 3, 0, 1, 2);
  1303.     for (size_t i = 0; i < insert.size(); ++i)
  1304.     {
  1305.         if (i == 70)
  1306.             system("pause");
  1307.         cout << "插入" << endl;
  1308.         cout << insert[i] << endl;
  1309.         obj.insertData(insert[i]);
  1310.         if (obj.isRTree() == false)
  1311.         {
  1312.             cout << "Error:不是R树!" << endl;
  1313.             exit(-1);
  1314.         }
  1315.         else
  1316.         {
  1317.             cout << "当前树是R树" << endl;
  1318.         }
  1319.     }
  1320.  
  1321.     for (size_t i = 0; i < insert.size(); ++i)
  1322.     {
  1323.         cout << "删除" << endl;
  1324.         cout << insert[i] << endl;
  1325.         if (obj.remove(insert[i]))
  1326.         {
  1327.             cout << "删除成功" << endl;
  1328.         }
  1329.         else
  1330.         {
  1331.             cout << "删除失败" << endl;
  1332.             exit(-1);
  1333.         }
  1334.  
  1335.         if (obj.isRTree() == false)
  1336.         {
  1337.             cout << "Error:不是R树!" << endl;
  1338.             exit(-1);
  1339.         }
  1340.         else
  1341.         {
  1342.             cout << "当前树是R树" << endl;
  1343.         }
  1344.     }
  1345.     return 0;
  1346. }
  1347.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/476025
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号