I am writing a merge sort algorithms, so I want all the methods take arguments that implements Comparable interface, i.e. having a method called compareTo.
I have been told many times to avoid using raw type in new code. But I can't find a right way to replace them.
public class Merge{
private static Comparable[] aux;
private Merge() {}
private static boolean less(Comparable v,Comparable w){
int sign=v.compareTo(w);
if (sign==0) throw new IllegalArgumentException("Repeated points");
return sign<0;
}
private static void exch(Comparable[] a,int i,int j){
Comparable swap =a[i];
a[i]=a[j];
a[j]=swap;
}
private static void insertSort(Comparable[] a,int lo,int hi){
for(int i=lo;i<hi+1;++i){
for(int j=i;j>lo;--j){
if(less(a[j],a[j-1]))
exch(a,j,j-1);
else
break;
}
}
}
private static void merge(Comparable[] a,Comparable[] aux,int lo,int mid,int hi){
for(int k=lo;k!=hi+1;++k){
aux[k]=a[k];
}
int i=lo,j=mid+1;
for(int k=lo;k!=hi+1;++k){
if(i>mid){
a[k]=aux[j++];
}
else if(j>hi){
a[k]=aux[i++];
}
else if(less(aux[j],aux[i])){
a[k]=aux[j++];
}
else{
a[k]=aux[i++];
}
}
}
private static void sort(Comparable[] a, Comparable[] aux,int lo,int hi){
if(hi<=lo+6){
insertSort(a,lo,hi);
return;
}
int mid=lo+ (hi-lo)/2;
sort(a,aux,lo,mid);
sort(a,aux,mid+1,hi);
if(!less(a[mid+1],a[mid])) return;
merge(a,aux,lo,mid,hi);
}
private static void sort(Comparable[] a){
aux=new Comparable[a.length];
sort(a,aux,0,a.length-1);
}
}
The question What is a raw type and why shouldn't we use it? is different from mine. Actually, I have read the question before. Still, I don't know how toa avoid using Comparable here.
Whereever you have Comparable, use T. And declare T as <T extends Comparable<? super T>>.
You will face a problem with array creation, though. There are two ways how to bypass that. You could clone the original array and clear it in case you need it to be initialized with null, or you could use Reflection to create the array.
public class Merge {
private Merge() {
}
private static <T extends Comparable<? super T>> boolean less(T v, T w) {
int sign = v.compareTo(w);
if (sign == 0) throw new IllegalArgumentException("Repeated points");
return sign < 0;
}
private static <T extends Comparable<? super T>> void exch(T[] a, int i, int j) {
T swap = a[i];
a[i] = a[j];
a[j] = swap;
}
private static <T extends Comparable<? super T>> void insertSort(T[] a, int lo, int hi) {
for (int i = lo; i < hi + 1; ++i) {
for (int j = i; j > lo; --j) {
if (less(a[j], a[j - 1]))
exch(a, j, j - 1);
else
break;
}
}
}
private static <T extends Comparable<? super T>> void merge(T[] a, T[] aux, int lo, int mid, int hi) {
for (int k = lo; k != hi + 1; ++k) {
aux[k] = a[k];
}
int i = lo, j = mid + 1;
for (int k = lo; k != hi + 1; ++k) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (less(aux[j], aux[i])) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
private static <T extends Comparable<? super T>> void sort(T[] a, T[] aux, int lo, int hi) {
if (hi <= lo + 6) {
insertSort(a, lo, hi);
return;
}
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
if (!less(a[mid + 1], a[mid])) return;
merge(a, aux, lo, mid, hi);
}
private static <T extends Comparable<? super T>> void sort(T[] a) {
T[] aux = a.clone();
sort(a, aux, 0, a.length - 1);
}
}
You can do away with the repetition of the type parameter <T extends Comparable<? super T>> and also the repetition of a and aux if you use a method object.
public enum Merge {
;
private static class Merger<T extends Comparable<? super T>> {
private final T[] a;
private final T[] aux;
private Merger(T[] a) {
this.a = a;
aux = a.clone();
}
private boolean less(T v, T w) {
int sign = v.compareTo(w);
if (sign == 0) throw new IllegalArgumentException("Repeated points");
return sign < 0;
}
private void exch(int i, int j) {
T swap = a[i];
a[i] = a[j];
a[j] = swap;
}
private void insertSort(int lo, int hi) {
for (int i = lo; i < hi + 1; ++i) {
for (int j = i; j > lo; --j) {
if (less(a[j], a[j - 1]))
exch(j, j - 1);
else
break;
}
}
}
private void merge(int lo, int mid, int hi) {
for (int k = lo; k != hi + 1; ++k) {
aux[k] = a[k];
}
int i = lo, j = mid + 1;
for (int k = lo; k != hi + 1; ++k) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (less(aux[j], aux[i])) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
private void sort(int lo, int hi) {
if (hi <= lo + 6) {
insertSort(lo, hi);
return;
}
int mid = lo + (hi - lo) / 2;
sort(lo, mid);
sort(mid + 1, hi);
if (!less(a[mid + 1], a[mid])) return;
merge(lo, mid, hi);
}
private void sort() {
sort(0, a.length - 1);
}
}
public static <T extends Comparable<? super T>> void sort(T[] a) {
new Merger<>(a).sort();
}
}