package org.maachang.rimdb.index ;

/**
 * 数字KeyValue.
 * 
 * @version 2014/06/29
 * @author  masahito suzuki
 * @since   rimdb-1.00
 */
@SuppressWarnings("unchecked")
public final class IndexUtil {
    private IndexUtil(){} ;
    
    /**
     * 完全一致検索.
     * @param a 対象の配列を設定します.
     * @param key 対象のキーを設定します.
     * @return int 項番が返却されます.
     *             [-1]が返却された場合、情報は存在しません.
     */
    public static final int searchInt( final int[] a,final int key ) {
        int low = 0 ;
        int high = a.length - 1 ;
        int mid,midVal ;
        while (low <= high) {
            if ((midVal = a[(mid = (low + high) >>> 1)]) < key) {
                low = mid + 1 ;
            }
            else if (midVal > key) {
                high = mid - 1 ;
            }
            else {
                return mid ;
            }
        }
        return -1 ;
    }
    
    /**
     * 大なり小なり検索.
     * @param big [true]の場合、第三引数が第二引数の検知条件より大きい条件(>=)を対象とします.
     * @param a 対象の配列を設定します.
     * @param key 対象のキーを設定します.
     * @return int 項番が返却されます.
     *             [-1]が返却された場合、情報は存在しません.
     */
    public static final int searchIntBS( final boolean big,final int[] a,final int key ) {
        int low = 0 ;
        int high = a.length - 1 ;
        int mid,midVal ;
        mid = 0 ;
        while (low <= high) {
            if (( midVal = a[( mid = (low + high) >>> 1 )] ) < key) {
                low = mid + 1 ;
            }
            else if (midVal > key) {
                high = mid - 1 ;
            }
            else {
                return mid ;
            }
        }
        if( big ) {
            if( a[mid] > key ) {
                return mid ;
            }
            else if( a.length <= mid + 1 ) {
                return a.length-1 ;
            }
            return mid + 1 ;
        }
        if( a[mid] > key ) {
            if( mid <= 0 ) {
                return 0 ;
            }
            return mid -1 ;
        }
        return mid ;
    }
    
    /**
     * 完全一致検索.
     * @param a 対象の配列を設定します.
     * @param key 対象のキーを設定します.
     * @return int 項番が返却されます.
     *             [-1]が返却された場合、情報は存在しません.
     */
    public static final int searchLong( final long[] a,final long key ) {
        int low = 0 ;
        int high = a.length - 1 ;
        int mid ;
        long midVal ;
        while (low <= high) {
            if ((midVal = a[(mid = (low + high) >>> 1)]) < key) {
                low = mid + 1 ;
            }
            else if (midVal > key) {
                high = mid - 1 ;
            }
            else {
                return mid ;
            }
        }
        return -1 ;
    }
    
    /**
     * 大なり小なり検索.
     * @param big [true]の場合、第三引数が第二引数の検知条件より大きい条件(>=)を対象とします.
     * @param a 対象の配列を設定します.
     * @param key 対象のキーを設定します.
     * @return int 項番が返却されます.
     *             [-1]が返却された場合、情報は存在しません.
     */
    public static final int searchLongBS( final boolean big,final long[] a,final long key ) {
        int low = 0 ;
        int high = a.length - 1 ;
        int mid ;
        long midVal ;
        mid = 0 ;
        while (low <= high) {
            if (( midVal = a[( mid = (low + high) >>> 1 )] ) < key) {
                low = mid + 1 ;
            }
            else if (midVal > key) {
                high = mid - 1 ;
            }
            else {
                return mid ;
            }
        }
        if( big ) {
            if( a[mid] > key ) {
                return mid ;
            }
            else if( a.length <= mid + 1 ) {
                return a.length-1 ;
            }
            return mid + 1 ;
        }
        if( a[mid] > key ) {
            if( mid <= 0 ) {
                return 0 ;
            }
            return mid -1 ;
        }
        return mid ;
    }
    
    /**
     * 完全一致検索.
     * @param a 対象の配列を設定します.
     * @param key 対象のキーを設定します.
     * @return int 項番が返却されます.
     *             [-1]が返却された場合、情報は存在しません.
     */
    public static final int search( final Comparable[] a, final Comparable key) {
        int low = 0 ;
        int high = a.length -1 ;
        int mid,cmp ;
        while (low <= high) {
            if ((cmp = a[mid = (low + high) >>> 1].compareTo(key)) < 0) {
                low = mid + 1;
            }
            else if (cmp > 0) {
                high = mid - 1;
            }
            else {
                return mid;
            }
        }
        return -1 ;
    }
    
    /**
     * 大なり小なり検索.
     * @param big [true]の場合、第三引数が第二引数の検知条件より大きい条件(>=)を対象とします.
     * @param a 対象の配列を設定します.
     * @param key 対象のキーを設定します.
     * @return int 項番が返却されます.
     *             [-1]が返却された場合、情報は存在しません.
     */
    public static final int searchBS( final boolean big,final Comparable[] a,final Comparable key ) {
        int low = 0 ;
        int high = a.length -1 ;
        int mid,cmp ;
        mid = 0 ;
        while (low <= high) {
            if ((cmp = a[mid = (low + high) >>> 1].compareTo(key)) < 0) {
                low = mid + 1;
            }
            else if (cmp > 0) {
                high = mid - 1;
            }
            else {
                return mid;
            }
        }
        if( big ) {
            if( a[mid].compareTo( key ) > 0 ) {
                return mid ;
            }
            else if( a.length <= mid + 1 ) {
                return a.length-1 ;
            }
            return mid + 1 ;
        }
        if( a[mid].compareTo( key ) > 0 ) {
            if( mid <= 0 ) {
                return 0 ;
            }
            return mid -1 ;
        }
        return mid ;
    }
}
