package org.maachang.rimdb.index ;

import java.util.Arrays;

/**
 * 基数ソート.
 * このソートでは、1つのSortLinesにのみ対応しています.
 * 
 * @version 2014/07/19
 * @author  masahito suzuki
 * @since   rimdb-1.00
 */
public final class ResultRadixSort {
    protected ResultRadixSort() {}
    
    /**
     * ソート処理.
     * @param sortLines ソート対象のインデックス行番号ソート情報を設定します.
     * @param desc [true]の場合降順でソートされます.
     * @param list ソート対象の数値リストを設定します.
     * @param length ソート対象のデータ長を設定します.
     * @param max ソート対象の最大値を設定します.
     */
    public static final void sort( final SortLines sortLines,final boolean desc,
        final int[] list,final int length,final int max ) {
        
        // 件数が一定以上の場合は、基数ソート.
        if( length > ResultSort.CHANGE_SORT ) {
            
            rsort( desc,sortLines.list,list,length,max ) ;
        }
        // 件数が一定以下の場合は、挿入コムソート.
        else {
            
            csort( desc,sortLines.list,list,length ) ;
        }
    }
    
    /** 256配列での基数ソート. **/
    protected static final void rsort( final boolean desc,final int[] sortLines,
        final int[] list,final int length,final int max ) {
        
        // 処理回数を計算.
        final int len ;
        if( max < 0x00000100 ) {
            len = 8 ;
        }
        else if( max < 0x00010000 ) {
            len = 16 ;
        }
        else if( max < 0x01000000 ) {
            len = 24 ;
        }
        else {
            len = 32 ;
        }
        
        int i,bb ;
        final int[] h = new int[ 256 ] ;
        final int[] b = new int[ length ] ;
        
        for( int shift = 0 ; shift < len ; shift += 8 ) {
            for( i = 0 ; i < length ; i ++ ) {
                h[ ( sortLines[ list[ i ] ] >> shift) & 255 ] ++ ;
                b[ i ] = list[ i ] ;
            }
            // 降順.
            if( desc ) {
                for( i = 255 ; i > 0 ; i -- ) {
                    h[ i - 1 ] += h[ i ] ;
                }
            }
            // 昇順.
            else {
                for( i = 1 ; i < 256 ; i ++ ) {
                    h[ i ] += h[ i - 1 ] ;
                }
            }
            for( i = length ; i > 0 ; ) {
                list[ ( --h[ ( sortLines[ bb=b[ -- i ] ] >> shift ) & 255 ] ) ] = bb ;
            }
            Arrays.fill( h,0,256,0 ) ;
        }
    }
    
    /** 挿入コムソート. **/
    protected static final void csort( final boolean desc,final int[] sortLines,
        final int[] list,final int length ) {
        // 比較的処理件数が少ない場合に呼び出される.
        
        int i,t,j,k ;
        int gap = length ;
        
        // 降順.
        if( desc ) {
            
            while( gap > 20 ) {
                gap = (int)( gap / 1.37 ) ;
                if( gap == 9 || gap == 10 ) {
                    gap = 11 ;
                }
                for( i = 0 ; i + gap < length ; i ++ ) {
                    if( sortLines[ list[ i + gap ] ] > sortLines[ list[ i ] ] ) {
                        t = list[ i ] ;
                        list[ i ] = list[ i + gap ] ;
                        list[ i + gap ] = t ;
                    }
                }
            }
            
            for( i = 1 ; i < length ; i ++ ) {
                t = list[ i ] ;
                j = i ; k = i ;
                if( sortLines[ t ] > sortLines[ list[ 0 ] ] ) {
                    while( j > 0 ) {
                        list[ j ] = list[ --k ] ;
                        j = k ;
                    }
                }
                else {
                    while( sortLines[ t ] > sortLines[ list[ --k ] ] ) {
                        list[ j ] = list[ k ] ;
                        j = k ;
                    }
                }
                list[ j ] = t ;
            }
        }
        // 昇順.
        else {
            
            while( gap > 20 ) {
                gap = (int)( gap / 1.37 ) ;
                if( gap == 9 || gap == 10 ) {
                    gap = 11 ;
                }
                for( i = 0 ; i + gap < length ; i ++ ) {
                    if( sortLines[ list[ i + gap ] ] < sortLines[ list[ i ] ] ) {
                        t = list[ i ] ;
                        list[ i ] = list[ i + gap ] ;
                        list[ i + gap ] = t ;
                    }
                }
            }
            
            for( i = 1 ; i < length ; i ++ ) {
                t = list[ i ] ;
                j = i ; k = i ;
                if( sortLines[ t ] < sortLines[ list[ 0 ] ] ) {
                    while( j > 0 ) {
                        list[ j ] = list[ --k ] ;
                        j = k ;
                    }
                }
                else {
                    while( sortLines[ t ] < sortLines[ list[ --k ] ] ) {
                        list[ j ] = list[ k ] ;
                        j = k ;
                    }
                }
                list[ j ] = t ;
            }
        }
        
    }
}
