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

using namespace std;

b_sort::b_sort(void)
{
    count = 0;
    firstComp = NULL;
    currentComp = NULL;
}

b_sort::~b_sort(void)
{
    while (firstComp != NULL)
    {
        comparator *temp = firstComp->next;
        delete firstComp;
        firstComp = temp;
    }
}

unsigned int b_sort::join(unsigned int i0, unsigned int i1, unsigned int shift, unsigned int n0, unsigned int n1)
{
    unsigned int i, tactCount0, tactCount1;

    if (n0 * n1 < 1)
        return 0;

    if (n0 == 1 && n1 == 1) {
        push(i0, i1);
        return 1;
    }

    tactCount0 = join(i0, i1, shift * 2, n0 - (n0) / 2, n1 - (n1) / 2);
    tactCount1 = join(i0 + shift, i1 + shift, shift * 2, (n0) / 2, (n1) / 2);
    for (i = 1; i < (n0 - 1); i+=2) {
        push(i0+shift*i, i0+shift*(i+1));
    }

    if (n0%2==0) {
        push(i0+shift*(n0-1), i1);

        i = 1;
    } else {
        i = 0;
    }

    for (;i<n1-1;i+=2){
        push(i1+shift*i, i1+shift*(i+1));
    }

    return tactCount0 > tactCount1 ? tactCount0 + 1 : tactCount1 + 1;
}


unsigned int b_sort::sort(unsigned int i, unsigned int step, unsigned int n)
{
    unsigned int tacts0, tacts1, tacts2;

    if (n < 2)
        return 0;

    if (n == 2){
        push(i, i + step);
        return 1;
    }

    tacts0 = sort(i, step, n / 2);
    tacts1 = sort(i + step * (n / 2), step, n - n / 2);
    tacts2 = join(i, i + step * (n / 2), step, n / 2, n - n / 2);
    if (tacts0 > tacts1) {
        return tacts0 + tacts2;
    } else {
        return tacts1 + tacts2;
    }
    return 0;
}


void b_sort::push(unsigned int i0, unsigned int i1)
{
    if (firstComp == NULL) {
        firstComp = new comparator;
        firstComp->first = i0;
        firstComp->second = i1;
        firstComp->next = NULL;
        currentComp = firstComp;
    }
    else {
        currentComp->next = new comparator;
        currentComp = currentComp->next;
        currentComp->first = i0;
        currentComp->second = i1;
        currentComp->next = NULL;
    }
    count++;
}