package me.alivecode.algs4;

import edu.princeton.cs.algs4.StdOut;

/**
 * Created by oujt on 17-4-5.
 */
public class LSD {
    private static final int BITS_PER_BYTE = 8;

    private LSD() {}

    public static void sort(String[] a) {
        final int n = a.length;
        final int w = a[0].length();

        for(int i = 1; i < n; i++) {
            if (a[i].length() != w) {
                throw new IllegalArgumentException("All strings in a[] must have same length");
            }
        }

        sort(a, w);
    }

    public static void sort(String[] a, int w) {
        final int n = a.length;
        final int R = 256; // for extended ascii

        for(int i = 0; i < n; i++) {
            if (a[i].length() < w) {
                throw new IllegalArgumentException("Length of strings in a[] must longer than equal to " + w);
            }
        }

        String[] aux = new String[n];

        for(int d = w - 1; d >= 0; d--) {
            int[] count = new int[R+1];

            for(int i = 0; i < n; i++) {
                count[a[i].charAt(d) + 1]++;
            }

            for(int r = 0; r < R; r++) {
                count[r+1] += count[r];
            }

            for(int i = 0; i < n; i++) {
                aux[count[a[i].charAt(d)]++] = a[i];
            }

            for(int i = 0; i < n; i++) {
                a[i] = aux[i];
            }
        }
    }

    public static void sort(int[] a) {
        final int BITS = 32;
        final int w = BITS / BITS_PER_BYTE;
        final int R = 256;
        final int mask = R - 1;
        final int n = a.length;
        int[] aux = new int[n];

        for(int d = 0; d < w; d++) {
            int[] count = new int[R+1];

            for(int i = 0; i < n; i++) {
                int c = (a[i] >> (BITS_PER_BYTE * d)) & mask;
                count[c + 1]++;
            }

            for(int r = 0; r < R; r++) {
                count[r+1] += count[r];
            }

            if (d == w - 1) {
                int shift1 = count[R] - count[R/2];
                int shift2 = count[R/2];

                for(int r = 0; r < R/2; r++) {
                    count[r] += shift1;
                }

                for(int r = R/2; r < R; r++) {
                    count[r] -= shift2;
                }
            }

            for(int i = 0; i < n; i++) {
                int c = (a[i] >> (BITS_PER_BYTE * d)) & mask;
                aux[count[c]++] = a[i];
            }

            for(int i = 0; i < n; i++) {
                a[i] = aux[i];
            }

        }
    }

    public static void main(String[] args) {

        StdOut.println("Sorting integer-------------------------------------");
        int[] a = {0xFFFF, 0xFFFFFFFF, 0x80000000, 0x7FFFFFFF };
        sort(a);
        for(int i : a) {
            StdOut.println(i);
        }

        StdOut.println("Sorting string--------------------------------------");
        String[] as = {"her", "and", "his", "dog", "cat", "hen", "are", "big"};
        sort(as);
        for(String s : as) {
            StdOut.println(s);
        }
    }
}

@@ -72,128 +72,513 @@
 %0A * 
-Created by oujt on 17-4-5.%0A */%0Apublic class LSD %7B%0A    private static final int BITS_PER_BYTE = 8;%0A%0A    private LSD() %7B%7D%0A
+The %7B@code LSD%7D class provides static methods for%0A * sorting string array and 32-bit integer array with%0A * Least-Significant-Digit-first radix sort.%0A */%0Apublic class LSD %7B%0A    private static final int BITS_PER_BYTE = 8;%0A%0A    private LSD() %7B%7D%0A%0A    /**%0A     * Rearranges the string array in ascending order.%0A     * All strings in the given array must have same length.%0A     * @param a the array to be sorted%0A     * @throws IllegalArgumentException if strings%0A     * in the array has different length%0A     */
 %0A   
@@ -901,32 +901,272 @@
 t(a, w);%0A    %7D%0A%0A
+    /**%0A     * Rearranges strings in the given array in ascending order.%0A     * @param a the given string array.%0A     *          All strings must longer than or equal to w%0A     * @param w %3Cem%3Ew%3C/em%3Eth to 0 characters to be compared%0A     */%0A
     public stati
@@ -1448,16 +1448,19 @@
 er than 
+or 
 equal to
@@ -2016,32 +2016,206 @@
        %7D%0A    %7D%0A%0A
+    /**%0A     * Rearranges the array of 32-bit integer in ascending order.%0A     * This is about 2x-3x faster than Arrays.sort()%0A     * @param a the array to be sorted%0A     */%0A
     public stati
@@ -2750,32 +2750,144 @@
 %0A            %7D%0A%0A
+            // 0x8000-0xFFFF is less than 0x0000-0x7FFF in%0A            // the left most byte of signed integers%0A
             if (
@@ -3478,24 +3478,46 @@
    %7D%0A    %7D%0A%0A
+    // unit test code%0A
     public s

Add LSD class for sorting strings and integers with Least-Significant-Digit-first algorithm.