boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp

   1 // Boost.Geometry Index
   2 //
   3 // R-tree boxes validating visitor 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_UTILITIES_ARE_BOXES_OK_HPP
  12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_BOXES_OK_HPP
  13
  14 #include <boost/geometry/algorithms/equals.hpp>
  15 #include <boost/geometry/index/detail/rtree/node/node.hpp>
  16
  17 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities {
  18
  19 namespace visitors {
  20
  21 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
  22 class are_boxes_ok
  23     : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
  24 {
  25     typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
  26     typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
  27
  28 public:
  29     are_boxes_ok(Translator const& tr, bool exact_match)
  30         : result(false), m_tr(tr), m_is_root(true), m_exact_match(exact_match)
  31     {}
  32
  33     void operator()(internal_node const& n)
  34     {
  35         typedef typename rtree::elements_type<internal_node>::type elements_type;
  36         elements_type const& elements = rtree::elements(n);
  37
  38         if (elements.empty())
  39         {
  40             result = false;
  41             return;
  42         }
  43
  44         Box box_bckup = m_box;
  45         bool is_root_bckup = m_is_root;
  46
  47         m_is_root = false;
  48
  49         for ( typename elements_type::const_iterator it = elements.begin();
  50               it != elements.end() ; ++it)
  51         {
  52             m_box = it->first;
  53
  54             rtree::apply_visitor(*this, *it->second);
  55
  56             if ( result == false )
  57                 return;
  58         }
  59
  60         m_box = box_bckup;
  61         m_is_root = is_root_bckup;
  62
  63         Box box_exp;
  64         geometry::convert(elements.front().first, box_exp);
  65         for( typename elements_type::const_iterator it = elements.begin() + 1;
  66             it != elements.end() ; ++it)
  67         {
  68             geometry::expand(box_exp, it->first);
  69         }
  70
  71         if ( m_exact_match )
  72             result = m_is_root || geometry::equals(box_exp, m_box);
  73         else
  74             result = m_is_root || geometry::covered_by(box_exp, m_box);
  75     }
  76
  77     void operator()(leaf const& n)
  78     {
  79         typedef typename rtree::elements_type<leaf>::type elements_type;
  80         elements_type const& elements = rtree::elements(n);
  81
  82         // non-root node
  83         if (!m_is_root)
  84         {
  85             if ( elements.empty() )
  86             {
  87                 result = false;
  88                 return;
  89             }
  90
  91             Box box_exp;
  92             geometry::convert(
  93                 index::detail::return_ref_or_bounds(m_tr(elements.front())),
  94                 box_exp);
  95             for(typename elements_type::const_iterator it = elements.begin() + 1;
  96                 it != elements.end() ; ++it)
  97             {
  98                 geometry::expand(box_exp, m_tr(*it));
  99             }
 100
 101             if ( m_exact_match )
 102                 result = geometry::equals(box_exp, m_box);
 103             else
 104                 result = geometry::covered_by(box_exp, m_box);
 105         }
 106         else
 107             result = true;
 108     }
 109
 110     bool result;
 111
 112 private:
 113     Translator const& m_tr;
 114     Box m_box;
 115     bool m_is_root;
 116     bool m_exact_match;
 117 };
 118
 119 } // namespace visitors
 120
 121 template <typename Rtree> inline
 122 bool are_boxes_ok(Rtree const& tree, bool exact_match = true)
 123 {
 124     typedef utilities::view<Rtree> RTV;
 125     RTV rtv(tree);
 126
 127     visitors::are_boxes_ok<
 128         typename RTV::value_type,
 129         typename RTV::options_type,
 130         typename RTV::translator_type,
 131         typename RTV::box_type,
 132         typename RTV::allocators_type
 133     > v(rtv.translator(), exact_match);
 134
 135     rtv.apply_visitor(v);
 136
 137     return v.result;
 138 }
 139
 140 }}}}}} // namespace boost::geometry::index::detail::rtree::utilities
 141
 142 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_BOXES_OK_HPP