← Back to branch summary

~ubuntu-branches/ubuntu/precise/weka/precise

« back to all changes in this revision

Viewing changes to weka/classifiers/misc/monotone/MultiDimensionalSort.java

  • Committer: Bazaar Package Importer
  • Author(s): Soeren Sonnenburg
  • Date: 2008-02-24 09:18:45 UTC
  • Revision ID: james.westby@ubuntu.com-20080224091845-1l8zy6fm6xipbzsr
Tags: upstream-3.5.7+tut1
Import upstream version 3.5.7+tut1

Show diffs side-by-side

added added

removed removed

Lines of Context:
weka/classifiers/misc/monotone/MultiDimensionalSort.java
 
1
/*
 
2
 *    This program is free software; you can redistribute it and/or modify
 
3
 *    it under the terms of the GNU General Public License as published by
 
4
 *    the Free Software Foundation; either version 2 of the License, or
 
5
 *    (at your option) any later version.
 
6
 *
 
7
 *    This program is distributed in the hope that it will be useful,
 
8
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
 *    GNU General Public License for more details.
 
11
 *
 
12
 *    You should have received a copy of the GNU General Public License
 
13
 *    along with this program; if not, write to the Free Software
 
14
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
15
 */
 
16
 
 
17
/*
 
18
 *    MultiDimensionalSort.java
 
19
 *    Copyright (C) 2004 Stijn Lievens
 
20
 *
 
21
 */
 
22
 
 
23
package weka.classifiers.misc.monotone;
 
24
 
 
25
import java.util.Arrays;
 
26
import java.util.Comparator;
 
27
 
 
28
/** 
 
29
 * Class for doing multidimensional sorting, using an array of
 
30
 * <code> Comparator. </code>
 
31
 * The goal is to sort an array topologically.  If <code> o1 </code>
 
32
 * and <code> o2 </code> are two objects of the array <code> a, </code>
 
33
 * and for all valid indices <code> i </code> in the array <code> c </code>
 
34
 * if holds that <code> c[i].compare(o1,o2) &lt; 0 </code> then
 
35
 * <code> o1 </code> comes before <code> o2 </code> in the sorted array.
 
36
 * <p>
 
37
 * A typical is the sorting of vectors in an n-dimensional space,
 
38
 * where the ordering is determined by the product ordering.
 
39
 * </p>
 
40
 * <p>
 
41
 * This implementation is part of the master's thesis: "Studie
 
42
 * en implementatie van instantie-gebaseerde algoritmen voor gesuperviseerd
 
43
 * rangschikken", Stijn Lievens, Ghent University, 2004. 
 
44
 * </p>
 
45
 * 
 
46
 * @author Stijn Lievens (stijn.lievens@ugent.be)
 
47
 * @version $Revision: 1.1 $
 
48
 */
 
49
public class MultiDimensionalSort {
 
50
 
 
51
  /** 
 
52
   * Sort an array using different comparators.
 
53
   *
 
54
   * @param a the array to be sorted.  The sorted array is returned 
 
55
   * in the array <code> a </code> itself.
 
56
   * @param c an array holding the different comparators
 
57
   */
 
58
  public static void multiDimensionalSort (Object[] a, Comparator[] c) {
 
59
    multiDimensionalSort(a, 0, a.length, c);
 
60
  }
 
61
 
 
62
  /** 
 
63
   * Sort part of an array using different comparators.
 
64
   * 
 
65
   * @param a the array to be sorted, the indicated part of the array will
 
66
   * be replaced by the sorted elements
 
67
   * @param fromIndex index of the first element to be sorted (inclusive)
 
68
   * @param toIndex index of the last element to be sorted (exclusive)
 
69
   * @param c array holding the different comparators
 
70
   * @throws IllegalArgumentException if <code> fromIndex &gt; toIndex </code>
 
71
   */
 
72
  public static void multiDimensionalSort(Object[] a, int fromIndex,
 
73
      int toIndex, Comparator[] c) 
 
74
    throws IllegalArgumentException {
 
75
    
 
76
    if (fromIndex > toIndex) {
 
77
      throw new IllegalArgumentException
 
78
      ("Illegal range: fromIndex can be at most toIndex");
 
79
    }
 
80
    multiDimensionalSort(a, fromIndex, toIndex, c, 0);
 
81
  }
 
82
 
 
83
  /**
 
84
   * Do the actual sorting in a recursive way.
 
85
   * 
 
86
   * @param a the array to be sorted, the indicated part of the array will
 
87
   * be replaced by the sorted elements
 
88
   * @param fromIndex index of the first element to be sorted (inclusive)
 
89
   * @param toIndex index of the last element to be sorted (exclusive)
 
90
   * @param c array holding the different comparators
 
91
   * @param depth the index of the comparator to use
 
92
   */
 
93
  private static void multiDimensionalSort(Object[] a, int fromIndex,
 
94
      int toIndex, Comparator[] c, int depth) {
 
95
 
 
96
    if (depth == c.length) {
 
97
      return; // maximum depth reached
 
98
    }
 
99
 
 
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
}
 
116
 
 
117