arrays - Same sorting algorithm for objects of different classes (Java)

Question

Right now I have a sorting algorithm that takes an array of objects in random order, sorts them into a new array based on a value attribute and returns the sorted array (Specifically an ArrayList altough I don't belive it will be relevant for my question). For my assignment I have now been instructed to sort another array of different objects, from order of highest to lowest based on these different objects' own value attributes. Instead of copypasting my already implemented algorithm altough changing object and attribute name in a couple of places or just straight up sorting the other objects in O(n^2) order, I would like to somehow reuse my current algorithm in a more general manner. To be more clear:

new Array<ClassA> a;
new Array<ClassB> b;

public Array<ClassB> sort(Array<ClassB> input){
    //sort based on certain attribute in ClassB;
    return sortedArray;
}

I wish to turn into:

new Array<ClassA> a;
new Array<ClassB> b;

public Array<ClassB> sort(Array<Object> input, Attribute x){
    //sort based on attribute of Object where which attribute is given as a parameter x;
    return sortedArray;
}

I understand this might come of as even more confusing than my written explanation so to be even MORE clear (I hope) I wish to turn my sorting algorithm into something simillar to this built in function from python: sorted(iterable, key=None, reverse=False)

The algorithm I have implemented is part of the assignment so I can't replace it with something from a library. If you thought my entire question was dumb, then please consider that english is not my native language, no - I am not quite familiar at all with programming terminology and yes - I am quite a terrible programmer. Then move on with your day! If you think you can provide me a reasonable answer however, it would be much appreciated :D

question from:https://stackoverflow.com/questions/65649483/same-sorting-algorithm-for-objects-of-different-classes-java

Answer 1

public Array<ClassB> sort(Array<Object> input, Attribute x){

this turns an array of arbitrary objects into an array containing instances of ClassB, which obviously insn't how it works.

Array<Object> input

This doesn't mean what you think it means. An Array<ClassB> is NOT a valid value for Array<Object>. After all, I can add a String to an Array<Object> (a String is an object!), but I can't add one to an Array<ClassB>. In computer tech terms, basic types in java (like Number and Integer) are covariant - any instance that is a subtype of X is also an X: An Integer is also a Number, is also an Object. But type args are invariant. Any instance that is a subtype of X, isn't compatible with X: a List<Integer> is not a List<Number>. This is because that's just how it works, as I showed above: You can add doubles to a List<Number>.

You can pick different variances: List<? extends Number> or List<? super Number> do this. You don't need it for this problem, though.

Generics link things. That's what you want here: Take in an array of some.. thing, and return an array of the same thing:

public <T> Array<T> sort(Array<T> input, Attribute x) {}

This says: There is some type T. No idea what it is. This T then serves to link things: Whatever the type of the input array? the output array has the same type.

Which is what you want.

Attribute x

It is not possible to refer to attributes in a programmatic manner. Fortunately, you don't actually need an attribute. You need a function: Given some T, provide a value; one that you now how to sort inherently. How this function works? You don't care. Long as it is consistent (returns the same value for any given instance), you can then sort it all based on that mapped value. So, you don't want Attribute, you want a function that turns a T into some thing you can sort. You have three options:

Go on a spree, listing every sortable concept you have.

public <T> Array<T> sortByInt(Array<T> input, ToIntFunction<T> f) {}
public <T> Array<T> sortByString(Array<T> input, Function<T, String> f) {}
public <T> Array<T> sortByDouble(Array<T> input, ToDoubleFunction<T, String> f) {}

etcetera. These methods really need different names, you don't want overloading here.

Map to object and pray

You have no idea how to sort any given object. You presumably only know how to sort integer, double, and string. You could write:

public <T> Array<T> sortByDouble(Array<T> input, Function<T, ?> f) {}

and then do checks at runtime if the function maps to what you wanted. If the function maps to, say, an InputStream, which is obviously not a thing you can sort, you'd have to check it, and throw an exception. It also gets quite confusing if one object is mapped to an int and another to a string. This sounds simple, but it isn't. Do not do this.

Use java' built in concept of self-ordered stuff.

Java has a type for this: Comparable. This gets a little complex; you want, here, that the objects can compare themselves to themselves, so:

public <T, V extends Comparable<V>> Array<T> sort(Array<T> input, Function<T, V> f) {}

That is getting a little complex, but it is the most correct version. Let's go through it:

• The <T, V... > part: This says that this method has 2 type variables. They are like normal variables, except they hold types.
• The T: It has no bounds whatsoever. Thus, it can be anything. Any code that calls this method will either explicitly pick something, or the compiler will figure it out.
• The V: This has bounds. V cannot just be anything. V must be some type that has the property that it implements Comparable<V> - in other words, a thing that can compare itself to another value of its own type. String, Integer, and many other things built into java are like this. String is a valid type to fill in for V.
• Array<T> - what the method returns.
• sort - the method name
• Array<T> input - the input. Note that this is linked to the return type.
• Function<T, V> - a function. This function will take in an object of type T and returns an object of type V. Remember, V can't just be anything - it needs to be some specific type that can order itself vs. something else of the same type, such as String or Integer.

With all this, you can write some code. For example:

T first = input.get(0); // still no idea what T is. But `input.get(0)` returns it.
T second = input.get(1);
V firstAttribute = function.apply(first); // extracts the sortable attribute
V secondAttribute = function.apply(second);
int ordering = firstAttribute.compareTo(secondAttribute); // magic!

That last line is a marvel. It compiles, and is guaranteed to work: firstAttribute is a V, and whilst we have no idea what V is (could be String. Could also be Integer), we do know that V has the int compareTo(V other) method. So, we can invoke that. A negative number means first is before second, a positive means first is after second, and a 0 response means first and second are either equal or, as far as comparing them is concerned, siblings - neither is 'before' the other.

That function is all you need to write sort algorithms.

Note ethat, given that first is a T, you can write:

Array<T> output = new Array<T>();
output.add(first);

The compiler does not know what T is, but it does know that first is a T, so this call is allowed.