Debian Codegraph @

packages/stk/stk_unit_tests/stk_util/util/UnitTestMCSR.cpp

raw
1 // Copyright 2002 - 2008, 2010, 2011 National Technology Engineering
2 // Solutions of Sandia, LLC (NTESS). Under the terms of Contract
3 // DE-NA0003525 with NTESS, the U.S. Government retains certain rights
4 // in this software.
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 // * Redistributions of source code must retain the above copyright
11 // notice, this list of conditions and the following disclaimer.
12 //
13 // * Redistributions in binary form must reproduce the above
14 // copyright notice, this list of conditions and the following
15 // disclaimer in the documentation and/or other materials provided
16 // with the distribution.
17 //
18 // * Neither the name of NTESS nor the names of its contributors
19 // may be used to endorse or promote products derived from this
20 // software without specific prior written permission.
21 //
22 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
25 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
26 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
28 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 //
34
35 #include "gtest/gtest.h"
36 #include "stk_util/util/MCSR.hpp"
37 #include <vector>
38
39
40 TEST( MCSR, basic)
41 {
42 constexpr unsigned numRows = 4;
43 constexpr int invalidItem = -1;
44 stk::util::MCSR<int> mcsr(numRows, invalidItem);
45
46 for(unsigned i=0; i<numRows; ++i) {
47 EXPECT_EQ(0u, mcsr.size(i));
48 EXPECT_EQ(mcsr.begin(i), mcsr.end(i));
49 EXPECT_TRUE(mcsr.items(i).empty());
50 }
51
52 #ifndef NDEBUG
53 EXPECT_ANY_THROW(mcsr.size(numRows));
54 EXPECT_ANY_THROW(mcsr.begin(numRows));
55 #endif
56 }
57
58 TEST(MCSR, find_sorted_insertion_index_empty)
59 {
60 std::vector<int> items;
61 stk::util::IndexRange indices(0,0);
62 const int item = 42;
63 EXPECT_EQ(0, stk::util::find_sorted_insertion_index(items, indices, item));
64 }
65
66 TEST(MCSR, addItem)
67 {
68 constexpr unsigned numRows = 3;
69 constexpr int invalidItem = -1;
70 stk::util::MCSR<int> mcsr(numRows, invalidItem);
71
72 unsigned row = 0;
73 int item = 1;
74
75 EXPECT_TRUE(mcsr.add_item(row, item));
76 EXPECT_EQ(1u, mcsr.size(row));
77 ASSERT_EQ(1u, std::distance(mcsr.begin(row), mcsr.end(row)));
78 EXPECT_EQ(1u, mcsr.items(row).size());
79 EXPECT_EQ(item, mcsr.begin(row)[0]);
80 }
81
82 TEST(MCSR, addTwoSeparateItems)
83 {
84 constexpr unsigned numRows = 3;
85 constexpr int invalidItem = -1;
86 stk::util::MCSR<int> mcsr(numRows, invalidItem);
87
88 unsigned row0 = 0, row1 = 1;
89 int item1 = 1, item11 = 11;
90 EXPECT_TRUE(mcsr.add_item(row0, item1));
91 EXPECT_TRUE(mcsr.add_item(row1, item11));
92
93 EXPECT_EQ(1u, mcsr.size(row0));
94 ASSERT_EQ(1u, std::distance(mcsr.begin(row0), mcsr.end(row0)));
95 EXPECT_EQ(item1, mcsr.begin(row0)[0]);
96
97 EXPECT_EQ(1u, mcsr.size(row1));
98 ASSERT_EQ(1u, std::distance(mcsr.begin(row1), mcsr.end(row1)));
99 EXPECT_EQ(item11, mcsr.begin(row1)[0]);
100 }
101
102 TEST(MCSR, addTwoSeparateItemsInReverseOrder)
103 {
104 constexpr unsigned numRows = 3;
105 constexpr int invalidItem = -1;
106 stk::util::MCSR<int> mcsr(numRows, invalidItem);
107
108 unsigned row0 = 0, row1 = 1;
109 int item1 = 1, item11 = 11;
110 EXPECT_TRUE(mcsr.add_item(row1, item11));
111 EXPECT_TRUE(mcsr.add_item(row0, item1));
112
113 EXPECT_EQ(1u, mcsr.size(row0));
114 ASSERT_EQ(1u, std::distance(mcsr.begin(row0), mcsr.end(row0)));
115 EXPECT_EQ(item1, mcsr.begin(row0)[0]);
116
117 EXPECT_EQ(1u, mcsr.size(row1));
118 ASSERT_EQ(1u, std::distance(mcsr.begin(row1), mcsr.end(row1)));
119 EXPECT_EQ(item11, mcsr.begin(row1)[0]);
120 }
121
122 TEST(MCSR, addItemsOutOfOrderForSingleRow)
123 {
124 constexpr unsigned numRows = 3;
125 constexpr int invalidItem = -1;
126 stk::util::MCSR<int> mcsr(numRows, invalidItem);
127
128 unsigned row0 = 0;
129
130 std::vector<int> items = {5, 9, 7};
131
132 for(int item : items) {
133 EXPECT_TRUE(mcsr.add_item(row0, item));
134 }
135
136 EXPECT_EQ(3u, mcsr.size(row0));
137 ASSERT_EQ(3u, std::distance(mcsr.begin(row0), mcsr.end(row0)));
138 const int* rowItems = mcsr.begin(row0);
139 std::sort(items.begin(), items.end());
140 for(unsigned i=0; i<3u; ++i) {
141 EXPECT_EQ(items[i], rowItems[i]);
142 }
143 }
144
145 TEST(MCSR, addDuplicates_noOp)
146 {
147 constexpr unsigned numRows = 3;
148 constexpr int invalidItem = -1;
149 stk::util::MCSR<int> mcsr(numRows, invalidItem);
150
151 unsigned row0 = 0;
152
153 std::vector<int> items = {5, 9, 7};
154
155 for(int item : items) {
156 EXPECT_TRUE(mcsr.add_item(row0, item));
157 }
158
159 EXPECT_FALSE(mcsr.add_item(row0, items[1]));
160
161 EXPECT_EQ(3u, mcsr.size(row0));
162 ASSERT_EQ(3u, std::distance(mcsr.begin(row0), mcsr.end(row0)));
163 EXPECT_EQ(3u, mcsr.items(row0).size());
164 const int* rowItems = mcsr.begin(row0);
165 std::sort(items.begin(), items.end());
166 for(unsigned i=0; i<3u; ++i) {
167 EXPECT_EQ(items[i], rowItems[i]);
168 }
169 }
170
171 TEST(MCSR, addTwoSeparateItemsThenAnotherForFirstRow)
172 {
173 constexpr unsigned numRows = 3;
174 constexpr int invalidItem = -1;
175 stk::util::MCSR<int> mcsr(numRows, invalidItem);
176
177 unsigned row0 = 0, row1 = 1;
178
179 int item1 = 1, item11 = 11;
180 EXPECT_TRUE(mcsr.add_item(row0, item1));
181 EXPECT_TRUE(mcsr.add_item(row1, item11));
182
183 int item2 = 2;
184 EXPECT_TRUE(mcsr.add_item(row0, item2));
185
186 EXPECT_EQ(2u, mcsr.size(row0));
187 ASSERT_EQ(2u, std::distance(mcsr.begin(row0), mcsr.end(row0)));
188 EXPECT_EQ(item1, mcsr.begin(row0)[0]);
189 EXPECT_EQ(item2, mcsr.begin(row0)[1]);
190
191 EXPECT_EQ(1u, mcsr.size(row1));
192 ASSERT_EQ(1u, std::distance(mcsr.begin(row1), mcsr.end(row1)));
193 EXPECT_EQ(item11, mcsr.begin(row1)[0]);
194
195 EXPECT_EQ(3u, mcsr.total_num_items());
196 EXPECT_EQ(1u, mcsr.num_unused_entries());
197
198 mcsr.compress();
199
200 EXPECT_EQ(3u, mcsr.total_num_items());
201 EXPECT_EQ(0u, mcsr.num_unused_entries());
202 }
203
204 TEST(MCSR, removeTheOnlyConnectivity)
205 {
206 constexpr unsigned numRows = 3;
207 constexpr int invalidItem = -1;
208 stk::util::MCSR<int> mcsr(numRows, invalidItem);
209
210 unsigned row0 = 0;
211
212 int item1 = 1;
213
214 EXPECT_TRUE(mcsr.add_item(row0, item1));
215 EXPECT_TRUE(mcsr.remove_item(row0, item1));
216
217 EXPECT_EQ(0u, mcsr.size(row0));
218 ASSERT_EQ(0u, std::distance(mcsr.begin(row0), mcsr.end(row0)));
219 EXPECT_EQ(1u, mcsr.num_unused_entries());
220 std::vector<int> testItems;
221 mcsr.clear(0, testItems);
222 EXPECT_EQ(1u, std::count_if(testItems.begin(), testItems.end(),
223 [&](const int& item){return item == invalidItem;}));
224 }
225
226 TEST(MCSR, addItemsInWeirdOrder)
227 {
228 constexpr unsigned numRows = 3;
229 constexpr int invalidItem = -1;
230 stk::util::MCSR<int> mcsr(numRows, invalidItem);
231
232 unsigned row0 = 0, row1 = 1, row2 = 2;
233
234 int item1 = 1, item2 = 2, item11 = 11, item12 = 12;
235
236 EXPECT_TRUE(mcsr.add_item(row0, item1));
237 EXPECT_TRUE(mcsr.add_item(row1, item11));
238 EXPECT_TRUE(mcsr.add_item(row0, item2));
239 EXPECT_TRUE(mcsr.add_item(row2, item12));
240
241 EXPECT_EQ(2u, mcsr.size(row0));
242 EXPECT_EQ(item1, mcsr.begin(row0)[0]);
243 EXPECT_EQ(item2, mcsr.begin(row0)[1]);
244
245 EXPECT_EQ(1u, mcsr.size(row1));
246 EXPECT_EQ(item11, mcsr.begin(row1)[0]);
247
248 EXPECT_EQ(1u, mcsr.size(row2));
249 EXPECT_EQ(item12, mcsr.begin(row2)[0]);
250 }
251
252 TEST(MCSR, addAndRemoveMultipleItems)
253 {
254 constexpr unsigned numRows = 3;
255 constexpr int invalidItem = -1;
256 stk::util::MCSR<int> mcsr(numRows, invalidItem);
257
258 unsigned row0 = 0, row1 = 1;
259
260 int entity1(1), entity2(2), entity11(11), entity12(12);
261
262 EXPECT_TRUE(mcsr.add_item(row0, entity1));
263 EXPECT_TRUE(mcsr.add_item(row1, entity11));
264 EXPECT_TRUE(mcsr.add_item(row0, entity2));
265 EXPECT_TRUE(mcsr.add_item(row1, entity12));
266 EXPECT_EQ(2u, mcsr.num_unused_entries());
267
268 EXPECT_TRUE(mcsr.remove_item(row0, entity2));
269 EXPECT_EQ(1u, mcsr.size(row0));
270 EXPECT_EQ(entity1, mcsr.begin(row0)[0]);
271
272 EXPECT_TRUE(mcsr.remove_item(row1, entity11));
273 EXPECT_EQ(1u, mcsr.size(row1));
274 EXPECT_EQ(entity12, mcsr.begin(1)[0]);
275
276 EXPECT_TRUE(mcsr.remove_item(row1, entity12));
277 EXPECT_EQ(0u, mcsr.size(row1));
278 EXPECT_EQ(mcsr.begin(row1), mcsr.end(row1));
279
280 EXPECT_FALSE(mcsr.remove_item(row0, entity2));
281 EXPECT_EQ(1u, mcsr.size(row0));
282 EXPECT_EQ(entity1, mcsr.begin(row0)[0]);
283
284 EXPECT_EQ(5u, mcsr.num_unused_entries());
285 std::vector<int> testItems;
286 mcsr.clear(0, testItems);
287 EXPECT_EQ(5u, std::count_if(testItems.begin(), testItems.end(),
288 [&](const int& item){return item == invalidItem;}));
289 }
290
291 TEST(MCSR, removeAllItemsForRow)
292 {
293 constexpr unsigned numRows = 3;
294 constexpr int invalidItem = -1;
295 stk::util::MCSR<int> mcsr(numRows, invalidItem);
296
297 unsigned row0 = 0, row1 = 1;
298
299 int entity1(1), entity2(2), entity11(11), entity12(12);
300
301 EXPECT_TRUE(mcsr.add_item(row0, entity1));
302 EXPECT_TRUE(mcsr.add_item(row1, entity11));
303 EXPECT_TRUE(mcsr.add_item(row0, entity2));
304 EXPECT_TRUE(mcsr.add_item(row1, entity12));
305
306 EXPECT_TRUE(mcsr.remove_items(row0));
307 EXPECT_EQ(0u, mcsr.size(row0));
308 EXPECT_EQ(mcsr.begin(0), mcsr.end(0));
309
310 EXPECT_EQ(2u, mcsr.size(row1));
311 EXPECT_EQ(entity11, mcsr.begin(row1)[0]);
312 EXPECT_EQ(entity12, mcsr.begin(row1)[1]);
313 }
314
315 TEST(MCSR, makeHoleThenFillHoleWithoutRaisingCapacity)
316 {
317 constexpr unsigned numRows = 3;
318 constexpr int invalidItem = -1;
319 stk::util::MCSR<int> mcsr(numRows, invalidItem);
320
321 unsigned row0 = 0, row1 = 1, row2 = 2;
322
323 int entity1(1), entity2(2), entity11(11), entity12(12);
324 int entity21(21), entity22(22);
325
326 EXPECT_TRUE(mcsr.add_item(row0, entity1));
327 EXPECT_TRUE(mcsr.add_item(row0, entity2));
328 EXPECT_TRUE(mcsr.add_item(row1, entity11));
329 EXPECT_TRUE(mcsr.add_item(row1, entity12));
330 EXPECT_TRUE(mcsr.add_item(row2, entity21));
331 EXPECT_TRUE(mcsr.add_item(row2, entity22));
332
333 size_t totalCapacity = mcsr.total_capacity();
334 size_t totalNumConnectivity = mcsr.total_num_items();
335 size_t numUnused = mcsr.num_unused_entries();
336
337 EXPECT_TRUE(mcsr.remove_items(row1));
338 EXPECT_EQ(0u, mcsr.size(row1));
339 EXPECT_EQ(mcsr.begin(row1), mcsr.end(row1));
340
341 EXPECT_TRUE(mcsr.add_item(row1, entity11));
342 EXPECT_TRUE(mcsr.add_item(row1, entity12));
343
344 EXPECT_TRUE(totalCapacity == mcsr.total_capacity());
345 EXPECT_TRUE(totalNumConnectivity == mcsr.total_num_items());
346 EXPECT_TRUE(numUnused == mcsr.num_unused_entries());
347 }
348
349 TEST(MCSR, removeItemsIf)
350 {
351 constexpr unsigned numRows = 3;
352 constexpr int invalidItem = -1;
353 stk::util::MCSR<int> mcsr(numRows, invalidItem);
354
355 unsigned row0 = 0, row1 = 1, row2 = 2;
356
357 int entity1(1), entity2(2), entity11(11), entity12(12), entity13(13), entity21(21), entity22(22);
358
359 EXPECT_TRUE(mcsr.add_item(row0, entity1));
360 EXPECT_TRUE(mcsr.add_item(row0, entity2));
361 EXPECT_TRUE(mcsr.add_item(row1, entity11));
362 EXPECT_TRUE(mcsr.add_item(row1, entity12));
363 EXPECT_TRUE(mcsr.add_item(row1, entity13));
364 EXPECT_TRUE(mcsr.add_item(row2, entity21));
365 EXPECT_TRUE(mcsr.add_item(row2, entity22));
366
367 EXPECT_TRUE(mcsr.remove_items_if(row1, [&](const int& i) { return i==entity12;}));
368 EXPECT_EQ(2u, mcsr.size(row1));
369 EXPECT_EQ(entity11, mcsr.begin(row1)[0]);
370 EXPECT_EQ(entity13, mcsr.begin(row1)[1]);
371 }
372
373 TEST(MCSR, removeItemsGreaterEqual)
374 {
375 constexpr unsigned numRows = 3;
376 constexpr int invalidItem = -1;
377 stk::util::MCSR<int> mcsr(numRows, invalidItem);
378
379 unsigned row0 = 0, row1 = 1, row2 = 2;
380
381 int entity1(1), entity2(2), entity11(11), entity12(12), entity13(13), entity21(21), entity22(22);
382
383 EXPECT_TRUE(mcsr.add_item(row0, entity1));
384 EXPECT_TRUE(mcsr.add_item(row0, entity2));
385 EXPECT_TRUE(mcsr.add_item(row1, entity11));
386 EXPECT_TRUE(mcsr.add_item(row1, entity12));
387 EXPECT_TRUE(mcsr.add_item(row1, entity13));
388 EXPECT_TRUE(mcsr.add_item(row2, entity21));
389 EXPECT_TRUE(mcsr.add_item(row2, entity22));
390
391 EXPECT_TRUE(mcsr.remove_items_if(row1, [&](const int& i) { return i >= entity12; }));
392 EXPECT_EQ(1u, mcsr.size(row1));
393 EXPECT_EQ(entity11, mcsr.begin(row1)[0]);
394 }
395