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

using namespace std;

struct NodeT {
    int data;
    NodeT * next;
};

ListT::ListT(){
    head = nullptr;
    size = 0;
    return;
}

void CopyList(NodeT * & dest, NodeT * src) {
   NodeT * tmp = nullptr;;
   NodeT * follow = nullptr;;
   NodeT * step = nullptr;;

   dest = nullptr;

   for(step = src; step != nullptr; step=step->next) {

       tmp = new NodeT;
       tmp->data = step->data;
       tmp->next = nullptr;

       if (dest == nullptr) {
          dest = tmp;
          follow = tmp;
       } else {
          follow -> next = tmp;
          follow = follow->next;
       }
   }

   return;

}

ListT::ListT(const ListT & rhs){
    size = rhs.size;
    CopyList(head, rhs.head);

    return;
}

void DeleteList(NodeT * head){
   NodeT * tmp;
   tmp = head;
   while (tmp != nullptr) {
       head = tmp->next;
       delete tmp;
       tmp = head;
   }

   return;
}

ListT::~ListT(){
    DeleteList(head);

    return;
}

ListT & ListT::operator = (const ListT & rhs){
    DeleteList(head);
    size = rhs.size;
    CopyList(head, rhs.head);

    return * this;
}

void ListT::Insert(int item){
    NodeT * tmp = nullptr;
    NodeT * trace;
    NodeT * tail;

    tmp = new NodeT;
    tmp->data = item;
    tmp->next = nullptr;

    if (head == nullptr or head->data > item) {
        tmp->next = head;
        head = tmp;
    } else {
    
        trace = head->next;
        tail = head;
        while (trace != nullptr and trace->data < item) {
           tail = trace;
           trace = trace -> next;
        }

        tmp->next = trace;
        tail->next = tmp;
    }


    size++;

    return;
}

void ListT::Delete(int item){
    NodeT * tmp = nullptr;
    NodeT * tail = nullptr;
   
    if (head != nullptr) {
        // special case, it is the first  item in the list
        if (head->data == item) {
            tmp = head;
            head = head->next;
            delete tmp;
            size--;
        } else {
            // General case 
            tmp = head->next;
            tail = head;

            // find it
            while (tmp != nullptr and tmp->data != item) {
               tail = tmp;
               tmp = tmp->next;
            }

            // did we find it?  If so, delete it.
            if (tmp != nullptr) {
               tail->next = tmp->next;
               delete tmp;
               size--;
            }
        }
    }
    return;
}

bool ListT::Find(int item) const{
    bool found = false;
    NodeT * tmp;

    tmp = head;
    while(not found and tmp != nullptr) {
       if (tmp->data == item) {
          found = true;
       } else {
          tmp = tmp->next;
       }
    }
    return found;
}

size_t ListT::Size(void) const{
    return size;
}

void ListT::PrintList(void) const{
    NodeT * tmp;

    if(head != nullptr) {
       cout <<"\t";
       cout << head->data;
       for(tmp = head->next; tmp != nullptr; tmp=tmp->next) {
          cout <<", " << tmp -> data;
       }
    }

    return;
}