/******************************************************************************/
/*!
\file   List.cpp
\author Brady Menendez
\par    email: brady.m\@digipen.edu
\par    DigiPen login: brady.m
\par    Course: CS170
\par    Section A
\par    Lab 6
\date   2/20/2017
\brief
  This is the implementation file for all member functions
  of a class called List, as specified in specification
  file List.h.

  Operations include:
    + List
    + ~List
    + MakeNode
    + Count
    + AddToEnd
    + AddToFront
    + FindItem
    + Insert
    + Concat
    + Delete
    + operator<<

  Hours spent on this assignment : 1 hour

  Specific portions that gave you the most trouble:
  Fixing Dr Memory warnings.

*/
/******************************************************************************/
#include <iostream> // cout
#include "List.h"

namespace CS170
{
  namespace ListLab
  {
    /*!*************************************************************************
    \brief
         Creates a list and sets the head to 0.
    ***************************************************************************/
    List::List()
    {
      head_ = 0;
    }

    /*!*************************************************************************
    \brief
      Creates a new node with a given value.

    \param value The value for the new node to hold
    \return Created node
    ***************************************************************************/
    Node* List::MakeNode(int value) const
    {
        // The Node constructor sets the value, and sets next to 0.
      return new Node(value);
    }

    /*!*************************************************************************
    \brief
        Prints all the nodes in the list.

    \param os  - the ostream
    \param list - the list to be printed
    ***************************************************************************/
    std::ostream& operator<<(std::ostream &os, const List& rhs)
    {
      Node *list = rhs.head_;
      while(list)
      {
        os << list->number << "   ";
        list = list->next;
      }

      return os;
    }

    /*!*************************************************************************
    \brief
        Counts the nodes in the list.

    \return count The number of nodes in the list.
    ***************************************************************************/
    int List::Count() const
    {
      Node *list = head_;  // node pointer to the head
      int count = 0;       // sets counter to 0
      while (list)         // goes through the list
      {
        count++;           // increments the counter
        list = list->next; // goes to the next node
      }
      return count;        // returns the number of nodes
    }

    /*!*************************************************************************
    \brief
        Adds a node to the end of the list.

    \param value The value the new node is gonna hold.
    ***************************************************************************/
    void List::AddToEnd(int value)
    {
      Node *newNode = MakeNode(value); // node pointer
      Node *temp = head_; // temp node pointer

      if (temp == NULL) // checks if temp is NULL
      {
        head_ = newNode; // pointes to pNode
        return;
      }

      while (temp->next) // checks if not NULL
      {
        temp = temp->next; // sets temp to next node
      }
      temp->next = newNode; // sets the node next to temp to a new node
    }

    /*!*************************************************************************
    \brief
         Adds a node to the front of the list

    \param value The value the new node is gonna hold.
    ***************************************************************************/
    void List::AddToFront(int value)
    {
      Node *newNode = MakeNode(value); // makes new node
      newNode->next = head_; // puts new node at the beginning of the list

      head_ = newNode; // sets new head
    }

    /*!*************************************************************************
    \brief
         Finds an item.

    \param value The value the new node is gonna hold.
    \return The node with the value to find
    ***************************************************************************/
    Node *List::FindItem(int value) const
    {
      Node *pNode = head_;          // node pointer to the head

      while (pNode)                 // goes through the list
      {
        if (pNode->number == value) // checks for the value needed
          return pNode;

        pNode = pNode->next;        // goes to the next node
      }
      return NULL;
    }

    /*!*************************************************************************
    \brief
         Deletes the entire linked list.
    ***************************************************************************/
    List::~List()
    {
      while (head_)               // goes through the list
      {
        Node *temp = head_->next; // node pointer to the node after the head
        delete head_;             // deletes the head
        head_ = temp;             // sets new head
      }
    }

    /*!*************************************************************************
    \brief
        Inserts a new node at the specified position

    \param value The value the new node is gonna hold.
    \param position the position in the list to put the node in.
    ***************************************************************************/
    void List::Insert(int value, int position)
    {
      if (position == 0)      // checks for first node in the list
      {
        AddToFront(value);    // adds new node to the front of the list
        return;
      }

      if (Count() < position)  // checks if position exceeds the number of nodes
        return;

      if (position == Count()) // checks if position is at the end of the list
      {
        AddToEnd(value);       // adds node to the end of the list
        return;
      }

      Node *newNode = MakeNode(value);         // makes new node
      Node *pNode = head_;                     // node pointer to head

      for (int i = 0; i < (position - 1); i++) // checks for position
      {
        pNode = pNode->next;                   // goes to next node
      }

      newNode->next = pNode->next;             // inserts node

      pNode->next = newNode;
    }

    /*!*************************************************************************
    \brief
        Inserts a new node at the specified position

    \param value The value the new node is gonna hold.
    ***************************************************************************/
    void List::Insert(int value)
    {

      Node *pNode = head_; // node pointer to head

      if (Count() == 0)    // checks if there is no nodes in the list
      {
        AddToFront(value); // adds it to the front
        return;
      }

      for (int i = 0; i < Count(); i++) // goest through the list
      {
        // checks if the first node is greater than the value
        if(pNode->number > value && i == 0)
        {
          AddToFront(value); // adds a new node to the front
          return;
        }

        // checks if the node is lesser than the previous one and greater than
        // the next one
        if(i <= (Count() - 2) && pNode->number <= value &&
        pNode->next->number > value)
        {
          Node *newNode = MakeNode(value); // makes new node
          newNode->next = pNode->next;     // links new node and the next node
          pNode->next = newNode; // links the previous node to the new one
          return;
        }

        // checks if last node is less than the value
        if(i == (Count() - 1) && pNode->number < value)
        {
          AddToEnd(value); // adds new node to the end of the list
          return;
        }

        pNode = pNode->next; // goes to next node
      }
    }

    /*!*************************************************************************
    \brief
        Deletes a node with a certain value.

    \param value The value to destroy.
    ***************************************************************************/
    void List::Delete(int value)
    {
      Node *pNode = head_; // pointer to the head

      if (!FindItem(value)) // checks if the value is in the list
      {
        return;
      }
      for (int i = 0; i < Count(); i++) // goes through each node
      {
          // checks if the first node has the value
          if (pNode->number == value && i == 0)
          {
            head_ = pNode->next; // moves head to next node
            delete pNode;        // deletes previous head
            return;
          }

          // checks if next node holds the value
          if (pNode->next->number == value
          && i < (Count() - 2))
          {
            Node *temp = pNode->next->next; // pointer to node after that one
            delete pNode->next; // deletes next node
            pNode->next = temp; // sets next node to the temp one
            return;
          }

        // checks if last node matches the value
        if (pNode->next->number == value
        && i == Count() - 2)
        {
          delete pNode->next; // deletes the node
          pNode->next = NULL; // sets pointer to the last node to null
          return;
        }

        pNode = pNode->next; // goes to the next node
      }
    }

    /*!*************************************************************************
    \brief
        Deletes all the values from a given list based on another one.

    \param Items The List to substract from the other one.
    ***************************************************************************/
    void List::Delete(const List& Items)
    {

      Node *list2 = Items.head_; // list 2 head pointer

      for (int i = 0; i < Items.Count(); i++) // goes through each node
      {
        Delete(list2->number); // deletes that value from the first list
        list2 = list2->next;   // goes to the next node
      }
    }

    /*!*************************************************************************
    \brief
        Adds one list to the end of another one.

    \param Source The List to add to the other one.
    ***************************************************************************/
    void List::Concat(const List& Source)
    {
      Node *list2 = Source.head_; // list 2 head pointer

      for (int i = 0; i < Source.Count(); i++) // goes through each node
      {
        AddToEnd(list2->number); // adds to the end of the first list2
        list2 = list2->next;     // goes to the next node
      }
    }
  } // namespace ListLab
} // namespace CS170