Directory: | ./ |
---|---|
File: | src/continuous-validation/intervals.hh |
Date: | 2024-08-10 11:29:48 |
Exec | Total | Coverage | |
---|---|---|---|
Lines: | 58 | 67 | 86.6% |
Branches: | 52 | 74 | 70.3% |
Line | Branch | Exec | Source |
---|---|---|---|
1 | // | ||
2 | // Copyright (c) 2014 CNRS | ||
3 | // Authors: Florent Lamiraux | ||
4 | // | ||
5 | |||
6 | // Redistribution and use in source and binary forms, with or without | ||
7 | // modification, are permitted provided that the following conditions are | ||
8 | // met: | ||
9 | // | ||
10 | // 1. Redistributions of source code must retain the above copyright | ||
11 | // notice, this list of conditions and the following disclaimer. | ||
12 | // | ||
13 | // 2. Redistributions in binary form must reproduce the above copyright | ||
14 | // notice, this list of conditions and the following disclaimer in the | ||
15 | // documentation and/or other materials provided with the distribution. | ||
16 | // | ||
17 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | ||
18 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | ||
19 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | ||
20 | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | ||
21 | // HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | ||
22 | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | ||
23 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | ||
24 | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | ||
25 | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | ||
26 | // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | ||
27 | // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH | ||
28 | // DAMAGE. | ||
29 | |||
30 | #ifndef HPP_CORE_CONTINUOUS_VALIDATION_INTERVALS_HH | ||
31 | #define HPP_CORE_CONTINUOUS_VALIDATION_INTERVALS_HH | ||
32 | |||
33 | #include <hpp/core/fwd.hh> | ||
34 | #include <list> | ||
35 | #include <ostream> | ||
36 | |||
37 | namespace hpp { | ||
38 | namespace core { | ||
39 | namespace continuousValidation { | ||
40 | 4464 | inline bool lastElement(const std::list<interval_t>& list, | |
41 | const std::list<interval_t>::iterator& it) { | ||
42 | 4464 | std::list<interval_t>::iterator it1 = it; | |
43 | 4464 | ++it1; | |
44 |
2/2✓ Branch 3 taken 205 times.
✓ Branch 4 taken 4259 times.
|
4464 | if (it1 == list.end()) return true; |
45 | 4259 | return false; | |
46 | } | ||
47 | /// Union of intervals | ||
48 | class Intervals { | ||
49 | public: | ||
50 | /// Reset to empty set | ||
51 | void clear() { intervals_.clear(); } | ||
52 | /// Union of this with an interval | ||
53 | 10200 | void unionInterval(const interval_t& interval) { | |
54 | 10200 | std::list<std::list<interval_t>::iterator> toErase; | |
55 | 10200 | unsigned int cas = 0; | |
56 | 10200 | std::list<interval_t>::iterator it = intervals_.begin(); | |
57 |
2/2✓ Branch 3 taken 25596 times.
✓ Branch 4 taken 753 times.
|
26349 | for (; it != intervals_.end(); ++it) { |
58 |
2/2✓ Branch 1 taken 4235 times.
✓ Branch 2 taken 21361 times.
|
25596 | if (interval.first < it->first) { |
59 | 4235 | cas = 1; | |
60 | 4235 | break; | |
61 |
2/2✓ Branch 1 taken 5212 times.
✓ Branch 2 taken 16149 times.
|
21361 | } else if (interval.first <= it->second) { |
62 | 5212 | cas = 2; | |
63 | 5212 | break; | |
64 | } | ||
65 | } | ||
66 |
2/2✓ Branch 0 taken 753 times.
✓ Branch 1 taken 9447 times.
|
10200 | if (cas == 0) { |
67 |
1/2✓ Branch 1 taken 753 times.
✗ Branch 2 not taken.
|
753 | intervals_.push_back(interval); |
68 |
2/2✓ Branch 0 taken 4235 times.
✓ Branch 1 taken 5212 times.
|
9447 | } else if (cas == 1) { |
69 | // intervals_ |------------| |=== *it ===| |---------| | ||
70 | // interval |------------------------------ | ||
71 |
2/2✓ Branch 3 taken 4297 times.
✓ Branch 4 taken 218 times.
|
4515 | for (; it != intervals_.end(); ++it) { |
72 |
2/2✓ Branch 1 taken 3865 times.
✓ Branch 2 taken 432 times.
|
4297 | if (interval.second < it->first) { |
73 | // intervals_ ---| |xxxxxxxx| |=== *it ===| |-------| | ||
74 | // interval |----------------| | ||
75 |
1/2✓ Branch 2 taken 3865 times.
✗ Branch 3 not taken.
|
3865 | intervals_.insert(it, interval); |
76 | 3865 | break; | |
77 |
2/2✓ Branch 1 taken 152 times.
✓ Branch 2 taken 280 times.
|
432 | } else if (interval.second < it->second) { |
78 | // intervals_ ---| |xxxxxx| |=== *it ===| |---------| | ||
79 | // interval |---------------------| | ||
80 | 152 | it->first = interval.first; | |
81 | 152 | break; | |
82 | } else { | ||
83 | // intervals_ ---| |=== *it ===| |--------| |--------| | ||
84 | // interval |------------------| | ||
85 |
1/2✓ Branch 1 taken 280 times.
✗ Branch 2 not taken.
|
280 | toErase.push_back(it); |
86 | } | ||
87 | } | ||
88 |
2/2✓ Branch 2 taken 218 times.
✓ Branch 3 taken 4017 times.
|
4235 | if (it == intervals_.end()) { |
89 |
1/2✓ Branch 1 taken 218 times.
✗ Branch 2 not taken.
|
218 | intervals_.push_back(interval); |
90 | } | ||
91 |
1/2✓ Branch 0 taken 5212 times.
✗ Branch 1 not taken.
|
5212 | } else if (cas == 2) { |
92 | // intervals_ |==== *it ====| |-------| |---------| | ||
93 | // interval |---------------------------------- | ||
94 |
2/2✓ Branch 2 taken 9844 times.
✓ Branch 3 taken 55 times.
|
9899 | for (std::list<interval_t>::iterator it1 = it; it1 != intervals_.end(); |
95 | 4687 | ++it1) { | |
96 |
2/2✓ Branch 1 taken 428 times.
✓ Branch 2 taken 9416 times.
|
9844 | if (interval.second < it1->first) { |
97 | // intervals_ |==== *it ====| |-----| |=== *it1 ===| | ||
98 | // interval |--------------| | ||
99 | 428 | it->second = interval.second; | |
100 |
2/2✓ Branch 1 taken 4952 times.
✓ Branch 2 taken 4464 times.
|
9416 | } else if (interval.second < it1->second) { |
101 | // intervals_ |==== *it ====| |-----| |=== *it1 ===| | ||
102 | // interval |-------------------| | ||
103 | 4952 | it->second = it1->second; | |
104 | // Remove it1 if different from it | ||
105 |
2/2✓ Branch 1 taken 4128 times.
✓ Branch 2 taken 824 times.
|
4952 | if (it1 != it) { |
106 |
1/2✓ Branch 1 taken 4128 times.
✗ Branch 2 not taken.
|
4128 | toErase.push_back(it1); |
107 | } | ||
108 | 4952 | break; | |
109 |
2/2✓ Branch 1 taken 205 times.
✓ Branch 2 taken 4259 times.
|
4464 | } else if (lastElement(intervals_, it1)) { |
110 | 205 | it->second = interval.second; | |
111 |
2/2✓ Branch 1 taken 11 times.
✓ Branch 2 taken 194 times.
|
205 | if (it1 != it) { |
112 |
1/2✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
|
11 | toErase.push_back(it1); |
113 | } | ||
114 | 205 | break; | |
115 | } else { | ||
116 | // intervals_ |==== *it ====| |xxxxx| |=== *it1 ===| | ||
117 | // interval |------------------------------------| | ||
118 | // Remove it1 if different from it | ||
119 |
2/2✓ Branch 1 taken 65 times.
✓ Branch 2 taken 4194 times.
|
4259 | if (it1 != it) { |
120 |
1/2✓ Branch 1 taken 65 times.
✗ Branch 2 not taken.
|
65 | toErase.push_back(it1); |
121 | } | ||
122 | } | ||
123 | } | ||
124 | } else { | ||
125 | ✗ | abort(); | |
126 | } | ||
127 | 10200 | for (std::list<std::list<interval_t>::iterator>::iterator itErase = | |
128 | 10200 | toErase.begin(); | |
129 |
2/2✓ Branch 2 taken 4484 times.
✓ Branch 3 taken 10200 times.
|
14684 | itErase != toErase.end(); ++itErase) { |
130 | 4484 | intervals_.erase(*itErase); | |
131 | } | ||
132 | 10200 | } | |
133 | |||
134 | 9855 | bool contains(const interval_t& interval) const { | |
135 | 9855 | for (std::list<interval_t>::const_iterator it = intervals_.begin(); | |
136 |
2/2✓ Branch 3 taken 36589 times.
✓ Branch 4 taken 8588 times.
|
45177 | it != intervals_.end(); ++it) { |
137 |
6/6✓ Branch 1 taken 11572 times.
✓ Branch 2 taken 25017 times.
✓ Branch 4 taken 1267 times.
✓ Branch 5 taken 10305 times.
✓ Branch 6 taken 1267 times.
✓ Branch 7 taken 35322 times.
|
36589 | if ((it->first <= interval.first) && (interval.second <= it->second)) { |
138 | 1267 | return true; | |
139 | } | ||
140 | } | ||
141 | 8588 | return false; | |
142 | } | ||
143 | |||
144 | bool contains(const value_type& value, bool reverse = false) const { | ||
145 | if (reverse) { | ||
146 | for (std::list<interval_t>::const_iterator it = intervals_.begin(); | ||
147 | it != intervals_.end(); ++it) { | ||
148 | if ((it->first <= value) && (value <= it->second)) { | ||
149 | return true; | ||
150 | } | ||
151 | } | ||
152 | } else { | ||
153 | for (std::list<interval_t>::const_reverse_iterator it = | ||
154 | intervals_.rbegin(); | ||
155 | it != intervals_.rend(); ++it) { | ||
156 | if ((it->first <= value) && (value <= it->second)) { | ||
157 | return true; | ||
158 | } | ||
159 | } | ||
160 | } | ||
161 | return false; | ||
162 | } | ||
163 | |||
164 | 52698 | const std::list<interval_t>& list() const { return intervals_; } | |
165 | |||
166 | ✗ | std::ostream& print(std::ostream& os) const { | |
167 | ✗ | os << "Intervals: " << std::endl; | |
168 | ✗ | for (std::list<interval_t>::const_iterator it = intervals_.begin(); | |
169 | ✗ | it != intervals_.end(); ++it) { | |
170 | ✗ | os << "[" << it->first << ", " << it->second << "]" << std::endl; | |
171 | } | ||
172 | ✗ | return os; | |
173 | } | ||
174 | |||
175 | std::string toString() const { | ||
176 | std::ostringstream oss; | ||
177 | print(oss); | ||
178 | return oss.str(); | ||
179 | } | ||
180 | |||
181 | private: | ||
182 | std::list<interval_t> intervals_; | ||
183 | }; // class Intervals | ||
184 | |||
185 | ✗ | inline std::ostream& operator<<(std::ostream& os, const Intervals& o) { | |
186 | ✗ | return o.print(os); | |
187 | } | ||
188 | } // namespace continuousValidation | ||
189 | } // namespace core | ||
190 | } // namespace hpp | ||
191 | #endif // HPP_CORE_CONTINUOUS_VALIDATION_INTERVALS_HH | ||
192 |