1 /*
2 * unittests/core/List.cc
3 * Apto
4 *
5 * Created by David on 2/14/11.
6 * Copyright 2011 David Michael Bryson. All rights reserved.
7 * http://programerror.com/software/apto
8 *
9 * Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
10 * following conditions are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the
13 * following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
15 * following disclaimer in the documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of David Michael Bryson, nor the names of contributors may be used to endorse or promote
17 * products derived from this software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY DAVID MICHAEL BRYSON AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
20 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL DAVID MICHAEL BRYSON OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
23 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
24 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
25 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 *
27 * Authors: David M. Bryson <david@programerror.com>
28 *
29 */
30
31 #include "apto/core/List.h"
32
33 #include "gtest/gtest.h"
34
35
36 // List<int, DL>
37 // --------------------------------------------------------------------------------------------------------------
38
TEST(CoreDLList,Construction)39 TEST(CoreDLList, Construction) {
40 Apto::List<int, Apto::DL> default_constructor;
41 EXPECT_EQ(0, default_constructor.GetSize());
42 }
43
44
TEST(CoreDLList,PushPop)45 TEST(CoreDLList, PushPop) {
46 Apto::List<int, Apto::DL> list;
47 EXPECT_EQ(0, list.GetSize());
48
49 for (int i = 0; i < 3; i++) list.Push(i);
50 EXPECT_EQ(3, list.GetSize());
51 EXPECT_EQ(2, list.GetFirst());
52
53 EXPECT_EQ(2, list.Pop());
54 EXPECT_EQ(2, list.GetSize());
55 EXPECT_EQ(1, list.Pop());
56 list.Push(8);
57 EXPECT_EQ(8, list.Pop());
58 EXPECT_EQ(1, list.GetSize());
59
60 list.PushRear(12);
61 EXPECT_EQ(0, list.Pop());
62 EXPECT_EQ(12, list.Pop());
63 EXPECT_EQ(0, list.GetSize());
64
65 for (int i = 0; i < 3; i++) list.PushRear(i);
66 EXPECT_EQ(3, list.GetSize());
67 EXPECT_EQ(2, list.GetLast());
68 EXPECT_EQ(2, list.PopRear());
69
70 list.Clear();
71 EXPECT_EQ(0, list.GetSize());
72 }
73
74
TEST(CoreDLList,Assignment)75 TEST(CoreDLList, Assignment) {
76 Apto::List<int, Apto::DL> list1;
77 for (int i = 0; i < 5; i++) list1.PushRear(i);
78
79 Apto::List<int, Apto::DL> list2;
80 for (int i = 0; i < 6; i++) list2.PushRear(5 + i);
81
82 EXPECT_NE(list1.GetSize(), list2.GetSize());
83 EXPECT_NE(list1.GetFirst(), list2.GetFirst());
84
85 list1 = list2;
86 EXPECT_EQ(list1.GetSize(), list2.GetSize());
87 EXPECT_EQ(list1.GetFirst(), list2.GetFirst());
88
89 list1 = list1;
90 EXPECT_EQ(list1.GetSize(), list2.GetSize());
91 EXPECT_EQ(list1.GetFirst(), list2.GetFirst());
92
93 Apto::List<int, Apto::DL> list_copy_constructor(list2);
94 EXPECT_EQ(list2.GetSize(), list_copy_constructor.GetSize());
95 EXPECT_EQ(list2.GetFirst(), list_copy_constructor.GetFirst());
96 }
97
98
TEST(CoreDLList,Remove)99 TEST(CoreDLList, Remove) {
100 Apto::List<int, Apto::DL> list;
101 Apto::List<int, Apto::DL>::EntryHandle* handle = NULL;
102
103 list.Push(5);
104 list.Push(10, &handle);
105 list.Push(15);
106 EXPECT_TRUE(handle != NULL);
107 if (handle) EXPECT_TRUE(handle->IsValid());
108 list.Remove(10);
109 if (handle) EXPECT_FALSE(handle->IsValid());
110 EXPECT_EQ(15, list.Pop());
111 EXPECT_EQ(5, list.Pop());
112 EXPECT_EQ(0, list.GetSize());
113
114 list.Push(5);
115 list.Push(10, &handle);
116 list.Push(15);
117 EXPECT_TRUE(handle != NULL);
118 if (handle) EXPECT_TRUE(handle->IsValid());
119 handle->Remove();
120 if (handle) EXPECT_FALSE(handle->IsValid());
121 EXPECT_EQ(15, list.Pop());
122 EXPECT_EQ(5, list.Pop());
123 EXPECT_EQ(0, list.GetSize());
124
125 delete handle;
126 }
127
128
TEST(CoreDLList,Contains)129 TEST(CoreDLList, Contains) {
130 Apto::List<int, Apto::DL> list;
131 list.Push(5);
132 list.Push(10);
133 list.Push(15);
134 EXPECT_TRUE(list.Contains(10));
135 EXPECT_FALSE(list.Contains(20));
136 }
137
138
TEST(CoreDLList,Iterators)139 TEST(CoreDLList, Iterators) {
140 Apto::List<int, Apto::DL> list;
141 for (int i = 0; i < 5; i++) list.PushRear(i);
142
143 Apto::List<int, Apto::DL>::Iterator it = list.Begin();
144 int i = 0;
145 while (it.Next()) {
146 EXPECT_EQ(i, *it.Get());
147 i++;
148 }
149
150 const Apto::List<int, Apto::DL>& const_list = list;
151 Apto::List<int, Apto::DL>::ConstIterator cit = const_list.Begin();
152 i = 0;
153 while (cit.Next()) {
154 EXPECT_EQ(i, *cit.Get());
155 i++;
156 }
157 }
158
159
TEST(CoreDLList,Comparison)160 TEST(CoreDLList, Comparison) {
161 Apto::List<int, Apto::DL> list1;
162 for (int i = 0; i < 3; i++) list1.PushRear(i);
163
164 Apto::List<int, Apto::DL> list2(list1);
165 list2.GetLast() = 5;
166
167 EXPECT_TRUE(list1 == list1);
168 EXPECT_TRUE(list2 == list2);
169 EXPECT_TRUE(list1 != list2);
170 EXPECT_FALSE(list1 == list2);
171 EXPECT_FALSE(list1 != list1);
172 EXPECT_FALSE(list2 != list2);
173 }
174
175
TEST(CoreDLList,Concatenation)176 TEST(CoreDLList, Concatenation) {
177 Apto::List<int, Apto::DL> list1;
178 for (int i = 0; i < 3; i++) list1.PushRear(i);
179
180
181 Apto::List<int, Apto::DL> list2;
182 list2.PushRear(5);
183
184 list2 += list2;
185 EXPECT_EQ(2, list2.GetSize());
186 EXPECT_EQ(5, list2.GetFirst());
187 EXPECT_EQ(5, list2.GetLast());
188
189 list1 += list2;
190
191 EXPECT_EQ(0, list1.Pop());
192 EXPECT_EQ(1, list1.Pop());
193 EXPECT_EQ(2, list1.Pop());
194 EXPECT_EQ(5, list1.Pop());
195 EXPECT_EQ(5, list1.Pop());
196
197 list2.PushRear(6);
198 Apto::List<int, Apto::DL> list3 = list2 + list2;
199 EXPECT_EQ(6, list3.GetSize());
200 EXPECT_EQ(5, list3.GetFirst());
201 EXPECT_EQ(6, list3.GetLast());
202
203 list2 = list2 + list2;
204 EXPECT_TRUE(list2 == list3);
205 }
206
207
208
209 // List<int, BufferedDL>
210 // --------------------------------------------------------------------------------------------------------------
211
TEST(CoreBufferedDLList,Construction)212 TEST(CoreBufferedDLList, Construction) {
213 Apto::List<int, Apto::BufferedDL> default_constructor;
214 EXPECT_EQ(0, default_constructor.GetSize());
215 }
216
217
TEST(CoreBufferedDLList,PushPop)218 TEST(CoreBufferedDLList, PushPop) {
219 Apto::List<int, Apto::BufferedDL> list;
220 EXPECT_EQ(0, list.GetSize());
221
222 for (int i = 0; i < 3; i++) list.Push(i);
223 EXPECT_EQ(3, list.GetSize());
224 EXPECT_EQ(2, list.GetFirst());
225
226 EXPECT_EQ(2, list.Pop());
227 EXPECT_EQ(2, list.GetSize());
228 EXPECT_EQ(1, list.Pop());
229 list.Push(8);
230 EXPECT_EQ(8, list.Pop());
231 EXPECT_EQ(1, list.GetSize());
232
233 list.PushRear(12);
234 EXPECT_EQ(0, list.Pop());
235 EXPECT_EQ(12, list.Pop());
236 EXPECT_EQ(0, list.GetSize());
237
238 for (int i = 0; i < 3; i++) list.PushRear(i);
239 EXPECT_EQ(3, list.GetSize());
240 EXPECT_EQ(2, list.GetLast());
241 EXPECT_EQ(2, list.PopRear());
242
243 list.Clear();
244 EXPECT_EQ(0, list.GetSize());
245 }
246
247
TEST(CoreBufferedDLList,Assignment)248 TEST(CoreBufferedDLList, Assignment) {
249 Apto::List<int, Apto::BufferedDL> list1;
250 for (int i = 0; i < 5; i++) list1.PushRear(i);
251
252 Apto::List<int, Apto::BufferedDL> list2;
253 for (int i = 0; i < 6; i++) list2.PushRear(5 + i);
254
255 EXPECT_NE(list1.GetSize(), list2.GetSize());
256 EXPECT_NE(list1.GetFirst(), list2.GetFirst());
257
258 list1 = list2;
259 EXPECT_EQ(list1.GetSize(), list2.GetSize());
260 EXPECT_EQ(list1.GetFirst(), list2.GetFirst());
261
262 list1 = list1;
263 EXPECT_EQ(list1.GetSize(), list2.GetSize());
264 EXPECT_EQ(list1.GetFirst(), list2.GetFirst());
265
266 Apto::List<int, Apto::BufferedDL> list_copy_constructor(list2);
267 EXPECT_EQ(list2.GetSize(), list_copy_constructor.GetSize());
268 EXPECT_EQ(list2.GetFirst(), list_copy_constructor.GetFirst());
269 }
270
271
TEST(CoreBufferedDLList,Remove)272 TEST(CoreBufferedDLList, Remove) {
273 Apto::List<int, Apto::BufferedDL> list;
274 Apto::List<int, Apto::BufferedDL>::EntryHandle* handle = NULL;
275
276 list.Push(5);
277 list.Push(10, &handle);
278 list.Push(15);
279 EXPECT_TRUE(handle != NULL);
280 if (handle) EXPECT_TRUE(handle->IsValid());
281 list.Remove(10);
282 if (handle) EXPECT_FALSE(handle->IsValid());
283 EXPECT_EQ(15, list.Pop());
284 EXPECT_EQ(5, list.Pop());
285 EXPECT_EQ(0, list.GetSize());
286
287 list.Push(5);
288 list.Push(10, &handle);
289 list.Push(15);
290 EXPECT_TRUE(handle != NULL);
291 if (handle) EXPECT_TRUE(handle->IsValid());
292 handle->Remove();
293 if (handle) EXPECT_FALSE(handle->IsValid());
294 EXPECT_EQ(15, list.Pop());
295 EXPECT_EQ(5, list.Pop());
296 EXPECT_EQ(0, list.GetSize());
297
298 delete handle;
299 }
300
301
TEST(CoreBufferedDLList,Contains)302 TEST(CoreBufferedDLList, Contains) {
303 Apto::List<int, Apto::BufferedDL> list;
304 list.Push(5);
305 list.Push(10);
306 list.Push(15);
307 EXPECT_TRUE(list.Contains(10));
308 EXPECT_FALSE(list.Contains(20));
309 }
310
311
TEST(CoreBufferedDLList,Iterators)312 TEST(CoreBufferedDLList, Iterators) {
313 Apto::List<int, Apto::BufferedDL> list;
314 for (int i = 0; i < 5; i++) list.PushRear(i);
315
316 Apto::List<int, Apto::BufferedDL>::Iterator it = list.Begin();
317 int i = 0;
318 while (it.Next()) {
319 EXPECT_EQ(i, *it.Get());
320 i++;
321 }
322
323 const Apto::List<int, Apto::BufferedDL>& const_list = list;
324 Apto::List<int, Apto::BufferedDL>::ConstIterator cit = const_list.Begin();
325 i = 0;
326 while (cit.Next()) {
327 EXPECT_EQ(i, *cit.Get());
328 i++;
329 }
330 }
331
332
TEST(CoreBufferedDLList,Comparison)333 TEST(CoreBufferedDLList, Comparison) {
334 Apto::List<int, Apto::BufferedDL> list1;
335 for (int i = 0; i < 3; i++) list1.PushRear(i);
336
337 Apto::List<int, Apto::BufferedDL> list2(list1);
338 list2.GetLast() = 5;
339
340 EXPECT_TRUE(list1 == list1);
341 EXPECT_TRUE(list2 == list2);
342 EXPECT_TRUE(list1 != list2);
343 EXPECT_FALSE(list1 == list2);
344 EXPECT_FALSE(list1 != list1);
345 EXPECT_FALSE(list2 != list2);
346 }
347
348
TEST(CoreBufferedDLList,Concatenation)349 TEST(CoreBufferedDLList, Concatenation) {
350 Apto::List<int, Apto::BufferedDL> list1;
351 for (int i = 0; i < 3; i++) list1.PushRear(i);
352
353
354 Apto::List<int, Apto::BufferedDL> list2;
355 list2.PushRear(5);
356
357 list2 += list2;
358 EXPECT_EQ(2, list2.GetSize());
359 EXPECT_EQ(5, list2.GetFirst());
360 EXPECT_EQ(5, list2.GetLast());
361
362 list1 += list2;
363
364 EXPECT_EQ(0, list1.Pop());
365 EXPECT_EQ(1, list1.Pop());
366 EXPECT_EQ(2, list1.Pop());
367 EXPECT_EQ(5, list1.Pop());
368 EXPECT_EQ(5, list1.Pop());
369
370 list2.PushRear(6);
371 Apto::List<int, Apto::BufferedDL> list3 = list2 + list2;
372 EXPECT_EQ(6, list3.GetSize());
373 EXPECT_EQ(5, list3.GetFirst());
374 EXPECT_EQ(6, list3.GetLast());
375
376 list2 = list2 + list2;
377 EXPECT_TRUE(list2 == list3);
378 }
379
380
381
382 // List<int, SparseVector>
383 // --------------------------------------------------------------------------------------------------------------
384
TEST(CoreSparseVectorList,Construction)385 TEST(CoreSparseVectorList, Construction) {
386 Apto::List<int, Apto::SparseVector> default_constructor;
387 EXPECT_EQ(0, default_constructor.GetSize());
388 }
389
390
TEST(CoreSparseVectorList,PushPop)391 TEST(CoreSparseVectorList, PushPop) {
392 Apto::List<int, Apto::SparseVector> list;
393 EXPECT_EQ(0, list.GetSize());
394
395 for (int i = 0; i < 3; i++) list.Push(i);
396 EXPECT_EQ(3, list.GetSize());
397 EXPECT_EQ(2, list.GetFirst());
398
399 EXPECT_EQ(2, list.Pop());
400 EXPECT_EQ(2, list.GetSize());
401 EXPECT_EQ(1, list.Pop());
402 list.Push(8);
403 EXPECT_EQ(8, list.Pop());
404 EXPECT_EQ(1, list.GetSize());
405
406 list.PushRear(12);
407 EXPECT_EQ(0, list.Pop());
408 EXPECT_EQ(12, list.Pop());
409 EXPECT_EQ(0, list.GetSize());
410
411 for (int i = 0; i < 3; i++) list.PushRear(i);
412 EXPECT_EQ(3, list.GetSize());
413 EXPECT_EQ(2, list.GetLast());
414 EXPECT_EQ(2, list.PopRear());
415
416 list.Clear();
417 EXPECT_EQ(0, list.GetSize());
418 }
419
420
TEST(CoreSparseVectorList,Assignment)421 TEST(CoreSparseVectorList, Assignment) {
422 Apto::List<int, Apto::SparseVector> list1;
423 for (int i = 0; i < 5; i++) list1.PushRear(i);
424
425 Apto::List<int, Apto::SparseVector> list2;
426 for (int i = 0; i < 6; i++) list2.PushRear(5 + i);
427
428 EXPECT_NE(list1.GetSize(), list2.GetSize());
429 EXPECT_NE(list1.GetFirst(), list2.GetFirst());
430
431 list1 = list2;
432 EXPECT_EQ(list1.GetSize(), list2.GetSize());
433 EXPECT_EQ(list1.GetFirst(), list2.GetFirst());
434
435 list1 = list1;
436 EXPECT_EQ(list1.GetSize(), list2.GetSize());
437 EXPECT_EQ(list1.GetFirst(), list2.GetFirst());
438
439 Apto::List<int, Apto::SparseVector> list_copy_constructor(list2);
440 EXPECT_EQ(list2.GetSize(), list_copy_constructor.GetSize());
441 EXPECT_EQ(list2.GetFirst(), list_copy_constructor.GetFirst());
442 }
443
444
TEST(CoreSparseVectorList,Remove)445 TEST(CoreSparseVectorList, Remove) {
446 Apto::List<int, Apto::SparseVector> list;
447 Apto::List<int, Apto::SparseVector>::EntryHandle* handle = NULL;
448
449 list.Push(5);
450 list.Push(10, &handle);
451 list.Push(15);
452 EXPECT_TRUE(handle != NULL);
453 if (handle) EXPECT_TRUE(handle->IsValid());
454 list.Remove(10);
455 if (handle) EXPECT_FALSE(handle->IsValid());
456 EXPECT_EQ(15, list.Pop());
457 EXPECT_EQ(5, list.Pop());
458 EXPECT_EQ(0, list.GetSize());
459
460 list.Push(5);
461 list.Push(10, &handle);
462 list.Push(15);
463 EXPECT_TRUE(handle != NULL);
464 if (handle) EXPECT_TRUE(handle->IsValid());
465 handle->Remove();
466 if (handle) EXPECT_FALSE(handle->IsValid());
467 EXPECT_EQ(15, list.Pop());
468 EXPECT_EQ(5, list.Pop());
469 EXPECT_EQ(0, list.GetSize());
470
471 delete handle;
472 }
473
474
TEST(CoreSparseVectorList,Contains)475 TEST(CoreSparseVectorList, Contains) {
476 Apto::List<int, Apto::SparseVector> list;
477 list.Push(5);
478 list.Push(10);
479 list.Push(15);
480 EXPECT_TRUE(list.Contains(10));
481 EXPECT_FALSE(list.Contains(20));
482 }
483
484
TEST(CoreSparseVectorList,Iterators)485 TEST(CoreSparseVectorList, Iterators) {
486 Apto::List<int, Apto::SparseVector> list;
487 for (int i = 0; i < 5; i++) list.PushRear(i);
488
489 Apto::List<int, Apto::SparseVector>::Iterator it = list.Begin();
490 int i = 0;
491 while (it.Next()) {
492 EXPECT_EQ(i, *it.Get());
493 i++;
494 }
495
496 const Apto::List<int, Apto::SparseVector>& const_list = list;
497 Apto::List<int, Apto::SparseVector>::ConstIterator cit = const_list.Begin();
498 i = 0;
499 while (cit.Next()) {
500 EXPECT_EQ(i, *cit.Get());
501 i++;
502 }
503 }
504
505
TEST(CoreSparseVectorList,Comparison)506 TEST(CoreSparseVectorList, Comparison) {
507 Apto::List<int, Apto::SparseVector> list1;
508 for (int i = 0; i < 3; i++) list1.PushRear(i);
509
510 Apto::List<int, Apto::SparseVector> list2(list1);
511 list2.GetLast() = 5;
512
513 EXPECT_TRUE(list1 == list1);
514 EXPECT_TRUE(list2 == list2);
515 EXPECT_TRUE(list1 != list2);
516 EXPECT_FALSE(list1 == list2);
517 EXPECT_FALSE(list1 != list1);
518 EXPECT_FALSE(list2 != list2);
519 }
520
521
TEST(CoreSparseVectorList,Concatenation)522 TEST(CoreSparseVectorList, Concatenation) {
523 Apto::List<int, Apto::SparseVector> list1;
524 for (int i = 0; i < 3; i++) list1.PushRear(i);
525
526
527 Apto::List<int, Apto::SparseVector> list2;
528 list2.PushRear(5);
529
530 list2 += list2;
531 EXPECT_EQ(2, list2.GetSize());
532 EXPECT_EQ(5, list2.GetFirst());
533 EXPECT_EQ(5, list2.GetLast());
534
535 list1 += list2;
536
537 EXPECT_EQ(0, list1.Pop());
538 EXPECT_EQ(1, list1.Pop());
539 EXPECT_EQ(2, list1.Pop());
540 EXPECT_EQ(5, list1.Pop());
541 EXPECT_EQ(5, list1.Pop());
542
543 list2.PushRear(6);
544 Apto::List<int, Apto::SparseVector> list3 = list2 + list2;
545 EXPECT_EQ(6, list3.GetSize());
546 EXPECT_EQ(5, list3.GetFirst());
547 EXPECT_EQ(6, list3.GetLast());
548
549 list2 = list2 + list2;
550 EXPECT_TRUE(list2 == list3);
551 }
552