Objective

This assignment will provide practice with a doubly-linked list, along with practice on the basic concept of an iterator over a container.

Task

In your prior course, you probably saw an example of a singly-linked list. Here is a simple example of such a container, implemented as a template class:

Singly-Linked List class example

For this assignment you will implement a templated doubly-linked list class, along with an associated iterator class for helping with generic list traversals. In a doubly-linked list, each node has a pointer to the next node AND a pointer to the previous node. The following starter files are provided for you:

tnode.h -- fully defines a templated node class for use in a doubly-linked list. Note that the member data includes a data element, as well as pointers to the next and previous nodes.

tlist.h -- provides the declarations of the template classes TList (the linked list class) and TListIterator (an associated class to help with list traversal).

driver.cpp -- contains some sample test calls to the linked list, but should not be considered a complete or thorough set of tests. You will need to create more test cases to fully test your class features. This driver is provided to help illustrate some of the basic class features and concepts, including the use of iterators.

driver_output.txt -- contains the output from running the above sample driver program

Your job will be to finish this templated set of classes by defining each of the functions in the TList and TListIterator classes. These should be defined in a file called:

tlist.hpp

Note that there is already a #include at the bottom of tlist.h where your definition file will be brought in. This illustrates a pretty standard format for setting up a templated class. Note also that you should not #include your tlist.h file inside of the tlist.hpp file, because the latter is already included into the former -- you don't want to create circular and infinite #includes!

Iterators

The small class called TListIterator is a helper class that can be used in conjunction with the linked list class. This is a common feature used in container classes like this. The purpose of an iterator is to provide a common and non-implementation-specific way of traversing a container, so that mulitple containers could potentially use common algorithms (like sorting and searching functions, for example). This will be explored more in the course. For the iterator class in this assignment, here is a brief sample use:

 // suppose that L is a linked list storing ints, and it has // already been populated with the values 3, 6, 9, 12, 15, 18, 21 // this call would retrieve a list iterator over the container L TListIterator itr = L.GetIterator(); // at this point, itr currently is positioned at the first element in // the list (the 3). int x = itr.GetValue(); // x would now store 3 itr.Next(); // itr has advanced to the 6 int y = itr.GetValue(); // y would now store 6 itr.Next(); itr.Next(); // we have now advanced to the 12 int z = itr.GetValue(); // z now stores 12 itr.Previous(); // now we have moved backwards, to the 9 int a = itr.GetValue(); // a stores 9. etc. 

This class essentially helps us walk through the linked list in a fairly easy way, with calls to Next() and Previous() to move around.

Program Details

Here are general descriptions of the two classes you are to define, along with a general description of each function's task.

1) class TList

The member data of this class consists of pointers to the first and last nodes, a size variable, and a dummy variable of type T that can be used for error-checking situations. Specifically, some of the functions specify to return a stored data item, but if you encounter a situation like an empty list or other situation where there would not BE a valid data item, you can return a reference to the dummy object instead. This is needed because some such functions are pass-by-reference (so that the retrieved item can be modified by the caller under normal situations).

Function descriptions

Default constructor -- creates an empty linked list

TList(T val, int num) -- creates a linked list containing "num" copies of the data element "val"

Clear -- clear out the list, resetting it to an empty list

Big Five

Destructor -- appropriate clean-up of list, no memory leaks

Copy constructor -- deep copy

Copy assignment operator -- deep copy

Move constructor -- constructor with standard move semantics

Move assignment operator -- assignment with standard move semantics

Accessors

IsEmpty -- returns true if the list is empty, false otherwise

GetSize -- returns the size (number of data elements) in the list

GetFirst -- returns the data element in the first node (by reference)

GetLast -- returns the data element in the last node (by reference)

Note that error situations in the last two functions would occur if the list was empty (this what the "dummy" item is for). Endpoint insert/removes

InsertFront -- insert the data (parameter) as the first node in the list

InsertBack -- insert the data (parameter) as the last node in the list

RemoveFront -- remove the first element in the list. If the list is empty, just leave it empty

RemoveBack -- remove the last element in the list. If the list is empty, just leave it empty

Iterator retrieval

GetIterator -- create and return an iterator that is positioned on the first node in the list. If list is empty, return default iterator

GetIteratorEnd -- create and return an iterator that is positioned on the last node in the list. If list is empty, return default iterator

Insert (2 parameters) The new data element (second parameter) should be inserted into the linked list just before the position given by the iterator (the first parameter). If the list is empty, just insert the single item. If the iterator doesn't refer to a node, insert the item at the end of the list.

Remove (1 parameter) This function should remove the data item that is given by the iterator (the parameter). The function should return an iterator to the node that is after the one that was just deleted. If the initial list was empty, there's nothing to delete -- so just leave it empty and return a default iterator.

Print Should print the entire list contents, front to back, separated by the delimiter given in the second parameter. This function may assume that the stored type T has an available insertion << operator available for printing. Print to the stream given in the first parameter.

operator+ This is a standalone function that should return a TList object that is the result of concatenating two TList objects together -- in parameter order. See driver.cpp program for examples.

2) class TListIterator

The TListIterator class has only one member data variable -- a pointer to the Node to which it currently refers (we'll call this the current node in the function descriptions below).

Default constructor -- a default iterator should just store the nunll pointer internally.

HasNext -- returns true if there is another node after the current node, false otherwise

HasPrevious -- returns true if there is another node before the current node, false otherwise

Next -- advances the iterator to the next node after the current one. Returns an iterator to the new position.

Previous -- moves the iterator to the previous node (before the current one). Returns an iterator to the new position.

GetData -- return the data item at the current node. If the iterator is not pointing to a node (i.e. null pointer), you can use the "dummy" that was defined previously. Note that this is a return by reference.

Define all of the functions for these two classes in the file tlist.hpp

3) Test Program

Create a test program of your own in the file mydriver.cpp. You can use my provided driver.cpp as a general model of how to populate a linked list. Your test program should contain the following tests/illustrations at a minimum:

Tests of all of the functions

Tests that involve Linked Lists of at least two different stored types. Suggested types: int, double, char, string

At least 10 tests of each of the following

InsertFront

InsertBack

RemoveFront

RemoveBack

Insert (iterator-based)

Remove (iterator-based)

The tests for each of these should not be all in a row for any single one. I.e. for best testing, make sure that insert/remove calls of a single function type are frequently interspersed between other types. (This way, a mistake in one will often be revealed by later calls to others)

Clear illustrations of list contents with Print before and after major sets of insert/delete tests. Make your outputs readable and easy to follow for best testing/results.

At least one test that uses an iterator to traverse the list front to back

At least one test that uses an iterator to traverse the list back to front

4) makefile

Create a makefile that configures a build of both my provided driver (driver.cpp) and your test program (mydriver.cpp). i.e. when you type "make" in the directory, it should compile and build both executables. Make your executables named "driver.x" and "mydriver.x", respectively.

5) General Requirements

Document your code appropriately so that it is readable and easy to navigate

You may use standard C++ I/O libraries, as well as class libraries like string. You may NOT use any of the container class libraries from the STL

If you wish to add any helper functions to the TList class, you may modify the tlist.h file for this purpose. But do NOT change any of the expected interface function prototypes or add extra member data. Any helper functions you write should be in the private section

Make sure your files compile and run on linprog.cs.fsu.edu with g++, using the C++11 standard compilation flag. This is where they will be tested and graded

------------------------------------------------------tnode.h----------------------------------------------------------------------------------

// Starter file for doubly-linked list. templated Node class // each Node stores a piece of data, along with prev and next pointers // to point to the previous and the next nodes in the list, respectively #include  template  class TList; // forward declaration template  class TListIterator; // forward declaration // declaration of Node class template  class Node { friend class TList; friend class TListIterator; public: Node(const T& d); Node(T && d); private: T data; // data element to store Node * prev; // pointer to previous node Node * next; // pointer to next node }; // Node constructor definitions template  Node::Node(const T& d) // copy version { data = d; // set data prev = next = nullptr; // null pointers to start } template  Node::Node(T && d) // MOVE version (if applicable for type T) { data = std::move(d); // set data prev = next = nullptr; // null pointers to start }

--------------------------------------------------------tlist.h --------------------------------------------------------------------

#include  #include  #include "tnode.h" // Declaration of class TList template  class TList { friend class TListIterator; public: TList(); // create empty linked list TList(T val, int num); // create list with num copies of val ~TList(); // destructor TList(const TList& L); // copy constructor TList& operator=(const TList& L); // copy assignment operator TList(TList && L); // move constructor TList& operator=(TList && L); // move assignment operator bool IsEmpty() const; // checks to see whether list is empty void Clear(); // clear out list, reset to empty int GetSize() const; // return the size of the list void InsertFront(const T& d); // insert data d as first element void InsertBack(const T& d); // insert data d as last element void RemoveFront(); // remove first element of list void RemoveBack(); // remove last element of list T& GetFirst() const; // return first element of list T& GetLast() const; // return last element of list TListIterator GetIterator() const; // return iterator to first item TListIterator GetIteratorEnd() const; // return iterator to last item // insert data element d just before item at pos position void Insert(TListIterator pos, const T& d); // remove data item at position pos. Return iterator to the item // that comes after the one being deleted TListIterator Remove(TListIterator pos); // print list contents in order, separated by given delimiter void Print(std::ostream& os, char delim = ' ') const; private: Node* first; // pointer to first node in list Node* last; // pointer to last node in list int size; // number of nodes in the list static T dummy; // dummy object, for empty list data returns // assuming type T has default construction }; template  T TList::dummy; // initialization of static member // stand-alone function for concatenating two TList objects template  TList operator+(const TList& t1, const TList& t2); // Declaration of class TListIterator template  class TListIterator { friend class TList; public: TListIterator(); // default constructor bool HasNext() const; // next item available? bool HasPrevious() const; // previous item available? TListIterator Next(); // advance to next item TListIterator Previous(); // move to previous item T& GetData() const; // return data element of current node private: Node* ptr; // pointer to current list item }; #include "tlist.hpp" // bring in definition file here 

-------------------------------------------------------------driver.cpp-------------------------------------------------------------------------

#include  #include  #include "tlist.h" using namespace std; template  void PrintList(const TList& L, string label) { cout << label << " size is: " << L.GetSize() << " " << label << " = "; L.Print(cout); cout << " "; } int main() { TList L1; // integer list for (int i = 0; i < 10; i++) L1.InsertBack(i*2); PrintList(L1, "L1"); for (int i = 0; i < 8; i++) L1.InsertFront( (i+1) * 100 ); PrintList(L1, "L1"); L1.RemoveBack(); PrintList(L1, "L1"); L1.RemoveBack(); PrintList(L1, "L1"); L1.RemoveFront(); PrintList(L1, "L1"); L1.RemoveFront(); PrintList(L1, "L1"); // try an iterator, and some middle inserts/deletes cout << "Testing some inserts with an iterator "; TListIterator itr = L1.GetIterator(); L1.Insert(itr, 999); itr.Next(); itr.Next(); // advance two spots L1.Insert(itr, 888); itr.Next(); itr.Next(); itr.Next(); // advance three spots L1.Insert(itr, 777); PrintList(L1, "L1"); cout << "Testing some removes (with iterator) "; itr.Next(); itr.Next(); // advance two spots itr = L1.Remove(itr); // delete current item PrintList(L1, "L1"); for (int i = 0; i < 5; i++) itr.Previous(); // back 5 spots itr = L1.Remove(itr); // delete current item PrintList(L1, "L1"); // building another list TList L2; for (int i = 0; i < 10; i++) L2.InsertBack(i * 3 + 1); PrintList(L2, "L2"); // Testing + overload: TList L3 = L1 + TList(100, 7); TList L4; L4 = L2 + L1; PrintList(L3, "L3"); PrintList(L4, "L4"); } 

-------------------------------------------------------------driver.output---------------------------------------------------------------------

L1 size is: 10 L1 = 0 2 4 6 8 10 12 14 16 18 L1 size is: 18 L1 = 800 700 600 500 400 300 200 100 0 2 4 6 8 10 12 14 16 18 L1 size is: 17 L1 = 800 700 600 500 400 300 200 100 0 2 4 6 8 10 12 14 16 L1 size is: 16 L1 = 800 700 600 500 400 300 200 100 0 2 4 6 8 10 12 14 L1 size is: 15 L1 = 700 600 500 400 300 200 100 0 2 4 6 8 10 12 14 L1 size is: 14 L1 = 600 500 400 300 200 100 0 2 4 6 8 10 12 14 Testing some inserts with an iterator L1 size is: 17 L1 = 999 600 500 888 400 300 200 777 100 0 2 4 6 8 10 12 14 Testing some removes (with iterator) L1 size is: 16 L1 = 999 600 500 888 400 300 200 777 100 0 4 6 8 10 12 14 L1 size is: 15 L1 = 999 600 500 888 400 200 777 100 0 4 6 8 10 12 14 L2 size is: 10 L2 = 1 4 7 10 13 16 19 22 25 28 L3 size is: 22 L3 = 999 600 500 888 400 200 777 100 0 4 6 8 10 12 14 100 100 100 100 100 100 100 L4 size is: 25 L4 = 1 4 7 10 13 16 19 22 25 28 999 600 500 888 400 200 777 100 0 4 6 8 10 12 14 

-------------------------------------------tlist.hpp---------------------------------------------------------------------------------------------- *******this is what i have completed so far. I am stuck on the cout overload for both print functions ****************

#include #include using namespace std;

//*****************************************************************// // ------ defintion os stream ------- // //*****************************************************************// template void TList::Print(std::ostream& os, char delim) const { // print list contents in order, separated by given delimiter for(auto ptr = begin(); ptr != end(); ++ptr) os << *ptr << delim; }

//*****************************************************************// // ------ defintion TListIterator ------- // //*****************************************************************// template typename TList::begin() { if (!IsEmpty()) { typename TList::TListIterator ptr {first->next}; } }

template // default constructor TListIterator::TListIterator() : ptr{ nullptr } {}

template bool TListIterator::HasNext() const { // returns true if there is another node AFTER the current node, false otherwise }

template bool TListIterator::HasPrevious() const { // returns true if there is another node BEFORE the current node, false otherwise }

template TListIterator TListIterator::Next() { // advances the iterator to the next node after the current one. Returns an iterator to the new position

}

template TListIterator TListIterator::Previous() { // move to previous item }

template T& TListIterator::TListIterator::GetData() const { // return data element of current node return ptr; }

//*****************************************************************// // ------ defintion TList ------- // //*****************************************************************// /*template void TList::initializeTList() { size = 0; // num of nodes in the list first = NULL; last = NULL; //first->next = last; // take node that first is pointing to, changes "next" address in "first" node and point it to last node // last->prev = first; // order: first-last

}*/

template TList::TList() { size = 0; first = NULL; last = NULL; }

template // create list with num copies of val TList::TList(T val, int num) { size = 0; first = NULL; last = NULL; for (int i = 0; i < num; i++) { InsertBack(val); } }

template TList::~TList() { // destructor Clear(); delete first; delete last; }

/*TList(const TList& L); // copy constructor TList& operator=(const TList& L); // copy assignment operator TList(TList && L); // move constructor TList& operator=(TList && L); // move assignment operator */

template void TList::Clear() { // clear list while (!IsEmpty()){ RemoveFront(); } }

template bool TList::IsEmpty() const { // checks to see if list is, empty returns true bool temp; if (GetSize() == 0) { temp = true; } return temp; }

template int TList::GetSize() const { // return the size of the list return size; }

template void TList::InsertFront(const T& d) { // insert data d as first element // push front }

template void TList::InsertBack(const T& d) { // insert data d as last element //push back Node* newNode = new Node(d); if (first == NULL) first = newNode; if (last != NULL) last->next = newNode; newNode->next = nullptr; newNode->prev = last; last = newNode; size++; // Increase size of list }

template void TList::RemoveFront() { // remove first element of list //pop front }

template void TList::RemoveBack() { // remove last element of list //pop back }

/* T& GetFirst() const; // return first element of list T& GetLast() const; // return last element of list TListIterator GetIterator() const; // return iterator to first item TListIterator GetIteratorEnd() const; // return iterator to last item insert data element d just before item at pos position void Insert(TListIterator pos, const T& d); remove data item at position pos. Return iterator to the item // that comes after the one being deleted TListIterator Remove(TListIterator pos); */