1 // Boost.Geometry Index 2 // 3 // R-tree levels validating visitor implementation 4 // 5 // Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland. 6 // 7 // This file was modified by Oracle on 2019. 8 // Modifications copyright (c) 2019 Oracle and/or its affiliates. 9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 10 // 11 // Use, modification and distribution is subject to the Boost Software License, 12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 13 // http://www.boost.org/LICENSE_1_0.txt) 14 15 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_OK_HPP 16 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_OK_HPP 17 18 #include <boost/geometry/index/detail/rtree/node/node.hpp> 19 20 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities { 21 22 namespace visitors { 23 24 template <typename MembersHolder> 25 class are_levels_ok 26 : public MembersHolder::visitor_const 27 { 28 typedef typename MembersHolder::internal_node internal_node; 29 typedef typename MembersHolder::leaf leaf; 30 31 public: are_levels_ok()32 inline are_levels_ok() 33 : result(true), m_leafs_level((std::numeric_limits<size_t>::max)()), m_current_level(0) 34 {} 35 operator ()(internal_node const & n)36 inline void operator()(internal_node const& n) 37 { 38 typedef typename rtree::elements_type<internal_node>::type elements_type; 39 elements_type const& elements = rtree::elements(n); 40 41 if (elements.empty()) 42 { 43 result = false; 44 return; 45 } 46 47 size_t current_level_backup = m_current_level; 48 ++m_current_level; 49 50 for ( typename elements_type::const_iterator it = elements.begin(); 51 it != elements.end() ; ++it) 52 { 53 rtree::apply_visitor(*this, *it->second); 54 55 if ( result == false ) 56 return; 57 } 58 59 m_current_level = current_level_backup; 60 } 61 operator ()(leaf const & n)62 inline void operator()(leaf const& n) 63 { 64 typedef typename rtree::elements_type<leaf>::type elements_type; 65 elements_type const& elements = rtree::elements(n); 66 67 // empty leaf in non-root node 68 if (0 < m_current_level && elements.empty()) 69 { 70 result = false; 71 return; 72 } 73 74 if ( m_leafs_level == (std::numeric_limits<size_t>::max)() ) 75 { 76 m_leafs_level = m_current_level; 77 } 78 else if ( m_leafs_level != m_current_level ) 79 { 80 result = false; 81 } 82 } 83 84 bool result; 85 86 private: 87 size_t m_leafs_level; 88 size_t m_current_level; 89 }; 90 91 } // namespace visitors 92 93 template <typename Rtree> inline are_levels_ok(Rtree const & tree)94bool are_levels_ok(Rtree const& tree) 95 { 96 typedef utilities::view<Rtree> RTV; 97 RTV rtv(tree); 98 99 visitors::are_levels_ok< 100 typename RTV::members_holder 101 > v; 102 103 rtv.apply_visitor(v); 104 105 return v.result; 106 } 107 108 }}}}}} // namespace boost::geometry::index::detail::rtree::utilities 109 110 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_OK_HPP 111