/[eiffelstudio]/FreeELKS/trunk/library/kernel/string_searcher.e
ViewVC logotype

Diff of /FreeELKS/trunk/library/kernel/string_searcher.e

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 91476 by ericb, Sat Feb 4 16:56:42 2006 UTC revision 91477 by ericb, Sun Jan 14 09:47:13 2007 UTC
# Line 28  feature {NONE} -- Initialization Line 28  feature {NONE} -- Initialization
28    
29  feature -- Initialization  feature -- Initialization
30    
31          initialize_deltas (a_pattern: STRING) is          initialize_deltas (a_pattern: STRING_GENERAL) is
32                          -- Initialize `deltas' with `a_pattern'.                          -- Initialize `deltas' with `a_pattern'.
33                          -- Optimized for ASCII characters only.                          -- Optimized for ASCII characters only.
34                  require                  require
35                          a_pattern_not_void: a_pattern /= Void                          a_pattern_not_void: a_pattern /= Void
36                            a_pattern_valid: a_pattern.is_valid_as_string_8
37                  do                  do
38                          internal_initialize_deltas (a_pattern, a_pattern.count, deltas)                          internal_initialize_deltas (a_pattern, a_pattern.count, deltas)
39                  end                  end
# Line 44  feature -- Access Line 45  feature -- Access
45    
46  feature -- Search  feature -- Search
47    
48          substring_index (a_string, a_pattern: STRING; start_pos, end_pos: INTEGER): INTEGER is          substring_index (a_string, a_pattern: STRING_GENERAL; start_pos, end_pos: INTEGER): INTEGER is
49                          -- Position of first occurrence of `a_pattern' at or after `start_pos'                          -- Position of first occurrence of `a_pattern' at or after `start_pos'
50                          -- and before `end_pos' in `a_string'.                          -- and before `end_pos' in `a_string'.
51                          -- 0 if there are no matches.                          -- 0 if there are no matches.
52                  require                  require
53                          a_string_not_void: a_string /= Void                          a_string_not_void: a_string /= Void
54                          a_pattern_not_void: a_pattern /= Void                          a_pattern_not_void: a_pattern /= Void
55                            a_pattern_valid: a_pattern.is_valid_as_string_8
56                          start_large_enough: start_pos >= 1                          start_large_enough: start_pos >= 1
57                          end_pos_large_enough: start_pos <= end_pos + 1                          end_pos_large_enough: start_pos <= end_pos + 1
58                          end_pos_small_enough: end_pos <= a_string.count                          end_pos_small_enough: end_pos <= a_string.count
# Line 69  feature -- Search Line 71  feature -- Search
71                          end                          end
72                  end                  end
73    
74          substring_index_with_deltas (a_string, a_pattern: STRING; start_pos, end_pos: INTEGER): INTEGER is          substring_index_with_deltas (a_string, a_pattern: STRING_GENERAL; start_pos, end_pos: INTEGER): INTEGER is
75                          -- Position of first occurrence of `a_pattern' at or after `start_pos' in `a_string'.                          -- Position of first occurrence of `a_pattern' at or after `start_pos' in `a_string'.
76                          -- 0 if there are no matches.                          -- 0 if there are no matches.
77                  require                  require
78                          a_string_not_void: a_string /= Void                          a_string_not_void: a_string /= Void
79                          a_pattern_not_void: a_pattern /= Void                          a_pattern_not_void: a_pattern /= Void
80                            a_pattern_valid: a_pattern.is_valid_as_string_8
81                          a_pattern_not_empty: not a_pattern.is_empty                          a_pattern_not_empty: not a_pattern.is_empty
82                          start_large_enough: start_pos >= 1                          start_large_enough: start_pos >= 1
83                          end_pos_large_enough: start_pos <= end_pos + 1                          end_pos_large_enough: start_pos <= end_pos + 1
84                          end_pos_small_enough: end_pos <= a_string.count                          end_pos_small_enough: end_pos <= a_string.count
85                  local                  local
86                          i, j: INTEGER                          i, j, l_end_pos: INTEGER
87                          l_pattern_count: INTEGER                          l_pattern_count: INTEGER
88                          l_matched: BOOLEAN                          l_matched: BOOLEAN
                         l_area, l_pattern_area: SPECIAL [CHARACTER]  
89                          l_char_code: INTEGER                          l_char_code: INTEGER
90                          l_deltas: like deltas                          l_deltas: like deltas
91                  do                  do
# Line 93  feature -- Search Line 95  feature -- Search
95                                  end                                  end
96                          else                          else
97                                  l_pattern_count := a_pattern.count                                  l_pattern_count := a_pattern.count
98                                  if l_pattern_count = 0 then                                  check l_pattern_count_positive: l_pattern_count > 0 end
99                                          Result := start_pos                                  from
100                                  else                                          i := start_pos
101                                            l_deltas := deltas
102                                            l_end_pos := end_pos + 1
103                                    until
104                                            i + l_pattern_count > l_end_pos
105                                    loop
106                                          from                                          from
107                                                  l_area := a_string.area                                                  j := 0
108                                                  l_pattern_area := a_pattern.area                                                  l_matched := True
                                                 l_deltas := deltas  
                                                 i := start_pos - 1  
109                                          until                                          until
110                                                  i + l_pattern_count > end_pos                                                  j = l_pattern_count
111                                          loop                                          loop
112                                                  from                                                  if a_string.code (i + j) /= a_pattern.code (j + 1) then
113                                                          j := 0                                                                  -- Mismatch, so we stop
114                                                          l_matched := True                                                          j := l_pattern_count - 1        -- Jump out of loop
115                                                  until                                                          l_matched := False
                                                         j = l_pattern_count  
                                                 loop  
                                                         if l_area.item (i + j) /= l_pattern_area.item (j) then  
                                                                         -- Mismatch, so we stop  
                                                                 j := l_pattern_count - 1        -- Jump out of loop  
                                                                 l_matched := False  
                                                         end  
                                                         j := j + 1  
116                                                  end                                                  end
117                                                    j := j + 1
118                                            end
119    
120                                                  if l_matched then                                          if l_matched then
121                                                                  -- We got the substring                                                          -- We got the substring
122                                                          Result := i + 1                                                  Result := i
123                                                          i := end_pos + 1        -- Jump out of loop                                                  i := l_end_pos  -- Jump out of loop
124                                                  else                                          else
125                                                                  -- Pattern was not found, shift to next location                                                          -- Pattern was not found, shift to next location
126                                                          l_char_code := l_area.item (i + l_pattern_count).code                                                  if i + l_pattern_count <= end_pos then
127                                                            l_char_code := a_string.code (i + l_pattern_count).to_integer_32
128                                                          if l_char_code > max_ascii_character_value then                                                          if l_char_code > max_ascii_character_value then
129                                                                  i := i + 1                                                                  i := i + 1
130                                                          else                                                          else
131                                                                  i := i + l_deltas.item (l_char_code)                                                                  i := i + l_deltas.item (l_char_code)
132                                                          end                                                          end
133                                                    else
134                                                            i := i + 1
135                                                  end                                                  end
136                                          end                                          end
137                                  end                                  end
138                          end                          end
139                  end                  end
140    
141          fuzzy_index (a_string, a_pattern: STRING; start_pos, end_pos, fuzzy: INTEGER): INTEGER is          fuzzy_index (a_string, a_pattern: STRING_GENERAL; start_pos, end_pos, fuzzy: INTEGER): INTEGER is
142                          -- Position of first occurrence of `a_pattern' at or after `start_pos' in                          -- Position of first occurrence of `a_pattern' at or after `start_pos' in
143                          -- `a_string' with 0..`fuzzy' mismatches between `a_string' and `a_pattern'.                          -- `a_string' with 0..`fuzzy' mismatches between `a_string' and `a_pattern'.
144                          -- 0 if there are no fuzzy matches.                          -- 0 if there are no fuzzy matches.
145                  require                  require
146                          a_string_not_void: a_string /= Void                          a_string_not_void: a_string /= Void
147                          a_pattern_not_void: a_pattern /= Void                          a_pattern_not_void: a_pattern /= Void
148                            a_pattern_valid: a_pattern.is_valid_as_string_8
149                          a_pattern_not_empty: not a_pattern.is_empty                          a_pattern_not_empty: not a_pattern.is_empty
150                          start_large_enough: start_pos >= 1                          start_large_enough: start_pos >= 1
151                          end_pos_large_enough: start_pos <= end_pos + 1                          end_pos_large_enough: start_pos <= end_pos + 1
# Line 150  feature -- Search Line 153  feature -- Search
153                          fuzzy_non_negative: fuzzy >= 0                          fuzzy_non_negative: fuzzy >= 0
154                          acceptable_fuzzy: fuzzy <= a_pattern.count                          acceptable_fuzzy: fuzzy <= a_pattern.count
155                  local                  local
156                          i, j, l_min_offset: INTEGER                          i, j, l_min_offset, l_end_pos: INTEGER
157                          l_pattern_count, l_nb_mismatched: INTEGER                          l_pattern_count, l_nb_mismatched: INTEGER
158                          l_matched: BOOLEAN                          l_matched: BOOLEAN
                         l_area, l_pattern_area: SPECIAL [CHARACTER]  
159                          l_char_code: INTEGER                          l_char_code: INTEGER
160                          l_deltas_array: like deltas_array                          l_deltas_array: like deltas_array
161                  do                  do
# Line 166  feature -- Search Line 168  feature -- Search
168                                  else                                  else
169                                          initialize_fuzzy_deltas (a_pattern, fuzzy)                                          initialize_fuzzy_deltas (a_pattern, fuzzy)
170                                          from                                          from
                                                 l_area := a_string.area  
                                                 l_pattern_area := a_pattern.area  
171                                                  l_pattern_count := a_pattern.count                                                  l_pattern_count := a_pattern.count
172                                                  l_deltas_array := deltas_array                                                  l_deltas_array := deltas_array
173                                                  i := start_pos - 1                                                  i := start_pos
174                                                    l_end_pos := end_pos + 1
175                                          until                                          until
176                                                  i + l_pattern_count > end_pos                                                  i + l_pattern_count > l_end_pos
177                                          loop                                          loop
178                                                  from                                                  from
179                                                          j := 0                                                          j := 0
# Line 181  feature -- Search Line 182  feature -- Search
182                                                  until                                                  until
183                                                          j = l_pattern_count                                                          j = l_pattern_count
184                                                  loop                                                  loop
185                                                          if l_area.item (i + j) /= l_pattern_area.item (j) then                                                          if a_string.code (i + j) /= a_pattern.code (j + 1) then
186                                                                  l_nb_mismatched := l_nb_mismatched + 1;                                                                  l_nb_mismatched := l_nb_mismatched + 1;
187                                                                  if l_nb_mismatched > fuzzy then                                                                  if l_nb_mismatched > fuzzy then
188                                                                                  -- Too manu mismatched, so we stop                                                                                  -- Too many mismatched, so we stop
189                                                                          j := l_pattern_count - 1        -- Jump out of loop                                                                          j := l_pattern_count - 1        -- Jump out of loop
190                                                                          l_matched := False                                                                          l_matched := False
191                                                                  end                                                                  end
# Line 194  feature -- Search Line 195  feature -- Search
195    
196                                                  if l_matched then                                                  if l_matched then
197                                                                  -- We got the substring                                                                  -- We got the substring
198                                                          Result := i + 1                                                          Result := i
199                                                          i := end_pos + 1        -- Jump out of loop                                                          i := l_end_pos  -- Jump out of loop
200                                                  else                                                  else
201                                                                  -- Pattern was not found, compute shift to next location                                                          if i + l_pattern_count <= end_pos then
202                                                          from                                                                          -- Pattern was not found, compute shift to next location
203                                                                  j := 0                                                                  from
204                                                                  l_min_offset := l_pattern_count + 1                                                                          j := 0
205                                                          until                                                                          l_min_offset := l_pattern_count + 1
206                                                                  j > fuzzy                                                                  until
207                                                          loop                                                                          j > fuzzy
208                                                                  l_char_code := l_area.item (i + l_pattern_count - j).code                                                                  loop
209                                                                  if l_char_code > max_ascii_character_value then                                                                          l_char_code := a_string.code (i + l_pattern_count - j).to_integer_32
210                                                                                  -- No optimization for a non-extended ASCII character.                                                                          if l_char_code > max_ascii_character_value then
211                                                                          l_min_offset := 1                                                                                          -- No optimization for a non-extended ASCII character.
212                                                                          j := fuzzy + 1 -- Jump out of loop                                                                                  l_min_offset := 1
213                                                                  else                                                                                  j := fuzzy + 1 -- Jump out of loop
214                                                                          l_min_offset := l_min_offset.min (l_deltas_array.item (j).item (l_char_code))                                                                          else
215                                                                                    l_min_offset := l_min_offset.min (l_deltas_array.item (j).item (l_char_code))
216                                                                            end
217                                                                            j := j + 1
218                                                                  end                                                                  end
219                                                                  j := j + 1                                                                  i := i + l_min_offset
220                                                            else
221                                                                    i := i + 1
222                                                          end                                                          end
                                                         i := i + l_min_offset  
223                                                  end                                                  end
224                                          end                                          end
225                                          deltas_array := Void                                          deltas_array := Void
# Line 232  feature {NONE} -- Implementation: Access Line 237  feature {NONE} -- Implementation: Access
237    
238  feature {NONE} -- Implementation  feature {NONE} -- Implementation
239    
240          internal_initialize_deltas (a_pattern: STRING; a_pattern_count: INTEGER; a_deltas: like deltas) is          internal_initialize_deltas (a_pattern: STRING_GENERAL; a_pattern_count: INTEGER; a_deltas: like deltas) is
241                          -- Initialize `a_deltas' with `a_pattern'.                          -- Initialize `a_deltas' with `a_pattern'.
242                          -- Optimized for ASCII characters only.                          -- Optimized for ASCII characters only.
243                  require                  require
244                          a_pattern_not_void: a_pattern /= Void                          a_pattern_not_void: a_pattern /= Void
245                            a_pattern_valid: a_pattern.is_valid_as_string_8
246                          a_pattern_count_not_negative: a_pattern_count >= 0                          a_pattern_count_not_negative: a_pattern_count >= 0
247                          a_pattern_count_valid: a_pattern_count <= a_pattern.count                          a_pattern_count_valid: a_pattern_count <= a_pattern.count
248                          a_deltas_not_void: a_deltas /= Void                          a_deltas_not_void: a_deltas /= Void
249                          a_deltas_valid: a_deltas.count <= max_ascii_character_value + 1                                          a_deltas_valid: a_deltas.count = max_ascii_character_value + 1
250                  local                  local
                         l_area: SPECIAL [CHARACTER]  
251                          i, l_char_code: INTEGER                          i, l_char_code: INTEGER
252                  do                  do
253                                  -- Initialize the delta table (one more than pattern count).                                  -- Initialize the delta table (one more than pattern count).
# Line 253  feature {NONE} -- Implementation Line 258  feature {NONE} -- Implementation
258                                  -- we scan the pattern from left to right (ie. if there is two 'a', only the                                  -- we scan the pattern from left to right (ie. if there is two 'a', only the
259                                  -- delta associated with the second --rightmost-- will be kept).                                  -- delta associated with the second --rightmost-- will be kept).
260                          from                          from
                                 l_area := a_pattern.area  
261                                  i := 0                                  i := 0
262                          until                          until
263                                  i = a_pattern_count                                  i = a_pattern_count
264                          loop                          loop
265                                  l_char_code := l_area.item (i).code                                  l_char_code := a_pattern.code (i + 1).to_integer_32
266                                  if l_char_code <= max_ascii_character_value then                                  if l_char_code <= max_ascii_character_value then
267                                          a_deltas.put (a_pattern_count - i, l_char_code)                                          a_deltas.put (a_pattern_count - i, l_char_code)
268                                  end                                  end
# Line 266  feature {NONE} -- Implementation Line 270  feature {NONE} -- Implementation
270                          end                          end
271                  end                  end
272    
273          initialize_fuzzy_deltas (a_pattern: STRING; fuzzy: INTEGER) is          initialize_fuzzy_deltas (a_pattern: STRING_GENERAL; fuzzy: INTEGER) is
274                          -- Compile `a_pattern' by computing the delta shift tables from a pattern                          -- Compile `a_pattern' by computing the delta shift tables from a pattern
275                          -- string. This has to be done before searching occurs. The first delta                          -- string. This has to be done before searching occurs. The first delta
276                          -- table is computed with the full pattern, the second one is computed with                          -- table is computed with the full pattern, the second one is computed with
# Line 274  feature {NONE} -- Implementation Line 278  feature {NONE} -- Implementation
278                          -- are computed and stored in `deltas_array'.                          -- are computed and stored in `deltas_array'.
279                  require                  require
280                          a_pattern_not_void: a_pattern /= Void                          a_pattern_not_void: a_pattern /= Void
281                            a_pattern_valid: a_pattern.is_valid_as_string_8
282                          fuzzy_positive: fuzzy > 0                          fuzzy_positive: fuzzy > 0
283                  local                  local
284                          l_deltas: like deltas                          l_deltas: like deltas
# Line 302  feature {NONE} -- Implementation Line 307  feature {NONE} -- Implementation
307    
308  invariant  invariant
309          deltas_not_void: deltas /= Void          deltas_not_void: deltas /= Void
310          deltas_valid: deltas.count <= max_ascii_character_value + 1          deltas_valid: deltas.count = max_ascii_character_value + 1
311    
312  end  end

Legend:
Removed from v.91476  
changed lines
  Added in v.91477

  ViewVC Help
Powered by ViewVC 1.1.23