package ru.ifmo.nds.util.median;

public final class HoareBidirectionalScanV1b implements DestructiveMedianFactory {
    private static final HoareBidirectionalScanV1b factoryInstance = new HoareBidirectionalScanV1b();

    public static HoareBidirectionalScanV1b instance() {
        return factoryInstance;
    }

    private static final DestructiveMedianAlgorithm algorithmInstance = new DestructiveMedianAlgorithm() {
        @Override
        public int maximumSize() {
            return Integer.MAX_VALUE;
        }

        @Override
        public double solve(double[] array, int from, int until) {
            switch (until - from) {
                case 1:
                    return array[from];
                case 2:
                    return Math.max(array[from], array[from + 1]);
            }

            int index = (from + until) >>> 1;
            int to = until - 1;
            while (to - from >= 3) {
                double pivot = Common.rearrange3(array, from, index, to);

                int l = from, r = to;
                do {
                    //noinspection StatementWithEmptyBody
                    while (array[++l] < pivot);
                    //noinspection StatementWithEmptyBody
                    while (array[--r] > pivot);
                    if (l >= r) {
                        break;
                    }
                    double tmp = array[l];
                    array[l] = array[r];
                    array[r] = tmp;
                } while (true);

                if (l == r) {
                    ++l;
                    --r;
                }

                if (index < r) {
                    to = r;
                } else if (l < index) {
                    from = l;
                } else if (r == index) {
                    return Common.maxUnchecked(array, from, r);
                } else if (l == index) {
                    return Common.minUnchecked(array, l, to);
                } else {
                    return pivot;
                }
            }

            return Common.solve3(array, from);
        }
    };

    @Override
    public DestructiveMedianAlgorithm createInstance(int maxSize) {
        return algorithmInstance;
    }
}

@@ -1058,16 +1058,51 @@
    do %7B%0A
+                    double lv, rv;%0A
         
@@ -1174,24 +1174,30 @@
      while (
+(lv = 
 array%5B++l%5D %3C
@@ -1194,16 +1194,17 @@
 ray%5B++l%5D
+)
  %3C pivot
@@ -1291,16 +1291,22 @@
  while (
+(rv = 
 array%5B--
@@ -1307,16 +1307,17 @@
 ray%5B--r%5D
+)
  %3E pivot
@@ -1410,51 +1410,8 @@
   %7D%0A
-                    double tmp = array%5Bl%5D;%0A
     
@@ -1437,24 +1437,18 @@
 ay%5Bl%5D = 
-array%5Br%5D
+rv
 ;%0A      
@@ -1476,11 +1476,10 @@
 %5D = 
-tmp
+lv
 ;%0A  

bring caching back to the v1b version of Hoare.