wasCSharpSQLite – Blame information for rev

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /*
2 * LsearchCmd.java
3 *
4 * Copyright (c) 1997 Cornell University.
5 * Copyright (c) 1997 Sun Microsystems, Inc.
6 * Copyright (c) 1998-1999 by Scriptics Corporation.
7 * Copyright (c) 2000 Christian Krone.
8 *
9 * See the file "license.terms" for information on usage and
10 * redistribution of this file, and for a DISCLAIMER OF ALL
11 * WARRANTIES.
12 *
13 * Included in SQLite3 port to C# for use in testharness only; 2008 Noah B Hart
14 *
15 * RCS @(#) $Id: LsearchCmd.java,v 1.2 2000/08/21 04:12:51 mo Exp $
16 *
17 */
18 using System;
19 namespace tcl.lang
20 {
21  
22 /*
23 * This class implements the built-in "lsearch" command in Tcl.
24 */
25  
26 class LsearchCmd : Command
27 {
28  
29 private static readonly string[] options = new string[] { "-ascii", "-decreasing", "-dictionary", "-exact", "-increasing", "-integer", "-glob", "-real", "-regexp", "-sorted" };
30 internal const int LSEARCH_ASCII = 0;
31 internal const int LSEARCH_DECREASING = 1;
32 internal const int LSEARCH_DICTIONARY = 2;
33 internal const int LSEARCH_EXACT = 3;
34 internal const int LSEARCH_INCREASING = 4;
35 internal const int LSEARCH_INTEGER = 5;
36 internal const int LSEARCH_GLOB = 6;
37 internal const int LSEARCH_REAL = 7;
38 internal const int LSEARCH_REGEXP = 8;
39 internal const int LSEARCH_SORTED = 9;
40  
41 internal const int ASCII = 0;
42 internal const int DICTIONARY = 1;
43 internal const int INTEGER = 2;
44 internal const int REAL = 3;
45  
46 internal const int EXACT = 0;
47 internal const int GLOB = 1;
48 internal const int REGEXP = 2;
49 internal const int SORTED = 3;
50  
51 /*
52 *-----------------------------------------------------------------------------
53 *
54 * cmdProc --
55 *
56 * This procedure is invoked to process the "lsearch" Tcl command.
57 * See the user documentation for details on what it does.
58 *
59 * Results:
60 * None.
61 *
62 * Side effects:
63 * See the user documentation.
64 *
65 *-----------------------------------------------------------------------------
66 */
67  
68 public TCL.CompletionCode cmdProc( Interp interp, TclObject[] objv )
69 {
70 int mode = GLOB;
71 int dataType = ASCII;
72 bool isIncreasing = true;
73 TclObject pattern;
74 TclObject list;
75  
76 if ( objv.Length < 3 )
77 {
78 throw new TclNumArgsException( interp, 1, objv, "?options? list pattern" );
79 }
80  
81 for ( int i = 1; i < objv.Length - 2; i++ )
82 {
83 switch ( TclIndex.get( interp, objv[i], options, "option", 0 ) )
84 {
85  
86 case LSEARCH_ASCII:
87 dataType = ASCII;
88 break;
89  
90 case LSEARCH_DECREASING:
91 isIncreasing = false;
92 break;
93  
94 case LSEARCH_DICTIONARY:
95 dataType = DICTIONARY;
96 break;
97  
98 case LSEARCH_EXACT:
99 mode = EXACT;
100 break;
101  
102 case LSEARCH_INCREASING:
103 isIncreasing = true;
104 break;
105  
106 case LSEARCH_INTEGER:
107 dataType = INTEGER;
108 break;
109  
110 case LSEARCH_GLOB:
111 mode = GLOB;
112 break;
113  
114 case LSEARCH_REAL:
115 dataType = REAL;
116 break;
117  
118 case LSEARCH_REGEXP:
119 mode = REGEXP;
120 break;
121  
122 case LSEARCH_SORTED:
123 mode = SORTED;
124 break;
125 }
126 }
127  
128 // Make sure the list argument is a list object and get its length and
129 // a pointer to its array of element pointers.
130  
131 TclObject[] listv = TclList.getElements( interp, objv[objv.Length - 2] );
132  
133 TclObject patObj = objv[objv.Length - 1];
134 string patternBytes = null;
135 int patInt = 0;
136 double patDouble = 0.0;
137 int length = 0;
138 if ( mode == EXACT || mode == SORTED )
139 {
140 switch ( dataType )
141 {
142  
143 case ASCII:
144 case DICTIONARY:
145  
146 patternBytes = patObj.ToString();
147 length = patternBytes.Length;
148 break;
149  
150 case INTEGER:
151 patInt = TclInteger.get( interp, patObj );
152 break;
153  
154 case REAL:
155 patDouble = TclDouble.get( interp, patObj );
156 break;
157 }
158 }
159 else
160 {
161  
162 patternBytes = patObj.ToString();
163 length = patternBytes.Length;
164 }
165  
166 // Set default index value to -1, indicating failure; if we find the
167 // item in the course of our search, index will be set to the correct
168 // value.
169  
170 int index = -1;
171 if ( mode == SORTED )
172 {
173 // If the data is sorted, we can do a more intelligent search.
174 int match = 0;
175 int lower = -1;
176 int upper = listv.Length;
177 while ( lower + 1 != upper )
178 {
179 int i = ( lower + upper ) / 2;
180 switch ( dataType )
181 {
182  
183 case ASCII:
184 {
185  
186 string bytes = listv[i].ToString();
187 match = patternBytes.CompareTo( bytes );
188 break;
189 }
190  
191 case DICTIONARY:
192 {
193  
194 string bytes = listv[i].ToString();
195 match = DictionaryCompare( patternBytes, bytes );
196 break;
197 }
198  
199 case INTEGER:
200 {
201 int objInt = TclInteger.get( interp, listv[i] );
202 if ( patInt == objInt )
203 {
204 match = 0;
205 }
206 else if ( patInt < objInt )
207 {
208 match = -1;
209 }
210 else
211 {
212 match = 1;
213 }
214 break;
215 }
216  
217 case REAL:
218 {
219 double objDouble = TclDouble.get( interp, listv[i] );
220 if ( patDouble == objDouble )
221 {
222 match = 0;
223 }
224 else if ( patDouble < objDouble )
225 {
226 match = -1;
227 }
228 else
229 {
230 match = 1;
231 }
232 break;
233 }
234 }
235 if ( match == 0 )
236 {
237  
238 // Normally, binary search is written to stop when it
239 // finds a match. If there are duplicates of an element in
240 // the list, our first match might not be the first occurance.
241 // Consider: 0 0 0 1 1 1 2 2 2
242 // To maintain consistancy with standard lsearch semantics,
243 // we must find the leftmost occurance of the pattern in the
244 // list. Thus we don't just stop searching here. This
245 // variation means that a search always makes log n
246 // comparisons (normal binary search might "get lucky" with
247 // an early comparison).
248  
249 index = i;
250 upper = i;
251 }
252 else if ( match > 0 )
253 {
254 if ( isIncreasing )
255 {
256 lower = i;
257 }
258 else
259 {
260 upper = i;
261 }
262 }
263 else
264 {
265 if ( isIncreasing )
266 {
267 upper = i;
268 }
269 else
270 {
271 lower = i;
272 }
273 }
274 }
275 }
276 else
277 {
278 for ( int i = 0; i < listv.Length; i++ )
279 {
280 bool match = false;
281 switch ( mode )
282 {
283  
284 case SORTED:
285 case EXACT:
286 {
287 switch ( dataType )
288 {
289  
290 case ASCII:
291 {
292  
293 string bytes = listv[i].ToString();
294 int elemLen = bytes.Length;
295 if ( length == elemLen )
296 {
297 match = bytes.Equals( patternBytes );
298 }
299 break;
300 }
301  
302 case DICTIONARY:
303 {
304  
305 string bytes = listv[i].ToString();
306 match = ( DictionaryCompare( bytes, patternBytes ) == 0 );
307 break;
308 }
309  
310 case INTEGER:
311 {
312 int objInt = TclInteger.get( interp, listv[i] );
313 match = ( objInt == patInt );
314 break;
315 }
316  
317 case REAL:
318 {
319 double objDouble = TclDouble.get( interp, listv[i] );
320 match = ( objDouble == patDouble );
321 break;
322 }
323 }
324 break;
325 }
326  
327 case GLOB:
328 {
329  
330 match = Util.stringMatch( listv[i].ToString(), patternBytes );
331 break;
332 }
333  
334 case REGEXP:
335 {
336  
337 match = Util.regExpMatch( interp, listv[i].ToString(), patObj );
338 break;
339 }
340 }
341 if ( match )
342 {
343 index = i;
344 break;
345 }
346 }
347 }
348 interp.setResult( index );
349 return TCL.CompletionCode.RETURN;
350 }
351  
352 /*
353 *----------------------------------------------------------------------
354 *
355 * DictionaryCompare -> dictionaryCompare
356 *
357 * This function compares two strings as if they were being used in
358 * an index or card catalog. The case of alphabetic characters is
359 * ignored, except to break ties. Thus "B" comes before "b" but
360 * after "a". Also, integers embedded in the strings compare in
361 * numerical order. In other words, "x10y" comes after "x9y", not
362 * before it as it would when using strcmp().
363 *
364 * Results:
365 * A negative result means that the first element comes before the
366 * second, and a positive result means that the second element
367 * should come first. A result of zero means the two elements
368 * are equal and it doesn't matter which comes first.
369 *
370 * Side effects:
371 * None.
372 *
373 *----------------------------------------------------------------------
374 */
375  
376 private static int DictionaryCompare( string left, string right )
377 // The strings to compare
378 {
379 char[] leftArr = left.ToCharArray();
380 char[] rightArr = right.ToCharArray();
381 char leftChar, rightChar, leftLower, rightLower;
382 int lInd = 0;
383 int rInd = 0;
384 int diff;
385 int secondaryDiff = 0;
386  
387 while ( true )
388 {
389 if ( ( rInd < rightArr.Length ) && ( System.Char.IsDigit( rightArr[rInd] ) ) && ( lInd < leftArr.Length ) && ( System.Char.IsDigit( leftArr[lInd] ) ) )
390 {
391 // There are decimal numbers embedded in the two
392 // strings. Compare them as numbers, rather than
393 // strings. If one number has more leading zeros than
394 // the other, the number with more leading zeros sorts
395 // later, but only as a secondary choice.
396  
397 int zeros = 0;
398 while ( ( rightArr[rInd] == '0' ) && ( rInd + 1 < rightArr.Length ) && ( System.Char.IsDigit( rightArr[rInd + 1] ) ) )
399 {
400 rInd++;
401 zeros--;
402 }
403 while ( ( leftArr[lInd] == '0' ) && ( lInd + 1 < leftArr.Length ) && ( System.Char.IsDigit( leftArr[lInd + 1] ) ) )
404 {
405 lInd++;
406 zeros++;
407 }
408 if ( secondaryDiff == 0 )
409 {
410 secondaryDiff = zeros;
411 }
412  
413 // The code below compares the numbers in the two
414 // strings without ever converting them to integers. It
415 // does this by first comparing the lengths of the
416 // numbers and then comparing the digit values.
417  
418 diff = 0;
419 while ( true )
420 {
421 if ( ( diff == 0 ) && ( lInd < leftArr.Length ) && ( rInd < rightArr.Length ) )
422 {
423 diff = leftArr[lInd] - rightArr[rInd];
424 }
425 rInd++;
426 lInd++;
427 if ( rInd >= rightArr.Length || !System.Char.IsDigit( rightArr[rInd] ) )
428 {
429 if ( lInd < leftArr.Length && System.Char.IsDigit( leftArr[lInd] ) )
430 {
431 return 1;
432 }
433 else
434 {
435 // The two numbers have the same length. See
436 // if their values are different.
437  
438 if ( diff != 0 )
439 {
440 return diff;
441 }
442 break;
443 }
444 }
445 else if ( lInd >= leftArr.Length || !System.Char.IsDigit( leftArr[lInd] ) )
446 {
447 return -1;
448 }
449 }
450 continue;
451 }
452  
453 // Convert character to Unicode for comparison purposes. If either
454 // string is at the terminating null, do a byte-wise comparison and
455 // bail out immediately.
456  
457 if ( ( lInd < leftArr.Length ) && ( rInd < rightArr.Length ) )
458 {
459  
460 // Convert both chars to lower for the comparison, because
461 // dictionary sorts are case insensitve. Covert to lower, not
462 // upper, so chars between Z and a will sort before A (where most
463 // other interesting punctuations occur)
464  
465 leftChar = leftArr[lInd++];
466 rightChar = rightArr[rInd++];
467 leftLower = System.Char.ToLower( leftChar );
468 rightLower = System.Char.ToLower( rightChar );
469 }
470 else if ( lInd < leftArr.Length )
471 {
472 diff = -rightArr[rInd];
473 break;
474 }
475 else if ( rInd < rightArr.Length )
476 {
477 diff = leftArr[lInd];
478 break;
479 }
480 else
481 {
482 diff = 0;
483 break;
484 }
485  
486 diff = leftLower - rightLower;
487 if ( diff != 0 )
488 {
489 return diff;
490 }
491 else if ( secondaryDiff == 0 )
492 {
493 if ( System.Char.IsUpper( leftChar ) && System.Char.IsLower( rightChar ) )
494 {
495 secondaryDiff = -1;
496 }
497 else if ( System.Char.IsUpper( rightChar ) && System.Char.IsLower( leftChar ) )
498 {
499 secondaryDiff = 1;
500 }
501 }
502 }
503 if ( diff == 0 )
504 {
505 diff = secondaryDiff;
506 }
507 return diff;
508 }
509 } // end LsearchCmd
510 }