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) 2003 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                         shift = new Hashtable ();
 164                         if (reverse)
 165                         {
 166                                 for (int i = len ; i > 0; -- i)
 167                                 {
 168                                         char c = str[i -1];
 169                                         shift[GetChar(c)] = i;
 170                                 }
 171                         }
 172                         else
 173                         {
 174                                 for (int i = 0; i < len; ++ i)
 175                                 {
 176                                         char c = str[i];
 177                                         shift[GetChar(c)] = len - i;
 178                                 }
 179                         }
 180
 181                 }
 182
 183                 private int GetShiftDistance (char c) {
 184                         if(shift == null)
 185                                 return 1;
 186
 187                         object s = shift[c];
 188                         return (s != null ? (int)s : len + 1);
 189                 }
 190
 191                 private char GetChar(char c) {
 192                         return (!ignore ? c : Char.ToLower(c));
 193                 }
 194
 195                 private string str;
 196                 private int len;
 197                 private bool ignore;
 198                 private bool reverse;
 199
 200                 private Hashtable shift;
 201                 private readonly static int THRESHOLD = 5;
 202         }
 203
 204 }