#pragma once

#include <iostream>
using namespace std;

class node
{
public:
	double data;
	node* next;
	node* prev;

	node(double x)
	{
		data = x;
		prev = nullptr;
		next = nullptr;
	}
};


class doublyLinkedList
{
public:
	//attributes
	node* head;
	node* tail;

	doublyLinkedList()
	{
		head = nullptr;
		tail = nullptr;
	}

	//For lab:
	//run time: O(1)
	void addFront(double x)
	{
		if (head == nullptr) //list is empty
		{
			//Create new node containing value x
			node* baby;
			baby = new node(x);

			//Point head at the new node
			head = baby;

			//Point tail to baby
			tail = baby;
		}
		else
		{
			//Create new node containing value x
			node* baby;
			baby = new node(x);

			//new node's next should point to
			//the previous first node.
			//(*baby).next = head;
			baby->next = head;

			//Point old head node's previous
			//to the new baby node
			head->prev = baby;

			//switch head pointer to point to new node
			head = baby;
		}
	}

	//run time: O(1)
	void addBack(double x)
	{
		if (head == nullptr) //list is empty
		{
			//Create new node containing value x
			node* baby;
			baby = new node(x);

			//Point head at the new node
			head = baby;

			//Point tail to baby
			tail = baby;
		}
		else
		{
			//Create new node containing value x
			node* baby;
			baby = new node(x);

			//previous point of new node
			//should be set to point at tail node
			baby->prev = tail;

			//Point old tail node's next
			//to the new baby node
			tail->next = baby;

			//switch tail pointer to point to new node
			tail = baby;
		}
	}

	//Print items from head to tail
	void printForwards()
	{
		node* current;
		current = head;

		while (current != nullptr)
		{
			cout << current->data << endl;
			current =  current->next;
		}

	}

	//Print items from tail to head
	void printBackwards()
	{
		for (node * c = tail; c!=nullptr; c=c->prev)
		{
			cout << c->data << endl;
		}
	}

	//Challenge #1: remove and return front item from list
	double popFront()
	{
		//Step 0:  Write down value we want to return
		double output = head->data;
		
		//Create pointer, point at node doomed to die
		node* doomed;
		doomed = head;

		//Move the head
		head = head->next;

		//Take care of memory leak
		delete doomed;

		//set's head's previous point to be null
		head->prev = nullptr;

		//Step last:
		return output;
	}

	//Challenge #2: remove and return last item from list
	double popBack()
	{
		double output = tail->data;

		node* doomed = tail;
		tail = tail->prev;
		delete doomed;
		tail->next = nullptr;

		return output;
	}


	//Return pointer to node with data value x.
	//Return nullptr if x is not present.
	node * findNode(double x)
	{
		for (node* iptr = head; iptr != nullptr; iptr = iptr->next)
		{
			if (iptr->data == x)
				return iptr;
		}
		return nullptr;
	}

	//Challenge #3: remove given item x from list
	void remove(double x)
	{
		//Step 1: find node containing x
		node* target = findNode(x);

		//Step 2: Figure out which case we are in
		if (target == nullptr) //Item not in list
		{
			//Do nothing.
		}
		else if (target == head) //Item is first node
		{
			popFront();
		}
		else if (target == tail) //Item is last node
		{
			popBack();
		}
		else //Item is somewhere in middle of list: Finish for quiz
		{

		}
	}


};