1144 lines
32 KiB
C++
1144 lines
32 KiB
C++
#include "ZUnitTest.hpp"
|
|
|
|
#include <ZSTL/ZListAlgo.hpp>
|
|
|
|
static const char* test_Append();
|
|
static const char* test_Append_Region();
|
|
static const char* test_Concatenate();
|
|
static const char* test_Concatenate_In_Region();
|
|
static const char* test_Contains();
|
|
static const char* test_Contains_In_Region();
|
|
static const char* test_Count();
|
|
static const char* test_Count_In_Region();
|
|
static const char* test_Excise();
|
|
static const char* test_FindFirst();
|
|
static const char* test_FirstOf_In_Region();
|
|
static const char* test_FirstNotOf();
|
|
static const char* test_FirstNotOf_In_Region();
|
|
static const char* test_Prepend();
|
|
static const char* test_Prepend_Region();
|
|
static const char* test_Remove();
|
|
static const char* test_Remove_In_Region();
|
|
static const char* test_RemoveAll();
|
|
static const char* test_RemoveAll_In_Region();
|
|
static const char* test_Reverse();
|
|
static const char* test_Reverse_In_Region();
|
|
static const char* test_ReverseNodes();
|
|
static const char* test_ReverseNodes_In_Region();
|
|
static const char* test_Slice();
|
|
static const char* test_Sort();
|
|
static const char* test_Sort_Region();
|
|
static const char* test_Sort_Comparator();
|
|
static const char* test_Sort_Comparator_Algorithm();
|
|
static const char* test_Sort_Comparator_Algorithm_Range();
|
|
static const char* test_Split();
|
|
static const char* test_SwapElements();
|
|
|
|
//List of unit tests
|
|
ZUnitTest ZListAlgoUnitTests[] =
|
|
{
|
|
{ "Append", test_Append },
|
|
{ "Append region", test_Append_Region},
|
|
{ "Concatenate", test_Concatenate },
|
|
{ "Concatenate in region", test_Concatenate_In_Region },
|
|
{ "Contains", test_Contains },
|
|
{ "Contains in region", test_Contains_In_Region },
|
|
{ "Count", test_Count },
|
|
{ "Count in region", test_Count_In_Region },
|
|
{ "Excise", test_Excise },
|
|
{ "FindFirstOf", test_FindFirst },
|
|
{ "FindFirstOf in region", test_FirstOf_In_Region },
|
|
{ "FirstNotOf", test_FirstNotOf },
|
|
{ "FirstNotOf in region", test_FirstNotOf_In_Region },
|
|
{ "Prepend", test_Prepend },
|
|
{ "Prepend region", test_Prepend_Region },
|
|
{ "Remove", test_Remove },
|
|
{ "Remove in region", test_Remove_In_Region },
|
|
{ "RemoveAll", test_RemoveAll },
|
|
{ "RemoveAll in region", test_RemoveAll_In_Region },
|
|
{ "Reverse", test_Reverse },
|
|
{ "Reverse in region", test_Reverse_In_Region },
|
|
{ "ReverseNodes", test_ReverseNodes },
|
|
{ "ReverseNodes in region", test_ReverseNodes_In_Region },
|
|
{ "Slice", test_Slice },
|
|
{ "Sort", test_Sort },
|
|
{ "Sort region", test_Sort_Region },
|
|
{ "Sort comparator", test_Sort_Comparator },
|
|
{ "Sort comparator algorithm", test_Sort_Comparator_Algorithm },
|
|
{ "Sort comparator algorithm region", test_Sort_Comparator_Algorithm_Range },
|
|
{ "Split", test_Split },
|
|
{ "SwapElements", test_SwapElements }
|
|
};
|
|
|
|
//Now declare the ZUnitTestBlock associated with this.
|
|
DECLARE_ZTESTBLOCK(ZListAlgo);
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Append()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int> list2;
|
|
int temp = -1;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
|
|
list2.PushBack(4);
|
|
list2.PushBack(5);
|
|
|
|
ZListAlgo::Append(list,list2);
|
|
TASSERT( list.Size() == 5, "Append() failed to create list of proper size!\n");
|
|
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 1, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 2, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 3, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 4, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 5, "Append() corrupted list!\n");
|
|
|
|
TASSERT( list.Size() == 0, "Append() somehow made excessively long list!");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Append_Region()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int> list2;
|
|
int temp = -1;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
|
|
list2.PushBack(4);
|
|
list2.PushBack(5);
|
|
list2.PushBack(6);
|
|
list2.PushBack(7);
|
|
list2.PushBack(8);
|
|
|
|
ZListAlgo::Append(list,list2, list2.At(2), list2.End());
|
|
TASSERT( list.Size() == 6, "Append() failed to create list of proper size!\n");
|
|
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 1, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 2, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 3, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 6, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 7, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 8, "Append() corrupted list!\n");
|
|
|
|
TASSERT( list.Size() == 0, "Append() somehow made excessively long list!");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Concatenate()
|
|
{
|
|
ZList<int> list1;
|
|
ZList<int> list2;
|
|
|
|
list1.PushBack(1);
|
|
list1.PushBack(2);
|
|
list1.PushBack(3);
|
|
list1.PushBack(4);
|
|
|
|
list2.PushBack(5);
|
|
list2.PushBack(6);
|
|
list2.PushBack(7);
|
|
list2.PushBack(8);
|
|
|
|
ZList<int> test = ZListAlgo::Concatenate(list1, list2);
|
|
|
|
TASSERT( test.Size() == 8, "Concatenate() output list shorter than sum of input lists!\n");
|
|
|
|
TASSERT( test.PopFront() == 1, "Concatenate() created wrong list!\n");
|
|
TASSERT( test.PopFront() == 2, "Concatenate() created wrong list!\n");
|
|
TASSERT( test.PopFront() == 3, "Concatenate() created wrong list!\n");
|
|
TASSERT( test.PopFront() == 4, "Concatenate() created wrong list!\n");
|
|
TASSERT( test.PopFront() == 5, "Concatenate() created wrong list!\n");
|
|
TASSERT( test.PopFront() == 6, "Concatenate() created wrong list!\n");
|
|
TASSERT( test.PopFront() == 7, "Concatenate() created wrong list!\n");
|
|
TASSERT( test.PopFront() == 8, "Concatenate() created wrong list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Concatenate_In_Region()
|
|
{
|
|
ZList<int> list1;
|
|
ZList<int> list2;
|
|
|
|
list1.PushBack(1);
|
|
list1.PushBack(2);
|
|
list1.PushBack(3);
|
|
list1.PushBack(4);
|
|
|
|
list2.PushBack(5);
|
|
list2.PushBack(6);
|
|
list2.PushBack(7);
|
|
list2.PushBack(8);
|
|
|
|
ZList<int> test = ZListAlgo::Concatenate(list1, list1.At(1), list1.At(3),
|
|
list2, list2.At(1), list2.At(3));
|
|
|
|
TASSERT( test.Size() == 4, "Concatenate() output list shorter than sum of input lists!\n");
|
|
|
|
TASSERT( test.PopFront() == 2, "Concatenate() created wrong list!\n");
|
|
TASSERT( test.PopFront() == 3, "Concatenate() created wrong list!\n");
|
|
TASSERT( test.PopFront() == 6, "Concatenate() created wrong list!\n");
|
|
TASSERT( test.PopFront() == 7, "Concatenate() created wrong list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Contains()
|
|
{
|
|
ZList<int> list;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
|
|
TASSERT( ZListAlgo::Contains(list, 1) == true, "Contains() failed to find present value!\n");
|
|
TASSERT( ZListAlgo::Contains(list, 2) == true, "Contains() failed to find present value!\n");
|
|
TASSERT( ZListAlgo::Contains(list, 3) == true, "Contains() failed to find present value!\n");
|
|
|
|
TASSERT( ZListAlgo::Contains(list, 4) == false, "Contains() successfully found missing value!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Contains_In_Region()
|
|
{
|
|
ZList<int> list;
|
|
ZListIterator<int> goodStartItr;
|
|
ZListIterator<int> goodEndItr;
|
|
|
|
ZListIterator<int> badStartItr;
|
|
ZListIterator<int> badEndItr;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
list.PushBack(4);
|
|
list.PushBack(5);
|
|
list.PushBack(6);
|
|
|
|
goodStartItr = list.At(2); // will point at 3
|
|
goodEndItr = list.At(4); // will point at 5
|
|
|
|
TASSERT( ZListAlgo::Contains(list, 1, goodStartItr, goodEndItr) == false, "Contains() sucessfully found missing value!\n");
|
|
TASSERT( ZListAlgo::Contains(list, 2, goodStartItr, goodEndItr) == false, "Contains() sucessfully found missing value!\n");
|
|
TASSERT( ZListAlgo::Contains(list, 3, goodStartItr, goodEndItr) == true, "Contains() failed to find value at inclusive endpoint!\n");
|
|
TASSERT( ZListAlgo::Contains(list, 4, goodStartItr, goodEndItr) == true, "Contains() failed to find value!\n");
|
|
TASSERT( ZListAlgo::Contains(list, 5, goodStartItr, goodEndItr) == false, "Contains() accidentally included exclusive endpoint!\n");
|
|
TASSERT( ZListAlgo::Contains(list, 6, goodStartItr, goodEndItr) == false, "Contains()sucessfully found missing value!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Count()
|
|
{
|
|
ZList<int> list;
|
|
|
|
//Fill list with 5 items and check for
|
|
for(int i=0; i<5; i++)
|
|
list.PushBack(1);
|
|
list.PushBack(2); //These add a bit of extra stuff to compare against
|
|
list.PushBack(3);
|
|
TASSERT(ZListAlgo::Count(list, 1) == 5, "Count() gave wrong number of items, should be 5");
|
|
|
|
//Remove 1 item from the front of the list
|
|
list.PopFront();
|
|
TASSERT( ZListAlgo::Count(list, 1) == 4, "Count() gave wrong number of items, should be 4");
|
|
|
|
//Empty the list
|
|
list.Clear();
|
|
TASSERT( ZListAlgo::Count(list, 1) == 0, "Count() gave wrong number of items, should be 0");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Count_In_Region()
|
|
{
|
|
ZList<int> list;
|
|
list.PushBack(3); //0
|
|
list.PushBack(2); //1
|
|
list.PushBack(3); //2
|
|
list.PushBack(3); //3
|
|
list.PushBack(1); //4
|
|
list.PushBack(6); //5
|
|
list.PushBack(3); //6
|
|
list.PushBack(8); //7
|
|
list.PushBack(1); //8
|
|
|
|
ZListIterator<int> start = list.At(3);
|
|
ZListIterator<int> end = list.At(7);
|
|
|
|
TASSERT( ZListAlgo::Count(list, 3, start, end) == 2, "Count() miscounted occurences in region!\n");
|
|
TASSERT( ZListAlgo::Count(list, 8, start, end) == 0, "Count() found element out of range!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Excise()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int> excise;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
list.PushBack(4);
|
|
list.PushBack(5);
|
|
list.PushBack(6);
|
|
|
|
ZListIterator<int> start = list.At(1); // points at 2
|
|
ZListIterator<int> end = list.At(4); // points at 5
|
|
excise = ZListAlgo::Excise(list,start,end);
|
|
|
|
TASSERT( list.Size() == 3, "Slice() mutated target list to incorrect size!\n");
|
|
TASSERT( excise.Size() == 3, "Slice() produced list of incorrect size!\n");
|
|
|
|
// check remainder
|
|
TASSERT( list.PopFront() == 1, "Slice() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 5, "Slice() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 6, "Slice() produced bad list!\n");
|
|
|
|
// check excised bit
|
|
TASSERT( excise.PopFront() == 2, "Slice() produced bad list!\n");
|
|
TASSERT( excise.PopFront() == 3, "Slice() produced bad list!\n");
|
|
TASSERT( excise.PopFront() == 4, "Slice() produced bad list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_FindFirst()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int>::Iterator it;
|
|
int i;
|
|
|
|
//Add 0-9
|
|
for(i=0; i<10; i++)
|
|
list.PushBack(i);
|
|
|
|
list.PushBack(1000);
|
|
|
|
//Find the element with the value '5'
|
|
it = ZListAlgo::FindFirst(list, 5);
|
|
if(it == list.End())
|
|
return "Find(5) could not find element known to exist";
|
|
if(*it != 5)
|
|
return "Find(5) found the wrong element";
|
|
|
|
//Find an element that does not exist
|
|
it = ZListAlgo::FindFirst(list, (int)0xdeadc0de);
|
|
if(it != list.End())
|
|
return "Find() erroneously found element known NOT to exist";
|
|
|
|
//Find an element 1000, then remove it
|
|
it = ZListAlgo::FindFirst(list, 1000);
|
|
if(it == list.End())
|
|
return "Find(1000) could not find element known to exist";
|
|
if(*it != 1000)
|
|
return "Find(1000) found the wrong element";
|
|
list.Erase(it);
|
|
|
|
//Now try to find it
|
|
it = ZListAlgo::FindFirst(list, 1000);
|
|
if(it != list.End())
|
|
return "Find(1000) erroneously found element known NOT to exist";
|
|
|
|
list.Clear();
|
|
|
|
ZListIterator<int> good;
|
|
ZListIterator<int> temp;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
list.PushBack(4);
|
|
list.PushBack(7);
|
|
list.PushBack(8);
|
|
|
|
good = list.At(1); // points at the first 2
|
|
|
|
// test whole-list ones
|
|
temp = ZListAlgo::FindFirst(list, 2);
|
|
|
|
TASSERT( temp == good, "FirstOf() misplaced element in list!\n");
|
|
|
|
temp = ZListAlgo::FindFirst(list, 5);
|
|
|
|
TASSERT( temp == list.End(), "FirstOf() returned good position to missing element!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_FirstOf_In_Region()
|
|
{
|
|
ZList<int> list;
|
|
ZListIterator<int> firstItr;
|
|
ZListIterator<int> badItr;
|
|
ZListIterator<int> start;
|
|
ZListIterator<int> end;
|
|
ZListIterator<int> good;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
list.PushBack(4);
|
|
list.PushBack(7);
|
|
list.PushBack(8);
|
|
|
|
firstItr = list.At(1);
|
|
badItr = list.End();
|
|
start = list.At(2); // points at second 2
|
|
end = list.At(5); // points at 7
|
|
good = list.At(4); // points at 4
|
|
|
|
// test whole-list ones
|
|
TASSERT( ZListAlgo::FindFirst(list, 2, list.Begin(), list.End()) == firstItr, "FirstOf() misplaced element in list!\n");
|
|
TASSERT( ZListAlgo::FindFirst(list, 5, list.Begin(), list.End()) == badItr, "FirstOf() returned good position to missing element!\n");
|
|
|
|
TASSERT( ZListAlgo::FindFirst(list, 4, start, end) == good, "FirstOf() misplaced element in list!\n");
|
|
TASSERT( ZListAlgo::FindFirst(list, 7, start, end) == list.End(), "FirstOf() returned good position to out-of-bounds element!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_FirstNotOf()
|
|
{
|
|
ZList<int> list;
|
|
ZListIterator<int> good;
|
|
ZListIterator<int> temp;
|
|
|
|
list.PushBack(2);
|
|
list.PushBack(2);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
list.PushBack(4);
|
|
|
|
good = list.At(3); // points at the 3
|
|
temp = ZListAlgo::FirstNotOf(list, 2);
|
|
TASSERT( temp == good, "FirstNotOf() misplaced element in list!\n");
|
|
|
|
good = list.Begin(); // points at first element in list (a 2, which is not a 3)
|
|
temp = ZListAlgo::FirstNotOf(list, 3);
|
|
TASSERT( temp == good, "FirstNotOf() misplaced element in list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_FirstNotOf_In_Region()
|
|
{
|
|
ZList<int> list;
|
|
ZListIterator<int> good;
|
|
ZListIterator<int> temp;
|
|
ZListIterator<int> start;
|
|
ZListIterator<int> end;
|
|
|
|
list.PushBack(2);
|
|
list.PushBack(2);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
list.PushBack(4);
|
|
list.PushBack(5);
|
|
list.PushBack(6);
|
|
|
|
good = list.At(3); // points at the 3
|
|
start = list.At(1); // points at the second 2
|
|
end = list.At(4); // points at the 4
|
|
temp = ZListAlgo::FirstNotOf(list, 2, start, end);
|
|
TASSERT( temp == good, "FirstNotOf() misplaced element in list!\n");
|
|
|
|
good = list.At(1); // points at the second 2
|
|
temp = ZListAlgo::FirstNotOf(list, 3, start, end);
|
|
TASSERT( temp == good, "FirstNotOf() misplaced element in list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Prepend()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int> list2;
|
|
int temp = -1;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
|
|
list2.PushBack(4);
|
|
list2.PushBack(5);
|
|
|
|
ZListAlgo::Prepend(list,list2);
|
|
TASSERT( list.Size() == 5, "Append() failed to create list of proper size!\n");
|
|
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 4, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 5, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 1, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 2, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 3, "Append() corrupted list!\n");
|
|
|
|
TASSERT( list.Size() == 0, "Append() somehow made excessively long list!");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Prepend_Region()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int> list2;
|
|
int temp = -1;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
|
|
list2.PushBack(4);
|
|
list2.PushBack(5);
|
|
list2.PushBack(6);
|
|
list2.PushBack(7);
|
|
list2.PushBack(8);
|
|
|
|
ZListAlgo::Prepend(list,list2, list2.At(2), list2.End());
|
|
TASSERT( list.Size() == 6, "Append() failed to create list of proper size!\n");
|
|
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 6, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 7, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 8, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 1, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 2, "Append() corrupted list!\n");
|
|
temp = list.PopFront();
|
|
TASSERT( temp == 3, "Append() corrupted list!\n");
|
|
|
|
TASSERT( list.Size() == 0, "Append() somehow made excessively long list!");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Remove()
|
|
{
|
|
ZList<int> list;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
list.PushBack(3);
|
|
list.PushBack(4);
|
|
list.PushBack(5);
|
|
|
|
ZListIterator<int> a = list.At(3);
|
|
ZListIterator<int> b = list.At(4);
|
|
|
|
ZListIterator<int> ap = ZListAlgo::Remove(list, 3);
|
|
TASSERT( list.Size() == 5, "Remove() failed to produce list of correct size!\n");
|
|
TASSERT( ap == a, "Remove() returned incorrect iterator!\n");
|
|
ZListIterator<int> bp = ZListAlgo::Remove(list, 3);
|
|
TASSERT( list.Size() == 4, "Remove() failed to produce list of correct size!\n");
|
|
TASSERT( bp == b, "Remove() returned incorrect iterator!\n");
|
|
TASSERT( list.PopFront() == 1, "Remove() produced incorrect list!\n");
|
|
TASSERT( list.PopFront() == 2, "Remove() produced incorrect list!\n");
|
|
TASSERT( list.PopFront() == 4, "Remove() produced incorrect list!\n");
|
|
TASSERT( list.PopFront() == 5, "Remove() produced incorrect list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Remove_In_Region()
|
|
{
|
|
ZList<int> list;
|
|
|
|
list.PushBack(1); // 0
|
|
list.PushBack(2); // 1
|
|
list.PushBack(3); // 2
|
|
list.PushBack(3); // 3
|
|
list.PushBack(4); // 4
|
|
list.PushBack(5); // 5
|
|
|
|
ZListIterator<int> start = list.At(3);
|
|
ZListIterator<int> end = list.At(list.Size());
|
|
|
|
ZListAlgo::Remove(list, 3, start, end);
|
|
TASSERT( list.Size() == 5, "Remove() failed to produce list of correct size!\n");
|
|
|
|
start = list.At(3);
|
|
end = list.At(list.Size());
|
|
ZListAlgo::Remove(list, 3, start, end);
|
|
TASSERT( list.Size() == 5, "Remove() removed element outstide of valid range!\n");
|
|
|
|
start = list.At(3);
|
|
end = list.At(list.Size());
|
|
ZListAlgo::Remove(list, 1, start, end);
|
|
TASSERT( list.Size() == 5, "Remove() removed element outside of valid range!\n");
|
|
TASSERT( list.PopFront() == 1, "Remove() produced incorrect list!\n");
|
|
TASSERT( list.PopFront() == 2, "Remove() produced incorrect list!\n");
|
|
TASSERT( list.PopFront() == 3, "Remove() produced incorrect list!\n");
|
|
TASSERT( list.PopFront() == 4, "Remove() produced incorrect list!\n");
|
|
TASSERT( list.PopFront() == 5, "Remove() produced incorrect list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_RemoveAll()
|
|
{
|
|
ZList<int> list;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(1);
|
|
list.PushBack(3);
|
|
list.PushBack(2);
|
|
list.PushBack(2);
|
|
list.PushBack(1);
|
|
|
|
ZListAlgo::RemoveAll(list, 2);
|
|
|
|
TASSERT( list.Size() == 4, "RemoveAll() produced list of incorrect size!\n");
|
|
|
|
TASSERT( list.PopFront() == 1, "RemoveAll() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 1, "RemoveAll() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 3, "RemoveAll() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 1, "RemoveAll() produced bad list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_RemoveAll_In_Region()
|
|
{
|
|
ZList<int> list;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(1);
|
|
list.PushBack(3);
|
|
list.PushBack(2);
|
|
list.PushBack(2);
|
|
list.PushBack(1);
|
|
|
|
ZListIterator<int> start = list.At(2);
|
|
ZListIterator<int> end = list.At(5);
|
|
|
|
ZListAlgo::RemoveAll(list, 2, start, end);
|
|
|
|
TASSERT( list.Size() == 6, "RemoveAll() produced list of incorrect size!\n");
|
|
|
|
TASSERT( list.PopFront() == 1, "RemoveAll() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 2, "RemoveAll() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 1, "RemoveAll() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 3, "RemoveAll() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 2, "RemoveAll() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 1, "RemoveAll() produced bad list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Reverse()
|
|
{
|
|
ZList<int> list;
|
|
|
|
// test list with odd number of elements
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
list.PushBack(4);
|
|
list.PushBack(5);
|
|
ZListAlgo::Reverse(list);
|
|
TASSERT( list.Size() == 5, "Reverse() produced list of incorrect size!\n");
|
|
TASSERT( list.PopFront() == 5, "Reverse() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 4, "Reverse() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 3, "Reverse() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 2, "Reverse() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 1, "Reverse() produced bad list!\n");
|
|
|
|
// test list with even number of elements
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
list.PushBack(4);
|
|
ZListAlgo::Reverse(list);
|
|
TASSERT( list.Size() == 4, "Reverse() produced list of incorrect size!\n");
|
|
TASSERT( list.PopFront() == 4, "Reverse() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 3, "Reverse() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 2, "Reverse() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 1, "Reverse() produced bad list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Reverse_In_Region()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int> list2;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
list.PushBack(4);
|
|
list.PushBack(5);
|
|
list.PushBack(6);
|
|
|
|
ZListIterator<int> start = list.At(1);
|
|
ZListIterator<int> end = list.At(4);
|
|
|
|
ZListAlgo::Reverse(list, start, end);
|
|
|
|
TASSERT( list.Size() == 6, "Reverse() produced list of incorrect size!\n");
|
|
|
|
// store a copy for later testing
|
|
list2 = list;
|
|
|
|
TASSERT( list.PopFront() == 1, "Reverse() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 4, "Reverse() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 3, "Reverse() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 2, "Reverse() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 5, "Reverse() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 6, "Reverse() produced bad list!\n");
|
|
|
|
// second batch is to make sure the list can be reverse iterated too
|
|
TASSERT( list2.PopBack() == 6, "Reverse() produced bad list!\n");
|
|
TASSERT( list2.PopBack() == 5, "Reverse() produced bad list!\n");
|
|
TASSERT( list2.PopBack() == 2, "Reverse() produced bad list!\n");
|
|
TASSERT( list2.PopBack() == 3, "Reverse() produced bad list!\n");
|
|
TASSERT( list2.PopBack() == 4, "Reverse() produced bad list!\n");
|
|
TASSERT( list2.PopBack() == 1, "Reverse() produced bad list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_ReverseNodes()
|
|
{
|
|
ZList<int> list;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
list.PushBack(4);
|
|
|
|
ZListAlgo::ReverseNodes(list);
|
|
|
|
TASSERT( list.Size() == 4, "ReverseNodes() produced list of incorrect size!\n");
|
|
|
|
TASSERT( list.PopFront() == 4, "ReverseNodes() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 3, "ReverseNodes() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 2, "ReverseNodes() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 1, "ReverseNodes() produced bad list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_ReverseNodes_In_Region()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int> list2;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
list.PushBack(4);
|
|
list.PushBack(5);
|
|
list.PushBack(6);
|
|
|
|
ZListIterator<int> start = list.At(1);
|
|
ZListIterator<int> end = list.At(4);
|
|
|
|
ZListAlgo::ReverseNodes(list, start, end);
|
|
|
|
TASSERT( list.Size() == 6, "ReverseNodes() produced list of incorrect size!\n");
|
|
|
|
// store a copy for later testing
|
|
list2 = list;
|
|
|
|
TASSERT( list.PopFront() == 1, "ReverseNodes() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 4, "ReverseNodes() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 3, "ReverseNodes() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 2, "ReverseNodes() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 5, "ReverseNodes() produced bad list!\n");
|
|
TASSERT( list.PopFront() == 6, "ReverseNodes() produced bad list!\n");
|
|
|
|
// second batch is to make sure the list can be reverse iterated too
|
|
TASSERT( list2.PopBack() == 6, "ReverseNodes() produced bad list!\n");
|
|
TASSERT( list2.PopBack() == 5, "ReverseNodes() produced bad list!\n");
|
|
TASSERT( list2.PopBack() == 2, "ReverseNodes() produced bad list!\n");
|
|
TASSERT( list2.PopBack() == 3, "ReverseNodes() produced bad list!\n");
|
|
TASSERT( list2.PopBack() == 4, "ReverseNodes() produced bad list!\n");
|
|
TASSERT( list2.PopBack() == 1, "ReverseNodes() produced bad list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Slice()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int> slice;
|
|
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(3);
|
|
list.PushBack(4);
|
|
list.PushBack(5);
|
|
list.PushBack(6);
|
|
|
|
ZListIterator<int> start = list.At(1); // points at 2
|
|
ZListIterator<int> end = list.At(4); // points at 5
|
|
slice = ZListAlgo::Slice(list,start,end);
|
|
|
|
TASSERT( list.Size() == 6, "Slice() mutated target list to incorrect size!\n");
|
|
TASSERT( slice.Size() == 3, "Slice() produced list of incorrect size!\n");
|
|
|
|
TASSERT( slice.PopFront() == 2, "Slice() produced bad list!\n");
|
|
TASSERT( slice.PopFront() == 3, "Slice() produced bad list!\n");
|
|
TASSERT( slice.PopFront() == 4, "Slice() produced bad list!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Sort()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int>::Iterator it;
|
|
int i;
|
|
int min;
|
|
|
|
srand(0xdeadc0de);
|
|
|
|
//Add 100 random integers
|
|
for(i=0; i<100; i++)
|
|
list.PushBack( rand() % 128 );
|
|
|
|
//Sort
|
|
ZListAlgo::Sort(list);
|
|
|
|
if(list.Size() != 100)
|
|
return "Sort() lost elements";
|
|
|
|
//Make sure it is monotonically increasing
|
|
for(it=list.Begin(), min = *it; it != list.End(); it++)
|
|
{
|
|
if(min > (*it))
|
|
return "Found element out of place after Sort()";
|
|
|
|
min = *it;
|
|
}
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Sort_Region()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int>::Iterator it;
|
|
ZListIterator<int> start;
|
|
ZListIterator<int> end;
|
|
int i, min;
|
|
|
|
srand(0xdeadc0de);
|
|
|
|
//Add 100 random integers
|
|
list.PushBack(998);
|
|
list.PushBack(999);
|
|
for(i=0; i<100; i++)
|
|
{
|
|
list.PushBack( rand() % 128 );
|
|
}
|
|
list.PushBack(1);
|
|
start = list.At(2);
|
|
end = list.At(list.Size()-1);
|
|
|
|
//Sort
|
|
ZListAlgo::Sort(list,start,end);
|
|
|
|
if(list.Size() != 103)
|
|
return "Sort() lost elements";
|
|
|
|
//Make sure the front wasn't moved
|
|
TASSERT(list.PopFront() == 998, "Sort() in region touched outside given bounds!\n");
|
|
TASSERT(list.PopFront() == 999, "Sort() in region touched outside given bounds!\n");
|
|
|
|
//Make sure it is monotonically increasing
|
|
min = -1;
|
|
int temp;
|
|
for(i=0; i<100; i++)
|
|
{
|
|
temp = list.PopFront();
|
|
TASSERT(temp >= min, "Found element out of place after Sort()!\n");
|
|
min = temp;
|
|
}
|
|
|
|
//Make sure the back wasn't moved
|
|
TASSERT(list.PopFront() == 1, "Sort() in region touched outside given bounds!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Sort_Comparator()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int>::Iterator it;
|
|
int i, min;
|
|
|
|
srand(0xdeadc0de);
|
|
|
|
//Add 100 random integers
|
|
for(i=0; i<100; i++)
|
|
list.PushBack( rand() % 128 );
|
|
|
|
//Sort
|
|
ZListAlgo::Sort(list, ZComparator<int>());
|
|
|
|
if(list.Size() != 100)
|
|
return "Sort() lost elements";
|
|
|
|
//Make sure it is monotonically increasing
|
|
for(it=list.Begin(), min = *it; it != list.End(); it++)
|
|
{
|
|
if(min > (*it))
|
|
return "Found element out of place after Sort()";
|
|
|
|
min = *it;
|
|
}
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Sort_Comparator_Algorithm()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int>::Iterator it;
|
|
int i, min;
|
|
|
|
srand(0xdeadc0de);
|
|
|
|
//Add 100 random integers
|
|
for(i=0; i<100; i++)
|
|
list.PushBack( rand() % 128 );
|
|
|
|
//Sort
|
|
ZListAlgo::Sort(list, ZComparator<int>(), ZListMergeSort<int>());
|
|
|
|
if(list.Size() != 100)
|
|
return "Sort() lost elements";
|
|
|
|
//Make sure it is monotonically increasing
|
|
for(it=list.Begin(), min = *it; it != list.End(); it++)
|
|
{
|
|
if(min > (*it))
|
|
return "Found element out of place after Sort()";
|
|
|
|
min = *it;
|
|
}
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Sort_Comparator_Algorithm_Range()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int>::Iterator it;
|
|
ZListIterator<int> start;
|
|
ZListIterator<int> end;
|
|
int i, min;
|
|
|
|
srand(0xdeadc0de);
|
|
|
|
//Add 100 random integers
|
|
list.PushBack(998);
|
|
list.PushBack(999);
|
|
for(i=0; i<100; i++)
|
|
{
|
|
list.PushBack( rand() % 128 );
|
|
}
|
|
list.PushBack(1);
|
|
start = list.At(2);
|
|
end = list.At(list.Size()-1);
|
|
|
|
//Sort
|
|
ZListAlgo::Sort(list, ZComparator<int>(), ZListMergeSort<int>(), start,end);
|
|
|
|
if(list.Size() != 103)
|
|
return "Sort() lost elements";
|
|
|
|
//Make sure the front wasn't moved
|
|
TASSERT(list.PopFront() == 998, "Sort() in region touched outside given bounds!\n");
|
|
TASSERT(list.PopFront() == 999, "Sort() in region touched outside given bounds!\n");
|
|
|
|
//Make sure it is monotonically increasing
|
|
min = -1;
|
|
int temp;
|
|
for(i=0; i<100; i++)
|
|
{
|
|
temp = list.PopFront();
|
|
TASSERT(temp >= min, "Found element out of place after Sort()!\n");
|
|
min = temp;
|
|
}
|
|
|
|
//Make sure the back wasn't moved
|
|
TASSERT(list.PopFront() == 1, "Sort() in region touched outside given bounds!\n");
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_Split()
|
|
{
|
|
ZList<int> list1, list2;
|
|
ZList<int>::Iterator it;
|
|
int i;
|
|
|
|
//list1 = 1, 2, 3, 4, 5
|
|
list1.Clear();
|
|
|
|
for(i = 0; i < 5; i++)
|
|
list1.PushBack(i + 1);
|
|
|
|
//Test inclusion into secondary list
|
|
it = ZListAlgo::FindFirst(list1, 3);
|
|
|
|
list2 = ZListAlgo::Split(list1, it);
|
|
|
|
if(list1.Size() != 2)
|
|
return "List 1 after split is wrong size";
|
|
if(list2.Size() != 3)
|
|
return "List 2 after split is wrong size";
|
|
if(list1.Front() != 1)
|
|
return "List 1 has wrong front value after split";
|
|
if(list1.Back() != 2)
|
|
return "List 1 has wrong back value after split";
|
|
if(list2.Front() != 3)
|
|
return "List 2 has wrong front value after split";
|
|
if(list2.Back() != 5)
|
|
return "List 2 has wrong back value after split";
|
|
|
|
return ZTEST_SUCCESS;
|
|
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
static const char* test_SwapElements()
|
|
{
|
|
ZList<int> list;
|
|
ZList<int>::Iterator e1, e2, it;
|
|
int i;
|
|
|
|
//Create list: 1,2,5,4,3
|
|
//We'll swap 3 & 5 to create: 1,2,3,4,5
|
|
list.PushBack(1);
|
|
list.PushBack(2);
|
|
list.PushBack(5);
|
|
list.PushBack(4);
|
|
list.PushBack(3);
|
|
|
|
//Find elements 3 and 5
|
|
e1 = ZListAlgo::FindFirst(list, 5);
|
|
e2 = ZListAlgo::FindFirst(list, 3);
|
|
|
|
//Swap them
|
|
ZListAlgo::SwapElements(list, e1, e2);
|
|
|
|
//Verify swap worked, since now they will be sorted
|
|
for(i=1, it=list.Begin(); it != list.End(); it++, i++)
|
|
{
|
|
if((*it) != i)
|
|
return "SwapElements() did not correctly the elements";
|
|
}
|
|
|
|
//Try making a list of two elements and swapping them (i.e. swapping front and back)
|
|
list.Clear();
|
|
list.PushBack(100);
|
|
list.PushBack(200);
|
|
e1 = ZListAlgo::FindFirst(list, 100);
|
|
e2 = ZListAlgo::FindFirst(list, 200);
|
|
ZListAlgo::SwapElements(list, e1, e2);
|
|
|
|
if(list.Front() != 200)
|
|
return "SwapElements() did not correctly swap front and back elements";
|
|
if(list.Back() != 100)
|
|
return "SwapElements() did not correctly swap front and back elements";
|
|
|
|
return ZTEST_SUCCESS;
|
|
}
|