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

   1 //\r
   2 // assembly:    System\r
   3 // namespace:   System.Text.RegularExpressions\r
   4 // file:        quicksearch.cs\r
   5 //\r
   6 // author:      Dan Lewis (dlewis@gmx.co.uk)\r
   7 //              (c) 2002\r
   8 \r
   9 using System;\r
  10 using System.Collections;\r
  11 \r
  12 namespace System.Text.RegularExpressions {\r
  13 \r
  14         // TODO use simple test for single character strings\r
  15 \r
  16         class QuickSearch {\r
  17                 // simplified boyer-moore for fast substring matching\r
  18         \r
  19                 public QuickSearch (string str, bool ignore) {\r
  20                         this.str = str;\r
  21                         this.len = str.Length;\r
  22                         this.ignore = ignore;\r
  23                 \r
  24                         Setup ();\r
  25                 }\r
  26                 \r
  27                 public string String {\r
  28                         get { return str; }\r
  29                 }\r
  30 \r
  31                 public int Length {\r
  32                         get { return len; }\r
  33                 }\r
  34 \r
  35                 public bool IgnoreCase {\r
  36                         get { return ignore; }\r
  37                 }\r
  38 \r
  39                 public int Search (string text, int start, int end) {\r
  40                         if (end > text.Length - len)\r
  41                                 end = text.Length - len;\r
  42                 \r
  43                         int ptr = start;\r
  44                         if (!ignore) {\r
  45                                 while (ptr <= end) {\r
  46                                         int i = len - 1;\r
  47                                         while (str[i] == text[ptr + i]) {\r
  48                                                 if (-- i < 0)\r
  49                                                         return ptr;\r
  50                                         }\r
  51 \r
  52                                         if (ptr < end)\r
  53                                                 ptr += GetShiftDistance (text[ptr + len]);\r
  54                                         else\r
  55                                                 break;\r
  56                                 }\r
  57                         }\r
  58                         else {\r
  59                                 // ignore case: same as above, but we convert text\r
  60                                 // to lower case before doing the string compare\r
  61                         \r
  62                                 while (ptr <= end) {\r
  63                                         int i = len - 1;\r
  64                                         while (str[i] == Char.ToLower (text[ptr + i])) {\r
  65                                                 if (-- i < 0)\r
  66                                                         return ptr;\r
  67                                         }\r
  68 \r
  69                                         if (ptr < end)\r
  70                                                 ptr += GetShiftDistance (text[ptr + len]);\r
  71                                         else\r
  72                                                 break;\r
  73                                 }\r
  74                         }\r
  75 \r
  76                         return -1;\r
  77                 }\r
  78 \r
  79                 // private\r
  80 \r
  81                 private void Setup () {\r
  82                         if (ignore)\r
  83                                 str = str.ToLower ();\r
  84 \r
  85                         shift = new Hashtable ();\r
  86                         for (int i = 0; i < len; ++ i) {\r
  87                                 char c = str[i];\r
  88 \r
  89                                 shift[c] = len - i;\r
  90                                 if (ignore)\r
  91                                         shift[Char.ToUpper (c)] = len - i;\r
  92                         }\r
  93                 }\r
  94             \r
  95                 int GetShiftDistance (char c){\r
  96                         object s = shift[c];\r
  97                         return (s != null ? (int)s : len + 1);\r
  98                 }\r
  99                 \r
 100                 private string str;\r
 101                 private int len;\r
 102                 private bool ignore;\r
 103 \r
 104                 Hashtable shift;\r
 105         }\r
 106 \r
 107 }\r