boost/geometry/index/detail/rtree/quadratic/redistribute_elements.hpp

   1 // Boost.Geometry Index
   2 //
   3 // R-tree quadratic split algorithm implementation
   4 //
   5 // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
   6 //
   7 // Use, modification and distribution is subject to the Boost Software License,
   8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   9 // http://www.boost.org/LICENSE_1_0.txt)
  10
  11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
  12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
  13
  14 #include <algorithm>
  15
  16 #include <boost/geometry/index/detail/algorithms/content.hpp>
  17 #include <boost/geometry/index/detail/algorithms/union_content.hpp>
  18
  19 #include <boost/geometry/index/detail/bounded_view.hpp>
  20
  21 #include <boost/geometry/index/detail/rtree/node/node.hpp>
  22 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
  23 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
  24
  25 namespace boost { namespace geometry { namespace index {
  26
  27 namespace detail { namespace rtree {
  28
  29 namespace quadratic {
  30
  31 template <typename Box, typename Elements, typename Parameters, typename Translator>
  32 inline void pick_seeds(Elements const& elements,
  33                        Parameters const& parameters,
  34                        Translator const& tr,
  35                        size_t & seed1,
  36                        size_t & seed2)
  37 {
  38     typedef typename Elements::value_type element_type;
  39     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
  40     typedef Box box_type;
  41     typedef typename index::detail::default_content_result<box_type>::type content_type;
  42     typedef index::detail::bounded_view<indexable_type, box_type> bounded_indexable_view;
  43
  44     const size_t elements_count = parameters.get_max_elements() + 1;
  45     BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "wrong number of elements");
  46     BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
  47
  48     content_type greatest_free_content = 0;
  49     seed1 = 0;
  50     seed2 = 1;
  51
  52     for ( size_t i = 0 ; i < elements_count - 1 ; ++i )
  53     {
  54         for ( size_t j = i + 1 ; j < elements_count ; ++j )
  55         {
  56             indexable_type const& ind1 = rtree::element_indexable(elements[i], tr);
  57             indexable_type const& ind2 = rtree::element_indexable(elements[j], tr);
  58
  59             box_type enlarged_box;
  60             //geometry::convert(ind1, enlarged_box);
  61             detail::bounds(ind1, enlarged_box);
  62             geometry::expand(enlarged_box, ind2);
  63
  64             bounded_indexable_view bounded_ind1(ind1);
  65             bounded_indexable_view bounded_ind2(ind2);
  66             content_type free_content = ( index::detail::content(enlarged_box)
  67                                             - index::detail::content(bounded_ind1) )
  68                                                 - index::detail::content(bounded_ind2);
  69
  70             if ( greatest_free_content < free_content )
  71             {
  72                 greatest_free_content = free_content;
  73                 seed1 = i;
  74                 seed2 = j;
  75             }
  76         }
  77     }
  78
  79     ::boost::ignore_unused_variable_warning(parameters);
  80 }
  81
  82 } // namespace quadratic
  83
  84 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
  85 struct redistribute_elements<Value, Options, Translator, Box, Allocators, quadratic_tag>
  86 {
  87     typedef typename Options::parameters_type parameters_type;
  88
  89     typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
  90     typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
  91     typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
  92
  93     typedef typename index::detail::default_content_result<Box>::type content_type;
  94
  95     template <typename Node>
  96     static inline void apply(Node & n,
  97                              Node & second_node,
  98                              Box & box1,
  99                              Box & box2,
 100                              parameters_type const& parameters,
 101                              Translator const& translator,
 102                              Allocators & allocators)
 103     {
 104         typedef typename rtree::elements_type<Node>::type elements_type;
 105         typedef typename elements_type::value_type element_type;
 106         typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
 107
 108         elements_type & elements1 = rtree::elements(n);
 109         elements_type & elements2 = rtree::elements(second_node);
 110
 111         BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == parameters.get_max_elements() + 1, "unexpected elements number");
 112
 113         // copy original elements - use in-memory storage (std::allocator)
 114         // TODO: move if noexcept
 115         typedef typename rtree::container_from_elements_type<elements_type, element_type>::type
 116             container_type;
 117         container_type elements_copy(elements1.begin(), elements1.end());                                   // MAY THROW, STRONG (alloc, copy)
 118         container_type elements_backup(elements1.begin(), elements1.end());                                 // MAY THROW, STRONG (alloc, copy)
 119
 120         // calculate initial seeds
 121         size_t seed1 = 0;
 122         size_t seed2 = 0;
 123         quadratic::pick_seeds<Box>(elements_copy, parameters, translator, seed1, seed2);
 124
 125         // prepare nodes' elements containers
 126         elements1.clear();
 127         BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "second node's elements container should be empty");
 128
 129         BOOST_TRY
 130         {
 131             // add seeds
 132             elements1.push_back(elements_copy[seed1]);                                                      // MAY THROW, STRONG (copy)
 133             elements2.push_back(elements_copy[seed2]);                                                      // MAY THROW, STRONG (alloc, copy)
 134
 135             // calculate boxes
 136             //geometry::convert(rtree::element_indexable(elements_copy[seed1], translator), box1);
 137             detail::bounds(rtree::element_indexable(elements_copy[seed1], translator), box1);
 138             //geometry::convert(rtree::element_indexable(elements_copy[seed2], translator), box2);
 139             detail::bounds(rtree::element_indexable(elements_copy[seed2], translator), box2);
 140
 141             // remove seeds
 142             if (seed1 < seed2)
 143             {
 144                 rtree::move_from_back(elements_copy, elements_copy.begin() + seed2);                        // MAY THROW, STRONG (copy)
 145                 elements_copy.pop_back();
 146                 rtree::move_from_back(elements_copy, elements_copy.begin() + seed1);                        // MAY THROW, STRONG (copy)
 147                 elements_copy.pop_back();
 148             }
 149             else
 150             {
 151                 rtree::move_from_back(elements_copy, elements_copy.begin() + seed1);                        // MAY THROW, STRONG (copy)
 152                 elements_copy.pop_back();
 153                 rtree::move_from_back(elements_copy, elements_copy.begin() + seed2);                        // MAY THROW, STRONG (copy)
 154                 elements_copy.pop_back();
 155             }
 156
 157             // initialize areas
 158             content_type content1 = index::detail::content(box1);
 159             content_type content2 = index::detail::content(box2);
 160
 161             size_t remaining = elements_copy.size();
 162
 163             // redistribute the rest of the elements
 164             while ( !elements_copy.empty() )
 165             {
 166                 typename container_type::reverse_iterator el_it = elements_copy.rbegin();
 167                 bool insert_into_group1 = false;
 168
 169                 size_t elements1_count = elements1.size();
 170                 size_t elements2_count = elements2.size();
 171
 172                 // if there is small number of elements left and the number of elements in node is lesser than min_elems
 173                 // just insert them to this node
 174                 if ( elements1_count + remaining <= parameters.get_min_elements() )
 175                 {
 176                     insert_into_group1 = true;
 177                 }
 178                 else if ( elements2_count + remaining <= parameters.get_min_elements() )
 179                 {
 180                     insert_into_group1 = false;
 181                 }
 182                 // insert the best element
 183                 else
 184                 {
 185                     // find element with minimum groups areas increses differences
 186                     content_type content_increase1 = 0;
 187                     content_type content_increase2 = 0;
 188                     el_it = pick_next(elements_copy.rbegin(), elements_copy.rend(),
 189                                       box1, box2, content1, content2, translator,
 190                                       content_increase1, content_increase2);
 191
 192                     if ( content_increase1 < content_increase2 ||
 193                          ( content_increase1 == content_increase2 && ( content1 < content2 ||
 194                            ( content1 == content2 && elements1_count <= elements2_count ) )
 195                          ) )
 196                     {
 197                         insert_into_group1 = true;
 198                     }
 199                     else
 200                     {
 201                         insert_into_group1 = false;
 202                     }
 203                 }
 204
 205                 // move element to the choosen group
 206                 element_type const& elem = *el_it;
 207                 indexable_type const& indexable = rtree::element_indexable(elem, translator);
 208
 209                 if ( insert_into_group1 )
 210                 {
 211                     elements1.push_back(elem);                                                              // MAY THROW, STRONG (copy)
 212                     geometry::expand(box1, indexable);
 213                     content1 = index::detail::content(box1);
 214                 }
 215                 else
 216                 {
 217                     elements2.push_back(elem);                                                              // MAY THROW, STRONG (alloc, copy)
 218                     geometry::expand(box2, indexable);
 219                     content2 = index::detail::content(box2);
 220                 }
 221
 222                 BOOST_GEOMETRY_INDEX_ASSERT(!elements_copy.empty(), "expected more elements");
 223                 typename container_type::iterator el_it_base = el_it.base();
 224                 rtree::move_from_back(elements_copy, --el_it_base);                                         // MAY THROW, STRONG (copy)
 225                 elements_copy.pop_back();
 226
 227                 BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "expected more remaining elements");
 228                 --remaining;
 229             }
 230         }
 231         BOOST_CATCH(...)
 232         {
 233             //elements_copy.clear();
 234             elements1.clear();
 235             elements2.clear();
 236
 237             rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_backup, allocators);
 238             //elements_backup.clear();
 239
 240             BOOST_RETHROW                                                                                     // RETHROW, BASIC
 241         }
 242         BOOST_CATCH_END
 243     }
 244
 245     // TODO: awulkiew - change following function to static member of the pick_next class?
 246
 247     template <typename It>
 248     static inline It pick_next(It first, It last,
 249                                Box const& box1, Box const& box2,
 250                                content_type const& content1, content_type const& content2,
 251                                Translator const& translator,
 252                                content_type & out_content_increase1, content_type & out_content_increase2)
 253     {
 254         typedef typename boost::iterator_value<It>::type element_type;
 255         typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
 256
 257         content_type greatest_content_incrase_diff = 0;
 258         It out_it = first;
 259         out_content_increase1 = 0;
 260         out_content_increase2 = 0;
 261
 262         // find element with greatest difference between increased group's boxes areas
 263         for ( It el_it = first ; el_it != last ; ++el_it )
 264         {
 265             indexable_type const& indexable = rtree::element_indexable(*el_it, translator);
 266
 267             // calculate enlarged boxes and areas
 268             Box enlarged_box1(box1);
 269             Box enlarged_box2(box2);
 270             geometry::expand(enlarged_box1, indexable);
 271             geometry::expand(enlarged_box2, indexable);
 272             content_type enlarged_content1 = index::detail::content(enlarged_box1);
 273             content_type enlarged_content2 = index::detail::content(enlarged_box2);
 274
 275             content_type content_incrase1 = (enlarged_content1 - content1);
 276             content_type content_incrase2 = (enlarged_content2 - content2);
 277
 278             content_type content_incrase_diff = content_incrase1 < content_incrase2 ?
 279                 content_incrase2 - content_incrase1 : content_incrase1 - content_incrase2;
 280
 281             if ( greatest_content_incrase_diff < content_incrase_diff )
 282             {
 283                 greatest_content_incrase_diff = content_incrase_diff;
 284                 out_it = el_it;
 285                 out_content_increase1 = content_incrase1;
 286                 out_content_increase2 = content_incrase2;
 287             }
 288         }
 289
 290         return out_it;
 291     }
 292 };
 293
 294 }} // namespace detail::rtree
 295
 296 }}} // namespace boost::geometry::index
 297
 298 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP