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

/**
 * SimpleSearch.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.util.lha.LzssSearchMethod;
import jp.gr.java_conf.dangan.util.lha.LzssOutputStream;

//import exceptions

/**
 * ʂȌ@\pȂ 
 * LzssSearchMethod ̍łVvȎB<br>
 * @\pȂ߁A
 * ̌@\pƔׂƒxA
 * ʂɏȂB<br>
 * 
 * <pre>
 * -- revision history --
 * $Log: SimpleSearch.java,v $
 * Revision 1.0  2002/08/05 00:00:00  dangan
 * add to version control
 * [change]
 *     LzssSearchMethod ̃C^tFCXύXɂ킹ăC^tFCXύXB
 * [maintenance]
 *     \[X
 *     ^up~
 *     CZX̏C
 *
 * </pre>
 * 
 * @author  $Author: dangan $
 * @version $Revision: 1.0 $
 */
public class SimpleSearch 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
     * position  Ö͎A
     * 㔼͈k{߂̃f[^̓obt@B
     * LzssSearchMethod̎ł͓ǂݍ݂̂݋B
     */
    private byte[] TextBuffer;

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


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

    /**
     * ʂȌ@\pȂVv
     * LzssSearchMethod \zB<br>
     * 
     * @param DictionarySize  TCY
     * @param MaxMatch        őv
     * @param Threshold       kA񈳏k臒l
     * @param TextBuffer      LZSSk{߂̃obt@
     */
    public SimpleSearch( int    DictionarySize,
                         int    MaxMatch,
                         int    Threshold,
                         byte[] TextBuffer ){

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


    //------------------------------------------------------------------
    // 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, int maxMatch )
    //  public void slide()
    //  public int putRequires()
    //------------------------------------------------------------------
    /**
     * SimpleSearch ͌@\gpȂ
     * ̃\bh͉ȂB
     * 
     * @param position TextBuffer̃f[^p^̊Jnʒu
     */
    public void put( int position ){    }

    /**
     * TextBuffer ̎̈ɂf[^p^
     * position n܂f[^p^
     * Œ̈v‚̂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 scanpos    = position - 1;

        byte[] buf     = this.TextBuffer;
        int max        = position + this.MaxMatch;
        int p          = 0;
        int s          = 0;
        int len        = 0;
        while( scanlimit < scanpos ){
            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( this.MaxMatch == len ) break;
            }
            scanpos--;
        }

        if( this.Threshold <= matchlen ){
            return LzssOutputStream.createSearchReturn( matchlen, matchpos );
        }else{
            return LzssOutputStream.NOMATCH;
        }
    }

    /**
     * TextBuffer ̎̈ɂ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 ){
        int matchlen   = this.Threshold - 1;
        int matchpos   = position;
        int scanlimit  = Math.max( this.DictionaryLimit,
                                   position - this.DictionarySize );
        int scanpos    = position - 1;

        byte[] buf     = this.TextBuffer;
        int max        = Math.min( position + this.MaxMatch, 
                                   this.TextBuffer.length );
        int p          = 0;
        int s          = 0;
        int len        = 0;
        while( scanlimit < scanpos ){
            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( this.MaxMatch == len ) break;
            }
            scanpos--;
        }

        if( this.Threshold <= matchlen ){
            return LzssOutputStream.createSearchReturn( matchlen, matchpos );
        }else{
            return LzssOutputStream.NOMATCH;
        }
    }

    /**
     * LzssOutputStream  slide() TextBuffer̃f[^
     * DictionarySize ړۂɌ@\̃f[^
     * Ɩړ鏈sB
     */
    public void slide(){
        this.DictionaryLimit = Math.max( 0, this.DictionaryLimit - this.DictionarySize );
    }

    /**
     * SimpleSearch ͌@\gpȂߏ 0 ԂB
     * 
     * @return  0
     */
    public int putRequires(){
        return 0;
    }

}
//end of SimpleSearch.java