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         class QuickSearch {
  18                 // simplified boyer-moore for fast substring matching
  19                 // (for short strings, we use simple scans)
  20
  21                 public QuickSearch (string str, bool ignore) {
  22                         this.str = str;
  23                         this.len = str.Length;
  24                         this.ignore = ignore;
  25
  26                         if (ignore)
  27                                 str = str.ToLower ();
  28
  29                         // create the shift table only for "long" search strings
  30                         if(len > THRESHOLD)
  31                                 SetupShiftTable ();
  32                 }
  33
  34                 public string String {
  35                         get { return str; }
  36                 }
  37
  38                 public int Length {
  39                         get { return len; }
  40                 }
  41
  42                 public bool IgnoreCase {
  43                         get { return ignore; }
  44                 }
  45
  46                 public int Search (string text, int start, int end) {
  47                         int ptr = start;
  48
  49                         // use simple scan for a single-character search string
  50                         if (len == 1) {
  51                                 while (ptr <= end) {
  52                                         if(str[0] == GetChar(text[ptr]))
  53                                                 return ptr;
  54                                         else
  55                                                 ptr++;
  56                                 }
  57                                 return -1;
  58                         }
  59
  60                         if (end > text.Length - len)
  61                                 end = text.Length - len;
  62
  63                         while (ptr <= end) {
  64                                 int i = len - 1;
  65                                 while (str[i] == GetChar(text[ptr + i])) {
  66                                         if (-- i < 0)
  67                                                 return ptr;
  68                                 }
  69
  70                                 if (ptr < end)
  71                                         ptr += GetShiftDistance (text[ptr + len]);
  72                                 else
  73                                         break;
  74                         }
  75
  76                         return -1;
  77                 }
  78
  79                 // private
  80
  81                 private void SetupShiftTable () {
  82                         shift = new Hashtable ();
  83                         for (int i = 0; i < len; ++ i) {
  84                                 char c = str[i];
  85                                 shift[GetChar(c)] = len - i;
  86                         }
  87                 }
  88
  89                 private int GetShiftDistance (char c) {
  90                         if(shift == null)
  91                                 return 1;
  92
  93                         object s = shift[c];
  94                         return (s != null ? (int)s : len + 1);
  95                 }
  96
  97                 private char GetChar(char c) {
  98                         return (!ignore ? c : Char.ToLower(c));
  99                 }
 100
 101                 private string str;
 102                 private int len;
 103                 private bool ignore;
 104
 105                 private Hashtable shift;
 106                 private readonly static int THRESHOLD = 5;
 107         }
 108
 109 }