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 using System;
  14 using System.Collections;
  15
  16 namespace System.Text.RegularExpressions {
  17         internal class QuickSearch {
  18                 // simplified boyer-moore for fast substring matching
  19                 // (for short strings, we use simple scans)
  20                 public QuickSearch (string str, bool ignore)
  21                         : this(str, ignore, false)
  22                 {
  23                 }
  24
  25                 public QuickSearch (string str, bool ignore, bool reverse) {
  26                         this.str = str;
  27                         this.len = str.Length;
  28                         this.ignore = ignore;
  29                         this.reverse = reverse;
  30
  31                         if (ignore)
  32                                 str = str.ToLower ();
  33
  34                         // create the shift table only for "long" search strings
  35                         if(len > THRESHOLD)
  36                                 SetupShiftTable ();
  37                 }
  38
  39                 public string String {
  40                         get { return str; }
  41                 }
  42
  43                 public int Length {
  44                         get { return len; }
  45                 }
  46
  47                 public bool IgnoreCase {
  48                         get { return ignore; }
  49                 }
  50
  51                 public int Search (string text, int start, int end) {
  52                         int ptr = start;
  53
  54
  55                         if ( reverse )
  56                         {
  57                                 if (start < end)
  58                                         return -1;
  59
  60                                 if ( ptr > text.Length)
  61                                 {
  62                                         ptr = text.Length;
  63                                 }
  64
  65                                 // use simple scan for a single-character search string
  66                                 if (len == 1)
  67                                 {
  68                                         while (--ptr >= end)
  69                                         {
  70                                                 if(str[0] == GetChar(text[ptr]))
  71                                                         return ptr ;
  72
  73                                         }
  74                                         return -1;
  75                                 }
  76
  77
  78                                 if ( end < len)
  79                                         end =  len - 1 ;
  80
  81                                 ptr--;
  82                                 while (ptr >= end)
  83                                 {
  84                                         int i = len -1 ;
  85                                         while (str[i] == GetChar(text[ptr - len +1 + i]))
  86                                         {
  87                                                 if (-- i <  0)
  88                                                         return ptr - len + 1;
  89                                         }
  90
  91                                         if (ptr > end)
  92                                         {
  93                                                 ptr -= GetShiftDistance (text[ptr - len ]);
  94
  95                                         }
  96                                         else
  97                                                 break;
  98                                 }
  99
 100                         }
 101                         else
 102                         {
 103                                 // use simple scan for a single-character search string
 104                                 if (len == 1)
 105                                 {
 106                                         while (ptr <= end)
 107                                         {
 108                                                 if(str[0] == GetChar(text[ptr]))
 109                                                         return ptr;
 110                                                 else
 111                                                         ptr++;
 112                                         }
 113                                         return -1;
 114                                 }
 115
 116                                 if (end > text.Length - len)
 117                                         end = text.Length - len;
 118
 119                                 while (ptr <= end)
 120                                 {
 121                                         int i = len - 1;
 122                                         while (str[i] == GetChar(text[ptr + i]))
 123                                         {
 124                                                 if (-- i < 0)
 125                                                         return ptr;
 126                                         }
 127
 128                                         if (ptr < end)
 129                                                 ptr += GetShiftDistance (text[ptr + len]);
 130                                         else
 131                                                 break;
 132                                 }
 133                         }
 134
 135                         return -1;
 136
 137                 }
 138
 139                         // private
 140
 141                 private void SetupShiftTable () {
 142                         shift = new Hashtable ();
 143                         if (reverse)
 144                         {
 145                                 for (int i = len ; i > 0; -- i)
 146                                 {
 147                                         char c = str[i -1];
 148                                         shift[GetChar(c)] = i;
 149                                 }
 150                         }
 151                         else
 152                         {
 153                                 for (int i = 0; i < len; ++ i)
 154                                 {
 155                                         char c = str[i];
 156                                         shift[GetChar(c)] = len - i;
 157                                 }
 158                         }
 159
 160                 }
 161
 162                 private int GetShiftDistance (char c) {
 163                         if(shift == null)
 164                                 return 1;
 165
 166                         object s = shift[c];
 167                         return (s != null ? (int)s : len + 1);
 168                 }
 169
 170                 private char GetChar(char c) {
 171                         return (!ignore ? c : Char.ToLower(c));
 172                 }
 173
 174                 private string str;
 175                 private int len;
 176                 private bool ignore;
 177                 private bool reverse;
 178
 179                 private Hashtable shift;
 180                 private readonly static int THRESHOLD = 5;
 181         }
 182
 183 }