MessageManager
.getString("error.implementation_error_sortbyfeature"));
}
+
boolean ignoreScore = method != FEATURE_SCORE;
StringBuffer scoreLabel = new StringBuffer();
scoreLabel.append(start + stop + method);
{
scoreLabel.append(groupLabels[i] == null ? "null" : groupLabels[i]);
}
+
+ /*
+ * if resorting the same feature, toggle sort order
+ */
+ if (lastSortByFeatureScore == null
+ || !scoreLabel.toString().equals(lastSortByFeatureScore))
+ {
+ sortByFeatureScoreAscending = true;
+ }
+ else
+ {
+ sortByFeatureScoreAscending = !sortByFeatureScoreAscending;
+ }
+ lastSortByFeatureScore = scoreLabel.toString();
+
SequenceI[] seqs = alignment.getSequencesArray();
boolean[] hasScore = new boolean[seqs.length]; // per sequence score
labs[l] = (fs[l].getDescription() != null ? fs[l]
.getDescription() : fs[l].getType());
}
- jalview.util.QuickSort.sort(labs, ((Object[]) feats[i]));
+ QuickSort.sort(labs, ((Object[]) feats[i]));
}
}
if (hasScore[i])
}
else
{
- int nf = (feats[i] == null) ? 0
- : ((SequenceFeature[]) feats[i]).length;
- // System.err.println("Sorting on Score: seq "+seqs[i].getName()+
- // " Feats: "+nf+" Score : "+scores[i]);
+ // int nf = (feats[i] == null) ? 0
+ // : ((SequenceFeature[]) feats[i]).length;
+ // // System.err.println("Sorting on Score: seq " +
+ // seqs[i].getName()
+ // + " Feats: " + nf + " Score : " + scores[i]);
}
}
}
-
- jalview.util.QuickSort.sort(scores, seqs);
+ QuickSort.sortByDouble(scores, seqs, sortByFeatureScoreAscending);
}
else if (method == FEATURE_DENSITY)
{
-
- // break ties between equivalent numbers for adjacent sequences by adding
- // 1/Nseq*i on the original order
- double fr = 0.9 / (1.0 * seqs.length);
for (int i = 0; i < seqs.length; i++)
{
- double nf;
- scores[i] = (0.05 + fr * i)
- + (nf = ((feats[i] == null) ? 0.0
- : 1.0 * ((SequenceFeature[]) feats[i]).length));
+ int featureCount = feats[i] == null ? 0
+ : ((SequenceFeature[]) feats[i]).length;
+ scores[i] = featureCount;
// System.err.println("Sorting on Density: seq "+seqs[i].getName()+
- // " Feats: "+nf+" Score : "+scores[i]);
+ // " Feats: "+featureCount+" Score : "+scores[i]);
}
- jalview.util.QuickSort.sort(scores, seqs);
+ QuickSort.sortByDouble(scores, seqs, sortByFeatureScoreAscending);
}
else
{
MessageManager.getString("error.not_yet_implemented"));
}
}
- if (lastSortByFeatureScore == null
- || !scoreLabel.toString().equals(lastSortByFeatureScore))
- {
- sortByFeatureScoreAscending = true;
- }
- else
- {
- sortByFeatureScoreAscending = !sortByFeatureScoreAscending;
- }
- if (sortByFeatureScoreAscending)
- {
- setOrder(alignment, seqs);
- }
- else
- {
- setReverseOrder(alignment, seqs);
- }
- lastSortByFeatureScore = scoreLabel.toString();
+
+ setOrder(alignment, seqs);
}
}
*/
public class QuickSort
{
+ /**
+ * A comparator that compares two integers by comparing their respective
+ * indexed values in an array of floats
+ */
static class FloatComparator implements Comparator<Integer>
{
-
private final float[] values;
- FloatComparator(float[] v)
+ private boolean ascending;
+
+ FloatComparator(float[] v, boolean asc)
{
values = v;
+ ascending = asc;
}
@Override
public int compare(Integer o1, Integer o2)
{
- return Float.compare(values[o1], values[o2]);
+ return ascending ? Float.compare(values[o1], values[o2]) : Float
+ .compare(values[o2], values[o1]);
}
+ }
+
+ /**
+ * A comparator that compares two integers by comparing their respective
+ * indexed values in an array of doubles
+ */
+ static class DoubleComparator implements Comparator<Integer>
+ {
+ private final double[] values;
+ private boolean ascending;
+
+ DoubleComparator(double[] v, boolean asc)
+ {
+ values = v;
+ ascending = asc;
+ }
+
+ @Override
+ public int compare(Integer o1, Integer o2)
+ {
+ if (ascending)
+ {
+ return Double.compare(values[o1], values[o2]);
+ }
+ else
+ {
+ return Double.compare(values[o2], values[o1]);
+ }
+ }
}
+ /**
+ * A comparator that compares two integers by comparing their respective
+ * indexed values in an array of ints
+ */
static class IntComparator implements Comparator<Integer>
{
-
private final int[] values;
- IntComparator(int[] v)
+ private boolean ascending;
+
+ IntComparator(int[] v, boolean asc)
{
values = v;
+ ascending = asc;
}
@Override
public int compare(Integer o1, Integer o2)
{
- return Integer.compare(values[o1], values[o2]);
+ return ascending ? Integer.compare(values[o1], values[o2]) : Integer
+ .compare(values[o2], values[o1]);
}
+ }
+
+ /**
+ * A comparator that compares two integers by comparing their respective
+ * indexed values in an array of comparable objects.
+ */
+ static class ExternalComparator implements Comparator<Integer>
+ {
+ private final Comparable[] values;
+ private boolean ascending;
+
+ ExternalComparator(Comparable[] v, boolean asc)
+ {
+ values = v;
+ ascending = asc;
+ }
+
+ @Override
+ public int compare(Integer o1, Integer o2)
+ {
+ return ascending ? values[o1].compareTo(values[o2]) : values[o2]
+ .compareTo(values[o1]);
+ }
}
/**
/**
* Sorts both arrays with respect to descending order of the items in the
- * first array.
+ * first array. The sorting is case-sensitive.
*
* @param arr
* @param s
}
/**
- * Sorts both arrays to give ascending order in the first array, by first
- * partitioning into zero and non-zero values before sorting the latter.
+ * Sorts both arrays to give ascending order by the first array, by first
+ * partitioning into zero and non-zero values before sorting the latter. This
+ * is faster than a direct call to charSortByFloat in the case where most of
+ * the array to be sorted is zero.
*
* @param arr
* @param s
public static void sort(float[] arr, char[] s)
{
/*
- * Sort all zero values to the front
+ * Move all zero values to the front, non-zero to the back, while counting
+ * negative values
*/
float[] f1 = new float[arr.length];
char[] s1 = new char[s.length];
- int nextZeroValue = 0;
+ int negativeCount = 0;
+ int zerosCount = 0;
int nextNonZeroValue = arr.length - 1;
for (int i = 0; i < arr.length; i++)
{
float val = arr[i];
- if (val > 0f)
+ if (val != 0f)
{
f1[nextNonZeroValue] = val;
s1[nextNonZeroValue] = s[i];
nextNonZeroValue--;
+ if (val < 0f)
+ {
+ negativeCount++;
+ }
}
else
{
- f1[nextZeroValue] = val;
- s1[nextZeroValue] = s[i];
- nextZeroValue++;
+ f1[zerosCount] = val;
+ s1[zerosCount] = s[i];
+ zerosCount++;
}
}
+ int positiveCount = arr.length - zerosCount - negativeCount;
- /*
- * Copy zero values back to original arrays
- */
- System.arraycopy(f1, 0, arr, 0, nextZeroValue);
- System.arraycopy(s1, 0, s, 0, nextZeroValue);
-
- if (nextZeroValue == arr.length)
+ if (zerosCount == arr.length)
{
return; // all zero
}
+
+ /*
+ * sort the non-zero values
+ */
+ float[] nonZeroFloats = Arrays.copyOfRange(f1, zerosCount, f1.length);
+ char[] nonZeroChars = Arrays.copyOfRange(s1, zerosCount, s1.length);
+ charSortByFloat(nonZeroFloats, nonZeroChars, true);
+
/*
- * Sort the non-zero values
+ * Backfill zero values to original arrays, after the space reserved for
+ * negatives
*/
- float[] nonZeroFloats = Arrays
- .copyOfRange(f1, nextZeroValue, f1.length);
- char[] nonZeroChars = Arrays.copyOfRange(s1, nextZeroValue, s1.length);
- externalSort(nonZeroFloats, nonZeroChars);
- // sort(nonZeroFloats, 0, nonZeroFloats.length - 1, nonZeroChars);
+ System.arraycopy(f1, 0, arr, negativeCount, zerosCount);
+ System.arraycopy(s1, 0, s, negativeCount, zerosCount);
/*
- * Assemble sorted non-zero results
+ * Copy sorted negative values to the front of arr, s
*/
- System.arraycopy(nonZeroFloats, 0, arr, nextZeroValue,
- nonZeroFloats.length);
- System.arraycopy(nonZeroChars, 0, s, nextZeroValue, nonZeroChars.length);
+ System.arraycopy(nonZeroFloats, 0, arr, 0, negativeCount);
+ System.arraycopy(nonZeroChars, 0, s, 0, negativeCount);
+
+ /*
+ * Copy sorted positive values after the negatives and zeros
+ */
+ System.arraycopy(nonZeroFloats, negativeCount, arr, negativeCount
+ + zerosCount, positiveCount);
+ System.arraycopy(nonZeroChars, negativeCount, s, negativeCount
+ + zerosCount, positiveCount);
}
/**
- * Sort by making an array of indices, and sorting it using a comparator that
- * refers to the float values.
+ * Sorts arrays of float and char by the float values, by making an array of
+ * indices, and sorting it using a comparator that refers to the float values.
*
* @see http
* ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
* after-sorting
* @param arr
* @param s
+ * @param ascending
*/
- protected static void externalSort(float[] arr, char[] s)
+ public static void charSortByFloat(float[] arr, char[] s,
+ boolean ascending)
{
final int length = arr.length;
Integer[] indices = makeIndexArray(length);
- Arrays.sort(indices, new FloatComparator(arr));
+ Arrays.sort(indices, new FloatComparator(arr, ascending));
/*
* Copy the array values as per the sorted indices
/**
* Sorts both arrays to give ascending order in the first array, by first
- * partitioning into zero and non-zero values before sorting the latter.
+ * partitioning into zero and non-zero values before sorting the latter. This
+ * is faster than a direct call to charSortByInt in the case where most of the
+ * array to be sorted is zero.
*
* @param arr
* @param s
*/
public static void sort(int[] arr, char[] s)
- {
- /*
- * Sort all zero values to the front
+ { /*
+ * Move all zero values to the front, non-zero to the back, while counting
+ * negative values
*/
int[] f1 = new int[arr.length];
char[] s1 = new char[s.length];
- int nextZeroValue = 0;
+ int negativeCount = 0;
+ int zerosCount = 0;
int nextNonZeroValue = arr.length - 1;
for (int i = 0; i < arr.length; i++)
{
int val = arr[i];
- if (val > 0f)
+ if (val != 0f)
{
f1[nextNonZeroValue] = val;
s1[nextNonZeroValue] = s[i];
nextNonZeroValue--;
+ if (val < 0)
+ {
+ negativeCount++;
+ }
}
else
{
- f1[nextZeroValue] = val;
- s1[nextZeroValue] = s[i];
- nextZeroValue++;
+ f1[zerosCount] = val;
+ s1[zerosCount] = s[i];
+ zerosCount++;
}
}
+ int positiveCount = arr.length - zerosCount - negativeCount;
- /*
- * Copy zero values back to original arrays
- */
- System.arraycopy(f1, 0, arr, 0, nextZeroValue);
- System.arraycopy(s1, 0, s, 0, nextZeroValue);
-
- if (nextZeroValue == arr.length)
+ if (zerosCount == arr.length)
{
return; // all zero
}
+
+ /*
+ * sort the non-zero values
+ */
+ int[] nonZeroInts = Arrays.copyOfRange(f1, zerosCount, f1.length);
+ char[] nonZeroChars = Arrays.copyOfRange(s1, zerosCount, s1.length);
+ charSortByInt(nonZeroInts, nonZeroChars, true);
+
+ /*
+ * Backfill zero values to original arrays, after the space reserved for
+ * negatives
+ */
+ System.arraycopy(f1, 0, arr, negativeCount, zerosCount);
+ System.arraycopy(s1, 0, s, negativeCount, zerosCount);
+
/*
- * Sort the non-zero values
+ * Copy sorted negative values to the front of arr, s
*/
- int[] nonZeroInts = Arrays.copyOfRange(f1, nextZeroValue, f1.length);
- char[] nonZeroChars = Arrays.copyOfRange(s1, nextZeroValue, s1.length);
- externalSort(nonZeroInts, nonZeroChars);
- // sort(nonZeroFloats, 0, nonZeroFloats.length - 1, nonZeroChars);
+ System.arraycopy(nonZeroInts, 0, arr, 0, negativeCount);
+ System.arraycopy(nonZeroChars, 0, s, 0, negativeCount);
/*
- * Assemble sorted non-zero results
+ * Copy sorted positive values after the negatives and zeros
*/
- System.arraycopy(nonZeroInts, 0, arr, nextZeroValue, nonZeroInts.length);
- System.arraycopy(nonZeroChars, 0, s, nextZeroValue, nonZeroChars.length);
+ System.arraycopy(nonZeroInts, negativeCount, arr, negativeCount
+ + zerosCount, positiveCount);
+ System.arraycopy(nonZeroChars, negativeCount, s, negativeCount
+ + zerosCount, positiveCount);
}
/**
- * Sort by making an array of indices, and sorting it using a comparator that
- * refers to the float values.
+ * Sorts arrays of int and char, by making an array of indices, and sorting it
+ * using a comparator that refers to the int values.
*
* @see http
* ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
* after-sorting
* @param arr
* @param s
+ * @param ascending
*/
- protected static void externalSort(int[] arr, char[] s)
+ public static void charSortByInt(int[] arr, char[] s, boolean ascending)
{
final int length = arr.length;
Integer[] indices = makeIndexArray(length);
- Arrays.sort(indices, new IntComparator(arr));
+ Arrays.sort(indices, new IntComparator(arr, ascending));
/*
* Copy the array values as per the sorted indices
System.arraycopy(sortedInts, 0, arr, 0, length);
System.arraycopy(sortedChars, 0, s, 0, s.length);
}
+
+ /**
+ * Sorts arrays of int and Object, by making an array of indices, and sorting
+ * it using a comparator that refers to the int values.
+ *
+ * @see http
+ * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
+ * after-sorting
+ * @param arr
+ * @param s
+ * @param ascending
+ */
+ public static void sortByInt(int[] arr, Object[] s, boolean ascending)
+ {
+ final int length = arr.length;
+ Integer[] indices = makeIndexArray(length);
+ Arrays.sort(indices, new IntComparator(arr, ascending));
+
+ /*
+ * Copy the array values as per the sorted indices
+ */
+ int[] sortedInts = new int[length];
+ Object[] sortedObjects = new Object[s.length];
+ for (int i = 0; i < length; i++)
+ {
+ sortedInts[i] = arr[indices[i]];
+ sortedObjects[i] = s[indices[i]];
+ }
+
+ /*
+ * And copy the sorted values back into the arrays
+ */
+ System.arraycopy(sortedInts, 0, arr, 0, length);
+ System.arraycopy(sortedObjects, 0, s, 0, s.length);
+ }
+
+ /**
+ * Sorts arrays of String and Object, by making an array of indices, and
+ * sorting it using a comparator that refers to the String values. Both arrays
+ * are sorted by case-sensitive order of the string array values.
+ *
+ * @see http
+ * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
+ * after-sorting
+ * @param arr
+ * @param s
+ * @param ascending
+ */
+ public static void sortByString(String[] arr, Object[] s,
+ boolean ascending)
+ {
+ final int length = arr.length;
+ Integer[] indices = makeIndexArray(length);
+ Arrays.sort(indices, new ExternalComparator(arr, ascending));
+
+ /*
+ * Copy the array values as per the sorted indices
+ */
+ String[] sortedStrings = new String[length];
+ Object[] sortedObjects = new Object[s.length];
+ for (int i = 0; i < length; i++)
+ {
+ sortedStrings[i] = arr[indices[i]];
+ sortedObjects[i] = s[indices[i]];
+ }
+
+ /*
+ * And copy the sorted values back into the arrays
+ */
+ System.arraycopy(sortedStrings, 0, arr, 0, length);
+ System.arraycopy(sortedObjects, 0, s, 0, s.length);
+ }
+
+ /**
+ * Sorts arrays of double and Object, by making an array of indices, and
+ * sorting it using a comparator that refers to the double values.
+ *
+ * @see http
+ * ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
+ * after-sorting
+ * @param arr
+ * @param s
+ * @param ascending
+ */
+ public static void sortByDouble(double[] arr, Object[] s,
+ boolean ascending)
+ {
+ final int length = arr.length;
+ Integer[] indices = makeIndexArray(length);
+ Arrays.sort(indices, new DoubleComparator(arr, ascending));
+
+ /*
+ * Copy the array values as per the sorted indices
+ */
+ double[] sortedDoubles = new double[length];
+ Object[] sortedObjects = new Object[s.length];
+ for (int i = 0; i < length; i++)
+ {
+ sortedDoubles[i] = arr[indices[i]];
+ sortedObjects[i] = s[indices[i]];
+ }
+
+ /*
+ * And copy the sorted values back into the arrays
+ */
+ System.arraycopy(sortedDoubles, 0, arr, 0, length);
+ System.arraycopy(sortedObjects, 0, s, 0, s.length);
+ }
}
import static org.testng.AssertJUnit.assertTrue;
import java.util.Arrays;
+import java.util.Random;
-import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
public class QuickSortTest
private static final String c4 = "Green";
- private Object[] things;
+ private static final String c5 = "Pink";
- private final Object[] sortedThings = new Object[] { c4, c2, c1, c3 };
-
- @BeforeMethod(alwaysRun = true)
- public void setUp()
+ @Test(groups = { "Functional" })
+ public void testSort_byIntValues()
{
- things = new Object[] { c1, c2, c3, c4 };
+ int[] values = new int[] { 3, 0, 4, 3, -1 };
+ Object[] things = new Object[] { c1, c2, c3, c4, c5 };
+
+ QuickSort.sort(values, things);
+ assertTrue(Arrays.equals(new int[] { -1, 0, 3, 3, 4 }, values));
+ // note sort is not stable: c1/c4 are equal but get reordered
+ Object[] expect = new Object[] { c5, c2, c4, c1, c3 };
+ assertTrue(Arrays.equals(expect, things));
}
+ /**
+ * Test the alternative sort objects by integer method
+ */
@Test(groups = { "Functional" })
- public void testSort_byIntValues()
+ public void testSortByInt()
{
- int[] values = new int[] { 3, 2, 4, 1 };
- QuickSort.sort(values, things);
- assertTrue(Arrays.equals(new int[] { 1, 2, 3, 4 }, values));
- assertTrue(Arrays.equals(sortedThings, things));
+ int[] values = new int[] { 3, 0, 4, 3, -1 };
+ Object[] things = new Object[] { c1, c2, c3, c4, c5 };
+
+ /*
+ * sort ascending
+ */
+ QuickSort.sortByInt(values, things, true);
+ assertTrue(Arrays.equals(new int[] { -1, 0, 3, 3, 4 }, values));
+ assertTrue(Arrays.equals(new Object[] { c5, c2, c1, c4, c3 }, things));
+
+ /*
+ * resort descending; c1/c4 should not change order
+ */
+ QuickSort.sortByInt(values, things, false);
+ assertTrue(Arrays.equals(new int[] { 4, 3, 3, 0, -1 }, values));
+ assertTrue(Arrays.equals(new Object[] { c3, c1, c4, c2, c5 }, things));
}
@Test(groups = { "Functional" })
public void testSort_byFloatValues()
{
- float[] values = new float[] { 3f, 2f, 4f, 1f };
+ float[] values = new float[] { 3f, 0f, 4f, 3f, -1f };
+ Object[] things = new Object[] { c1, c2, c3, c4, c5 };
QuickSort.sort(values, things);
- assertTrue(Arrays.equals(new float[] { 1f, 2f, 3f, 4f }, values));
- assertTrue(Arrays.equals(sortedThings, things));
+ assertTrue(Arrays.equals(new float[] { -1f, 0f, 3f, 3f, 4f }, values));
+ // note sort is not stable: c1/c4 are equal but get reordered
+ assertTrue(Arrays.equals(new Object[] { c5, c2, c4, c1, c3 }, things));
}
@Test(groups = { "Functional" })
public void testSort_byDoubleValues()
{
- double[] values = new double[] { 3d, 2d, 4d, 1d };
+ double[] values = new double[] { 3d, 0d, 4d, 3d, -1d };
+ Object[] things = new Object[] { c1, c2, c3, c4, c5 };
QuickSort.sort(values, things);
- assertTrue(Arrays.equals(new double[] { 1d, 2d, 3d, 4d }, values));
- assertTrue(Arrays.equals(sortedThings, things));
+ assertTrue(Arrays.equals(new double[] { -1d, 0d, 3d, 3d, 4d }, values));
+ // note sort is not stable: c1/c4 are equal but get reordered
+ assertTrue(Arrays.equals(new Object[] { c5, c2, c4, c1, c3 }, things));
}
/**
@Test(groups = { "Functional" })
public void testSort_byStringValues()
{
- String[] values = new String[] { "JOHN", "henry", "lucy", "ALISON" };
+ Object[] things = new Object[] { c1, c2, c3, c4, c5 };
+ String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
+ "ALISON" };
QuickSort.sort(values, things);
- assertTrue(Arrays.equals(new String[] { "lucy", "henry", "JOHN",
+ assertTrue(Arrays.equals(new String[] { "lucy", "henry", "henry",
+ "JOHN",
"ALISON" }, values));
- assertTrue(Arrays.equals(new Object[] { c3, c2, c1, c4 }, things));
+ assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
}
/**
public void testSort_withDuplicates()
{
int[] values = new int[] { 3, 4, 2, 4, 1 };
- Object[] things = new Object[] { "A", "X", "Y", "B", "Z" };
- QuickSort.sort(values, things);
+ Object[] letters = new Object[] { "A", "X", "Y", "B", "Z" };
+ QuickSort.sort(values, letters);
assertTrue(Arrays.equals(new int[] { 1, 2, 3, 4, 4 }, values));
// this fails - do we care?
assertTrue(Arrays.equals(new Object[] { "Z", "Y", "A", "X", "B" },
- things));
+ letters));
}
/**
- * Test that exercises sort with a mostly zero-valued sortby array. May be of
- * interest to check the sort algorithm is efficient.
+ * Test of method that sorts chars by a float array
*/
@Test(groups = { "Functional" })
- public void testSort_MostlyZeroValues()
+ public void testSort_charSortByFloat_mostlyZeroValues()
{
char[] residues = new char[64];
for (int i = 0; i < 64; i++)
float[] counts = new float[64];
counts[43] = 16;
counts[59] = 7;
- counts[62] = 2;
+ counts[62] = -2;
QuickSort.sort(counts, residues);
+ assertEquals(62, residues[0]); // negative sorts to front
+ assertEquals(59, residues[62]); // 7 sorts to next-to-end
+ assertEquals(43, residues[63]); // 16 sorts to end
+ }
+
+ /**
+ * Timing test - to be run manually as needed, not part of the automated
+ * suite. <br>
+ * It shows that the optimised sort is 3-4 times faster than the simple
+ * external sort if the data to be sorted is mostly zero, but slightly slower
+ * if the data is fully populated with non-zero values. Worst case for an
+ * array of size 256 is about 100 sorts per millisecond.
+ */
+ @Test(groups = { "Timing" }, enabled = false)
+ public void testSort_timingTest()
+ {
+ char[] residues = new char[256];
+ for (int i = 0; i < residues.length; i++)
+ {
+ residues[i] = (char) i;
+ }
+ float[] counts = new float[residues.length];
+
+ int iterations = 1000000;
+
+ /*
+ * time it using optimised sort (of a mostly zero-filled array)
+ */
+ long start = System.currentTimeMillis();
+ for (int i = 0; i < iterations; i++)
+ {
+ Arrays.fill(counts, 0f);
+ counts[43] = 16;
+ counts[59] = 7;
+ counts[62] = -2;
+ QuickSort.sort(counts, residues);
+ }
+ long elapsed = System.currentTimeMillis() - start;
+ System.out
+ .println(String
+ .format("Time for %d optimised sorts of mostly zeros array length %d was %dms",
+ iterations, counts.length, elapsed));
+
+ /*
+ * time it using unoptimised external sort
+ */
+ start = System.currentTimeMillis();
+ for (int i = 0; i < iterations; i++)
+ {
+ Arrays.fill(counts, 0f);
+ counts[43] = 16;
+ counts[59] = 7;
+ counts[62] = -2;
+ QuickSort.charSortByFloat(counts, residues, true);
+ }
+ elapsed = System.currentTimeMillis() - start;
+ System.out
+ .println(String
+ .format("Time for %d external sorts of mostly zeros array length %d was %dms",
+ iterations, counts.length, elapsed));
+
+ /*
+ * optimised external sort, well-filled array
+ */
+ Random random = new Random();
+ float[] randoms = new float[counts.length];
+ for (int i = 0; i < randoms.length; i++)
+ {
+ randoms[i] = random.nextFloat();
+ }
+
+ start = System.currentTimeMillis();
+ for (int i = 0; i < iterations; i++)
+ {
+ System.arraycopy(randoms, 0, counts, 0, randoms.length);
+ QuickSort.sort(counts, residues);
+ }
+ elapsed = System.currentTimeMillis() - start;
+ System.out
+ .println(String
+ .format("Time for %d optimised sorts of non-zeros array length %d was %dms",
+ iterations, counts.length, elapsed));
+
+ /*
+ * time unoptimised external sort, filled array
+ */
+ start = System.currentTimeMillis();
+ for (int i = 0; i < iterations; i++)
+ {
+ System.arraycopy(randoms, 0, counts, 0, randoms.length);
+ QuickSort.charSortByFloat(counts, residues, true);
+ }
+ elapsed = System.currentTimeMillis() - start;
+ System.out
+ .println(String
+ .format("Time for %d external sorts of non-zeros array length %d was %dms",
+ iterations, counts.length, elapsed));
+ }
+
+ /**
+ * Test that exercises sort without any attempt at fancy optimisation
+ */
+ @Test(groups = { "Functional" })
+ public void testCharSortByFloat()
+ {
+ char[] residues = new char[64];
+ for (int i = 0; i < 64; i++)
+ {
+ residues[i] = (char) i;
+ }
+ float[] counts = new float[64];
+ counts[43] = 16;
+ counts[59] = 7;
+ counts[62] = -2;
+
+ /*
+ * sort ascending
+ */
+ QuickSort.charSortByFloat(counts, residues, true);
+ assertEquals(62, residues[0]);
+ assertEquals(59, residues[62]);
assertEquals(43, residues[63]);
+
+ /*
+ * resort descending
+ */
+ QuickSort.charSortByFloat(counts, residues, false);
+ assertEquals(62, residues[63]);
+ assertEquals(59, residues[1]);
+ assertEquals(43, residues[0]);
+ }
+
+ /**
+ * Test of method that sorts chars by an int array
+ */
+ @Test(groups = { "Functional" })
+ public void testSort_charSortByInt_mostlyZeroValues()
+ {
+ char[] residues = new char[64];
+ for (int i = 0; i < 64; i++)
+ {
+ residues[i] = (char) i;
+ }
+ int[] counts = new int[64];
+ counts[43] = 16;
+ counts[59] = 7;
+ counts[62] = -2;
+ QuickSort.sort(counts, residues);
+ assertEquals(62, residues[0]); // negative sorts to front
+ assertEquals(59, residues[62]); // 7 sorts to next-to-end
+ assertEquals(43, residues[63]); // 16 sorts to end
+ }
+
+ /**
+ * Test that exercises sorting without any attempt at fancy optimisation.
+ */
+ @Test(groups = { "Functional" })
+ public void testCharSortByInt()
+ {
+ char[] residues = new char[64];
+ for (int i = 0; i < 64; i++)
+ {
+ residues[i] = (char) i;
+ }
+ int[] counts = new int[64];
+ counts[43] = 16;
+ counts[59] = 7;
+ counts[62] = -2;
+
+ /*
+ * sort ascending
+ */
+ QuickSort.charSortByInt(counts, residues, true);
+ assertEquals(62, residues[0]);
assertEquals(59, residues[62]);
- assertEquals(62, residues[61]);
+ assertEquals(43, residues[63]);
+
+ /*
+ * resort descending
+ */
+ QuickSort.charSortByInt(counts, residues, false);
+ assertEquals(62, residues[63]);
+ assertEquals(59, residues[1]);
+ assertEquals(43, residues[0]);
+ }
+
+ /**
+ * Tests the alternative method to sort bby String in descending order,
+ * case-sensitive
+ */
+ @Test(groups = { "Functional" })
+ public void testSortByString()
+ {
+ Object[] things = new Object[] { c1, c2, c3, c4, c5 };
+ String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
+ "ALISON" };
+
+ /*
+ * sort descending
+ */
+ QuickSort.sortByString(values, things, false);
+ assertTrue(Arrays.equals(new String[] { "lucy", "henry", "henry",
+ "JOHN", "ALISON" }, values));
+ assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
+
+ /*
+ * resort ascending
+ */
+ QuickSort.sortByString(values, things, true);
+ assertTrue(Arrays.equals(new String[] { "ALISON", "JOHN", "henry",
+ "henry", "lucy" }, values));
+ // sort is stable: c2/c4 do not swap order
+ assertTrue(Arrays.equals(new Object[] { c5, c1, c2, c4, c3 }, things));
}
}
git://source.jalview.org / jalview.git / commitdiff