rtree/utilities/are_levels_ok.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree levels validating visitor implementation
0004 //
0005 // Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2019-2023.
0008 // Modifications copyright (c) 2019-2023 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011 //
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_OK_HPP
0017 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_OK_HPP
0018
0019 #include <boost/geometry/index/detail/rtree/node/node.hpp>
0020 #include <boost/geometry/index/detail/rtree/utilities/view.hpp>
0021
0022 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities {
0023
0024 namespace visitors {
0025
0026 template <typename MembersHolder>
0027 class are_levels_ok
0028     : public MembersHolder::visitor_const
0029 {
0030     typedef typename MembersHolder::internal_node internal_node;
0031     typedef typename MembersHolder::leaf leaf;
0032
0033 public:
0034     inline are_levels_ok()
0035         : result(true), m_leafs_level((std::numeric_limits<size_t>::max)()), m_current_level(0)
0036     {}
0037
0038     inline void operator()(internal_node const& n)
0039     {
0040         typedef typename rtree::elements_type<internal_node>::type elements_type;
0041         elements_type const& elements = rtree::elements(n);
0042
0043         if (elements.empty())
0044         {
0045             result = false;
0046             return;
0047         }
0048
0049         size_t current_level_backup = m_current_level;
0050         ++m_current_level;
0051
0052         for ( typename elements_type::const_iterator it = elements.begin();
0053               it != elements.end() ; ++it)
0054         {
0055             rtree::apply_visitor(*this, *it->second);
0056
0057             if ( result == false )
0058                 return;
0059         }
0060
0061         m_current_level = current_level_backup;
0062     }
0063
0064     inline void operator()(leaf const& n)
0065     {
0066         typedef typename rtree::elements_type<leaf>::type elements_type;
0067         elements_type const& elements = rtree::elements(n);
0068
0069         // empty leaf in non-root node
0070         if (0 < m_current_level && elements.empty())
0071         {
0072             result = false;
0073             return;
0074         }
0075
0076         if ( m_leafs_level == (std::numeric_limits<size_t>::max)() )
0077         {
0078             m_leafs_level = m_current_level;
0079         }
0080         else if ( m_leafs_level != m_current_level )
0081         {
0082             result = false;
0083         }
0084     }
0085
0086     bool result;
0087
0088 private:
0089     size_t m_leafs_level;
0090     size_t m_current_level;
0091 };
0092
0093 } // namespace visitors
0094
0095 template <typename Rtree> inline
0096 bool are_levels_ok(Rtree const& tree)
0097 {
0098     typedef utilities::view<Rtree> RTV;
0099     RTV rtv(tree);
0100
0101     visitors::are_levels_ok<
0102         typename RTV::members_holder
0103     > v;
0104
0105     rtv.apply_visitor(v);
0106
0107     return v.result;
0108 }
0109
0110 }}}}}} // namespace boost::geometry::index::detail::rtree::utilities
0111
0112 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_OK_HPP