//start of TwoLevelHashSearch.java
//TEXT_STYLE:CODE=Shift_JIS(Japanese):RET_CODE=CRLF

/**
 * TwoLevelHashSearch.java
 * 
 * Copyright (C) 2002  Michel Ishizuka  All rights reserved.
 * 
 * ȉ̏ɓӂȂ΃\[XƃoCi`̍ĔzzƎgp
 * ύX̗Lɂ炸‚B
 * 
 * PD\[XR[h̍ĔzzɂĒ쌠\ ̏̃Xg
 *     щL̐ێȂĂ͂ȂȂB
 * 
 * QDoCi`̍ĔzzɂĒ쌠\ ̏̃Xg
 *     щL̐gp ̑̔zz
 *     ܂ގɋLqȂ΂ȂȂB
 * 
 * ̃\tgEFA͐Β˔ڂɂĖۏ؂Œ񋟂A̖
 * IBłƂۏ؁AilLƂۏ؂ɂƂǂ܂炸A
 * Ȃ閾IшÎIȕۏ؂ȂB
 * Β˔ڂ ̃\tgEFA̎gpɂ钼ړIAԐړIA
 * IAȁAT^IȁA邢͕KRIȑQ(gpɂf[^
 * AƖ̒f〈܂Ăv̈⎸A֐i
 * T[rX̓l邪AĂꂾɌ肳Ȃ
 * Q)ɑ΂āAȂ鎖Ԃ̌ƂȂƂĂA_̐
 * C△ߎӔC܂ ȂӔC낤ƂAƂꂪs
 * ŝׂ߂łƂĂA܂͂̂悤ȑQ̉”\
 * ĂƂĂ؂̐ӔC𕉂Ȃ̂ƂB
 */

package jp.gr.java_conf.dangan.util.lha;

//import classes and interfaces
import jp.gr.java_conf.dangan.io.Bits;
import jp.gr.java_conf.dangan.lang.reflect.Factory;
import jp.gr.java_conf.dangan.util.lha.HashShort;
import jp.gr.java_conf.dangan.util.lha.HashMethod;
import jp.gr.java_conf.dangan.util.lha.LzssOutputStream;
import jp.gr.java_conf.dangan.util.lha.LzssSearchMethod;

//import exceptions
import java.io.IOException;
import java.lang.NoSuchMethodException;
import java.lang.ClassNotFoundException;
import java.lang.InstantiationException;
import java.lang.reflect.InvocationTargetException;

import java.lang.Error;
import java.lang.NoSuchMethodError;
import java.lang.InstantiationError;
import java.lang.NoClassDefFoundError;


/**
 * iKnbVƒPAXggčꂽ LzssSearchMethodB<br>
 * <a href="http://search.ieice.org/2000/pdf/e83-a_12_2689.pdf">茓̘_</a>
 * QlɂB
 * 
 * <pre>
 * -- revision history --
 * $Log: TwoLevelHashSearch.java,v $
 * Revision 1.1  2002/12/10 22:06:40  dangan
 * [bug fix]
 *     searchAndPut() ōŋ߂̍ŒvȂoOCB
 *
 * Revision 1.0  2002/12/03 00:00:00  dangan
 * first edition
 * add to version control
 *
 * </pre>
 * 
 * @author  $Author: dangan $
 * @version $Revision: 1.1 $
 */
public class TwoLevelHashSearch implements LzssSearchMethod{


    //------------------------------------------------------------------
    //  instance field
    //------------------------------------------------------------------
    //  LZSS parameter
    //------------------------------------------------------------------
    //  private int DictionarySize
    //  private int MaxMatch
    //  private int Threshold
    //------------------------------------------------------------------
    /**
     * LZSSTCYB
     */
    private int DictionarySize;

    /**
     * LZSSkɎgplB
     * ővB
     */
    private int MaxMatch;

    /**
     * LZSSkɎgp臒lB
     * v ̒lȏł΁AkR[ho͂B
     */
    private int Threshold;


    //------------------------------------------------------------------
    //  instance field
    //------------------------------------------------------------------
    //  text buffer
    //------------------------------------------------------------------
    //  private byte[] TextBuffer
    //  private int DictionaryLimit
    //------------------------------------------------------------------
    /**
     * LZSSk{߂̃obt@B
     * Ö͎A
     * 㔼͈k{߂̃f[^̓obt@B
     * LzssSearchMethod̎ł͓ǂݍ݂̂݋B
     */
    private byte[] TextBuffer;

    /**
     * ̌EʒuB 
     * TextBufferO̎̈Ƀf[^ꍇ
     * ̈ɂs̃f[^(Javał0)gp
     * Ĉkŝ}~B
     */
    private int DictionaryLimit;


    //------------------------------------------------------------------
    //  instance field
    //------------------------------------------------------------------
    //  primary hash
    //------------------------------------------------------------------
    //  private HashMethod primaryHash
    //  private int[] primaryHashTable
    //  private int[] primaryCount
    //------------------------------------------------------------------
    /**
     * iڂ̃nbV֐
     */
    private HashMethod primaryHash;

    /**
     * iڂ̃nbVe[u
     * Y͈iڂ̃nbVlAe iڂ̃nbVe[u index
     */
    private int[] primaryHashTable;

    /**
     * iڂ̃nbVe[uɊ‚̃f[^p^
     * o^Ă邩JEgĂB
     */
    private int[] primaryCount;


    //------------------------------------------------------------------
    //  instance field
    //------------------------------------------------------------------
    //  secondary hash
    //------------------------------------------------------------------
    //  private int[] secondaryHashRequires
    //  private int[] secondaryHashTable
    //  private int[] dummy
    //------------------------------------------------------------------
    /**
     * iڂ̃nbVlZo邽߂ɕKvȃoCgB
     */
    private int[] secondaryHashRequires;

    /**
     * iڂ̃nbVe[u
     * Y iڂ̃nbVe[u̒l + iڂ̃nbVlA
     * e TextBuffer ̃f[^p^̊Jnʒu
     */
    private int[] secondaryHashTable;

    /**
     * slide() ̖ secondaryHashTable Ɠւ_~[zB
     * g܂킵pB
     */
    private int[] dummy;


    //------------------------------------------------------------------
    //  instance field
    //------------------------------------------------------------------
    //  cahined list
    //------------------------------------------------------------------
    //  private int[] prev
    //------------------------------------------------------------------
    /**
     * nbVlƒf[^p^Jnʒu
     * PAXgB
     */
    private int[] prev;


    //------------------------------------------------------------------
    //  constructor
    //------------------------------------------------------------------
    //  private TwoLevelHashSearch()
    //  public TwoLevelHashSearch( int DictionarySize, int MaxMatch, 
    //                             int Threshold, byte[] TextBuffer )
    //  public TwoLevelHashSearch( int DictionarySize, int MaxMatch, 
    //                             int Threshold, byte[] TextBuffer,
    //                             String HashMethodClassName )
    //------------------------------------------------------------------
    /**
     * ftHgRXgN^B
     * gpsB
     */
    private TwoLevelHashSearch(){ }

    /**
     * iKnbVgp LzssSearchMethod \zB<br>
     * iڂ̃nbV֐ɂ ftHĝ̂gpB<br>
     * 
     * @param DictionarySize      TCY
     * @param MaxMatch            őv
     * @param Threshold           kA񈳏k臒l
     * @param TextBuffer          LZSSk{߂̃obt@
     */
    public TwoLevelHashSearch( int    DictionarySize,
                               int    MaxMatch,
                               int    Threshold,
                               byte[] TextBuffer ){
        this( DictionarySize,
              MaxMatch,
              Threshold,
              TextBuffer,
              HashShort.class.getName() );
    }


    /**
     * iKnbVgp LzssSearchMethod \zB
     * 
     * @param DictionarySize      TCY
     * @param MaxMatch            őv
     * @param Threshold           kA񈳏k臒l
     * @param TextBuffer          LZSSk{߂̃obt@
     * @param HashMethodClassName Hash֐񋟂NX
     * 
     * @exception NoClassDefFoundError
     *              HashMethodClassName ŗ^ꂽNX‚ȂꍇB
     * @exception InstantiationError
     *              HashMethodClassName ŗ^ꂽNX
     *              abstract class ł邽߃CX^X𐶐łȂꍇB
     * @exception NoSuchMethodError
     *              HashMethodClassName ŗ^ꂽNX
     *              RXgN^ HashMethod( byte[] )ȂꍇB
     */
    public TwoLevelHashSearch( int    DictionarySize,
                               int    MaxMatch,
                               int    Threshold,
                               byte[] TextBuffer,
                               String HashMethodClassName ){

        this.DictionarySize   = DictionarySize;
        this.MaxMatch         = MaxMatch;
        this.Threshold        = Threshold;
        this.TextBuffer       = TextBuffer;
        this.DictionaryLimit  = this.DictionarySize;

        try{
            this.primaryHash = (HashMethod)Factory.createInstance(
                                                HashMethodClassName, 
                                                new Object[]{ TextBuffer } );
        }catch( ClassNotFoundException exception ){
            throw new NoClassDefFoundError( exception.getMessage() );
        }catch( InvocationTargetException exception ){
            throw new Error( exception.getTargetException().getMessage() );
        }catch( NoSuchMethodException exception ){
            throw new NoSuchMethodError( exception.getMessage() );
        }catch( InstantiationException exception ){
            throw new InstantiationError( exception.getMessage() );
        }

        // nbVe[u
        this.primaryHashTable   = new int[ this.primaryHash.tableSize() ];
        this.secondaryHashTable = new int[ ( this.primaryHash.tableSize() 
                                           + this.DictionarySize / 4 ) ];
        for( int i = 0 ; i < this.primaryHashTable.length ; i++ ){
            this.primaryHashTable[i]   = i;
            this.secondaryHashTable[i] = -1;
        }

        // ̑̔z񐶐 
        // primaryCount  secondaryHashRequires ͔z񐶐Ƀ[NAĂ鎖𗘗pB
        this.primaryCount          = new int[ this.primaryHash.tableSize() ];
        this.secondaryHashRequires = new int[ this.primaryHash.tableSize() ];
        this.dummy                 = new int[ this.secondaryHashTable.length ];

        // AXg
        this.prev = new int[ this.DictionarySize ];
        for( int i = 0 ; i < this.prev.length ; i++ ){
            this.prev[i] = -1;
        }
    }


    //------------------------------------------------------------------
    //  method of jp.gr.java_conf.dangan.util.lha.LzssSearchMethod
    //------------------------------------------------------------------
    //  public void put( int position )
    //  public int searchAndPut( int position )
    //  public int search( int position, int lastPutPos )
    //  public void slide( int slideWidth, int slideEnd )
    //  public int putRequires()
    //------------------------------------------------------------------
    /**
     * position n܂f[^p^
     * iKnbVƘAXg琬錟@\ɓo^B<br>
     * 
     * @param position TextBuffer̃f[^p^̊Jnʒu
     */
    public void put( int position ){
        int phash = this.primaryHash.hash( position );
        int base  = this.primaryHashTable[ phash ];
        int shash = this.secondaryHash( position, this.secondaryHashRequires[ phash ] );

        this.primaryCount[ phash ]++;
        this.prev[ position & ( this.DictionarySize - 1 ) ] = 
                                        this.secondaryHashTable[ base + shash ];
        this.secondaryHashTable[ base + shash ] = position;
    }

    /**
     * iKnbVƘAXg琬錟@\ɓo^ꂽ
     * f[^p^ position n܂f[^p^
     * Œ̈v‚̂A
     *  position n܂f[^p^ 
     * iKnbVƘAXg琬錟@\ɓo^B<br>
     * 
     * @param position TextBuffer̃f[^p^̊JnʒuB
     * 
     * @return v‚ꍇ
     *         LzssOutputStream.createSearchReturn 
     *         ɂĐꂽvʒuƈv̏’lA
     *         v‚Ȃꍇ
     *         LzssOutputStream.NOMATCHB
     * 
     * @see LzssOutputStream#createSearchReturn(int,int)
     * @see LzssOutputStream#NOMATCH
     */
    public int searchAndPut( int position ){
        int matchlen  = this.Threshold - 1;
        int matchpos  = position;
        int scanlimit = Math.max( this.DictionaryLimit,
                                  position - this.DictionarySize );


        int phash    = this.primaryHash.hash( position );
        int base     = this.primaryHashTable[ phash ];
        int requires = this.secondaryHashRequires[ phash ];
        int shash    = this.secondaryHash( position, requires );
        int scanpos  = this.secondaryHashTable[ base + shash ];

        byte[] buf   = this.TextBuffer;
        int max      = position + this.MaxMatch;
        int s        = 0;
        int p        = 0;
        int len      = 0;

        //------------------------------------------------------------------
        //  iڂ̃nbVɂđI΂ꂽAXg郋[v
        while( scanlimit <= scanpos ){
            if( buf[ scanpos + matchlen ] == buf[ position + matchlen ] ){
                s = scanpos;
                p = position;
                while( buf[s] == buf[p] ){
                    s++;
                    p++;
                    if( max <= p ) break;
                }

                len = p - position;
                if( matchlen < len ){
                    matchpos = scanpos;
                    matchlen = len;
                    if( max <= p ) break;
                }
            }
            scanpos = this.prev[ scanpos & ( this.DictionarySize - 1 ) ];
        }

        //------------------------------------------------------------------
        //  iڂ̃nbVɂČIꂽAXgɈvꍇA
        //  iڂ̃nbVɓo^ĂSĂ̘AXg
        int revbits  = 1;
        int loopend  = requires - Math.max( 0, this.Threshold - this.primaryHash.hashRequires() );
        int maxmatch = this.primaryHash.hashRequires() + requires - 1;
        for( int i = 1, send = 4 ; i <= loopend && matchlen <= maxmatch ; i++, send <<= 2 ){
            max += position + maxmatch;
            while( revbits < send ){
                scanpos  = this.secondaryHashTable[ base + ( shash ^ revbits ) ];
                while( scanlimit <= scanpos ){
                    if( buf[ scanpos ] == buf[ position ] ){
                        s = scanpos + 1;
                        p = position + 1;
                        while( buf[s] == buf[p] ){
                            s++;
                            p++;
                            if( max <= p ) break;
                        }

                        len = p - position;
                        if( matchlen < len
                         || ( matchlen == len && matchpos < scanpos ) ){
                            matchpos = scanpos;
                            matchlen = len;
                            if( max <= p ){
                                scanlimit = scanpos;
                                break;
                            }
                        }
                    }
                    scanpos = this.prev[ scanpos & ( this.DictionarySize - 1 ) ];
                }
                revbits++;
            }
            maxmatch = this.primaryHash.hashRequires() + requires - i - 1;
        }
        
        //------------------------------------------------------------------
        //  iKnbVƘAXggp@\
        //  position n܂f[^p^o^B
        this.primaryCount[ phash ]++;
        this.prev[ position & ( this.DictionarySize - 1 ) ] = 
                                        this.secondaryHashTable[ base + shash ];
        this.secondaryHashTable[ base + shash ] = position;

        //------------------------------------------------------------------
        //  ŒvĂяoɕԂB
        if( this.Threshold <= matchlen ){
            return LzssOutputStream.createSearchReturn( matchlen, matchpos );
        }else{
            return LzssOutputStream.NOMATCH;
        }
    }

    /**
     * nbVƘAXggp@\ɓo^ꂽ
     * f[^p^ position n܂f[^p^
     * Œ̈v‚̂𓾂B<br>
     * 
     * @param position   TextBuffer̃f[^p^̊JnʒuB
     * @param lastPutPos Ōɓo^f[^p^̊JnʒuB
     * 
     * @return v‚ꍇ
     *         LzssOutputStream.createSearchReturn 
     *         ɂĐꂽvʒuƈv̏’lA
     *         v‚Ȃꍇ
     *         LzssOutputStream.NOMATCHB
     * 
     * @see LzssOutputStream#createSearchReturn(int,int)
     * @see LzssOutputStream#NOMATCH
     */
    public int search( int position, int lastPutPos ){

        //------------------------------------------------------------------
        //  nbVƘAXgɂ錟@\ɓo^ĂȂ
        //  f[^p^PȒŌB
        int matchlen   = this.Threshold - 1;
        int matchpos   = position;
        int scanpos    = position - 1;
        int scanlimit  = Math.max( this.DictionaryLimit, lastPutPos );

        byte[] buf     = this.TextBuffer;
        int max        = Math.min( this.TextBuffer.length,
                                   position + this.MaxMatch );
        int s          = 0;
        int p          = 0;
        int len        = 0;
        while( scanlimit < scanpos ){
            s = scanpos;
            p = position;
            while( buf[ s ] == buf[ p ] ){
                s++;
                p++;
                if( max <= p ) break;
            }

            if( matchlen < len ){
                matchpos = scanpos;
                matchlen = len;
            }
            scanpos--;
        }

        //------------------------------------------------------------------
        //  iKnbVƘAXggp@\猟B
        int phashRequires = this.primaryHash.hashRequires();
        if( phashRequires < this.TextBuffer.length - position ){

            int phash    = this.primaryHash.hash( position );
            int base     = this.primaryHashTable[ phash ];
            int requires = this.secondaryHashRequires[ phash ];
            int shash;
            int start;
            if( phashRequires + requires < this.TextBuffer.length - position ){
                shash   = this.secondaryHash( position, requires );
                start   = 0;
            }else{
                int avail = this.TextBuffer.length - position - phashRequires;
                shash   = this.secondaryHash( position, avail ) << ( ( requires - avail ) * 2 );
                start   = requires - avail;
            }
            int revbits = 0;
            int loopend  = requires - Math.max( 0, this.Threshold - this.primaryHash.hashRequires() );
            int maxmatch = this.MaxMatch;

            //------------------------------------------------------------------
            //  iڂ̂ɓo^ĂAXgDx̏Ɍ郋[v
            for( int i = start, send = ( 1 << ( i * 2 ) ) ; i <= requires ; i++, send <<= 2 ){
                max += position + maxmatch;
                while( revbits < send ){
                    scanpos  = this.secondaryHashTable[ base + ( shash ^ revbits ) ];
                    while( scanlimit <= scanpos ){
                        if( buf[ scanpos ] == buf[ position ] ){
                            s = scanpos + 1;
                            p = position + 1;
                            while( buf[s] == buf[p] ){
                                s++;
                                p++;
                                if( max <= p ) break;
                            }

                            len = p - position;
                            if( matchlen < len
                             || ( matchlen == len && matchpos < scanpos ) ){
                                matchpos = scanpos;
                                matchlen = len;
                                if( max <= p ){
                                    scanlimit = scanpos;
                                    break;
                                }
                            }
                        }
                        scanpos = this.prev[ scanpos & ( this.DictionarySize - 1 ) ];
                    }
                    revbits++;
                }
                maxmatch = this.primaryHash.hashRequires() + requires - i - 1;
            }
        }// if( phashRequires < this.TextBuffer.length - position )

        //------------------------------------------------------------------
        //  ŒvĂяoɕԂB
        if( this.Threshold <= matchlen ){
            return LzssOutputStream.createSearchReturn( matchlen, matchpos );
        }else{
            return LzssOutputStream.NOMATCH;
        }

    }

    /**
     * TextBufferposition܂ł̃f[^
     * OֈړہAɉ SearchMethod
     * f[^ TextBuffer̃f[^ƖȂ悤
     * Oֈړ鏈sB
     */
    public void slide(){

        //------------------------------------------------------------------
        //  DictionaryLimitXV
        this.DictionaryLimit = Math.max( 0, this.DictionaryLimit - this.DictionarySize );

        //------------------------------------------------------------------
        //  primaryCount ̒lɂ secondaryHashTable č\
        int secondaryIndex = 0;
        int dummyIndex     = 0;
        for( int i = 0 ; i < this.primaryHashTable.length ; i++ ){
            this.primaryHashTable[i] = dummyIndex;
            int bits = this.secondaryHashRequires[i] * 2;

            if( 1 << ( 5 + bits ) <= this.primaryCount[i] ){
                for( int j = 0 ; j < ( 1 << bits ) ; j++ ){
                    this.divide( dummyIndex, secondaryIndex, this.primaryHash.hashRequires() + this.secondaryHashRequires[i] );
                    dummyIndex     += 4;
                    secondaryIndex += 1;
                }
                this.secondaryHashRequires[i]++;

            }else if( 0 < bits && this.primaryCount[i] < ( 1 << ( 2 + bits ) ) ){
                for( int j = 0 ; j < ( 1 << ( bits - 2 ) ) ; j++ ){
                    this.merge( dummyIndex, secondaryIndex );
                    dummyIndex     += 1;
                    secondaryIndex += 4;
                }
                this.secondaryHashRequires[i]--;

            }else{
                for( int j = 0 ; j < ( 1 << bits ) ; j++ ){
                    int pos = this.secondaryHashTable[ secondaryIndex++ ] - this.DictionarySize;
                    this.dummy[ dummyIndex++ ] = ( 0 <= pos ? pos : -1 );
                }
            }
            this.primaryCount[i] = 0;
        }
        int[] temp = this.secondaryHashTable;
        this.secondaryHashTable = this.dummy;
        this.dummy = temp;

        //------------------------------------------------------------------
        //  AXgXV
        for( int i = 0 ; i < this.prev.length ; i++  ){
            int pos =  this.prev[i] - this.DictionarySize;
            this.prev[i] = ( 0 <= pos ? pos : -1 );
        }
    }

    /**
     * put()  LzssSearchMethodɃf[^
     * o^ƂɎgpf[^ʂ𓾂B
     * TwoLevelHashSearch ł́AŎgpĂ HashMethod ̎ 
     * hash() ̂߂ɕKvƂf[^( HashMethod.hashRequires() ̖߂l ) 
     *  iڂ̃nbVɕKvȍő̃oCg𑫂̂ԂB
     * 
     * @return iڂƓiڂ̃nbVɕKvȃoCg𑫂́B
     */
    public int putRequires(){
        return this.primaryHash.hashRequires() 
               + Math.max( Bits.len( this.DictionarySize ) - 5, 0 ) / 2;
    }


    //------------------------------------------------------------------
    //  local method
    //------------------------------------------------------------------
    //  secondary hash method
    //------------------------------------------------------------------
    //  private int secondaryHash( int position, int hashRequires )
    //------------------------------------------------------------------
    /**
     * iڂ̃nbV֐
     * 
     * @param position     TextBuffer̃f[^p^̊Jnʒu
     * @param hashRequires iڂ̃nbVlZôɕKvȃoCg
     */
    private int secondaryHash( int position, int hashRequires ){
        int hash = 0;
        int pos  = position + this.primaryHash.hashRequires();

        while( 0 < hashRequires-- ){
            hash <<= 2;
            hash  |= this.TextBuffer[ pos++ ] & 0x03;
        }

        return hash;
    }


    //------------------------------------------------------------------
    //  local method
    //------------------------------------------------------------------
    //  divide and merge chained list
    //------------------------------------------------------------------
    //  private void divide( int dbase, int sbase, int divoff )
    //  private void merge( int dbase, int sbase )
    //------------------------------------------------------------------
    /**
     * iڂ̃nbVe[uƘAXg𕪊򂳂B
     * 
     * @param dbase   this.dummy  index
     * @param sbase   this.secondaryHashTable  index
     * @param divoff ʒu 
     */
    private void divide( int dbase, int sbase, int divoff ){
        int limit     = this.DictionarySize;
        int position  = this.secondaryHashTable[ sbase ];
        int[] current = { -1, -1, -1, -1 };
        
        //------------------------------------------------------------------
        //  AXg𕪊򂳂Ă[v
        while( limit < position ){
            int shash = this.TextBuffer[ position + divoff ] & 0x03;
            if( 0 < current[ shash ] ){
                this.prev[ current[ shash ] & ( this.DictionarySize - 1 ) ] = position;
            }else{
                this.dummy[ dbase + shash ] = position - this.DictionarySize; 
            }
            current[ shash ] = position;
            position = this.prev[ position & ( this.DictionarySize - 1 ) ];
        }

        //------------------------------------------------------------------
        //  AXg^[~l[gB
        for( int i = 0 ; i < current.length ; i++ ){
            if( 0 < current[ i ] ){
                this.prev[ current[ i ] & ( this.DictionarySize - 1 ) ] = -1;
            }else{
                this.dummy[ dbase + i ] = -1; 
            }
        }
    }

    /**
     * iڂ̃nbVe[uƘAXg𑩂˂B
     * 
     * @param dbase   this.dummy  index
     * @param sbase   this.secondaryHashTable  index
     */
    private void merge( int dbase, int sbase ){
        int limit    = this.DictionarySize;
        int position = -1;

        //------------------------------------------------------------------
        //  AXg𑩂˂Ă[v
        while( true ){
            int shash = 0;
            int max   = this.secondaryHashTable[ sbase ];
            for( int i = 1 ; i < 4 ; i++ ){
                if( max < this.secondaryHashTable[ sbase + i ] ){
                    shash = i;
                    max   = this.secondaryHashTable[ sbase + i ];
                }
            }
            
            if( limit < max ){
                this.secondaryHashTable[ sbase + shash ] = 
                                 this.prev[ max & ( this.DictionarySize - 1 ) ];

                if( 0 < position ){
                    this.prev[ position & ( this.DictionarySize - 1 ) ] = max;
                }else{
                    this.dummy[ dbase ]  = max - this.DictionarySize;
                }
                position = max;
            }else{
                break;
            }
        }

        //------------------------------------------------------------------
        //  AXg^[~l[gB
        if( 0 < position ){
            this.prev[ position & ( this.DictionarySize - 1 ) ] = -1;
        }else{
            this.dummy[ dbase ] = -1;
        }
    }

}
//end of TwoLevelHashSearch.java