Permalink
Cannot retrieve contributors at this time
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
yasi/YASI_12/ds.doublylinkedlist.test.h
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
749 lines (647 sloc)
34.2 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #pragma once | |
| #if YASI_TEST_THIS_MODULE != 1 | |
| #define YASI_TEST_THIS_MODULE 1 | |
| #endif | |
| #include "ds.doublylinkedlist.h" | |
| using namespace std; | |
| namespace yasi{ | |
| namespace ds{ | |
| // test | |
| class DoublyLinkedListTest : public yasi::Test { | |
| typedef DoublyLinkedList<int, DListNode<int> >::node_t node_t; | |
| typedef DoublyLinkedList<int, DListNode<int> > IntList; | |
| typedef IntList::iterator IntIterator; | |
| protected: | |
| template<class E> | |
| void checkListElements(DoublyLinkedList<E, DListNode<E> >* pList, const E* srcArr, const int n){ | |
| E* pElems = new E[n]; | |
| DoublyLinkedList<E, DListNode<E> >& list = *pList; | |
| list.elements(&pElems); | |
| ASSERT_EQ(true, arrcmp(srcArr, pElems, n)) << "arrays are not the same" << endl | |
| << "actual: " << arrToString(srcArr, n) << endl | |
| << "expected: " << arrToString(pElems, n); | |
| DELETE_ARR_SAFE(pElems); | |
| } | |
| public: | |
| virtual void fromArray(){ | |
| IntList list; | |
| int srcArr[] = { 10, 20, 30, 40 }; | |
| int n = ARR_LENGTH(srcArr); | |
| list.fromArray(srcArr, n); // build list | |
| ASSERT_NE(0, (int)list.head()) << "head is NULL"; | |
| ASSERT_EQ(4, (int)list.size()) << "size is not 4"; | |
| int j = n - 1; | |
| for (IntIterator it = list.begin(); it != list.end(); it++){ | |
| ASSERT_EQ(srcArr[j], *it) << "element mismatch at item " << n - j - 1 << " in list"; | |
| j--; | |
| } | |
| } | |
| virtual void elements(){ | |
| IntList list; | |
| int srcArr[] = { 10, 20, 30, 40 }; | |
| int n = ARR_LENGTH(srcArr); | |
| list.fromArray(srcArr, n); // build list | |
| //ASSERT_NE(0, (int)list.head()) << "list head is NULL"; | |
| ASSERT_EQ(n, list.size()) << "list size should have been " << n; | |
| // since the elements are given in reverse order | |
| int* pRev = new int[n]; | |
| arrrev(srcArr, n, &pRev); | |
| ASSERT_NE(0, (int)pRev) << "array reverse failed"; | |
| { | |
| SCOPED_TRACE("elements"); | |
| checkListElements(&list, pRev, n); | |
| } | |
| DELETE_ARR_SAFE(pRev); | |
| } | |
| void relements(){ | |
| IntList list; | |
| int srcArr[] = { 10, 20, 30, 40 }; | |
| const int n = ARR_LENGTH(srcArr); | |
| list.fromArray(srcArr, n); // build list | |
| ASSERT_EQ(n, list.size()) << "list size should have been " << n; | |
| int* pRelems = new int[n]; | |
| list.relements(&pRelems); | |
| // pRelems should be in the same order as srcArr | |
| ASSERT_EQ(true, arrcmp(srcArr, pRelems, n)) << "arrays are not the same" << endl | |
| << "actual: " << arrToString(pRelems, n) << endl | |
| << "expected: " << arrToString(srcArr, n); | |
| DELETE_ARR_SAFE(pRelems); | |
| } | |
| void toString(){ | |
| int srcArr[] = { 1, 2, 3, 4 }; | |
| const string expected = "4->3->2->1->"; | |
| IntList list(srcArr, ARR_LENGTH(srcArr)); | |
| string actual = list.toString(); | |
| ASSERT_EQ(expected, actual) << "toString() is wrong"; | |
| } | |
| void addFront(){ | |
| IntList list; | |
| ASSERT_EQ(0, list.size()) << "size should be zero"; | |
| ASSERT_EQ(0, (int)list.head()) << "head should be NULL"; | |
| node_t *n1, *n2, *n3; | |
| // add head | |
| { | |
| SCOPED_TRACE("add #1"); | |
| n1 = list.addFront(4); // new node is at head | |
| // list: 4 | |
| ASSERT_NE(0, (int)list.head()) << "head is NULL"; | |
| ASSERT_NE(0, (int)list.tail()) << "tail is NULL"; | |
| ASSERT_EQ(list.head(), list.tail()) << "head != tail"; | |
| ASSERT_EQ(list.head(), n1) << "addFront() does not return correct node"; | |
| ASSERT_NE(0, (int)n1) << "head is NULL although list has items"; | |
| ASSERT_EQ(list.end().pNode, n1->next()) << "head's next should be end()"; | |
| ASSERT_EQ(list.end().pNode, n1->prev()) << "head's prev should be end()"; | |
| ASSERT_EQ(1, list.size()) << "size should have been 1"; | |
| ASSERT_EQ(false, list.empty()) << "non-empty list is showing empty"; | |
| ASSERT_EQ(4, n1->element) << "head-element should have been 4"; | |
| // iterators | |
| ASSERT_EQ(list.head(), list.begin().pNode) << "head() not equal to begin().pNode"; | |
| ASSERT_EQ(list.tail(), list.begin().pNode) << "tail() not equal to begin().pNode"; | |
| ASSERT_NE(list.begin(), list.end()) << "begin() and end() same for non-empty list"; | |
| ASSERT_EQ(list.end(), ++list.begin()) << "++begin() and end() not same"; | |
| ASSERT_EQ(list.begin(), --list.end()) << "--end() and begin() not same"; | |
| ASSERT_NE(list.end(), list.begin()++) << "begin()++ and end() same"; | |
| ASSERT_NE(list.begin(), list.end()--) << "end()-- and begin() same"; | |
| ASSERT_EQ(list.head(), (list.begin()++).pNode) << "begin()++.pNode not head()"; | |
| ASSERT_EQ(list.tail(), (--list.end()).pNode) << "--end().pNode not tail()"; | |
| ASSERT_EQ(list.end().pNode, (++list.begin()).pNode) << "begin++.pNode should be end()"; | |
| ASSERT_EQ(list.begin().pNode, (--list.end()).pNode) << "--end.pNode should be begin()"; | |
| ASSERT_EQ(4, *list.begin()) << "begin()-element should have been 4"; | |
| ASSERT_EQ(4, *(--list.end())) << "--end()-element should have been 4"; | |
| } | |
| // add 2nd element | |
| { | |
| SCOPED_TRACE("add #2"); | |
| n2 = list.addFront(5); // new node is at head | |
| // list: 5->4 | |
| ASSERT_NE(0, (int)list.head()) << "head is NULL although list has items"; | |
| ASSERT_EQ(list.head(), n2) << "n2 should be head"; | |
| ASSERT_EQ(list.tail(), n1) << "n1 should be tail"; | |
| ASSERT_NE(list.end().pNode, list.head()->next()) << "head->next is end() although list has 2 items"; | |
| ASSERT_EQ(n1, list.head()->next()) << "head->next hsould be n1"; | |
| ASSERT_EQ(list.head(), n1->prev()) << "n1->prev should be head"; | |
| ASSERT_EQ(list.end().pNode, list.tail()->next()) << "tail->next should be end()"; | |
| ASSERT_EQ(list.end().pNode, n1->prev()->prev()) << "n1->perv->prev should be end()"; | |
| ASSERT_EQ(5, list.head()->element) << "head element should have been 5"; | |
| ASSERT_EQ(2, list.size()) << "size should have been 2"; | |
| ASSERT_EQ(false, list.empty()) << "non-empty list is showing empty"; | |
| ASSERT_EQ(5, list.head()->element) << "head-element should have been 5"; | |
| ASSERT_EQ(4, list.head()->next()->element) << "head->next element should have been 4"; | |
| // iterators | |
| ASSERT_EQ(list.head(), list.begin().pNode) << "head() not equal to begin().pNode"; | |
| ASSERT_EQ(list.tail(), (--(list.end())).pNode) << "tail() not equal to --end().pNode"; | |
| ASSERT_NE(list.begin(), list.end()) << "begin() and end() same for non-empty list"; | |
| ASSERT_EQ(list.end(), ++(++(list.begin()))) << "++++begin() not end()"; | |
| ASSERT_EQ(list.begin(), --(--(list.end()))) << "----end() not begin()"; | |
| ASSERT_EQ(n2, (list.begin()++).pNode) << "begin++.pNode should be n2"; | |
| ASSERT_EQ(n1, (++(list.begin())).pNode) << "++begin.pNode should be n1"; | |
| ASSERT_EQ(n2, (--(--list.end())).pNode) << "----end.pNode should be n2"; | |
| ASSERT_EQ(n1, (--(list.end())).pNode) << "--end.pNode should be n1"; | |
| ASSERT_EQ(5, *(list.begin())) << "begin()-element should have been 5"; | |
| ASSERT_EQ(4, *(++(list.begin()))) << "++begin()-element should have been 4"; | |
| ASSERT_EQ(5, *(list.begin()++)) << "begin()-element should have been 5"; | |
| ASSERT_EQ(4, *(--list.end())) << "--end()-element should have been 4"; | |
| ASSERT_EQ(5, *(--(--list.end()))) << "----end()-element should have been 5"; | |
| } | |
| // add more elements | |
| { | |
| SCOPED_TRACE("add #3"); | |
| n3 = list.addFront(6); // new node is at head | |
| // list: 6->5->4 | |
| ASSERT_NE(0, (int)list.head()) << "head is NULL although list has items"; | |
| ASSERT_NE(0, (int)list.head()->next()) << "head->next is NULL"; | |
| ASSERT_NE(0, (int)list.head()->next()->next()) << "head->next->next is NULL"; | |
| ASSERT_EQ(n3, list.head()) << "n3 should be head"; | |
| ASSERT_EQ(n1, list.tail()) << "n1 should be tail"; | |
| ASSERT_EQ(n2, list.head()->next()) << "n2 should be head->next"; | |
| ASSERT_EQ(n2, list.tail()->prev()) << "n2 should be tail->prev"; | |
| ASSERT_EQ(n3, n2->prev()) << "n3 should be n2->prev"; | |
| ASSERT_EQ(list.tail(), n2->next()) << "n2->next should be tail"; | |
| ASSERT_EQ(list.end().pNode, list.tail()->next()) << "tail->next should be end()"; | |
| ASSERT_EQ(list.end().pNode, list.head()->prev()) << "head->prev should be end()"; | |
| ASSERT_EQ(6, list.head()->element) << "head element should have been 6"; | |
| ASSERT_EQ(5, list.head()->next()->element) << "head->next element should have been 5"; | |
| ASSERT_EQ(4, list.head()->next()->next()->element) << "head->next->next element should have been 4"; | |
| ASSERT_EQ(3, list.size()) << "size should have been 3"; | |
| ASSERT_EQ(false, list.empty()) << "non-empty list is showing empty"; | |
| // iterators | |
| ASSERT_EQ(list.head(), list.begin().pNode) << "head() not equal to begin().pNode"; | |
| ASSERT_NE(list.begin(), list.end()) << "begin() and end() same for non-empty list"; | |
| ASSERT_EQ(n3, (list.begin()).pNode) << "begin.pNode should be n3"; | |
| ASSERT_EQ(n3, ((list.begin())++).pNode) << "begin++.pNode should be n3"; | |
| ASSERT_EQ(n3, ((list.begin())--).pNode) << "begin--.pNode should be n3"; | |
| ASSERT_EQ(n2, (++(list.begin())).pNode) << "++begin.pNode should be n2"; | |
| ASSERT_EQ(n1, (++(++(list.begin()))).pNode) << "++++begin.pNode should be pNode"; | |
| ASSERT_EQ(list.end(), (++(++(++list.begin())))) << "++++++begin() not end()"; | |
| ASSERT_EQ(n3, (--(--(--list.end()))).pNode) << "------end.pNode should be n3"; | |
| ASSERT_EQ(n2, (--(--list.end())).pNode) << "----end.pNode should be n2"; | |
| ASSERT_EQ(n1, (--list.end()).pNode) << "--end.pNode should be pNode"; | |
| ASSERT_EQ(list.begin(), --(--(--list.end()))) << "------end should be begin"; | |
| ASSERT_EQ(6, *(list.begin())) << "begin()-element should have been 6"; | |
| ASSERT_EQ(6, *(list.begin()++)) << "begin()++-element should have been 6"; | |
| ASSERT_EQ(6, *(list.begin()--)) << "begin()-- element should have been 6"; | |
| ASSERT_EQ(5, *(++(list.begin()))) << "++begin()-element should have been 5"; | |
| ASSERT_EQ(4, *(++(++(list.begin())))) << "++++begin()-element should have been 4"; | |
| ASSERT_EQ(4, *(--list.end())) << "--end()-element should have been 4"; | |
| ASSERT_EQ(5, *(--(--list.end()))) << "----end()-element should have been 5"; | |
| ASSERT_EQ(6, *(--(--(--list.end())))) << "------end()-element should have been 6"; | |
| } | |
| } | |
| void addBack(){ | |
| IntList list; | |
| ASSERT_EQ(0, list.size()) << "size should be zero"; | |
| ASSERT_EQ(0, (int)list.head()) << "head should be NULL"; | |
| ASSERT_EQ(0, (int)list.tail()) << "head should be NULL"; | |
| node_t *n1, *n2, *n3; | |
| // add head | |
| { | |
| SCOPED_TRACE("add #1"); | |
| n1 = list.addBack(4); // new node is at head | |
| // list: 4 | |
| ASSERT_NE(0, (int)list.head()) << "head is NULL"; | |
| ASSERT_NE(0, (int)list.tail()) << "tail is NULL"; | |
| ASSERT_EQ(list.head(), list.tail()) << "head != tail"; | |
| ASSERT_EQ(list.head(), n1) << "head() not n1"; | |
| ASSERT_EQ(list.tail(), n1) << "tail() not n1"; | |
| ASSERT_NE(0, (int)n1) << "head is NULL although list has items"; | |
| ASSERT_EQ(list.end().pNode, n1->next()) << "head's next should be end()"; | |
| ASSERT_EQ(list.end().pNode, n1->prev()) << "head's prev should be end()"; | |
| ASSERT_EQ(1, list.size()) << "size should have been 1"; | |
| ASSERT_EQ(false, list.empty()) << "non-empty list is showing empty"; | |
| ASSERT_EQ(4, n1->element) << "head-element should have been 4"; | |
| // iterators | |
| ASSERT_EQ(list.head(), list.begin().pNode) << "head() not equal to begin().pNode"; | |
| ASSERT_EQ(list.tail(), list.begin().pNode) << "tail() not equal to begin().pNode"; | |
| ASSERT_NE(list.begin(), list.end()) << "begin() and end() same for non-empty list"; | |
| ASSERT_EQ(list.end(), ++list.begin()) << "++begin() and end() not same"; | |
| ASSERT_EQ(list.begin(), --list.end()) << "--end() and begin() not same"; | |
| ASSERT_NE(list.end(), list.begin()++) << "begin()++ and end() same"; | |
| ASSERT_NE(list.begin(), list.end()--) << "end()-- and begin() same"; | |
| ASSERT_EQ(list.head(), (list.begin()++).pNode) << "begin()++.pNode not head()"; | |
| ASSERT_EQ(list.tail(), (--list.end()).pNode) << "--end().pNode not tail()"; | |
| ASSERT_EQ(list.end().pNode, (++list.begin()).pNode) << "begin++.pNode should be end()"; | |
| ASSERT_EQ(list.begin().pNode, (--list.end()).pNode) << "--end.pNode should be begin()"; | |
| ASSERT_EQ(4, *list.begin()) << "begin()-element should have been 4"; | |
| ASSERT_EQ(4, *(--list.end())) << "--end()-element should have been 4"; | |
| } | |
| // add 2nd element | |
| { | |
| SCOPED_TRACE("add #2"); | |
| n2 = list.addBack(5); // new node is at head | |
| // list: 4->5 | |
| ASSERT_NE(0, (int)list.head()) << "head is NULL although list has items"; | |
| ASSERT_EQ(list.head(), n1) << "n1 should be head"; | |
| ASSERT_EQ(list.tail(), n2) << "n2 should be tail"; | |
| ASSERT_EQ(list.tail(), list.head()->next()) << "head->next should be tail"; | |
| ASSERT_NE(list.end().pNode, list.head()->next()) << "head->next is end()"; | |
| ASSERT_EQ(n2, list.head()->next()) << "head->next should be n2"; | |
| ASSERT_EQ(list.head(), n2->prev()) << "n2->prev should be head"; | |
| ASSERT_EQ(list.end().pNode, list.tail()->next()) << "tail->next should be end()"; | |
| ASSERT_EQ(list.end().pNode, n2->prev()->prev()) << "n2->perv->prev should be end()"; | |
| ASSERT_EQ(4, list.head()->element) << "head element should have been 4"; | |
| ASSERT_EQ(5, list.tail()->element) << "tail element should have been 5"; | |
| ASSERT_EQ(2, list.size()) << "size should have been 2"; | |
| ASSERT_EQ(false, list.empty()) << "non-empty list is showing empty"; | |
| // iterators | |
| ASSERT_EQ(list.head(), list.begin().pNode) << "head() not equal to begin().pNode"; | |
| ASSERT_EQ(list.tail(), (--(list.end())).pNode) << "tail() not equal to --end().pNode"; | |
| ASSERT_NE(list.begin(), list.end()) << "begin() and end() same for non-empty list"; | |
| ASSERT_EQ(list.end(), ++(++(list.begin()))) << "++++begin() not end()"; | |
| ASSERT_EQ(list.begin(), --(--(list.end()))) << "----end() not begin()"; | |
| ASSERT_EQ(n1, (list.begin()++).pNode) << "begin++.pNode should be n1"; | |
| ASSERT_EQ(n2, (++(list.begin())).pNode) << "++begin.pNode should be n2"; | |
| ASSERT_EQ(n1, (--(--list.end())).pNode) << "----end.pNode should be n1"; | |
| ASSERT_EQ(n2, (--(list.end())).pNode) << "--end.pNode should be n2"; | |
| ASSERT_EQ(4, *(list.begin())) << "begin()-element should have been 4"; | |
| ASSERT_EQ(5, *(++(list.begin()))) << "++begin() element should have been 5"; | |
| ASSERT_EQ(4, *(list.begin()++)) << "begin()++ element should have been 4"; | |
| ASSERT_EQ(5, *(--list.end())) << "--end()-element should have been 5"; | |
| ASSERT_EQ(4, *(--(--list.end()))) << "----end()-element should have been 4"; | |
| } | |
| // add more elements | |
| { | |
| SCOPED_TRACE("add #3"); | |
| n3 = list.addBack(6); // new node is at head | |
| // list: 4->5->6 | |
| ASSERT_NE(0, (int)list.head()) << "head is NULL although list has items"; | |
| ASSERT_NE(list.end().pNode, list.head()->next()) << "head->next is end()"; | |
| ASSERT_NE(list.end().pNode, list.head()->next()->next()) << "head->next->next is end()"; | |
| ASSERT_EQ(n3, list.tail()) << "n3 should be tail"; | |
| ASSERT_EQ(n1, list.head()) << "n1 should be head"; | |
| ASSERT_EQ(n2, list.head()->next()) << "n2 should be head->next"; | |
| ASSERT_EQ(n2, list.tail()->prev()) << "n2 should be tail->prev"; | |
| ASSERT_EQ(n3, n2->next()) << "n3 should be n2->next"; | |
| ASSERT_EQ(list.head(), n2->prev()) << "n2->prev should be head"; | |
| ASSERT_EQ(list.end().pNode, list.tail()->next()) << "tail->next should be end()"; | |
| ASSERT_EQ(list.end().pNode, list.head()->prev()) << "head->prev should be end()"; | |
| ASSERT_EQ(4, list.head()->element) << "head element should have been 4"; | |
| ASSERT_EQ(5, list.head()->next()->element) << "head->next element should have been 5"; | |
| ASSERT_EQ(6, list.head()->next()->next()->element) << "head->next->next element should have been 6"; | |
| ASSERT_EQ(3, list.size()) << "size should have been 3"; | |
| ASSERT_EQ(false, list.empty()) << "non-empty list is showing empty"; | |
| // iterators | |
| ASSERT_EQ(list.head(), list.begin().pNode) << "head() not equal to begin().pNode"; | |
| ASSERT_NE(list.begin(), list.end()) << "begin() and end() same for non-empty list"; | |
| ASSERT_EQ(n1, (list.begin()).pNode) << "begin.pNode should be n1"; | |
| ASSERT_EQ(n1, ((list.begin())++).pNode) << "begin++.pNode should be n1"; | |
| ASSERT_EQ(n1, ((list.begin())--).pNode) << "begin--.pNode should be n1"; | |
| ASSERT_EQ(n2, (++(list.begin())).pNode) << "++begin.pNode should be n2"; | |
| ASSERT_EQ(n3, (++(++(list.begin()))).pNode) << "++++begin.pNode should be n3"; | |
| ASSERT_EQ(list.end(), (++(++(++list.begin())))) << "++++++begin() not end()"; | |
| ASSERT_EQ(n1, (--(--(--list.end()))).pNode) << "------end.pNode should be n1"; | |
| ASSERT_EQ(n2, (--(--list.end())).pNode) << "----end.pNode should be n2"; | |
| ASSERT_EQ(n3, (--list.end()).pNode) << "--end.pNode should be n3"; | |
| ASSERT_EQ(list.begin(), --(--(--list.end()))) << "------end should be begin"; | |
| ASSERT_EQ(4, *(list.begin())) << "begin()-element should have been 4"; | |
| ASSERT_EQ(4, *(list.begin()++)) << "begin()++-element should have been 4"; | |
| ASSERT_EQ(4, *(list.begin()--)) << "begin()-- element should have been 4"; | |
| ASSERT_EQ(5, *(++(list.begin()))) << "++begin()-element should have been 5"; | |
| ASSERT_EQ(6, *(++(++(list.begin())))) << "++++begin()-element should have been 6"; | |
| ASSERT_EQ(6, *(--list.end())) << "--end()-element should have been 6"; | |
| ASSERT_EQ(5, *(--(--list.end()))) << "----end()-element should have been 5"; | |
| ASSERT_EQ(4, *(--(--(--list.end())))) << "------end()-element should have been 4"; | |
| } | |
| } | |
| void insert(){ | |
| IntList list; | |
| node_t* n[] = { | |
| list.addBack(0), | |
| list.addBack(1), | |
| list.addBack(2), | |
| list.addBack(3) | |
| }; | |
| // list: 0--1--2--3 | |
| // insert before 0 | |
| { | |
| SCOPED_TRACE("insert before 0"); | |
| node_t* n_1 = list.insert(n[0], -1); // insert -1 before 0 | |
| ASSERT_EQ(5, list.size()) << "size not 5"; | |
| ASSERT_EQ(-1, *list.begin()) << "begin() element not -1"; | |
| ASSERT_EQ(n_1, list.begin().pNode) << "begin() node not n_1"; | |
| } | |
| // list: (-1)--0--1--2--3 | |
| // insert after 3 | |
| { | |
| SCOPED_TRACE("insert after 3"); | |
| node_t* n4 = list.insert(n[3]->next(), 4); // insert 4 after 3 | |
| ASSERT_EQ(6, list.size()) << "size not 6"; | |
| ASSERT_EQ(4, *--list.end()) << "--end() element not 4"; | |
| ASSERT_EQ(n4, (--list.end()).pNode) << "--end() node not n4"; | |
| } | |
| // list: (-1)--0--1--2--3--4 | |
| // insert before 2 | |
| { | |
| SCOPED_TRACE("insert before 2"); | |
| node_t* n10 = list.insert(n[2], 10); // insert 10 before 2 | |
| ASSERT_EQ(7, list.size()) << "size not 7"; | |
| ASSERT_EQ(10, *++ ++ ++list.begin()) << "n10 element not 10 from begin"; | |
| ASSERT_EQ(n10, (-- -- -- --list.end()).pNode) << "node not n10 from end"; | |
| } | |
| // list: (-1)--0--1--10--2--3--4 | |
| } | |
| void addBefore(){ | |
| IntList list; | |
| ASSERT_EQ(0, list.size()) << "size should be zero"; | |
| ASSERT_EQ(0, (int)list.head()) << "head should be NULL"; | |
| // add before NULL | |
| node_t* pNode = list.addBefore(5, NULL); // should fail | |
| ASSERT_EQ(NULL, pNode) << "added before NULL"; | |
| // one-item list | |
| node_t* n0 = list.addFront(0); | |
| ASSERT_EQ(0, n0->element) << "wrong element"; | |
| node_t* n1 = list.addBefore(1, n0); | |
| // list: 1->0 | |
| ASSERT_EQ(n1, list.head()) << "n1 should be head"; | |
| ASSERT_EQ(n0, list.tail()) << "n0 should be tail"; | |
| ASSERT_EQ(1, list.head()->element) << "wrong head element"; | |
| ASSERT_EQ(0, list.tail()->element) << "wrong tail element"; | |
| ASSERT_EQ(n0, n1->next()) << "n1->next should be n0"; | |
| ASSERT_EQ(n1, n0->prev()) << "n0->prev should be n1"; | |
| ASSERT_EQ(2, list.size()) << "size should be 2"; | |
| ASSERT_EQ(list.end().pNode, n1->prev()) << "n1->prev should be end()"; | |
| ASSERT_EQ(list.end().pNode, n0->next()) << "n0->next should be end()"; | |
| // add more items | |
| const int testSize = 5; | |
| node_t* n[testSize]; | |
| n[0] = n0; | |
| n[1] = n1; | |
| for (int i = 2; i < testSize; i++){ | |
| n[i] = list.addBefore(i, n[i - 1]); | |
| } | |
| // list: 4->3->2->1->0 | |
| ASSERT_EQ(5, list.size()) << "size should be 5"; | |
| ASSERT_EQ(n[4], list.head()) << "4 should be at head"; | |
| ASSERT_EQ(n[3], list.head()->next()) << "3 should be 4->next"; | |
| ASSERT_EQ(n[2], list.head()->next()->next()) << "2 should be 3->next"; | |
| ASSERT_EQ(n[1], list.head()->next()->next()->next()) << "1 should be 2->next"; | |
| ASSERT_EQ(n[0], list.head()->next()->next()->next()->next()) << "0 should be 1->next"; | |
| ASSERT_EQ(list.end().pNode, list.head()->next()->next()->next()->next()->next()) << "tail->next should be end()"; | |
| ASSERT_EQ(n[0], list.tail()) << "0 should be at tail"; | |
| ASSERT_EQ(n[1], list.tail()->prev()) << "1 should be 0->prev"; | |
| ASSERT_EQ(n[2], list.tail()->prev()->prev()) << "2 should be 1->prev"; | |
| ASSERT_EQ(n[3], list.tail()->prev()->prev()->prev()) << "3 should be 2->prev"; | |
| ASSERT_EQ(n[4], list.tail()->prev()->prev()->prev()->prev()) << "4 should be 3->prev"; | |
| ASSERT_EQ(list.end().pNode, list.tail()->prev()->prev()->prev()->prev()->prev()) << "head->prev should be end()"; | |
| ASSERT_EQ(4, list.head()->element) << "4 should be at head"; | |
| ASSERT_EQ(3, list.head()->next()->element) << "3 should be 4->next"; | |
| ASSERT_EQ(2, list.head()->next()->next()->element) << "2 should be 3->next"; | |
| ASSERT_EQ(1, list.head()->next()->next()->next()->element) << "1 should be 2->next"; | |
| ASSERT_EQ(0, list.head()->next()->next()->next()->next()->element) << "0 should be 1->next"; | |
| // add in the middle | |
| node_t* n10 = list.addBefore(10, n[2]); | |
| // list: 4->3->10->2->1->0 | |
| ASSERT_EQ(6, list.size()) << "size should be 6"; | |
| ASSERT_EQ(n[4], list.head()) << "4 should be at head"; | |
| ASSERT_EQ(n[3], list.head()->next()) << "3 should be 4->next"; | |
| ASSERT_EQ(n10, list.head()->next()->next()) << "10 should be 3->next"; | |
| ASSERT_EQ(n[2], list.head()->next()->next()->next()) << "2 should be 10->next"; | |
| ASSERT_EQ(n[1], list.head()->next()->next()->next()->next()) << "1 should be 10->next"; | |
| ASSERT_EQ(n[0], list.head()->next()->next()->next()->next()->next()) << "0 should be 1->next"; | |
| ASSERT_EQ(list.end().pNode, list.head()->next()->next()->next()->next()->next()->next()) << "tail->next should be end()"; | |
| ASSERT_EQ(n[0], list.tail()) << "0 should be at tail"; | |
| ASSERT_EQ(n[1], list.tail()->prev()) << "1 should be 0->prev"; | |
| ASSERT_EQ(n[2], list.tail()->prev()->prev()) << "2 should be 1->prev"; | |
| ASSERT_EQ(n10, list.tail()->prev()->prev()->prev()) << "10 should be 2->prev"; | |
| ASSERT_EQ(n[3], list.tail()->prev()->prev()->prev()->prev()) << "3 should be 10->prev"; | |
| ASSERT_EQ(n[4], list.tail()->prev()->prev()->prev()->prev()->prev()) << "4 should be 3->prev"; | |
| ASSERT_EQ(list.end().pNode, list.tail()->prev()->prev()->prev()->prev()->prev()->prev()) << "head->prev should be end()"; | |
| ASSERT_EQ(4, list.head()->element) << "4 should be at head"; | |
| ASSERT_EQ(3, list.head()->next()->element) << "3 should be 4->next"; | |
| ASSERT_EQ(10, list.head()->next()->next()->element) << "10 should be 3->next"; | |
| ASSERT_EQ(2, list.head()->next()->next()->next()->element) << "2 should be 10->next"; | |
| ASSERT_EQ(1, list.head()->next()->next()->next()->next()->element) << "1 should be 10->next"; | |
| ASSERT_EQ(0, list.head()->next()->next()->next()->next()->next()->element) << "0 should be 1->next"; | |
| } | |
| void addAfter(){ | |
| IntList list; | |
| ASSERT_EQ(0, list.size()) << "size should be zero"; | |
| ASSERT_EQ(0, (int)list.head()) << "head should be NULL"; | |
| // add before NULL | |
| node_t* pNode = list.addBefore(5, NULL); // should fail | |
| ASSERT_EQ(NULL, pNode) << "added before NULL"; | |
| // one-item list | |
| node_t* n4 = list.addFront(4); | |
| ASSERT_EQ(4, n4->element) << "wrong element"; | |
| node_t* n3 = list.addAfter(3, n4); | |
| // list: 4->3 | |
| ASSERT_EQ(n4, list.head()) << "n1 should be head"; | |
| ASSERT_EQ(n3, list.tail()) << "n0 should be tail"; | |
| ASSERT_EQ(4, list.head()->element) << "wrong head element"; | |
| ASSERT_EQ(3, list.tail()->element) << "wrong tail element"; | |
| ASSERT_EQ(n3, n4->next()) << "n4->next should be n3"; | |
| ASSERT_EQ(n4, n3->prev()) << "n3->prev should be n4"; | |
| ASSERT_EQ(2, list.size()) << "size should be 2"; | |
| ASSERT_EQ(list.end().pNode, n4->prev()) << "n4->prev should be end()"; | |
| ASSERT_EQ(list.end().pNode, n3->next()) << "n3->next should be end()"; | |
| // add more items | |
| const int testSize = 5; | |
| node_t* n[testSize]; | |
| n[4] = n4; | |
| n[3] = n3; | |
| for (int i = 2; i >= 0; i--){ | |
| n[i] = list.addAfter(i, n[i + 1]); | |
| } | |
| // list: 4->3->2->1->0 | |
| ASSERT_EQ(5, list.size()) << "size should be 5"; | |
| ASSERT_EQ(n[4], list.head()) << "4 should be at head"; | |
| ASSERT_EQ(n[3], list.head()->next()) << "3 should be 4->next"; | |
| ASSERT_EQ(n[2], list.head()->next()->next()) << "2 should be 3->next"; | |
| ASSERT_EQ(n[1], list.head()->next()->next()->next()) << "1 should be 2->next"; | |
| ASSERT_EQ(n[0], list.head()->next()->next()->next()->next()) << "0 should be 1->next"; | |
| ASSERT_EQ(list.end().pNode, list.head()->next()->next()->next()->next()->next()) << "tail->next should be end()"; | |
| ASSERT_EQ(n[0], list.tail()) << "0 should be at tail"; | |
| ASSERT_EQ(n[1], list.tail()->prev()) << "1 should be 0->prev"; | |
| ASSERT_EQ(n[2], list.tail()->prev()->prev()) << "2 should be 1->prev"; | |
| ASSERT_EQ(n[3], list.tail()->prev()->prev()->prev()) << "3 should be 2->prev"; | |
| ASSERT_EQ(n[4], list.tail()->prev()->prev()->prev()->prev()) << "4 should be 3->prev"; | |
| ASSERT_EQ(list.end().pNode, list.tail()->prev()->prev()->prev()->prev()->prev()) << "head->prev should be end()"; | |
| ASSERT_EQ(4, list.head()->element) << "4 should be at head"; | |
| ASSERT_EQ(3, list.head()->next()->element) << "3 should be 4->next"; | |
| ASSERT_EQ(2, list.head()->next()->next()->element) << "2 should be 3->next"; | |
| ASSERT_EQ(1, list.head()->next()->next()->next()->element) << "1 should be 2->next"; | |
| ASSERT_EQ(0, list.head()->next()->next()->next()->next()->element) << "0 should be 1->next"; | |
| // add in the middle | |
| node_t* n10 = list.addAfter(10, n[3]); | |
| // list: 4->3->10->2->1->0 | |
| ASSERT_EQ(6, list.size()) << "size should be 6"; | |
| ASSERT_EQ(n[4], list.head()) << "4 should be at head"; | |
| ASSERT_EQ(n[3], list.head()->next()) << "3 should be 4->next"; | |
| ASSERT_EQ(n10, list.head()->next()->next()) << "10 should be 3->next"; | |
| ASSERT_EQ(n[2], list.head()->next()->next()->next()) << "2 should be 10->next"; | |
| ASSERT_EQ(n[1], list.head()->next()->next()->next()->next()) << "1 should be 10->next"; | |
| ASSERT_EQ(n[0], list.head()->next()->next()->next()->next()->next()) << "0 should be 1->next"; | |
| ASSERT_EQ(list.end().pNode, list.head()->next()->next()->next()->next()->next()->next()) << "tail->next should be end()"; | |
| ASSERT_EQ(n[0], list.tail()) << "0 should be at tail"; | |
| ASSERT_EQ(n[1], list.tail()->prev()) << "1 should be 0->prev"; | |
| ASSERT_EQ(n[2], list.tail()->prev()->prev()) << "2 should be 1->prev"; | |
| ASSERT_EQ(n10, list.tail()->prev()->prev()->prev()) << "10 should be 2->prev"; | |
| ASSERT_EQ(n[3], list.tail()->prev()->prev()->prev()->prev()) << "3 should be 10->prev"; | |
| ASSERT_EQ(n[4], list.tail()->prev()->prev()->prev()->prev()->prev()) << "4 should be 3->prev"; | |
| ASSERT_EQ(list.end().pNode, list.tail()->prev()->prev()->prev()->prev()->prev()->prev()) << "head->prev should be end()"; | |
| ASSERT_EQ(4, list.head()->element) << "4 should be at head"; | |
| ASSERT_EQ(3, list.head()->next()->element) << "3 should be 4->next"; | |
| ASSERT_EQ(10, list.head()->next()->next()->element) << "10 should be 3->next"; | |
| ASSERT_EQ(2, list.head()->next()->next()->next()->element) << "2 should be 10->next"; | |
| ASSERT_EQ(1, list.head()->next()->next()->next()->next()->element) << "1 should be 10->next"; | |
| ASSERT_EQ(0, list.head()->next()->next()->next()->next()->next()->element) << "0 should be 1->next"; | |
| } | |
| void remove(){ | |
| int e; | |
| bool ok; | |
| node_t *n1, *n2, *n3, *n4, *n5; | |
| IntList list; | |
| ASSERT_EQ(0, list.size()) << "size should be zero"; | |
| ASSERT_EQ(0, (int)list.head()) << "head should be NULL"; | |
| { | |
| SCOPED_TRACE("removing from empty list"); | |
| ok = list.remove(list.head(), e); // should fail | |
| ASSERT_EQ(false, ok) << "remove() succeeded on empty list"; | |
| } | |
| { | |
| SCOPED_TRACE("removing the only node"); | |
| n1 = list.addFront(1); | |
| ok = list.remove(n1, e); | |
| ASSERT_EQ(true, ok) << "remove failed"; | |
| ASSERT_EQ(1, e) << "wrong element in removed node"; | |
| ASSERT_EQ(0, list.size()) << "size should be zero"; | |
| ASSERT_EQ(true, list.empty()) << "list should be empty"; | |
| // reinsert a node | |
| list.addFront(1); | |
| ASSERT_EQ(1, list.size()) << "size should be 1"; | |
| ASSERT_EQ(false, list.empty()) << "list should be non-empty"; | |
| } | |
| { | |
| // list: 1 | |
| SCOPED_TRACE("remove the second node of a size-2 list"); | |
| n1 = list.addFront(2); // list: 2->1 | |
| ok = list.remove(n1, e); // list: 1 | |
| ASSERT_EQ(true, ok) << "remove failed"; | |
| ASSERT_EQ(2, e) << "wrong element in removed node"; | |
| ASSERT_EQ(1, list.size()) << "size should be zero"; | |
| ASSERT_EQ(false, list.empty()) << "list should be empty"; | |
| ASSERT_EQ(1, list.head()->element) << "head-element should be 1"; | |
| } | |
| { | |
| // list: 1 | |
| SCOPED_TRACE("remove the last node of a size-3 list"); | |
| n1 = list.head(); // list: 1 | |
| n2 = list.addFront(2); // list: 2->1 | |
| n3 = list.addFront(3); // list: 3->2->1 | |
| ok = list.remove(n1, e); // remove 1; list: 3->2 | |
| ASSERT_EQ(true, ok) << "remove failed"; | |
| ASSERT_EQ(1, e) << "wrong element in removed node"; | |
| ASSERT_EQ(2, list.size()) << "size should be 2"; | |
| ASSERT_EQ(false, list.empty()) << "list should not be empty"; | |
| ASSERT_EQ(n3, list.head()) << "wrong pointer at list head"; | |
| ASSERT_EQ(n2, list.tail()) << "wrong pointer at list tail"; | |
| ASSERT_EQ(n2, list.head()->next()) << "wrong pointer at list head->next"; | |
| ASSERT_EQ(n3, list.tail()->prev()) << "wrong pointer at list tail->prev"; | |
| ASSERT_EQ(3, list.head()->element) << "head-element should be 1"; | |
| ASSERT_EQ(2, list.head()->next()->element) << "head-element should be 2"; | |
| } | |
| { | |
| // list: 3->2 | |
| SCOPED_TRACE("remove a middle node"); | |
| n3 = list.head(); // list: 3->2 | |
| n2 = n3->next(); // | |
| n4 = list.addFront(4); // list: 4->3->2 | |
| n5 = list.addFront(5); // list: 5->4->3->2 | |
| // try to remove 4 | |
| ok = list.remove(n4, e); // remove 4; list: 5->3->2 | |
| ASSERT_EQ(true, ok) << "remove failed"; | |
| ASSERT_EQ(4, e) << "removed element should be 4"; | |
| ASSERT_EQ(3, list.size()) << "size should be 3"; | |
| ASSERT_EQ(false, list.empty()) << "list should not be empty"; | |
| ASSERT_EQ(n5, list.head()) << "wrong pointer at list head"; | |
| ASSERT_EQ(n3, list.head()->next()) << "wrong pointer at list head->next"; | |
| ASSERT_EQ(n2, list.head()->next()->next()) << "wrong pointer at list head->next->next"; | |
| ASSERT_EQ(list.end().pNode, n2->next()) << "last->next should be end()"; | |
| ASSERT_EQ(n2, list.tail()) << "wrong pointer at list tail"; | |
| ASSERT_EQ(n3, list.tail()->prev()) << "wrong pointer at list tail->prev"; | |
| ASSERT_EQ(n5, list.tail()->prev()->prev()) << "wrong pointer at list tail->prev->prev"; | |
| ASSERT_EQ(list.end().pNode, n5->prev()) << "head->prev should be end()"; | |
| ASSERT_EQ(5, list.head()->element) << "head-element should be 5"; | |
| ASSERT_EQ(3, list.head()->next()->element) << "head-element should be 3"; | |
| ASSERT_EQ(2, list.head()->next()->next()->element) << "head-element should be 2"; | |
| // now try to remove 3 | |
| // list: 5->3->2 | |
| ok = list.remove(n3, e); // remove 3; list: 5->2 | |
| ASSERT_EQ(true, ok) << "remove failed"; | |
| ASSERT_EQ(3, e) << "removed element should be 3"; | |
| ASSERT_EQ(2, list.size()) << "size should be 2"; | |
| ASSERT_EQ(false, list.empty()) << "list should not be empty"; | |
| ASSERT_EQ(n5, list.head()) << "wrong pointer at list head"; | |
| ASSERT_EQ(n2, list.head()->next()) << "wrong pointer at list head->next"; | |
| ASSERT_EQ(list.end().pNode, list.head()->next()->next()) << "last->next should be end()"; | |
| ASSERT_EQ(n2, list.tail()) << "wrong pointer at list tail"; | |
| ASSERT_EQ(n5, list.tail()->prev()) << "wrong pointer at list tail->prev"; | |
| ASSERT_EQ(list.end().pNode, list.tail()->prev()->prev()) << "head->prev should be end()"; | |
| ASSERT_EQ(5, list.head()->element) << "head-element should be 5"; | |
| ASSERT_EQ(2, list.head()->next()->element) << "head-next element should be 2"; | |
| } | |
| } | |
| void head(){ | |
| int e; | |
| //IntList list = * static_cast<IntList*>(createList()); | |
| IntList list; | |
| node_t* pNode = list.head(); | |
| ASSERT_EQ(0, (int)pNode) << "head must be null at the beginning"; | |
| list.addFront(4); | |
| pNode = list.head(); | |
| ASSERT_NE(0, (int)pNode) << "head is NULL although list has items"; | |
| ASSERT_EQ(list.end().pNode, pNode->next()) << "head's next should be end()"; | |
| ASSERT_EQ(list.head(), list.tail()) << "tail should be = head"; | |
| ASSERT_EQ(1, list.size()) << "size should have been 1"; | |
| ASSERT_EQ(false, list.empty()) << "non-empty list is showing empty"; | |
| ASSERT_EQ(4, pNode->element) << "head-element should have been 4"; | |
| list.remove(pNode, e); | |
| pNode = list.head(); | |
| ASSERT_EQ(0, (int)pNode) << "head should have been null"; | |
| } | |
| void tail(){ | |
| int e; | |
| IntList list; | |
| node_t* pNode = list.tail(); | |
| ASSERT_EQ(0, (int)pNode) << "tail must be null at the beginning"; | |
| list.addFront(4); | |
| pNode = list.tail(); | |
| ASSERT_NE(0, (int)pNode) << "tail is NULL although list has items"; | |
| ASSERT_EQ(list.end().pNode, pNode->next()) << "tail's next should be end()"; | |
| ASSERT_EQ(list.end().pNode, pNode->prev()) << "tail's prev should be end()"; | |
| ASSERT_EQ(list.head(), list.tail()) << "tail should be = head"; | |
| ASSERT_EQ(1, list.size()) << "size should have been 1"; | |
| ASSERT_EQ(false, list.empty()) << "non-empty list is showing empty"; | |
| ASSERT_EQ(4, pNode->element) << "tail-element should have been 4"; | |
| list.remove(pNode, e); | |
| pNode = list.tail(); | |
| ASSERT_EQ(0, (int)pNode) << "tail should have been null"; | |
| } | |
| void clear(){ | |
| IntList list; | |
| int srcArr[] = { 10, 20, 30, 40 }; | |
| int n = ARR_LENGTH(srcArr); | |
| list.fromArray(srcArr, n); // build list | |
| //ASSERT_NE(0, (int)list.head()) << "list head is NULL"; | |
| ASSERT_EQ(n, list.size()) << "list size should have been " << n; | |
| list.clear(); | |
| ASSERT_EQ(0, list.size()) << "size not zero after clear"; | |
| ASSERT_EQ(true, list.empty()) << "size not zero after clear"; | |
| ASSERT_EQ(NULL, list.head()) << "head not NULL after clear"; | |
| ASSERT_EQ(NULL, list.tail()) << "tail not NULL after clear"; | |
| } | |
| }; | |
| ADD_TEST_F(DoublyLinkedListTest, insert); | |
| ADD_TEST_F(DoublyLinkedListTest, addFront); | |
| ADD_TEST_F(DoublyLinkedListTest, addBack); | |
| ADD_TEST_F(DoublyLinkedListTest, addBefore); | |
| ADD_TEST_F(DoublyLinkedListTest, addAfter); | |
| ADD_TEST_F(DoublyLinkedListTest, remove); | |
| ADD_TEST_F(DoublyLinkedListTest, head); | |
| ADD_TEST_F(DoublyLinkedListTest, tail); | |
| ADD_TEST_F(DoublyLinkedListTest, fromArray); | |
| ADD_TEST_F(DoublyLinkedListTest, elements); | |
| ADD_TEST_F(DoublyLinkedListTest, relements); | |
| ADD_TEST_F(DoublyLinkedListTest, clear); | |
| ADD_TEST_F(DoublyLinkedListTest, toString); | |
| } | |
| } |