/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

import java.util.concurrent.*;
import java.util.*;

class DoublePairSort {
    static final class DoublePair implements Comparable<DoublePair> {
        public final double fst;
        public final double snd;
        public DoublePair(double f, double s) { fst = f; snd = s; }
        public final int compareTo(DoublePair p) {
            double y = p.fst, x = fst;
            return (x < y) ? -1 : (x > y) ? 1 : 0;
        }
    }

    static final long NPS = (1000L * 1000 * 1000);
    
    public static void main(String[] args) throws Exception {
        int n = 100000000;
        int reps = 30;
        int sreps = 2;
        try {
            if (args.length > 0)
                n = Integer.parseInt(args[0]);
            if (args.length > 1)
                reps = Integer.parseInt(args[1]);
        }
        catch (Exception e) {
            System.out.println("Usage: java ArraysSort n reps");
            return;
        }

        ForkJoinPool pool = ForkJoinPool.commonPool();

        DoublePair[] a = new DoublePair[n];
        DoublePair[] src = new DoublePair[n];
        for (int i = 0; i < n; ++i)
            src[i] = new DoublePair((double)hash(i), (double)i);

        test(src, a, 3, false);
        System.out.println(pool);
        test(src, a, reps, true);
        System.out.println(pool);
    }

    static void test(DoublePair[] src, DoublePair[] a, int reps, boolean par) {
        String lab = par? "par" : "seq";
        int n = src.length;
        System.out.printf("Sorting %d pairs, %d replications\n", n, reps);
        long start = System.nanoTime();
        for (int i = 0; i < reps; ++i) {
            System.arraycopy(src, 0, a, 0, n);
            long last = System.nanoTime();
            if (par)
                java.util.Arrays.parallelSort(a);
            else
                java.util.Arrays.sort(a);
            long now = System.nanoTime();
            double total = (double)(now - start) / NPS;
            double elapsed = (double)(now - last) / NPS;
            System.out.printf("%s sort   time:  %7.3f total %9.3f\n",
                              lab, elapsed, total);
            checkSorted(a);
        }
    }

    // generates a int hash from an int value 
    static int hash(int i) {
        long v = (long)i * 3935559000370003845L + 2691343689449507681L;
        v = v ^ (v >>> 21);
        v = v ^ (v << 37);
        v = v ^ (v >>> 4);
        v = v * 4768777513237032717L;
        v = v ^ (v << 20);
        v = v ^ (v >>> 41);
        v = v ^ (v <<  5);
        return (int) (v & ((1L << 31) - 1L));
    }

    static void checkSorted(DoublePair[] a) {
        int n = a.length;
        double x = a[0].fst, y;
        for (int i = 0; i < n - 1; i++) {
            if (x > (y = a[i+1].fst))
                throw new Error("Unsorted at " + i + ": " + x + " / " + y);
            x = y;
        }
    }
}