Mercurial > octave-nkf

comparison src/DLD-FUNCTIONS/strfind.cc @ 11586:12df7854fa7c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
strip trailing whitespace from source files
author John W. Eaton <jwe@octave.org>
date Thu, 20 Jan 2011 17:24:59 -0500
parents 7d6d8c1e471f
children 7a5aacf65f81
comparison
equal deleted inserted replaced
11585:1473d0cf86d2 11586:12df7854fa7c
41 #define ORD(ch) static_cast<unsigned char>(ch) 41 #define ORD(ch) static_cast<unsigned char>(ch)
42 #define TABSIZE (UCHAR_MAX + 1) 42 #define TABSIZE (UCHAR_MAX + 1)
43 43
44 // This is the quick search algorithm, as described at 44 // This is the quick search algorithm, as described at
45 // http://www-igm.univ-mlv.fr/~lecroq/string/node19.html 45 // http://www-igm.univ-mlv.fr/~lecroq/string/node19.html
46 static void 46 static void
47 qs_preprocess (const Array<char>& needle, 47 qs_preprocess (const Array<char>& needle,
48 octave_idx_type table[TABSIZE]) 48 octave_idx_type table[TABSIZE])
49 { 49 {
50 const char *x = needle.data (); 50 const char *x = needle.data ();
51 octave_idx_type m = needle.numel (); 51 octave_idx_type m = needle.numel ();
55 for (octave_idx_type i = 0; i < m; i++) 55 for (octave_idx_type i = 0; i < m; i++)
56 table[ORD(x[i])] = m - i; 56 table[ORD(x[i])] = m - i;
57 } 57 }
58 58
59 59
60 static Array<octave_idx_type> 60 static Array<octave_idx_type>
61 qs_search (const Array<char>& needle, 61 qs_search (const Array<char>& needle,
62 const Array<char>& haystack, 62 const Array<char>& haystack,
63 const octave_idx_type table[TABSIZE], 63 const octave_idx_type table[TABSIZE],
64 bool overlaps = true) 64 bool overlaps = true)
65 { 65 {
105 // General case. 105 // General case.
106 octave_idx_type j = 0; 106 octave_idx_type j = 0;
107 107
108 if (overlaps) 108 if (overlaps)
109 { 109 {
110 while (j < n - m) 110 while (j < n - m)
111 { 111 {
112 if (std::equal (x, x + m, y + j)) 112 if (std::equal (x, x + m, y + j))
113 accum.push_back (j); 113 accum.push_back (j);
114 j += table[ORD(y[j + m])]; 114 j += table[ORD(y[j + m])];
115 } 115 }
116 } 116 }
117 else 117 else
118 { 118 {
119 while (j < n - m) 119 while (j < n - m)
120 { 120 {
121 if (std::equal (x, x + m, y + j)) 121 if (std::equal (x, x + m, y + j))
122 { 122 {
123 accum.push_back (j); 123 accum.push_back (j);
124 j += m; 124 j += m;
134 134
135 octave_idx_type nmatch = accum.size (); 135 octave_idx_type nmatch = accum.size ();
136 octave_idx_type one = 1; 136 octave_idx_type one = 1;
137 Array<octave_idx_type> result (dim_vector (std::min (one, nmatch), nmatch)); 137 Array<octave_idx_type> result (dim_vector (std::min (one, nmatch), nmatch));
138 octave_idx_type k = 0; 138 octave_idx_type k = 0;
139 for (std::deque<octave_idx_type>::const_iterator iter = accum.begin (); 139 for (std::deque<octave_idx_type>::const_iterator iter = accum.begin ();
140 iter != accum.end (); iter++) 140 iter != accum.end (); iter++)
141 { 141 {
142 result.xelem (k++) = *iter; 142 result.xelem (k++) = *iter;
143 } 143 }
144 144
205 Array<char> needle = argpat.char_array_value (); 205 Array<char> needle = argpat.char_array_value ();
206 OCTAVE_LOCAL_BUFFER (octave_idx_type, table, UCHAR_MAX); 206 OCTAVE_LOCAL_BUFFER (octave_idx_type, table, UCHAR_MAX);
207 qs_preprocess (needle, table); 207 qs_preprocess (needle, table);
208 208
209 if (argstr.is_string ()) 209 if (argstr.is_string ())
210 retval = octave_value (qs_search (needle, argstr.char_array_value (), 210 retval = octave_value (qs_search (needle, argstr.char_array_value (),
211 table, overlaps), 211 table, overlaps),
212 true, true); 212 true, true);
213 else if (argstr.is_cell ()) 213 else if (argstr.is_cell ())
214 { 214 {
215 const Cell argsc = argstr.cell_value (); 215 const Cell argsc = argstr.cell_value ();
216 Cell retc (argsc.dims ()); 216 Cell retc (argsc.dims ());
218 218
219 for (octave_idx_type i = 0; i < ns; i++) 219 for (octave_idx_type i = 0; i < ns; i++)
220 { 220 {
221 octave_value argse = argsc(i); 221 octave_value argse = argsc(i);
222 if (argse.is_string ()) 222 if (argse.is_string ())
223 retc(i) = octave_value (qs_search (needle, argse.char_array_value (), 223 retc(i) = octave_value (qs_search (needle, argse.char_array_value (),
224 table, overlaps), 224 table, overlaps),
225 true, true); 225 true, true);
226 else 226 else
227 { 227 {
228 error ("strfind: each element of CELLSTR must be a string"); 228 error ("strfind: each element of CELLSTR must be a string");
229 break; 229 break;
260 260
261 */ 261 */
262 262
263 static Array<char> 263 static Array<char>
264 qs_replace (const Array<char>& str, const Array<char>& pat, 264 qs_replace (const Array<char>& str, const Array<char>& pat,
265 const Array<char>& rep, 265 const Array<char>& rep,
266 const octave_idx_type table[TABSIZE], 266 const octave_idx_type table[TABSIZE],
267 bool overlaps = true) 267 bool overlaps = true)
268 { 268 {
269 Array<char> ret = str; 269 Array<char> ret = str;
270 270