#ifndef SINGLY_LINKED_LIST_HPP
#define SINGLY_LINKED_LIST_HPP

struct ListNode
{
	int _data{ 0 };
	ListNode* _next{ nullptr };
};

struct SinglyLinkedList
{
	size_t _size{ 0 };
	ListNode* _head{ nullptr };
};

bool Append(SinglyLinkedList* list, ListNode* node);
bool Prepend(SinglyLinkedList* list, ListNode* node);
bool RemoveFirst(SinglyLinkedList* list);
bool RemoveLast(SinglyLinkedList* list);
bool InsertAfter(SinglyLinkedList* list, const int data, ListNode* node);
bool InsertBefore(SinglyLinkedList* list, const int data, ListNode* node);
bool Clear(SinglyLinkedList* list);
ListNode* Extract(SinglyLinkedList* list, const int data);
bool Empty(SinglyLinkedList* list);
bool Remove(SinglyLinkedList* list, ListNode* node);

//code
bool Append(SinglyLinkedList* list, ListNode* node )
{
	//we have a list
	//we need to add a node to the end of the list

	//empty
	if (Empty(list)) 
	{
		list->_head = node;
		list->_size++;
		return true;
	}
	//Append head
	if(list->_size == 1)
	{
		list->_head->_next = node;
		list->_size++;
		return true;
	}
	//Down the list
	ListNode* travel = nullptr;
	for(travel = list->_head; travel->_next != nullptr;)
	{
		travel = travel->_next;
	}
	travel->_next = node;
	list->_size++;
	return true;
}

bool Prepend(SinglyLinkedList* list, ListNode* node) 
{
	if (Empty(list))
	{
		list->_head = node;
		list->_size++;
		return true;
	}

	node->_next = list->_head;
	list->_head = node;

	list->_size++;
	return true;
}

bool RemoveFirst(SinglyLinkedList* list)
{
	//check if zero size
	if (Empty(list)) return true;

	if(list->_size == 1)
	{

		list->_head = nullptr;
	}
	else
	{
		ListNode* prev = list->_head;
		list->_head = list->_head->_next;
		prev->_next = nullptr;
	}

	list->_size--;

	return true;
}

bool RemoveLast(SinglyLinkedList* list)
{
	if (Empty(list)) return true;

	if (list->_size == 1)
	{
		list->_head = nullptr;
		return true;
	}
	
	ListNode* travel = list->_head;
	while(travel->_next->_next != nullptr)
	{
		travel = travel->_next;
	}
	travel->_next = nullptr;
	list->_size--;
	return true;
	
}

bool InsertAfter(SinglyLinkedList* list, const int data, ListNode* node)
{
	//first to find data
	//thoughts? What if we are inserting at after end.
	ListNode* travel;
	for (travel = list->_head; travel->_data != data && travel->_next != nullptr; )
	{
		travel = travel->_next;
	}

	if (travel->_next == nullptr) 
	{
		return Append(list, node);
	}

	node->_next = travel->_next;
	travel->_next = node;
	list->_size++;

	//then insert after data
	return true;
}

bool InsertBefore(SinglyLinkedList* list, const int data, ListNode* node)
{
	if (list->_head->_data == data)
		return Prepend(list, node);

	ListNode* travel;
	for (travel = list->_head; travel->_next->_data != data;)
	{
		travel = travel->_next;
	}

	node->_next = travel->_next;
	travel->_next = node;
	list->_size++;

	return true;
	
}

bool Clear(SinglyLinkedList* list)
{
	//consider the head
	//consider the size
	//We have to detach every node from each other
	//start at the head
	//use a node* to track our position

	if (list->_size == 0) return true;

	ListNode* travel = list->_head;
	ListNode* prev = travel;

	do
	{
		prev = travel;
		travel = travel->_next;
		prev->_data = 0;
		prev->_next = nullptr;
		
	} while (travel != nullptr && travel->_next != nullptr);

	list->_size = 0;
	list->_head = nullptr;

	return true;
}

ListNode* Extract(SinglyLinkedList* list, const int data)
{
	//check if empty, shortcut return
	ListNode* temp = new ListNode{0, nullptr};
	ListNode* travel = nullptr;

	if (Empty(list))
	{
		return temp;
	}
	//Read through list
	for (travel = list->_head; travel->_data != data && travel->_next != nullptr; )
	{
		travel = travel->_next;
	}
	//find the data
		//pointer to the node
	temp->_data = travel->_data;
		//remove node from list
	if(Remove(list, travel))
	{
		return temp;
	}
	//or don't find data

	return nullptr;
}

bool Remove(SinglyLinkedList* list, ListNode* node)
{
	//find the node
	//Read through list
	ListNode* travel = list->_head;
	ListNode* prev = travel;

	while(travel != node)
	{
		prev = travel;

		travel = travel->_next;
	}
	//if first, remove first
	if(travel == list->_head)
	{
		return RemoveFirst(list);
	}
	//if last, remove last
	if(travel->_next == nullptr)
	{
		return RemoveLast(list);
	}
	//else in middle
	//remove travel's node
	//will need previous node
		//to set previous's next to travel's next
	prev->_next = travel->_next; //fixing pointer between nodes
									//removes dangling pointer from prev to travel

	//delete travel
	travel->_next = nullptr;
	travel->_data = 0;
	list->_size--;
}

bool Empty(SinglyLinkedList* list)
{
	return (list->_size == 0 && list->_head == nullptr);
}

#endif // !SINGLY_LINKED_LIST_HPP