java - ¿Debería compararse Comparable con otro tipo?

Question

Me pregunto si alguna vez hay un caso de uso válido para lo siguiente:

class Base {}

class A implements Comparable<Base> {
    //...
}

Parece ser un patrón común (consulte Collections para ver varios ejemplos) aceptar una colección de tipo T , donde T extends Comparable<? super T> T extends Comparable<? super T> .

Pero parece técnicamente imposible cumplir el contrato de compareTo() cuando se compara con una clase base, porque no hay forma de asegurar que otra clase no extienda la base con una comparación contradictoria. Considere el siguiente ejemplo:

class Base {
    final int foo;
    Base(int foo) {
        this.foo = foo;
    }
}

class A extends Base implements Comparable<Base> {
    A(int foo) {
        super(foo);
    }
    public int compareTo(Base that) {
        return Integer.compare(this.foo, that.foo); // sort by foo ascending
    }
}

class B extends Base implements Comparable<Base> {
    B(int foo) {
        super(foo);
    }
    public int compareTo(Base that) {
        return -Integer.compare(this.foo, that.foo); // sort by foo descending
    }
}

Tenemos dos clases que amplían la Base utilizando comparaciones que no siguen una regla común (si hubiera una regla común, es casi seguro que se implementaría en la Base ). Sin embargo, la siguiente clasificación rota se compilará:

Collections.sort(Arrays.asList(new A(0), new B(1)));

¿No sería más seguro aceptar solo las extensiones T extends Comparable<T> ? ¿O hay algún caso de uso que validaría el comodín?

Answer 1

Esta es una muy buena pregunta. Primero, comencemos con la razón por la cual las Collections usan métodos como

binarySearch(List<? extends Comparable<? super T>> list, T key)

De hecho, ¿por qué no solo

binarySearch(List<? extends Comparable<T>> list, T key)

La razón de esto es el principio de PECS : Producer Extends, Consumer Super. ¿Qué hace binarySearch ? Lee los elementos de la lista y luego los compara al pasar sus valores a la función compareTo . Dado que lee los elementos, la lista actúa como un productor y, por lo tanto, la primera parte: Producer Extiende. Este es obvio, entonces, ¿qué pasa con la parte Super Consumo?

Consumer Super básicamente significa que si solo vas a pasar valores a alguna función, realmente no te importa si acepta el tipo exacto de tu objeto o una superclase de él. Entonces, lo que dice la declaración binarySearch es: puedo buscar cualquier cosa siempre y cuando se pueda pasar algo al método compareTo de los elementos de la lista.

En el caso de la clasificación no es tan obvio, porque los elementos solo se comparan entre sí. Pero incluso entonces, ¿qué sucede si la Base implementa la Comparable<Base> (y la comparación completa) y A y B simplemente extienden la Base sin tocar la comparación de ninguna manera? Entonces no podrá ordenar las listas de A y B porque no implementan Comparable<A> y Comparable<B> respectivamente. ¡Tendría que volver a implementar la interfaz completa cada vez que realice una subclase!

Otro ejemplo: ¿qué pasaría si alguien quisiera hacer una búsqueda binaria en una lista que contenga instancias de alguna clase que ni siquiera extienda su Base ?

class BaseComparable implements Comparable<Base> {
    private final Base key;
    // other fields

    BaseComparable(Base key, ...) {
        this.key = key;
        // other fields initialization
    }

    @Override
    public int compareTo(Base otherKey) {
        return this.key.compareTo(otherKey);
    }
};

Y ahora quieren usar una instancia de A como la clave para esta búsqueda binaria. ¿Solo pueden hacerlo por el ? super T ? super T parte. Tenga en cuenta que esta clase no tiene idea de si la clave es una A o una B por lo que no es posible implementar Comparable<A/B> .

En cuanto a su ejemplo, supongo que es solo un ejemplo de diseño deficiente. Desafortunadamente, no veo ninguna manera de prevenir tales cosas sin romper el principio de PECS y / o limitar la funcionalidad ya limitada de los genéricos de Java.

Answer 2

La restricción

    T extends Comparable<? super T>

debe entenderse como

    T extends S, S extends Comparable<S>

Un tipo Comparable es siempre auto-comparativo.

Si X <: Comparable<Y> , debe darse el caso de que X <: Y <: Comparable<Y> .

Incluso podríamos "probar" eso del contrato de compareTo() . Dado que se debe definir el reverso y.compareTo(x) , debe ser cierto que Y <: Comparable<A>, X<:A Siguiendo el mismo argumento, tenemos A <: Comparable<Y> . Entonces la transitividad conducirá a A=Y