import java.util.ArrayList;
import java.util.Arrays;

/**
 * a class for several sorting algorithms
 * 
 * @author 
 *
 */
public class Sort {
  
  
  /**
   * minsort - O(N**2) sorting (also: selection sort)
   * @param A, an array of ints, to be sorted in place
   */
  public static void minsort(int[] A) {
    // TODO - write minsort
  }
  
  
  
  
  /**
   * bucketsort - O(N) sorting, sort of...
   * @param A, an array of ints, to be sorted in place
   */
  public static void bucketsort(int[] A) {
    // TODO - write bucketsort
  }
  

  
  /**
   * this Heap class implements a binary min-heap
   * it uses Java's ArrayList<Integer> as the storage for
   *    its data, named this.heapdata
   *   
   * Here's the official ArrayList documentation:
   *   docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html
   *   
   * Here are all of the ArrayList methods I used:
   *  - heapdata.size() ~ the # of nodes currently in the heap
   *  - heapdata.set( i, val ) ~ sets element i to have a value of val
   *  - heapdata.get( i ) ~ returns the value at index i
   *  
   * Here are two methods used in the provided code below (not in percolate):
   *  - heapdata.remove( i ) ~ removes the element at index i
   *  - heapdata.add( val ) ~ adds one element to the end of the heap
   *                          it has value val
   *                          after this call, heapdata.size() has increased by 1
   *                          
   * At all times (except just before calling percolate_up and percolate_down),
   * the heap property should be true:
   *   Every node is less than (or equal to) both its children
   */
  static class Heap
  {
    /**
     * this.heapdata is the storage for our heap
     * 
     * indexing reminders:
     * 
     * for an element at index i:
     *    its parent is at index (i-1)/2
     *    its leftchild is at index 2*i+1
     *    its rightchild is at index 2*i+2
     */
    public ArrayList<Integer> heapdata;
    
    /**
     * constructor for our Heap class
     */
    public Heap() {
      this.heapdata = new ArrayList<Integer>(); // construct our heapdata
    }
    
    /**
     * our toString method, delegating to the ArrayList toString method
     * @return the string representation of this.heapdata
     */
    public String toString() {
      return "" + this.heapdata; // Uses ArrayList's toString method
    }
    
    /**
     * this method also delegates to the ArrayList size method
     * @return the number of nodes currently in the Heap
     */
    public int size() {
      return this.heapdata.size(); // Uses ArrayList's size method
    }
    
    /**
     * percolate_up should adjust the last element of the heap
     *    by swapping it with its parent, grandparent, ...
     *    until the heap property is satisfied
     */
    private void percolate_up() {
      // TODO - write percolate_up
    }
    
    /**
     * percolate_down should adjust the first element of the heap
     *    by swapping it with its smaller child, grandchild, ...
     *    until the heap property is satisfied
     */
    private void percolate_down() {
      // TODO - write percolate_down
    }
    
    /**
     * inserts an element to the heap and maintains the heap property
     * @param val, the value to be inserted to the heap
     */
    public void heap_insert(int val) {
      this.heapdata.add(val); // adds to the back of the heapdata
      this.percolate_up();  // fixes the heap up!
    }
    
    /**
     * removes and returns the minimum value in the heap
     *   it makes sure the heap property is maintained, too
     * @return the smallest value that was in the heap
     */
    public int heap_remove_min() {
      if (this.size() <= 0)  {
        System.out.println("Error: can not remove from an empty heap.");
        return -1;
      }
      // get the min, remove the last element, and then fix things up...
      int min = heapdata.get(0);
      int end = heapdata.remove(heapdata.size()-1); // size is now one smaller
      // percolate if there are elements still in the heap!
      if (heapdata.size() > 0) {
        this.heapdata.set(0, end);
        this.percolate_down(); 
      }
      // now, we return that min
      return min;
    }
  }
  
  /**
   * heapsort sorts by creating a min-heap and then removing
   *     consecutive minimum elements until it's done!
   * @param A, the array to be sorted
   */
  public static void heapsort(int[] A) {
    // create our heap, H
    Heap H = new Sort.Heap();
    // put all of the elements into the heap
    for (int n:A) {
      H.heap_insert(n);
      //System.out.println("Add " + n + " to get " + H);
    }
    // take the min values out of the heap
    for (int i=0 ; i<A.length ; ++i) {
      A[i] = H.heap_remove_min();
      //System.out.println("Remove first " + A[i] + " to leave " + H);
    }
    //System.out.println("A is now " + Arrays.toString(A));
    return;
  }

  /**
   * main, used for less formal tests than the JUnit ones...
   * @param args, the command-line inputs, not used here
   */
  public static void main(String[] args) {
    int[] A = { 6, 2, 9, 3, 4, 8, 0, 1, 7, 5 };
    //int[] A = { 9, 9, 0, 9, 9, 0, 0, 0, 9, 0, 7 };
    System.out.println("A is " + Arrays.toString(A));
    //bucketsort( A );
    heapsort( A );
    //minsort(A);
    System.out.println("A is " + Arrays.toString(A));
  }
  
  
  
  /**
   * extra credit #2 - quicksort
   *   sorts in place - and without add'l arrays!
   * @param A, an array of ints
   */
  public static void quicksort(int[] A) {
    // TODO - if you'd like to try the ex. cr.
    Arrays.sort( A );
    // this lets all the tests pass, for now...
    // though it won't count as ex cr :^)
  }

}