wasCSharpSQLite – Blame information for rev

Subversion Repositories:
Rev:
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 }