1 // Boost.Geometry Index
2 //
3 // R-tree boxes validating visitor implementation
4 //
5 // Copyright (c) 2011-2014 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:
are_boxes_ok(Translator const & tr,bool exact_match)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
operator ()(internal_node const & n)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;
64 geometry::convert(elements.front().first, box_exp);
65 for( typename elements_type::const_iterator it = elements.begin() + 1;
66 it != elements.end() ; ++it)
67 {
68 geometry::expand(box_exp, it->first);
69 }
70
71 if ( m_exact_match )
72 result = m_is_root || geometry::equals(box_exp, m_box);
73 else
74 result = m_is_root || geometry::covered_by(box_exp, m_box);
75 }
76
operator ()(leaf const & n)77 void operator()(leaf const& n)
78 {
79 typedef typename rtree::elements_type<leaf>::type elements_type;
80 elements_type const& elements = rtree::elements(n);
81
82 // non-root node
83 if (!m_is_root)
84 {
85 if ( elements.empty() )
86 {
87 result = false;
88 return;
89 }
90
91 Box box_exp;
92 geometry::convert(
93 index::detail::return_ref_or_bounds(m_tr(elements.front())),
94 box_exp);
95 for(typename elements_type::const_iterator it = elements.begin() + 1;
96 it != elements.end() ; ++it)
97 {
98 geometry::expand(box_exp, m_tr(*it));
99 }
100
101 if ( m_exact_match )
102 result = geometry::equals(box_exp, m_box);
103 else
104 result = geometry::covered_by(box_exp, m_box);
105 }
106 else
107 result = true;
108 }
109
110 bool result;
111
112 private:
113 Translator const& m_tr;
114 Box m_box;
115 bool m_is_root;
116 bool m_exact_match;
117 };
118
119 } // namespace visitors
120
121 template <typename Rtree> inline
are_boxes_ok(Rtree const & tree,bool exact_match=true)122 bool are_boxes_ok(Rtree const& tree, bool exact_match = true)
123 {
124 typedef utilities::view<Rtree> RTV;
125 RTV rtv(tree);
126
127 visitors::are_boxes_ok<
128 typename RTV::value_type,
129 typename RTV::options_type,
130 typename RTV::translator_type,
131 typename RTV::box_type,
132 typename RTV::allocators_type
133 > v(rtv.translator(), exact_match);
134
135 rtv.apply_visitor(v);
136
137 return v.result;
138 }
139
140 }}}}}} // namespace boost::geometry::index::detail::rtree::utilities
141
142 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_BOXES_OK_HPP
143