// FILE: driver.cxx
// Solution to Homework 2 Problems 1, 2, 3
// It takes integers, perform insertion sort, and store them in a linked list

#include <iostream>
#include <cstdlib>
#include <string>
#include "node2.h"
#include "dnode2.h"
#include "apvector.h"
#include "rando.h"
#include "systimer.h"

using namespace main_savitch_6B;

// insertion sort via a singly linked list
node<int> *Sort1()
{
    int n;
    node<int> *head = NULL;
    node<int> *cursor = NULL;

    while(cin>>n)
    {
        // when the list is empty, create the head node using a node constructor
        if(head == NULL)
            head= new node<int>(n, NULL);

        // insert a new node before the head using list_head_insert().
        else if(n < head->data())
            list_head_insert(head, n);

        else    // n is greater than or equal to head->data()
            for(cursor = head; cursor != NULL; cursor = cursor->link())

            // insert a new node at the end or in the middle of the list using list_insert()
            // take advantage of lazy evaluation
                if(cursor->link() == NULL || n >= cursor->data() && n < cursor->link()->data())
                {
                    list_insert(cursor,n);
                    break;
                }
    } // end of while

    return head;
}

// insertion sort via a singly linked list
node<int> *Sort1(const apvector<int>& numbers)
{
    int n;
    node<int> *head = NULL;
    node<int> *cursor = NULL;

    for(int i = 0; i < numbers.length(); i++)
    {
        n = numbers[i];     // work on one element from numbers at a time

        // when the list is empty, create the head node using a node constructor
        if(head == NULL)
            head= new node<int>(n, NULL);

        // insert a new node before the head using list_head_insert().
        else if(n < head->data())
            list_head_insert(head, n);

        else    // n is greater than or equal to head->data()
            for(cursor = head; cursor != NULL; cursor = cursor->link())

            // insert a new node at the end or in the middle of the list using list_insert()
            // take advantage of lazy evaluation
                if(cursor->link() == NULL || n >= cursor->data() && n < cursor->link()->data())
                {
                    list_insert(cursor,n);
                    break;
                }
    } // end of for

    return head;
}

// insertion sort via a doubly linked list
dnode<int> *Sort2()
{
    int n;
    dnode<int> *current = NULL;
    dnode<int> *insert = NULL;

    while(cin>>n)
    {
        // when the list is empty, create the current node using a dnode constructor
        if(current == NULL)
            current = new dnode<int>(n, NULL, NULL);

        // n is smaller than currentt->data(), insert a new node before the current node
        else if(n < current->data())
        {
            while(current->back() != NULL && n < current->back()->data())
                current = current->back();

            // insert at the very beginning of the list
            if(current->back() == NULL)
            {
                insert = new dnode<int>(n, current, NULL);
                current->set_back(insert);
                current = insert;
            }

            // insert somewhere between the very begining and the current node of the list
            else
            {
                insert = new dnode<int>(n, current, current->back());
                current->back()->set_fore(insert);
                current->set_back(insert);
                current = insert;
            }
        }

        // n is greater than or equal to current->data(), insert a new node after the current node
        else
        {
            while(current->fore() != NULL && n >= current->fore()->data())
                current = current->fore();

            // insert at the very end of the list
            if(current->fore() == NULL)
            {
                insert = new dnode<int>(n, NULL, current);
                current->set_fore(insert);
                current = insert;
            }

            // insert somewhere between the current node  and the very end of the list
            else
            {
                insert = new dnode<int>(n, current->fore(), current);
                current->fore()->set_back(insert);
                current->set_fore(insert);
                current = insert;
            }
        }

    } // end of while

    return current;
}

// insertion sort via a doubly linked list
dnode<int> *Sort2(const apvector<int>& numbers)
{
    int n;
    dnode<int> *current = NULL;
    dnode<int> *insert = NULL;

    for(int i = 0; i < numbers.length(); i++)
    {
        n = numbers[i];      // work on one element from numbers at a time

        // when the list is empty, create the current node using a dnode constructor
        if(current == NULL)
            current = new dnode<int>(n, NULL, NULL);

        // n is smaller than currentt->data(), insert a new node before the current node
        else if(n < current->data())
        {
            while(current->back() != NULL && n < current->back()->data())
                current = current->back();

            // insert at the very beginning of the list
            if(current->back() == NULL)
            {
                insert = new dnode<int>(n, current, NULL);
                current->set_back(insert);
                current = insert;
            }

            // insert somewhere between the very begining and the current node of the list
            else
            {
                insert = new dnode<int>(n, current, current->back());
                current->back()->set_fore(insert);
                current->set_back(insert);
                current = insert;
            }
        }

        // n is greater than or equal to current->data(), insert a new node after the current node
        else
        {
            while(current->fore() != NULL && n >= current->fore()->data())
                current = current->fore();

            // insert at the very end of the list
            if(current->fore() == NULL)
            {
                insert = new dnode<int>(n, NULL, current);
                current->set_fore(insert);
                current = insert;
            }

            // insert somewhere between the current node  and the very end of the list
            else
            {
                insert = new dnode<int>(n, current->fore(), current);
                current->fore()->set_back(insert);
                current->set_fore(insert);
                current = insert;
            }
        }

    } // end of while

    return current;
}

// turn a sorted array into an almost sorted array with a given block size
// assume all blocks are full blocks
void permute(apvector<int>& numbers, int blockSize)
{
    RandGen rnd;    // random number generator
    int positionToSwap;
    int temp;

    for(int i = 0; i < numbers.length()/blockSize; i++)
        for(int j = 0; j < blockSize; j++)
        {
            // the position to swap is a random integer in that block
            positionToSwap = rnd.RandInt(i*blockSize, i*blockSize+j);

            // swap the jth element of the block with the element at positionToSwap
            temp = numbers[positionToSwap];
            numbers[positionToSwap] = numbers[i*blockSize+j];
            numbers[i*blockSize+j] = temp;
        }

}

int main()
{
    string dummy;   // dummy string to clear the input stream
    RandGen rnd;    // random number generator
    SysTimer timer; // system timer
    apvector<int> apv;   // apvector
    double runningTime1 = 0.0, runningTime2 = 0.0; // elapsed time for Sort1 and Sort2, respectively

    // node pointers for singly linked list
    node<int> *cursor;
    node<int> *head;

    // dnode pointers for doubly linked list
    dnode<int> *dcursor;
    dnode<int> *current;


    cout << "Testing Problem 1 Sort1...\n"
         << "Please enter one integer per line, enter a letter to end input\n";
    head = Sort1();

    // print out the list sorted by Sort1
    for(cursor = head; cursor != NULL; cursor = cursor->link())
        cout << cursor->data() << " ";
    cout << endl;

    cin.clear();    // reset the input stream
    cin >> dummy;   // ignore the input of the wrong data type

    cout << endl << "Testing Problem 1 Sort2...\n"
         << "Please enter one integer per line, enter a letter to end input\n";
    current = Sort2();

    // move the current pointer back to the head of the list
    while(current != NULL && current->back() != NULL)
        current = current->back();

    // print out the list sorted by Sort2
    for(dcursor = current; dcursor != NULL; dcursor = dcursor->fore())
        cout << dcursor->data() << " ";
    cout << endl;

    cin.clear();    // reset the input stream
    cin >> dummy;   // ignore the input of the wrong data type

    cout << endl << "Testing Problem 2...\n";

    for(int n = 1000; n <= 1000; n += 1000)
    {
        apv.resize(n);

        // 10 iterations
        for(int i = 0; i < 10; i++)
        {
            // each element is a random integer between 1 and n
            for(int j = 0; j < n; j++)
                apv[j] = rnd.RandInt(1, n);

            // time Sort1
            timer.start();
            head = Sort1(apv);
            timer.stop();
            runningTime1 += timer.elapsedTime();

            // time Sort2
            timer.start();
            current = Sort2(apv);
            timer.stop();
            runningTime2 += timer.elapsedTime();
        }

        // average of 10 iterations
        runningTime1 /= 10;
        runningTime2 /= 10;
        cout << "n = " << n << ": " << "Sort1 time = " << runningTime1
             << ", Sort2 time = " << runningTime2 << endl;

        // reset elapsed time to 0 for the next n
        runningTime1 = 0.0;
        runningTime2 = 0.0;
    }

    cout << endl << "Testing Problem 3...\n";

    for(int n = 1000; n <= 1000; n += 1000)
    {
        apv.resize(n);

        // a sorted array containing elements from 1 to n
        for(int j = 0; j < n; j++)
            apv[j] = j + 1;

        // 10 iterations
        for(int i = 0; i < 10; i++)
        {
            permute(apv, 10); // generate an almost sorted array with a block size of 10

            // time Sort1
            timer.start();
            head = Sort1(apv);
            timer.stop();
            runningTime1 += timer.elapsedTime();

            // time Sort2
            timer.start();
            current = Sort2(apv);
            timer.stop();
            runningTime2 += timer.elapsedTime();
        }

        // average of 10 iterations
        runningTime1 /= 10;
        runningTime2 /= 10;
        cout << "n = " << n << ": " << "Sort1 time = " << runningTime1
             << ", Sort2 time = " << runningTime2 << endl;

        // reset elapsed time to 0 for the next n
        runningTime1 = 0.0;
        runningTime2 = 0.0;
    }


    return EXIT_SUCCESS;
}