1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 // Unit Test
3
4 // Copyright (c) 2015, Oracle and/or its affiliates.
5
6 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
8
9 // Licensed under the Boost Software License version 1.0.
10 // http://www.boost.org/users/license.html
11
12 #ifndef BOOST_TEST_MODULE
13 #define BOOST_TEST_MODULE test_maximum_gap
14 #endif
15
16 #include <boost/test/included/unit_test.hpp>
17
18 #include <cstddef>
19
20 #include <iostream>
21 #include <sstream>
22 #include <vector>
23
24 #include <boost/geometry/algorithms/detail/max_interval_gap.hpp>
25
26 namespace bg = boost::geometry;
27
28 class uint_interval
29 {
30 public:
31 typedef unsigned value_type;
32 typedef int difference_type;
33
uint_interval(unsigned left,unsigned right)34 uint_interval(unsigned left, unsigned right)
35 : m_left(left)
36 , m_right(right)
37 {}
38
39 template <std::size_t Index>
get() const40 value_type get() const
41 {
42 return (Index == 0) ? m_left : m_right;
43 }
44
length() const45 difference_type length() const
46 {
47 return static_cast<int>(m_right) - static_cast<int>(m_left);
48 }
49
50 private:
51 unsigned m_left, m_right;
52 };
53
54 struct uint_intervals
55 : public std::vector<uint_interval>
56 {
uint_intervalsuint_intervals57 uint_intervals()
58 {}
59
uint_intervalsuint_intervals60 uint_intervals(unsigned left, unsigned right)
61 {
62 this->push_back(uint_interval(left, right));
63 }
64
operator ()uint_intervals65 uint_intervals & operator()(unsigned left, unsigned right)
66 {
67 this->push_back(uint_interval(left, right));
68 return *this;
69 }
70 };
71
operator <<(std::ostream & os,uint_interval const & interval)72 std::ostream& operator<<(std::ostream& os, uint_interval const& interval)
73 {
74 os << "[" << interval.get<0>() << ", " << interval.get<1>() << "]";
75 return os;
76 }
77
78
79 template <typename RangeOfIntervals>
test_one(std::string const & case_id,RangeOfIntervals const & intervals,typename boost::range_value<RangeOfIntervals>::type::difference_type expected_gap)80 inline void test_one(std::string const& case_id,
81 RangeOfIntervals const& intervals,
82 typename boost::range_value
83 <
84 RangeOfIntervals
85 >::type::difference_type expected_gap)
86 {
87 typedef typename boost::range_value<RangeOfIntervals>::type interval_type;
88 typedef typename interval_type::difference_type gap_type;
89
90 gap_type gap = bg::maximum_gap(intervals);
91
92 std::ostringstream stream;
93 for (typename boost::range_const_iterator<RangeOfIntervals>::type
94 it = boost::const_begin(intervals);
95 it != boost::const_end(intervals);
96 ++it)
97 {
98 stream << " " << *it;
99 }
100
101 #ifdef BOOST_GEOMETRY_TEST_DEBUG
102 std::cout << "intervals:" << stream.str() << std::endl;
103 std::cout << "gap found? " << ((gap > 0) ? "yes" : "no") << std::endl;
104 std::cout << "max gap length: " << gap << std::endl;
105 std::cout << std::endl << std::endl;
106 #endif
107
108 BOOST_CHECK_MESSAGE(gap == expected_gap,
109 case_id << "; intervals: "
110 << stream.str()
111 << "; expected: " << expected_gap
112 << ", detected: " << gap);
113 }
114
BOOST_AUTO_TEST_CASE(test_maximum_gap)115 BOOST_AUTO_TEST_CASE( test_maximum_gap )
116 {
117 uint_intervals intervals;
118
119 intervals = uint_intervals(3,4)(1,10)(5,11)(20,35)(12,14)(36,40)(39,41)(35,36)(37,37)(50,50)(50,51);
120 test_one("case_01", intervals, 9);
121
122 intervals = uint_intervals(3,4)(1,10)(5,11)(20,35)(52,60)(12,14)(36,40)(39,41)(35,36)(37,37)(55,56);
123 test_one("case_02", intervals, 11);
124
125 intervals = uint_intervals(3,4);
126 test_one("case_03", intervals, 0);
127
128 intervals = uint_intervals(3,4)(15,15);
129 test_one("case_04", intervals, 11);
130
131 intervals = uint_intervals(3,14)(5,5)(5,6);
132 test_one("case_05", intervals, 0);
133
134 intervals = uint_intervals(3,10)(15,15)(15,18)(15,16);
135 test_one("case_06", intervals, 5);
136
137 intervals = uint_intervals(38,41)(3,10)(15,15)(15,18)(15,16)(20,30)(22,30)(23,30);
138 test_one("case_07", intervals, 8);
139 }
140