////////////////////////////////////////////////////////////////////////////////
// Faculty of Computing, Universiti Teknologi Malaysia
// SCSJ2013- Data Structures and Algorithms
// Semester 1, 2018/2019
// Assignment 1  - Program 1 Linked List
////////////////////////////////////////////////////////////////////////////////

#include<iostream>
using namespace std;

class Node{
    private:
        char id;
    public:
        Node *next;

        Node(char anId=0)
        { id = anId;
          next =NULL;
        }

        char getId() const
        { return id; }
};


// To print the list of nodes from first to last
void print(Node *first,  Node *last)
{
    Node *node = first;
    while (node){
        cout << node->getId() << "\t";
        node=node->next;
    }
    cout << endl;
}


int main()
{
    Node *first, *last;

    first = last = new Node('A');

    for (char ch='B'; ch <='G'; ch++){
        last->next = new Node(ch);
        last = last->next;
    }

    print(first, last);
    cin.get();

    Node *node;

    // Task 1 : Insert a new node (with the id of 'X') in front of the list
    node = new Node('X');
    node->next = first;
    first = node;



    print(first, last);
    cin.get();
    //-------------------------------------------------


    // Task 2 Insert a new node (with the id of 'Y') between node 'C' and node 'D'

    //  X--->A--->B--->C--->D--->E--->F--->G--->NULL
    Node* current = first;
    while (current->next != NULL)     // keep looping through all the linked list; 2nd condition is for making sure you don't go beyond list boundries
    {
        if(current->getId() == 'C')
        {
            Node* newnode = new Node('Y');   // creat a new node X
            newnode->next = current->next;   // X-->next = C--->next which is D, we connect to preserve the connection, then we break in the next statment
            current->next = newnode;         // we now break C--->next from being D to be the newnode we created which is X


            /* supposingly here we add break because it's uncesseary to loop anymore. */
            break;
        }

        current = current->next;    // update statment like i++
    }



    print(first, last);
    cin.get();
    //-------------------------------------------------


    // Task 3 Insert a new node (with the id of 'Z') at the end of the list
    current = first;                  // re-intiating current to start at the beggining of the linked list. no need for new pointer.
    while (current->next != NULL)     // 2nd condition is for making sure you don't go beyond list boundries
    {
        current = current->next;      // after we arrive at the end of the linked list, loop will autmatically break;
    }                                 // current will be now pointing to the last element in the linked list.

    current->next = new Node('Z');    // last element Next ----> our new inserted 'Z';
    last = current->next;             // updating the value of last


    print(first, last);
    cin.get();
    //-------------------------------------------------


    // Task 4   (Swap first and last elements)

    current = first;
    while(current->next != last && current->next != NULL)  // 2nd condition is for making sure you don't go beyond list boundries
    {
        current = current->next;
    }
    // current is now the element before the last.

    last->next = first->next;      // last is now connected to the 2nd elemnt in the list
    current->next = first;        // element before the last is connected to the new last which is the beggining of the array.
    first = last;                 // updating first and last;
    last = current->next;         // since current is the element before the last.
    last->next = NULL;            // not to forget to make the last pointing to null, otherwise it will be closed(infinite)loop for print


    print(first, last);
    cin.get();
    //-------------------------------------------------


    // Task 5 : Swap the positions of the node ‘D’ and ‘E’
    // i assume the I already know D and E are going be adjacent !!



    current = first;
    while(current->next->getId() != 'D' && current->next != NULL)  // 2nd condition is for making sure you don't go beyond list boundries
    {
        current = current->next;
    }
    // current is now the one before d
    Node* temp = current->next->next;      // tmp = the one after D which is E
    current->next->next = temp->next;           // D-->next = E-->next;
    temp->next = current->next;            // E next is D
    current->next = temp;                   // D next is E

    print(first, last);
    cin.get();
    //-------------------------------------------------


    // Task 6 : Delete the last node from the list


    current=first;
    while(current->next != last && current->next != NULL)  // 2nd condition is for making sure you don't go beyond list boundries
    {
        current = current->next;
    }
    // current now is poiting on the element befor the last
    delete current->next;
    current->next = NULL;



    print(first, last);
    cin.get();
    //-------------------------------------------------

    // Z       A       B       C       Y       E       D       F       G
    // Task 7 : Delete the node ‘C’ from the list
    current = first;
    Node* temp1;
    while(current->next->getId() != 'C' && current->next != NULL) // 2nd condition is for making sure you don't go beyond list boundries
    {
        current = current->next;
    }
    // current is now the element just before C

    temp1 = current->next;
    current->next = current->next->next;  // the one before C point to the thing that C orginally points to
    delete temp1;

    print(first, last);
    cin.get();
    //-------------------------------------------------


    // Task 8 : Delete the first node from the list


    current = first->next;        // make the current to be the 2nd element.
    first->next = NULL;          // breaking connection between first node and 2nd node
    delete first->next;          // deleting the pointer
    first = current;            // putting first at the beggining of the new linked list.



    print(first, last);
    cin.get();
    //-------------------------------------------------




    // Find any number from the list (based on input entered by the user)

    cout <<"What character position you would like to find?  enter the once character only: ";
    char c;           // character input
    cin>>c;
    current = first;
    int currentElementIndex = 1;
    while(current->getId() != c && current->next != NULL)  // looping untill you find the character & making sure you don't go beyond list boundries
    {
        current = current->next;
        currentElementIndex++;
    }

    cout <<"Your Element is the element number \"" << currentElementIndex <<"\" in the list. \n \n";



    print(first, last);
    cin.get();
    //-------------------------------------------------
}