package org.maachang.mimdb.core.util ;

/**
 * 数字KeySet.
 * 
 * @version 2013/10/29
 * @author masahito suzuki
 * @since MasterInMemDB 1.00
 */
public final class NumberKeySet {
    private static final int DEF_LENGTH = 32 ;
    
    private static final class NumberKeyChild {
        int b ;
        NumberKeyChild n ;
        NumberKeyChild( int v ) {
            b = v ;
        }
        NumberKeyChild( int v,NumberKeyChild nn ) {
            b = v ;
            n = nn ;
        }
    }
    
    private NumberKeyChild[] list ;
    private int mask ;
    private int length ;
    private int limit ;
    private int base ;
    
    /**
     * コンストラクタ.
     */
    public NumberKeySet() {
        this( DEF_LENGTH ) ;
    }
    
    /**
     * コンストラクタ.
     * @param size 初期サイズを設定します.
     */
    public NumberKeySet( int size ) {
        if( size <= DEF_LENGTH ) {
            size = DEF_LENGTH ;
        }
        else {
            size = NumberKeySet.bitMask( size ) ;
        }
        list = new NumberKeyChild[ size ] ;
        length = 0 ;
        mask = size - 1 ;
        limit = size ;
        base = size ;
    }
    
    /**
     * コンストラクタ.
     * @param mode [true]の場合、第二引数の条件に重複情報は存在しない場合に設定します.
     * @param lst 変換対象のNumberListを設定します.
     */
    public NumberKeySet( boolean mode,NumberList lst ) {
        int[] ary = lst.list ;
        int len = lst.length ;
        int bufLen = NumberKeySet.bitMask( len ) << 1 ;
        
        list = new NumberKeyChild[ bufLen ] ;
        length = len ;
        mask = bufLen - 1 ;
        limit = bufLen ;
        base = bufLen ;
        
        int b,h ;
        if( mode ) {
            // 重複条件が存在しない場合の追加処理.
            for( int i = 0 ; i < len ; i ++ ) {
                b = ary[ i ] ;
                if( list[ ( h = b & mask ) ] == null ) {
                    list[ h ] = new NumberKeyChild( b ) ;
                }
                else {
                    list[ h ] = new NumberKeyChild( b,list[ h ] ) ;
                }
            }
        }
        else {
            // 重複条件が存在する場合の追加処理.
            NumberKeyChild ch ;
            for( int i = 0 ; i < len ; i ++ ) {
                b = ary[ i ] ;
                if( list[ ( h = b & mask ) ] == null ) {
                    list[ h ] = new NumberKeyChild( b ) ;
                }
                else {
                    ch = list[ h ] ;
                    while( ch.n != null ) {
                        if( ch.b == b ) {
                            break ;
                        }
                        ch = ch.n ;
                    }
                    if( ch.b != b ) {
                        ch.n = new NumberKeyChild( b ) ;
                    }
                }
            }
        }
    }
    
    /**
     * クリア.
     */
    public void clear() {
        list = new NumberKeyChild[ base ] ;
        length = 0 ;
        mask = base - 1 ;
        limit = base ;
    }
    
    /**
     * 数値追加.
     * @param b 対象の数値を設定します.
     */
    public void add( int b ) {
        int h ;
        if( length + 1 >= limit ) {
            int nLen = limit << 1 ;
            int msk = nLen - 1 ;
            NumberKeyChild[] nList = new NumberKeyChild[ nLen ] ;
            NumberKeyChild n,t ;
            for( int i = 0 ; i < limit ; i ++ ) {
                n = list[ i ] ;
                while( n != null ) {
                    if( nList[ ( h = n.b & msk ) ] == null ) {
                        t = n.n ;
                        n.n = null ;
                    }
                    else {
                        t = n.n ;
                        n.n = nList[ h ] ;
                    }
                    nList[ h ] = n ;
                    n = t ;
                }
            }
            list = nList ;
            limit = nLen ;
            mask = msk ;
        }
        if( list[ ( h = b & mask ) ] == null ) {
            list[ h ] = new NumberKeyChild( b ) ;
            length ++ ;
        }
        else {
            NumberKeyChild nn = list[ h ] ;
            while( nn.n != null ) {
                if( nn.b == b ) {
                    return ;
                }
                nn = nn.n ;
            }
            if( nn.b != b ) {
                nn.n = new NumberKeyChild( b ) ;
                length ++ ;
            }
        }
    }
    
    /**
     * 情報が存在するかチェック.
     * @param b 対象の数値を設定します.
     * @return boolean [true]の場合、数値は存在します.
     */
    public boolean contains( int b ) {
        if( list[ b & mask ] != null ) {
            NumberKeyChild n = list[ b & mask ] ;
            while( n != null ) {
                if( n.b == b ) {
                    return true ;
                }
                n = n.n ;
            }
        }
        return false ;
    }
    
    /**
     * 削除処理.
     * @param b 対象の数値を設定します.
     */
    public void remove( int b ) {
        if( list[ b & mask ] != null ) {
            NumberKeyChild bf = null ;
            NumberKeyChild n = list[ b & mask ] ;
            while( n != null ) {
                if( n.b == b ) {
                    if( bf == null ) {
                        if( n.n == null ) {
                            list[ b & mask ] = null ;
                        }
                        else {
                            list[ b & mask ] = n.n ;
                        }
                    }
                    else {
                        if( n.n == null ) {
                            bf.n = null ;
                        }
                        else {
                            bf.n = n.n ;
                        }
                    }
                    length -- ;
                    break ;
                }
                bf = n ;
                n = n.n ;
            }
        }
    }
    
    /**
     * サイズを取得.
     * @return int サイズが返却されます.
     */
    public int size() {
        return length ;
    }
    
    /**
     * 数値配列として返却.
     * @return int[] 数値配列として返却します.
     */
    public int[] array() {
        if( length <= 0 ) {
            return null ;
        }
        NumberKeyChild n ;
        int cnt = 0 ;
        int[] ret = new int[ length ] ;
        for( int i = 0 ; i < limit ; i ++ ) {
            if( list[ i ] != null ) {
                n = list[ i ] ;
                while( n != null ) {
                    ret[ cnt ++ ] = n.b ;
                    n = n.n ;
                }
            }
        }
        return ret ;
    }
    
    /** 位置読み込み条件. **/
    private int pos = 0 ;
    private NumberKeyChild cPos = null ;
    
    /**
     * 読み込み中の位置をリセット.
     * @return NumberKeySet このオブジェクトが返却されます.
     */
    public NumberKeySet reset() {
        pos = 0 ;
        cPos = null ;
        return this ;
    }
    
    /**
     * 次の読み込み条件を取得.
     * @return boolean [true]が返却された場合、情報は存在します.
     */
    public boolean hasNext() {
        if( cPos != null ) {
            if( ( cPos = cPos.n ) != null ) {
                return true ;
            }
        }
        while( pos < limit ) {
            if( ( cPos = list[ pos ++ ] ) != null ) {
                return true ;
            }
        }
        return false ;
    }
    
    /**
     * 現在の読み込み位置の情報を取得.
     * @return int 現在の読み込み位置の内容が返却されます.
     *             [-1]の場合は、情報は存在しません.
     */
    public int next() {
        if( cPos == null ) {
            return -1 ;
        }
        return cPos.b ;
    }
    
    /** ビットマスク情報を作成. **/
    protected static final int bitMask( int x ) {
        if( x < 0x00000040 ) {
            return 0x00000040 ;
        }
        x |= ( x >>  1 );
        x |= ( x >>  2 );
        x |= ( x >>  4 );
        x |= ( x >>  8 );
        x |= ( x >> 16 );
        x = (x & 0x55555555) + (x >> 1 & 0x55555555);
        x = (x & 0x33333333) + (x >> 2 & 0x33333333);
        x = (x & 0x0f0f0f0f) + (x >> 4 & 0x0f0f0f0f);
        x = (x & 0x00ff00ff) + (x >> 8 & 0x00ff00ff);
        x = (x & 0x0000ffff) + (x >>16 & 0x0000ffff);
        return 1 << ( ( (x & 0x0000ffff) + (x >>16 & 0x0000ffff) ) - 1 ) ;
    }
}
