package ru.ifmo.nds.util;

import java.util.Arrays;

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) {
        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;
                ++left;
            } else {
                scratchR[right] = ii;
                ++right;
            }
        }
        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) {
        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;
                ++l;
            } else if (v == median) {
                scratchM[m] = ii;
                ++m;
            } else {
                scratchR[r] = ii;
                ++r;
            }
        }
        m -= tempFrom;
        System.arraycopy(scratchM, tempFrom, indices, l, m);
        m += l;
        System.arraycopy(scratchR, tempFrom, indices, m, r - tempFrom);
        return pack(l, m);
    }

    public final int mergeThree(int[] indices, int tempFrom,
                                int fromLeft, int untilLeft,
                                int fromMid, int untilMid,
                                int fromRight, int untilRight) {
        if (fromMid != untilMid) {
            untilLeft = mergeTwo(indices, tempFrom, fromLeft, untilLeft, fromMid, untilMid);
        }
        return mergeTwo(indices, tempFrom, fromLeft, untilLeft, fromRight, untilRight);
    }

    private int mergeTwo(int[] indices, int tempFrom, int fromLeft, int untilLeft, int fromRight, int untilRight) {
        if (fromRight == untilRight) {
            return untilLeft;
        }
        fromLeft = -Arrays.binarySearch(indices, fromLeft, untilLeft, indices[fromRight]) - 1;
        int target = tempFrom;
        int l = fromLeft, r = fromRight;
        if (l < untilLeft && r < untilRight) {
            int il = indices[l];
            int ir = indices[r];
            while (true) {
                if (il <= ir) {
                    scratchM[target] = il;
                    ++target;
                    if (++l == untilLeft) {
                        break;
                    }
                    il = indices[l];
                } else {
                    scratchM[target] = ir;
                    ++target;
                    if (++r == untilRight) {
                        break;
                    }
                    ir = 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 (newR != untilLeft && 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 newR + 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);
    }
}
