#include "LinkedList.h"

//
// Default constructor, copy constructor, assignment oerator,
// and destructor

static Node *duplicateLinkedList(Node *head);
static Node *searchLinkedList(Datatype value, Node *head);
LinkedList::LinkedList()
{
    head = NULL;
}
LinkedList::LinkedList(const LinkedList& original)
{
    head = duplicateLinkedList(original.head);
}
LinkedList& LinkedList::operator=(const LinkedList& original)
{
    if (&original != this)
    {
        Node *newhead = duplicateLinkedList(original.head);
        removeAll();
        head = newhead;
    }
    return *this;
}
LinkedList::~LinkedList()
{
    removeAll();
    cout <<"Destructor Call" << endl;
}
//
// isEmpty
//
// Purpose: Check if a Multiset instance is empty.
// Argument(s): N/A
// Return: True if the Multiset instance is empty, and false
//         otherwise.
//
bool LinkedList::isEmpty() const
{
    return head==NULL;
}
//
// getCount
//
// Purpose: Get the number of items in a Multiset instance.
// Argument(s): N/A
// Return: The number of items currently in the Multiset instance.
//
unsigned int LinkedList::getCount() const
{
    unsigned int count = 0;
    for (Node *p = head; p != NULL; p = p->next)
    {
        count++;
    }
    return count;
}
const Datatype& LinkedList::retrieve(unsigned int index) const
{
    Node *p = head; // make sure to check for output, if wrong head-> next
    for (unsigned int i = 0; i < index; i++)
    {
        p = p -> next;
    }
    return p->datum;

}
unsigned int LinkedList::find(const Datatype& value) const
{
    int i = 0;
    for (Node *p = head; p != NULL; p = p->next)
    {
        if (p-> datum == value)
        {
            return i;
        }
        else
        {
            i++;
        }
    }

    return NOT_IN_LIST;
}
bool LinkedList::contains(const Datatype& value) const
{
    for (Node *p = head; p != NULL; p = p->next)
    {
        if (p -> datum == value)
        {
            return true;
        }

    }

    return false;
}
//
// insert
//
// Purpose: Insert an item into a Multiset instance.
// Argument(s):
//   x: A type ItemType item to be inserted into the Multiset instance.
// Side Effect: an additional occurrence of x is in the Multiset instance.
// Return: N/A
//
void LinkedList::insert(const Datatype& value)
{
    // Find the node before the spot to insert
    Node *prev = searchLinkedList(value, head);
    // Create new node
    Node *newp = new Node(value);
    // Insert
    if (prev == NULL)
    {
        newp->next = head;
        head = newp;
    }
    else
    {
        newp->next = prev->next;
        prev->next = newp;
    }
}
//
// removeByIndex
//
// Purpose: Remove an item from a Multiset instance.
// Argument(s):
// index: A index value of the item to be removed from the Multiset instance.
// Return: N/A
//
void LinkedList::removeByIndex(unsigned int index)
{

    Node *prev = NULL;
    Node *current = head;
    unsigned int i = 0;
    while (current != NULL && i < index)
    {
        prev = current;
        current = current->next;
        i++;
    }
    // 2 cases: Target has a predecessor or not
    if (prev != NULL)
    {
        // Target has a predecessor

        // Remove
        prev->next = current -> next;
        delete current;

    }
    else
    {

        head = current->next;
        delete current;

    }
}
void LinkedList::removeAll()
{
    Node *current = NULL;
    Node *next = head;
    while (next != NULL)
    {
        current = next;
        next = current->next;
        delete current;
    }
    head = NULL;

}
static Node *searchLinkedList(Datatype value, Node *head)
{
    Node *prev = NULL;
    Node *current = head;
    while (current != NULL && current->next != NULL)
    {
        prev = current;
        current = current->next;
    }
    return prev;
}
static Node *duplicateLinkedList(Node *head)
{
    if (head == NULL) return NULL;
    Node *newp = new Node(head->datum);
    Node *prev = newp;
    Node *p = head->next;
    while (p != NULL)
    {
        prev->next = new Node(p->datum);
        prev = prev->next;
        p = p->next;
    }
    prev->next = NULL;
    return newp;
}