/*
Copyright (C) 1999 CERN - European Organization for Nuclear Research.
Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
is hereby granted without fee, provided that the above copyright notice appear in all copies and
that both that copyright notice and this permission notice appear in supporting documentation.
CERN makes no representations about the suitability of this software for any purpose.
It is provided "as is" without expressed or implied warranty.
*/
package cern.colt.matrix.tobject.algo;
import cern.colt.function.tint.IntComparator;
import cern.colt.matrix.AbstractFormatter;
import cern.colt.matrix.tobject.ObjectMatrix1D;
import cern.colt.matrix.tobject.ObjectMatrix2D;
import cern.colt.matrix.tobject.ObjectMatrix3D;
/**
* Matrix quicksorts and mergesorts. Use idioms like
* Sorting.quickSort.sort(...) and Sorting.mergeSort.sort(...)
* .
*
* This is another case demonstrating one primary goal of this library:
* Delivering easy to use, yet very efficient APIs. The sorts return convenient
* sort views. This enables the usage of algorithms which scale well with
* the problem size: For example, sorting a 1000000 x 10000 or a 1000000 x 100 x
* 100 matrix performs just as fast as sorting a 1000000 x 1 matrix. This is so,
* because internally the algorithms only move around integer indexes, they do
* not physically move around entire rows or slices. The original matrix is left
* unaffected.
*
* The quicksort is a derivative of the JDK 1.2 V1.26 algorithms (which are, in
* turn, based on Bentley's and McIlroy's fine work). The mergesort is a
* derivative of the JAL algorithms, with optimisations taken from the JDK
* algorithms. Mergesort is stable (by definition), while quicksort is
* not. A stable sort is, for example, helpful, if matrices are sorted
* successively by multiple columns. It preserves the relative position of equal
* elements.
*
* @see cern.colt.GenericSorting
* @see cern.colt.Sorting
* @see java.util.Arrays
*
* @author wolfgang.hoschek@cern.ch
* @version 1.1, 25/May/2000
*/
public class ObjectSorting extends cern.colt.PersistentObject {
/**
*
*/
private static final long serialVersionUID = 1L;
/**
* A prefabricated quicksort.
*/
public static final ObjectSorting quickSort = new ObjectSorting(); // already has
// quicksort
// implemented
/**
* A prefabricated mergesort.
*/
public static final ObjectSorting mergeSort = new ObjectSorting() { // override
/**
*
*/
private static final long serialVersionUID = 1L;
// quicksort with
// mergesort
protected void runSort(int[] a, int fromIndex, int toIndex, IntComparator c) {
cern.colt.Sorting.mergeSort(a, fromIndex, toIndex, c);
}
protected void runSort(int fromIndex, int toIndex, IntComparator c, cern.colt.Swapper swapper) {
cern.colt.GenericSorting.mergeSort(fromIndex, toIndex, c, swapper);
}
};
/**
* Makes this class non instantiable, but still let's others inherit from
* it.
*/
protected ObjectSorting() {
}
protected void runSort(int[] a, int fromIndex, int toIndex, IntComparator c) {
cern.colt.Sorting.quickSort(a, fromIndex, toIndex, c);
}
protected void runSort(int fromIndex, int toIndex, IntComparator c, cern.colt.Swapper swapper) {
cern.colt.GenericSorting.quickSort(fromIndex, toIndex, c, swapper);
}
/**
* Sorts the vector into ascending order, according to the natural
* ordering. The returned view is backed by this matrix, so changes in
* the returned view are reflected in this matrix, and vice-versa. To sort
* ranges use sub-ranging views. To sort descending, use flip views ...
*
* Example:
*
*
* 7, 1, 3, 1
*
*
* ==> 1, 1, 3, 7
The vector IS NOT SORTED.
The new VIEW IS SORTED.
*
*
*
*
*
* @param vector
* the vector to be sorted.
* @return a new sorted vector (matrix) view. Note that the original
* matrix is left unaffected.
*/
public ObjectMatrix1D sort(final ObjectMatrix1D vector) {
int[] indexes = new int[(int) vector.size()]; // row indexes to reorder
// instead of matrix itself
for (int i = indexes.length; --i >= 0;)
indexes[i] = i;
IntComparator comp = new IntComparator() {
public int compare(int a, int b) {
Comparable av = (Comparable) (vector.getQuick(a));
Comparable bv = (Comparable) (vector.getQuick(b));
int r = av.compareTo(bv);
return r < 0 ? -1 : (r > 0 ? 1 : 0);
}
};
runSort(indexes, 0, indexes.length, comp);
return vector.viewSelection(indexes);
}
/**
* Sorts the vector into ascending order, according to the order induced by
* the specified comparator. The returned view is backed by this matrix, so
* changes in the returned view are reflected in this matrix, and
* vice-versa. The algorithm compares two cells at a time, determinining
* whether one is smaller, equal or larger than the other. To sort ranges
* use sub-ranging views. To sort descending, use flip views ...
*
* Example:
*
*
* // sort by sinus of cells
* ObjectComparator comp = new ObjectComparator() {
* public int compare(Object a, Object b) {
* Object as = Math.sin(a);
* Object bs = Math.sin(b);
* return as < bs ? -1 : as == bs ? 0 : 1;
* }
* };
* sorted = quickSort(vector, comp);
*
*
* @param vector
* the vector to be sorted.
* @param c
* the comparator to determine the order.
* @return a new matrix view sorted as specified. Note that the original
* vector (matrix) is left unaffected.
*/
public ObjectMatrix1D sort(final ObjectMatrix1D vector, final java.util.Comparator c) {
int[] indexes = new int[(int) vector.size()]; // row indexes to reorder
// instead of matrix itself
for (int i = indexes.length; --i >= 0;)
indexes[i] = i;
IntComparator comp = new IntComparator() {
public int compare(int a, int b) {
return c.compare(vector.getQuick(a), vector.getQuick(b));
}
};
runSort(indexes, 0, indexes.length, comp);
return vector.viewSelection(indexes);
}
/**
* Sorts the matrix rows into ascending order, according to the natural
* ordering of the matrix values in the given column. The returned view
* is backed by this matrix, so changes in the returned view are reflected
* in this matrix, and vice-versa. To sort ranges use sub-ranging views. To
* sort columns by rows, use dice views. To sort descending, use flip views
* ...
*
* Example:
*
*
* 4 x 2 matrix:
7, 6
5, 4
3, 2
1, 0
*
*
* column = 0;
view = quickSort(matrix,column);
System.out.println(view);
==>
*
*
*
*
* 4 x 2 matrix:
1, 0
3, 2
5, 4
7, 6
* The matrix IS NOT SORTED.
* The new VIEW IS SORTED.
*
*
*
*
*
* @param matrix
* the matrix to be sorted.
* @param column
* the index of the column inducing the order.
* @return a new matrix view having rows sorted by the given column. Note
* that the original matrix is left unaffected.
* @throws IndexOutOfBoundsException
* if column < 0 || column >= matrix.columns().
*/
public ObjectMatrix2D sort(ObjectMatrix2D matrix, int column) {
if (column < 0 || column >= matrix.columns())
throw new IndexOutOfBoundsException("column=" + column + ", matrix=" + AbstractFormatter.shape(matrix));
int[] rowIndexes = new int[matrix.rows()]; // row indexes to reorder
// instead of matrix itself
for (int i = rowIndexes.length; --i >= 0;)
rowIndexes[i] = i;
final ObjectMatrix1D col = matrix.viewColumn(column);
IntComparator comp = new IntComparator() {
public int compare(int a, int b) {
Comparable av = (Comparable) (col.getQuick(a));
Comparable bv = (Comparable) (col.getQuick(b));
int r = av.compareTo(bv);
return r < 0 ? -1 : (r > 0 ? 1 : 0);
}
};
runSort(rowIndexes, 0, rowIndexes.length, comp);
// view the matrix according to the reordered row indexes
// take all columns in the original order
return matrix.viewSelection(rowIndexes, null);
}
/**
* Sorts the matrix rows according to the order induced by the specified
* comparator. The returned view is backed by this matrix, so changes in the
* returned view are reflected in this matrix, and vice-versa. The algorithm
* compares two rows (1-d matrices) at a time, determinining whether one is
* smaller, equal or larger than the other. To sort ranges use sub-ranging
* views. To sort columns by rows, use dice views. To sort descending, use
* flip views ...
*
* Example:
*
*
* // sort by sum of values in a row
* ObjectMatrix1DComparator comp = new ObjectMatrix1DComparator() {
* public int compare(ObjectMatrix1D a, ObjectMatrix1D b) {
* Object as = a.zSum();
* Object bs = b.zSum();
* return as < bs ? -1 : as == bs ? 0 : 1;
* }
* };
* sorted = quickSort(matrix, comp);
*
*
* @param matrix
* the matrix to be sorted.
* @param c
* the comparator to determine the order.
* @return a new matrix view having rows sorted as specified. Note that
* the original matrix is left unaffected.
*/
public ObjectMatrix2D sort(final ObjectMatrix2D matrix, final ObjectMatrix1DComparator c) {
int[] rowIndexes = new int[matrix.rows()]; // row indexes to reorder
// instead of matrix itself
for (int i = rowIndexes.length; --i >= 0;)
rowIndexes[i] = i;
final ObjectMatrix1D[] views = new ObjectMatrix1D[matrix.rows()]; // precompute
// views
// for
// speed
for (int i = views.length; --i >= 0;)
views[i] = matrix.viewRow(i);
IntComparator comp = new IntComparator() {
public int compare(int a, int b) {
// return c.compare(matrix.viewRow(a), matrix.viewRow(b));
return c.compare(views[a], views[b]);
}
};
runSort(rowIndexes, 0, rowIndexes.length, comp);
// view the matrix according to the reordered row indexes
// take all columns in the original order
return matrix.viewSelection(rowIndexes, null);
}
/**
* Sorts the matrix slices into ascending order, according to the natural
* ordering of the matrix values in the given [row,column]
* position. The returned view is backed by this matrix, so changes in the
* returned view are reflected in this matrix, and vice-versa. To sort
* ranges use sub-ranging views. To sort by other dimensions, use dice
* views. To sort descending, use flip views ...
*
* The algorithm compares two 2-d slices at a time, determinining whether
* one is smaller, equal or larger than the other. Comparison is based on
* the cell [row,column] within a slice. Let A and
* B be two 2-d slices. Then we have the following rules
*
* - A < B iff A.get(row,column) < B.get(row,column)
*
- A == B iff A.get(row,column) == B.get(row,column)
*
- A > B iff A.get(row,column) > B.get(row,column)
*
*
* @param matrix
* the matrix to be sorted.
* @param row
* the index of the row inducing the order.
* @param column
* the index of the column inducing the order.
* @return a new matrix view having slices sorted by the values of the slice
* view matrix.viewRow(row).viewColumn(column). Note
* that the original matrix is left unaffected.
* @throws IndexOutOfBoundsException
* if
* row < 0 || row >= matrix.rows() || column < 0 || column >= matrix.columns()
* .
*/
public ObjectMatrix3D sort(ObjectMatrix3D matrix, int row, int column) {
if (row < 0 || row >= matrix.rows())
throw new IndexOutOfBoundsException("row=" + row + ", matrix=" + AbstractFormatter.shape(matrix));
if (column < 0 || column >= matrix.columns())
throw new IndexOutOfBoundsException("column=" + column + ", matrix=" + AbstractFormatter.shape(matrix));
int[] sliceIndexes = new int[matrix.slices()]; // indexes to reorder
// instead of matrix
// itself
for (int i = sliceIndexes.length; --i >= 0;)
sliceIndexes[i] = i;
final ObjectMatrix1D sliceView = matrix.viewRow(row).viewColumn(column);
IntComparator comp = new IntComparator() {
public int compare(int a, int b) {
Comparable av = (Comparable) (sliceView.getQuick(a));
Comparable bv = (Comparable) (sliceView.getQuick(b));
int r = av.compareTo(bv);
return r < 0 ? -1 : (r > 0 ? 1 : 0);
}
};
runSort(sliceIndexes, 0, sliceIndexes.length, comp);
// view the matrix according to the reordered slice indexes
// take all rows and columns in the original order
return matrix.viewSelection(sliceIndexes, null, null);
}
/**
* Sorts the matrix slices according to the order induced by the specified
* comparator. The returned view is backed by this matrix, so changes in the
* returned view are reflected in this matrix, and vice-versa. The algorithm
* compares two slices (2-d matrices) at a time, determinining whether one
* is smaller, equal or larger than the other. To sort ranges use
* sub-ranging views. To sort by other dimensions, use dice views. To sort
* descending, use flip views ...
*
* Example:
*
*
* // sort by sum of values in a slice
* ObjectMatrix2DComparator comp = new ObjectMatrix2DComparator() {
* public int compare(ObjectMatrix2D a, ObjectMatrix2D b) {
* Object as = a.zSum();
* Object bs = b.zSum();
* return as < bs ? -1 : as == bs ? 0 : 1;
* }
* };
* sorted = quickSort(matrix, comp);
*
*
* @param matrix
* the matrix to be sorted.
* @param c
* the comparator to determine the order.
* @return a new matrix view having slices sorted as specified. Note that
* the original matrix is left unaffected.
*/
public ObjectMatrix3D sort(final ObjectMatrix3D matrix, final ObjectMatrix2DComparator c) {
int[] sliceIndexes = new int[matrix.slices()]; // indexes to reorder
// instead of matrix
// itself
for (int i = sliceIndexes.length; --i >= 0;)
sliceIndexes[i] = i;
final ObjectMatrix2D[] views = new ObjectMatrix2D[matrix.slices()]; // precompute
// views
// for
// speed
for (int i = views.length; --i >= 0;)
views[i] = matrix.viewSlice(i);
IntComparator comp = new IntComparator() {
public int compare(int a, int b) {
// return c.compare(matrix.viewSlice(a), matrix.viewSlice(b));
return c.compare(views[a], views[b]);
}
};
runSort(sliceIndexes, 0, sliceIndexes.length, comp);
// view the matrix according to the reordered slice indexes
// take all rows and columns in the original order
return matrix.viewSelection(sliceIndexes, null, null);
}
}
Ads help maintain this website.