wasCSharpSQLite – Blame information for rev
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | office | 1 | /* |
2 | * QSort.java |
||
3 | * |
||
4 | * Copyright (c) 1997 Cornell University. |
||
5 | * Copyright (c) 1997 Sun Microsystems, Inc. |
||
6 | * |
||
7 | * See the file "license.terms" for information on usage and |
||
8 | * redistribution of this file, and for a DISCLAIMER OF ALL |
||
9 | * WARRANTIES. |
||
10 | * |
||
11 | * Included in SQLite3 port to C# for use in testharness only; 2008 Noah B Hart |
||
12 | * |
||
13 | * RCS @(#) $Id: QSort.java,v 1.2 1999/05/09 01:14:07 dejong Exp $ |
||
14 | * |
||
15 | */ |
||
16 | using System.Text; |
||
17 | namespace tcl.lang |
||
18 | { |
||
19 | |||
20 | /* |
||
21 | * This file is adapted from the JDK 1.0 QSortAlgorithm.java demo program. |
||
22 | * Original copyright notice is preserveed below. |
||
23 | * |
||
24 | * @(#)QSortAlgorithm.java 1.3 29 Feb 1996 James Gosling |
||
25 | * |
||
26 | * Copyright (c) 1994-1996 Sun Microsystems, Inc. All Rights Reserved. |
||
27 | * |
||
28 | * Permission to use, copy, modify, and distribute this software |
||
29 | * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and |
||
30 | * without fee is hereby granted. |
||
31 | * Please refer to the file http://www.javasoft.com/copy_trademarks.html |
||
32 | * for further important copyright and trademark information and to |
||
33 | * http://www.javasoft.com/licensing.html for further important |
||
34 | * licensing information for the Java (tm) Technology. |
||
35 | * |
||
36 | * SUN MAKES NO REPRESENTATIONS OR WARRANTIES. ABOUT THE SUITABILITY OF |
||
37 | * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED |
||
38 | * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A |
||
39 | * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR |
||
40 | * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR |
||
41 | * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. |
||
42 | * |
||
43 | * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE |
||
44 | * CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE |
||
45 | * PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT |
||
46 | * NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE |
||
47 | * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE |
||
48 | * SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE |
||
49 | * PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES"). SUN |
||
50 | * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR |
||
51 | * HIGH RISK ACTIVITIES. |
||
52 | */ |
||
53 | |||
54 | /// <summary> Sorts an array of TclObjects.</summary> |
||
55 | sealed class QSort |
||
56 | { |
||
57 | internal const int ASCII = 0; |
||
58 | internal const int INTEGER = 1; |
||
59 | internal const int REAL = 2; |
||
60 | internal const int COMMAND = 3; |
||
61 | internal const int DICTIONARY = 4; |
||
62 | |||
63 | // Data used during sort. |
||
64 | |||
65 | private int sortMode; |
||
66 | private int sortIndex; |
||
67 | private bool sortIncreasing; |
||
68 | private string sortCommand; |
||
69 | private Interp sortInterp; |
||
70 | |||
71 | /// <summary> This is a generic version of C.A.R Hoare's Quick Sort |
||
72 | /// algorithm. This will handle arrays that are already |
||
73 | /// sorted, and arrays with duplicate keys.<BR> |
||
74 | /// |
||
75 | /// If you think of a one dimensional array as going from |
||
76 | /// the lowest index on the left to the highest index on the right |
||
77 | /// then the parameters to this function are lowest index or |
||
78 | /// left and highest index or right. The first time you call |
||
79 | /// this function it will be with the parameters 0, a.length - 1. |
||
80 | /// |
||
81 | /// </summary> |
||
82 | /// <param name="a"> an integer array |
||
83 | /// </param> |
||
84 | /// <param name="lo0"> left boundary of array partition |
||
85 | /// </param> |
||
86 | /// <param name="hi0"> right boundary of array partition |
||
87 | /// </param> |
||
88 | private void quickSort( TclObject[] a, int lo0, int hi0 ) |
||
89 | { |
||
90 | int lo = lo0; |
||
91 | int hi = hi0; |
||
92 | TclObject mid; |
||
93 | |||
94 | if ( hi0 > lo0 ) |
||
95 | { |
||
96 | // Arbitrarily establishing partition element as the midpoint of |
||
97 | // the array. |
||
98 | mid = a[( lo0 + hi0 ) / 2]; |
||
99 | |||
100 | // loop through the array until indices cross |
||
101 | while ( lo <= hi ) |
||
102 | { |
||
103 | // find the first element that is greater than or equal to |
||
104 | // the partition element starting from the left Index. |
||
105 | |||
106 | while ( ( lo < hi0 ) && ( compare( a[lo], mid ) < 0 ) ) |
||
107 | { |
||
108 | ++lo; |
||
109 | } |
||
110 | |||
111 | // find an element that is smaller than or equal to |
||
112 | // the partition element starting from the right Index. |
||
113 | |||
114 | while ( ( hi > lo0 ) && ( compare( a[hi], mid ) > 0 ) ) |
||
115 | { |
||
116 | --hi; |
||
117 | } |
||
118 | |||
119 | // if the indexes have not crossed, swap |
||
120 | if ( lo <= hi ) |
||
121 | { |
||
122 | swap( a, lo, hi ); |
||
123 | ++lo; |
||
124 | --hi; |
||
125 | } |
||
126 | } |
||
127 | |||
128 | // If the right index has not reached the left side of array |
||
129 | // must now sort the left partition. |
||
130 | |||
131 | if ( lo0 < hi ) |
||
132 | { |
||
133 | quickSort( a, lo0, hi ); |
||
134 | } |
||
135 | |||
136 | // If the left index has not reached the right side of array |
||
137 | // must now sort the right partition. |
||
138 | |||
139 | if ( lo < hi0 ) |
||
140 | { |
||
141 | quickSort( a, lo, hi0 ); |
||
142 | } |
||
143 | } |
||
144 | } |
||
145 | |||
146 | /// <summary> Swaps two items in the array. |
||
147 | /// |
||
148 | /// </summary> |
||
149 | /// <param name="a">the array. |
||
150 | /// </param> |
||
151 | /// <param name="i">index of first item. |
||
152 | /// </param> |
||
153 | /// <param name="j">index of first item. |
||
154 | /// </param> |
||
155 | private static void swap( TclObject[] a, int i, int j ) |
||
156 | { |
||
157 | TclObject T; |
||
158 | T = a[i]; |
||
159 | a[i] = a[j]; |
||
160 | a[j] = T; |
||
161 | } |
||
162 | |||
163 | /// <summary> Starts the quick sort with the given parameters. |
||
164 | /// |
||
165 | /// </summary> |
||
166 | /// <param name="interp">if cmd is specified, it is evaluated inside this |
||
167 | /// interp. |
||
168 | /// </param> |
||
169 | /// <param name="a">the array of TclObject's to sort. |
||
170 | /// </param> |
||
171 | /// <param name="mode">the sortng mode. |
||
172 | /// </param> |
||
173 | /// <param name="increasing">true if the sorted array should be in increasing |
||
174 | /// order. |
||
175 | /// </param> |
||
176 | /// <param name="cmd">the command to use for comparing items. It is used only |
||
177 | /// if sortMode is COMMAND. |
||
178 | /// </param> |
||
179 | /// <param name="unique">true if the result should contain no duplicates. |
||
180 | /// </param> |
||
181 | /// <returns> the length of the sorted array. This length may be different |
||
182 | /// from the length if array a due to the unique option. |
||
183 | /// </returns> |
||
184 | /// <exception cref=""> TclException if an error occurs during sorting. |
||
185 | /// </exception> |
||
186 | internal int sort( Interp interp, TclObject[] a, int mode, int index, bool increasing, string cmd, bool unique ) |
||
187 | { |
||
188 | sortInterp = interp; |
||
189 | sortMode = mode; |
||
190 | sortIndex = index; |
||
191 | sortIncreasing = increasing; |
||
192 | sortCommand = cmd; |
||
193 | quickSort( a, 0, a.Length - 1 ); |
||
194 | if ( !unique ) |
||
195 | { |
||
196 | return a.Length; |
||
197 | } |
||
198 | |||
199 | int uniqueIx = 1; |
||
200 | for ( int ix = 1; ix < a.Length; ix++ ) |
||
201 | { |
||
202 | if ( compare( a[ix], a[uniqueIx - 1] ) == 0 ) |
||
203 | { |
||
204 | a[ix].release(); |
||
205 | } |
||
206 | else |
||
207 | { |
||
208 | if ( ix != uniqueIx ) |
||
209 | { |
||
210 | a[uniqueIx] = a[ix]; |
||
211 | a[uniqueIx].preserve(); |
||
212 | } |
||
213 | uniqueIx++; |
||
214 | } |
||
215 | } |
||
216 | return uniqueIx; |
||
217 | |||
218 | } |
||
219 | |||
220 | /// <summary> Compares the order of two items in the array. |
||
221 | /// |
||
222 | /// </summary> |
||
223 | /// <param name="obj1">first item. |
||
224 | /// </param> |
||
225 | /// <param name="obj2">second item. |
||
226 | /// </param> |
||
227 | /// <returns> 0 if they are equal, 1 if obj1 > obj2, -1 otherwise. |
||
228 | /// |
||
229 | /// </returns> |
||
230 | /// <exception cref=""> TclException if an error occurs during sorting. |
||
231 | /// </exception> |
||
232 | private int compare( TclObject obj1, TclObject obj2 ) |
||
233 | { |
||
234 | |||
235 | int index; |
||
236 | int code = 0; |
||
237 | |||
238 | if ( sortIndex != -1 ) |
||
239 | { |
||
240 | // The "-index" option was specified. Treat each object as a |
||
241 | // list, extract the requested element from each list, and |
||
242 | // compare the elements, not the lists. The special index "end" |
||
243 | // is signaled here with a negative index (other than -1). |
||
244 | |||
245 | TclObject obj; |
||
246 | if ( sortIndex < -1 ) |
||
247 | { |
||
248 | index = TclList.getLength( sortInterp, obj1 ) - 1; |
||
249 | } |
||
250 | else |
||
251 | { |
||
252 | index = sortIndex; |
||
253 | } |
||
254 | |||
255 | obj = TclList.index( sortInterp, obj1, index ); |
||
256 | if ( obj == null ) |
||
257 | { |
||
258 | |||
259 | throw new TclException( sortInterp, "element " + index + " missing from sublist \"" + obj1 + "\"" ); |
||
260 | } |
||
261 | obj1 = obj; |
||
262 | |||
263 | if ( sortIndex < -1 ) |
||
264 | { |
||
265 | index = TclList.getLength( sortInterp, obj2 ) - 1; |
||
266 | } |
||
267 | else |
||
268 | { |
||
269 | index = sortIndex; |
||
270 | } |
||
271 | |||
272 | obj = TclList.index( sortInterp, obj2, index ); |
||
273 | if ( obj == null ) |
||
274 | { |
||
275 | |||
276 | throw new TclException( sortInterp, "element " + index + " missing from sublist \"" + obj2 + "\"" ); |
||
277 | } |
||
278 | obj2 = obj; |
||
279 | } |
||
280 | |||
281 | switch ( sortMode ) |
||
282 | { |
||
283 | |||
284 | case ASCII: |
||
285 | // ATK C# CompareTo use option |
||
286 | // similar to -dictionary but a > A |
||
287 | code = System.Globalization.CultureInfo.InvariantCulture.CompareInfo.Compare( obj1.ToString(), obj2.ToString(), System.Globalization.CompareOptions.Ordinal ); |
||
288 | // code = obj1.ToString().CompareTo(obj2.ToString()); |
||
289 | break; |
||
290 | |||
291 | case DICTIONARY: |
||
292 | |||
293 | code = doDictionary( obj1.ToString(), obj2.ToString() ); |
||
294 | break; |
||
295 | |||
296 | case INTEGER: |
||
297 | try |
||
298 | { |
||
299 | int int1 = TclInteger.get( sortInterp, obj1 ); |
||
300 | int int2 = TclInteger.get( sortInterp, obj2 ); |
||
301 | |||
302 | if ( int1 > int2 ) |
||
303 | { |
||
304 | code = 1; |
||
305 | } |
||
306 | else if ( int2 > int1 ) |
||
307 | { |
||
308 | code = -1; |
||
309 | } |
||
310 | } |
||
311 | catch ( TclException e1 ) |
||
312 | { |
||
313 | sortInterp.addErrorInfo( "\n (converting list element from string to integer)" ); |
||
314 | throw e1; |
||
315 | } |
||
316 | break; |
||
317 | |||
318 | case REAL: |
||
319 | try |
||
320 | { |
||
321 | double f1 = TclDouble.get( sortInterp, obj1 ); |
||
322 | double f2 = TclDouble.get( sortInterp, obj2 ); |
||
323 | |||
324 | if ( f1 > f2 ) |
||
325 | { |
||
326 | code = 1; |
||
327 | } |
||
328 | else if ( f2 > f1 ) |
||
329 | { |
||
330 | code = -1; |
||
331 | } |
||
332 | } |
||
333 | catch ( TclException e2 ) |
||
334 | { |
||
335 | sortInterp.addErrorInfo( "\n (converting list element from string to real)" ); |
||
336 | throw e2; |
||
337 | } |
||
338 | break; |
||
339 | |||
340 | case COMMAND: |
||
341 | StringBuilder sbuf = new StringBuilder( sortCommand ); |
||
342 | |||
343 | Util.appendElement( sortInterp, sbuf, obj1.ToString() ); |
||
344 | |||
345 | Util.appendElement( sortInterp, sbuf, obj2.ToString() ); |
||
346 | try |
||
347 | { |
||
348 | sortInterp.eval( sbuf.ToString(), 0 ); |
||
349 | } |
||
350 | catch ( TclException e3 ) |
||
351 | { |
||
352 | sortInterp.addErrorInfo( "\n (user-defined comparison command)" ); |
||
353 | throw e3; |
||
354 | } |
||
355 | |||
356 | try |
||
357 | { |
||
358 | code = TclInteger.get( sortInterp, sortInterp.getResult() ); |
||
359 | } |
||
360 | catch ( TclException e ) |
||
361 | { |
||
362 | sortInterp.resetResult(); |
||
363 | TclException e4 = new TclException( sortInterp, "comparison command returned non-numeric result" ); |
||
364 | throw e4; |
||
365 | } |
||
366 | break; |
||
367 | |||
368 | |||
369 | default: |
||
370 | |||
371 | throw new TclRuntimeError( "Unknown sortMode " + sortMode ); |
||
372 | |||
373 | } |
||
374 | |||
375 | if ( sortIncreasing ) |
||
376 | { |
||
377 | return code; |
||
378 | } |
||
379 | else |
||
380 | { |
||
381 | return -code; |
||
382 | } |
||
383 | } |
||
384 | |||
385 | |||
386 | /// <summary> Compares the order of two strings in "dictionary" order. |
||
387 | /// |
||
388 | /// </summary> |
||
389 | /// <param name="str1">first item. |
||
390 | /// </param> |
||
391 | /// <param name="str2">second item. |
||
392 | /// </param> |
||
393 | /// <returns> 0 if they are equal, 1 if obj1 > obj2, -1 otherwise. |
||
394 | /// </returns> |
||
395 | private int doDictionary( string str1, string str2 ) |
||
396 | { |
||
397 | int diff = 0, zeros; |
||
398 | int secondaryDiff = 0; |
||
399 | |||
400 | bool cont = true; |
||
401 | int i1 = 0, i2 = 0; |
||
402 | int len1 = str1.Length; |
||
403 | int len2 = str2.Length; |
||
404 | |||
405 | |||
406 | while ( cont ) |
||
407 | { |
||
408 | if ( i1 >= len1 || i2 >= len2 ) |
||
409 | { |
||
410 | break; |
||
411 | } |
||
412 | |||
413 | if ( System.Char.IsDigit( str2[i2] ) && System.Char.IsDigit( str1[i1] ) ) |
||
414 | { |
||
415 | |||
416 | // There are decimal numbers embedded in the two |
||
417 | // strings. Compare them as numbers, rather than |
||
418 | // strings. If one number has more leading zeros than |
||
419 | // the other, the number with more leading zeros sorts |
||
420 | // later, but only as a secondary choice. |
||
421 | |||
422 | zeros = 0; |
||
423 | while ( ( i2 < ( len2 - 1 ) ) && ( str2[i2] == '0' ) ) |
||
424 | { |
||
425 | i2++; |
||
426 | zeros--; |
||
427 | } |
||
428 | while ( ( i1 < ( len1 - 1 ) ) && ( str1[i1] == '0' ) ) |
||
429 | { |
||
430 | i1++; |
||
431 | zeros++; |
||
432 | } |
||
433 | if ( secondaryDiff == 0 ) |
||
434 | { |
||
435 | secondaryDiff = zeros; |
||
436 | } |
||
437 | |||
438 | |||
439 | // The code below compares the numbers in the two |
||
440 | // strings without ever converting them to integers. It |
||
441 | // does this by first comparing the lengths of the |
||
442 | // numbers and then comparing the digit values. |
||
443 | |||
444 | diff = 0; |
||
445 | while ( true ) |
||
446 | { |
||
447 | |||
448 | if ( i1 >= len1 || i2 >= len2 ) |
||
449 | { |
||
450 | cont = false; |
||
451 | break; |
||
452 | } |
||
453 | if ( diff == 0 ) |
||
454 | { |
||
455 | diff = str1[i1] - str2[i2]; |
||
456 | } |
||
457 | i1++; |
||
458 | i2++; |
||
459 | if ( i1 >= len1 || i2 >= len2 ) |
||
460 | { |
||
461 | cont = false; |
||
462 | break; |
||
463 | } |
||
464 | |||
465 | |||
466 | if ( !System.Char.IsDigit( str2[i2] ) ) |
||
467 | { |
||
468 | if ( System.Char.IsDigit( str1[i1] ) ) |
||
469 | { |
||
470 | return 1; |
||
471 | } |
||
472 | else |
||
473 | { |
||
474 | if ( diff != 0 ) |
||
475 | { |
||
476 | return diff; |
||
477 | } |
||
478 | break; |
||
479 | } |
||
480 | } |
||
481 | else if ( !System.Char.IsDigit( str1[i1] ) ) |
||
482 | { |
||
483 | return -1; |
||
484 | } |
||
485 | } |
||
486 | continue; |
||
487 | } |
||
488 | diff = str1[i1] - str2[i2]; |
||
489 | if ( diff != 0 ) |
||
490 | { |
||
491 | if ( System.Char.IsUpper( str1[i1] ) && System.Char.IsLower( str2[i2] ) ) |
||
492 | { |
||
493 | diff = System.Char.ToLower( str1[i1] ) - str2[i2]; |
||
494 | if ( diff != 0 ) |
||
495 | { |
||
496 | return diff; |
||
497 | } |
||
498 | else if ( secondaryDiff == 0 ) |
||
499 | { |
||
500 | secondaryDiff = -1; |
||
501 | } |
||
502 | } |
||
503 | else if ( System.Char.IsUpper( str2[i2] ) && System.Char.IsLower( str1[i1] ) ) |
||
504 | { |
||
505 | diff = str1[i1] - System.Char.ToLower( str2[i2] ); |
||
506 | if ( diff != 0 ) |
||
507 | { |
||
508 | return diff; |
||
509 | } |
||
510 | else if ( secondaryDiff == 0 ) |
||
511 | { |
||
512 | secondaryDiff = 1; |
||
513 | } |
||
514 | } |
||
515 | else |
||
516 | { |
||
517 | return diff; |
||
518 | } |
||
519 | } |
||
520 | i1++; |
||
521 | i2++; |
||
522 | } |
||
523 | |||
524 | if ( i1 >= len1 && i2 < len2 ) |
||
525 | { |
||
526 | if ( !System.Char.IsDigit( str2[i2] ) ) |
||
527 | { |
||
528 | return 1; |
||
529 | } |
||
530 | else |
||
531 | { |
||
532 | return -1; |
||
533 | } |
||
534 | } |
||
535 | else if ( i2 >= len2 && i1 < len1 ) |
||
536 | { |
||
537 | if ( !System.Char.IsDigit( str1[i1] ) ) |
||
538 | { |
||
539 | return -1; |
||
540 | } |
||
541 | else |
||
542 | { |
||
543 | return 1; |
||
544 | } |
||
545 | } |
||
546 | |||
547 | if ( diff == 0 ) |
||
548 | { |
||
549 | diff = secondaryDiff; |
||
550 | } |
||
551 | return diff; |
||
552 | } |
||
553 | } |
||
554 | } |