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

/**
 * HashAndBinaryTreeSearch.java
 * 
 * Copyright (C) 2002  Michel Ishizuka  All rights reserved.
 * 
 * ȉ̏ɓӂȂ΃\[XƃoCi`̍ĔzzƎgp
 * ύX̗Lɂ炸‚B
 * 
 * ȉ̏ɓӂȂ΃\[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.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;

/**
 * nbVƓ񕪖؂g LzssSearchMethod ̎B<br>
 * <pre>
 * f[^knhubN[]
 *        M.l\/J.-L.QB[ 
 *                uERp 
 *                  ISBN4-8101-8605-9
 *                             5728~(Ŕ,̍w̉i)
 * </pre>
 * QlɂB<br>
 * 񕪖؂ł́AŒv‚邱Ƃ͂ł邪A
 * ł߂v‚Ƃ͌Ȃ߁A
 * LZSS vʒu߂ꏊɕ΂鎖
 * p悤 -lh5- ̂悤Ȉk@ł́A
 * k͂炩ቺB
 * 
 * <pre>
 * -- revision history --
 * $Log: HashAndBinaryTreeSearch.java,v $
 * Revision 1.0  2002/08/05 00:00:00  dangan
 * add to version control
 * [change]
 *     LzssSearchMethod ̃C^tFCXύXɂ킹ăC^tFCXύX
 * [maintenance]
 *     \[X
 *     ^up~
 *     CZX̏C
 *
 * </pre>
 * 
 * @author  $Author: dangan $
 * @version $Revision: 1.0 $
 */
public class HashAndBinaryTreeSearch implements LzssSearchMethod{


    //------------------------------------------------------------------
    //  class field
    //------------------------------------------------------------------
    //  private static final int UNUSED
    //  private static final int ROOT_NODE
    //------------------------------------------------------------------
    /**
     * gpĂȂlB
     * parent[node]  UNUSED ꍇ node ͖gpnodełB
     * small[node], large[node]  UNUSED ꍇ
     * node 瑤̎qm[hȂB
     */
    private static final int UNUSED = -1;

    /**
     * 񕪖؂̍lB
     * parent[node]  ROOT_NODE ꍇ node ͓񕪖؂̍łB
     */
    private static final int ROOT_NODE = -2;


    //------------------------------------------------------------------
    //  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
    //------------------------------------------------------------------
    //  hash
    //------------------------------------------------------------------
    //  private HashMethod hashMethod
    //  private int[] hashTable
    //------------------------------------------------------------------
    /**
     * nbV֐
     */
    private HashMethod hashMethod;

    /**
     * nbVe[u
     * Y̓nbVlAe͌X̃nbVl
     * 񕪖؂̍̃f[^p^̊JnʒuB
     */
    private int[] hashTable;


    //------------------------------------------------------------------
    //  instance field
    //------------------------------------------------------------------
    //  binary tree
    //------------------------------------------------------------------
    //  private int[] parent
    //  private int[] small
    //  private int[] large
    //  private int[] dummy
    //------------------------------------------------------------------
    /**
     * ẽf[^p^̊JnʒuB
     * Y̓m[hԍAe͐em[h̃f[^p^̊Jnʒu
     */
    private int[] parent;

    /**
     * q̃f[^p^̊JnʒuB
     * Y̓m[hԍAe͏qm[hf[^p^̊Jnʒu
     */
    private int[] small;

    /**
     * 傫q̃f[^p^̊JnʒuB
     * Y̓m[hԍAe͑傫qm[hf[^p^̊Jnʒu
     */
    private int[] large;

    /**
     * slide p̃obt@
     */
    private int[] dummy;


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

    /**
     * nbVƓ񕪖؂gp@\\zB<br>
     * nbV֐̓ftHĝ̂gpB
     * 
     * @param DictionarySize      TCY
     * @param MaxMatch            Œv
     * @param Threshold           kA񈳏k臒l
     * @param TextBuffer          LZSSk{߂̃obt@
     */
    public HashAndBinaryTreeSearch( int    DictionarySize,
                                    int    MaxMatch,
                                    int    Threshold,
                                    byte[] TextBuffer ){

        this( DictionarySize,
              MaxMatch,
              Threshold,
              TextBuffer,
              HashShort.class.getName() );
    }

    /**
     * nbVƓ񕪖؂gp 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[] )
     *              Ȃꍇ
     */
    public HashAndBinaryTreeSearch( 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.hashMethod = (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[ȕ
        this.hashTable = new int[ this.hashMethod.tableSize() ];
        for( int i = 0 ; i < this.hashTable.length ; i++ ){
            this.hashTable[i] = HashAndBinaryTreeSearch.UNUSED;
        }

        //  񕪖؂̏
        this.parent = new int[ DictionarySize ];
        this.large  = new int[ DictionarySize ];
        this.small  = new int[ DictionarySize ];
        for( int i = 0 ; i < this.parent.length ; i++ ){
            this.parent[i] = HashAndBinaryTreeSearch.UNUSED;
        }
    }


    //------------------------------------------------------------------
    //  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^
     * nbVƓ񕪖؂gp@\ɓo^B<br>
     * 
     * @param position TextBuffer̃f[^p^̊Jnʒu
     */
    public void put( int position ){

        //------------------------------------------------------------------
        //  񕪖؂łÂf[^p^폜
        this.deleteNode( position - this.DictionarySize );

        //------------------------------------------------------------------
        //  񕪖؂ position }ʒu
        int hash       = this.hashMethod.hash( position );
        int parentpos  = this.hashTable[ hash ];
        int scanpos    = this.hashTable[ hash ];

        byte[] buf     = this.TextBuffer;
        int max        = position + this.MaxMatch;
        int p          = 0;
        int s          = 0;
        while( scanpos != HashAndBinaryTreeSearch.UNUSED ){

            s = scanpos;
            p = position;
            while( buf[ s ] == buf[ p ] ){
                s++;
                p++;
                if( max <= p ){
                    //Sv𔭌
                    this.replaceNode( scanpos, position );
                    return;
                }
            }

            parentpos = scanpos;
            scanpos = ( buf[ s ] < buf[ p ] 
                      ? this.large[ scanpos & ( this.DictionarySize - 1 ) ]
                      : this.small[ scanpos & ( this.DictionarySize - 1 ) ] );
        }

        //------------------------------------------------------------------
        //  position n܂f[^p^ 񕪖؂ɓo^
        if( this.hashTable[ hash ] != HashAndBinaryTreeSearch.UNUSED ){
            this.addNode( parentpos, position, p - position );
        }else{
            this.hashTable[ hash ] = position;
            int node = position & ( this.DictionarySize - 1 );
            this.parent[ node ] = HashAndBinaryTreeSearch.ROOT_NODE;
            this.small[ node ]  = HashAndBinaryTreeSearch.UNUSED;
            this.large[ node ]  = HashAndBinaryTreeSearch.UNUSED;
        }
    }

    /**
     * nbVƓ񕪖؂gp@\ɓo^ꂽ
     * f[^p^ position n܂f[^p^
     * Œ̈v‚̂A
     *  position n܂f[^p^ 
     * nbVƓ񕪖؂gp@\ɓ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 ){

        //------------------------------------------------------------------
        //  񕪖؂łÂf[^p^폜
        this.deleteNode( position - this.DictionarySize );

        //------------------------------------------------------------------
        //  񕪖؂Œv
        int hash       = this.hashMethod.hash( position );
        int matchlen   = -1;
        int matchpos   = this.hashTable[ hash ];
        int parentpos  = this.hashTable[ hash ];
        int scanpos    = this.hashTable[ hash ];

        byte[] buf     = this.TextBuffer;
        int max        = position + this.MaxMatch;
        int p          = 0;
        int s          = 0;
        int len        = 0;
        while( scanpos != HashAndBinaryTreeSearch.UNUSED ){
            s = scanpos;
            p = position;
            while( buf[ s ] == buf[ p ] ){
                s++;
                p++;
                if( max <= p ){
                    //Sv𔭌
                    this.replaceNode( matchpos, position );
                    return LzssOutputStream.createSearchReturn( matchlen, matchpos );
                }
            }

            len = p - position;
            if( matchlen < len ){
                matchpos = scanpos;
                matchlen = len;
            }else if( matchlen == len && matchpos < scanpos ){
                matchpos = scanpos;
            }

            parentpos = scanpos;
            scanpos = ( buf[ s ] < buf[ p ]
                      ? this.large[ scanpos & ( this.DictionarySize - 1 ) ]
                      : this.small[ scanpos & ( this.DictionarySize - 1 ) ] );
        }

        //------------------------------------------------------------------
        //  position n܂f[^p^ 񕪖؂ɓo^
        if( this.hashTable[ hash ] != HashAndBinaryTreeSearch.UNUSED ){
            this.addNode( parentpos, position, len );
        }else{
            this.hashTable[ hash ] = position;
            int node               = position & ( this.DictionarySize - 1 );
            this.parent[ node ]    = HashAndBinaryTreeSearch.ROOT_NODE;
            this.small[ node ]     = HashAndBinaryTreeSearch.UNUSED;
            this.large[ node ]     = HashAndBinaryTreeSearch.UNUSED;
        }

        //------------------------------------------------------------------
        //  \bh̐擪ō폜ꂽ
        //  łf[^p^Ɣr
        scanpos  = position - this.DictionarySize;
        if( this.DictionaryLimit <= scanpos ){
            len = 0;
            while( this.TextBuffer[ scanpos  + len ]
                == this.TextBuffer[ position + len ] ){
                if( this.MaxMatch <= ++len ) break;
            }

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

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

    /**
     * nbVƓ񕪖؂gp@\ɓo^ꂽf[^p^
     * position n܂f[^p^ƍŒ̈v‚̂𓾂B<br>
     * TextBuffer.length &lt position + MaxMatch ƂȂ悤 position ł́A
     * 񕪖؂SɑȂߍŒ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 ){

        //------------------------------------------------------------------
        //  񕪖؂ɓ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--;
        }

        //------------------------------------------------------------------
        //  񕪖؂T
        if( this.hashMethod.hashRequires() <= this.TextBuffer.length - position ){
            int hash  = this.hashMethod.hash( position );
            scanpos   = this.hashTable[ hash ];
            scanlimit = Math.max( this.DictionaryLimit, 
                                  position - this.DictionarySize );
            while( scanpos != HashAndBinaryTreeSearch.UNUSED ){
                s = scanpos;
                p = position;
                while( buf[ s ] == buf[ p ] ){
                    s++;
                    p++;
                    if( max <= p ) break;
                }

                if( p < max ){
                    len = p - position;
                    if( scanlimit <= scanpos ){
                        if( matchlen < len ){
                            matchpos = scanpos;
                            matchlen = len;
                        }else if( matchlen == len && matchpos < scanpos ){
                            matchpos = scanpos;
                        }
                    }
                    scanpos = ( buf[ s ] < buf[ p ]
                              ? this.large[ scanpos & ( this.DictionarySize - 1 ) ]
                              : this.small[ scanpos & ( this.DictionarySize - 1 ) ] );
                }else{
                    break;
                }
            }
        }

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

    /**
     * TextBuffer position ܂ł̃f[^OֈړہA
     * ɉ nbVƓ񕪖؂gp@\\f[^
     * TextBuffer̃f[^ƖȂ悤ɑOֈړ鏈sB 
     */
    public void slide(){
        this.DictionaryLimit = Math.max( 0, this.DictionaryLimit - this.DictionarySize );

        this.slideTree( this.hashTable );
        this.slideTree( this.parent );
        this.slideTree( this.small );
        this.slideTree( this.large );
    }

    /**
     * put() ܂ searchAndPut() gp
     * f[^p^񕪖؂ɓo^ۂ
     * KvƂf[^ʂ𓾂B<br>
     * 񕪖؂͓o^̍ۂɃf[^p^\ 
     * S(MaxMatchoCg)̃f[^KvƂB
     * 
     * @return RXgN^ŗ^ MaxMatch
     */
    public int putRequires(){
        return this.MaxMatch;
    }


    //------------------------------------------------------------------
    //  local method
    //------------------------------------------------------------------
    //  node operation
    //------------------------------------------------------------------
    //  private void addNode( int addpos, int position, int len )
    //  private void deleteNode( int position )
    //  private void contractNode( int oldpos, int newpos )
    //  private void replaceNode( int oldpos, int newpos )
    //------------------------------------------------------------------
    /**
     * parentpos ̃f[^p^̎qƂ 
     * position n܂f[^p^񕪖؂ɓo^B<br>
     * parentpos  position ̃f[^p^ len oCgvB
     * position ̈ʒũm[h͂炩 deleteNode 
     * UNUSED ̏ԂɂĂƁB
     * 
     * @param parentpos ẽf[^p^TextBuffer̊Jnʒu
     * @param position  VKljf[^p^TextBuffer̊Jnʒu
     * @param len       ẽf[^p^ƐVKljf[^p^̈v
     */
    private void addNode( int parentpos, int position, int len ){
        int parentnode = parentpos & ( this.DictionarySize - 1 );
        int node       = position  & ( this.DictionarySize - 1 );

        if( this.TextBuffer[ parentpos + len ] < this.TextBuffer[ position  + len ] ){
            this.large[ parentnode ] = position;
        }else{
            this.small[ parentnode ] = position;
        }
        this.parent[ node ] = parentpos;
        this.small[ node ]  = HashAndBinaryTreeSearch.UNUSED;
        this.large[ node ]  = HashAndBinaryTreeSearch.UNUSED;
    }

    /**
     * position n܂f[^p^񕪖؂폜B<br>
     * 
     * @param position 폜f[^p^̊Jnʒu
     */
    private void deleteNode( int position ){
        int node = position & ( this.DictionarySize - 1 );

        if( this.parent[ node ] != HashAndBinaryTreeSearch.UNUSED ){
            if( this.small[ node ] == HashAndBinaryTreeSearch.UNUSED
             && this.large[ node ] == HashAndBinaryTreeSearch.UNUSED ){
                this.contractNode( position, HashAndBinaryTreeSearch.UNUSED );
            }else if( this.small[ node ] == HashAndBinaryTreeSearch.UNUSED ){
                this.contractNode( position, this.large[ node ] );
            }else if( this.large[ node ] == HashAndBinaryTreeSearch.UNUSED ){
                this.contractNode( position, this.small[ node ] );
            }else{
                int replace = this.findNext( position );
                this.deleteNode( replace );
                this.replaceNode( position, replace );
            }
        }
    }

    /**
     * q newpos Ȃ oldpos , newpos ŒuB
     * oldpos ͓񕪖؂폜B
     * 
     * @param oldpos 폜f[^p^̊Jnʒu
     * @param newpos oldposɒuf[^p^̊Jnʒu
     */
    private void contractNode( int oldpos, int newpos ){
        int oldnode    = oldpos    & ( this.DictionarySize - 1 );
        int newnode    = newpos    & ( this.DictionarySize - 1 );
        int parentpos  = this.parent[ oldnode ];
        int parentnode = parentpos & ( this.DictionarySize - 1 );

        if( parentpos != HashAndBinaryTreeSearch.ROOT_NODE ){
            if( oldpos == this.small[ parentnode ] ){
                this.small[ parentnode ] = newpos;
            }else{
                this.large[ parentnode ] = newpos;
            }
        }else{
            this.hashTable[ this.hashMethod.hash( oldpos ) ] = newpos;
        }

        if( newpos != HashAndBinaryTreeSearch.UNUSED ){
            this.parent[ newnode ] = parentpos;
        }

        this.parent[ oldnode ] = HashAndBinaryTreeSearch.UNUSED;
    }

    /**
     * oldpos 񕪖؂Ɋ܂܂ȂVf[^p^ newpos ŒuB
     * newpos 񕪖؂Ɋ܂܂Ă悤ȏꍇɂ́A
     * deleteNode(newpos) ȂǂāA
     * 񕪖؂OKvB
     * oldpos ͓񕪖؂폜B
     * 
     * @param oldpos 폜f[^p^̊Jnʒu
     * @param newpos oldposɒuf[^p^̊Jnʒu
     */
    private void replaceNode( int oldpos, int newpos ){
        int oldnode    = oldpos    & ( this.DictionarySize - 1 );
        int newnode    = newpos    & ( this.DictionarySize - 1 );
        int parentpos  = this.parent[ oldnode ];
        int parentnode = parentpos & ( this.DictionarySize - 1 );

        if( parentpos != HashAndBinaryTreeSearch.ROOT_NODE ){
            if( oldpos == this.small[ parentnode ] ){
                this.small[ parentnode ] = newpos;
            }else{
                this.large[ parentnode ] = newpos;
            }
        }else{
            this.hashTable[ this.hashMethod.hash( oldpos ) ] = newpos;
        }

        this.parent[ newnode ] = parentpos;
        this.small[ newnode ]  = this.small[ oldnode ];
        this.large[ newnode ]  = this.large[ oldnode ];
        if( this.small[ newnode ] != HashAndBinaryTreeSearch.UNUSED ){
            this.parent[ this.small[ newnode ] & ( this.DictionarySize - 1 ) ] = newpos;
        }
        if( this.large[ newnode ] != HashAndBinaryTreeSearch.UNUSED ){
            this.parent[ this.large[ newnode ] & ( this.DictionarySize - 1 ) ] = newpos;
        }

        this.parent[ oldnode ] = HashAndBinaryTreeSearch.UNUSED;
        this.large[ oldnode ]  = HashAndBinaryTreeSearch.UNUSED;
        this.small[ oldnode ]  = HashAndBinaryTreeSearch.UNUSED;
    }


    //------------------------------------------------------------------
    //  local method
    //------------------------------------------------------------------
    //  other
    //------------------------------------------------------------------
    //  private int findNext( int position )
    //  private void slideTree( int[] src, int[] dst, int start, int end, int width )
    //------------------------------------------------------------------
    /**
     * deleteNode( position ) ƂɁA
     * small  large ̗̗t‚ꍇA
     * position ̂n܂f[^p^
     * uׂ f[^p^̊JnʒuToB
     * 
     * @param position uf[^p^̊Jnʒu
     * 
     * @return position ̂n܂f[^p^
     *         uׂ f[^p^̊Jnʒu
     */
    private int findNext( int position ){
        int node = position & ( this.DictionarySize - 1 );

        position = this.small[ node ];
        node =  position & ( this.DictionarySize - 1 );
        while( HashAndBinaryTreeSearch.UNUSED != this.large[ node ] ){
            position = this.large[ node ];
            node     = position & ( this.DictionarySize - 1 );
        }

        return position;
    }


    /**
     * slide() ɁA񕪖؂̊evfړ邽߂ɎgpB
     * 
     * @param array z
     */
    private void slideTree( int[] array ){
        for( int i = 0 ; i < array.length ; i++ ){
            array[ i ] = ( 0 <= array[i] 
                         ? array[i] - this.DictionarySize 
                         : array[i] );
        }
    }

}
//end of HashAndBinaryTreeSearch.java