peca

#include "MergeP.h"



MergeP::MergeP(const char* inCharArray, size_t leftFirst, size_t leftLast, size_t rightFirst,
    size_t rightLast, char* outCharArray, size_t outIndex) :
    inCharArray(inCharArray),
    leftFirst(leftFirst),
    leftLast(leftLast),
    rightFirst(rightFirst),
    rightLast(rightLast),
    outCharArray(outCharArray),
    outIndex(outIndex)
{
}


MergeP::~MergeP()
{
}

task * MergeP::execute()
{
    size_t dim1 = leftLast - leftFirst + 1;
    size_t dim2 = rightLast - rightFirst + 1;

    if (dim1 < dim2)
    {
        swap(leftFirst, rightFirst);
        swap(leftLast, rightLast);
        swap(dim1, dim2);
    }

    if (dim1 == 0) return NULL;
    if (dim1 + dim2 <= 8192)
        MergeSerial(leftFirst, leftLast, rightFirst, rightLast, outIndex);
    else
    {
        size_t mid1 = leftFirst + (leftLast - leftFirst) / 2;
        size_t mid2 = BinarySearch(inCharArray[mid1], rightFirst, rightLast);
        size_t mid3 = outIndex + (mid1 - leftFirst) + (mid2 - rightFirst);
        outCharArray[mid3] = inCharArray[mid1];

        MergeP* mergeOne = new(task::allocate_child()) MergeP(inCharArray, leftFirst, size_t(mid1 - 1),
            rightFirst, size_t(mid2 - 1), outCharArray, outIndex);
        MergeP* mergeTwo = new(task::allocate_child()) MergeP(inCharArray, size_t(mid1 + 1), leftLast,
            mid2, rightLast, outCharArray, size_t(mid3 + 1));

        set_ref_count(3);
        spawn(*mergeOne);
        spawn_and_wait_for_all(*mergeTwo);
    }
    return NULL;
}

size_t MergeP::BinarySearch(char x, size_t first, size_t last)
{
    size_t low = first;
    size_t high = max(first, size_t(last + 1));
    while (low < high)
    {
        size_t mid = low + (high - low) / 2;
        if (x <= inCharArray[mid])
            high = mid;
        else
            low = size_t(mid + 1);
    }

    return high;
}

void MergeP::MergeSerial(size_t leftFirst, size_t leftLast, size_t rightFirst, size_t rightLast, size_t outIndex)
{
    while (leftFirst <= leftLast && rightFirst <= rightLast)
    {
        if (inCharArray[leftFirst] <= inCharArray[rightFirst])
            outCharArray[outIndex++] = inCharArray[leftFirst++];
        else
            outCharArray[outIndex++] = inCharArray[rightFirst++];
    }
    while (leftFirst <= leftLast)
        outCharArray[outIndex++] = inCharArray[leftFirst++];
    while (rightFirst <= rightLast)
        outCharArray[outIndex++] = inCharArray[rightFirst++];
}