algorithms/detail/max_interval_gap.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2015-2020, Oracle and/or its affiliates.
0004
0005 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0006 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0007
0008 // Licensed under the Boost Software License version 1.0.
0009 // http://www.boost.org/users/license.html
0010
0011 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_MAX_INTERVAL_GAP_HPP
0012 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_MAX_INTERVAL_GAP_HPP
0013
0014 #include <cstddef>
0015 #include <functional>
0016 #include <queue>
0017 #include <utility>
0018 #include <vector>
0019
0020 #include <boost/range/begin.hpp>
0021 #include <boost/range/end.hpp>
0022 #include <boost/range/value_type.hpp>
0023
0024 #include <boost/geometry/core/assert.hpp>
0025 #include <boost/geometry/util/math.hpp>
0026 #include <boost/geometry/algorithms/detail/sweep.hpp>
0027
0028
0029 namespace boost { namespace geometry
0030 {
0031
0032 #ifndef DOXYGEN_NO_DETAIL
0033 namespace detail { namespace max_interval_gap
0034 {
0035
0036 // the class Interval must provide the following:
0037 // * must define the type value_type
0038 // * must define the type difference_type
0039 // * must have the methods:
0040 //   value_type get<Index>() const
0041 //   difference_type length() const
0042 // where an Index value of 0 (resp., 1) refers to the left (resp.,
0043 // right) endpoint of the interval
0044
0045 template <typename Interval>
0046 class sweep_event
0047 {
0048 public:
0049     typedef Interval interval_type;
0050     typedef typename Interval::value_type time_type;
0051
0052     sweep_event(Interval const& interval, bool start_event = true)
0053         : m_interval(std::cref(interval))
0054         , m_start_event(start_event)
0055     {}
0056
0057     inline bool is_start_event() const
0058     {
0059         return m_start_event;
0060     }
0061
0062     inline interval_type const& interval() const
0063     {
0064         return m_interval;
0065     }
0066
0067     inline time_type time() const
0068     {
0069         return (m_start_event)
0070             ? interval().template get<0>()
0071             : interval().template get<1>();
0072     }
0073
0074     inline bool operator<(sweep_event const& other) const
0075     {
0076         if (! math::equals(time(), other.time()))
0077         {
0078             return time() < other.time();
0079         }
0080         // a start-event is before an end-event with the same event time
0081         return is_start_event() && ! other.is_start_event();
0082     }
0083
0084 private:
0085     std::reference_wrapper<Interval const> m_interval;
0086     bool m_start_event;
0087 };
0088
0089 template <typename Event>
0090 struct event_greater
0091 {
0092     inline bool operator()(Event const& event1, Event const& event2) const
0093     {
0094         return event2 < event1;
0095     }
0096 };
0097
0098
0099 struct initialization_visitor
0100 {
0101     template <typename Range, typename PriorityQueue, typename EventVisitor>
0102     static inline void apply(Range const& range,
0103                              PriorityQueue& queue,
0104                              EventVisitor&)
0105     {
0106         BOOST_GEOMETRY_ASSERT(queue.empty());
0107
0108         // it is faster to build the queue directly from the entire
0109         // range, rather than insert elements one after the other
0110         PriorityQueue pq(boost::begin(range), boost::end(range));
0111         std::swap(pq, queue);
0112     }
0113 };
0114
0115
0116 template <typename Event>
0117 class event_visitor
0118 {
0119     typedef typename Event::time_type event_time_type;
0120     typedef typename Event::interval_type::difference_type difference_type;
0121
0122 public:
0123     event_visitor()
0124         : m_overlap_count(0)
0125         , m_max_gap_left(0)
0126         , m_max_gap_right(0)
0127     {}
0128
0129     template <typename PriorityQueue>
0130     inline void apply(Event const& event, PriorityQueue& queue)
0131     {
0132         if (event.is_start_event())
0133         {
0134             ++m_overlap_count;
0135             queue.push(Event(event.interval(), false));
0136         }
0137         else
0138         {
0139             --m_overlap_count;
0140             if (m_overlap_count == 0 && ! queue.empty())
0141             {
0142                 // we may have a gap
0143                 BOOST_GEOMETRY_ASSERT(queue.top().is_start_event());
0144
0145                 event_time_type next_event_time
0146                     = queue.top().interval().template get<0>();
0147                 difference_type gap = next_event_time - event.time();
0148                 if (gap > max_gap())
0149                 {
0150                     m_max_gap_left = event.time();
0151                     m_max_gap_right = next_event_time;
0152                 }
0153             }
0154         }
0155     }
0156
0157     event_time_type const& max_gap_left() const
0158     {
0159         return m_max_gap_left;
0160     }
0161
0162     event_time_type const& max_gap_right() const
0163     {
0164         return m_max_gap_right;
0165     }
0166
0167     difference_type max_gap() const
0168     {
0169         return m_max_gap_right - m_max_gap_left;
0170     }
0171
0172 private:
0173     std::size_t m_overlap_count;
0174     event_time_type m_max_gap_left, m_max_gap_right;
0175 };
0176
0177 }} // namespace detail::max_interval_gap
0178 #endif // DOXYGEN_NO_DETAIL
0179
0180
0181 // Given a range of intervals I1, I2, ..., In, maximum_gap() returns
0182 // the maximum length of an interval M that satisfies the following
0183 // properties:
0184 //
0185 // 1. M.left >= min(I1, I2, ..., In)
0186 // 2. M.right <= max(I1, I2, ..., In)
0187 // 3. intersection(interior(M), Ik) is the empty set for all k=1, ..., n
0188 // 4. length(M) is maximal
0189 //
0190 // where M.left and M.right denote the left and right extreme values
0191 // for the interval M, and length(M) is equal to M.right - M.left.
0192 //
0193 // If M does not exist (or, alternatively, M is identified as the
0194 // empty set), 0 is returned.
0195 //
0196 // The algorithm proceeds for performing a sweep: the left endpoints
0197 // are inserted into a min-priority queue with the priority being the
0198 // value of the endpoint. The sweep algorithm maintains an "overlap
0199 // counter" that counts the number of overlaping intervals at any
0200 // specific sweep-time value.
0201 // There are two types of events encountered during the sweep:
0202 // (a) a start event: the left endpoint of an interval is found.
0203 //     In this case the overlap count is increased by one and the
0204 //     right endpoint of the interval in inserted into the event queue
0205 // (b) an end event: the right endpoint of an interval is found.
0206 //     In this case the overlap count is decreased by one. If the
0207 //     updated overlap count is 0, then we could expect to have a gap
0208 //     in-between intervals. This gap is measured as the (absolute)
0209 //     distance of the current interval right endpoint (being
0210 //     processed) to the upcoming left endpoint of the next interval
0211 //     to be processed (if such an interval exists). If the measured
0212 //     gap is greater than the current maximum gap, it is recorded.
0213 // The initial maximum gap is initialized to 0. This value is returned
0214 // if no gap is found during the sweeping procedure.
0215
0216 template <typename RangeOfIntervals, typename T>
0217 inline typename boost::range_value<RangeOfIntervals>::type::difference_type
0218 maximum_gap(RangeOfIntervals const& range_of_intervals,
0219             T& max_gap_left, T& max_gap_right)
0220 {
0221     typedef typename boost::range_value<RangeOfIntervals>::type interval_type;
0222     typedef detail::max_interval_gap::sweep_event<interval_type> event_type;
0223
0224     // create a min-priority queue for the events
0225     std::priority_queue
0226         <
0227             event_type,
0228             std::vector<event_type>,
0229             detail::max_interval_gap::event_greater<event_type>
0230         > queue;
0231
0232     // define initialization and event-process visitors
0233     detail::max_interval_gap::initialization_visitor init_visitor;
0234     detail::max_interval_gap::event_visitor<event_type> sweep_visitor;
0235
0236     // perform the sweep
0237     geometry::sweep(range_of_intervals,
0238                     queue,
0239                     init_visitor,
0240                     sweep_visitor);
0241
0242     max_gap_left = sweep_visitor.max_gap_left();
0243     max_gap_right = sweep_visitor.max_gap_right();
0244     return sweep_visitor.max_gap();
0245 }
0246
0247 template <typename RangeOfIntervals>
0248 inline typename boost::range_value<RangeOfIntervals>::type::difference_type
0249 maximum_gap(RangeOfIntervals const& range_of_intervals)
0250 {
0251     typedef typename boost::range_value<RangeOfIntervals>::type interval_type;
0252
0253     typename interval_type::value_type left, right;
0254
0255     return maximum_gap(range_of_intervals, left, right);
0256 }
0257
0258
0259 }} // namespace boost::geometry
0260
0261 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_MAX_INTERVAL_GAP_HPP