@@ -0,0 +1,1945 @@
+/*-%0A * Copyright (c) 2014 Mikolaj Izdebski%0A *%0A * Licensed under the Apache License, Version 2.0 (the %22License%22);%0A * you may not use this file except in compliance with the License.%0A * You may obtain a copy of the License at%0A *%0A *     http://www.apache.org/licenses/LICENSE-2.0%0A *%0A * Unless required by applicable law or agreed to in writing, software%0A * distributed under the License is distributed on an %22AS IS%22 BASIS,%0A * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.%0A * See the License for the specific language governing permissions and%0A * limitations under the License.%0A */%0Apackage org.lbzip2.impl;%0A%0Aimport static org.lbzip2.impl.Unsigned.umin;%0A%0A/**%0A * A simple BWT implementation based on LSD radix sort.%0A * %0A * @author Mikolaj Izdebski%0A */%0Aclass RadixSortBWT%0A    implements BWT%0A%7B%0A    public int transform( int%5B%5D B, int n )%0A    %7B%0A        int%5B%5D U = new int%5B256%5D;%0A        int%5B%5D C = new int%5B256%5D;%0A        int%5B%5D P = new int%5Bn%5D;%0A        int%5B%5D R = new int%5Bn%5D;%0A%0A        for ( int i = 0; i %3C n; i++ )%0A        %7B%0A            C%5BB%5Bi%5D%5D++;%0A            P%5Bi%5D = i;%0A        %7D%0A%0A        int cum = 0;%0A        for ( int i = 0; i %3C 256; i++ )%0A            C%5Bi%5D = ( cum += C%5Bi%5D ) - C%5Bi%5D;%0A        assert cum == n;%0A%0A        for ( int d = 1; d %3C= n; d++ )%0A        %7B%0A            System.arraycopy( C, 0, U, 0, 256 );%0A%0A            for ( int i = 0; i %3C n; i++ )%0A            %7B%0A                int j = P%5Bi%5D;%0A                int t = umin( j - d, j - d + n );%0A                R%5BU%5BB%5Bt%5D%5D++%5D = j;%0A            %7D%0A%0A            int%5B%5D T = P;%0A            P = R;%0A            R = T;%0A        %7D%0A%0A        System.arraycopy( B, 0, R, 0, n );%0A        int idx = n;%0A        for ( int i = 0; i %3C n; i++ )%0A        %7B%0A            int j = P%5Bi%5D;%0A            if ( j == 0 )%0A            %7B%0A                assert idx == n;%0A                idx = i;%0A                j = n;%0A            %7D%0A%0A            B%5Bi%5D = R%5Bj - 1%5D;%0A        %7D%0A%0A        assert idx %3C n;%0A        return idx;%0A    %7D%0A%7D%0A

Implement BWT based on LSD radix sort