/* 
 * implementations of basic sorting algorithms, and IntList
 */

//using System.Random;

/*
 * Class IntList represents a list of ints; it is our own version
 * of List<int>. 
 * You create the list entries by using add(), one at a time.
 * Once you have a list, you can print it. 
 * 
 * You can get the nth value with get(n), or set the nth value with set(n, val).
 * If n is out of range, get(n) returns 0 and set(n, val) does nothing.
 * 
 */

import java.util.Random;

class Sorters {
}

class IntList {
    // instance variables - replace the example below with your own
    private int[] elements;
    private int currsize;

    /**
     * Constructor for objects of class IntList
     */
    public IntList()
    {
        // initialise instance variables
        final int defaultCapacity = 5;
        currsize = 0;
        elements = new int[defaultCapacity];
    }
    
    /* */
    public IntList(int[] A) {
	currsize = A.length;
        elements = new int[currsize];
	for (int i=0; i<currsize; i++) elements[i] = A[i];
    }
    /* */
    /**
     * parameter constructor, allowing you to predefine a capacity.
     */
    public IntList(int capacity) {
        currsize = 0;
        elements = new int[capacity];
    }
       
    /**
     * add() Adds the value y to the list, at position currsize
     * (that is, at the end of the existing list).
     * The size of the list is incremented.
     * If pos = nums.length, there is no more room, so this version doesn't do anything;
     * THAT PART YOU ARE TO FIX!!
     */
    public void add(int y) {
        if (currsize == elements.length) {
            System.err.println("no more room to add " + y); 
        }
        elements[currsize] = y;
        currsize += 1;      // or currsize++
    }
    
   

    // y is the fill value
    public void Fill(int y) {
	for (int i=currsize; i<elements.length; i++) {
		add(y);
	}
    }

    public void RandomFill() {
	Random r = new Random();
	for (int i=currsize; i<elements.length; i++) {
		add(r.nextInt());
	}
    }

    public void RandomFill(int max) {
	Random r = new Random();
	for (int i=currsize; i<elements.length; i++) {
		add(r.nextInt(max));
	}
    }

    // get nth value, with range check
    public int get(int n) {
        if (n<0 || n >= currsize) {
            System.out.println("Warning: IntList.get() called with out-of-range n = " + n);
            return 0;		// special thing for an otherwise annoying case!
        }
        return elements[n];
    }
    
    // set nth value, with range check
    public void set(int n, int val) {
        if (n<0 || n >= currsize) {
            System.out.println("Warning: IntList.set() called with out-of-range n = " + n);
            return;
        }
        elements[n] = val;
    }
    
    public int size() {
        return currsize;
    }

    
     public void print2() {
         int i=0;
         while (i<currsize) {
            System.out.println(i + ":  " + elements[i]);
            i++;    
        }
    }
    
    
    private void swap(int i, int j) {
	//if (i<0 || i >= currsize || j<0 || j>= currsize) return;
	if (i==j) return;
	int temp = elements[i];
	elements[i] = elements[j];
	elements[j] = temp;
    }

    private static void swap(int [] A, int i, int j) {
	//if (i<0 || i >= currsize || j<0 || j>= currsize) return;
	if (i==j) return;
	int temp = A[i];
	A[i] = A[j];
	A[j] = temp;
    }

    private static void mergeblocks(int[] A, int[] T, int start, int blocksize) {
	mergeblocks2(A, T, start, blocksize, blocksize);
    }

    private static void mergeblocks2(int[] A, int[] T, int start, int block1, int block2) {
        // merge A[start]..A[start+block1-1] and A[start+block1]..A[end],
        // where end = min(start+block1+block2-1, len)
	// destination is temp[start...end]
	// note second block can be partial or empty
	int i = start;
        int j = start+block1;        // second block start
        
        int end1 = start+block1-1;
        int end2 = end1 +block2;

	if (end1 > A.length-1) {	// no second block
	    for (i=start; i<=A.length-1; i++) T[i] = A[i];
	    return;
	}
        
        if (end2 > A.length-1) {
            end2 = A.length-1;
        }
        
        int k = start;
        while (i<=end1 && j<=end2) {
            if (A[i]<A[j]) {
                T[k++] = A[i++];
            } else {
                T[k++] = A[j++];
            }
        }
        if (i>end1) { // copy rest of j
            while (k<=end2) T[k++] = A[j++];
        } else {
            while (k<=end2) T[k++] = A[i++];
        }
    }

    // merges consecutive blocks of size blocksize into sorted chunks of size 2*blocksize
    private static void mergepass(int [] A, int [] temp, int blocksize) {
	int bstart = 0;
	while (bstart < A.length) {
	    mergeblocks(A, temp, bstart, blocksize);
	    bstart += 2*blocksize;
	}
    }

  
   // recursive mergesort
    public void rmsort() {
       	//Stopwatch s = new Stopwatch();
    	long starttime = System.currentTimeMillis();
    	int[] temp = new int[elements.length];
    	rmsort_aux(elements, temp, 0, elements.length -1);
    	long elapsedMilliseconds = System.currentTimeMillis() - starttime;
    	//System.out.println("mergesort took %d milliseconds", elapsedMilliseconds);

    }

    // sorts A[lo]..A[hi] into temp[lo]..temp[hi]
    public static void rmsort_aux(int[] A, int[] temp, int lo, int hi) {
    	if (lo == hi) return;
    	int mid = (lo+hi)/2;
    	rmsort_aux(A,temp,lo,mid);
    	rmsort_aux(A,temp,mid+1,hi);
    	mergeblocks2(A, temp, lo, mid-lo+1, hi-mid);
        for (int i = lo; i<=hi; i++) A[i]=temp[i];
    	
    }
  
    private static void aswap(int[] a1, int[] a2) {
	    int[] temp = a1;
	    a1 = a2;
	    a2 = temp;
    }

    // selection sort
    public void ssort1() {
    	//long starttime = System.currentTimeMillis();
    	for (int i = 0; i<currsize-1; i++) {
    	    // find smallest of elements[i]..elements[currsize-1] and swap to position i
    	    int index_min = i;
    	    int curr_min_val = elements[i];
    	    for (int j = i+1; j<currsize; j++) {
        		if (elements[j] < curr_min_val) {
        		    curr_min_val = elements[j];
        		    index_min = j;
        		}
    	    }
    	    swap(i,index_min);
    	}
    	//long elapsedMilliseconds = System.currentTimeMillis() - starttime;
    	//System.out.printf("selection sort took %d milliseconds%n", elapsedMilliseconds);
    }

    // straight outta Bailey, p 123
    public void ssort() {
    	//long starttime = System.currentTimeMillis();
        int numUnsorted = currsize;
        int index;
        // general index
        int max;
        // index of largest value
        while (numUnsorted > 0) {
            // determine maximum value in array
            max = 0;
            for (index = 1; index < numUnsorted; index++)  {
               if (elements[max] < elements[index]) max = index;
            }
            swap(max,numUnsorted-1);
            numUnsorted--;
        }
    }
    
    public void isort1() {
    	//Stopwatch s = new Stopwatch();
    	long starttime = System.currentTimeMillis();
    	int i;
    	for (int k=1; k<elements.length; k++) {
                 int next = elements[k]; i=k-1;	// next element to put into position
                  while (i > 0 && elements[i] > next) {	// move bigger elements up by 1
                		elements[i+1] = elements[i];
    			i --;
                  }
                  if (i==0) elements[0] = next; else elements[i+1] = next;
    	}
    	long elapsedMilliseconds = System.currentTimeMillis() - starttime;
    	//System.out.printf("insertion sort took %d milliseconds%n", elapsedMilliseconds);

    }

    // Again, straight from Bailey, p 125
    public void isort() {
        int numSorted = 1;  // number of values in place
        int index;          // general index
        while (numSorted < currsize)  {
        // take the first unsorted value
            int temp = elements[numSorted];
            // ...and insert it among the sorted:
            for (index = numSorted; index > 0; index--) {
                if (temp < elements[index-1]) {
                    elements[index] = elements[index-1];
                } else {
                    break;
                }
            }
            // reinsert value
            elements[index] = temp;
            numSorted++;
        }
    }


    
    public void print() {
	for (int i = 0; i< elements.length; i++) {
	    System.out.print(elements[i]);
	    System.out.print(' ');
	}
	System.out.println();
    }

    public void print(int[] A) {
	for (int i = 0; i< A.length; i++) {
	    System.out.print(A[i]);
	    System.out.print(' ');
	}
	System.out.println();
    }

     public static void print3(int [] A) {
	for (int i = 0; i< A.length; i++) {
	    System.out.print(A[i]);
	    System.out.print(' ');
	}
	System.out.println();
    }

     public static void print3(int [] A, int l, int r) {
	for (int i = l; i<= r; i++) {
	    System.out.print(A[i]);
	    System.out.print(' ');
	}
	System.out.println();
    }

    public static void print(int[] A, int left, int pivot, int right) {
	System.out.format("left=%d, pivot=%d, right=%d  ", left, pivot, right);
	print3(A);
    }

    public boolean checksort() {
	for (int i=1; i<elements.length; i++) {
	    if (elements[i-1] > elements[i]) return false;
	}
	return true;
    }

    /**
     * quicksort sort, normal version
     */
    public void qsort1() {
    // pre: 0 <= n <= data.length
    // post: values in data[0..n-1] are in ascending order
        quickSortRecursive1(elements, 0, elements.length-1);
    }
    
    // experimental version
    public void qsort2() {
    // pre: 0 <= n <= data.length
    // post: values in data[0..n-1] are in ascending order
        quickSortRecursive2(elements, 0, elements.length-1);
    }


    // quickSortRecursive1 uses simple_partition(), which sometimes fails!

    private static void quickSortRecursive1(int [] data,int left,int right)
    // pre: left <= right
    // post: data[left..right] in ascending order
    {
        int pivotindex;   // the final location of the leftmost value
        if (left >= right) return;
	int pval = (data[left]+data[right])/2;
        pivotindex = simple_partition(data,pval,left,right);    /* 1 - place pivot */
        quickSortRecursive1(data,left,pivotindex-1); /* 2 - sort small */
        quickSortRecursive1(data,pivotindex,right);/* 3 - sort large */
        /* done! */
    }

    /*
     * this version assumes the pivot value appears in the array. 
     * Partition1 returns a value pivot such that
     * A[left]..A[pivot-1] are all <= A[pivot] <= all A[pivot+1]..A[right]
     * BAD
     */
    private static int bailey_partition(int [] A, int left, int right) {
    // pre: left <= right
    // post: data[left] placed in the correct (returned) location
        int pivotvalue = A[left];
        while (true)
        {
            // move right "pointer" toward left

            // assert: data[left] = pivotvalue
            //int pivotvalue = data[left];
	    //int pivotvalue = data[(left+right)/2];
            
            while (left < right && pivotvalue < A[right]) right--;
            //while (left < right && pivotvalue < data[right]) right--;
            if (left < right) swap(A,left++,right);
            else return left;	// left == right == pivot
	    // now pivotvalue = A[right]
            // move left pointer toward right
            // asssert: data[right] = pivotvalue
            while (left < right && A[left] < pivotvalue) left++;
            //while (left < right && data[left] < pivotvalue) left++;
            if (left < right) swap(A,left,right--);
            else return right;	// left == right == pivot
        }
    }
    
    private static int bailey_partition_orig(int [] A, int left, int right) {
    // pre: left <= right
    // post: data[left] placed in the correct (returned) location
    // pivotvalue = data[left]
        while (true)
        {
            // move right "pointer" toward left

            // assert: data[left] = pivotvalue
            //int pivotvalue = data[left];
	    //int pivotvalue = data[(left+right)/2];
            
            while (left < right && A[left] < A[right]) right--;
            //while (left < right && pivotvalue < data[right]) right--;
            if (left < right) swap(A,left++,right);
            else return left;	// left == right == pivot
            // move left pointer toward right
            // asssert: data[right] = pivotvalue
            while (left < right && A[left] < A[right]) left++;
            //while (left < right && data[left] < pivotvalue) left++;
            if (left < right) swap(A,left,right--);
            else return right;	// left == right == pivot
        }
    }
    
    private static int horvick_partition(int [] items, int left, int right, int pivotIndex) {
	int pivotValue = items[pivotIndex];
	swap(items, pivotIndex, right);
	int storeIndex = left;
	for (int i = left; i < right; i++) {
	    if (items[i] < pivotValue) {
		swap(items, i, storeIndex);
		storeIndex += 1;
	    }
	}
	swap(items, storeIndex, right);
	return storeIndex;
    }


    /*
     * this version takes a pivot value, pivotvalue, and rearranges the array 
     * so that if pi is the value returned, then j<pi => data[j] < pivotvalue
     * and j>=pi => pivotvalue <= data[j]
     * At termination, we know left <= pivotindex <= right
     * bad outcome: pivotindex == origleft
     */
    private static int simple_partition(int [] data, int pivotvalue, int left, int right) {
    // pre: left <= right
    // post: data[left] placed in the correct (returned) location
    // pivotvalue = data[left]
	int retval = 0;
	int origleft = left, origright = right;
        while (true)
        {
            while (left < right && pivotvalue <= data[right]) right--;
	    // now left == right or data[right] < pivotvalue
	    //if (left==right) return right;
            while (left < right && data[left] < pivotvalue) left++;
 	    // now left == right or pivotvalue <= data[left]
            //if (left==right) return left+1;
            if (left < right) swap(data,left,right);
	    else break;
        }
        if (data[right] < pivotvalue) retval = right+1;
        else retval = right;	// left == right == pivot
	//System.out.printf("partition(%d,%d,%d) returns %d%n", pivotvalue, origleft, origright, retval);
	if (retval == origleft) {
		System.out.format("partition(%d,%d,%d) returns %d%n", 
			pivotvalue, origleft, origright, retval);
		print3(data,origleft, origright);
	}
	return retval;
    }
    



    /**
     * in the following version, partition2 returns a value pivot such that
     * A[left]..A[pivot] are all less than A[pivot+1]..A[right]
     * But A[pivot] need not be bigger than any A[i] for i<pivot
     */
    private static void quickSortRecursive2(int [] data,int left,int right)
    // pre: left <= right
    // post: data[left..right] in ascending order
    {
        //System.out.println("left="+left + ", right=" + right);
        int pivot;   // the final location of the leftmost value
        //int pivotvalue;
        
        if (left >= right) return;
        
        pivot = bailey_partition(data,left,right);    /* 1 - place pivot */
	//pivot = horvick_partition(data, left, right, (left+right)/2);
	//print(data, left, pivot, right);
        quickSortRecursive2(data,left,pivot-1); 	/* 2 - sort small */
        quickSortRecursive2(data,pivot+1,right);/* 3 - sort large */
        /* done! */
    }
    

 }