GCC Code Coverage Report

Directory: ./
File: src/matrix-view.cc
Date: 2025-05-05 12:19:30
Exec Total Coverage
Lines: 134 143 93.7%
Branches: 104 158 65.8%
Line Branch Exec Source
1 // Copyright (c) 2017 CNRS
2 // Authors: Joseph Mirabel (joseph.mirabel@laas.fr) and Florent Lamiraux
3 //
4
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
7 // met:
8 //
9 // 1. Redistributions of source code must retain the above copyright
10 // notice, this list of conditions and the following disclaimer.
11 //
12 // 2. Redistributions in binary form must reproduce the above copyright
13 // notice, this list of conditions and the following disclaimer in the
14 // documentation and/or other materials provided with the distribution.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
27 // DAMAGE.
28
29 #include <hpp/constraints/matrix-view.hh>
30
31 namespace Eigen {
32 typedef hpp::constraints::size_type size_type;
33
34 namespace internal {
35 template <bool lfirst, bool rfirst>
36 struct BlockIndexComp {
37 typedef BlockIndex::segment_t segment_t;
38 223898 bool operator()(const segment_t& l, const segment_t& r) const {
39 223898 return (lfirst ? l.first : l.first + l.second) <
40 223898 (rfirst ? r.first : r.first + r.second);
41 }
42 };
43 struct BlockIndexCompFull {
44 typedef BlockIndex::segment_t segment_t;
45 82140 bool operator()(const segment_t& l, const segment_t& r) const {
46
5/6
✓ Branch 0 taken 82101 times.
✓ Branch 1 taken 39 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 82097 times.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 82140 return (l.first < r.first) || (l.first == r.first && l.second < r.second);
47 }
48 };
49 } // namespace internal
50
51 32156 void BlockIndex::sort(segments_t& a) {
52 32156 std::sort(a.begin(), a.end(), internal::BlockIndexCompFull());
53 32156 }
54
55 53747 void BlockIndex::shrink(segments_t& a) {
56
2/2
✓ Branch 1 taken 36968 times.
✓ Branch 2 taken 16779 times.
 53747 if (a.size() < 2) return;
57 // Find consecutive element which overlap
58 16779 typename segments_t::iterator e2 = a.begin();
59 16779 typename segments_t::iterator e1 = e2++;
60 internal::BlockIndexComp<false, true> lend_before_rstart;
61
2/2
✓ Branch 2 taken 60115 times.
✓ Branch 3 taken 16779 times.
 76894 while (e2 != a.end()) {
62
2/2
✓ Branch 3 taken 41243 times.
✓ Branch 4 taken 18872 times.
 60115 if (!lend_before_rstart(*e1, *e2)) {
63 41243 e1->second = std::max(e1->second, e2->first + e2->second - e1->first);
64
1/2
✓ Branch 2 taken 41243 times.
✗ Branch 3 not taken.
 41243 e2 = a.erase(e2);
65 } else {
66 18872 e1 = e2;
67 18872 ++e2;
68 }
69 }
70 }
71
72 6453 bool BlockIndex::overlap(const segment_t& a, const segment_t& b) {
73
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 6452 times.
 6453 if (a.second == 0) return false;
74
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 6451 times.
 6452 if (b.second == 0) return false;
75
76 6451 size_type aend = a.first + a.second;
77 6451 size_type bend = b.first + b.second;
78
79
4/4
✓ Branch 0 taken 6433 times.
✓ Branch 1 taken 18 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 6431 times.
 6451 if (a.first <= b.first && b.first < aend) return true;
80
4/4
✓ Branch 0 taken 6432 times.
✓ Branch 1 taken 17 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 6431 times.
 6449 if (a.first < bend && bend <= aend) return true;
81 6448 return false;
82 }
83
84 120302 size_type BlockIndex::cardinal(const segments_t& a) {
85 120302 size_type c = 0;
86
2/2
✓ Branch 3 taken 132442 times.
✓ Branch 4 taken 120302 times.
 252744 for (typename segments_t::const_iterator _a = a.begin(); _a != a.end(); ++_a)
87 132442 c += _a->second;
88 120302 return c;
89 }
90
91 ✗ BlockIndex::segments_t BlockIndex::sum(const segment_t& a, const segment_t& b) {
92 ✗ if (a.first > b.first) return sum(b, a);
93 // a.first <= b.first
94 ✗ segments_t s(1, a);
95 ✗ if (a.first + a.second >= b.first)
96 ✗ s[0].second = std::max(a.second, b.first + b.second - a.first);
97 else
98 ✗ s.push_back(b);
99 ✗ return s;
100 }
101
102 5 void BlockIndex::add(segments_t& a, const segment_t& b) {
103 // Sorted insertion of b into a
104 segments_t::iterator _it =
105
1/2
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
 5 std::upper_bound(a.begin(), a.end(), b, internal::BlockIndexCompFull());
106 // if a is empty, make sure _it is equal to a.end ()
107
3/4
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 3 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
 5 assert(_it == a.end() || !a.empty());
108
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 5 a.insert(_it, b);
109 5 }
110
111 12923 void BlockIndex::add(segments_t& a, const segments_t& b) {
112 // Sorted insertion of b into a, assuming b is sorted.
113
2/2
✓ Branch 1 taken 12871 times.
✓ Branch 2 taken 52 times.
 12923 if (a.empty()) {
114
1/2
✓ Branch 1 taken 12871 times.
✗ Branch 2 not taken.
 12871 a = b;
115 12871 return;
116 }
117 52 segments_t::iterator _a = a.begin();
118
2/2
✓ Branch 4 taken 42 times.
✓ Branch 5 taken 52 times.
 94 for (segments_t::const_iterator _b = b.begin(); _b != b.end(); ++_b) {
119
1/2
✓ Branch 3 taken 42 times.
✗ Branch 4 not taken.
 42 _a = std::upper_bound(_a, a.end(), *_b, internal::BlockIndexCompFull());
120
1/2
✓ Branch 3 taken 42 times.
✗ Branch 4 not taken.
 42 _a = a.insert(_a, *_b);
121 42 ++_a;
122 }
123 }
124
125 13039 BlockIndex::segments_t BlockIndex::difference(const segment_t& a,
126 const segment_t& b) {
127
3/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 13038 times.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 13039 if (a.second == 0) return segments_t(0);
128
3/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 13037 times.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 13038 if (b.second == 0) return segments_t(1, a);
129
130 13037 size_type aend = a.first + a.second;
131 13037 size_type bend = b.first + b.second;
132 13037 segments_t diffs;
133
134
2/2
✓ Branch 0 taken 12919 times.
✓ Branch 1 taken 118 times.
 13037 if (a.first < b.first) {
135 12919 size_type end = std::min(aend, b.first);
136
1/2
✓ Branch 2 taken 12919 times.
✗ Branch 3 not taken.
 12919 diffs.push_back(segment_t(a.first, end - a.first));
137 }
138
2/2
✓ Branch 0 taken 158 times.
✓ Branch 1 taken 12879 times.
 13037 if (bend < aend) {
139 158 size_type start = std::max(a.first, bend);
140
1/2
✓ Branch 2 taken 158 times.
✗ Branch 3 not taken.
 158 diffs.push_back(segment_t(start, aend - start));
141 }
142 13037 return diffs;
143 13037 }
144
145 25914 BlockIndex::segments_t BlockIndex::difference(const segments_t& a,
146 const segment_t& b) {
147
1/2
✓ Branch 3 taken 25914 times.
✗ Branch 4 not taken.
 25914 segments_t::const_iterator first(std::upper_bound(
148 a.begin(), a.end(), b, internal::BlockIndexComp<true, false>()));
149
3/4
✓ Branch 2 taken 13040 times.
✓ Branch 3 taken 12874 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 13040 times.
 25914 assert(first == a.end() || b.first <= first->first + first->second);
150
1/2
✓ Branch 3 taken 25914 times.
✗ Branch 4 not taken.
 25914 segments_t::const_iterator last(std::upper_bound(
151 a.begin(), a.end(), b, internal::BlockIndexComp<false, true>()));
152
3/4
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 25906 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 8 times.
 25914 assert(last == a.end() || b.first + b.second <= last->first);
153 25914 segments_t ret;
154
1/2
✓ Branch 2 taken 25914 times.
✗ Branch 3 not taken.
 25914 ret.reserve(a.size() + 2);
155
1/2
✓ Branch 4 taken 25914 times.
✗ Branch 5 not taken.
 25914 ret.insert(ret.end(), a.begin(), first);
156
2/2
✓ Branch 2 taken 13033 times.
✓ Branch 3 taken 25914 times.
 38947 for (typename segments_t::const_iterator _a = first; _a != last; ++_a) {
157
1/2
✓ Branch 2 taken 13033 times.
✗ Branch 3 not taken.
 13033 segments_t diff = difference(*_a, b);
158
1/2
✓ Branch 5 taken 13033 times.
✗ Branch 6 not taken.
 13033 ret.insert(ret.end(), diff.begin(), diff.end());
159 13033 }
160
1/2
✓ Branch 4 taken 25914 times.
✗ Branch 5 not taken.
 25914 ret.insert(ret.end(), last, a.end());
161 51828 return ret;
162 }
163
164 25872 BlockIndex::segments_t BlockIndex::difference(const segment_t& a,
165 const segments_t& b) {
166
1/2
✓ Branch 2 taken 25872 times.
✗ Branch 3 not taken.
 25872 segments_t diff(1, a);
167
2/2
✓ Branch 3 taken 25912 times.
✓ Branch 4 taken 25872 times.
 51784 for (typename segments_t::const_iterator _b = b.begin(); _b != b.end(); ++_b)
168
1/2
✓ Branch 2 taken 25912 times.
✗ Branch 3 not taken.
 25912 diff = difference(diff, *_b);
169 25872 return diff;
170 }
171
172 12922 BlockIndex::segments_t BlockIndex::difference(const segments_t& a,
173 const segments_t& b) {
174 12922 segments_t diff;
175
2/2
✓ Branch 3 taken 12948 times.
✓ Branch 4 taken 12922 times.
 25870 for (typename segments_t::const_iterator _a = a.begin(); _a != a.end();
176 12948 ++_a) {
177
1/2
✓ Branch 2 taken 12948 times.
✗ Branch 3 not taken.
 12948 segments_t d = difference(*_a, b);
178
1/2
✓ Branch 5 taken 12948 times.
✗ Branch 6 not taken.
 12948 diff.insert(diff.end(), d.begin(), d.end());
179 12948 }
180 12922 return diff;
181 }
182
183 63 BlockIndex::segments_t BlockIndex::split(segments_t& segments,
184 const size_type& cardinal) {
185
2/4
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 63 times.
 63 assert(BlockIndex::cardinal(segments) >= cardinal);
186
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 63 times.
 63 assert(cardinal >= 0);
187 63 segments_t result;
188 63 size_type remaining = cardinal;
189 63 segments_t::iterator it(segments.begin());
190
1/2
✓ Branch 2 taken 75 times.
✗ Branch 3 not taken.
 75 while (it != segments.end()) {
191
2/2
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 68 times.
 75 if (it->second > remaining) {
192
1/2
✓ Branch 3 taken 7 times.
✗ Branch 4 not taken.
 7 result.push_back(segment_t(it->first, remaining));
193 7 it->first += remaining;
194 7 it->second -= remaining;
195 7 return result;
196
2/2
✓ Branch 1 taken 56 times.
✓ Branch 2 taken 12 times.
 68 } else if (it->second == remaining) {
197
1/2
✓ Branch 2 taken 56 times.
✗ Branch 3 not taken.
 56 result.push_back(*it);
198
1/2
✓ Branch 2 taken 56 times.
✗ Branch 3 not taken.
 56 it = segments.erase(it);
199 56 return result;
200 } else {
201 12 remaining -= it->second;
202
1/2
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 12 result.push_back(*it);
203
1/2
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 12 it = segments.erase(it);
204 }
205 }
206 ✗ return result;
207 }
208
209 13 BlockIndex::segments_t BlockIndex::extract(const segments_t& segments,
210 size_type start,
211 size_type cardinal) {
212
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 13 times.
 13 assert(start >= 0);
213
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 13 times.
 13 assert(cardinal >= 0);
214
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 13 times.
 13 assert(segments[0].first >= 0);
215
2/4
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 13 times.
 13 assert(start + cardinal <= BlockIndex::cardinal(segments));
216 13 segments_t result;
217 13 size_type remainingToStart = start;
218 size_type startIndex;
219 size_type remainingToEnd;
220 13 segments_t::const_iterator it(segments.begin());
221
1/2
✓ Branch 2 taken 31 times.
✗ Branch 3 not taken.
 31 while (it != segments.end()) {
222
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 14 times.
 31 if (remainingToStart >= 0) {
223 // looking for start
224
2/2
✓ Branch 1 taken 13 times.
✓ Branch 2 taken 4 times.
 17 if (it->second > remainingToStart) {
225 13 startIndex = it->first + remainingToStart;
226
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 10 times.
 13 if (it->second - remainingToStart >= cardinal) {
227
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 result.push_back(segment_t(startIndex, cardinal));
228 3 return result;
229 } else {
230
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 result.push_back(
231 10 segment_t(startIndex, it->second - remainingToStart));
232 10 remainingToEnd = cardinal - (it->second - remainingToStart);
233 10 ++it;
234 10 remainingToStart = -1;
235 }
236 } else {
237 4 remainingToStart -= it->second;
238 4 ++it;
239 }
240 } else {
241 // looking for end
242
2/2
✓ Branch 1 taken 10 times.
✓ Branch 2 taken 4 times.
 14 if (it->second >= remainingToEnd) {
243
1/2
✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
 10 result.push_back(segment_t(it->first, remainingToEnd));
244 10 return result;
245 } else {
246
1/2
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 4 result.push_back(segment_t(it->first, it->second));
247 4 remainingToEnd -= it->second;
248 4 ++it;
249 }
250 }
251 }
252 ✗ assert(false && "Failed to extract segments_t");
253 // Avoid compilation warning
254 return segments_t();
255 13 }
256 } // namespace Eigen
257