PROJECT 2 THAT WORKS!!!!

#include "Set.h"
#include <iostream>

void Set::initializeEmptySet()
{
	m_size = 0;

	m_head = new Node;
	m_tail = m_head;
	m_head->m_next = nullptr;
	m_head->m_prev = nullptr;
	m_tail->m_prev = nullptr;
	m_tail->m_next = nullptr;
}

Set::Set()
{
	initializeEmptySet();
}

// Before we can actually insert the node, we need to implement the insert before function
void Set::insertNewHead(const ItemType& value)
{

	Node* new_head = new Node;
	new_head->m_value = value;

	m_head->m_prev = new_head;
	new_head->m_prev = nullptr;
	new_head->m_next = m_head;
	m_head = new_head;

	m_size++;
}

void Set::insertNewTail(const ItemType& value)
{
	if (m_head == nullptr)
		insertNewHead(value);

	else
	{
		Node* old_tail = m_tail;

		Node* new_tail = new Node;
		old_tail->m_next = new_tail;
		new_tail->m_value = value;
		new_tail->m_prev = old_tail;
		new_tail->m_next = nullptr;
		m_tail = new_tail;
	}

	m_size++;
}

void Set::insertBefore(Node* p, const ItemType& value)
{
	//Create a new node

	Node* new_pointer = new Node;
	new_pointer->m_value = value;

	if (p == m_head)
	{
		insertNewHead(value);
		return;
	}

	// Set the new pointer's previous pointer equal to p's previous pointer
	// Then set the new pointer's next pointer equal to p
	new_pointer->m_prev = p->m_prev;
	new_pointer->m_next = p;

	// We must now make the previous nodes point to this new node
	// Then we must make the next node have its previous point to this node.
	new_pointer->m_prev->m_next = new_pointer;
	new_pointer->m_next->m_prev = new_pointer;

	m_size++;
}

// I have no idea how to write these function parameters
// Why is there a Set:: before declaring a node pointer?
// Is it because we can only define what a node pointer is after defining it's from the Set class?
Set::Node* Set::findClosestLocation(const ItemType& value) const
{
	Node* traversalNode = m_head;

	while (traversalNode->m_next != nullptr && traversalNode->m_value < value)
	{
		traversalNode = traversalNode->m_next;
	}

	return traversalNode;
}

bool Set::insert(const ItemType& value)
{
	Node* closestNode = findClosestLocation(value);

	// When we are inserting a new head into an empty linkedList we should also initialize the tail.
	if (m_size == 0)
	{
		insertNewHead(value);
		m_tail = m_head;
		m_head->m_next = nullptr;
		return true;
	}

	// First check if we already have that value in our linked list
	else if (closestNode->m_value == value)
	{
		return false;
	}

	// Then if it's closest node is the tail, we'll check if it should go before or after the tail
	// If we need to create a new tail, then we'll run that function
	// If not, we can actually just insert it before the tail (and run it like everything else)
	else if (closestNode == m_tail)
	{
		if (value > m_tail->m_value)
		{
			insertNewTail(value);
			return true;
		}
	}

	// insertBefore command actually checks if it should be a new head
	insertBefore(closestNode, value);
	return true;
}

void Set::actualErase(Node* p)
{
	// There are 4 cases to consider
	// If there is only a single node, then we will delete it and set its next and prev to nullptr
	// This is different from deleting a node in the middle because we don't have to link surrounding nodes together after deletion
	if (m_size == 1)
	{
		p->m_next = p->m_prev = nullptr;
	}

	// If we are deleting the head, then we must allocate a new head
	else if (p == m_head)
	{
		m_head = m_head->m_next;
		p->m_next->m_prev = nullptr;
	}

	// If we are deleting the tail, then we must allocate a new tail
	else if (p == m_tail)
	{
		m_tail = m_tail->m_prev;
		p->m_prev->m_next = nullptr;
	}

	// Because we are deleting a node in the middle, we need to make sure that we are linking the surrounding nodes together
	else
	{
		p->m_prev->m_next = p->m_next;
		p->m_next->m_prev = p->m_prev;
	}

	delete p;
	m_size--;
}

bool Set::erase(const ItemType& value)
{
	Node* closestNode = findClosestLocation(value);

	if (closestNode->m_value != value)
		return false;

	actualErase(closestNode);
	return true;
}

Set::~Set()
{
	while (m_size > 0)
		actualErase(m_head);
}

void Set::printLinkedList()
{
	Node* traversalNode = m_head;

	while (traversalNode != nullptr)
	{
		std::cout << traversalNode->m_value << " ";
		traversalNode = traversalNode->m_next;
	}

	std::cout << "\n";
}

bool Set::contains(const ItemType& value) const
{
	Node* closestNode = findClosestLocation(value);
	return (closestNode->m_value == value);
}

bool Set::get(int i, ItemType& value) const
{
	if (i < 0 || i >= m_size)
		return false;

	Node* traversalNode;

	// Closer to head
	if (i < (m_size / 2))
	{
		traversalNode = m_head;
		for (int j = 0; j != i; j++)
		{
			traversalNode = traversalNode->m_next;
		}
	}

	// Closer to tail
	else
	{
		traversalNode = m_tail;
		for (int j = m_size - 1; j != i; j--)
			traversalNode = traversalNode->m_prev;
	}

	value = traversalNode->m_value;
	return true;
}

void Set::swap(Set& other)
{
	Node* tempHead = other.m_head;
	other.m_head = m_head;
	m_head = tempHead;

	int tempSize = other.m_size;
	other.m_size = m_size;
	m_size = tempSize;

	// Ask Carey later about swapping tails
	// It makes sense that you can't really swap the tails after swapping the heads
	// Is there a more elegant solution though?

	Node* originalTraversalNode = m_head;
	for (int i = 1; i < m_size; i++)
		originalTraversalNode = originalTraversalNode->m_next;
	m_tail = originalTraversalNode;

	Node* swappedTraversalNode = other.m_head;
	for (int i = 1; i < other.m_size; i++)
		swappedTraversalNode = swappedTraversalNode->m_next;
	other.m_tail = swappedTraversalNode;
}

Set::Set(const Set& other)
{
	initializeEmptySet();

	// Copy all non-dummy other Nodes.  (This will set m_size.)
	// Inserting each new node before the dummy node that m_head points to
	// puts the new node at the end of the list.

	Node* traversalNode = other.m_head;

	for (int i = 0; i < other.m_size; i++)
	{
		insert(traversalNode->m_value);
		traversalNode = traversalNode->m_next;
	}
}

Set& Set::operator=(const Set& other)
{
	// Trying to avoid aliasing, which is when we use two different pointers/ references to acess the same variable
	// This is a problem if we try to first delete the data of the original before reassigning it to itself
	// Our solution it see if the parameter has the same object address as the target object
	if (this == &other)
	{
		return *this;
	}

	// Typically, we could simply delete the elements inside the array now, but Carey doesn't want us to use a for loop
	// Thus, we will do the Smallberg method of using a copy constructor and a swap method

	// Call the copy constructor to recreate the other set and then swap elements between the original set and the copied set
	// Temporary array will actually deconstruct itself
	Set temp(other);
	swap(temp);

	Node* traversalNode = m_head;
	int i = 1;

	std::cout << "\n";

	// Return the dereferenced contents of the Sets
	// Now works for a = b = c as well
	return *this;
}

void unite(const Set& s1, const Set& s2, Set& result)
{
	// We have to worry about aliasing, which is when we use two different pointers/ references to acess the same variable
	// The big worry here is if inputted result is actually s1 or s2

	// If s1, s2, and result are all the same-- then the result is already the union
	// If the result is s1, insert s2's elements into the result
	// If the result is s2, insert s1's elements into the result
	// If the result is its own distinct set, we will first assign it s1's contents, then check if s2 is the same as s1, and if they are different then we will insert s2 into s1

	// Naturally we will try to insert S2 into S1
	const Set* insertedNode = &s2;

	// First let's check if s1, s2, and result are all the same
	if (&result == &s1 && &result == &s2)
	{
		return;
	}

	// If result is the same as S2, we will make the insertedNode into s1
	else if (&result == &s2)
	{
		insertedNode = &s1;
	}

	// Now that we have determined that result is not s2 and that s1, s2, and result are not all the same
	// We will assign result to be equal to s1
	// Then we will check if s1 and s2 are the same
	// If they are, then we will simply return the set
	else
	{
		result = s1;
		if (&s1 == &s2)
		{
			return;
		}
	}

	// If s1 and s2 are not the same, then we will insert one into the other
	// If result was the same address as s2, then we will

	int size_of_insertedNode = insertedNode->size();
	ItemType x;

	for (int i = 0; i < size_of_insertedNode; i++)
	{
		insertedNode->get(i, x);
		result.insert(x);
	}
}

void butNot(const Set& s1, const Set& s2, Set& result)
{
	// We run into aliasing issues if s2 is the same as result
	// There will be an issue if we try removing s2 from result when s2 is the same as result
	// Because then result w

	// So we will actually just make a local copy of s2
	Set s2LocalCopy(s2);
	int size_of_local_copy = s2LocalCopy.size();

	// Then we will use the assignment operator to make the result equal to s1
	// We won't run into aliasing issues because our assignment operator already takes care of that issue
	result = s1;

	for (int i = 0; i < size_of_local_copy; i++)
	{
		ItemType x;
		s2LocalCopy.get(i, x);
		result.erase(x);
	}

}

void Set::printDetailedLinkedList()
{
	Node* traversalNode = m_head;

	std::cout << "Size is: " << m_size << "\n";
	std::cout << "Head is: " << m_head->m_value << "\n";
	std::cout << "Tail is: " << m_tail->m_value << "\n";


	for (int i = 0; i < m_size; i++)
	{
		std::cout << "The " << i << " Node is: " << traversalNode->m_value << "\n";
		std::cout << "Its previous location is: " << &(traversalNode->m_prev) << "\n";
		if (traversalNode->m_prev == nullptr)
			std::cout << "The previous location is a null pointer. \n";
		std::cout << "Its next location is: " << &(traversalNode->m_next) << "\n";
		if (traversalNode->m_next == nullptr)
			std::cout << "The next location is a null pointer. \n";

		traversalNode = traversalNode->m_next;
	}

	std::cout << "\n";
}