/*
 * @author Ranides Atterwim <ranides@gmail.com>
 * @copyright Ranides Atterwim
 * @license WTFPL
 * @url http://ranides.net/projects/assira
 */
package net.ranides.assira.collection.arrays;

import java.util.Arrays;
import java.util.Random;
import org.junit.Test;
import static org.junit.Assert.*;

/**
 *
 * @author Ranides Atterwim <ranides@gmail.com>
 */
public class IntArraySortTest {
    
    public IntArraySortTest() {
    }

    @Test
    public void testQuickSort_cmp() {
        int[] input3 = rangeR(100,200);
        int[] input4 = rangeR(100,200);
           
        IntArraySort.quickSort(input3, (a,b) -> a-b);
        assertArrayEquals(rangeA(100,200), input3);
        
        IntArraySort.quickSort(input4, (a,b) -> b-a);
        assertArrayEquals(rangeD(100, 200), input4);
    }
    
    @Test
    public void testMergeSort() {
        int[] input1 = rangeR(100,200);
           
        IntArraySort.mergeSort(input1);
        assertArrayEquals(rangeA(100,200), input1);
    }
    
    @Test
    public void testMergeSort_cmp() {
        int[] input1 = rangeR(100,200);
        int[] input2 = rangeR(100,200);
           
        IntArraySort.mergeSort(input1, (a,b) -> a-b);
        assertArrayEquals(rangeA(100,200), input1);
        
        IntArraySort.mergeSort(input2, (a,b) -> b-a);
        assertArrayEquals(rangeD(100,200), input2);
    }
    
    @Test
    public void testRadixSort() {
        int[] input1 = rangeR(10,20);
           
        IntArraySort.radixSort(input1);
        assertArrayEquals(rangeA(10,20), input1);
        
        int[] input2 = rangeR(100,200);
           
        IntArraySort.radixSort(input2);
        assertArrayEquals(rangeA(100,200), input2);
    }
    
    @Test
    public void testRadixSort_pairs() {
        int[] input1a = rangeR(100,200);
        int[] input1b = rangeR(100,200);
           
        IntArraySort.radixSort(input1a, input1b);
        assertArrayEquals(rangeA(100,200), input1a);
        assertArrayEquals(rangeA(100,200), input1b);
        
        int[] input2a = new int[]{1,5,3,7,2,4,6};
        int[] input2b = new int[]{5,8,9,1,1,3,2};
        
        IntArraySort.radixSort(input2a, input2b);
        assertArrayEquals(new int[]{1,2,3,4,5,6,7}, input2a);
        assertArrayEquals(new int[]{5,1,9,3,8,2,1}, input2b);
    }
    
    @Test
    public void testRadixSort_indirect() {
        testRadixSort_indirect(true);
        testRadixSort_indirect(false);
    }
    
    private void testRadixSort_indirect(boolean stable) {
        int[] input1a = new int[]{1,5,3,7,2,4,6};
        int[] input1p = new int[]{5,6,4,2,3,0,1};
        int[] input1q = new int[]{0,1,2,3,4,5,6};
           
        IntArraySort.radixSortIndirect(input1p, input1a, stable);

        assertArrayEquals(new int[]{1,5,3,7,2,4,6}, input1a);
        assertArrayEquals(new int[]{0,4,2,5,1,6,3}, input1p);
        
        IntArraySort.radixSortIndirect(input1q, input1a, stable);
        assertArrayEquals(new int[]{1,5,3,7,2,4,6}, input1a);
        assertArrayEquals(new int[]{0,4,2,5,1,6,3}, input1q);
        
        int[] input2a = rangeR(100,200);
        int[] input2p = rangeR(0,100);
        
        IntArraySort.radixSortIndirect(input2p, input2a, stable);
        
        assertArrayEquals(rangeR(100,200), input2a);
        assertArrayEquals(rangeA(100,200), merge(input2p, input2a));
    }
    
    @Test
    public void testRadixSort_indirect_pair() {
        testRadixSort_indirect_pair(true);
        testRadixSort_indirect_pair(false);
    }
    
    private void testRadixSort_indirect_pair(boolean stable) {
        int[] input1a = rangeR(100,200);
        int[] input1b = rangeR(300,400);
        int[] input1p = rangeR(0, input1a.length);
        
        IntArraySort.radixSortIndirect(input1p, input1a, input1b, stable);
        
        assertArrayEquals(rangeR(100,200), input1a);
        assertArrayEquals(rangeR(300,400), input1b);
        assertArrayEquals(rangeA(100,200), merge(input1p, input1a));
        
        int[] input2a = rangeR(10,20);
        int[] input2b = rangeR(30,40);
        int[] input2p = rangeR(0,input2a.length);
        
        IntArraySort.radixSortIndirect(input2p, input2a, input2b, stable);
        
        assertArrayEquals(rangeR(10,20), input2a);
        assertArrayEquals(rangeR(30,40), input2b);
        assertArrayEquals(rangeA(10,20), merge(input2p, input2a));
    }
    
    @Test
    public void testLexicalSort() {
        testLexicalSort(4, 3);
        testLexicalSort(100, 16);
        testLexicalSort(16, 100);
    }
    
    private void testLexicalSort(int m, int n) {
        int[][] array1 = items(m, n);
        
        String[] expected = str(trans(array1));
        Arrays.sort(expected);
        
        IntArraySort.lexicalSort(array1);
        assertArrayEquals(expected, str(trans(array1)));
    }
    
    private static int[][] trans(int[][] array) {
        int M = array.length;
        int N = array[0].length;
        int[][] result = new int[N][M];
        for(int n=0; n<N; n++) {
            for(int m=0; m<M; m++) {
                result[n][m] = array[m][n];
            }
        }
        return result;
    }
    
    private static int[][] items(int m, int n) {
        int[][] result = new int[m][];
        for(int i=0; i<result.length; i++) {
            result[i] = item(637 + i, n);
        }
        return result;
    }
    
    private static int[] item(long seed, int size) {
        Random rand = new Random(seed);
        int result[] = new int[size];
        for(int i=0; i<size; i++) {
            result[i] = 65 + rand.nextInt(26);
        }
        return result;
    }
    
    private static String str(int[] item) {
        char[] chars = new char[item.length];
        for(int i=0; i<item.length; i++) {
            chars[i] = (char)item[i];
        }
        return new String(chars);
    }
    
    private static String[] str(int[][] items) {
        String[] result = new String[items.length];
        for(int i=0; i<result.length; i++) {
            result[i] = str(items[i]);
        }
        return result;
    }
    
    private static int[] merge(int[] perm, int[]values) {
        int[] output = new int[perm.length];
        for(int i=0; i<perm.length; i++) {
            output[i] = values[perm[i]];
        }
        return output;
    }
    
    private static int[] rangeR(int begin, int end) {
        int[] array = rangeA(begin,end);
        ArrayUtils.shuffle(new Random(333), array);
        return array;
    }
    
    private static int[] rangeA(int begin, int end) {
        int[] array = new int[end-begin];
        for(int i=0; i<array.length; i++) {
            array[i] = i+begin;
        }
        return array;
    }
    
    private static int[] rangeD(int begin, int end) {
        int[] array = new int[end-begin];
        for(int i=0; i<array.length; i++) {
            array[i] = end-i-1;
        }
        return array;
    }

}
