wasCSharpSQLite – Rev 1
?pathlinks?
/*
* QSort.java
*
* Copyright (c) 1997 Cornell University.
* Copyright (c) 1997 Sun Microsystems, Inc.
*
* See the file "license.terms" for information on usage and
* redistribution of this file, and for a DISCLAIMER OF ALL
* WARRANTIES.
*
* Included in SQLite3 port to C# for use in testharness only; 2008 Noah B Hart
*
* RCS @(#) $Id: QSort.java,v 1.2 1999/05/09 01:14:07 dejong Exp $
*
*/
using System.Text;
namespace tcl.lang
{
/*
* This file is adapted from the JDK 1.0 QSortAlgorithm.java demo program.
* Original copyright notice is preserveed below.
*
* @(#)QSortAlgorithm.java 1.3 29 Feb 1996 James Gosling
*
* Copyright (c) 1994-1996 Sun Microsystems, Inc. All Rights Reserved.
*
* Permission to use, copy, modify, and distribute this software
* and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and
* without fee is hereby granted.
* Please refer to the file http://www.javasoft.com/copy_trademarks.html
* for further important copyright and trademark information and to
* http://www.javasoft.com/licensing.html for further important
* licensing information for the Java (tm) Technology.
*
* SUN MAKES NO REPRESENTATIONS OR WARRANTIES. ABOUT THE SUITABILITY OF
* THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
* TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
* PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
*
* THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE
* CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE
* PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT
* NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE
* SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE
* SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE
* PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES"). SUN
* SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR
* HIGH RISK ACTIVITIES.
*/
/// <summary> Sorts an array of TclObjects.</summary>
sealed class QSort
{
internal const int ASCII = 0;
internal const int INTEGER = 1;
internal const int REAL = 2;
internal const int COMMAND = 3;
internal const int DICTIONARY = 4;
// Data used during sort.
private int sortMode;
private int sortIndex;
private bool sortIncreasing;
private string sortCommand;
private Interp sortInterp;
/// <summary> This is a generic version of C.A.R Hoare's Quick Sort
/// algorithm. This will handle arrays that are already
/// sorted, and arrays with duplicate keys.<BR>
///
/// If you think of a one dimensional array as going from
/// the lowest index on the left to the highest index on the right
/// then the parameters to this function are lowest index or
/// left and highest index or right. The first time you call
/// this function it will be with the parameters 0, a.length - 1.
///
/// </summary>
/// <param name="a"> an integer array
/// </param>
/// <param name="lo0"> left boundary of array partition
/// </param>
/// <param name="hi0"> right boundary of array partition
/// </param>
private void quickSort( TclObject[] a, int lo0, int hi0 )
{
int lo = lo0;
int hi = hi0;
TclObject mid;
if ( hi0 > lo0 )
{
// Arbitrarily establishing partition element as the midpoint of
// the array.
mid = a[( lo0 + hi0 ) / 2];
// loop through the array until indices cross
while ( lo <= hi )
{
// find the first element that is greater than or equal to
// the partition element starting from the left Index.
while ( ( lo < hi0 ) && ( compare( a[lo], mid ) < 0 ) )
{
++lo;
}
// find an element that is smaller than or equal to
// the partition element starting from the right Index.
while ( ( hi > lo0 ) && ( compare( a[hi], mid ) > 0 ) )
{
--hi;
}
// if the indexes have not crossed, swap
if ( lo <= hi )
{
swap( a, lo, hi );
++lo;
--hi;
}
}
// If the right index has not reached the left side of array
// must now sort the left partition.
if ( lo0 < hi )
{
quickSort( a, lo0, hi );
}
// If the left index has not reached the right side of array
// must now sort the right partition.
if ( lo < hi0 )
{
quickSort( a, lo, hi0 );
}
}
}
/// <summary> Swaps two items in the array.
///
/// </summary>
/// <param name="a">the array.
/// </param>
/// <param name="i">index of first item.
/// </param>
/// <param name="j">index of first item.
/// </param>
private static void swap( TclObject[] a, int i, int j )
{
TclObject T;
T = a[i];
a[i] = a[j];
a[j] = T;
}
/// <summary> Starts the quick sort with the given parameters.
///
/// </summary>
/// <param name="interp">if cmd is specified, it is evaluated inside this
/// interp.
/// </param>
/// <param name="a">the array of TclObject's to sort.
/// </param>
/// <param name="mode">the sortng mode.
/// </param>
/// <param name="increasing">true if the sorted array should be in increasing
/// order.
/// </param>
/// <param name="cmd">the command to use for comparing items. It is used only
/// if sortMode is COMMAND.
/// </param>
/// <param name="unique">true if the result should contain no duplicates.
/// </param>
/// <returns> the length of the sorted array. This length may be different
/// from the length if array a due to the unique option.
/// </returns>
/// <exception cref=""> TclException if an error occurs during sorting.
/// </exception>
internal int sort( Interp interp, TclObject[] a, int mode, int index, bool increasing, string cmd, bool unique )
{
sortInterp = interp;
sortMode = mode;
sortIndex = index;
sortIncreasing = increasing;
sortCommand = cmd;
quickSort( a, 0, a.Length - 1 );
if ( !unique )
{
return a.Length;
}
int uniqueIx = 1;
for ( int ix = 1; ix < a.Length; ix++ )
{
if ( compare( a[ix], a[uniqueIx - 1] ) == 0 )
{
a[ix].release();
}
else
{
if ( ix != uniqueIx )
{
a[uniqueIx] = a[ix];
a[uniqueIx].preserve();
}
uniqueIx++;
}
}
return uniqueIx;
}
/// <summary> Compares the order of two items in the array.
///
/// </summary>
/// <param name="obj1">first item.
/// </param>
/// <param name="obj2">second item.
/// </param>
/// <returns> 0 if they are equal, 1 if obj1 > obj2, -1 otherwise.
///
/// </returns>
/// <exception cref=""> TclException if an error occurs during sorting.
/// </exception>
private int compare( TclObject obj1, TclObject obj2 )
{
int index;
int code = 0;
if ( sortIndex != -1 )
{
// The "-index" option was specified. Treat each object as a
// list, extract the requested element from each list, and
// compare the elements, not the lists. The special index "end"
// is signaled here with a negative index (other than -1).
TclObject obj;
if ( sortIndex < -1 )
{
index = TclList.getLength( sortInterp, obj1 ) - 1;
}
else
{
index = sortIndex;
}
obj = TclList.index( sortInterp, obj1, index );
if ( obj == null )
{
throw new TclException( sortInterp, "element " + index + " missing from sublist \"" + obj1 + "\"" );
}
obj1 = obj;
if ( sortIndex < -1 )
{
index = TclList.getLength( sortInterp, obj2 ) - 1;
}
else
{
index = sortIndex;
}
obj = TclList.index( sortInterp, obj2, index );
if ( obj == null )
{
throw new TclException( sortInterp, "element " + index + " missing from sublist \"" + obj2 + "\"" );
}
obj2 = obj;
}
switch ( sortMode )
{
case ASCII:
// ATK C# CompareTo use option
// similar to -dictionary but a > A
code = System.Globalization.CultureInfo.InvariantCulture.CompareInfo.Compare( obj1.ToString(), obj2.ToString(), System.Globalization.CompareOptions.Ordinal );
// code = obj1.ToString().CompareTo(obj2.ToString());
break;
case DICTIONARY:
code = doDictionary( obj1.ToString(), obj2.ToString() );
break;
case INTEGER:
try
{
int int1 = TclInteger.get( sortInterp, obj1 );
int int2 = TclInteger.get( sortInterp, obj2 );
if ( int1 > int2 )
{
code = 1;
}
else if ( int2 > int1 )
{
code = -1;
}
}
catch ( TclException e1 )
{
sortInterp.addErrorInfo( "\n (converting list element from string to integer)" );
throw e1;
}
break;
case REAL:
try
{
double f1 = TclDouble.get( sortInterp, obj1 );
double f2 = TclDouble.get( sortInterp, obj2 );
if ( f1 > f2 )
{
code = 1;
}
else if ( f2 > f1 )
{
code = -1;
}
}
catch ( TclException e2 )
{
sortInterp.addErrorInfo( "\n (converting list element from string to real)" );
throw e2;
}
break;
case COMMAND:
StringBuilder sbuf = new StringBuilder( sortCommand );
Util.appendElement( sortInterp, sbuf, obj1.ToString() );
Util.appendElement( sortInterp, sbuf, obj2.ToString() );
try
{
sortInterp.eval( sbuf.ToString(), 0 );
}
catch ( TclException e3 )
{
sortInterp.addErrorInfo( "\n (user-defined comparison command)" );
throw e3;
}
try
{
code = TclInteger.get( sortInterp, sortInterp.getResult() );
}
catch ( TclException e )
{
sortInterp.resetResult();
TclException e4 = new TclException( sortInterp, "comparison command returned non-numeric result" );
throw e4;
}
break;
default:
throw new TclRuntimeError( "Unknown sortMode " + sortMode );
}
if ( sortIncreasing )
{
return code;
}
else
{
return -code;
}
}
/// <summary> Compares the order of two strings in "dictionary" order.
///
/// </summary>
/// <param name="str1">first item.
/// </param>
/// <param name="str2">second item.
/// </param>
/// <returns> 0 if they are equal, 1 if obj1 > obj2, -1 otherwise.
/// </returns>
private int doDictionary( string str1, string str2 )
{
int diff = 0, zeros;
int secondaryDiff = 0;
bool cont = true;
int i1 = 0, i2 = 0;
int len1 = str1.Length;
int len2 = str2.Length;
while ( cont )
{
if ( i1 >= len1 || i2 >= len2 )
{
break;
}
if ( System.Char.IsDigit( str2[i2] ) && System.Char.IsDigit( str1[i1] ) )
{
// There are decimal numbers embedded in the two
// strings. Compare them as numbers, rather than
// strings. If one number has more leading zeros than
// the other, the number with more leading zeros sorts
// later, but only as a secondary choice.
zeros = 0;
while ( ( i2 < ( len2 - 1 ) ) && ( str2[i2] == '0' ) )
{
i2++;
zeros--;
}
while ( ( i1 < ( len1 - 1 ) ) && ( str1[i1] == '0' ) )
{
i1++;
zeros++;
}
if ( secondaryDiff == 0 )
{
secondaryDiff = zeros;
}
// The code below compares the numbers in the two
// strings without ever converting them to integers. It
// does this by first comparing the lengths of the
// numbers and then comparing the digit values.
diff = 0;
while ( true )
{
if ( i1 >= len1 || i2 >= len2 )
{
cont = false;
break;
}
if ( diff == 0 )
{
diff = str1[i1] - str2[i2];
}
i1++;
i2++;
if ( i1 >= len1 || i2 >= len2 )
{
cont = false;
break;
}
if ( !System.Char.IsDigit( str2[i2] ) )
{
if ( System.Char.IsDigit( str1[i1] ) )
{
return 1;
}
else
{
if ( diff != 0 )
{
return diff;
}
break;
}
}
else if ( !System.Char.IsDigit( str1[i1] ) )
{
return -1;
}
}
continue;
}
diff = str1[i1] - str2[i2];
if ( diff != 0 )
{
if ( System.Char.IsUpper( str1[i1] ) && System.Char.IsLower( str2[i2] ) )
{
diff = System.Char.ToLower( str1[i1] ) - str2[i2];
if ( diff != 0 )
{
return diff;
}
else if ( secondaryDiff == 0 )
{
secondaryDiff = -1;
}
}
else if ( System.Char.IsUpper( str2[i2] ) && System.Char.IsLower( str1[i1] ) )
{
diff = str1[i1] - System.Char.ToLower( str2[i2] );
if ( diff != 0 )
{
return diff;
}
else if ( secondaryDiff == 0 )
{
secondaryDiff = 1;
}
}
else
{
return diff;
}
}
i1++;
i2++;
}
if ( i1 >= len1 && i2 < len2 )
{
if ( !System.Char.IsDigit( str2[i2] ) )
{
return 1;
}
else
{
return -1;
}
}
else if ( i2 >= len2 && i1 < len1 )
{
if ( !System.Char.IsDigit( str1[i1] ) )
{
return -1;
}
else
{
return 1;
}
}
if ( diff == 0 )
{
diff = secondaryDiff;
}
return diff;
}
}
}