package sorts;

import java.util.concurrent.RecursiveAction;
/**
 * FJQuickSort_Partial.java
 * Here is a partial implementation that may help you implement FJQuickSort_MINE.
 * 
 */
public class FJQuickSort_Partial extends GenericSortAlgorithm {

    // Secondary array used by the algorithm.
    private int[] other;
    // Flag indicating which array currently holds the subarray to be sorted.
    // If true, then "array" (from GenericSortAlgorithm) is the destination.
    // If false, then "other" is the destination.
    private boolean AIsArray;
    // Cutoff threshold for using sequential sorting.
    private static final int QS_CUTOFF = 10000;
    private static final int PART_CUTOFF = 50000;

    // Default constructor.
    public FJQuickSort_Partial() {
    }

    // Constructor used for recursive tasks.
    public FJQuickSort_Partial(int[] primary, int[] other, int left, int right, boolean aIsDest) {
        super(primary, left, right);
        // THIS bug took a long time!
		if (aIsDest) {
			this.array = primary;
			this.other = other;
		} else {
			this.array = other;
			this.other = primary;
		}
        this.AIsArray = aIsDest;
    }

	@Override
	public String getName() {
		return "FJQS Mine";
	}

    /**
     * Overridden sort method. Allocates the secondary array and then invokes the sort.
     */
    @Override
    public void sort(int[] array) {
        int n = array.length;
        this.array = array;
        this.other = new int[n];
        this.left = 0;
        this.right = n - 1;
        this.AIsArray = true;
        // Use the common pool.
        pool.invoke(this);
    }
    
    /**
     * This is the main compute method for the Fork�Join task.
     * We treat the subarray as [left, right] (inclusive).
     */
    @Override
    protected void compute() { // looks good
        // Set local variables for source and destination arrays.
        // If primaryIsDestination is true, then array is the source and other is the destination;
        // otherwise, other is the source and array is the destination.
        int[] A, B;
        if (AIsArray) {
            A = array;
            B = other;
        } else {
            A = other;
            B = array;
        }
        
        if (right-left < QS_CUTOFF) {
            // For small subarrays, simply sort sequentially.
            quickSort(A, left, right); // Or call a better version!
            // If the sorted output is not in the destination array, copy it.
            if (!AIsArray) {
                parallelCopy(A, B, left, right); 
            }
        } else {
            // For larger subarrays, perform the advanced partition.
            int mid = left + (right - left) / 2;
            swap(A, left, mid);
            int pivotValue = A[left];
            
            // Partition the subarray using our parallel prefix and pack.
            // The partitionP method uses the interval [left, right+1) (right is exclusive).
            Range pivots = partitionP(A, B, left, right + 1, pivotValue, AIsArray);
            
            // Create recursive subtasks with swapped roles:
            FJQuickSort_Partial leftTask = new FJQuickSort_Partial(B, A, left, pivots.lo - 1, !AIsArray);
            FJQuickSort_Partial rightTask = new FJQuickSort_Partial(B, A, pivots.hi, right, !AIsArray);
            leftTask.fork();
            rightTask.compute();
            leftTask.join();
        }
    }


    /**
     * Partition the subarray using a parallel prefix-sum and pack method.
     * The interval is [l, r) (with r exclusive). Returns a Range object such that
     * [Range.lo, Range.hi) are indices where pivotValue is placed.
     */
    private Range partitionP(int[] in, int[] out, int l, int r, int pivotValue, boolean inIsDestination) { // looks good
        // TODO Implement me as follows:
    	// Create a root note
    	// Call partition Up
    	// Call partition down (after doing a calculation based on result of partition up.
    	// Create a new Range object based on the results of parition up and down that 
    	// contains the range of the pivots.
    	// Fill in the range with the pivot values
    	// return the range.
    	return null;
    }

    /**
     * Parallel copy from one array to another in the interval [lo, r] (inclusive end).
     */
    private void parallelCopy(int[] in, int[] out, int lo, int hi) { // looks good
        if (hi - lo < PART_CUTOFF) {
            for (int i = lo; i <= hi; i++) {
                out[i] = in[i];
            }
        } else {
            int mid = lo + (hi - lo) / 2;
            ParallelCopyTask task1 = new ParallelCopyTask(in, out, lo, mid-1);
            ParallelCopyTask task2 = new ParallelCopyTask(in, out, mid, hi);
            task1.fork();
            task2.compute();
            task1.join();
        }
    }

    private class ParallelCopyTask extends RecursiveAction { // looks good
        int[] in, out;
        int lo, hi;
        ParallelCopyTask(int[] in, int[] out, int lo, int hi) {
            this.in = in;
            this.out = out;
            this.lo = lo;
            this.hi = hi;
        }
        @Override
        protected void compute() {
            parallelCopy(in, out, lo, hi);
        }
    }

    /**
     * Inner class to represent a range [lo, hi) (hi exclusive).
     */
    private static class Range { // looks good
        int lo, hi;
        Range(int lo, int hi) { this.lo = lo; this.hi = hi; }
    }

    /**
     * Inner class corresponding to the pnode structure.
     * Represents a segment of the array and holds counts.
     */
    private static class PNode { // looks good.
        PNode left, right;
        int sum, sum2;  // Counts: sum = # of values < pivot, sum2 = # of values > pivot.
        int lo, hi;     // Interval [lo, hi) (hi exclusive)
        int fl, fl2;    // Prefix sums (fromLeft values)
        PNode(int lo, int hi) {
            this.lo = lo; this.hi = hi;
            left = right = null;
            sum = sum2 = fl = fl2 = 0;
        }
    }

    /**
     * Recursively compute counts for the node (partitionUp) in parallel.
     */
    private static void partitionUp(PNode root, int[] in, int pivotValue) {
        // TODO Implement me!
    }

    private static class PartitionUpTask extends RecursiveAction {
        private final PNode node;
        private final int[] in;
        private final int pivotValue;
        public PartitionUpTask(PNode node, int[] in, int pivotValue) {
            this.node = node;
            this.in = in;
            this.pivotValue = pivotValue;
        }
        @Override
        protected void compute() {
            partitionUp(node, in, pivotValue);
        }
    }

    /**
     * Recursively propagate prefix sums and �pack� the elements (partitionDown) in parallel.
     */
    private static void partitionDown(PNode root, int[] in, int[] out, int l, int l2, int pivotValue) {
       // TODO Implement me!
    }

    private static class PartitionDownTask extends RecursiveAction {
        private final PNode node;
        private final int[] in, out;
        private final int l, l2, pivotValue;
        public PartitionDownTask(PNode node, int[] in, int[] out, int l, int l2, int pivotValue) {
            this.node = node;
            this.in = in;
            this.out = out;
            this.l = l;
            this.l2 = l2;
            this.pivotValue = pivotValue;
        }
        @Override
        protected void compute() {
            partitionDown(node, in, out, l, l2, pivotValue);
        }
    }

}