mcs/class/System/System.Text.RegularExpressions/quicksearch.cs

   1 //
   2 // assembly:    System
   3 // namespace:   System.Text.RegularExpressions
   4 // file:        quicksearch.cs
   5 //
   6 // Authors:     Dan Lewis (dlewis@gmx.co.uk)
   7 //               Juraj Skripsky (juraj@hotfeet.ch)
   8 //
   9 // (c) 2002 Dan Lewis
  10 // (c) 2007 Juraj Skripsky
  11 //
  12
  13 //
  14 // Permission is hereby granted, free of charge, to any person obtaining
  15 // a copy of this software and associated documentation files (the
  16 // "Software"), to deal in the Software without restriction, including
  17 // without limitation the rights to use, copy, modify, merge, publish,
  18 // distribute, sublicense, and/or sell copies of the Software, and to
  19 // permit persons to whom the Software is furnished to do so, subject to
  20 // the following conditions:
  21 //
  22 // The above copyright notice and this permission notice shall be
  23 // included in all copies or substantial portions of the Software.
  24 //
  25 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  26 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  27 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  28 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  29 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  30 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  31 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  32 //
  33
  34 using System;
  35 using System.Collections;
  36
  37 namespace System.Text.RegularExpressions {
  38         internal class QuickSearch {
  39                 // simplified boyer-moore for fast substring matching
  40                 // (for short strings, we use simple scans)
  41                 public QuickSearch (string str, bool ignore)
  42                         : this(str, ignore, false)
  43                 {
  44                 }
  45
  46                 public QuickSearch (string str, bool ignore, bool reverse) {
  47                         this.str = str;
  48                         this.len = str.Length;
  49                         this.ignore = ignore;
  50                         this.reverse = reverse;
  51
  52                         if (ignore)
  53                                 str = str.ToLower ();
  54
  55                         // create the shift table only for "long" search strings
  56                         if(len > THRESHOLD)
  57                                 SetupShiftTable ();
  58                 }
  59
  60                 public string String {
  61                         get { return str; }
  62                 }
  63
  64                 public int Length {
  65                         get { return len; }
  66                 }
  67
  68                 public bool IgnoreCase {
  69                         get { return ignore; }
  70                 }
  71
  72                 public int Search (string text, int start, int end) {
  73                         int ptr = start;
  74
  75
  76                         if ( reverse )
  77                         {
  78                                 if (start < end)
  79                                         return -1;
  80
  81                                 if ( ptr > text.Length)
  82                                 {
  83                                         ptr = text.Length;
  84                                 }
  85
  86                                 // use simple scan for a single-character search string
  87                                 if (len == 1)
  88                                 {
  89                                         while (--ptr >= end)
  90                                         {
  91                                                 if(str[0] == GetChar(text[ptr]))
  92                                                         return ptr ;
  93
  94                                         }
  95                                         return -1;
  96                                 }
  97
  98
  99                                 if ( end < len)
 100                                         end =  len - 1 ;
 101
 102                                 ptr--;
 103                                 while (ptr >= end)
 104                                 {
 105                                         int i = len -1 ;
 106                                         while (str[i] == GetChar(text[ptr - len +1 + i]))
 107                                         {
 108                                                 if (-- i <  0)
 109                                                         return ptr - len + 1;
 110                                         }
 111
 112                                         if (ptr > end)
 113                                         {
 114                                                 ptr -= GetShiftDistance (text[ptr - len ]);
 115
 116                                         }
 117                                         else
 118                                                 break;
 119                                 }
 120
 121                         }
 122                         else
 123                         {
 124                                 // use simple scan for a single-character search string
 125                                 if (len == 1)
 126                                 {
 127                                         while (ptr <= end)
 128                                         {
 129                                                 if(str[0] == GetChar(text[ptr]))
 130                                                         return ptr;
 131                                                 else
 132                                                         ptr++;
 133                                         }
 134                                         return -1;
 135                                 }
 136
 137                                 if (end > text.Length - len)
 138                                         end = text.Length - len;
 139
 140                                 while (ptr <= end)
 141                                 {
 142                                         int i = len - 1;
 143                                         while (str[i] == GetChar(text[ptr + i]))
 144                                         {
 145                                                 if (-- i < 0)
 146                                                         return ptr;
 147                                         }
 148
 149                                         if (ptr < end)
 150                                                 ptr += GetShiftDistance (text[ptr + len]);
 151                                         else
 152                                                 break;
 153                                 }
 154                         }
 155
 156                         return -1;
 157
 158                 }
 159
 160                         // private
 161
 162                 private void SetupShiftTable () {
 163                         bool needsExtendedTable = len > (byte.MaxValue - 1);
 164
 165                         byte maxLowChar = 0;
 166                         for (int i = 0; i < len; i++) {
 167                                 char cur = str [i];
 168                                 if (cur <= (char)byte.MaxValue) {
 169                                         if ((byte)cur > maxLowChar)
 170                                                 maxLowChar = (byte)cur;
 171                                 } else
 172                                         needsExtendedTable = true;
 173                         }
 174
 175                         shift = new byte [maxLowChar + 1];
 176                         if (needsExtendedTable)
 177                                 shiftExtended = new Hashtable ();
 178
 179                         for (int i = 0, j = len; i < len; i++, j--) {
 180                                 char c = str [(!reverse ? i : j - 1)];
 181                                 if (c < shift.Length) {
 182                                         if (j < byte.MaxValue) {
 183                                                 shift [c] = (byte)j;
 184                                                 continue;
 185                                         } else {
 186                                                 shift [c] = byte.MaxValue;
 187                                         }
 188                                 }
 189                                 shiftExtended [c] = j;
 190                         }
 191                 }
 192
 193                 private int GetShiftDistance (char c) {
 194                         if (shift == null)
 195                                 return 1;
 196
 197                         c = GetChar (c);
 198                         if (c < shift.Length) {
 199                                 int dist = shift [c];
 200                                 if (dist == 0) {
 201                                         return len + 1;
 202                                 } else {
 203                                         if (dist != byte.MaxValue)
 204                                                 return dist;
 205                                 }
 206                         } else {
 207                                 if (c < (char)byte.MaxValue)
 208                                         return len + 1;
 209                         }
 210
 211                         if (shiftExtended == null)
 212                                 return len + 1;
 213
 214                         object s = shiftExtended [c];
 215                         return (s != null ? (int)s : len + 1);
 216                 }
 217
 218                 private char GetChar(char c) {
 219                         return (!ignore ? c : Char.ToLower(c));
 220                 }
 221
 222                 private string str;
 223                 private int len;
 224                 private bool ignore;
 225                 private bool reverse;
 226
 227                 // shift[idx] contains value x  means
 228                 //  x == 0             => shift dist. == len + 1
 229                 //  x == byte.Maxvalue => shift dist. >= 255, look it up in shiftExtended
 230                 //  otherwise          => shift dist. == x
 231                 private byte[] shift;
 232                 private Hashtable shiftExtended;
 233                 private readonly static int THRESHOLD = 5;
 234         }
 235
 236 }