import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import junit.framework.TestCase;

public class SorterTests extends TestCase {
    
    private ISorter sorter;
    
    public void setUp() {
        // modify this to test different versions of sort
        sorter = new Sorter1();
    }
    
    /** Make sure that sort correctly handles a null input. */
    public void testCheckForNull() {
        assertNull("sort should return null for null input", sorter.sort(null));
    }
    
    /** Make sure that sort correctly handles an empty array as input. */
    public void testCheckForEmpty() {
        int[] orig = {};
        int[] sorted = sorter.sort(orig);
        assertEquals("sort of an empty list is non-null and empty", 0, sorted.length);       
    }
    
    /** Make sure that the output of sort is actually sorted. */
    public void testSorted() {
        int[] orig = {1,-5,8,2,3,-6,2,7,5,9,0};
        int[] sorted = sorter.sort(orig);
        assertTrue("Output of sort should be sorted", isSorted(sorted));
    }

    /** Make sure that the output of sort contains exactly the same elements as the input. */
    public void testElements() {
        int[] orig = {4,4,4,5,5,6,2,3,1,1};
        int[] sorted = sorter.sort(orig);
        Map<Integer, Integer> origElts   = countElts(orig)
                            , sortedElts = countElts(sorted);        
        
        assertEquals("sort should result in a list containing exactly the same elements as the input list", origElts, sortedElts);        
    }
    
    /** Make sure that sort does not modify the input array. */
    public void testPurity() {
        int[] origOrig = {2,8,4,1,2,0,0,-208,48};
        int[] orig = {2,8,4,1,2,0,0,-208,48};
        sorter.sort(orig);
        assertTrue("sort should not modify the input array", Arrays.equals(origOrig, orig));
    }
    
    /** Helper method to count the occurrences of each element in an array. */
    private Map<Integer, Integer> countElts(int[] list) {
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for ( int elt : list ) {
            if ( counts.containsKey(elt) ) {
                counts.put(elt, counts.get(elt) + 1);
            } else {
                counts.put(elt, 1);
            }
        }
        return counts;
    }
    
    /** Helper method to check whether a list is sorted. */
    private boolean isSorted(int[] list) {
        if ( list != null && list.length > 1 ) {
            for (int i = 0; i < list.length - 1; i++) {
                if ( list[i] > list[i+1] )
                    return false;
            }
        }
        return true;
    }
}