package org.maachang.mimdb.core.impl;

import java.util.Arrays;

import org.maachang.mimdb.core.util.NumberKeyValue;
import org.maachang.mimdb.core.util.NumberList;
import org.maachang.mimdb.core.util.ObjectList;

/**
 * NGram情報の作成.
 * 
 * @version 2013/10/17
 * @author masahito suzuki
 * @since MasterInMemDB 1.00
 */
public class NGram {
    private NGram() {}
    
    /** NGramの位置条件. **/
    private static final class NGramInfo implements Comparable<NGramInfo> {
        int position ;  // 文字位置.
        boolean end ;   // 終端文字.
        int lineNo ;    // 行番号.
        public NGramInfo( int p,boolean e,int l ) {
            position = p ; end = e ; lineNo = l ;
        }
        public int compareTo( NGramInfo n ) {
            // 行番号が同じ場合.
            if( lineNo == n.lineNo ) {
                return position - n.position ;
            }
            // 行番号が一致しない場合.
            return lineNo - n.lineNo ;
        }
    }
    
    /** NGram作業領域. **/
    private static final class NGramWork {
        int element ;
        ObjectList<NGramInfo> info = new ObjectList<NGramInfo>() ;
    }
    
    /** NGram要素. **/
    private static final class NGramElement implements Comparable<NGramElement> {
        int element ;           // 要素情報.
        NGramInfo[] info ;      // NGram１データ.
        public int compareTo( NGramElement n ) {
            return element - n.element ;
        }
    }
    
    /** NGramIndex. **/
    private static final class NGramIndex {
        NGramElement[] list ;   // NGram要素.
        MStringIndexKey[] src ; // 元データ.
        int srcLength ;         // 元データ行数.
        int allLength ;         // ngramデータ数.
    }
    
    /**
     * NGramインデックス情報の作成.
     * @param list 対象の文字列群を設定します.
     * @return Object NGramインデックスが返却されます.
     * @exception Exception 例外.
     */
    public static final Object createIndex( MStringIndexKey[] list )
        throws Exception {
        if( list == null ) {
            return null ;
        }
        int n,j,len,lenJ,srcLen ;
        NGramWork w ;
        NumberKeyValue<NGramWork> work ;
        
        // インデックスキー配列.
        char[] s ;
        len = list.length ;
        srcLen = len ;
        // NGram作業リストを作成.
        work = new NumberKeyValue<NGramWork>( len ) ;
        for( int i = 0 ; i < len ; i ++ ) {
            if( list[ i ] == null || list[ i ].length() <= 0 ) {
                continue ;
            }
            s = list[ i ].value ;
            lenJ = s.length ;
            for( j = 0 ; j < lenJ ; j ++ ) {
                n = (int)( s[ j ] & 0x0000ffff ) ;
                if( ( w = work.get( n ) ) == null ) {
                    w = new NGramWork() ;
                    w.element = n ;
                    work.put( n,w ) ;
                }
                w.info.add( new NGramInfo( j,( j + 1 == lenJ ),i ) ) ;
            }
        }
        
        // NGram作業リストを整形.
        int cnt = 0 ;
        int allLength = 0 ;
        NGramInfo[] info ;
        NGramElement em ;
        ObjectList<NGramInfo> tmp ;
        len = work.size() ;
        NumberKeyValue<NGramWork> it = work.reset() ;
        NGramElement[] emList = new NGramElement[ len ] ;
        while( it.hasNext() ) {
            n = it.next() ;
            w = it.nextValue() ;
            tmp = w.info ;
            lenJ = tmp.size() ;
            info = new NGramInfo[ lenJ ] ;
            for( j = 0 ; j < lenJ ; j ++ ) {
                info[ j ] = tmp.get( j ) ;
            }
            allLength += lenJ ;
            Arrays.sort( info ) ; // [NGramInfo]行番号(行番号が同一の場合は、位置情報)毎にソートされる.
            em = new NGramElement() ;
            em.element = n ;
            em.info = info ;
            emList[ cnt ++ ] = em ;
        }
        Arrays.sort( emList ) ;// [NGramElement[]]文字要素毎にソートされる.
        
        NGramIndex ret = new NGramIndex() ;
        ret.list = emList ;
        ret.srcLength = srcLen ;
        ret.src = list ;
        ret.allLength = allLength ;
        return ret ;
        
        // NGramElement[] は文字要素毎でソートされ
        // その内部の情報である[NGramInfo]は、行番号(行番号が同一の場合は、位置情報)毎にソートされる.
    }
    
    /** NGram要素の完全一致検索. **/
    private static final int searchNGramElements( NGramElement[] a,int key) {
        int low = 0 ;
        int high = a.length - 1 ;
        int mid,midVal ;
        while (low <= high) {
            mid = (low + high) >>> 1;
            midVal = a[mid].element;
            if (midVal < key) {
                low = mid + 1;
            }
            else if (midVal > key) {
                high = mid - 1;
            }
            else {
                return mid; // key found
            }
        }
        return -1 ; // key not found.
    }
    
    /** NGram要素内容の位置情報を検索. **/
    private static final int searchNGramInfo( NGramInfo[] a,int key ) {
        int low = 0 ;
        int high = a.length - 1 ;
        int mid,midVal ;
        while (low <= high) {
            mid = (low + high) >>> 1;
            midVal = a[mid].lineNo;
            if (midVal < key) {
                low = mid + 1;
            }
            else if (midVal > key) {
                high = mid - 1;
            }
            else {
                // 同一項番の先頭を返却.
                while( -- mid >= 0 && a[mid].lineNo == key ) ;
                if( mid < 0 ) {
                    return 0 ;
                }
                return mid + 1 ; // key found
            }
        }
        return -1 ; // key not found.
    }
    
    /** 指定位置の次の文字から一致しているかチェック. **/
    private static final int nextEq( MStringIndexKey[] list,int no,MStringIndexKey value,int off ) {
        char[] src = list[ no ].value ;
        char[] chk = value.value ;
        int len = chk.length ;
        if( src.length < off + len ) {
            return -1 ;
        }
        int i = off + 1 ;
        int p = 1 ;
        while( p < len ) {
            if( src[ i ] != chk[ p ] ) {
                break ;
            }
            ++ i ;
            ++ p ;
        }
        if( p == len ) {
            return off ;
        }
        return -1 ;
    }
    
    /** 最後の文字が一致しているかチェック. **/
    private static final int lastEq( MStringIndexKey[] list,int no,MStringIndexKey value,int off ) {
        char[] src = list[ no ].value ;
        char[] chk = value.value ;
        if( src.length < off + chk.length ) {
            return -1 ;
        }
        int i = off ;
        int p = 0 ;
        int len = chk.length - 1 ;
        while( p < len ) {
            if( src[ i ] != chk[ p ] ) {
                break ;
            }
            ++ i ;
            ++ p ;
        }
        if( p == len ) {
            return off ;
        }
        return -1 ;
    }
    
    /**
     * 開始検索.
     * @param ngram createNGramで作成されたオブジェクトを設定します.
     * @param value チェック対象の開始文字列を設定します.
     * @return NGramResult 一致項番群が返却されます.
     *                     [null]の場合、検索結果は存在しません.
     */
    public static final NGramResult startsWith( Object ngram,MStringIndexKey value ) {
        // 先頭位置の情報を検索.
        NGramIndex index = ( NGramIndex )ngram ;
        int p = searchNGramElements( index.list,(int)value.value[ 0 ] ) ;
        if( p == -1 ) {
            return null ;
        }
        // 先頭位置検索.
        NGramInfo in ;
        NGramResult res = new NGramLineList( false,index.srcLength ) ;
        NGramInfo[] info = index.list[ p ].info ;
        int len = info.length ;
        
        // １文字検索指定の場合.
        int strLen = value.length ;
        if( strLen == 1 ) {
            for( int i = 0 ; i < len ; i ++ ) {
                if( info[ i ].position == 0 ) {
                    res.add( info[ i ].lineNo,1 ) ;
                }
            }
        }
        // 複数文字検索の場合.
        else {
            MStringIndexKey[] src = index.src ;
            for( int i = 0 ; i < len ; i ++ ) {
                if( ( in = info[ i ] ).position == 0 && nextEq( src,in.lineNo,value,0 ) == 0 ) {
                    res.add( in.lineNo,strLen ) ;
                }
            }
        }
        return res ;
    }
    
    /**
     * 終端検索.
     * @param and 連結検索条件を設定します.
     * @param ngram createNGramで作成されたオブジェクトを設定します.
     * @param value チェック対象の開始文字列を設定します.
     * @return NGramResult 一致項番群が返却されます.
     *                     [null]の場合、検索結果は存在しません.
     */
    public static final NGramResult endsWith( NGramResult and,Object ngram,MStringIndexKey value ) {
        NGramIndex index = ( NGramIndex )ngram ;
        // 終端条件を検索.
        int strLen = value.length ;
        int p = searchNGramElements( index.list,(int)value.value[ strLen-1 ] ) ;
        if( p == -1 ) {
            return null ;
        }
        
        int lenJ,n,o,j,oLen ;
        int strLenM = strLen - 1 ;
        NGramInfo in ;
        NGramInfo[] info = index.list[ p ].info ;
        
        // 連結検索条件が存在する場合.
        NGramResult res ;
        if( and != null ) {
            // and条件に存在する項番での、終端条件を検索.
            res = and.newList() ;
            int len = and.length() ;
            MStringIndexKey[] src = index.src ;
            MStringIndexKey nowSrc ;
            // 文字情報が１文字の場合.
            if( strLen == 1 ) {
                for( int i = 0 ; i < len ; i ++ ) {
                    if( ( j = searchNGramInfo( info,and.position( i ) ) ) == -1 ) {
                        continue ;
                    }
                    lenJ = info.length ;
                    n = and.position( i ) ;
                    o = and.offset( i ) ;
                    nowSrc = src[ n ] ;
                    for( ; j < lenJ && n == ( in = info[ j ] ).lineNo ; j ++ ) {
                        // 終端文字であり、終端位置-文字長が、
                        // 連結検索された位置よりも大きい場合は、対象とする.
                        if( in.end && in.position - strLenM >= o &&
                            nowSrc.length == o + strLen + 1 ) {
                            res.add( in.lineNo,in.position ) ;
                        }
                    }
                }
            }
            // 複数文字検索の場合.
            else {
                for( int i = 0 ; i < len ; i ++ ) {
                    if( ( j = searchNGramInfo( info,and.position( i ) ) ) == -1 ) {
                        continue ;
                    }
                    lenJ = info.length ;
                    n = and.position( i ) ;
                    o = and.offset( i ) ;
                    nowSrc = src[ n ] ;
                    for( ; j < lenJ && n == ( in = info[ j ] ).lineNo ; j ++ ) {
                        // 終端文字であり、終端位置-文字長が、
                        // 連結検索された位置よりも大きい場合は、対象とする.
                        if( in.end && in.position - strLenM >= o &&
                            nowSrc.length == o + strLen + 1 &&
                            lastEq( src,in.lineNo,value,( oLen = in.position - strLenM ) ) == oLen ) {
                            res.add( in.lineNo,in.position ) ;
                        }
                    }
                }
            }
        }
        // 連結検索条件で無い場合.
        else {
            res = new NGramLineList( false,index.srcLength ) ;
            int len = info.length ;
            // 文字情報が１文字の場合.
            if( strLen == 1 ) {
                for( int i = 0 ; i < len ; i ++ ) {
                    if( info[ i ].end ) {
                        res.add( info[ i ].lineNo,info[ i ].position ) ;
                    }
                }
            }
            // 複数文字検索の場合.
            else {
                MStringIndexKey[] src = index.src ;
                for( int i = 0 ; i < len ; i ++ ) {
                    if( ( in = info[ i ] ).end &&
                        lastEq( src,in.lineNo,value,( oLen = in.position - strLenM ) ) == oLen ) {
                        res.add( in.lineNo,in.position  ) ;
                    }
                }
            }
        }
        return res ;
    }
    
    /**
     * 文字検索.
     * @param and 連結検索条件を設定します.
     * @param ngram createNGramで作成されたオブジェクトを設定します.
     * @param value チェック対象の開始文字列を設定します.
     * @return NGramResult 一致項番群が返却されます.
     *                     [null]の場合、検索結果は存在しません.
     */
    public static final NGramResult indexOf( NGramResult and,Object ngram,MStringIndexKey value ) {
        NGramIndex index = ( NGramIndex )ngram ;
        
        // 指定文字の最初を検索.
        int strLen = value.length ;
        int p = searchNGramElements( index.list,(int)value.value[ 0 ] ) ;
        if( p == -1 ) {
            return null ;
        }
        
        int lenJ,n,o,j ;
        NGramInfo in ;
        NGramInfo[] info = index.list[ p ].info ;
        MStringIndexKey[] src = index.src ;
        
        // 連結検索条件が存在する場合.
        NGramResult res ;
        if( and != null ) {
            // and条件に存在する項番での、終端条件を検索.
            res = and.newList() ;
            int len = and.length() ;
            // １文字検索の場合.
            if( strLen == 1 ) {
                for( int i = 0 ; i < len ; i ++ ) {
                    // 指定ポジションの位置を取得.
                    if( ( j = searchNGramInfo( info,and.position( i ) ) ) == -1 ) {
                        continue ;
                    }
                    lenJ = info.length ;
                    n = and.position( i ) ;
                    o = and.offset( i ) ;
                    for( ; j < lenJ && n == ( in = info[ j ] ).lineNo ; j ++ ) {
                        // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                        if( in.position >= o  ) {
                            res.add( in.lineNo,in.position + strLen ) ;
                            // 一番position位置の低い条件を1件のみ対象とする.
                            break ;
                        }
                    }
                }
            }
            // 複数文字検索の場合.
            else {
                for( int i = 0 ; i < len ; i ++ ) {
                    // 指定ポジションの位置を取得.
                    if( ( j = searchNGramInfo( info,and.position( i ) ) ) == -1 ) {
                        continue ;
                    }
                    lenJ = info.length ;
                    n = and.position( i ) ;
                    o = and.offset( i ) ;
                    for( ; j < lenJ && n == ( in = info[ j ] ).lineNo ; j ++ ) {
                        // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                        if( in.position >= o && nextEq( src,n,value,in.position ) == in.position ) {
                            res.add( in.lineNo,in.position + strLen ) ;
                            // 一番position位置の低い条件を1件のみ対象とする.
                            break ;
                        }
                    }
                }
            }
        }
        // 連結検索条件で無い場合.
        else {
            res = new NGramLineList( false,index.srcLength ) ;
            int len = info.length ;
            // １文字検索の場合.
            if( strLen == 1 ) {
                for( int i = 0 ; i < len ; i ++ ) {
                    // 先頭の１件を対象とする.
                    j = info[ i ].lineNo ;
                    res.add( info[ i ].lineNo,info[ i ].position + strLen ) ;
                    // 次のLineNoまで移動.
                    ++ i ;
                    while( i < len ) {
                        if( info[ i ].lineNo != j ) {
                            -- i ;
                            break ;
                        }
                        ++ i ;
                    }
                }
            }
            // 複数文字検索の場合.
            else {
                for( int i = 0 ; i < len ; i ++ ) {
                    in = info[ i ] ;
                    // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                    if( nextEq( src,in.lineNo,value,in.position ) == in.position ) {
                        res.add( in.lineNo,in.position + strLen ) ;
                        // 次のLineNoまで移動.
                        ++ i ;
                        while( i < len ) {
                            if( info[ i ].lineNo != in.lineNo ) {
                                -- i ;
                                break ;
                            }
                            ++ i ;
                        }
                    }
                }
            }
        }
        return res ;
    }
    
    /**
     * 現在ポジション後に指定文字が連続しているかチェック.
     * @param last 一致した条件が最後方条件としてチェックする場合は[true].
     * @param and 連結検索条件を設定します.
     * @param ngram createNGramで作成されたオブジェクトを設定します.
     * @param value チェック対象の開始文字列を設定します.
     * @param addOff 対象のオフセット位置を移動させて検索する場合に利用します.
     * @param beforeIndexOf 前回のindexof処理時の条件を設定することで、offset配置のやり直しが出来ます.
     * @return NGramResult 一致項番群が返却されます.
     *                     [null]の場合、検索結果は存在しません.
     */
    public static final NGramResult eqaulsPosition( boolean last,NGramResult and,Object ngram,MStringIndexKey value,
        int addOff,MStringIndexKey beforeIndexOf ) {
        NGramIndex index = ( NGramIndex )ngram ;
        
        // 指定文字の最初を検索.
        int strLen = value.length ;
        int p = searchNGramElements( index.list,(int)value.value[ 0 ] ) ;
        if( p == -1 ) {
            return null ;
        }
        
        int lenJ,n,j,bwLen ;
        int o,oo,ooo,op ;
        NGramInfo in ;
        NGramInfo[] info = index.list[ p ].info ;
        MStringIndexKey[] src = index.src ;
        MStringIndexKey nowSrc ;
        
        NGramResult res ;
        
        if( beforeIndexOf != null ) {
            bwLen = beforeIndexOf.length ;
        }
        else {
            bwLen = 0 ;
        }
        
        // 一致条件が最後方一致条件で検索する場合.
        if( last ) {
            
            // 連結検索条件が存在する場合.
            if( and != null ) {
                // and条件に存在する項番での、終端条件を検索.
                res = and.newList() ;
                int len = and.length() ;
                // １文字検索の場合.
                if( strLen == 1 ) {
                    for( int i = 0 ; i < len ; i ++ ) {
                        if( ( j = searchNGramInfo( info,and.position( i ) ) ) == -1 ) {
                            continue ;
                        }
                        lenJ = info.length ;
                        n = and.position( i ) ;
                        o = and.offset( i ) + addOff ;
                        nowSrc = src[ n ] ;
                        // 前回indexof条件が存在しない場合.
                        if( beforeIndexOf == null ) {
                            for( ; j < lenJ && n == ( in = info[ j ] ).lineNo ; j ++ ) {
                                // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                                if( in.position == o && nowSrc.length() == o + strLen ) {
                                    res.add( in.lineNo,o + strLen ) ;
                                    break ;
                                }
                            }
                        }
                        // 前回indexof条件が存在する場合.
                        else {
                            oo = and.offset( i ) - bwLen ;
                            lv_end_one : {
                                for( ; j < lenJ && n == ( in = info[ j ] ).lineNo ; j ++ ) {
                                    // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                                    if( in.position == o && nowSrc.length() == o + strLen ) {
                                        res.add( in.lineNo,o + strLen ) ;
                                        break lv_end_one ;
                                    }
                                    // 見つからない場合は、前のindexof候補を再検索して再度処理.
                                    ooo = oo + 1 ;
                                    while( ( ooo = nowSrc.indexOf( beforeIndexOf,ooo ) ) != -1 ) {
                                        if( in.position == ( op = ooo + bwLen ) + addOff && nowSrc.length == op + addOff + strLen ) {
                                            res.add( in.lineNo,op + addOff + strLen ) ;
                                            break lv_end_one ;
                                        }
                                        ooo ++ ;
                                    }
                                }
                            }
                        }
                    }
                }
                // 複数文字検索の場合.
                else {
                    for( int i = 0 ; i < len ; i ++ ) {
                        if( ( j = searchNGramInfo( info,and.position( i ) ) ) == -1 ) {
                            continue ;
                        }
                        lenJ = info.length ;
                        n = and.position( i ) ;
                        o = and.offset( i ) + addOff ;
                        nowSrc = src[ n ] ;
                        // 前回indexof条件が存在しない場合.
                        if( beforeIndexOf == null ) {
                            for( ; j < lenJ && n == ( in = info[ j ] ).lineNo ; j ++ ) {
                                // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                                if( in.position == o && nowSrc.length() == o + strLen &&
                                    nextEq( src,n,value,o ) == o ) {
                                    res.add( in.lineNo,o + strLen ) ;
                                    break ;
                                }
                            }
                        }
                        // 前回indexof条件が存在する場合.
                        else {
                            oo = and.offset( i ) - bwLen ;
                            lv_end_array : {
                                for( ; j < lenJ && n == ( in = info[ j ] ).lineNo ; j ++ ) {
                                    // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                                    if( in.position == o && nowSrc.length() == o + strLen &&
                                        nextEq( src,n,value,o ) == o ) {
                                        res.add( in.lineNo,o + strLen ) ;
                                        break lv_end_array ;
                                    }
                                    // 見つからない場合は、前のindexof候補を再検索して再度処理.
                                    ooo = oo + 1 ;
                                    while( ( ooo = nowSrc.indexOf( beforeIndexOf,ooo ) ) != -1 ) {
                                        if( in.position == ( op = ooo + bwLen ) + addOff && nowSrc.length == op + addOff + strLen &&
                                            nextEq( src,n,value,op + addOff ) == op + addOff ) {
                                            res.add( in.lineNo,op + addOff + strLen ) ;
                                            break lv_end_array ;
                                        }
                                        ooo ++ ;
                                    }
                                }
                            }
                        }
                    }
                }
            }
            // 連結検索条件で無い場合.
            else {
                res = new NGramLineList( false,index.srcLength ) ;
                int len = info.length ;
                // １文字検索の場合.
                if( strLen == 1 ) {
                    for( int i = 0 ; i < len ; i ++ ) {
                        j = ( in = info[ i ] ).lineNo ;
                        // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                        if( in.position == addOff ) {
                            if( src[ in.lineNo ].length() == strLen + addOff ) {
                                res.add( in.lineNo,strLen + addOff ) ;
                                // 次のLineNoに移動.
                                ++ i ;
                                while( i < len ) {
                                    if( info[ i ].lineNo != j ) {
                                        -- i ;
                                        break ;
                                    }
                                    ++ i ;
                                }
                            }
                        }
                        else {
                            // 次のLineNoに移動.
                            ++ i ;
                            while( i < len ) {
                                if( info[ i ].lineNo != j ) {
                                    -- i ;
                                    break ;
                                }
                                ++ i ;
                            }
                        }
                    }
                }
                // 複数文字検索の場合.
                else {
                    for( int i = 0 ; i < len ; i ++ ) {
                        j = ( in = info[ i ] ).lineNo ;
                        // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                        if( in.position == addOff ) {
                            if( src[ in.lineNo ].length() == strLen + addOff &&
                                nextEq( src,in.lineNo,value,addOff ) == addOff ) {
                                res.add( in.lineNo,strLen + addOff ) ;
                                ++ i ;
                                // 次のLineNoに移動.
                                while( i < len ) {
                                    if( info[ i ].lineNo != j ) {
                                        -- i ;
                                        break ;
                                    }
                                    ++ i ;
                                }
                            }
                        }
                        else {
                            // 次のLineNoに移動.
                            ++ i ;
                            while( i < len ) {
                                if( info[ i ].lineNo != j ) {
                                    -- i ;
                                    break ;
                                }
                                ++ i ;
                            }
                        }
                    }
                }
            }
            
        }
        // 通常一致.
        else {
            
            // 連結検索条件が存在する場合.
            if( and != null ) {
                // and条件に存在する項番での、終端条件を検索.
                res = and.newList() ;
                int len = and.length() ;
                // １文字検索の場合.
                if( strLen == 1 ) {
                    for( int i = 0 ; i < len ; i ++ ) {
                        if( ( j = searchNGramInfo( info,and.position( i ) ) ) == -1 ) {
                            continue ;
                        }
                        lenJ = info.length ;
                        n = and.position( i ) ;
                        o = and.offset( i ) + addOff ;
                        // 前回indexof条件が存在しない場合.
                        if( beforeIndexOf == null ) {
                            for( ; j < lenJ && n == ( in = info[ j ] ).lineNo ; j ++ ) {
                                // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                                if( in.position == o ) {
                                    res.add( in.lineNo,o + strLen ) ;
                                    break ;
                                }
                            }
                        }
                        // 前回indexof条件が存在する場合.
                        else {
                            oo = and.offset( i ) - bwLen ;
                            nowSrc = src[ n ] ;
                            lv_indexof_one : {
                                for( ; j < lenJ && n == ( in = info[ j ] ).lineNo ; j ++ ) {
                                    // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                                    if( in.position == o ) {
                                        res.add( in.lineNo,o + strLen ) ;
                                        break lv_indexof_one ;
                                    }
                                    // 見つからない場合は、前のindexof候補を再検索して再度処理.
                                    ooo = oo + 1 ;
                                    while( ( ooo = nowSrc.indexOf( beforeIndexOf,ooo ) ) != -1 ) {
                                        if( in.position == ( op = ooo + bwLen ) + addOff ) {
                                            res.add( in.lineNo,op + addOff + strLen ) ;
                                            break lv_indexof_one ;
                                        }
                                        ooo ++ ;
                                    }
                                }
                            }
                        }
                    }
                }
                // 複数文字検索の場合.
                else {
                    for( int i = 0 ; i < len ; i ++ ) {
                        if( ( j = searchNGramInfo( info,and.position( i ) ) ) == -1 ) {
                            continue ;
                        }
                        lenJ = info.length ;
                        n = and.position( i ) ;
                        o = and.offset( i ) + addOff ;
                        // 前回indexof条件が存在しない場合.
                        if( beforeIndexOf == null ) {
                            for( ; j < lenJ && n == ( in = info[ j ] ).lineNo ; j ++ ) {
                                // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                                if( in.position == o && nextEq( src,n,value,o ) == o ) {
                                    res.add( in.lineNo,o + strLen ) ;
                                    break ;
                                }
                            }
                        }
                        // 前回indexof条件が存在する場合.
                        else {
                            oo = and.offset( i ) - bwLen ;
                            nowSrc = src[ n ] ;
                            lv_indexof_array : {
                                for( ; j < lenJ && n == ( in = info[ j ] ).lineNo ; j ++ ) {
                                    // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                                    if( in.position == o && nextEq( src,n,value,o ) == o ) {
                                        res.add( in.lineNo,o + strLen ) ;
                                        break lv_indexof_array ;
                                    }
                                    // 見つからない場合は、前のindexof候補を再検索して再度処理.
                                    ooo = oo + 1 ;
                                    while( ( ooo = nowSrc.indexOf( beforeIndexOf,ooo ) ) != -1 ) {
                                        if( in.position == ( op = ooo + bwLen ) + addOff && nextEq( src,n,value,op + addOff ) == op + addOff ) {
                                            res.add( in.lineNo,op + addOff + strLen ) ;
                                            break lv_indexof_array ;
                                        }
                                        ooo ++ ;
                                    }
                                }
                            }
                        }
                    }
                }
            }
            // 連結検索条件で無い場合.
            else {
                res = new NGramLineList( false,index.srcLength ) ;
                int len = info.length ;
                // １文字検索の場合.
                if( strLen == 1 ) {
                    for( int i = 0 ; i < len ; i ++ ) {
                        j = info[ i ].lineNo ;
                        // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                        if( info[ i ].position == addOff ) {
                            res.add( info[ i ].lineNo,strLen + addOff ) ;
                            // 次のLineNoに移動.
                            ++ i ;
                            while( i < len ) {
                                if( info[ i ].lineNo != j ) {
                                    -- i ;
                                    break ;
                                }
                                ++ i ;
                            }
                        }
                        else {
                            // 次のLineNoに移動.
                            ++ i ;
                            while( i < len ) {
                                if( info[ i ].lineNo != j ) {
                                    -- i ;
                                    break ;
                                }
                                ++ i ;
                            }
                        }
                    }
                }
                // 複数文字検索の場合.
                else {
                    for( int i = 0 ; i < len ; i ++ ) {
                        j = info[ i ].lineNo ;
                        // 対象文字位置に対して、連結検索位置が大きい場合は対象とする.
                        if( info[ i ].position == addOff ) {
                            if( nextEq( src,info[ i ].lineNo,value,addOff ) == addOff ) {
                                res.add( info[ i ].lineNo,strLen + addOff ) ;
                                ++ i ;
                                // 次のLineNoに移動.
                                while( i < len ) {
                                    if( info[ i ].lineNo != j ) {
                                        -- i ;
                                        break ;
                                    }
                                    ++ i ;
                                }
                            }
                        }
                        else {
                            // 次のLineNoに移動.
                            ++ i ;
                            while( i < len ) {
                                if( info[ i ].lineNo != j ) {
                                    -- i ;
                                    break ;
                                }
                                ++ i ;
                            }
                        }
                    }
                }
            }
            
        }
        return res ;
    }
}

/** NGram行番号格納リスト. **/
final class NGramLineList implements NGramResult {
    private NumberList mem ;
    private int length ;
    NGramLineList() {}
    NGramLineList( int m ) {
        this( true,m ) ;
    }
    NGramLineList( boolean mode,int m ) {
        if( mode ) {
            NumberList mm = new NumberList( m << 1 ) ;
            for( int i = 0 ; i < m ; i ++ ) {
                mm.add( i ) ;
                mm.add( 0 ) ;
            }
            mem = mm ;
            length = m ;
        }
        else {
            mem = new NumberList( m >> 2 ) ;
            length = 0 ;
        }
    }
    public NGramResult newList() {
        NGramLineList ret = new NGramLineList() ;
        if( length <= 0 ) {
            ret.mem = null ;
            ret.length = 0 ;
        }
        else {
            ret.mem = new NumberList( length >> 2 ) ;
            ret.length = 0 ;
        }
        return ret ;
    }
    public void add( int p,int o ) {
        mem.add( p ) ;
        mem.add( o ) ;
        length ++ ;
    }
    public int length() {
        return length ;
    }
    public int position( int no ) {
        return mem.get( no << 1 ) ;
    }
    public int offset( int no ) {
        return mem.get( ( no << 1 ) + 1 ) ;
    }
    public void offset( int no,int newOff ) {
        mem.set( ( no << 1 ) + 1,newOff ) ;
    }
    public int[] list() {
        int[] ret = new int[ length ] ;
        int j = 0 ;
        for( int i = 0 ; i < length ; i ++ ) {
            ret[ i ] = mem.get( j ) ;
            j += 2 ;
        }
        return ret ;
    }
    protected void endOffset( int off,MStringIndexKey[] src,MStringIndexKey beforeIndexOf ) {
        int len = length ;
        int cnt = 0 ;
        NumberList tmp = new NumberList( len >> 2 ) ;
        if( beforeIndexOf == null ) {
            for( int i = 0,j = 0 ; i < len ; i ++,j += 2 ) {
                if( src[ mem.get( j ) ].length == mem.get( j+1 ) + off ) {
                    tmp.add( mem.get( j ) ) ;
                    tmp.add( mem.get( j+1 ) + off ) ;
                    cnt ++ ;
                }
            }
        }
        else {
            int p,cLen ;
            MStringIndexKey s ;
            int bLen = beforeIndexOf.length ;
            for( int i = 0,j = 0 ; i < len ; i ++,j += 2 ) {
                if( ( s = src[ mem.get( j ) ] ).length == mem.get( j+1 ) + off ) {
                    tmp.add( mem.get( j ) ) ;
                    tmp.add( mem.get( j+1 ) + off ) ;
                    cnt ++ ;
                }
                else {
                    cLen = s.length ;
                    p = mem.get( j+1 ) - ( bLen - 1 ) ;
                    while( ( p = s.indexOf( beforeIndexOf,p ) ) != -1 ) {
                        if( cLen == p + bLen + off ) {
                            tmp.add( mem.get( j ) ) ;
                            tmp.add( p + bLen + off ) ;
                            cnt ++ ;
                            break ;
                        }
                        p ++ ;
                    }
                }
            }
        }
        mem = tmp ;
        length = cnt ;
    }
}

