//
// Test of Sorting Algorithms
//
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <cstdlib>
#include <ctime>

void bubbleSort(
    std::vector<double>::iterator first, // First element of the segment,
    std::vector<double>::iterator last   // element after the last
);

void directSort(
    std::vector<double>::iterator first, // First element of the segment,
    std::vector<double>::iterator last   // element after the last
);

void heapSort(
    std::vector<double>::iterator first, // First element of the segment,
    std::vector<double>::iterator last   // element after the last
);

void merge(
    std::vector<double>::iterator a0,   // Beginning of first array
    std::vector<double>::iterator a1,   // After-end of first array
    std::vector<double>::iterator b0,   // Beginning of second array
    std::vector<double>::iterator b1,   // After-end of second array
    std::vector<double>::iterator c     // Beginning of resulting array
);

void mergeSortTopBottom(
    std::vector<double>::iterator first, // Beginning of array segment to sort
    std::vector<double>::iterator last   // After-end of array segment to sort
);

void mergeSortRecursive(
    std::vector<double>::iterator first, // Beginning of array segment to sort
    std::vector<double>::iterator last,  // After-end of array segment to sort
    std::vector<double>::iterator tmpMem // Beginnig of temporary memory
);

void mergeSortBottomTop(
    std::vector<double>::iterator first, // Beginning of array segment to sort
    std::vector<double>::iterator last   // After-end of array segment to sort
);

void bubbleDown(
    std::vector<double>::iterator first,    // First element of the segment,
    size_t n,                               // size of array segment,
    size_t k                                // Element to sieve
);

void printArray(
    std::vector<double>::iterator first,    // First element of the segment,
    std::vector<double>::iterator last      // element after the last
);

int main() {
    std::cout << "Test of Sorting Algorithms" << std::endl;
    
    // Initialize a random generator
    time_t tim, ttt;
    tim = time(&ttt);
    std::cout << "Seconds since beginning of epoche: " << tim << std::endl;
    srand((unsigned int) tim);
    
    while (true) {
        std::cout << "Which algorithm?" << std::endl
            << "1 -- Bubble Sort, 2 -- Direct Sort," << std::endl
            << "3 -- Heap Sort, 4 -- Merge Sort Bottom-Top" << std::endl
            << "5 -- Merge Sort Top-Bottom, 0 -- quit:" << std::endl;
        int alg = 1;
        std::cin >> alg;
        if (!std::cin.good() || alg <= 0 || alg > 5)
            break;
        size_t n;    
        std::cout << "Size of array:" << std::endl;
        std::cin >> n;
        if (!std::cin.good() || n == 0)
            break;
        std::vector<double> a(n);
        
        // Generate a random contents
        for (size_t i = 0; i < n; ++i) {
            double v = 1000.*double(rand())/double(RAND_MAX);
            a[i] = v;
        }
        std::cout << "Source array:" << std::endl; 
        printArray(a.begin(), a.end());
        std::cout << "--------" << std::endl; 
        
        if (alg == 1) {
            bubbleSort(a.begin(), a.end());
        } else if (alg == 2) {
            directSort(a.begin(), a.end());
        } else if (alg == 3) {
            heapSort(a.begin(), a.end());
        } else if (alg == 4) {
            mergeSortBottomTop(a.begin(), a.end());
        } else if (alg == 5) {
            mergeSortTopBottom(a.begin(), a.end());
        }
        std::cout << "Sorted array:" << std::endl; 
        printArray(a.begin(), a.end());
        std::cout << "--------" << std::endl; 
    }     
    return 0;
}        
        
void printArray(
    std::vector<double>::iterator first,    // First element of the segment,
    std::vector<double>::iterator last      // element after the last
) {
    std::cout << std::fixed << std::setprecision(3);
    size_t n = last - first;
    if (n <= 1000) {
        for (size_t i = 0; i < n; ++i) {
            if (i > 0) {
                // Print a delimiter
                if (i%5 == 0) 
                    std::cout << std::endl;
                else
                    std::cout << " ";
            }
            std::cout << first[i];
        }
    } else {
        for (size_t i = 0; i < 100; ++i) {
            if (i > 0) {
                // Print a delimiter
                if (i%5 == 0) 
                    std::cout << std::endl;
                else
                    std::cout << " ";
            }
            std::cout << first[i];
        }
        std::cout << std::endl << "..." << std::endl;
        for (size_t i = n-100; i < n; ++i) {
            if (i > n-100) {
                // Print a delimiter
                if (i%5 == 0) 
                    std::cout << std::endl;
                else
                    std::cout << " ";
            }
            std::cout << first[i];
        }
    }
    std::cout << std::endl;
}    

void bubbleSort(
    std::vector<double>::iterator a,    // First element of the segment,
    std::vector<double>::iterator last  // element after the last
) {
    bool wasInversions = true;
    int pass = 0;
    size_t n = last - a;
    while (wasInversions) {
        wasInversions = false;
        for (size_t i = 0; i < n-1-pass; ++i) {
            if (a[i] > a[i+1]) {
                std::swap(a[i], a[i+1]);
                wasInversions = true;
            }
        }
        ++pass;
    }
}   

void directSort(
    std::vector<double>::iterator a,    // Beginning of array segment to sort
    std::vector<double>::iterator last  // After-end of array segment
) {
    size_t n = last - a;
    for (size_t i = 0; i < n-1; ++i) {
        size_t indMin = i;
        for (size_t j = i+1; j < n; ++j) {
            if (a[j] < a[indMin])
                indMin = j;
        }
        if (indMin != i)
            std::swap(a[i], a[indMin]);
    }
}

void heapSort(
    std::vector<double>::iterator a,    // First element of the segment,
    std::vector<double>::iterator last  // element after the last
) {
    //... to be implemented...
    std::cout << "heapSort is not implemented yet..." << std::endl;

}

void bubbleDown(
    std::vector<double>::iterator a,    // First element of the segment,
    size_t n,                           // size of array segment,
    size_t k                            // Element to sieve
) {
    while (true) {
        size_t s1 = 2*k + 1;    // Left son of k
        if (s1 >= n)
            break;
        size_t s2 = s1 + 1;     // Right son of k
        size_t s = s1;          // Elder son   
        if (s2 < n && a[s2] > a[s1])
            s = s2;
        if (a[k] >= a[s])
            break;
        std::swap(a[k], a[s]);
        k = s;
    }
}    

void mergeSortTopBottom(
    std::vector<double>::iterator first, // Beginning of array segment to sort
    std::vector<double>::iterator last   // After-end of array segment to sort
) {
    size_t n = last - first;
    std::vector<double> tmpMem(n);
    mergeSortRecursive(
        first, last,
        tmpMem.begin()
    );
}

void mergeSortRecursive(
    std::vector<double>::iterator first, // Beginning of array segment to sort
    std::vector<double>::iterator last,  // After-end of array segment to sort
    std::vector<double>::iterator tmpMem // Beginnig of temporary memory
) {
    //... to be implemented...
    std::cout << "mergeSortRecursive is not implemented yet..." << std::endl;

}

void mergeSortBottomTop(
    std::vector<double>::iterator first, // Beginning of array segment to sort
    std::vector<double>::iterator last   // After-end of array segment to sort
) {
    //... to be implemented...
    std::cout << "mergeSortBottomTop is not implemented yet..." << std::endl;

}

void merge(
    std::vector<double>::iterator a0,   // Beginning of first array
    std::vector<double>::iterator a1,   // After-end of first array
    std::vector<double>::iterator b0,   // Beginning of second array
    std::vector<double>::iterator b1,   // After-end of second array
    std::vector<double>::iterator c     // Beginning of resulting array
) {
    while (a0 != a1 && b0 != b1) {
        if (*a0 <= *b0) {
            *c = *a0;
            ++a0;
        } else {
            *c = *b0;
            ++b0;
        }
        ++c;
    }
    while (a0 != a1) {
        *c = *a0;
        ++c; ++a0;
    }
    while (b0 != b1) {
        *c = *b0;
        ++c; ++b0;
    }
}