src/com/stevesoft/pat/SkipBMH.java

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