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