I believe that I am finished with the implementation and testing of the DoubleLinkList class using templates in C++. At this point I should be able to start using the class. Hope to get to that sometime this weekend.
Following is the screen capture of a console displayed on my Windows
machine using Visual Studio 2013 while running the test code for double linked lists:
main <<< testing widgets ... main <<< widget: this: 0x9f084fe998 id: 1234 name ==>widget_1234<== main <<< testing nodes ... main <<< node: this: 0x9f084fea50 next: 0x0 prev: 0x0 main <<< widget: this: 0x9f084fea58 id: 1234 name ==>widget_1234<== main <<< n this: 0x286723c0430 next: 0x0 prev: 0x0 data: 1 main <<< crudeList this: 0x286723c0430 next: 0x286723c0430 prev: 0x286723c0430 data: 1 main <<< n this: 0x286723c0ff0 next: 0x0 prev: 0x0 data: 2 main <<< crudeList this: 0x286723c0430 next: 0x286723c0ff0 prev: 0x286723c0ff0 data: 1 main <<< n this: 0x286723c1110 next: 0x0 prev: 0x0 data: 3 main <<< crudeList this: 0x286723c0430 next: 0x286723c0ff0 prev: 0x286723c1110 data: 1 main <<< n this: 0x286723c0530 next: 0x0 prev: 0x0 data: 4 main <<< crudeList this: 0x286723c0430 next: 0x286723c0ff0 prev: 0x286723c0530 data: 1 main <<< n this: 0x286723c1230 next: 0x0 prev: 0x0 data: 5 main <<< crudeList this: 0x286723c0430 next: 0x286723c0ff0 prev: 0x286723c1230 data: 1 main <<< p this: 0x286723c0430 next: 0x286723c0ff0 prev: 0x286723c1230 data: 1 main <<< p this: 0x286723c0ff0 next: 0x286723c1110 prev: 0x286723c0430 data: 2 main <<< p this: 0x286723c1110 next: 0x286723c0530 prev: 0x286723c0ff0 data: 3 main <<< p this: 0x286723c0530 next: 0x286723c1230 prev: 0x286723c1110 data: 4 main <<< p this: 0x286723c1230 next: 0x286723c0430 prev: 0x286723c0530 data: 5 main <<< testing link list ... main <<< list: this: 0x286723c12b0 count: 0 maxCount: 13 head: 0x286723c12b0 tail: 0x286723c12b0 main <<< enqueue widget: this: 0x9f084feca8 id: 1 name ==>widget_1<== main <<< enqueue widget: this: 0x9f084feca8 id: 2 name ==>widget_2<== main <<< enqueue widget: this: 0x9f084feca8 id: 3 name ==>widget_3<== main <<< enqueue widget: this: 0x9f084feca8 id: 4 name ==>widget_4<== main <<< enqueue widget: this: 0x9f084feca8 id: 5 name ==>widget_5<== main <<< list: this: 0x286723c12b0 count: 5 maxCount: 13 head: 0x286723c16a0 tail: 0x286723c1c20 p: 0x286723c16a0 data: this: 0x286723c16a8 id: 1 name ==>widget_1<== next: 0x286723c1860 p: 0x286723c1860 data: this: 0x286723c1868 id: 2 name ==>widget_2<== next: 0x286723c19a0 p: 0x286723c19a0 data: this: 0x286723c19a8 id: 3 name ==>widget_3<== next: 0x286723c1ae0 p: 0x286723c1ae0 data: this: 0x286723c1ae8 id: 4 name ==>widget_4<== next: 0x286723c1c20 p: 0x286723c1c20 data: this: 0x286723c1c28 id: 5 name ==>widget_5<== next: 0x286723c12b0 main <<< dequeue widget: this: 0x9f084fed90 id: 1 name ==>widget_1<== main <<< dequeue widget: this: 0x9f084fed90 id: 2 name ==>widget_2<== main <<< dequeue widget: this: 0x9f084fed90 id: 3 name ==>widget_3<== main <<< dequeue widget: this: 0x9f084fed90 id: 4 name ==>widget_4<== main <<< dequeue widget: this: 0x9f084fed90 id: 5 name ==>widget_5<== main <<< enqueue widget: this: 0x9f084fe998 id: 1 name ==>widget_1<== main <<< enqueue widget: this: 0x9f084fe998 id: 2 name ==>widget_2<== main <<< enqueue widget: this: 0x9f084fe998 id: 3 name ==>widget_3<== main <<< head: this: 0x9f084feec0 id: 1 name ==>widget_1<== main <<< tail: this: 0x9f084fef20 id: 3 name ==>widget_3<== main <<< count: 3 j: 0 p: this: 0x286723c1620 next: 0x286723c17e0 prev: 0x0 main <<< insertAfter widget: this: 0x9f084ff058 id: 4 name ==>widget_4<== main <<< count: 4 j: 0 p: this: 0x286723c1620 next: 0x286723c1a60 prev: 0x0 main <<< insertAfter widget: this: 0x9f084ff058 id: 5 name ==>widget_5<== main <<< count: 5 j: 3 p: this: 0x286723c17e0 next: 0x286723c1920 prev: 0x286723c1a60 main <<< insertAfter widget: this: 0x9f084ff058 id: 6 name ==>widget_6<== main <<< count: 6 j: 0 p: this: 0x286723c1620 next: 0x286723c1c20 prev: 0x0 main <<< insertAfter widget: this: 0x9f084ff058 id: 7 name ==>widget_7<== main <<< count: 7 j: 3 p: this: 0x286723c1a60 next: 0x286723c17e0 prev: 0x286723c1c20 main <<< insertAfter widget: this: 0x9f084ff058 id: 8 name ==>widget_8<== main <<< count: 8 j: 0 p: this: 0x286723c1620 next: 0x286723c1ea0 prev: 0x0 main <<< insertAfter widget: this: 0x9f084ff058 id: 9 name ==>widget_9<== main <<< count: 9 j: 1 p: this: 0x286723c2120 next: 0x286723c1ea0 prev: 0x286723c1620 main <<< insertAfter widget: this: 0x9f084ff058 id: 10 name ==>widget_10<== main <<< count: 10 j: 3 p: this: 0x286723c1ea0 next: 0x286723c1c20 prev: 0x286723c2260 main <<< insertAfter widget: this: 0x9f084ff058 id: 11 name ==>widget_11<== main <<< count: 11 j: 9 p: this: 0x286723c1d60 next: 0x286723c1920 prev: 0x286723c17e0 main <<< insertAfter widget: this: 0x9f084ff058 id: 12 name ==>widget_12<== main <<< count: 12 j: 8 p: this: 0x286723c17e0 next: 0x286723c1d60 prev: 0x286723c1fe0 main <<< insertAfter widget: this: 0x9f084ff058 id: 13 name ==>widget_13<== main <<< list->isFull i: 11 main <<< list: this: 0x286723c12b0 count: 13 maxCount: 13 head: 0x286723c1620 tail: 0x286723c1920 p: 0x286723c1620 data: this: 0x286723c1628 id: 1 name ==>widget_1<== next: 0x286723c2120 p: 0x286723c2120 data: this: 0x286723c2128 id: 9 name ==>widget_9<== next: 0x286723c2260 p: 0x286723c2260 data: this: 0x286723c2268 id: 10 name ==>widget_10<== next: 0x286723c1ea0 p: 0x286723c1ea0 data: this: 0x286723c1ea8 id: 7 name ==>widget_7<== next: 0x286723c23a0 p: 0x286723c23a0 data: this: 0x286723c23a8 id: 11 name ==>widget_11<== next: 0x286723c1c20 p: 0x286723c1c20 data: this: 0x286723c1c28 id: 5 name ==>widget_5<== next: 0x286723c1a60 p: 0x286723c1a60 data: this: 0x286723c1a68 id: 4 name ==>widget_4<== next: 0x286723c1fe0 p: 0x286723c1fe0 data: this: 0x286723c1fe8 id: 8 name ==>widget_8<== next: 0x286723c17e0 p: 0x286723c17e0 data: this: 0x286723c17e8 id: 2 name ==>widget_2<== next: 0x286723c2620 p: 0x286723c2620 data: this: 0x286723c2628 id: 13 name ==>widget_13<== next: 0x286723c1d60 p: 0x286723c1d60 data: this: 0x286723c1d68 id: 6 name ==>widget_6<== next: 0x286723c24e0 p: 0x286723c24e0 data: this: 0x286723c24e8 id: 12 name ==>widget_12<== next: 0x286723c1920 p: 0x286723c1920 data: this: 0x286723c1928 id: 3 name ==>widget_3<== next: 0x286723c12b0 main <<< pop widget: this: 0x9f084fe998 id: 3 name ==>widget_3<== main <<< pop widget: this: 0x9f084fe998 id: 12 name ==>widget_12<== main <<< pop widget: this: 0x9f084fe998 id: 6 name ==>widget_6<== main <<< pop widget: this: 0x9f084fe998 id: 13 name ==>widget_13<== main <<< pop widget: this: 0x9f084fe998 id: 2 name ==>widget_2<== main <<< pop widget: this: 0x9f084fe998 id: 8 name ==>widget_8<== main <<< pop widget: this: 0x9f084fe998 id: 4 name ==>widget_4<== main <<< pop widget: this: 0x9f084fe998 id: 5 name ==>widget_5<== main <<< pop widget: this: 0x9f084fe998 id: 11 name ==>widget_11<== main <<< pop widget: this: 0x9f084fe998 id: 7 name ==>widget_7<== main <<< pop widget: this: 0x9f084fe998 id: 10 name ==>widget_10<== main <<< pop widget: this: 0x9f084fe998 id: 9 name ==>widget_9<== main <<< pop widget: this: 0x9f084fe998 id: 1 name ==>widget_1<== main <<< enqueue widget: this: 0x9f084fe998 id: 1 name ==>widget_1<== main <<< insertBefore widget: this: 0x9f084ff2b8 id: 2 name ==>widget_2<== main <<< insertBefore widget: this: 0x9f084ff2b8 id: 3 name ==>widget_3<== main <<< insertBefore widget: this: 0x9f084ff2b8 id: 4 name ==>widget_4<== main <<< insertBefore widget: this: 0x9f084ff2b8 id: 5 name ==>widget_5<== main <<< insertBefore widget: this: 0x9f084ff2b8 id: 6 name ==>widget_6<== main <<< insertBefore widget: this: 0x9f084ff2b8 id: 7 name ==>widget_7<== main <<< insertBefore widget: this: 0x9f084ff2b8 id: 8 name ==>widget_8<== main <<< insertBefore widget: this: 0x9f084ff2b8 id: 9 name ==>widget_9<== main <<< insertBefore widget: this: 0x9f084ff2b8 id: 10 name ==>widget_10<== main <<< insertBefore widget: this: 0x9f084ff2b8 id: 11 name ==>widget_11<== main <<< list: this: 0x286723c12b0 count: 11 maxCount: 13 head: 0x286723c1ea0 tail: 0x286723c15a0 p: 0x286723c1ea0 data: this: 0x286723c1ea8 id: 7 name ==>widget_7<== next: 0x286723c1d60 p: 0x286723c1d60 data: this: 0x286723c1d68 id: 6 name ==>widget_6<== next: 0x286723c2260 p: 0x286723c2260 data: this: 0x286723c2268 id: 10 name ==>widget_10<== next: 0x286723c1fe0 p: 0x286723c1fe0 data: this: 0x286723c1fe8 id: 8 name ==>widget_8<== next: 0x286723c17e0 p: 0x286723c17e0 data: this: 0x286723c17e8 id: 2 name ==>widget_2<== next: 0x286723c1ae0 p: 0x286723c1ae0 data: this: 0x286723c1ae8 id: 4 name ==>widget_4<== next: 0x286723c23a0 p: 0x286723c23a0 data: this: 0x286723c23a8 id: 11 name ==>widget_11<== next: 0x286723c1c20 p: 0x286723c1c20 data: this: 0x286723c1c28 id: 5 name ==>widget_5<== next: 0x286723c2120 p: 0x286723c2120 data: this: 0x286723c2128 id: 9 name ==>widget_9<== next: 0x286723c19a0 p: 0x286723c19a0 data: this: 0x286723c19a8 id: 3 name ==>widget_3<== next: 0x286723c15a0 p: 0x286723c15a0 data: this: 0x286723c15a8 id: 1 name ==>widget_1<== next: 0x286723c12b0 main <<< push widget: this: 0x9f084fe998 id: 1 name ==>widget_1<== main <<< push widget: this: 0x9f084fe998 id: 2 name ==>widget_2<== main <<< push widget: this: 0x9f084fe998 id: 3 name ==>widget_3<== main <<< push widget: this: 0x9f084fe998 id: 4 name ==>widget_4<== main <<< push widget: this: 0x9f084fe998 id: 5 name ==>widget_5<== main <<< push widget: this: 0x9f084fe998 id: 6 name ==>widget_6<== main <<< push widget: this: 0x9f084fe998 id: 7 name ==>widget_7<== main <<< push widget: this: 0x9f084fe998 id: 8 name ==>widget_8<== main <<< list: this: 0x286723c12b0 count: 8 maxCount: 13 head: 0x286723c16a0 tail: 0x286723c1fe0 p: 0x286723c16a0 data: this: 0x286723c16a8 id: 1 name ==>widget_1<== next: 0x286723c1860 p: 0x286723c1860 data: this: 0x286723c1868 id: 2 name ==>widget_2<== next: 0x286723c19a0 p: 0x286723c19a0 data: this: 0x286723c19a8 id: 3 name ==>widget_3<== next: 0x286723c1ae0 p: 0x286723c1ae0 data: this: 0x286723c1ae8 id: 4 name ==>widget_4<== next: 0x286723c1c20 p: 0x286723c1c20 data: this: 0x286723c1c28 id: 5 name ==>widget_5<== next: 0x286723c1d60 p: 0x286723c1d60 data: this: 0x286723c1d68 id: 6 name ==>widget_6<== next: 0x286723c1ea0 p: 0x286723c1ea0 data: this: 0x286723c1ea8 id: 7 name ==>widget_7<== next: 0x286723c1fe0 p: 0x286723c1fe0 data: this: 0x286723c1fe8 id: 8 name ==>widget_8<== next: 0x286723c12b0 main <<< pop widget: this: 0x9f084ff4f8 id: 8 name ==>widget_8<== main <<< pop widget: this: 0x9f084ff4f8 id: 7 name ==>widget_7<== main <<< pop widget: this: 0x9f084ff4f8 id: 6 name ==>widget_6<== main <<< pop widget: this: 0x9f084ff4f8 id: 5 name ==>widget_5<== main <<< pop widget: this: 0x9f084ff4f8 id: 4 name ==>widget_4<== main <<< pop widget: this: 0x9f084ff4f8 id: 3 name ==>widget_3<== main <<< pop widget: this: 0x9f084ff4f8 id: 2 name ==>widget_2<== main <<< pop widget: this: 0x9f084ff4f8 id: 1 name ==>widget_1<== main <<< count: 0
The test code in C++ follows:
// **** ****
#include <iostream>
#include <time.h>
// **** ****
using namespace std;
// **** header files (templates contain actual implementations) ****
#include "Widget.h"
#include "Node.h"
#include "SingleLinkList.h"
#include "DoubleLinkList.h"
#include "Solution.h"
// **** constructor ****
Solution::Solution()
{}
// **** destructor ****
Solution::~Solution()
{}
/*
* TEST code.
*/
int main()
{
// **** constant(s) ****
const int MAX_ELEMENTS = 13;
// **** ****
char buffer[BUFSIZ];
errno_t error = 0;
// ***** activity message ****
cout << "main <<< testing widgets ..." << endl;
// **** create a new Widget ****
Widget widget = Widget();
// **** populate widget ****
try {
widget.setId(1234);
} catch (int ex) {
if (ex == widget.WidgetInvalidId) {
cerr << "main <<< EXCEPTION widget.setId() - WidgetInvalidId" << endl;
exit(ex);
}
}
try {
widget.setName("widget_1234");
} catch (int ex) {
if (ex == widget.WidgetInvalidName) {
cerr << "main <<< EXCEPTION widget.setName() - WidgetInvalidName" << endl;
exit(ex);
}
}
// **** display the widget ****
cout << "main <<< widget: " << widget.toString() << endl;
// ***** activity message ****
cout << endl;
cout << "main <<< testing nodes ..." << endl;
// **** instantiate a node ****
Node<Widget> node = Node<Widget>(widget);
// **** display the node ****
cout << "main <<< node: " << node.toString() << endl;
// **** display the widget ****
cout << "main <<< widget: " << node.data.toString() << endl;
cout << endl;
// **** build a crude list of nodes ****
Node<int> *crudeList = nullptr;
for (int i = 1; i <= 5; i++) {
// **** allocate a node ****
Node<int> *n = new Node<int>(i);
cout << "main <<< n " << n->toString() << " data: " << n->data << endl; // **** if list is emply then this node becomes the list (poor practice) **** if (crudeList == nullptr) { crudeList = n; n->next = crudeList;
n->prev = crudeList;
}
// **** else insert the node at the tail of the list ****
else {
Node<int> *p = crudeList;
for ( ; p->next != crudeList; p = p->next) {}
p->next = n;
n->next = crudeList;
n->prev = p;
crudeList->prev = n;
}
// **** display the crudeList node ****
cout << "main <<< crudeList " << crudeList->toString() << " data: " << crudeList->data << endl;
}
cout << endl;
// **** traverse the crude list of nodes ****
for (Node<int> *p = crudeList; true; p = p->next)
{
cout << "main <<< p " << p->toString() << " data: " << p->data << endl; if (p->next == crudeList) {
break;
}
}
cout << endl;
// **** delete all elements from the crude list of nodes ****
for (Node<int> *p = crudeList; p != crudeList; ) {
Node<int> *n = p;
p = p->next;
cout << "main <<< deleting: " << n->data << endl;
delete(n);
}
// ***** activity message ****
cout << "main <<< testing link list ..." << endl;
// **** allocate a linked list ****
//SingleLinkList<Widget> *list = new SingleLinkList<Widget>(MAX_ELEMENTS);
DoubleLinkList<Widget> *list = new DoubleLinkList<Widget>(MAX_ELEMENTS);
cout << "main <<< list: " << list->toString() << endl;
// **** loop inserting elements into the queue ****
for (int i = 1; i <= 5; i++) { // **** check if queue is full **** if (list->isFull()) {
cout << "main <<< list->isFull() i: " << i << endl;
continue;
}
// **** set the widget to be inserted into the queue ****
int status = _itoa_s(i, buffer, sizeof(buffer), 10);
string widgetName = "widget_" + string(buffer);
Widget widget = Widget(i, widgetName);
cout << "main <<< enqueue widget: " << widget.toString() << endl; // ***** enqueue widget **** try { list->enqueue(widget);
} catch (const int ex) {
cerr << "main <<< EXCEPTION - list->enqueue(widget) ex: " << ex << endl;
exit(ex);
}
}
cout << "main <<< list: " << list->toString() << endl << endl; // **** loop removing elements from the queue **** while (!list->isEmpty()) {
cout << "main <<< dequeue widget: " << list->dequeue().toString() << endl;
}
cout << endl;
// **** insert some widgets into the queue ****
for (int i = 1; i <= 3; i++) { // **** check if queue is full **** if (list->isFull())
{
cout << "main <<< list->isFull() i: " << i << endl;
continue;
}
// **** create a widget ****
int status = _itoa_s(i, buffer, sizeof(buffer), 10);
string widgetName = "widget_" + string(buffer);
widget = Widget(i, widgetName);
cout << "main <<< enqueue widget: " << widget.toString() << endl; // **** enqueue the widget into the queue **** list->enqueue(widget);
}
cout << endl;
// **** peek at the head of queue ****
cout << "main <<< head: " << list->peekHead().toString() << endl;
// **** peek at the tail of the queue ****
cout << "main <<< tail: " << list->peekTail().toString() << endl << endl;
// **** seed the pseudo random number generator ****
srand((unsigned int)time(nullptr));
// **** insert after ****
int j = 0;
Node<Widget> *p = nullptr;
for (int i = 1; i <= 11; i++) { // **** check if queue is full **** if (list->isFull()) {
cerr << "main <<< list->isFull i: " << i << endl; continue; } // **** generate a random location in the queue **** try { j = rand() % list->getCount();
} catch (int ex) {
cerr << "main <<< EXCEPTION - rand() % list->getCount() ex: " << ex << endl; exit(ex); } // **** pointer to specified element in the queue **** p = list->elementAt(j);
cout << "main <<< count: " << list->getCount() << " j: " << j << " p: " << p->toString() << endl; // **** set a widget **** int widgetId = list->getCount() + 1;
int status = _itoa_s(widgetId, buffer, sizeof(buffer), 10);
string widgetName = "widget_" + string(buffer);
Widget widget = Widget(widgetId, widgetName);
cout << "main <<< insertAfter widget: " << widget.toString() << endl; // **** insert widget into the queue AFTER the specified element **** try { list->insertAfter(p, widget);
} catch (int ex) {
cerr << "main <<< EXCEPTION list->insertAfter() ex: " << ex << endl;
exit(ex);
}
}
cout << endl;
// **** display the list ****
cout << "main <<< list: " << list->toString() << endl << endl; // **** POP from the tail of the queue (all widgets) **** while (!list->isEmpty()) {
widget = list->pop();
cout << "main <<< pop widget: " << widget.toString() << endl;
}
cout << endl; // **** set the widget **** widget = Widget(1, "widget_1"); // **** enqueue the widget **** list->enqueue(widget);
cout << "main <<< enqueue widget: " << widget.toString() << endl;
// **** insert BEFORE ****
for (int i = 2; i <= 11; i++) { // **** check if queue is empty **** if (list->isEmpty()) {
cout << "main <<< list->isEmpty i: " << i << endl; continue; } // **** check if queue is full **** if (list->isFull())
{
cout << "main <<< list->isFull i: " << i << endl;
continue;
}
// **** location to insert before in queue (for starters) ****
Node<Widget> *p = nullptr;
// **** generate a random location in the queue ****
try {
j = rand() % list->getCount();
} catch (int ex) {
cerr << "main <<< EXCEPTION - rand() % list->getCount() ex: " << ex << endl; exit(ex); } // **** point to an element in the queue **** try { p = list->elementAt(j);
} catch (int ex) {
cout << "main <<< EXCEPTION list->elementAt j: " << j << " ex: " << ex << endl; exit(ex); } // **** create a widget **** int widgetId = list->getCount() + 1;
int status = _itoa_s(widgetId, buffer, sizeof(buffer), 10);
string widgetName = "widget_" + string(buffer);
Widget widget = Widget(widgetId, widgetName);
cout << "main <<< insertBefore widget: " << widget.toString() << endl; // **** insert widget into the queue BEFORE the specified element **** try { list->insertBefore(p, widget);
}
catch (int ex)
{
cerr << "main <<< EXCEPTION list->insertBefore p:" << p->toString() << " ex: " << ex << endl;
exit(ex);
}
}
// **** display the list ****
cout << "main <<< list: " << list->toString() << endl << endl; // **** clear the queue **** while (!list->isEmpty()) {
list->dequeue();
}
// **** push elements on the stack (queue) ****
for (int i = 0; i <= 7; i++) { // **** check if the stack is full **** if (list->isFull()) {
cout << "main <<< list->isFull i: " << i << endl; continue; } // **** create a widget **** int widgetId = list->getCount() + 1;
int status = _itoa_s(widgetId, buffer, sizeof(buffer), 10);
string widgetName = "widget_" + string(buffer);
widget = Widget(widgetId, widgetName);
cout << "main <<< push widget: " << widget.toString() << endl; // **** push the widget on to the stack (queue) **** list->push(widget);
}
// **** display the list ****
cout << "main <<< list: " << list->toString() << endl << endl; // **** pop elements from the stack (queue) **** while (!list->isEmpty()) {
cout << "main <<< pop widget: " << list->pop().toString() << endl;
}
cout << endl;
// **** display the count of elements in the list ****
cout << "main <<< count: " << list->getCount() << endl;
// **** all done ****
return 0;
}
The C++ code for the DoubleLinkList class using templates follows:
#pragma once
// **** ****
#include <string>
// **** ****
#include "Node.h"
// **** vvvv class definition vvvv ****
template <typename T>
class DoubleLinkList
{
// **** constants ****
public:
const int QueueIsFull = -1;
const int QueueIsEmpty = -2;
const int QueueInvalidLocation = -3;
const int QueueNullPointer = -4;
const int QueueInvalidPointer = -5;
const int QueueInvalidMaxCount = -6;
// **** members ****
private:
int count;
int maxCount;
Node<T> *head;
Node<T> *tail;
// **** constructor ****
public:
DoubleLinkList();
// **** constructor ****
public:
DoubleLinkList(int maxElements);
// **** destructor ****
public:
~DoubleLinkList();
// **** list of getters ****
public:
Node<T> *DoubleLinkList<T>::getHead();
public:
int DoubleLinkList<T>::getCount();
public:
Node<T> *DoubleLinkList<T>::getTail();
// **** list of setters ****
// **** generate string for the specified queue object ****
public:
std::string DoubleLinkList<T>::toString();
// **** enqueue element at tail of queue ****
public:
void DoubleLinkList<T>::enqueue(T myData);
// **** check if queue is full ****
public:
bool DoubleLinkList<T>::isFull();
// **** check if queue is empty ****
public:
bool DoubleLinkList<T>::isEmpty();
// **** dequeue element at head of queue ****
public:
T DoubleLinkList<T>::dequeue();
// ***** peek at the head element of the queue ****
public:
T DoubleLinkList<T>::peekHead();
// **** peek at the tail of the queue ****
public:
T DoubleLinkList<T>::peekTail();
// **** return a pointer to the element in the queue at the specified location ****
public:
Node<T> *DoubleLinkList<T>::elementAt(int loc);
// **** insert element AFTER specified element ****
public:
void DoubleLinkList<T>::insertAfter(Node<T> *p, T myData);
// **** check if pointer points to element in this queue ****
public:
bool DoubleLinkList<T>::isValidPointer(Node<T> *p);
// **** pop element from head of queue (FIFO - stack) ****
public:
T DoubleLinkList<T>::pop();
// **** insert new element BEFORE specified element ****
public:
void DoubleLinkList<T>::insertBefore(Node<T> *p, T myData);
// **** PUSH an element into a queue (stack) ****
public:
void DoubleLinkList<T>::push(T myData);
};
// **** vvvv class implementation vvvv ****
/*
Base constructor.
*/
template <typename T>
DoubleLinkList<T>::DoubleLinkList()
{
count = 0;
maxCount = 0;
head = (Node<T> *)this;
tail = (Node<T> *)this;
}
/*
Constructor indicating max count of element is the queue.
*/
template <typename T>
DoubleLinkList<T>::DoubleLinkList(int maxElements)
{
// **** check if the max number of elements is invalid ****
if (maxElements < 0)
{
throw QueueInvalidMaxCount;
}
// **** ****
count = 0;
maxCount = maxElements;
head = (Node<T> *)this;
tail = (Node<T> *)this;
}
/*
Base destructor.
*/
template <typename T>
DoubleLinkList<T>::~DoubleLinkList()
{}
/*
Build a string representation of the queue and it's elements.
*/
template <typename T>
std::string DoubleLinkList<T>::toString()
{
std::string str = "";
char buffer[64];
int status;
// **** collect data from the queue ****
status = _ui64toa_s((long long)this, buffer, sizeof(buffer), 16);
str += "this: 0x" + std::string(buffer);
status = _itoa_s(count, buffer, sizeof(buffer), 10);
str += " count: " + std::string(buffer);
status = _itoa_s(maxCount, buffer, sizeof(buffer), 10);
str += " maxCount: " + std::string(buffer);
status = _ui64toa_s((long long)head, buffer, sizeof(buffer), 16);
str += " head: 0x" + std::string(buffer);
status = _ui64toa_s((long long)tail, buffer, sizeof(buffer), 16);
str += " tail: 0x" + std::string(buffer);
// **** collect data from the queue elements ****
for (Node<T> *p = this->head; p != (Node<T> *)this; p = p->next)
{
str += "\n";
status = _ui64toa_s((long long)p, buffer, sizeof(buffer), 16);
str += "\t\tp: 0x" + std::string(buffer);
str += " data: " + (p->data).toString();
status = _ui64toa_s((long long)p->next, buffer, sizeof(buffer), 16);
str += " next: 0x" + std::string(buffer);
}
// **** ****
return str;
}
/*
Enqueue element at the tail of the queue.
The queue maintains a FIFO order (enqueue & dequeue).
*/
template <typename T>
void DoubleLinkList<T>::enqueue(T myData)
{
// **** check if queue is full ****
if ((maxCount != 0) && (count >= maxCount))
{
throw QueueIsFull;
}
// **** allocate new node ****
Node<T> *node = new Node<T>(myData);
// **** insert node in empty queue ****
if (DoubleLinkList<T>::count == 0)
{
DoubleLinkList<T>::head = node;
DoubleLinkList<T>::tail = node;
}
// **** insert new element at the tail of the queue ****
else
{
DoubleLinkList<T>::tail->next = node;
node->prev = DoubleLinkList<T>::tail;
}
// **** ****
node->next = (Node<T> *)this;
DoubleLinkList<T>::tail = node;
DoubleLinkList<T>::count++;
}
/*
Determine if the queue is FULL.
Same but less elegant approach could be achieved with getCount() and a test.
*/
template <typename T>
bool DoubleLinkList<T>::isFull()
{
return (count >= maxCount);
}
/*
Determine if the queue is EMPTY.
Same but less elegant approach could be achieved with getCount() and a test.
*/
template <typename T>
bool DoubleLinkList<T>::isEmpty()
{
return (count <= 0);
}
/*
Dequeue element at head of queue.
The queue maintains a FIFO order (enqueue & dequeue).
*/
template <typename T>
T DoubleLinkList<T>::dequeue()
{
// **** check if the queue is empty ****
if (count <= 0)
{
throw QueueIsEmpty;
}
// **** for ease of use ****
Node<T> *node = head;
// **** get the data from the head node ****
T data = node->data;
// **** update the head ****
head = head->next;
// **** first remaining node points to the queue ****
node->next->prev = (Node<T> *)this;
// **** free (head) node ****
delete(node);
// **** decrement queue count ****
count--;
// **** update tail (queue is empty) ****
if (count == 0)
{
head = (Node<T> *)this;
tail = (Node<T> *)this;
}
// **** return data ****
return data;
}
/*
Return the element at the HEAD of the queue.
Throws exception if queue is empty.
*/
template <typename T>
T DoubleLinkList<T>::peekHead()
{
if (count <= 0) { throw QueueIsEmpty; } else { return this->head->data;
}
}
/*
Return the element at the TAIL of the queue.
Throws exception if queue is empty.
*/
template <typename T>
T DoubleLinkList<T>::peekTail()
{
if (count <= 0) { throw QueueIsEmpty; } else { return this->tail->data;
}
}
/*
Get the element at the HEAD of the queue.
Element is not removed from the queue.
*/
template <typename T>
Node<T> *DoubleLinkList<T>::getHead()
{
return head;
}
/*
Get the count of elements in the queue.
*/
template <typename T>
int DoubleLinkList<T>::getCount()
{
return count;
}
/*
Get the TAIL from the queue.
Element is not removed from the queue.
*/
template <typename T>
Node<T> *DoubleLinkList<T>::getTail()
{
return tail;
}
/*
Return a pointer to the element in the queue at the specified location.
The first element in a non-empty queue is at location 0.
*/
template <typename T>
Node<T> *DoubleLinkList<T>::elementAt(int loc)
{
// **** check if queue is empty ****
if (count <= 0) {
throw QueueIsEmpty;
}
// **** check if location is out of range ****
if ((loc < 0) || (loc > count))
{
throw QueueInvalidLocation;
}
// **** traverse the queue until the specified element is reached ****
Node<T> *p = head;
for (int i = 0; i < loc; i++) { p = p->next;
}
// **** ****
return p;
}
/*
Insert the specified element AFTER the specified one.
*/
template <typename T>
void DoubleLinkList<T>::insertAfter(Node<T> *p, T myData)
{
// **** check if queue is full ****
if ((maxCount != 0) && (count >= maxCount))
{
throw QueueIsFull;
}
// **** check for null pointer ****
if (p == nullptr)
{
throw QueueNullPointer;
}
// **** check if specified pointer is NOT in the queue ****
if (!isValidPointer(p))
{
throw QueueInvalidPointer;
}
// **** allocate new node ****
Node<T> *node = new Node<T>(myData);
// **** insert new element after the specified one ****
node->next = p->next;
node->prev = p;
p->next->prev = node;
p->next = node;
// **** update the queue ****
if (p == tail)
{
tail = node;
}
count++;
}
/*
Check if the specified pointer a valid pointer in this queue.
*/
template<typename T>
bool DoubleLinkList<T>::isValidPointer(Node<T> *p)
{
// **** check for null pointer ****
if (p == nullptr)
{
throw QueueNullPointer;
}
// **** traverse the queue looking for the specified pointer ****
for (Node<T> *q = head; q != (Node<T> *)this; q = q->next)
{
if (q == p)
{
// **** node found ****
return true;
}
}
// **** node NOT found ****
return false;
}
/*
Pop the element at tail of the queue.
A queue maintains a FIFO order (enqueue & dequeue).
A stack (implemented as a queue) maintains a FILO order (push & pop).
*/
template <typename T>
T DoubleLinkList<T>::pop()
{
// **** check if the queue is empty ****
if (count <= 0)
{
throw QueueIsEmpty;
}
// **** for ease of use ****
Node<T> *node = tail;
// **** get the data (to be returned) from the tail node ****
T data = node->data;
// **** queue has a single element at this time ****
if (count == 1)
{
head = (Node<T> *)this;
tail = (Node<T> *)this;
}
// **** queue has more than one element at this time ****
else
{
tail = tail->prev;
tail->next = (Node<T> *)this;
}
// **** free (previous tail) node ****
delete(node);
// **** decrement queue count ****
count--;
// **** return value ****
return data;
}
/*
Insert the specified element BEFORE the specified one.
*/
template <typename T>
void DoubleLinkList<T>::insertBefore(Node<T> *p, T myData)
{
// **** check if queue is full ****
if ((maxCount != 0) && (count >= maxCount))
{
throw QueueIsFull;
}
// **** check for null pointer ****
if (p == nullptr)
{
throw QueueNullPointer;
}
// **** check if specified pointer is NOT in the queue ****
if (!isValidPointer(p))
{
throw QueueInvalidPointer;
}
// **** allocate new node ****
Node<T> *node = new Node<T>(myData);
// **** node being inserted BEFORE p ****
node->next = p;
node->prev = p->prev;
// **** insert BEFORE head node ****
if (p == head)
{
head = node;
}
// **** insert somewhere else ****
else
{
p->prev->next = node;
}
p->prev = node;
// **** update the queue count ****
count++;
}
/*
PUSH and element into a stack (implemented as a queue).
*/
template <typename T>
void DoubleLinkList<T>::push(T myData)
{
enqueue(myData);
}
As usual, I have made changes to the test and the DoubleLinkList class code based on what I was experiencing during development. For example, when invoking the insertBefore(p, widget) method, a check is now made to verify that the queue is not empty. In addition, you will notice that the test code line: j = rand() % list->getCount(); is surrounded by a try / catch. This was done to prevent an exception if inserting into an empty queue.
I cannot emphasize how important is to always develop software using a test driven development (TDD) approach. The design of the code will improve in addition to making it very robust.
If you have comments or questions regarding this or any other post please do not hesitate and send me a message. Will replay as soon as possible and will not use your name unless you allow me to do so.
John
john.canessa@gmail.com
Follow me on Twitter: john_canessa