001 /* 002 * Sort 003 * 004 * Copyright (c) 2001, 2002, 2003 Marco Schmidt. 005 * All rights reserved. 006 */ 007 008 package net.sourceforge.jiu.util; 009 010 import net.sourceforge.jiu.util.ComparatorInterface; 011 012 /** 013 * Provides sorting of an Object array. 014 * @author Marco Schmidt 015 */ 016 public class Sort 017 { 018 /** 019 * This class is supposed to have static methods only. 020 * To hide any constructor, we define an empty private one. 021 */ 022 private Sort() 023 { 024 } 025 026 /** 027 * Sorts some (or all) elements of an Object array according to a specified comparator. 028 * This method does exactly the same as java.util.Arrays.sort(Object[], int, int, Comparator). 029 * Unfortunately, this method is not available in Java 1.1, so it must be provided here. 030 * <p> 031 * As for the implementation of this method, it is taken from Arrays.java as found in 032 * Classpath 0.0.2 (2001-01-06). 033 * Go to <a href="http://www.classpath.org">www.classpath.org</a> to learn more 034 * about the project, which implements the Java core libraries under the GPL. 035 * 036 * @param a the array which is to be sorted 037 * @param from the index value of the first element of the interval to be sorted 038 * @param to the index value of the last element of the interval to be sorted 039 * @param c the comparator used to query the relation between two objects 040 */ 041 public static void sort(Object[] a, int from, int to, ComparatorInterface c) 042 { 043 if (a == null) 044 { 045 throw new IllegalArgumentException("The object array to be sorted must be non-null."); 046 } 047 if (from > to) 048 { 049 throw new IllegalArgumentException("The from parameter (" + from + ") must be smaller than or equal to the to parameter (" + to + ")."); 050 } 051 if (to >= a.length) 052 { 053 throw new IllegalArgumentException("The to parameter (" + to + ") must be smaller than the array length (" + a.length + ")."); 054 } 055 if (c == null) 056 { 057 throw new IllegalArgumentException("The comparator parameter must be non-null."); 058 } 059 // First presort the array in chunks of length 6 with insertion sort. 060 // mergesort would give too much overhead for this length. 061 for (int chunk = from; chunk < to; chunk += 6) 062 { 063 int end = Math.min(chunk + 6, to); 064 for (int i = chunk + 1; i < end; i++) 065 { 066 if (c.compare(a[i - 1], a[i]) > 0) 067 { 068 // not already sorted 069 int j = i; 070 Object elem = a[j]; 071 do 072 { 073 a[j] = a[j - 1]; 074 j--; 075 } 076 while (j > chunk && c.compare(a[j - 1], elem) > 0); 077 a[j] = elem; 078 } 079 } 080 } 081 082 int len = to - from; 083 // If length is smaller or equal 6 we are done. 084 if (len <= 6) 085 return; 086 087 Object[]src = a; 088 Object[]dest = new Object[len]; 089 Object[]t = null; // t is used for swapping src and dest 090 091 // The difference of the fromIndex of the src and dest array. 092 int srcDestDiff = -from; 093 094 // The merges are done in this loop 095 for (int size = 6; size < len; size <<= 1) 096 { 097 for (int start = from; start < to; start += size << 1) 098 { 099 // mid ist the start of the second sublist; 100 // end the start of the next sublist (or end of array). 101 int mid = start + size; 102 int end = Math.min(to, mid + size); 103 104 // The second list is empty or the elements are already in 105 // order - no need to merge 106 if (mid >= end || c.compare(src[mid - 1], src[mid]) <= 0) 107 { 108 System.arraycopy(src, start, 109 dest, start + srcDestDiff, end - start); 110 111 // The two halves just need swapping - no need to merge 112 } 113 else if (c.compare(src[start], src[end - 1]) > 0) 114 { 115 System.arraycopy(src, start, 116 dest, end - size + srcDestDiff, size); 117 System.arraycopy(src, mid, 118 dest, start + srcDestDiff, end - mid); 119 120 } 121 else 122 { 123 // Declare a lot of variables to save repeating 124 // calculations. Hopefully a decent JIT will put these 125 // in registers and make this fast 126 int p1 = start; 127 int p2 = mid; 128 int i = start + srcDestDiff; 129 130 // The main merge loop; terminates as soon as either 131 // half is ended 132 while (p1 < mid && p2 < end) 133 { 134 dest[i++] = 135 src[c.compare(src[p1], src[p2]) <= 0 ? p1++ : p2++]; 136 } 137 138 // Finish up by copying the remainder of whichever half 139 // wasn't finished. 140 if (p1 < mid) 141 System.arraycopy(src, p1, dest, i, mid - p1); 142 else 143 System.arraycopy(src, p2, dest, i, end - p2); 144 } 145 } 146 // swap src and dest ready for the next merge 147 t = src; 148 src = dest; 149 dest = t; 150 from += srcDestDiff; 151 to += srcDestDiff; 152 srcDestDiff = -srcDestDiff; 153 } 154 155 // make sure the result ends up back in the right place. Note 156 // that src and dest may have been swapped above, so src 157 // contains the sorted array. 158 if (src != a) 159 { 160 // Note that from == 0. 161 System.arraycopy(src, 0, a, srcDestDiff, to); 162 } 163 } 164 165 /** 166 * Sort the complete argument array according to the argument comparator. 167 * Simply calls <code>sort(a, 0, a.length - 1, comparator);</code> 168 * @param a array to be sorted 169 * @param comparator the comparator used to compare to array entries 170 */ 171 public static void sort(Object[] a, ComparatorInterface comparator) 172 { 173 sort(a, 0, a.length - 1, comparator); 174 } 175 }