//
// This software is now distributed according to
// the Lesser Gnu Public License.  Please see
// http://www.gnu.org/copyleft/lesser.txt for
// the details.
//    -- Happy Computing!
//
package com.stevesoft.pat;

import com.stevesoft.pat.wrap.StringWrap;

/** Like Skip, but implements a
    <a href="http://www.dcc.uchile.cl/~rbaeza/handbook/algs/7/713b.srch.p.html">
    Boyer-Moore-Horspool</a> type search
    method that has been modified to be more like a "T-search" (see
    the Michael Tamm''s article in <i>C'T, magazin fuer computer und technic</i>, August 97
    p 292).  Yet another important source of information for me was
    the <a href="http://www.go2net.com/people/paulp/deep/1997/05/14/">
    Deep Magic</a> article on string searching.  As of this writing, I can
    beat String's indexOf method in many cases.
    @see com.stevesoft.pat.Skip
    @see com.stevesoft.pat.Skip2
    */
public class SkipBMH extends Skip {
    // This number could be 256, but I think it's
    // big enough.  Note, it must be a power of 2.
    final int MAX_CHAR = 64;
    final char[] skip = new char[MAX_CHAR];
    int sm1;
    int jump_ahead = 0;
    char uc,lc,tc,x;
    final boolean exact(char c) {
        return (ign && anyc(c))||c==x;
    }
    final boolean anyc(char c) {
        return c==uc||c==lc||c==tc;
    }
    public SkipBMH(String pt,boolean ign) { this(pt,ign,0); }
    public SkipBMH(String pt) { this(pt,false,0); }
    public SkipBMH(String pt,boolean ign,int offset) {
        super(pt,ign,offset);
        for(int k=0;k<MAX_CHAR;k++)
            skip[k] = (char)src.length();

        sm1 = src.length()-1;
        x = src.charAt(sm1);
        uc=CaseMgr.toUpperCase(x);
        lc=CaseMgr.toLowerCase(x);
        tc=CaseMgr.toTitleCase(x);

        // We don't really want 65536 long arrays in skip[],
        // so we mask of the higher bits.  This can be combined
        // with ignore case, so accounting for upper
        // case costs us nothing extra.
        for(int k=0;k<src.length()-1;k++) {
            char x_ = src.charAt(k);
            if(ign) {
                char uc_ = CaseMgr.toUpperCase(x_);
                char lc_ = CaseMgr.toLowerCase(x_);
                char tc_ = CaseMgr.toTitleCase(x_);
                skip[uc_ & (MAX_CHAR-1)]=(char)(src.length()-k-1);
                skip[lc_ & (MAX_CHAR-1)]=(char)(src.length()-k-1);
                skip[tc_ & (MAX_CHAR-1)]=(char)(src.length()-k-1);
            } else
                skip[x_ & (MAX_CHAR-1)] = (char)(src.length()-k-1);
        }

        // This trick can be found in the July issue of
        // C-T magazine.  This makes the method a type of
        // "T-search."
        jump_ahead = src.length()-1;
        for(int k=0;k<src.length()-1;k++) {
            char y=src.charAt(sm1-k-1);
            if(exact(y)) {
                jump_ahead = k;
                break;
            }
        }
    }
    /** Set to true if you only want to compare two of the
        characters in the String. */
    final public int searchRegion(String s,int start,int end) {
        return find(s,start,end);
    }
    final public int searchFrom(String s,int start) {
        return find(s,start,s.length());
    }
    final public int search(String s) { return find(s,0,s.length()); }
    public int find(String s,int start,int end) {
        start += offset+sm1;
        int vend = min(s.length()-1,end+sm1+offset),k;
        int vend1 = vend-jump_ahead;
        if(ign) {
            for(k=start; k <= vend1;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {
                // table look-up is expensive, avoid it if possible
                if( anyc(s.charAt(k)) ) {
                    if(CaseMgr.regionMatches(src,ign,0,s,k-sm1,sm1))
                        return k-sm1-offset;
                    k += jump_ahead;
                }
            }
            for(; k <= vend;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {
                // table look-up is expensive, avoid it if possible
                if( anyc(s.charAt(k)) ) {
                    if(CaseMgr.regionMatches(src,ign,0,s,k-sm1,sm1))
                        return k-sm1-offset;
                    k += jump_ahead;
                    if(k > vend) return -1;
                }
            }
        } else {
            for(k=start; k <= vend1;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {
                // table look-up is expensive, avoid it if possible
                if( x==s.charAt(k) ) {
                    //if(src.regionMatches(0,s,k-sm1,sm1))
                    if(CaseMgr.regionMatches(src,false,0,s,k-sm1,sm1))
                        return k-sm1-offset;
                    k += jump_ahead;
                }
            }
            for(; k <= vend;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {
                // table look-up is expensive, avoid it if possible
                if( x==s.charAt(k) ) {
                    //if(src.regionMatches(0,s,k-sm1,sm1))
                    if(CaseMgr.regionMatches(src,false,0,s,k-sm1,sm1))
                        return k-sm1-offset;
                    k += jump_ahead;
                    if(k > vend) return -1;
                }
            }
        }

        return -1;
    }
    public int find(StringLike s,int start,int end) {
        if(s instanceof StringWrap)
          return find(s.toString(),start,end);
        start += offset+sm1;
        int vend = min(s.length()-1,end+sm1+offset),k;
        int vend1 = vend-jump_ahead;
        if(ign) {
            for(k=start; k <= vend1;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {
                // table look-up is expensive, avoid it if possible
                if( anyc(s.charAt(k)) ) {
                    if(CaseMgr.regionMatches(src,ign,0,s,k-sm1,sm1))
                        return k-sm1-offset;
                    k += jump_ahead;
                }
            }
            for(; k <= vend;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {
                // table look-up is expensive, avoid it if possible
                if( anyc(s.charAt(k)) ) {
                    if(CaseMgr.regionMatches(src,ign,0,s,k-sm1,sm1))
                        return k-sm1-offset;
                    k += jump_ahead;
                    if(k > vend) return -1;
                }
            }
        } else {
            for(k=start; k <= vend1;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {
                // table look-up is expensive, avoid it if possible
                if( x==s.charAt(k) ) {
                    //if(src.regionMatches(0,s,k-sm1,sm1))
                    if(CaseMgr.regionMatches(src,false,0,s,k-sm1,sm1))
                        return k-sm1-offset;
                    k += jump_ahead;
                }
            }
            for(; k <= vend;k += skip[s.charAt(k) & (MAX_CHAR-1)] ) {
                // table look-up is expensive, avoid it if possible
                if( x==s.charAt(k) ) {
                    //if(src.regionMatches(0,s,k-sm1,sm1))
                    if(CaseMgr.regionMatches(src,false,0,s,k-sm1,sm1))
                        return k-sm1-offset;
                    k += jump_ahead;
                    if(k > vend) return -1;
                }
            }
        }

        return -1;
    }
}