src/com/stevesoft/pat/SkipBMH.java

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