1 /**
2  *
3  *   Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU)
4  *   info_at_agrum_dot_org
5  *
6  *  This library is free software: you can redistribute it and/or modify
7  *  it under the terms of the GNU Lesser General Public License as published by
8  *  the Free Software Foundation, either version 3 of the License, or
9  *  (at your option) any later version.
10  *
11  *  This library is distributed in the hope that it will be useful,
12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  *  GNU Lesser General Public License for more details.
15  *
16  *  You should have received a copy of the GNU Lesser General Public License
17  *  along with this library.  If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 
22 #include <gumtest/AgrumTestSuite.h>
23 #include <gumtest/testsuite_utils.h>
24 
25 #include <agrum/tools/graphs/parts/nodeGraphPart.h>
26 
27 namespace gum_tests {
28 
29   class NodeGraphPartTestSuite: public CxxTest::TestSuite {
30     public:
testConstructor()31     void testConstructor() { TS_GUM_ASSERT_THROWS_NOTHING(gum::NodeGraphPart ngp); }
32 
testInsertion()33     void testInsertion() {
34       gum::NodeGraphPart ngp;
35       TS_ASSERT_EQUALS(ngp.size(), (gum::Size)0)
36       TS_ASSERT(ngp.empty())
37 
38       gum::NodeId firstId = ngp.addNode();
39       TS_ASSERT(!ngp.empty())
40       TS_ASSERT_EQUALS(ngp.size(), (gum::Size)1)
41       TS_ASSERT_EQUALS(firstId, (gum::NodeId)0)
42 
43       ngp.addNode();
44       TS_ASSERT_EQUALS(ngp.size(), (gum::Size)2)
45 
46       ngp.addNode();
47       TS_ASSERT_EQUALS(ngp.size(), (gum::Size)3)
48 
49       gum::NodeId next  = ngp.nextNodeId();
50       gum::NodeId next2 = ngp.addNode();
51       TS_ASSERT_EQUALS(next, next2)
52 
53       TS_GUM_ASSERT_THROWS_NOTHING(ngp.addNodeWithId(next2 + 1));
54       TS_ASSERT_THROWS(ngp.addNodeWithId(next2 + 1), gum::DuplicateElement)
55     }
56 
testSuppression()57     void testSuppression() {
58       gum::NodeGraphPart ngp;
59       ngp.addNode();
60       ngp.addNode();
61       gum::NodeId id3 = ngp.addNode();
62       ngp.addNode();
63 
64       ngp.eraseNode(id3);
65       TS_GUM_ASSERT_THROWS_NOTHING(ngp.eraseNode(id3));
66       TS_ASSERT_EQUALS(ngp.size(), (gum::Size)3)
67 
68       TS_GUM_ASSERT_THROWS_NOTHING(ngp.addNodeWithId(id3));
69       TS_ASSERT_THROWS(ngp.addNodeWithId(id3), gum::DuplicateElement)
70       TS_ASSERT_EQUALS(ngp.size(), (gum::Size)4)
71 
72       ngp.clear();
73       TS_ASSERT_EQUALS(ngp.size(), (gum::Size)0)
74     }
75 
testAdd2()76     void testAdd2() {
77       gum::NodeGraphPart ngp;
78       ngp.addNodeWithId(gum::NodeId(3));
79       TS_ASSERT_EQUALS(ngp._sizeHoles_(), (gum::Size)3)
80       ngp.addNodeWithId(gum::NodeId(2));
81       ngp.addNodeWithId(gum::NodeId(1));
82       ngp.addNodeWithId(gum::NodeId(0));
83       TS_ASSERT_EQUALS(ngp._sizeHoles_(), (gum::Size)0)
84 
85       gum::NodeGraphPart ngp2;
86       ngp2.addNodeWithId(gum::NodeId(0));
87       ngp2.addNodeWithId(gum::NodeId(1));
88       ngp2.addNodeWithId(gum::NodeId(2));
89       ngp2.addNodeWithId(gum::NodeId(3));
90 
91       TS_ASSERT_EQUALS(ngp, ngp2)
92     }
93 
testCopy()94     void testCopy() {
95       gum::NodeGraphPart ngp;
96       ngp.addNode();
97       ngp.addNode();
98       _ForTestCopy_(ngp);
99       TS_ASSERT_EQUALS(ngp._sizeHoles_(), (gum::Size)0)
100       gum::NodeId id3 = ngp.addNode();
101       gum::NodeId id4 = ngp.addNode();
102       ngp.eraseNode(id3);
103       _ForTestCopy_(ngp);
104       TS_ASSERT_EQUALS(ngp._sizeHoles_(), (gum::Size)1)
105       ngp.eraseNode(id4);
106       _ForTestCopy_(ngp);
107       TS_ASSERT_EQUALS(ngp._sizeHoles_(),
108                        (gum::Size)0);   // 2 last hole has vanished
109     }
110 
testInsertionForcee()111     void testInsertionForcee() {
112       gum::NodeGraphPart ngp;
113       gum::NodeId        a = 1;
114       gum::NodeId        b = 2;
115       gum::NodeId        c = 3;
116       gum::NodeId        d = 4;
117       gum::NodeId        e = 5;
118       gum::NodeId        f = 6;
119       gum::NodeId        g = 7;
120 
121       ngp.addNodeWithId(c);
122       TS_ASSERT(ngp._inHoles_(a))
123       TS_ASSERT(ngp._inHoles_(b))
124       TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)3))
125       TS_ASSERT_EQUALS(ngp.bound(), c + 1)
126 
127       ngp.addNodeWithId(a);
128       TS_ASSERT(ngp._inHoles_(b))
129       TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)2))
130       TS_ASSERT_EQUALS(ngp.bound(), c + 1)
131 
132       ngp.addNodeWithId(f);
133       TS_ASSERT(ngp._inHoles_(b))
134       TS_ASSERT(ngp._inHoles_(d))
135       TS_ASSERT(ngp._inHoles_(e))
136       TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)4))
137       TS_ASSERT_EQUALS(ngp.bound(), f + 1)
138 
139       ngp.addNodeWithId(e);
140       TS_ASSERT(ngp._inHoles_(b))
141       TS_ASSERT(ngp._inHoles_(d))
142       TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)3))
143       TS_ASSERT_EQUALS(ngp.bound(), f + 1)
144 
145       ngp.addNodeWithId(b);
146       TS_ASSERT(ngp._inHoles_(d))
147       TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)2))
148       TS_ASSERT_EQUALS(ngp.bound(), f + 1)
149 
150       ngp.addNodeWithId(d);
151       TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)1))
152       TS_ASSERT_EQUALS(ngp.bound(), f + 1)
153 
154       ngp.addNodeWithId(g);
155       TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)1))
156       TS_ASSERT_EQUALS(ngp.bound(), g + 1)
157 
158       ngp.addNodeWithId(gum::NodeId(0));
159       TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)0))
160       TS_ASSERT_EQUALS(ngp.bound(), g + 1)
161 
162       TS_ASSERT_THROWS(ngp.addNodeWithId(f), gum::DuplicateElement)
163     }
164 
testGarbageCollecting()165     void testGarbageCollecting() {
166       gum::NodeGraphPart ngp;
167       gum::NodeId        node = 6;
168 
169       TS_ASSERT_EQUALS(ngp.bound(), (gum::NodeId)(0))
170       TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)0))
171       TS_ASSERT_EQUALS(ngp.nextNodeId(), ((gum::Size)0))
172       ngp.addNodeWithId(node);
173       TS_ASSERT_EQUALS(ngp.bound(), (gum::NodeId)(node + 1))
174       TS_ASSERT_EQUALS(ngp._sizeHoles_(), (gum::Size(node)))
175       TS_ASSERT(ngp.nextNodeId() < node);   // we fill one of the holes
176       ngp.eraseNode(node);
177       TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)0))
178       TS_ASSERT_EQUALS(ngp.nextNodeId(), ((gum::Size)0))
179       TS_ASSERT_EQUALS(ngp.bound(), (gum::NodeId)(0))
180 
181       // do we fill all the holes?
182       gum::NodeGraphPart ngp2;
183       ngp2.addNodeWithId(node);
184 
185       for (gum::Size i = 1; i < node; i++) {
186         TS_ASSERT_EQUALS(ngp2._sizeHoles_(), (gum::Size(node) + 1 - i))
187         TS_ASSERT(ngp2.addNode() < node)
188       }
189 
190       TS_ASSERT_EQUALS(ngp2._sizeHoles_(), (gum::Size)1)
191 
192       TS_ASSERT_EQUALS(ngp2.nextNodeId(), gum::NodeId(node - 1))
193 
194       ngp2.addNode();
195 
196       TS_ASSERT_EQUALS(ngp2._sizeHoles_(), (gum::Size)0)
197       TS_ASSERT_EQUALS(ngp2.nextNodeId(), gum::NodeId(node + 1))
198     }
199 
testUnsafeIterator()200     void testUnsafeIterator() {
201       gum::NodeGraphPart ngp;
202 
203       for (gum::NodeId i = 0; i < 20; ++i) {
204         ngp.addNodeWithId(i);
205       }
206 
207       for (gum::NodeId i = 0; i < 20; ++i) {
208         if (i % 3 == 0) { ngp.eraseNode(i); }
209       }
210 
211       gum::NodeGraphPartIteratorSafe safe_iter = ngp.beginSafe();   // safe iterator needed here
212 
213       for (gum::NodeGraphPartIterator iter = ngp.begin(); iter != ngp.end(); ++iter, ++safe_iter) {
214         TS_ASSERT_EQUALS(*iter, *safe_iter)
215       }
216 
217       gum::Size nb = 0, nb2 = 0;
218 
219       for (auto x: ngp) {
220         ++nb;
221         nb2 += x;
222       }
223 
224       TS_ASSERT_EQUALS(nb, (gum::Size)13)
225     }
226 
testBigNodeGraphPart()227     void testBigNodeGraphPart() { TS_GUM_ASSERT_THROWS_NOTHING(_privateTestBigNodeGraphPart_()); }
228 
testIteratorEnd()229     void testIteratorEnd() {
230       gum::NodeGraphPart nodeset;
231       nodeset.addNode();
232       gum::Size cpt = 0;
233 
234       for (gum::NodeGraphPartIteratorSafe iter = nodeset.beginSafe();   // safe iterator needed here
235            iter != nodeset.endSafe();
236            ++iter) {
237         if (cpt == 0) {
238           nodeset.eraseNode(*iter);
239           cpt++;
240         } else {
241           // If false : infinite loop spotted
242           TS_ASSERT(false)
243           break;
244         }
245       }
246     }
247 
testIteratorEraseNode()248     void testIteratorEraseNode() {
249       gum::NodeGraphPart nodeset;
250       const gum::Size    max_cpt = 100;
251 
252       for (gum::NodeId i = 0; i < max_cpt; ++i) {
253         nodeset.addNode();
254       }
255 
256       gum::Size cpt = 0;
257 
258       for (gum::NodeGraphPartIteratorSafe iter = nodeset.beginSafe();   // safe iterator needed here
259            iter != nodeset.endSafe();
260            ++iter, ++cpt) {
261         TS_GUM_ASSERT_THROWS_NOTHING(nodeset.eraseNode(*iter));
262 
263         if (cpt > max_cpt) {
264           // If false : infinite loop spotted
265           TS_ASSERT(false)
266           break;
267         }
268       }
269 
270       TS_ASSERT_EQUALS(cpt, max_cpt)
271     }
272 
testIteratorAddNodes()273     void testIteratorAddNodes() {
274       gum::NodeGraphPart nodeset;
275 
276       auto v = nodeset.addNodes(100);
277       for (gum::NodeId i = 0; i < 100; i++)
278         TS_ASSERT_EQUALS(v[i], i)
279 
280       for (int i = 0; i < 5; i++)
281         nodeset.eraseNode(2 + i * 19);
282 
283       nodeset.addNodes(5);
284 
285       TS_ASSERT_EQUALS(nodeset.size(), (gum::Size)100)
286 
287       gum::NodeId i = 0;
288       for (auto n: nodeset.nodes())
289         TS_ASSERT_EQUALS(n, i++)
290 
291       gum::NodeGraphPart nodeset2;
292       nodeset2.addNodes(10);
293       gum::NodeGraphPart futureIds;
294 
295       nodeset2.eraseNode(1);
296       futureIds.addNodeWithId(1);
297       nodeset2.eraseNode(3);
298       futureIds.addNodeWithId(3);
299       nodeset2.eraseNode(5);
300       futureIds.addNodeWithId(5);
301 
302       auto v2 = nodeset2.addNodes(4);
303       futureIds.addNodeWithId(10);   // the 4th added node as 10 for id
304 
305       for (auto n: v2) {
306         TS_GUM_ASSERT_THROWS_NOTHING(futureIds.eraseNode(n));
307       }
308       TS_ASSERT(futureIds.empty())
309     }
310 
311     private:
312 #define NBR_PROFILING_NODES 50000
_privateTestBigNodeGraphPart_()313     void _privateTestBigNodeGraphPart_() {
314       {
315         gum::NodeGraphPart ngp;
316         // direct
317 
318         for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) {
319           ngp.addNode();
320         }
321 
322         for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) {
323           ngp.eraseNode(node);
324         }
325       }
326 
327       {
328         gum::NodeGraphPart ngp;
329         // reverse
330 
331         for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) {
332           ngp.addNode();
333         }
334 
335         for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) {
336           ngp.eraseNode(NBR_PROFILING_NODES - node);
337         }
338       }
339 
340       {
341         gum::NodeGraphPart ngp;
342 
343         // direct with id
344 
345         for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) {
346           ngp.addNodeWithId(node);
347         }
348 
349         for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) {
350           ngp.eraseNode(node);
351         }
352       }
353 
354       {
355         gum::NodeGraphPart ngp;
356 
357         // reverse with id
358 
359         for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) {
360           ngp.addNodeWithId(NBR_PROFILING_NODES - node);
361         }
362 
363         for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) {
364           ngp.eraseNode(10000 - node);
365         }
366       }
367     }
368 
_ForTestCopy_(gum::NodeGraphPart & ngp)369     void _ForTestCopy_(gum::NodeGraphPart& ngp) {
370       gum::NodeGraphPart ngp2(ngp);
371       TS_ASSERT_EQUALS(ngp.toString(), ngp2.toString())
372 
373       gum::NodeGraphPart ngp3 = ngp;
374       TS_ASSERT_EQUALS(ngp.toString(), ngp3.toString())
375 
376       gum::NodeGraphPart ngp4;
377       TS_ASSERT(ngp4.empty())
378       ngp4 = ngp;
379       TS_ASSERT_EQUALS(ngp.toString(), ngp3.toString())
380     }
381   };
382 }   // namespace gum_tests
383