projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | // Boost.Geometry Index |
| 2 | // | |
| 3 | // R-tree levels validating visitor implementation | |
| 4 | // | |
| 5 | // Copyright (c) 2011-2013 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_LEVELS_OK_HPP | |
| 12 | #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_OK_HPP | |
| 13 | ||
| 14 | #include <boost/geometry/index/detail/rtree/node/node.hpp> | |
| 15 | ||
| 16 | namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities { | |
| 17 | ||
| 18 | namespace visitors { | |
| 19 | ||
| 20 | template <typename Value, typename Options, typename Box, typename Allocators> | |
| 21 | class are_levels_ok | |
| 22 | : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type | |
| 23 | { | |
| 24 | typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; | |
| 25 | typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; | |
| 26 | ||
| 27 | public: | |
| 28 | inline are_levels_ok() | |
| 29 | : result(true), m_leafs_level((std::numeric_limits<size_t>::max)()), m_current_level(0) | |
| 30 | {} | |
| 31 | ||
| 32 | inline void operator()(internal_node const& n) | |
| 33 | { | |
| 34 | typedef typename rtree::elements_type<internal_node>::type elements_type; | |
| 35 | elements_type const& elements = rtree::elements(n); | |
| 36 | ||
| 37 | if (elements.empty()) | |
| 38 | { | |
| 39 | result = false; | |
| 40 | return; | |
| 41 | } | |
| 42 | ||
| 43 | size_t current_level_backup = m_current_level; | |
| 44 | ++m_current_level; | |
| 45 | ||
| 46 | for ( typename elements_type::const_iterator it = elements.begin(); | |
| 47 | it != elements.end() ; ++it) | |
| 48 | { | |
| 49 | rtree::apply_visitor(*this, *it->second); | |
| 50 | ||
| 51 | if ( result == false ) | |
| 52 | return; | |
| 53 | } | |
| 54 | ||
| 55 | m_current_level = current_level_backup; | |
| 56 | } | |
| 57 | ||
| 58 | inline void operator()(leaf const& n) | |
| 59 | { | |
| 60 | typedef typename rtree::elements_type<leaf>::type elements_type; | |
| 61 | elements_type const& elements = rtree::elements(n); | |
| 62 | ||
| 63 | // empty leaf in non-root node | |
| 64 | if (0 < m_current_level && elements.empty()) | |
| 65 | { | |
| 66 | result = false; | |
| 67 | return; | |
| 68 | } | |
| 69 | ||
| 70 | if ( m_leafs_level == (std::numeric_limits<size_t>::max)() ) | |
| 71 | { | |
| 72 | m_leafs_level = m_current_level; | |
| 73 | } | |
| 74 | else if ( m_leafs_level != m_current_level ) | |
| 75 | { | |
| 76 | result = false; | |
| 77 | } | |
| 78 | } | |
| 79 | ||
| 80 | bool result; | |
| 81 | ||
| 82 | private: | |
| 83 | size_t m_leafs_level; | |
| 84 | size_t m_current_level; | |
| 85 | }; | |
| 86 | ||
| 87 | } // namespace visitors | |
| 88 | ||
| 89 | template <typename Rtree> inline | |
| 90 | bool are_levels_ok(Rtree const& tree) | |
| 91 | { | |
| 92 | typedef utilities::view<Rtree> RTV; | |
| 93 | RTV rtv(tree); | |
| 94 | ||
| 95 | visitors::are_levels_ok< | |
| 96 | typename RTV::value_type, | |
| 97 | typename RTV::options_type, | |
| 98 | typename RTV::box_type, | |
| 99 | typename RTV::allocators_type | |
| 100 | > v; | |
| 101 | ||
| 102 | rtv.apply_visitor(v); | |
| 103 | ||
| 104 | return v.result; | |
| 105 | } | |
| 106 | ||
| 107 | }}}}}} // namespace boost::geometry::index::detail::rtree::utilities | |
| 108 | ||
| 109 | #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_OK_HPP |