rtree/utilities/are_boxes_ok.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree boxes validating visitor implementation
0004 //
0005 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2019.
0008 // Modifications copyright (c) 2019 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010 //
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_BOXES_OK_HPP
0016 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_BOXES_OK_HPP
0017
0018 #include <boost/geometry/algorithms/equals.hpp>
0019 #include <boost/geometry/index/detail/rtree/node/node.hpp>
0020
0021 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities {
0022
0023 namespace visitors {
0024
0025 template <typename MembersHolder>
0026 class are_boxes_ok
0027     : public MembersHolder::visitor_const
0028 {
0029     typedef typename MembersHolder::box_type box_type;
0030     typedef typename MembersHolder::parameters_type parameters_type;
0031     typedef typename MembersHolder::translator_type translator_type;
0032
0033     typedef typename MembersHolder::internal_node internal_node;
0034     typedef typename MembersHolder::leaf leaf;
0035
0036 public:
0037     are_boxes_ok(parameters_type const& parameters, translator_type const& tr, bool exact_match)
0038         : result(false), m_parameters(parameters), m_tr(tr), m_is_root(true), m_exact_match(exact_match)
0039     {}
0040
0041     void operator()(internal_node const& n)
0042     {
0043         typedef typename rtree::elements_type<internal_node>::type elements_type;
0044         elements_type const& elements = rtree::elements(n);
0045
0046         if (elements.empty())
0047         {
0048             result = false;
0049             return;
0050         }
0051
0052         box_type box_bckup = m_box;
0053         bool is_root_bckup = m_is_root;
0054
0055         m_is_root = false;
0056
0057         for ( typename elements_type::const_iterator it = elements.begin();
0058               it != elements.end() ; ++it)
0059         {
0060             m_box = it->first;
0061
0062             rtree::apply_visitor(*this, *it->second);
0063
0064             if ( result == false )
0065                 return;
0066         }
0067
0068         m_box = box_bckup;
0069         m_is_root = is_root_bckup;
0070
0071         box_type box_exp = rtree::elements_box<box_type>(elements.begin(), elements.end(), m_tr,
0072                                                          index::detail::get_strategy(m_parameters));
0073
0074         if ( m_exact_match )
0075             result = m_is_root || geometry::equals(box_exp, m_box);
0076         else
0077             result = m_is_root || geometry::covered_by(box_exp, m_box);
0078     }
0079
0080     void operator()(leaf const& n)
0081     {
0082         typedef typename rtree::elements_type<leaf>::type elements_type;
0083         elements_type const& elements = rtree::elements(n);
0084
0085         // non-root node
0086         if (!m_is_root)
0087         {
0088             if ( elements.empty() )
0089             {
0090                 result = false;
0091                 return;
0092             }
0093
0094             box_type box_exp = rtree::values_box<box_type>(elements.begin(), elements.end(), m_tr,
0095                                                            index::detail::get_strategy(m_parameters));
0096
0097             if ( m_exact_match )
0098                 result = geometry::equals(box_exp, m_box);
0099             else
0100                 result = geometry::covered_by(box_exp, m_box);
0101         }
0102         else
0103             result = true;
0104     }
0105
0106     bool result;
0107
0108 private:
0109     parameters_type const& m_parameters;
0110     translator_type const& m_tr;
0111     box_type m_box;
0112     bool m_is_root;
0113     bool m_exact_match;
0114 };
0115
0116 } // namespace visitors
0117
0118 template <typename Rtree> inline
0119 bool are_boxes_ok(Rtree const& tree, bool exact_match = true)
0120 {
0121     typedef utilities::view<Rtree> RTV;
0122     RTV rtv(tree);
0123
0124     visitors::are_boxes_ok<
0125         typename RTV::members_holder
0126     > v(tree.parameters(), rtv.translator(), exact_match);
0127
0128     rtv.apply_visitor(v);
0129
0130     return v.result;
0131 }
0132
0133 }}}}}} // namespace boost::geometry::index::detail::rtree::utilities
0134
0135 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_BOXES_OK_HPP