Author: Paramjeet Reen

How do I check a given string with "Template" pattern.

Answer:

Some of you may have already seen the translation of PattenMatch() API of common.c 
in MSDN Samples\VC98\sdk\sdktools\tlist by Jerome FORESTIER. 

This function is an attempt at improving & extending the translated code. The 
various improvements & extensions are: 

1. Removed bug wherein InputString="ab" is rejected by Pattern="a*b". 

2. Optimization has been incorporated for trailing wildcard "*" in the Pattern 
string. For such cases, there is a very significant speed increase which is 
directly propotional to the number of chars in the InputString that match the 
trailing Pattern wildcard. e.g. this function is 20 times faster for Pattern="a*" 
and InputString="abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb". The speed difference becomes 
even more on increasing the number of "b" characters in the InputString. 

3. Added new functionality of set exclusion. e.g. [^a-d] matches true if the 
InputString character is not a,b,c or d. 

4. Discarded local variables in the original translation. Used array notation 
instead. 

5. Added plenty of comments! 

6. This implementation is on an average 20% faster than the original translation. 
1   
2   {*****************************************************************}
3   {* This function implements a subset of regular expression based *}
4   {* search and is based on the translation of PattenMatch() API   *}
5   {* of common.c in MSDN Samples\VC98\sdk\sdktools\tlist           *}
6   {*****************************************************************}
7   {* MetaChars are  :                                              *}
8   {*            '*' : Zero or more chars.                          *}
9   {*            '?' : Any one char.                                *}
10  {*         [adgj] : Individual chars (inclusion).                *}
11  {*        [^adgj] : Individual chars (exclusion).                *}
12  {*          [a-d] : Range (inclusion).                           *}
13  {*         [^a-d] : Range (exclusion).                           *}
14  {*       [a-dg-j] : Multiple ranges (inclusion).                 *}
15  {*      [^a-dg-j] : Multiple ranges (exclusion).                 *}
16  {*  [ad-fhjnv-xz] : Mix of range & individual chars (inclusion). *}
17  {* [^ad-fhjnv-xz] : Mix of range & individual chars (exclusion). *}
18  {*****************************************************************}
19  
20  function MatchPattern(InpStr, Pattern: PChar): Boolean;
21  begin
22    while (True) do
23    begin
24      case Pattern[0] of
25        #0:
26          begin //End of pattern reached.
27            Result := (InpStr[0] = #0); //TRUE if end of InpStr.
28            Exit;
29          end;
30  
31        '*':
32          begin //Match zero or more occurances of any char.
33            if (Pattern[1] = #0) then
34            begin //Match any number of trailing chars.
35              Result := True;
36              Exit;
37            end
38            else
39              Inc(Pattern);
40  
41            while (InpStr[0] <> #0) do
42            begin //Try to match any substring of InpStr.
43              if (MatchPattern(InpStr, Pattern)) then
44              begin
45                Result := True;
46                Exit;
47              end;
48  
49              //Continue testing next char...
50              Inc(InpStr);
51            end;
52          end;
53  
54        '?':
55          begin //Match any one char.
56            if (InpStr[0] = #0) then
57            begin
58              Result := False;
59              Exit;
60            end;
61  
62            //Continue testing next char...
63            Inc(InpStr);
64            Inc(Pattern);
65          end;
66  
67        '[':
68          begin //Match given set of chars.
69            if (Pattern[1] in [#0, '[', ']']) then
70            begin //Invalid Set - So no match.
71              Result := False;
72              Exit;
73            end;
74  
75            if (Pattern[1] = '^') then
76            begin //Match for exclusion of given set...
77              Inc(Pattern, 2);
78              Result := True;
79              while (Pattern[0] <> ']') do
80              begin
81                if (Pattern[1] = '-') then
82                begin //Match char exclusion range.
83                  if (InpStr[0] >= Pattern[0]) and (InpStr[0] <= Pattern[2]) then
84                  begin //Given char failed set exclusion range.
85                    Result := False;
86                    Break;
87                  end
88                  else
89                    Inc(Pattern, 3);
90                end
91                else
92                begin //Match individual char exclusion.
93                  if (InpStr[0] = Pattern[0]) then
94                  begin //Given char failed set element exclusion.
95                    Result := False;
96                    Break;
97                  end
98                  else
99                    Inc(Pattern);
100               end;
101             end;
102           end
103           else
104           begin //Match for inclusion of given set...
105             Inc(Pattern);
106             Result := False;
107             while (Pattern[0] <> ']') do
108             begin
109               if (Pattern[1] = '-') then
110               begin //Match char inclusion range.
111                 if (InpStr[0] >= Pattern[0]) and (InpStr[0] <= Pattern[2]) then
112                 begin //Given char matched set range inclusion. Continue testing...
113                   Result := True;
114                   Break;
115                 end
116                 else
117                   Inc(Pattern, 3);
118               end
119               else
120               begin //Match individual char inclusion.
121                 if (InpStr[0] = Pattern[0]) then
122                 begin //Given char matched set element inclusion. Continue 
123 testing...
124                   Result := True;
125                   Break;
126                 end
127                 else
128                   Inc(Pattern);
129               end;
130             end;
131           end;
132 
133           if (Result) then
134           begin //Match was found. Continue further.
135             Inc(InpStr);
136 
137             //Position Pattern to char after "]"
138             while (Pattern[0] <> ']') and (Pattern[0] <> #0) do
139               Inc(Pattern);
140 
141             if (Pattern[0] = #0) then
142             begin //Invalid Pattern - missing "]"
143               Result := False;
144               Exit;
145             end
146             else
147               Inc(Pattern);
148           end
149           else
150             Exit;
151         end;
152 
153     else
154       begin //Match given single char.
155         if (InpStr[0] <> Pattern[0]) then
156         begin
157           Result := False;
158           Break;
159         end;
160 
161         //Continue testing next char...
162         Inc(InpStr);
163         Inc(Pattern);
164       end;
165     end;
166   end;
167 end;