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
sweep_event(Interval const & interval,bool start_event=true)51 sweep_event(Interval const& interval, bool start_event = true)
52 : m_interval(boost::cref(interval))
53 , m_start_event(start_event)
54 {}
55
is_start_event() const56 inline bool is_start_event() const
57 {
58 return m_start_event;
59 }
60
interval() const61 inline interval_type const& interval() const
62 {
63 return m_interval;
64 }
65
time() const66 inline time_type time() const
67 {
68 return (m_start_event)
69 ? interval().template get<0>()
70 : interval().template get<1>();
71 }
72
operator <(sweep_event const & other) const73 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 {
operator ()boost::geometry::detail::max_interval_gap::event_greater91 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>
applyboost::geometry::detail::max_interval_gap::initialization_visitor101 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:
event_visitor()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>
apply(Event const & event,PriorityQueue & queue)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
max_gap_left() const165 bare_time_type const& max_gap_left() const
166 {
167 return m_max_gap_left;
168 }
169
max_gap_right() const170 bare_time_type const& max_gap_right() const
171 {
172 return m_max_gap_right;
173 }
174
max_gap() const175 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
maximum_gap(RangeOfIntervals const & range_of_intervals,T & max_gap_left,T & max_gap_right)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
maximum_gap(RangeOfIntervals const & range_of_intervals)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
279