import java.util.ArrayList;
import java.util.Collections;
import java.util.TreeSet;

/**
 * Driver that performs heap sort on a list of numbers.
 *
 *   @author Dave Reed
 *   @version 10/9/18
 */
public class TreeSorts {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        for (int i = 1; i <= 10; i++) {
            nums.add(i);
        }
        Collections.shuffle(nums);
        
        System.out.println(nums);
        
        TreeSorts.heapSort(nums);
        
        System.out.println(nums);
        
        Collections.shuffle(nums);
        
        System.out.println(nums);
        
        TreeSorts.redBlackSort(nums);
        
        System.out.println(nums);
    }
    
    public static void heapSort(ArrayList<Integer> items) {
        MinHeap<Integer> itemHeap = new MinHeap<Integer>();
        for (int i = 0; i < items.size(); i++) {
            itemHeap.add(items.get(i));
        }

        for (int i = 0; i < items.size(); i++) {
            items.set(i, itemHeap.minValue());
            itemHeap.remove();
        }
    }    
    
    public static void redBlackSort(ArrayList<Integer> items) {
        TreeSet<Integer> itemSet = new TreeSet<Integer>();
        for (int i = 0; i < items.size(); i++) {
            itemSet.add(items.get(i));
        }

        int i = 0;
        for (int val : itemSet) {
            items.set(i, val);
            i++;
        }
    }  
}