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

/**
 * PatriciaTrieSearch.java
 * 
 * Copyright (C) 2001-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 java.math.BigInteger;
import jp.gr.java_conf.dangan.io.Bits;
import jp.gr.java_conf.dangan.util.lha.LzssOutputStream;
import jp.gr.java_conf.dangan.util.lha.LzssSearchMethod;

//import exceptions

/**
 * PATRICIA Trie gp LzssSearchMethod ̎B
 * 
 * <pre>
 * -- revision history --
 * $Log: PatriciaTrieSearch.java,v $
 * Revision 1.2  2002/12/10 22:28:55  dangan
 * [bug fix]
 *     put( DictionarySize * 2 )
 *     searchAndPut( DictionarySize * 2 ) ɑΉĂȂ̂CB
 *
 * Revision 1.1  2002/12/04 00:00:00  dangan
 * [change]
 *     LzssSearchMethod ̃C^tFCXύXɍ킹ăC^tFCXύXB
 * [maintenance]
 *     \[X
 *
 * Revision 1.0  2002/08/15 00:00:00  dangan
 * add to version control
 * [bug fix]
 *     contractNode  hashtable ̘AXgɌq̂YĂCB
 *     z  PatriciaTrieSearch.ROOT_NODE(-1) ŃANZXĂ̂CB
 * [maintenance]
 *     \[X
 *     ^up~
 *     CZX̏C
 *
 * </pre>
 * 
 * @author  $Author: dangan $
 * @version $Revision: 1.2 $
 */
public class PatriciaTrieSearch implements LzssSearchMethod{


    //------------------------------------------------------------------
    //  class field
    //------------------------------------------------------------------
    //  private static final int UNUSED
    //------------------------------------------------------------------
    /**
     * gpĂȂlB
     * parent[node]  UNUSED ꍇ node ͖gp node łB
     * prev[node], next[node]  UNUSED ꍇ́A
     * 瑤ɌZm[hƂB
     */
    private static final int UNUSED = 0;


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

    /**
     * LZSS kɎgplB
     * ővB
     */
    private int MaxMatch;

    /**
     * LZSS k/񈳏k臒lB
     * v ̒lȏł΁AkR[ho͂B
     */
    private int Threshold;


    //------------------------------------------------------------------
    //  instance field
    //------------------------------------------------------------------
    //  Text Buffer
    //------------------------------------------------------------------
    //  private byte[] TextBuffer
    //  private int DictionaryLimit
    //------------------------------------------------------------------
    /**
     * LZSS k{߂̃obt@B
     * LzssSearchMethod ̎ł͓ǂݍ݂̂݋B
     */
    private byte[] TextBuffer;

    /**
     * ̌EʒuB
     * TextBufferO̎̈ɖɃf[^ꍇ
     * ̈ɂs̃f[^(Java ł0)gp
     * ksȂ悤ɂB
     */
    private int DictionaryLimit;


    //------------------------------------------------------------------
    //  instance field
    //------------------------------------------------------------------
    //  PATRICIA TRIE
    //------------------------------------------------------------------
    //  private int[] parent
    //  private int[] hashTable
    //  private int[] prev
    //  private int[] next
    //  private int[] position
    //  private int[] level
    //  private int[] childnum
    //  private int avail
    //  private int shift
    //------------------------------------------------------------------
    /**
     * ẽm[hԍB
     * parent[node]  node ̐em[h̔ԍB
     */
    private int[] parent;

    /**
     * q̃nbVlB
     * hashTable[ hash( node, ch ) ] 
     * node ̕ ch ̎qm[h̃nbVlB
     */
    private int[] hashTable;

    /**
     * hashTable AȂoAXg̈ꕔB
     * nbVl ‘Õm[h̃m[hԍB
     * prev[ node ]  node ƓnbVlA
     * AXg node ̈‘OɈʒum[h node ԍB
     * prev[ node ]  l̏ꍇ͑Srbg]nbVlB
     */
    private int[] prev;

    /**
     * hashTable AȂoAXg̈ꕔB
     * nbVl Œ̃m[h̃m[hԍB
     * next[ node ]  node ƓnbVlA
     * AXg node ̈ŒɈʒum[h node ԍB
     * 
     * ܂AtłȂm[hɊւĂ next  avail  gpȃm[h
     * X^bN(AXg)\B
     * 
     * ɁASvߍ폜ꂽtm[hŁA
     * PATRICIA Trie ɑ݂Ătm[hւ̈AXg\B
     */
    private int[] next;

    /**
     * m[h TextBuffer ̃f[^p^̊JnʒuB
     * position[ node ]  node ̃f[^p^̊JnʒuB
     */
    private int[] position;

    /**
     * m[h ʒuB
     * level[ node ]  node ̎qm[h򂷂ʒuB
     */
    private int[] level;

    /**
     * m[h̎qm[h̐B
     * childnum[ node ]  node ̎qm[h̐B
     */
    private int[] childnum;

    /**
     * next \関gpm[h̃X^bÑX^bN|C^B
     */
    private int avail;

    /**
     * nbVɎgpVtgl
     */
    private int shift;


    //------------------------------------------------------------------
    //  instance field
    //------------------------------------------------------------------
    //  other
    //------------------------------------------------------------------
    //  private int lastMatchPos
    //  private int lastMatchLen
    //------------------------------------------------------------------
    /**
     * Ō searchAndPut() ܂ put() œꂽ
     * ꂽ PatriciaTrie̍Œvʒu
     */
    private int lastMatchPos;

    /**
     * Ō searchAndPut() ܂ put() 
     * ꂽ PatriciaTrie̍Œv
     */
    private int lastMatchLen;


    //------------------------------------------------------------------
    //  constructer
    //------------------------------------------------------------------
    //  private PatriciaTreeSearch()
    //  public PatriciaTreeSearch( int DictionarySize, int MaxMatch,
    //                             int Threshold, byte[] TextBuffer )
    //------------------------------------------------------------------
    /**
     * ftHgRXgN^B
     * gpsB
     */
    private PatriciaTrieSearch(){   }

    /**
     * RXgN^B
     * PATRICIA Trie gp@\\zB
     * 
     * @param DictionarySize TCY
     * @param MaxMatch       Œv
     * @param Threshold      kA񈳏k臒l
     * @param TextBuffer     LZSSk{߂̃obt@
     */
    public PatriciaTrieSearch( int    DictionarySize,
                               int    MaxMatch,
                               int    Threshold,
                               byte[] TextBuffer ){

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

        this.parent          = new int[ this.DictionarySize * 2 ];
        this.prev            = new int[ this.DictionarySize * 2 ];
        this.next            = new int[ this.DictionarySize * 2 ];
        this.position        = new int[ this.DictionarySize ];
        this.level           = new int[ this.DictionarySize ];
        this.childnum        = new int[ this.DictionarySize ];
        this.hashTable       = new int[ 
                PatriciaTrieSearch.generateProbablePrime( 
                        this.DictionarySize + ( this.DictionarySize >> 2 ) ) ];

        for( int i = 2 ; i < this.DictionarySize ; i++ ){
            this.next[i] = i - 1;
        }
        this.avail = this.DictionarySize - 1;

        for( int i = 0 ; i < this.DictionarySize * 2 ; i++ ){
            this.parent[ i ]    = PatriciaTrieSearch.UNUSED;
        }

        for( int i = 0 ; i < this.hashTable.length ; i++ ){
            this.hashTable[ i ] = PatriciaTrieSearch.UNUSED;
        }

        this.shift = Bits.len( this.DictionarySize ) - 8;

        this.lastMatchLen = 0;
        this.lastMatchPos = 0;
    }


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

        //------------------------------------------------------------------
        //  PATRICIA Trie łÂf[^p^폜
        int posnode = ( position & ( this.DictionarySize - 1 ) ) + this.DictionarySize;
        this.deleteNode( posnode );

        //------------------------------------------------------------------
        //  PATRICIA Trie Œv
        int matchnode = -1;
        int matchpos  = position;
        int scannode;
        int matchlen;
        if( 3 < this.lastMatchLen ){

            //Öv臒l傫΁A
            //t lastMatchLen - 1 ̈vB
            scannode  = ( this.lastMatchPos + 1 ) | this.DictionarySize;

            //Œv߂ scannode  
            //PATRICIA Trie 菜Ăꍇ̏
            while( this.parent[ scannode ] == PatriciaTrieSearch.UNUSED ){
                scannode = this.next[ scannode ];
            }

            //t ԂɐeւƒH
            //lastMatchLen - 1 ȉ level ƒm[hTB
            int node  = this.parent[ scannode ];
            this.lastMatchLen--;
            while( 0 < node 
                && this.lastMatchLen <= this.level[ node ] ){
                scannode = node;
                node = this.parent[ node ];
            }

            //ɐeւƒH position XVĂB
            while( 0 < node  ){
                this.position[ node ] = position;
                node = this.parent[ node ];
            }

            matchlen  = this.lastMatchLen;
        }else{

            //PATRICIA Trie  HB
            scannode  = this.child( this.TextBuffer[ position ] - 128, 
                                    this.TextBuffer[ position + 1 ] & 0xFF );
            matchlen  = 2;

            if( scannode == PatriciaTrieSearch.UNUSED ){
                // position ljB
                this.attachNode( this.TextBuffer[ position ] - 128, posnode, 
                                 this.TextBuffer[ position + 1 ] & 0xFF );
                this.lastMatchLen = matchlen;
                return;
            }
        }

        while( true ){
            int max;
            if( scannode < this.DictionarySize ){
                max       = this.level[ scannode ];
                matchnode = scannode;
                matchpos  = this.position[ scannode ];
            }else{
                max       = this.MaxMatch;
                matchnode = scannode;
                matchpos  = ( position <= scannode
                            ? scannode - this.DictionarySize
                            : scannode );
            }

            while( matchlen < max
                && ( this.TextBuffer[ matchpos + matchlen ] 
                  == this.TextBuffer[ position + matchlen ] ) ){
                matchlen++;
            }

            if( matchlen == max && matchlen < this.MaxMatch ){
                this.position[ scannode ] = position;
                scannode = this.child( scannode, 
                                       this.TextBuffer[ position + matchlen ] & 0xFF );

                if( scannode == PatriciaTrieSearch.UNUSED ){
                    this.attachNode( matchnode, posnode, 
                                     this.TextBuffer[ position + matchlen ] & 0xFF );
                    break;
                }else{
                    matchlen++;
                }
            }else if( matchlen < max ){
                //matchnode  position 𕪊򂳂B
                this.splitNode( matchnode, matchpos, posnode, position, matchlen );
                break;
            }else{
                //Sv𔭌Am[huB
                this.replaceNode( matchnode, posnode );
                this.next[ matchnode ] = position;
                break;
            }
        }

        //ʂۑ
        this.lastMatchLen = matchlen;
        this.lastMatchPos = matchpos;
    }

    /**
     * PATRICIA Trie ɓo^ꂽf[^p^ 
     * position n܂f[^p^
     * Œ̈v‚̂A
     *  position n܂f[^p^ 
     * PATRICIA Trie ɓ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 ){

        //------------------------------------------------------------------
        //  PATRICIA Trie łÂf[^p^폜
        int posnode = ( position & ( this.DictionarySize - 1 ) ) + this.DictionarySize;
        this.deleteNode( posnode );

        //------------------------------------------------------------------
        //  PATRICIA Trie Œv
        int matchnode = -1;
        int matchpos  = position;
        int scannode  = 0;
        int matchlen  = 0;
        if( 3 < this.lastMatchLen ){

            //Öv臒l傫΁A
            //t lastMatchLen - 1 ̈vB
            scannode  = ( this.lastMatchPos + 1 ) | this.DictionarySize;

            //Œv߂ scannode  
            //PATRICIA Trie 菜Ăꍇ̏
            while( this.parent[ scannode ] == PatriciaTrieSearch.UNUSED ){
                scannode = this.next[ scannode ];
            }

            //t ԂɐeւƒH
            //lastMatchLen - 1 ȉ level ƒm[hTB
            int node  = this.parent[ scannode ];
            this.lastMatchLen--;
            while( 0 < node 
                && this.lastMatchLen <= this.level[ node ] ){
                scannode = node;
                node = this.parent[ node ];
            }

            //ɐeւƒH position XVĂB
            while( 0 < node  ){
                this.position[ node ] = position;
                node = this.parent[ node ];
            }

            matchlen  = this.lastMatchLen;
        }else{
            //PATRICIA Trie  HB
            scannode  = this.child( this.TextBuffer[ position ] - 128, 
                                    this.TextBuffer[ position + 1 ] & 0xFF );
            matchlen  = 2;
        }

        // scannode == UNUSED ƂȂ̂ lastMatchLen 臒l菬Ƃ̂݁B
        if( scannode != PatriciaTrieSearch.UNUSED ){
            while( true ){
                int max;
                if( scannode < this.DictionarySize ){
                    max       = this.level[ scannode ];
                    matchnode = scannode;
                    matchpos  = this.position[ scannode ];
                }else{
                    max       = this.MaxMatch;
                    matchnode = scannode;
                    matchpos  = ( position <= scannode
                                ? scannode - this.DictionarySize
                                : scannode );
                }

                while( matchlen < max
                    && ( this.TextBuffer[ matchpos + matchlen ] 
                      == this.TextBuffer[ position + matchlen ] ) ){
                    matchlen++;
                }

                if( matchlen == max && matchlen < this.MaxMatch ){
                    this.position[ scannode ] = position;
                    scannode = this.child( scannode, 
                                           this.TextBuffer[ position + matchlen ] & 0xFF );

                    if( scannode == PatriciaTrieSearch.UNUSED ){
                        //matchnode  position ljB
                        this.attachNode( matchnode, posnode, 
                                         this.TextBuffer[ position + matchlen ] & 0xFF );
                        break;
                    }else{
                        matchlen++;
                    }
                }else if( matchlen < max ){
                    //matchnode  position 𕪊򂳂B
                    this.splitNode( matchnode, matchpos, posnode, position, matchlen );
                    break;
                }else{
                    //Sv𔭌Am[huB
                    this.replaceNode( matchnode, posnode );
                    this.next[ matchnode ] = position;
                    break;
                }
            }
        }else{ //if( scannode != PatriciaTrieSearch.UNUSED )
            // position ljB
            this.attachNode( this.TextBuffer[ position ] - 128, posnode, 
                             this.TextBuffer[ position + 1 ] & 0xFF );
            matchlen = 0;
        }

        //ʂۑ
        this.lastMatchLen = matchlen;
        this.lastMatchPos = matchpos;


        //------------------------------------------------------------------
        //  \bh擪 PATRICIA Trie 폜f[^p^`FbNB
        scannode = position - this.DictionarySize;
        if( this.DictionaryLimit <= scannode ){
            int len = 0;
            while( this.TextBuffer[ scannode + len ]
                == this.TextBuffer[ position + len ] )
                if( this.MaxMatch <= ++len ) break;

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

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

    /**
     * PATRICIA Trie ɓ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 ){

        //------------------------------------------------------------------
        //  PATRICIA Trie ɓo^ĂȂf[^p^
        //  PȒŌB
        int scanlimit = Math.max( this.DictionaryLimit, lastPutPos );
        int scanpos   = position - 1;
        int matchlen  = 0;
        int matchpos  = 0;

        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;
            }

            len = p - position;
            if( matchlen < len ){
                matchpos = scanpos;
                matchlen = len;
                if( max <= p ) break;
            }
            scanpos--;
        }


        //------------------------------------------------------------------
        //  PATRICIA Trie T
        if( 2 < this.TextBuffer.length - position  ){
            int matchnode = this.child( this.TextBuffer[ position ] - 128, 
                                        this.TextBuffer[ position + 1 ] & 0xFF );
            scanlimit = Math.max( this.DictionaryLimit, 
                                  position - this.DictionarySize );
            len       = 2;
            while( matchnode != PatriciaTrieSearch.UNUSED ){
                int maxlen;
                if( matchnode < this.DictionarySize ){
                    maxlen  = this.level[ matchnode ];
                    scanpos = this.position[ matchnode ];
                }else{
                    maxlen  = this.MaxMatch;
                    scanpos = ( lastPutPos < matchnode
                              ? matchnode - this.DictionarySize
                              : matchnode );
                }

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

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

                    if( len == maxlen && matchlen < this.MaxMatch ){
                        if( position + len < this.TextBuffer.length ){
                            matchnode = this.child( matchnode, 
                                                    this.TextBuffer[ position + len ] & 0xFF );

                            if( matchnode != PatriciaTrieSearch.UNUSED ){
                                len++;
                            }
                        }else{
                            break;
                        }
                    }else{  //maxlen ɖȂv‚ Sv‚
                        break;
                    }
                }else{ //if( scanlimit <= scanpos ) vp^͌E𒴂ĂB
                    break;
                }
            }   //while( matchnode != PatriciaTrieSearch.UNUSED )
        }   //if( 2 <= this.TextBuffer.length - position  )


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

    /**
     * TextBufferposition܂ł̃f[^
     * OֈړہAɉ LzssSearchMethod
     * ̃f[^ TextBuffer̃f[^ƖȂ
     * ɑOֈړ鏈sB 
     */
    public void slide(){
        this.DictionaryLimit = Math.max( 0, this.DictionaryLimit - this.DictionarySize );
        this.lastMatchPos   -= this.DictionarySize;

        for( int i = 0 ; i < this.position.length ; i++ ){
            int pos = this.position[i] - this.DictionarySize;
            if( 0 < pos ){
                this.position[i] = pos;
            }else{
                this.position[i] = 0;
            }
        }
    }

    /**
     * put()  LzssSearchMethodɃf[^
     * o^ƂɎgpf[^ʂ𓾂B
     * PatriciaTrieSearch ł́A MaxMatch ԂB
     * 
     * @return  MaxMatch
     */
    public int putRequires(){
        return this.MaxMatch;
    } 

    //------------------------------------------------------------------
    //  local method
    //------------------------------------------------------------------
    //  manipulate node
    //------------------------------------------------------------------
    //  private void splitNode( int oldnode, int oldpos, int position, int splitLen )
    //  private void deleteNode( int node )
    //  private void attatchNode( int parentnode, int childnode, int pos )
    //  private void replaceNode( int oldnode, int newnode )
    //  private void contractNode( int node )
    //------------------------------------------------------------------
    /**
     * oldnode  splitLen ŕ򂳂B
     * oldnode ̂ʒuɂ͐Vm[hV݂A
     * Vm[h oldnode  position qɎB
     * 
     * @param oldnode  򂳂m[h 
     * @param oldpos   oldnode wf[^p^̊Jnʒu
     * @param posnode  position pm[h
     * @param position TextBuffer ̃f[^p^̊Jnʒu
     * @param splitLen f[^p^̕ʒu
     */
    private void splitNode( int oldnode, int oldpos, int posnode, int position, int splitLen ){
        //X^bN Vm[h擾B
        int newnode = this.avail;
        this.avail  = this.next[ newnode ];

        this.replaceNode( oldnode, newnode );
        this.level[ newnode ]     = splitLen;
        this.position[ newnode ]  = position;
        this.childnum[ newnode ]  = 0;

        this.attachNode( newnode, oldnode,  
                         this.TextBuffer[ oldpos   + splitLen ] & 0xFF );
        this.attachNode( newnode, posnode, 
                         this.TextBuffer[ position + splitLen ] & 0xFF );
    }


    /**
     * PATRICIA Trie tł node 폜B
     * Kvł node ̐em[ȟJグsB
     * 
     * @param node 폜tm[h
     */
    private void deleteNode( int node ){
        if( this.parent[ node ] != PatriciaTrieSearch.UNUSED ){
            int parent = this.parent[ node ];
            int prev   = this.prev[ node ];
            int next   = this.next[ node ];

            this.parent[ node ] = PatriciaTrieSearch.UNUSED;
            this.prev[ node ]   = PatriciaTrieSearch.UNUSED;
            this.next[ node ]   = PatriciaTrieSearch.UNUSED;

            if( 0 <= prev ){
                this.next[ prev ]       = next;
            }else{
                this.hashTable[ ~prev ] = next;
            }
            this.prev[ next ] = prev;

            if( 0 < parent ){ //parent  PATRICIA Trie ̍Ŗꍇ true ƂȂ
                this.childnum[ parent ]--;

                if( this.childnum[ parent ] <= 1 ){
                    this.contractNode( this.child( parent,
                                        this.TextBuffer[ this.position[ parent ]
                                                        + this.level[ parent ] ]
                                        & 0xFF ) );
                }
            }
        }
    }

    /**
     * parentnode  childnode ljB
     * 
     * @param parentnode childnode ljΏۂ̐em[h
     * @param childnode  parentnode ɒljm[h
     * @param pos        TextBufferݏʒuB
     *                   t position m肷邽߂ɎgpB
     */
    private void attachNode( int parentnode, int childnode, int ch ){
        int hash                 = this.hash( parentnode, ch );
        int node                 = this.hashTable[ hash ];
        this.hashTable[ hash ]   = childnode;
        this.parent[ childnode ] = parentnode;
        this.prev[ childnode ]   = ~hash;
        this.next[ childnode ]   = node;
        this.prev[ node ]        = childnode;

        if( 0 < parentnode ){
            this.childnum[ parentnode ]++;
        }
    }

    /**
     * oldnode  newnode ւB
     * newnode ͎qm[hƂ̊֌WێB
     * oldnode ͒u PATRICIA Trie 菜B
     * 
     * @param oldnode ւ Trie 폜m[h
     * @param newnode oldnode ̂ʒu֐ڑm[h
     */
    private void replaceNode( int oldnode, int newnode ){
        this.parent[ newnode ]   = this.parent[ oldnode ];
        this.prev[ newnode ]     = this.prev[ oldnode ];
        this.next[ newnode ]     = this.next[ oldnode ];

        this.prev[ this.next[ newnode ] ] = newnode;

        if( this.prev[ newnode ] < 0 ){
            this.hashTable[ ~this.prev[ newnode ] ] = newnode;
        }else{
            this.next[ this.prev[ newnode ] ]       = newnode;
        }

        this.parent[ oldnode ] = PatriciaTrieSearch.UNUSED;
        this.prev[ oldnode ]   = PatriciaTrieSearch.UNUSED;
        this.next[ oldnode ]   = PatriciaTrieSearch.UNUSED;
    }

    /**
     * Z̖Ȃ node グB
     * node ̐em[h PATRICIA Trie 폜A
     *  node ̈ʒuɐڑB
     * Z킪ǂ ͌ĂяosB
     * 
     * @param node グm[h
     */
    private void contractNode( int node ){
        int parentnode    = this.parent[ node ];

        this.prev[ this.next[ node ] ] = this.prev[ node ];
        if( 0 <= this.prev[ node ] ){
            this.next[ this.prev[ node ] ]        = this.next[ node ];
        }else{
            this.hashTable[ ~ this.prev[ node ] ] = this.next[ node ];
        }
        this.replaceNode( parentnode, node );

        //gpȂȂ parentnode X^bNɕԊ҂B
        this.next[ parentnode ] = this.avail;
        this.avail              = parentnode;
    }


    //------------------------------------------------------------------
    //  local method
    //------------------------------------------------------------------
    //  other
    //------------------------------------------------------------------
    //  public void slideTree( int[] src, int[] dst, int width )
    //  private int child( int parent, int ch )
    //  private int hash( int node, int ch )
    //------------------------------------------------------------------
    /**
     * slide  Trie ̊evfړ鏈sB
     * 
     * @param src   ړ
     * @param dst   ړ
     * @param width ړ
     */
    private void slideTree( int[] src, int[] dst, int width ){
        for( int i = 0 ; i < this.DictionarySize ; i++ )
            dst[i] = ( src[ i ] < this.DictionarySize
                     ? src[ i ]
                     : ( ( src[ i ] - width ) & ( this.DictionarySize - 1 ) ) 
                         + this.DictionarySize );

        for( int i = this.DictionarySize ; i < src.length ; i++  )
            dst[ ( ( i - width ) & ( this.DictionarySize - 1 ) ) 
                 + this.DictionarySize ] = ( src[ i ] < this.DictionarySize
                                           ? src[ i ]
                                           : ( ( src[ i ] - width ) 
                                               & ( this.DictionarySize - 1 ) )
                                             + this.DictionarySize );
    }

    /**
     * parent  ch ŕ򂵂q𓾂B
     * m[hꍇ UNUSED ԂB
     * 
     * @param parent em[h
     * @param ch     򕶎
     * 
     * @return qm[h
     */
    private int child( int parent, int ch ){
        int node = this.hashTable[ this.hash( parent, ch ) ];

        //this.parent[ PatriciaTrieSearch.UNUSED ] = parent;
        while( node != PatriciaTrieSearch.UNUSED
            && this.parent[ node ] != parent ){
            node = this.next[ node ];
        }

        return node;
    }

    /**
     * node  ch  nbVl𓾂
     * 
     * @param node m[h
     * @param ch   򕶎
     * 
     * @return nbVl
     */
    private int hash( int node, int ch ){
        return ( node + ( ch << this.shift ) + 256 ) % this.hashTable.length;
    }

    //------------------------------------------------------------------
    //  local method
    //------------------------------------------------------------------
    //  generate prime
    //------------------------------------------------------------------
    //  private static int generateProbablePrime( int num )
    //------------------------------------------------------------------
    /**
     * num ȏ̍ł f(͋[f)𐶐B 
     * ߂l fłȂm 1/256 ȉłB
     * 
     * @param num ̒lȏ̑f𐶐B
     *
     * @return ꂽf(͋[f)
     */
    private static int generateProbablePrime( int num ){
        num = num + ( ( num & 1 ) == 0 ? 1 : 0 );

        while( !(new BigInteger(Integer.toString(num))).isProbablePrime( 8 ) ){
            num += 2;
            num = num + ( ( num % 3 ) == 0 ? 2 : 0 );
            num = num + ( ( num % 5 ) == 0 ? 2 : 0 );
            num = num + ( ( num % 7 ) == 0 ? 2 : 0 );
        }
        return num;
    }

}

// 
//  
//  //------------------------------------------------------------------
//  //  local method
//  //------------------------------------------------------------------
//  //  check
//  //------------------------------------------------------------------
//  //  private void checkTrie( int pos )
//  //  private void checkNode( int node, int pos )
//  //  private void writeNode( int node )
//  //------------------------------------------------------------------
//  /**
//   * TrieŜ̃`FbNsB
//   * 
//   * @param pos ݏʒuB
//   * 
//   * @exception RuntimeException Trie ĂꍇB
//   */
//  private void checkTrie( int pos ){
//      for( int i = -256 ; i < 0 ; i++ ){
//          this.checkNode( i, pos );
//      }
//
//      for( int i = 1 ; i < this.DictionarySize ; i++ ){
//          if( this.parent[ i ] != PatriciaTrieSearch.UNUSED ){
//              this.checkNode( i, pos );
//          }
//      }
//  }
//
//  /**
//   * tłȂ Node ̃`FbNsB
//   * 
//   * `FbNڂ
//   * (1) eq֌W
//   * (2) position ɖB
//   * (3) level ɖB
//   * (4) node  this.childnum[node] ‚̎qĂ鎖B
//   * 4ځB
//   * 
//   * @param node `FbNm[h
//   * @param pos  ݏʒu
//   * 
//   * @exception RuntimeException L̃`FbN̉ꂩsꍇB
//   */
//  private void checkNode( int node, int pos ){
//
//      int nlevel;
//      int npos;
//      if( node < 0 ){
//          nlevel = 0;
//          npos   = this.TextBuffer.length;
//      }else{
//          nlevel = this.level[ node ];
//          npos   = this.position[ node ];
//      }
//
//      int childcount = 0;
//      for( int i = 0 ; i < 256 ; i++ ){
//          int child = this.child( node, i );
//
//          if( child != PatriciaTrieSearch.UNUSED ){
//              childcount++;
//
//              if( this.parent[ child ] != node ){
//                  System.out.println( "unlink::parent<->child" );
//                  this.writeNode( node );
//                  this.writeNode( child );
//                  throw new RuntimeException( "Trie Broken" );
//              }
//
//              if( child < this.DictionarySize ){
//                  if( this.level[ child ] <= nlevel ){
//                      System.out.println( "broken hierarchy::level" );
//                      this.writeNode( node );
//                      this.writeNode( child );
//                      throw new RuntimeException( "Trie Broken" );
//                  }
//
//                  if( npos < this.position[ child ] ){
//                      System.out.println( "broken hierarchy::position" );
//                      this.writeNode( node );
//                      this.writeNode( child );
//                      throw new RuntimeException( "Trie Broken" );
//                  }
//                  //this.checkTrie( child, pos );
//              }else{
//                  int childpos = ( pos <= child ? child - this.DictionarySize : child );
//                  if( npos < childpos ){
//                      System.out.println( "broken hierarchy::position" );
//                      this.writeNode( node );
//                      this.writeNode( child );
//                      throw new RuntimeException( "Trie Broken" );
//                  }
//              }
//          }
//      }
//
//      if( 0 < node && node < this.DictionarySize ){
//          if( this.childnum[ node ] != childcount ){
//              System.out.println( "broken hierarchy::childnum" );
//              this.writeNode( node );
//              throw new RuntimeException( "Trie Broken" );
//          }
//      }
//  }
//
//  /**
//   * m[h̏o͂B
//   * 
//   * @param node o͂m[h
//   */
//  private void writeNode( int node ){
//      if( 0 < node ){
//        System.out.println( "this.parent[" + node + "]  ::" + this.parent[ node ] );
//        System.out.println( "this.prev[" + node + "]    ::" + this.prev[ node ] );
//        System.out.println( "this.next[" + node + "]    ::" + this.next[ node ] );
//        if( node < this.DictionarySize ){
//            System.out.println( "this.childnum[" + node + "]::" + this.childnum[ node ] );
//            System.out.println( "this.position[" + node + "]::" + this.position[ node ] );
//            System.out.println( "this.level[" + node + "]   ::" + this.level[ node ] );
//        }
//    }else if( node < 0 ){
//        System.out.println( "ROOT_NODE                  ::" + node );
//    }else{
//        System.out.println( "UNUSED                     ::" + node );
//    }
//      
//  }

//end of PatriciaTrieSearch.java