ceph/src/boost/boost/geometry/algorithms/detail/max_interval_gap.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2015, 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_MAX_INTERVAL_GAP_HPP
  11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_MAX_INTERVAL_GAP_HPP
  12
  13 #include <cstddef>
  14 #include <queue>
  15 #include <utility>
  16 #include <vector>
  17
  18 #include <boost/core/ref.hpp>
  19 #include <boost/range.hpp>
  20 #include <boost/type_traits/remove_const.hpp>
  21 #include <boost/type_traits/remove_reference.hpp>
  22
  23 #include <boost/geometry/core/assert.hpp>
  24 #include <boost/geometry/util/math.hpp>
  25 #include <boost/geometry/algorithms/detail/sweep.hpp>
  26
  27
  28 namespace boost { namespace geometry
  29 {
  30
  31 #ifndef DOXYGEN_NO_DETAIL
  32 namespace detail { namespace max_interval_gap
  33 {
  34
  35 // the class Interval must provide the following:
  36 // * must define the type value_type
  37 // * must define the type difference_type
  38 // * must have the methods:
  39 //   value_type get<Index>() const
  40 //   difference_type length() const
  41 // where an Index value of 0 (resp., 1) refers to the left (resp.,
  42 // right) endpoint of the interval
  43
  44 template <typename Interval>
  45 class sweep_event
  46 {
  47 public:
  48     typedef Interval interval_type;
  49     typedef typename Interval::value_type time_type;
  50
  51     sweep_event(Interval const& interval, bool start_event = true)
  52         : m_interval(boost::cref(interval))
  53         , m_start_event(start_event)
  54     {}
  55
  56     inline bool is_start_event() const
  57     {
  58         return m_start_event;
  59     }
  60
  61     inline interval_type const& interval() const
  62     {
  63         return m_interval;
  64     }
  65
  66     inline time_type time() const
  67     {
  68         return (m_start_event)
  69             ? interval().template get<0>()
  70             : interval().template get<1>();
  71     }
  72
  73     inline bool operator<(sweep_event const& other) const
  74     {
  75         if (! math::equals(time(), other.time()))
  76         {
  77             return time() < other.time();
  78         }
  79         // a start-event is before an end-event with the same event time
  80         return is_start_event() && ! other.is_start_event();
  81     }
  82
  83 private:
  84     boost::reference_wrapper<Interval const> m_interval;
  85     bool m_start_event;
  86 };
  87
  88 template <typename Event>
  89 struct event_greater
  90 {
  91     inline bool operator()(Event const& event1, Event const& event2) const
  92     {
  93         return event2 < event1;
  94     }
  95 };
  96
  97
  98 struct initialization_visitor
  99 {
 100     template <typename Range, typename PriorityQueue, typename EventVisitor>
 101     static inline void apply(Range const& range,
 102                              PriorityQueue& queue,
 103                              EventVisitor&)
 104     {
 105         BOOST_GEOMETRY_ASSERT(queue.empty());
 106
 107         // it is faster to build the queue directly from the entire
 108         // range, rather than insert elements one after the other
 109         PriorityQueue pq(boost::begin(range), boost::end(range));
 110         std::swap(pq, queue);
 111     }
 112 };
 113
 114
 115 template <typename Event>
 116 class event_visitor
 117 {
 118     typedef typename Event::time_type event_time_type;
 119     typedef typename Event::interval_type::difference_type difference_type;
 120
 121     typedef typename boost::remove_const
 122         <
 123             typename boost::remove_reference
 124                 <
 125                     event_time_type
 126                 >::type
 127         >::type bare_time_type;
 128
 129
 130 public:
 131     event_visitor()
 132         : m_overlap_count(0)
 133         , m_max_gap_left(0)
 134         , m_max_gap_right(0)
 135     {}
 136
 137     template <typename PriorityQueue>
 138     inline void apply(Event const& event, PriorityQueue& queue)
 139     {
 140         if (event.is_start_event())
 141         {
 142             ++m_overlap_count;
 143             queue.push(Event(event.interval(), false));
 144         }
 145         else
 146         {
 147             --m_overlap_count;
 148             if (m_overlap_count == 0 && ! queue.empty())
 149             {
 150                 // we may have a gap
 151                 BOOST_GEOMETRY_ASSERT(queue.top().is_start_event());
 152
 153                 event_time_type next_event_time
 154                     = queue.top().interval().template get<0>();
 155                 difference_type gap = next_event_time - event.time();
 156                 if (gap > max_gap())
 157                 {
 158                     m_max_gap_left = event.time();
 159                     m_max_gap_right = next_event_time;
 160                 }
 161             }
 162         }
 163     }
 164
 165     bare_time_type const& max_gap_left() const
 166     {
 167         return m_max_gap_left;
 168     }
 169
 170     bare_time_type const& max_gap_right() const
 171     {
 172         return m_max_gap_right;
 173     }
 174
 175     difference_type max_gap() const
 176     {
 177         return m_max_gap_right - m_max_gap_left;
 178     }
 179
 180 private:
 181     std::size_t m_overlap_count;
 182     bare_time_type m_max_gap_left, m_max_gap_right;
 183 };
 184
 185 }} // namespace detail::max_interval_gap
 186 #endif // DOXYGEN_NO_DETAIL
 187
 188
 189 // Given a range of intervals I1, I2, ..., In, maximum_gap() returns
 190 // the maximum length of an interval M that satisfies the following
 191 // properties:
 192 //
 193 // 1. M.left >= min(I1, I2, ..., In)
 194 // 2. M.right <= max(I1, I2, ..., In)
 195 // 3. intersection(interior(M), Ik) is the empty set for all k=1, ..., n
 196 // 4. length(M) is maximal
 197 //
 198 // where M.left and M.right denote the left and right extreme values
 199 // for the interval M, and length(M) is equal to M.right - M.left.
 200 //
 201 // If M does not exist (or, alternatively, M is identified as the
 202 // empty set), 0 is returned.
 203 //
 204 // The algorithm proceeds for performing a sweep: the left endpoints
 205 // are inserted into a min-priority queue with the priority being the
 206 // value of the endpoint. The sweep algorithm maintains an "overlap
 207 // counter" that counts the number of overlaping intervals at any
 208 // specific sweep-time value.
 209 // There are two types of events encountered during the sweep:
 210 // (a) a start event: the left endpoint of an interval is found.
 211 //     In this case the overlap count is increased by one and the
 212 //     right endpoint of the interval in inserted into the event queue
 213 // (b) an end event: the right endpoint of an interval is found.
 214 //     In this case the overlap count is decreased by one. If the
 215 //     updated overlap count is 0, then we could expect to have a gap
 216 //     in-between intervals. This gap is measured as the (absolute)
 217 //     distance of the current interval right endpoint (being
 218 //     processed) to the upcoming left endpoint of the next interval
 219 //     to be processed (if such an interval exists). If the measured
 220 //     gap is greater than the current maximum gap, it is recorded.
 221 // The initial maximum gap is initialized to 0. This value is returned
 222 // if no gap is found during the sweeping procedure.
 223
 224 template <typename RangeOfIntervals, typename T>
 225 inline typename boost::range_value<RangeOfIntervals>::type::difference_type
 226 maximum_gap(RangeOfIntervals const& range_of_intervals,
 227             T& max_gap_left, T& max_gap_right)
 228 {
 229     typedef typename boost::range_value<RangeOfIntervals>::type interval_type;
 230     typedef detail::max_interval_gap::sweep_event<interval_type> event_type;
 231
 232     // create a min-priority queue for the events
 233     std::priority_queue
 234         <
 235             event_type,
 236             std::vector<event_type>,
 237             detail::max_interval_gap::event_greater<event_type>
 238         > queue;
 239
 240     // define initialization and event-process visitors
 241     detail::max_interval_gap::initialization_visitor init_visitor;
 242     detail::max_interval_gap::event_visitor<event_type> sweep_visitor;
 243
 244     // perform the sweep
 245     geometry::sweep(range_of_intervals,
 246                     queue,
 247                     init_visitor,
 248                     sweep_visitor);
 249
 250     max_gap_left = sweep_visitor.max_gap_left();
 251     max_gap_right = sweep_visitor.max_gap_right();
 252     return sweep_visitor.max_gap();
 253 }
 254
 255 template <typename RangeOfIntervals>
 256 inline typename boost::range_value<RangeOfIntervals>::type::difference_type
 257 maximum_gap(RangeOfIntervals const& range_of_intervals)
 258 {
 259     typedef typename boost::remove_const
 260         <
 261             typename boost::remove_reference
 262                 <
 263                     typename boost::range_value
 264                         <
 265                             RangeOfIntervals
 266                         >::type::value_type
 267                 >::type
 268         >::type value_type;
 269
 270     value_type left, right;
 271
 272     return maximum_gap(range_of_intervals, left, right);
 273 }
 274
 275
 276 }} // namespace boost::geometry
 277
 278 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_MAX_INTERVAL_GAP_HPP