package tmp;

import java.util.Random;

/**
 * Implements the classic partitioning routine. Chooses a pivot and partitions the given
 * array of integers around that.
 */
public class ClassicPartition {

    /**
     * Partitions the given array in place in O(n) time. Chooses a random pivot which is placed at the 0th index.
     * The invariant maintained is that after every number (starting from index 1) is read, the pivot could
     * be placed at the index that is its correctly sorted position in the partial subarray examined so far.
     *
     * @param a an integer array that is partitioned in place
     * @return integer representing the index of the pivot; if this method returns a number i, then the following holds:
     * <pre>
     *     a[j] < pivot for all 0 <= j < i, and
     *     a[j] >= pivot for all i+1 <= j < a.length
     * </pre>
     */
    static int partition(int[] a) {
        setPivot(a);
        int pivot = a[0];
//        System.out.println("pivot: " + pivot);
        int pi = 0; //pi is the sorted index of the pivot
        for (int i = 1; i < a.length; i++) {
            if (a[i] < pivot) {
                a[pi] = a[i];
                a[i] = a[pi + 1];
                pi += 1;
            }
        }
        a[pi] = pivot;
        return pi;
    }

    private static int setPivot(int[] a, int... defaultIndex) {
        int i = -1;
        if (defaultIndex.length == 1) {
            int defi = defaultIndex[0];
            if (defi < 0 || defi >= a.length) {
                throw new IllegalArgumentException("defaultIndex: " + defi + " invalid for array length: " + a.length);
            }
            i = defi;
        } else {
            Random r = new Random(System.currentTimeMillis()); // no need for a repeatable random value
            i = r.nextInt(a.length);
        }
        int t = a[0];
        a[0] = a[i];
        a[i] = t;
        return i;
    }
}

@@ -24,16 +24,38 @@
 va.util.
+concurrent.ThreadLocal
 Random;%0A
@@ -528,16 +528,8 @@
 the 
-partial 
 suba
@@ -546,14 +546,18 @@
 ned 
-so far
+until then
 .%0A  
@@ -868,24 +868,135 @@
    * %3C/pre%3E%0A
+     * I believe Nick Lomuto has a very similar routine, but I can say that I came up with this independently.%0A
      */%0A    
@@ -1023,16 +1023,32 @@
 (int%5B%5D a
+, int lo, int hi
 ) %7B%0A    
@@ -1061,16 +1061,24 @@
 tPivot(a
+, lo, hi
 );%0A     
@@ -1094,17 +1094,18 @@
 vot = a%5B
-0
+lo
 %5D;%0A//   
@@ -1230,16 +1230,21 @@
  i =
+ lo +
  1; i %3C 
 a.le
@@ -1239,24 +1239,18 @@
  1; i %3C 
-a.lengt
 h
+i
 ; i++) %7B
@@ -1444,16 +1444,100 @@
 %0A    %7D%0A%0A
+    static int partition(int%5B%5Da) %7B%0A        return partition(a, 0, a.length);%0A    %7D%0A%0A
     priv
@@ -1564,24 +1564,40 @@
 vot(int%5B%5D a,
+ int lo, int hi,
  int... defa
@@ -1620,18 +1620,210 @@
     
+// remember: li is inclusive and hi is exclusive%0A        if (hi - lo %3C 1) %7B%0A            throw new IllegalArgumentException(%22low: %22 + lo + %22, high: %22 + hi + %22 fail the contract%22);%0A        %7D%0A        
 int i
- = -1
 ;%0A  
@@ -1923,17 +1923,18 @@
 (defi %3C 
-0
+lo
  %7C%7C defi
@@ -1937,24 +1937,18 @@
 defi %3E= 
-a.lengt
 h
+i
 ) %7B%0A    
@@ -2038,34 +2038,60 @@
 for 
-array length: %22 + a.length
+given low (incl): %22 + lo + %22 and high (excl): %22 + hi
 );%0A 
@@ -2158,117 +2158,39 @@
     
-Random r = new Random(System.currentTimeMillis()); // no need for a repeatable random value%0A            i = r
+i = ThreadLocalRandom.current()
 .nex
@@ -2194,24 +2194,22 @@
 nextInt(
-a.length
+lo, hi
 );%0A     

make partition routine more general