lab4

import java.io.*;
import java.util.*;

public class Lab4
{
    /**
     *  Problem: Sort multi-digit integers (with n total digits) in O(n) time.
     */
    private static void problem(byte[][] arr)
    {
       //get the length of arr
       int length = 0;
       for(int i = 0; i < arr.length; i++){
          if(length < arr[i].length){
          length = arr[i].length;
          }
       }
       //make counting sort array
       int[] countingSort = new int[length+1];
       //add 1 to the index value of the length of arr at i
       for(int i = 0; i < arr.length; i++){
          countingSort[arr[i].length]++;
       }
       //subtract from the first index
       countingSort[0]--;
       //index = index plus previous index
       for(int i = 1; i < countingSort.length; i++){
           countingSort[i] = countingSort[i] + countingSort[i-1];
       }
       //make new array to sort
       byte[][] sortLengths = new byte[arr.length][];
       //put arr in sort array at index counting sort index arr[i].length
       for(int i = arr.length-1; i >= 0; i--){
          sortLengths[countingSort[arr[i].length]] = arr[i];
          countingSort[arr[i].length]--;
       }
       //var for first and last index in sort that have the same length and new counting sort array
       int beg = 0;
       int end = 0;
       int indexPointer = 0;

       byte[][] sortValues = new byte[arr.length][];

       for(int i = 0; i < sortLengths.length; i++) {
           //find the index of where the lengths are the same
           if(sortLengths[beg].length == sortLengths[end].length) {
               end++;
           }
           //if not the same -1 and then counting sort the array
         if(end == sortLengths.length || sortLengths[beg].length < sortLengths[end].length) {

            for(indexPointer = 0; indexPointer < sortLengths[beg].length; indexPointer++){
            int[] radixSort = new int[128];
            radixSort[0]--;
                  //increase index value of number in sort
                  for(int j = beg; j <= end-1; j++) {
                      radixSort[(int) sortLengths[j][indexPointer]]++;
                  }
                  //index = index + prevoius index
                  for(int j = 1; j < radixSort.length; j++) {
                      radixSort[j] = radixSort[j] + radixSort[j-1];
                  }

                  for(int j = end-1; j >= beg; j--) {
                  //take last value and put it in the index
                 sortValues[beg + radixSort[(int) sortLengths[j][indexPointer]]] = sortLengths[j];
                      radixSort[(int) sortLengths[j][indexPointer]]--;
                  }

            }
               beg = end;
           }

       }
       for(int k = 0; k < arr.length; k++){
          arr[k] = sortValues[k];
       }
       //arr = sortValues;

       //for loop with beg end var
       //make array 128
       //



       //System.out.print(" ");
        // Implement me!
    }

    // ---------------------------------------------------------------------
    // Do not change any of the code below!

    private static final int LabNo = 4;
    private static final String quarter = "Winter 2020";

    private static final Random rng = new Random(654321);

    private static boolean testProblem(byte[][] testCase)
    {
        byte[][] numbersCopy = new byte[testCase.length][];

        // Create copy.
        for (int i = 0; i < testCase.length; i++)
        {
            numbersCopy[i] = testCase[i].clone();
        }

        // Sort
        problem(testCase);
        Arrays.sort(numbersCopy, new numberComparator());

        // Compare if both equal
        if (testCase.length != numbersCopy.length)
        {
            return false;
        }

        for (int i = 0; i < testCase.length; i++)
        {
            if (testCase[i].length != numbersCopy[i].length)
            {
                return false;
            }

            for (int j = 0; j < testCase[i].length; j++)
            {
                if (testCase[i][j] != numbersCopy[i][j])
                {
                    return false;
                }
            }
        }

        return true;
    }

    // Very bad way of sorting.
    private static class numberComparator implements Comparator<byte[]>
    {
        @Override
        public int compare(byte[] n1, byte[] n2)
        {
            // Ensure equal length
            if (n1.length < n2.length)
            {
                byte[] tmp = new byte[n2.length];
                for (int i = 0; i < n1.length; i++)
                {
                    tmp[i] = n1[i];
                }
                n1 = tmp;
            }

            if (n1.length > n2.length)
            {
                byte[] tmp = new byte[n1.length];
                for (int i = 0; i < n2.length; i++)
                {
                    tmp[i] = n2[i];
                }
                n2 = tmp;
            }

            // Compare digit by digit.
            for (int i = n1.length - 1; i >=0; i--)
            {
                if (n1[i] < n2[i]) return -1;
                if (n1[i] > n2[i]) return 1;
            }

            return 0;
        }
    }

    public static void main(String args[])
    {
        System.out.println("CS 302 -- " + quarter + " -- Lab " + LabNo);
        testProblems();
    }

    private static void testProblems()
    {
        int noOfLines = 10000;

        System.out.println("-- -- -- -- --");
        System.out.println(noOfLines + " test cases.");

        boolean passedAll = true;

        for (int i = 1; i <= noOfLines; i++)
        {
            byte[][] testCase =  createTestCase(i);

            boolean passed = false;
            boolean exce = false;

            try
            {
                passed = testProblem(testCase);
            }
            catch (Exception ex)
            {
                passed = false;
                exce = true;
            }

            if (!passed)
            {
                System.out.println("Test " + i + " failed!" + (exce ? " (Exception)" : ""));
                passedAll = false;

                break;
            }
        }

        if (passedAll)
        {
            System.out.println("All test passed.");
        }

    }

    private static byte[][] createTestCase(int testNo)
    {
        int maxSize = Math.min(100, testNo) + 5;
        int size = rng.nextInt(maxSize) + 5;

        byte[][] numbers = new byte[size][];

        for (int i = 0; i < size; i++)
        {
            int digits = rng.nextInt(maxSize) + 1;
            numbers[i] = new byte[digits];

            for (int j = 0; j < digits - 1; j++)
            {
                numbers[i][j] = (byte)rng.nextInt(128);
            }

            // Ensures that the most significant digit is not 0.
            numbers[i][digits - 1] = (byte)(rng.nextInt(127) + 1);
        }

        return numbers;
    }

}