Project 6: Templates and Iterators
Github Classroom link: See blackboard

Create an Iterator for a Double Linked list. The nodes of the double linked list will have both a next and a prev.

You have been given the following files:
driver.cpp - no need to modify
DoubleLinkedList.h - you will be implementing the functions in this file


DoubleLinkedList.h This is a templated class, no .cpp Contains the following functions:
(a) constructor - provided for you.
(b) destructor - implement if needed.
(c) push_front - adds a node to the beginning of the double linked list.
(d) operator<< - provided for you
(e) begin - returns an Iterator, provided for you
(f) end - Returns an iterator referring to the past-the-end element in the list container (null), provided for you.
(g) find - Returns an iterator to the first element in the range [first,last) that is equal to value. The range searched is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last. If no elements match, the function returns end().
(h) insert_before - inserting a new element before the element at the specified position. The function returns an iterator pointing to the newly inserted element. If not found return end(). Call the insert_before of the iterator except when adding to the beginning of the list, use the push_front to do that. The function returns an iterator pointing to the newly inserted element. If not found return end().
(i) insert_after - inserting a new element after the element at the specified position. The function returns an iterator pointing to the newly inserted element. If not found return end()
(j) remove - returns an iterator pointing to the element that followed the element erased by the function call. Returns end() if the operation erased the last element in the sequence.
(k) replace - replaces all occurrences of the old_value with a new_value within two Iterator positions. The range searched is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
(l) reverseString - Return a string of the data within the nodes from iterator position to beginning of linked list, separated by a space.
(m) toString - provided for you. Returns a string of the data within all the nodes of the double linked list, separated by a space.


Iterator The Iterator class is a nested class within DoubleLinkedList. It will contain the following methods:
(a) constructor - provided for you
(b) destructor - implement if needed
(c) operator!= - determines if two Iterators are not equal
(d) operator++ - moves to the next node in the DoubleLinkedList
(e) operator-- - moves back to the previous node in the DoubleLinkedList
(f) operator* - returns the data portion of the node
(g) insert_before - inserts a new node before the Iterator position, returns Iterator to the new node. You do not have to implement inserting before the beginning of the list. This should be caught by the insert_before in DoubleLinkedList.
(h) insert_after - inserts a new node after the Iterator position, returns Iterator to the new node
(i) remove - Removes the node and returns an iterator to the next node which is after the deleted node in the DoubleLinkedList.
(j) operator== - determines if two Iterators are equal to each other

The driver.cpp provided will print out the following.

UNIT TESTS for Iterators for a DoubleLinkedList

Initial list
1 2 3 4
FIND

find position of 3
find posiiton of 7 (there is no 7 but shouldn't crash)

INSERT BEFORE

find a 3, insert 33 before 3
1 2 33 3 4
find a 7, insert a 8 before the 7 (there is no 7, shouldn't insert)
1 2 33 3 4

INSERT AFTER

find position of 1 and insert 33 after 1
1 33 2 33 3 4 
find position of 4 and insert 1 after 4
1 33 2 33 3 4 1

REMOVE

find position of 3 and remove 3
1 33 2 33 4 1
find position of 7 and remove 7 (there is no 7, no change)
1 33 2 33 4 1

REPLACE

replace all occurances of 33 with 333
1 333 2 333 4 1
replace first occurances of 1 with 8
8 333 2 333 4 1
replace all occurances of 7 with 777 (there is no 777, no replacements)
8 333 2 333 4 1
find a 333, find another 333 after that 333, insert a 5 before the second 333
8 333 2 5 333 4 1

REVERSE STRING

find position of 4 and reverseString from 4
4 333 5 2 333 8
find position of 2 and reverseString from 2
2 333 8
find a 333, find another 333 after that 333, reverseString from second 333
333 5 2 333 8



one two three four
one two 2 1/2 three four
You have been provided with two testing files - tests.cpp is for the autograding and testing.cpp is the one to test your program on the gl server and run a valgrind report.

A makefile is provided. "make driver" will run driver.cpp. "make testing" will run all the tests and give you a score. "make testMemory" is for the gl server to find memory leaks. "make test" will run the tests that are used for the autograding. 

i am workong in this assignment 

currently i have this implementation 

of the file i know some things are missing and i havent implemented them yet 
but i want you to check and see if i hwvat i have so far is correct 
 
/*
 * DoubleLinkedList.h
 *
 *  Created on: Nov 1, 2024
 *      Author: Professor Kartchner
 */

#ifndef DOUBLELINKEDLIST_H_
#define DOUBLELINKEDLIST_H_

#include <iostream>
#include <string>
#include <sstream>
using namespace std;


template<typename T>
class DoubleLinkedList
{
private:
	struct Node
	{
		T data;
		Node* next;
		Node* prev;
		Node(const T& d, Node* n, Node* p) : data(d), next(n), prev(p) { }
	};

	Node* head;

public:
	DoubleLinkedList() : head(NULL) { }
	~DoubleLinkedList() {
		DoubleLinkedList<T>::Iterator current = begin();

		while(current != NULL){
			current = remove(current);
		}

	}
	void push_front(const T& value) {
		//adds a node to the beginning of the DoubleLinked list
		//creating  a new node
		Node* node = new Node(value, head, nullptr);

		//Update the current head if the list isn't empty
		if(head != nullptr){
			head->prev = node;
		}

		//Update the list's head
		head = node;
		
	}

	friend std::ostream& operator<< (std::ostream& os, DoubleLinkedList<T>& linkedList)
	{
		for (Iterator iter = linkedList.begin(); iter != linkedList.end(); ++iter)
		{
			os << *iter << " ";
		}
		return os;
	}

	class Iterator
	{
	private:
		Node* iNode;
	public:
		Iterator(Node* head) : iNode(head) { }
		~Iterator() {
			//implement if needed;
		}

		//check if iNode is the same
		bool operator!=(const Iterator& rhs) const
		{
			return iNode != rhs.iNode;
		}


		//prefix increment
		//moves to the next node in the DoubleLinked list
		Iterator& operator++()
		{
			iNode = iNode->next;
			return *this;
		}

		//prefix decrement
		//moves back to the previous node in the DoubleLinked list
		Iterator& operator--()
		{
			iNode = iNode->prev;
			return *this;
		}

		//dereference operator
		//returns the data portion of the node
		T& operator*() const
		{
			return iNode->data;
		}

		bool operator==(const Iterator& rhs) const {
        return iNode == rhs.iNode;
    }

		//inserts a new node beore the Iterator position, returns Iterator to the new node.
		//You do not have to implement inserting before the beginning of the list. This should
		//be caught by the insert_before in DoubleLinkedList
		Iterator& insert_before(const T& value) {
			//creating a new node with prev inode value
			Node* node = new Node(value, iNode, iNode->prev);
			
			//Update pointers of adj nodes
			if(iNode->prev != nullptr){
				iNode->prev->next = node;	
			}
			//Update current nodes prev pointer
			iNode->prev = node;
			//Update Iterator to point to new node
			iNode = node;
			return *this;
			
		}

		//inserts a new node after the Iterator position, returns Iterator to the new node
		Iterator& insert_after(const T& value) {
			//creating a new node with next inode value
			Node* node = new Node(value, iNode->next, iNode);
			
			//Update pointers of adj nodes
			if(iNode->next != nullptr){
				iNode->next->prev = node;	
			}
			//Update current nodes next pointer
			iNode->next = node;
			//Update Iterator to point to new node
			iNode = node;
			return *this;
		}

		//Removes the node and returns an iterator to the next node which is after the
		//deleted note in the DoubleLinkedList
		Iterator& remove() {
			//Temp variables to hold pointers
			Node* next = iNode->next;
			Node* prev = iNode->prev;

			//previous node exists update
			if(prev != nullptr){
				prev->next = next;
			}
			//next node exists update
			if(next != nullptr){
				next->prev = prev;	
			}


			//Delete current node
			delete iNode;
			//update iNode to point to next node
			iNode = next;
			return *this;
		}

	};

	/** Return iterator pointing to the first value in linked list */
	Iterator begin(void)
	{
		return DoubleLinkedList<T>::Iterator(head);
	}

	/** Return iterator pointing to something not in the linked list
	Returns an iterator referring to the past-the-end element in the
	list container. */
	Iterator end(void)
	{
		return DoubleLinkedList<T>::Iterator(NULL);
	}

	/*Returns an iterator to the first element in the range [first,last)
	that compares equal to value. The range searched is [first,last),
	which contains all the elements between first and last, including
	the element pointed by first but not the element pointed by last.
	If no elements match, the function returns end().*/
	Iterator find(Iterator first, Iterator last, const T& value)
	{
		for(Iterator iter = first; iter != last; ++iter){
			//if we find the value return 
			if(*iter == value)
				return iter;
		}
		return end();
	}

	/*The container is extended by inserting a new element before the
	element at the specified position. The function returns an iterator
	pointing to the newly inserted element.
	If not found return end()*/
	Iterator insert_before(Iterator position, const T& value)
	{
		Node* current = position.iNode;
		if(current != nullptr){
			Node* node = new Node(value, current, current->prev);
			
			if(current->prev != nullptr) {
				current->prev->next = node;
			}
			current->prev = node;
			return Iterator(node);
			}
		//was not foudn return end
		return end();
	}

	/*The container is extended by inserting a new element after the
	element at the specified position. The function returns an iterator
	pointing to the newly inserted element.*/
	Iterator insert_after(Iterator position, const T& value)
	{
		Node* current = position.iNode;
		if(current != nullptr){
			Node* node = new Node(value, current->next, current);
			
			if(current->next != nullptr) {
				current->next->prev = node;
			}
			current->next = node;
			return Iterator(node);
			}	
		return end();
	}

	/** Return iterator pointing to next item after deleted node linked list */
	/*Removes from the list container a single element (position) and returns an
	iterator pointing to the element that followed the element erased by the function
	call. This is the container end if the operation erased the last element in the sequence.*/

	Iterator remove(Iterator position)
	{
		return DoubleLinkedList<T>::Iterator(head); //replace this
	}

	/** Return a string from iterator position to beginning of linked list, separated by a space*/
	string reverseString(Iterator position)
	{
		return " ";
	}

	void replace(Iterator first, Iterator last, const T& old_value, const T& new_value)
	{
		return;
	}

	string toString() {
		ostringstream oSS;
		Iterator current = begin();
		while (current != end()) {
			oSS << *current << " ";
			++current;
		}
		return oSS.str();
	}
};



#endif /* DOUBLELINKEDLIST_H_ */
 

currently when i try and compile i get this error thought 
g++ -Wall driver.cpp -o test
In file included from driver.cpp:2:0:
DoubleLinkedList.h: In instantiation of 'DoubleLinkedList<T>::Iterator DoubleLinkedList<T>::insert_before(DoubleLinkedList<T>::Iterator, const T&) [with T = int]':
driver.cpp:28:46:   required from here
DoubleLinkedList.h:205:28: error: 'DoubleLinkedList<int>::Node* DoubleLinkedList<int>::Iterator::iNode' is private within this context
   Node* current = position.iNode;
                   ~~~~~~~~~^~~~~
DoubleLinkedList.h:68:9: note: declared private here
   Node* iNode;
         ^~~~~
DoubleLinkedList.h: In instantiation of 'DoubleLinkedList<T>::Iterator DoubleLinkedList<T>::insert_after(DoubleLinkedList<T>::Iterator, const T&) [with T = int]':
driver.cpp:40:45:   required from here
DoubleLinkedList.h:224:28: error: 'DoubleLinkedList<int>::Node* DoubleLinkedList<int>::Iterator::iNode' is private within this context
   Node* current = position.iNode;
                   ~~~~~~~~~^~~~~
DoubleLinkedList.h:68:9: note: declared private here
   Node* iNode;
         ^~~~~
DoubleLinkedList.h: In instantiation of 'DoubleLinkedList<T>::Iterator DoubleLinkedList<T>::insert_before(DoubleLinkedList<T>::Iterator, const T&) [with T = std::__cxx11::basic_string<char>]':
driver.cpp:122:45:   required from here
DoubleLinkedList.h:205:28: error: 'DoubleLinkedList<std::__cxx11::basic_string<char> >::Node* DoubleLinkedList<std::__cxx11::basic_string<char> >::Iterator::iNode' is private within this context
   Node* current = position.iNode;
                   ~~~~~~~~~^~~~~
DoubleLinkedList.h:68:9: note: declared private here
   Node* iNode;
         ^~~~~
makefile:11: recipe for target 'compile' failed 

i cant modify the class in anyway apart from just implemeting the given methods to me