package ru.ifmo.nds.util;

public final class SplitMergeHelper {
    private final int[] scratchM, scratchR;

    public SplitMergeHelper(int size) {
        scratchM = new int[size];
        scratchR = new int[size];
    }

    public final int splitInTwo(double[] points, int[] indices,
                                int tempFrom, int from, int until, double median,
                                boolean equalToLeft, double minVal, double maxVal) {
        if (minVal == median && maxVal == median) {
            return equalToLeft ? until : from;
        } else if (minVal > median || !equalToLeft && minVal == median) {
            return from;
        } else if (maxVal < median || equalToLeft && maxVal == median) {
            return until;
        } else {
            int left = from, right = tempFrom;
            for (int i = from; i < until; ++i) {
                int ii = indices[i];
                double v = points[ii];
                if (v < median || (equalToLeft && v == median)) {
                    indices[left++] = ii;
                } else {
                    scratchR[right++] = ii;
                }
            }
            System.arraycopy(scratchR, tempFrom, indices, left, right - tempFrom);
            return left;
        }
    }

    public final long splitInThree(double[] points, int[] indices,
                                   int tempFrom, int from, int until, double median,
                                   double minVal, double maxVal) {
        if (minVal == median && maxVal == median) {
            return pack(from, until);
        } else if (minVal > median) {
            return pack(from, from);
        } else if (maxVal < median) {
            return pack(until, until);
        } else {
            int l = from, m = tempFrom, r = tempFrom;
            for (int i = from; i < until; ++i) {
                int ii = indices[i];
                double v = points[ii];
                if (v < median) {
                    indices[l++] = ii;
                } else if (v == median) {
                    scratchM[m++] = ii;
                } else {
                    scratchR[r++] = ii;
                }
            }
            System.arraycopy(scratchM, tempFrom, indices, l, m - tempFrom);
            System.arraycopy(scratchR, tempFrom, indices, l + m - tempFrom, r - tempFrom);
            return pack(l, m - tempFrom + l);
        }
    }

    public final int mergeTwo(int[] indices, int tempFrom, int fromLeft, int untilLeft, int fromRight, int untilRight) {
        int target = tempFrom;
        int l = fromLeft, r = fromRight;
        while (l < untilLeft && r < untilRight) {
            if (indices[l] <= indices[r]) {
                scratchM[target++] = indices[l++];
            } else {
                scratchM[target++] = indices[r++];
            }
        }
        int newR = fromLeft + (target - tempFrom) + untilLeft - l;
        if (r != newR && untilRight > r) {
            // copy the remainder of right to its place
            System.arraycopy(indices, r, indices, newR, untilRight - r);
        }
        if (l != fromLeft + (target - tempFrom) && untilLeft > l) {
            // copy the remainder of left to its place
            System.arraycopy(indices, l, indices, fromLeft + (target - tempFrom), untilLeft - l);
        }
        if (target > tempFrom) {
            // copy the merged part
            System.arraycopy(scratchM, tempFrom, indices, fromLeft, target - tempFrom);
        }
        return fromLeft + (target - tempFrom) + untilLeft - l + untilRight - r;
    }

    private static long pack(int mid, int right) {
        return (((long) (mid)) << 32) ^ right;
    }

    public static int extractMid(long packed) {
        return (int) (packed >>> 32);
    }

    public static int extractRight(long packed) {
        return (int) (packed);
    }
}

@@ -1033,26 +1033,24 @@
 ces%5Bleft
-++
 %5D = ii;%0A
         
@@ -1033,32 +1033,60 @@
 ces%5Bleft%5D = ii;%0A
+                    ++left;%0A
                 
@@ -1128,26 +1128,24 @@
 hR%5Bright
-++
 %5D = ii;%0A
         
@@ -1128,32 +1128,61 @@
 hR%5Bright%5D = ii;%0A
+                    ++right;%0A
                 
@@ -2042,26 +2042,24 @@
 ndices%5Bl
-++
 %5D = ii;%0A
         
@@ -2042,32 +2042,57 @@
 ndices%5Bl%5D = ii;%0A
+                    ++l;%0A
                 
@@ -2147,26 +2147,24 @@
 ratchM%5Bm
-++
 %5D = ii;%0A
         
@@ -2147,32 +2147,57 @@
 ratchM%5Bm%5D = ii;%0A
+                    ++m;%0A
                 
@@ -2239,18 +2239,16 @@
 hR%5Br
-++
 %5D = ii;%0A
     
@@ -2235,32 +2235,57 @@
 ratchR%5Br%5D = ii;%0A
+                    ++r;%0A
                 
@@ -2735,13 +2735,10 @@
     
-while
+if
  (l 
@@ -2783,19 +2783,24 @@
        i
-f (
+nt il = 
 indices%5B
@@ -2805,60 +2805,294 @@
 s%5Bl%5D
- %3C= indices%5Br%5D) %7B%0A                scratchM%5Btarget++%5D
+;%0A            int ir = indices%5Br%5D;%0A            while (true) %7B%0A                if (il %3C= ir) %7B%0A                    scratchM%5Btarget%5D = il;%0A                    ++target;%0A                    if (++l == untilLeft) %7B%0A                        break;%0A                    %7D%0A                    il
  = i
@@ -3099,18 +3099,16 @@
 ndices%5Bl
-++
 %5D;%0A     
@@ -3106,32 +3106,36 @@
 l%5D;%0A            
+ 
+   
 %7D else %7B%0A       
@@ -3119,32 +3119,36 @@
        %7D else %7B%0A
+    
                 
@@ -3166,27 +3166,198 @@
 rget
-++%5D = indices%5Br++%5D;
+%5D = ir;%0A                    ++target;%0A                    if (++r == untilRight) %7B%0A                        break;%0A                    %7D%0A                    ir = indices%5Br%5D;%0A                %7D
 %0A   

Improve SplitMergeHelper.mergeTwo by arranging variables accurately.