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

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