ceph/src/boost/libs/geometry/include/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-2015 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 = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr);
  64
  65         if ( m_exact_match )
  66             result = m_is_root || geometry::equals(box_exp, m_box);
  67         else
  68             result = m_is_root || geometry::covered_by(box_exp, m_box);
  69     }
  70
  71     void operator()(leaf const& n)
  72     {
  73         typedef typename rtree::elements_type<leaf>::type elements_type;
  74         elements_type const& elements = rtree::elements(n);
  75
  76         // non-root node
  77         if (!m_is_root)
  78         {
  79             if ( elements.empty() )
  80             {
  81                 result = false;
  82                 return;
  83             }
  84
  85             Box box_exp = rtree::values_box<Box>(elements.begin(), elements.end(), m_tr);
  86
  87             if ( m_exact_match )
  88                 result = geometry::equals(box_exp, m_box);
  89             else
  90                 result = geometry::covered_by(box_exp, m_box);
  91         }
  92         else
  93             result = true;
  94     }
  95
  96     bool result;
  97
  98 private:
  99     Translator const& m_tr;
 100     Box m_box;
 101     bool m_is_root;
 102     bool m_exact_match;
 103 };
 104
 105 } // namespace visitors
 106
 107 template <typename Rtree> inline
 108 bool are_boxes_ok(Rtree const& tree, bool exact_match = true)
 109 {
 110     typedef utilities::view<Rtree> RTV;
 111     RTV rtv(tree);
 112
 113     visitors::are_boxes_ok<
 114         typename RTV::value_type,
 115         typename RTV::options_type,
 116         typename RTV::translator_type,
 117         typename RTV::box_type,
 118         typename RTV::allocators_type
 119     > v(rtv.translator(), exact_match);
 120
 121     rtv.apply_visitor(v);
 122
 123     return v.result;
 124 }
 125
 126 }}}}}} // namespace boost::geometry::index::detail::rtree::utilities
 127
 128 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_BOXES_OK_HPP