/*
7/22/2025, 6:03PM, start. X E.
7:32PM, like done untested. X E.
7:50PM, like done, untested. X E.
8:41PM, like done, untested. X E.
7/25/2025, 1:25PM, done better. X E.
7/29/2025, 1:46PM, start fixes for speed. X E.
2:08PM, break, broken. X E.
3:34PM, back.
7/30/2025, 11:56AM, ended 8:30PM yesterday, back today.
7:13PM, like done but could be more accurate. X E.
8/5/2025, 2:29PM, begin revamp. X E.
2:45PM, begin tests. X E. 10:12PM, busted. X E.
8/6/2025, 2:24PM, Made Rust merge sort today, now implementing it here. X E.
2:30PM, like done, testing. X E.
5:24PM, returned to continue. X E.
9:24PM, success? X E.
8/7/2025, 5:52PM, start improvements. X E.
5:54PM, done but untested. X E.
8/22/2025, 1:41PM, start revamp to new. X E.
1:49PM, maybe done. X E. 1:53PM, done. X E.
*/
/*
7/26/2023, 12:32PM, start.
Started by Norvel M. IV, Josiah.
Started on Ubuntu Touch using uText.
I define "X E" and "XE" ending things to mean:
"All that is near and with this me and since like my last adequate uncertainty to this me as per one might be input maybe or might not be input maybe or might be output maybe or might not be output maybe, maybe or maybe not, maybe.".
In a sentence, "A" may be lower case and if a period is after "X E" then period may be omitted from that definition.
This Rinom is intended to allow drawing in 3 or more dimensions using dimension axes on a 2 dimensional screen.
X E.
*/
// Define the input and output buffers
RWStructuredBuffer<float> points;
RWStructuredBuffer<float2> points2d;
RWStructuredBuffer<uint> shapes;
RWStructuredBuffer<uint> shapeEnds;
RWStructuredBuffer<float2> zDists;
RWStructuredBuffer<uint> drawOrder;
RWStructuredBuffer<uint> tempOrder;
// Constant buffer for parameters
cbuffer ComputeParams {
    uint3 xyz;          // 3 integers for x, y, z
    uint unitSize;      // Number of floats per unit
    uint pointNumber;   // Number of points
    uint shapeNumber;   // Number of shapes
    float3 constants;   // 3 float constants
    float2 offset2d;    // 2d offsets
    uint shouldRound;   // Whether to round
    float roundWith;    // What to round with
    float precPad;      // Precision padding
    //X E
};
//X E
uniform uint2 step; // step[0] is number to do to other number of it e.g. 2 to 2 or 1 to 1. step[1] defines drawOrder or tempOrder to other.
//X E

//Note that any more elements than half what a 32 bit number can hold may have bad behavior.
// Compute shader entry point
[shader("compute")]
[numthreads(256, 1, 1)] // Thread group size, adjustable
void mergeSortMain(uint3 id : SV_DispatchThreadID) {
    // Exit early if index is out of bounds or buffer is 0/1 long.
    if (id.x>=shapeNumber||shapeNumber<=1) {
        //X E
        return;
        //X E
    }
    // Identify block [block_start, end) containing `id` and its midpoint `mid`.
    const uint block_start=(id.x/(step[0]*2))*(step[0]*2);
    const uint mid=block_start+step[0];
    //Check for no other half
    if (mid>=shapeNumber) {
        if (step[1]==0) {
            tempOrder[id.x]=drawOrder[id.x];
        } else {
            drawOrder[id.x]=tempOrder[id.x];
        }
        //X E
        return;
        //X E
    }
    uint end=mid+step[0];
    if (end>shapeNumber) {
        end=shapeNumber;
    }
    if (step[1]==0) {
        //drawOrder is from and tempOrder is to.
        const uint x=drawOrder[id.x];
        if (id.x>=mid) {
            //right side
            uint lo=block_start; // left half: [block_start, mid)
            uint hi=mid-1;
            uint m;
            while (lo<hi) {
                m=(lo+hi+1)/2;
                if (zDists[drawOrder[m]][0]>zDists[x][0]||
                    (zDists[drawOrder[m]][0]==zDists[x][0]&&
                    zDists[drawOrder[m]][1]>=zDists[x][1])) { // left[m] >= x ==> element is in prefix, search right
                    lo=m+1;
                } else {           // left[m] < x ==> element is not in prefix, search left (exclude m)
                    hi=m-1;    // Eliminate half+1 by setting hi to m-1
                }
            }
            // Adjust count: lo is the first index where key(lo) < x, so count elements >= x
            // If lo < mid and key(lo) >= x, include lo in the count
            if (lo<mid) {
                if (zDists[drawOrder[lo]][0]>zDists[x][0]||
                    (zDists[drawOrder[lo]][0]==zDists[x][0]&&
                    zDists[drawOrder[lo]][1]>=zDists[x][1])) {
                    tempOrder[lo+id.x-mid+1]=x;
                } else {
                    tempOrder[lo+id.x-mid]=x;
                }
            } else {
                tempOrder[lo+id.x-mid]=x;
            }
        } else {
            //left side
            uint lo=mid;      // right half: [mid, end)
            uint hi=end-1;
            uint m;
            while (lo<hi) {
                m=(lo+hi+1)/2;
                if (zDists[drawOrder[m]][0]>zDists[x][0]||
                    (zDists[drawOrder[m]][0]==zDists[x][0]&&
                    zDists[drawOrder[m]][1]>zDists[x][1])) { // right[m] > x  ==> element is in prefix, search right
                    lo=m+1;
                } else {           // right[m] <= x ==> element is not in prefix, search left (exclude m)
                    hi=m-1;    // Eliminate half+1 by setting hi to m-1
                }
            }
            // Adjust count: lo is the first index where key(lo) <= x, so count elements > x
            // If lo < end and key(lo) > x, include lo in the count
            if (lo<end) {
                if (zDists[drawOrder[lo]][0]>zDists[x][0]||
                    (zDists[drawOrder[lo]][0]==zDists[x][0]&&
                    zDists[drawOrder[lo]][1]>zDists[x][1])) {
                    tempOrder[id.x+lo-mid+1]=x;
                } else {
                    tempOrder[id.x+lo-mid]=x;
                }
            } else {
                tempOrder[id.x+lo-mid]=x;
            }
        }
    } else {
        //tempOrder is from and drawOrder is to.
        const uint x=tempOrder[id.x];
        if (id.x>=mid) {
            //right side
            uint lo=block_start; // left half: [block_start, mid)
            uint hi=mid-1;
            uint m;
            while (lo<hi) {
                m=(lo+hi+1)/2;
                if (zDists[tempOrder[m]][0]>zDists[x][0]||
                    (zDists[tempOrder[m]][0]==zDists[x][0]&&
                    zDists[tempOrder[m]][1]>=zDists[x][1])) { // left[m] >= x ==> element is in prefix, search right
                    lo=m+1;
                } else {           // left[m] < x ==> element is not in prefix, search left (exclude m)
                    hi=m-1;    // Eliminate half+1 by setting hi to m-1
                }
            }
            // Adjust count: lo is the first index where key(lo) < x, so count elements >= x
            // If lo < mid and key(lo) >= x, include lo in the count
            if (lo<mid) {
                if (zDists[tempOrder[lo]][0]>zDists[x][0]||
                    (zDists[tempOrder[lo]][0]==zDists[x][0]&&
                    zDists[tempOrder[lo]][1]>=zDists[x][1])) {
                    drawOrder[lo+id.x-mid+1]=x;
                } else {
                    drawOrder[lo+id.x-mid]=x;
                }
            } else {
                drawOrder[lo+id.x-mid]=x;
            }
        } else {
            //left side
            uint lo=mid;      // right half: [mid, end)
            uint hi=end-1;
            uint m;
            while (lo<hi) {
                m=(lo+hi+1)/2;
                if (zDists[tempOrder[m]][0]>zDists[x][0]||
                    (zDists[tempOrder[m]][0]==zDists[x][0]&&
                    zDists[tempOrder[m]][1]>zDists[x][1])) { // right[m] > x  ==> element is in prefix, search right
                    lo=m+1;
                } else {           // right[m] <= x ==> element is not in prefix, search left (exclude m)
                    hi=m-1;    // Eliminate half+1 by setting hi to m-1
                }
            }
            // Adjust count: lo is the first index where key(lo) <= x, so count elements > x
            // If lo < end and key(lo) > x, include lo in the count
            if (lo<end) {
                if (zDists[tempOrder[lo]][0]>zDists[x][0]||
                    (zDists[tempOrder[lo]][0]==zDists[x][0]&&
                    zDists[tempOrder[lo]][1]>zDists[x][1])) {
                    drawOrder[id.x+lo-mid+1]=x;
                } else {
                    drawOrder[id.x+lo-mid]=x;
                }
            } else {
                drawOrder[id.x+lo-mid]=x;
            }
        }
    }
    //X E
}
//X E