As this implementation is to use all the functions implemented on Data Structure and Algorithm - Linked List: Common API and Data Structure and Algorithm - Linked List: Merge Sort. So the major difficulty is to maintain the two cached property "m_Tail" and "m_Size". And the purpose is to achieve the same/better performance than C API implementation in Data Structure and Algorithm - Linked List: Common API and Data Structure and Algorithm - Linked List: Merge Sort.
Just realize that C++11 has introduced a new STL container called std::forward_list which is an implementation of single-linked-list. More details please refer to forward_list on cppreference. Read through its APIs and it provides the same sort of utilities as this implementation.
Just realize that C++11 has introduced a new STL container called std::forward_list which is an implementation of single-linked-list. More details please refer to forward_list on cppreference. Read through its APIs and it provides the same sort of utilities as this implementation.
// C++ Implementation
// ********************************************************************************
// LinkedListContainer.h
#ifndef LINKED_LIST_CONTAINER_H
#define LINKED_LIST_CONTAINER_H
#include "LinkedListAlgo.h"
#include "LinkedListElement.h"
#include "LinkedListSort.h"
template <typename T>
class LinkedListContainer
{
typedef LinkedListElement<T>* NodePtr;
typedef LinkedListElement<T> Node;
public:
LinkedListContainer()
{}
~LinkedListContainer()
{
DeleteList();
}
void PushBack(const T& data)
{
LL_PushBack(&m_Tail, data);
if (m_Head == nullptr) {
// empty list before push
m_Head = m_Tail;
}
else {
m_Tail = m_Tail->next;
}
++m_Size;
}
void PushFront(const T& data)
{
LL_PushFront(&m_Head, data);
if (m_Tail == nullptr) {
// empty list before push
m_Tail = m_Head;
}
++m_Size;
}
void PopBack()
{
if (m_Head == nullptr) {
return;
}
if (m_Head == m_Tail) {
// empty list after pop
delete m_Tail;
m_Head = nullptr;
m_Tail = nullptr;
}
else {
NodePtr temp = m_Head;
while (temp) {
if (temp->next == m_Tail) {
break;
}
temp = temp->next;
}
delete m_Tail;
m_Tail = temp;
m_Tail->next = nullptr;
}
--m_Size;
}
void PopFront()
{
if (m_Head == nullptr) {
return;
}
LL_PopFront(&m_Head);
if (m_Head == nullptr) {
// empty list after pop
m_Tail = nullptr;
}
--m_Size;
}
bool Insert(size_t pos, const T& data)
{
if (pos > m_Size) {
return false;
}
if (pos == 0) {
PushFront(data);
}
else if (pos == m_Size) {
PushBack(data);
}
else {
LL_Insert(&m_Head, pos, data);
++m_Size;
}
return true;
}
bool Insert(const NodePtr posPtr, const T& data)
{
if (m_Head == nullptr || posPtr == nullptr) {
return false;
}
if (!LL_Insert(&m_Head, posPtr, data)) {
return false;
}
++m_size;
return true;
}
bool Erase(const size_t pos)
{
if (m_Head == nullptr || pos >= m_Size) {
return false;
}
if (pos == 0) {
PopFront();
}
else if (pos == (m_Size - 1)) {
PopBack();
}
else {
// in this case no need to update m_Tail
if (!LL_Erase(&m_Head, pos)) {
return false;
}
--m_Size;
}
return true;
}
// after this functin, posPtr becomes invalid
bool Erase(const NodePtr posPtr)
{
if (posPtr == m_Head) {
PopFront();
}
else if (posPtr == m_Tail) {
PopBack();
}
else {
// in this case no need to update m_Tail
if (!LL_Erase(&m_Head, posPtr)) {
return fasle;
}
--m_Size;
}
return true;
}
ptrdiff_t Find(const T& data)
{
NodePtr temp = m_Head;
ptrdiff_t pos = 0;
while (temp) {
if (temp->data == data) {
return pos;
}
++pos;
temp = temp->next;
}
return -1;
}
void Reverse()
{
m_Tail = m_Head;
LL_Reverse(&m_Head);
}
size_t GetSize() const {
return m_Size;
}
void MergeSort()
{
LL_MergeSort(&m_Head);
// reset m_Tail
ResetTail();
}
/*
* After this opertaion, &other will lose the ownership
*/
void SortedMerge(LinkedListContainer<T>& other)
{
m_Size += other.m_Size;
if (m_Tail->data < other.m_Tail->data) {
m_Tail = other.m_Tail;
}
m_Head = LL_SortedMerge(m_Head, other.m_Head);
// "other" has to lose the ownership, otherwise
// may cuase double free
other.m_Head = nullptr;
other.m_Tail = nullptr;
other.m_Size = 0;
}
void SortedMerge_Recursive(LinkedListContainer<T>& other)
{
m_Size += other.m_Size;
// m_Tail points the largest element
if (m_Tail->data > other.m_Tail->data) {
m_Tail = other.m_Tail;
}
m_Head = LL_SortedMergeRecursively(m_Head, other.m_Head);
}
/*
* Has to work on a sorted linkedlist
*/
void RemoveDuplicates()
{
if (m_Head == nullptr){
return;
}
// Do not call LL_RemoveDuplicates()
// otherwise has to update m_Tail and m_Size
// cause worse performance
NodePtr curValPtr = m_Head;
NodePtr nextValPtr = m_Head->next;
while (nextValPtr != nullptr) {
if (nextValPtr->data == curValPtr->data) {
curValPtr->next = nextValPtr->next;
delete nextValPtr;
nextValPtr = curValPtr->next;
--m_Size;
}
else {
curValPtr = nextValPtr;
nextValPtr = nextValPtr->next;
}
}
m_Tail = curValPtr;
return;
}
void DeleteList()
{
LL_Delete(&m_Head);
// m_Head should set as nullptr already
m_Tail = nullptr;
m_Size = 0;
}
bool GetNth(size_t n, T& t)
{
return LL_GetNth(m_Head, n, t);
}
void Print(std::ostream& os)
{
NodePtr temp = m_Head;
while (temp != nullptr) {
os << temp->data;
temp = temp->next;
}
}
private:
void ResetTail()
{
NodePtr prev = m_Head;
m_Tail = m_Head;
while (m_Tail != nullptr) {
prev = m_Tail;
m_Tail = m_Tail->next;
}
m_Tail = prev;
}
NodePtr m_Head = nullptr;
NodePtr m_Tail = nullptr;
size_t m_Size = 0;
};
#endif
// test.cpp
void TestLinkedListContainer()
{
LinkedListContainer<int> myLLC;
myLLC.PushFront(10);
assert(myLLC.GetSize() == 1);
myLLC.PushBack(20);
assert(myLLC.GetSize() == 2);
int val;
assert(myLLC.GetNth(0, val) == true);
assert(val == 10);
assert(myLLC.GetNth(1, val) == true);
assert(val == 20);
myLLC.PushFront(30);
assert(myLLC.GetSize() == 3);
assert(myLLC.GetNth(0, val) == true);
assert(val == 30);
myLLC.PopFront();
assert(myLLC.GetSize() == 2);
assert(myLLC.GetNth(0, val) == true);
assert(val == 10);
myLLC.PopBack();
assert(myLLC.GetSize() == 1);
assert(myLLC.GetNth(0, val) == true);
assert(val == 10);
myLLC.PopFront();
assert(myLLC.GetSize() == 0);
assert(myLLC.GetNth(0, val) == false);
myLLC.PushBack(40);
assert(myLLC.GetSize() == 1);
assert(myLLC.GetNth(0, val) == true);
assert(val == 40);
myLLC.PushFront(50);
assert(myLLC.GetSize() == 2);
assert(myLLC.GetNth(0, val) == true);
assert(val == 50);
myLLC.PopFront();
assert(myLLC.GetNth(0, val) == true);
assert(val == 40);
myLLC.PopBack();
assert(myLLC.GetSize() == 0);
assert(myLLC.Insert(2, 30) == false);
assert(myLLC.GetSize() == 0);
assert(myLLC.Insert((size_t)0, 30) == true);
assert(myLLC.GetSize() == 1);
assert(myLLC.GetNth(0, val) == true);
assert(val == 30);
myLLC.PushBack(40);
assert(myLLC.GetSize() == 2);
assert(myLLC.GetNth(1, val) == true);
assert(val == 40);
myLLC.PopFront();
myLLC.PopFront();
assert(myLLC.GetSize() == 0);
// construct 9, 12, 10, 3, 20, 18, 10, 40
myLLC.PushFront(3);
myLLC.PushFront(10);
myLLC.PushFront(12);
myLLC.PushFront(9);
myLLC.PushBack(20);
myLLC.PushBack(18);
myLLC.PushBack(10);
myLLC.PushBack(40);
assert(myLLC.GetSize() == 8);
assert(myLLC.GetNth(0, val) == true);
assert(val == 9);
assert(myLLC.GetNth(1, val) == true);
assert(val == 12);
assert(myLLC.GetNth(2, val) == true);
assert(val == 10);
assert(myLLC.GetNth(3, val) == true);
assert(val == 3);
assert(myLLC.GetNth(4, val) == true);
assert(val == 20);
assert(myLLC.GetNth(5, val) == true);
assert(val == 18);
assert(myLLC.GetNth(6, val) == true);
assert(val == 10);
assert(myLLC.GetNth(7, val) == true);
assert(val == 40);
assert(myLLC.GetNth(8, val) == false);
// construct 9, 12, 10, 3, 20, 18, 10, 40
// 3, 9, 10, 10, 12, 18,20, 40
myLLC.MergeSort();
assert(myLLC.GetSize() == 8);
assert(myLLC.GetNth(0, val) == true);
assert(val == 3);
assert(myLLC.GetNth(1, val) == true);
assert(val == 9);
assert(myLLC.GetNth(2, val) == true);
assert(val == 10);
assert(myLLC.GetNth(3, val) == true);
assert(val == 10);
assert(myLLC.GetNth(4, val) == true);
assert(val == 12);
assert(myLLC.GetNth(5, val) == true);
assert(val == 18);
assert(myLLC.GetNth(6, val) == true);
assert(val == 20);
assert(myLLC.GetNth(7, val) == true);
assert(val == 40);
assert(myLLC.GetNth(8, val) == false);
assert(myLLC.Erase(8) == false);
// 3, 9, 10, 10, 12, 18, 20
assert(myLLC.Erase(7) == true);
// 9, 10, 10, 12, 18, 20
assert(myLLC.Erase((size_t)0) == true);
// 9, 10, 10, 18, 20
assert(myLLC.Erase(3) == true);
assert(myLLC.GetSize() == 5);
assert(myLLC.GetNth(0, val) == true);
assert(val == 9);
assert(myLLC.GetNth(1, val) == true);
assert(val == 10);
assert(myLLC.GetNth(2, val) == true);
assert(val == 10);
assert(myLLC.GetNth(3, val) == true);
assert(val == 18);
assert(myLLC.GetNth(4, val) == true);
assert(val == 20);
assert(myLLC.GetNth(5, val) == false);
// 9, 10, 18, 20
myLLC.RemoveDuplicates();
assert(myLLC.GetSize() == 4);
assert(myLLC.GetNth(0, val) == true);
assert(val == 9);
assert(myLLC.GetNth(1, val) == true);
assert(val == 10);
assert(myLLC.GetNth(2, val) == true);
assert(val == 18);
assert(myLLC.GetNth(3, val) == true);
assert(val == 20);
assert(myLLC.GetNth(5, val) == false);
// 20, 9, 10, 18, 20
assert(myLLC.Insert((size_t)0, 20) == true);
// 20, 9, 10, 18, 9, 20
assert(myLLC.Insert(4, 9) == true);
// 20, 9, 10, 18, 9, 20, 18
assert(myLLC.Insert(6, 18));
assert(myLLC.GetSize() == 7);
assert(myLLC.GetNth(0, val) == true);
assert(val == 20);
assert(myLLC.GetNth(1, val) == true);
assert(val == 9);
assert(myLLC.GetNth(2, val) == true);
assert(val == 10);
assert(myLLC.GetNth(3, val) == true);
assert(val == 18);
assert(myLLC.GetNth(4, val) == true);
assert(val == 9);
assert(myLLC.GetNth(5, val) == true);
assert(val == 20);
assert(myLLC.GetNth(6, val) == true);
assert(val == 18);
assert(myLLC.GetNth(7, val) == false);
// 9, 9, 10, 18, 18, 20, 20
myLLC.MergeSort();
assert(myLLC.GetSize() == 7);
assert(myLLC.GetNth(0, val) == true);
assert(val == 9);
assert(myLLC.GetNth(1, val) == true);
assert(val == 9);
assert(myLLC.GetNth(2, val) == true);
assert(val == 10);
assert(myLLC.GetNth(3, val) == true);
assert(val == 18);
assert(myLLC.GetNth(4, val) == true);
assert(val == 18);
assert(myLLC.GetNth(5, val) == true);
assert(val == 20);
assert(myLLC.GetNth(6, val) == true);
assert(val == 20);
assert(myLLC.GetNth(7, val) == false);
// 9, 10, 18, 20
myLLC.RemoveDuplicates();
assert(myLLC.GetSize() == 4);
assert(myLLC.GetNth(0, val) == true);
assert(val == 9);
assert(myLLC.GetNth(1, val) == true);
assert(val == 10);
assert(myLLC.GetNth(2, val) == true);
assert(val == 18);
assert(myLLC.GetNth(3, val) == true);
assert(val == 20);
assert(myLLC.GetNth(4, val) == false);
// const another list 1, 15, 25, 19, 12
LinkedListContainer<int> myLLC2;
myLLC2.PushFront(25);
myLLC2.PushBack(19);
myLLC2.PushFront(15);
myLLC2.PushBack(12);
myLLC2.PushFront(1);
assert(myLLC2.GetSize() == 5);
// 1, 12, 15, 19, 25
myLLC2.MergeSort();
assert(myLLC2.GetSize() == 5);
assert(myLLC2.GetNth(0, val) == true);
assert(val == 1);
assert(myLLC2.GetNth(1, val) == true);
assert(val == 12);
assert(myLLC2.GetNth(2, val) == true);
assert(val == 15);
assert(myLLC2.GetNth(3, val) == true);
assert(val == 19);
assert(myLLC2.GetNth(4, val) == true);
assert(val == 25);
assert(myLLC2.GetNth(5, val) == false);
// 1, 9, 10, 12, 15, 18, 19, 20, 25
myLLC.SortedMerge(myLLC2);
assert(myLLC2.GetSize() == 0);
assert(myLLC.GetSize() == 9);
assert(myLLC.GetNth(0, val) == true);
assert(val == 1);
assert(myLLC.GetNth(1, val) == true);
assert(val == 9);
assert(myLLC.GetNth(2, val) == true);
assert(val == 10);
assert(myLLC.GetNth(3, val) == true);
assert(val == 12);
assert(myLLC.GetNth(4, val) == true);
assert(val == 15);
assert(myLLC.GetNth(5, val) == true);
assert(val == 18);
assert(myLLC.GetNth(6, val) == true);
assert(val == 19);
assert(myLLC.GetNth(7, val) == true);
assert(val == 20);
assert(myLLC.GetNth(8, val) == true);
assert(val == 25);
assert(myLLC.GetNth(9, val) == false);
}
//********************************************************************************
Side-talk of TDD:
In these 4 blogs for Linked List, I have really enjoyed and experienced the power of Test Driven Development (test implementation, production code implementation, regression testing, code refactoring and repeat the 4 steps. See TDD on wiki). Especially experience on the micro-cycle implementation of TDD. In my mind, TDD can be implemented in two different scopes, one (macro scope) is on the sprint/user-story scope and another (micro scope) is on the unit-test scope. I did enjoyed the TDD implementation on macro scope, because it is more about acceptance testing and serves a good indication against what the software is about to delivery. But I never enjoyed the micro scope because I thought is was too tedious and time-consuming. Time-consuming was always my excuse not to do so by arguing not having enough resource/time.
But in these four blogs I found the power and joy of micro implementation of TDD. One of good example is to decide passing a pointer to pointer "**" or a pointer "*" to LinkedListElement as the argument, as I mentioned this issue on Data Structure and Algorithm - Linked List: Common API. The same function, for instance "LL_PushFront", depends on the setup of the test. By passing a pointer "*" this function will work as expected, if the "head" is not empty/nullptr. But if it is an empty list ("head" is nullptr), then passing a pointer "*" to LinkedListElement will not work and it has to pass as a pointer to a pointer "**" to LinkedListElement because it is to change the value of "head" when the Linked List becomes from empty to non-empty. This kinds of design errors can be easily spotted by TDD in a very intuitive sense by adding tiny tests one by one. Otherwise it may take some seriously debugging. I have to say from now on I will adopt this idiom.
Bibliography:
[1] http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
[2] Glenn W. Rowe, Data Structure & Algorithm C++, Prentice Hall, 1996
[3] http://en.wikipedia.org/wiki/Test-driven_development
[4] http://en.cppreference.com/w/cpp/container/forward_list
[1] http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
[2] Glenn W. Rowe, Data Structure & Algorithm C++, Prentice Hall, 1996
[3] http://en.wikipedia.org/wiki/Test-driven_development
[4] http://en.cppreference.com/w/cpp/container/forward_list
No comments:
Post a Comment