ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/closest_feature/range_to_range.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014, Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   6
   7 // Licensed under the Boost Software License version 1.0.
   8 // http://www.boost.org/users/license.html
   9
  10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_RANGE_TO_RANGE_HPP
  11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_RANGE_TO_RANGE_HPP
  12
  13 #include <cstddef>
  14
  15 #include <iterator>
  16 #include <utility>
  17
  18 #include <boost/geometry/core/assert.hpp>
  19 #include <boost/geometry/core/point_type.hpp>
  20 #include <boost/geometry/strategies/distance.hpp>
  21 #include <boost/geometry/algorithms/dispatch/distance.hpp>
  22 #include <boost/geometry/index/rtree.hpp>
  23
  24
  25 namespace boost { namespace geometry
  26 {
  27
  28 #ifndef DOXYGEN_NO_DETAIL
  29 namespace detail { namespace closest_feature
  30 {
  31
  32
  33 // returns a pair of a objects where the first is an object of the
  34 // r-tree range and the second an object of the query range that
  35 // realizes the closest feature of the two ranges
  36 class range_to_range_rtree
  37 {
  38 private:
  39     template
  40     <
  41         typename RTreeRangeIterator,
  42         typename QueryRangeIterator,
  43         typename Strategy,
  44         typename RTreeValueType,
  45         typename Distance
  46     >
  47     static inline void apply(RTreeRangeIterator rtree_first,
  48                              RTreeRangeIterator rtree_last,
  49                              QueryRangeIterator queries_first,
  50                              QueryRangeIterator queries_last,
  51                              Strategy const& strategy,
  52                              RTreeValueType& rtree_min,
  53                              QueryRangeIterator& qit_min,
  54                              Distance& dist_min)
  55     {
  56         typedef index::rtree<RTreeValueType, index::linear<8> > rtree_type;
  57
  58         BOOST_GEOMETRY_ASSERT( rtree_first != rtree_last );
  59         BOOST_GEOMETRY_ASSERT( queries_first != queries_last );
  60
  61         Distance const zero = Distance(0);
  62         dist_min = zero;
  63
  64         // create -- packing algorithm
  65         rtree_type rt(rtree_first, rtree_last);
  66
  67         RTreeValueType t_v;
  68         bool first = true;
  69
  70         for (QueryRangeIterator qit = queries_first;
  71              qit != queries_last; ++qit, first = false)
  72         {
  73             std::size_t n = rt.query(index::nearest(*qit, 1), &t_v);
  74
  75             BOOST_GEOMETRY_ASSERT( n > 0 );
  76             // n above is unused outside BOOST_GEOMETRY_ASSERT,
  77             // hence the call to boost::ignore_unused below
  78             //
  79             // however, t_v (initialized by the call to rt.query(...))
  80             // is used below, which is why we cannot put the call to
  81             // rt.query(...) inside BOOST_GEOMETRY_ASSERT
  82             boost::ignore_unused(n);
  83
  84             Distance dist = dispatch::distance
  85                 <
  86                     RTreeValueType,
  87                     typename std::iterator_traits
  88                         <
  89                             QueryRangeIterator
  90                         >::value_type,
  91                     Strategy
  92                 >::apply(t_v, *qit, strategy);
  93
  94             if (first || dist < dist_min)
  95             {
  96                 dist_min = dist;
  97                 rtree_min = t_v;
  98                 qit_min = qit;
  99                 if ( math::equals(dist_min, zero) )
 100                 {
 101                     return;
 102                 }
 103             }
 104         }
 105     }
 106
 107 public:
 108     template <typename RTreeRangeIterator, typename QueryRangeIterator>
 109     struct return_type
 110     {
 111         typedef std::pair
 112             <
 113                 typename std::iterator_traits<RTreeRangeIterator>::value_type,
 114                 QueryRangeIterator
 115             > type;
 116     };
 117
 118
 119     template
 120     <
 121         typename RTreeRangeIterator,
 122         typename QueryRangeIterator,
 123         typename Strategy,
 124         typename Distance
 125     >
 126     static inline typename return_type
 127         <
 128             RTreeRangeIterator, QueryRangeIterator
 129         >::type apply(RTreeRangeIterator rtree_first,
 130                       RTreeRangeIterator rtree_last,
 131                       QueryRangeIterator queries_first,
 132                       QueryRangeIterator queries_last,
 133                       Strategy const& strategy,
 134                       Distance& dist_min)
 135     {
 136         typedef typename std::iterator_traits
 137             <
 138                 RTreeRangeIterator
 139             >::value_type rtree_value_type;
 140
 141         rtree_value_type rtree_min;
 142         QueryRangeIterator qit_min;
 143
 144         apply(rtree_first, rtree_last, queries_first, queries_last,
 145               strategy, rtree_min, qit_min, dist_min);
 146
 147         return std::make_pair(rtree_min, qit_min);
 148     }
 149
 150
 151     template
 152     <
 153         typename RTreeRangeIterator,
 154         typename QueryRangeIterator,
 155         typename Strategy
 156     >
 157     static inline typename return_type
 158         <
 159             RTreeRangeIterator, QueryRangeIterator
 160         >::type apply(RTreeRangeIterator rtree_first,
 161                       RTreeRangeIterator rtree_last,
 162                       QueryRangeIterator queries_first,
 163                       QueryRangeIterator queries_last,
 164                       Strategy const& strategy)
 165     {
 166         typedef typename std::iterator_traits
 167             <
 168                 RTreeRangeIterator
 169             >::value_type rtree_value_type;
 170
 171         typename strategy::distance::services::return_type
 172             <
 173                 Strategy,
 174                 typename point_type<rtree_value_type>::type,
 175                 typename point_type
 176                     <
 177                         typename std::iterator_traits
 178                             <
 179                                 QueryRangeIterator
 180                             >::value_type
 181                     >::type
 182             >::type dist_min;
 183
 184         return apply(rtree_first, rtree_last, queries_first, queries_last,
 185                      strategy, dist_min);
 186     }
 187 };
 188
 189
 190 }} // namespace detail::closest_feature
 191 #endif // DOXYGEN_NO_DETAIL
 192
 193 }} // namespace boost::geometry
 194
 195
 196 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_FEATURE_RANGE_TO_RANGE_HPP