001: /*
002: * This program is free software; you can redistribute it and/or modify
003: * it under the terms of the GNU General Public License as published by
004: * the Free Software Foundation; either version 2 of the License, or
005: * (at your option) any later version.
006: *
007: * This program is distributed in the hope that it will be useful,
008: * but WITHOUT ANY WARRANTY; without even the implied warranty of
009: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
010: * GNU General Public License for more details.
011: *
012: * You should have received a copy of the GNU General Public License
013: * along with this program; if not, write to the Free Software
014: * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
015: */
016:
017: /*
018: * MultiDimensionalSort.java
019: * Copyright (C) 2004 Stijn Lievens
020: *
021: */
022:
023: package weka.classifiers.misc.monotone;
024:
025: import java.util.Arrays;
026: import java.util.Comparator;
027:
028: /**
029: * Class for doing multidimensional sorting, using an array of
030: * <code> Comparator. </code>
031: * The goal is to sort an array topologically. If <code> o1 </code>
032: * and <code> o2 </code> are two objects of the array <code> a, </code>
033: * and for all valid indices <code> i </code> in the array <code> c </code>
034: * if holds that <code> c[i].compare(o1,o2) < 0 </code> then
035: * <code> o1 </code> comes before <code> o2 </code> in the sorted array.
036: * <p>
037: * A typical is the sorting of vectors in an n-dimensional space,
038: * where the ordering is determined by the product ordering.
039: * </p>
040: * <p>
041: * This implementation is part of the master's thesis: "Studie
042: * en implementatie van instantie-gebaseerde algoritmen voor gesuperviseerd
043: * rangschikken", Stijn Lievens, Ghent University, 2004.
044: * </p>
045: *
046: * @author Stijn Lievens (stijn.lievens@ugent.be)
047: * @version $Revision: 1.1 $
048: */
049: public class MultiDimensionalSort {
050:
051: /**
052: * Sort an array using different comparators.
053: *
054: * @param a the array to be sorted. The sorted array is returned
055: * in the array <code> a </code> itself.
056: * @param c an array holding the different comparators
057: */
058: public static void multiDimensionalSort(Object[] a, Comparator[] c) {
059: multiDimensionalSort(a, 0, a.length, c);
060: }
061:
062: /**
063: * Sort part of an array using different comparators.
064: *
065: * @param a the array to be sorted, the indicated part of the array will
066: * be replaced by the sorted elements
067: * @param fromIndex index of the first element to be sorted (inclusive)
068: * @param toIndex index of the last element to be sorted (exclusive)
069: * @param c array holding the different comparators
070: * @throws IllegalArgumentException if <code> fromIndex > toIndex </code>
071: */
072: public static void multiDimensionalSort(Object[] a, int fromIndex,
073: int toIndex, Comparator[] c)
074: throws IllegalArgumentException {
075:
076: if (fromIndex > toIndex) {
077: throw new IllegalArgumentException(
078: "Illegal range: fromIndex can be at most toIndex");
079: }
080: multiDimensionalSort(a, fromIndex, toIndex, c, 0);
081: }
082:
083: /**
084: * Do the actual sorting in a recursive way.
085: *
086: * @param a the array to be sorted, the indicated part of the array will
087: * be replaced by the sorted elements
088: * @param fromIndex index of the first element to be sorted (inclusive)
089: * @param toIndex index of the last element to be sorted (exclusive)
090: * @param c array holding the different comparators
091: * @param depth the index of the comparator to use
092: */
093: private static void multiDimensionalSort(Object[] a, int fromIndex,
094: int toIndex, Comparator[] c, int depth) {
095:
096: if (depth == c.length) {
097: return; // maximum depth reached
098: }
099:
100: Comparator comp = c[depth]; // comparator to use
101: Arrays.sort(a, fromIndex, toIndex, comp); // sort part of the array
102:
103: // look for breakpoints in the array and sort recursively
104: int mark = fromIndex;
105: for (int i = fromIndex + 1; i < toIndex; i++) {
106: if (comp.compare(a[i - 1], a[i]) != 0) {
107: // a[i] is different from a[i-1], breakpoint detected
108: multiDimensionalSort(a, mark, i, c, depth + 1);
109: mark = i;
110: }
111: }
112: // sort the last part
113: multiDimensionalSort(a, mark, toIndex, c, depth + 1);
114: }
115: }
|