src/com/stevesoft/pat/SkipBMH.java

   1 //
   2 // This software is now distributed according to
   3 // the Lesser Gnu Public License.  Please see
   4 // http://www.gnu.org/copyleft/lesser.txt for
   5 // the details.
   6 //    -- Happy Computing!
   7 //
   8 package com.stevesoft.pat;
   9
  10 import com.stevesoft.pat.wrap.StringWrap;
  11
  12 /**
  13  * Like Skip, but implements a <a
  14  * href="http://www.dcc.uchile.cl/~rbaeza/handbook/algs/7/713b.srch.p.html">
  15  * Boyer-Moore-Horspool</a> type search method that has been modified to be more
  16  * like a "T-search" (see the Michael Tamm''s article in <i>C'T, magazin fuer
  17  * computer und technic</i>, August 97 p 292). Yet another important source of
  18  * information for me was the <a
  19  * href="http://www.go2net.com/people/paulp/deep/1997/05/14/"> Deep Magic</a>
  20  * article on string searching. As of this writing, I can beat String's indexOf
  21  * method in many cases.
  22  *
  23  * @see com.stevesoft.pat.Skip
  24  * @see com.stevesoft.pat.Skip2
  25  */
  26 public class SkipBMH extends Skip
  27 {
  28   // This number could be 256, but I think it's
  29   // big enough. Note, it must be a power of 2.
  30   final int MAX_CHAR = 64;
  31
  32   final char[] skip = new char[MAX_CHAR];
  33
  34   int sm1;
  35
  36   int jump_ahead = 0;
  37
  38   char uc, lc, tc, x;
  39
  40   final boolean exact(char c)
  41   {
  42     return (ign && anyc(c)) || c == x;
  43   }
  44
  45   final boolean anyc(char c)
  46   {
  47     return c == uc || c == lc || c == tc;
  48   }
  49
  50   public SkipBMH(String pt, boolean ign)
  51   {
  52     this(pt, ign, 0);
  53   }
  54
  55   public SkipBMH(String pt)
  56   {
  57     this(pt, false, 0);
  58   }
  59
  60   public SkipBMH(String pt, boolean ign, int offset)
  61   {
  62     super(pt, ign, offset);
  63     for (int k = 0; k < MAX_CHAR; k++)
  64     {
  65       skip[k] = (char) src.length();
  66     }
  67
  68     sm1 = src.length() - 1;
  69     x = src.charAt(sm1);
  70     uc = CaseMgr.toUpperCase(x);
  71     lc = CaseMgr.toLowerCase(x);
  72     tc = CaseMgr.toTitleCase(x);
  73
  74     // We don't really want 65536 long arrays in skip[],
  75     // so we mask of the higher bits. This can be combined
  76     // with ignore case, so accounting for upper
  77     // case costs us nothing extra.
  78     for (int k = 0; k < src.length() - 1; k++)
  79     {
  80       char x_ = src.charAt(k);
  81       if (ign)
  82       {
  83         char uc_ = CaseMgr.toUpperCase(x_);
  84         char lc_ = CaseMgr.toLowerCase(x_);
  85         char tc_ = CaseMgr.toTitleCase(x_);
  86         skip[uc_ & (MAX_CHAR - 1)] = (char) (src.length() - k - 1);
  87         skip[lc_ & (MAX_CHAR - 1)] = (char) (src.length() - k - 1);
  88         skip[tc_ & (MAX_CHAR - 1)] = (char) (src.length() - k - 1);
  89       }
  90       else
  91       {
  92         skip[x_ & (MAX_CHAR - 1)] = (char) (src.length() - k - 1);
  93       }
  94     }
  95
  96     // This trick can be found in the July issue of
  97     // C-T magazine. This makes the method a type of
  98     // "T-search."
  99     jump_ahead = src.length() - 1;
 100     for (int k = 0; k < src.length() - 1; k++)
 101     {
 102       char y = src.charAt(sm1 - k - 1);
 103       if (exact(y))
 104       {
 105         jump_ahead = k;
 106         break;
 107       }
 108     }
 109   }
 110
 111   /**
 112    * Set to true if you only want to compare two of the characters in the
 113    * String.
 114    */
 115   final public int searchRegion(String s, int start, int end)
 116   {
 117     return find(s, start, end);
 118   }
 119
 120   final public int searchFrom(String s, int start)
 121   {
 122     return find(s, start, s.length());
 123   }
 124
 125   final public int search(String s)
 126   {
 127     return find(s, 0, s.length());
 128   }
 129
 130   public int find(String s, int start, int end)
 131   {
 132     start += offset + sm1;
 133     int vend = min(s.length() - 1, end + sm1 + offset), k;
 134     int vend1 = vend - jump_ahead;
 135     if (ign)
 136     {
 137       for (k = start; k <= vend1; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
 138       {
 139         // table look-up is expensive, avoid it if possible
 140         if (anyc(s.charAt(k)))
 141         {
 142           if (CaseMgr.regionMatches(src, ign, 0, s, k - sm1, sm1))
 143           {
 144             return k - sm1 - offset;
 145           }
 146           k += jump_ahead;
 147         }
 148       }
 149       for (; k <= vend; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
 150       {
 151         // table look-up is expensive, avoid it if possible
 152         if (anyc(s.charAt(k)))
 153         {
 154           if (CaseMgr.regionMatches(src, ign, 0, s, k - sm1, sm1))
 155           {
 156             return k - sm1 - offset;
 157           }
 158           k += jump_ahead;
 159           if (k > vend)
 160           {
 161             return -1;
 162           }
 163         }
 164       }
 165     }
 166     else
 167     {
 168       for (k = start; k <= vend1; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
 169       {
 170         // table look-up is expensive, avoid it if possible
 171         if (x == s.charAt(k))
 172         {
 173           // if(src.regionMatches(0,s,k-sm1,sm1))
 174           if (CaseMgr.regionMatches(src, false, 0, s, k - sm1, sm1))
 175           {
 176             return k - sm1 - offset;
 177           }
 178           k += jump_ahead;
 179         }
 180       }
 181       for (; k <= vend; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
 182       {
 183         // table look-up is expensive, avoid it if possible
 184         if (x == s.charAt(k))
 185         {
 186           // if(src.regionMatches(0,s,k-sm1,sm1))
 187           if (CaseMgr.regionMatches(src, false, 0, s, k - sm1, sm1))
 188           {
 189             return k - sm1 - offset;
 190           }
 191           k += jump_ahead;
 192           if (k > vend)
 193           {
 194             return -1;
 195           }
 196         }
 197       }
 198     }
 199
 200     return -1;
 201   }
 202
 203   public int find(StringLike s, int start, int end)
 204   {
 205     if (s instanceof StringWrap)
 206     {
 207       return find(s.toString(), start, end);
 208     }
 209     start += offset + sm1;
 210     int vend = min(s.length() - 1, end + sm1 + offset), k;
 211     int vend1 = vend - jump_ahead;
 212     if (ign)
 213     {
 214       for (k = start; k <= vend1; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
 215       {
 216         // table look-up is expensive, avoid it if possible
 217         if (anyc(s.charAt(k)))
 218         {
 219           if (CaseMgr.regionMatches(src, ign, 0, s, k - sm1, sm1))
 220           {
 221             return k - sm1 - offset;
 222           }
 223           k += jump_ahead;
 224         }
 225       }
 226       for (; k <= vend; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
 227       {
 228         // table look-up is expensive, avoid it if possible
 229         if (anyc(s.charAt(k)))
 230         {
 231           if (CaseMgr.regionMatches(src, ign, 0, s, k - sm1, sm1))
 232           {
 233             return k - sm1 - offset;
 234           }
 235           k += jump_ahead;
 236           if (k > vend)
 237           {
 238             return -1;
 239           }
 240         }
 241       }
 242     }
 243     else
 244     {
 245       for (k = start; k <= vend1; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
 246       {
 247         // table look-up is expensive, avoid it if possible
 248         if (x == s.charAt(k))
 249         {
 250           // if(src.regionMatches(0,s,k-sm1,sm1))
 251           if (CaseMgr.regionMatches(src, false, 0, s, k - sm1, sm1))
 252           {
 253             return k - sm1 - offset;
 254           }
 255           k += jump_ahead;
 256         }
 257       }
 258       for (; k <= vend; k += skip[s.charAt(k) & (MAX_CHAR - 1)])
 259       {
 260         // table look-up is expensive, avoid it if possible
 261         if (x == s.charAt(k))
 262         {
 263           // if(src.regionMatches(0,s,k-sm1,sm1))
 264           if (CaseMgr.regionMatches(src, false, 0, s, k - sm1, sm1))
 265           {
 266             return k - sm1 - offset;
 267           }
 268           k += jump_ahead;
 269           if (k > vend)
 270           {
 271             return -1;
 272           }
 273         }
 274       }
 275     }
 276
 277     return -1;
 278   }
 279 }