Génériques Java et Infinity (comparables)

Question

Avec le type Integer, vous pouvez faire ceci:

int lowest = Integer.MIN_VALUE;

Que puis-je faire si j'utilise des génériques?

K lowest = <...>;

J'en ai besoin pour mettre en œuvre quelque chose de similaire à une PriorityQueue. J'ai accès à un noeud que je veux supprimer de la file d'attente, mais ce n'est pas le minimum.

1. I need to make it the min by decreasing the key of that node,
2. And then remove the min.

Je suis coincé sur la première marche. La seule chose que je puisse faire est de définir la clé du nœud sur le min en cours. Pas sûr que ce soit suffisant.

Answer 1

Cela n’a aucun sens ...

Etant donné que vous ne savez pas ce que K est à ce moment-là, (c'est-à-dire que vous l'implémentez de manière générique ... duh!), vous ne pouvez pas spécifier de limite min / max pour cela.

dans le cas où K pourrait être un objet int, long, string OU, vous ne pouviez pas deviner utiliser

Integer.MIN_VALUE, "" OU NULL.

Je suppose que ce que vous recherchez est un K.MIN_VALUE_OF_EVENTUAL_TYPE mais cela n'existe pas.

Answer 2

Il n'y a pas de forme générique de MIN_VALUE ou MAX_VALUE pour tous les types comparables.

Pensez à une classe Time qui implémente comparable. Il n'y a pas de MAX_VALUE pour Time, même s'il est comparable.

Answer 3

J'essaie d'imaginer quel scénario exigerait un tel comportement. C’est ce que je peux faire de mieux.

AVERTISSEMENT: ce code est dangereux. S'il vous plaît, soyez miséricordieux envers moi pour avoir posté une telle abomination. Ce n'est qu'une preuve de concept.

public class Lowest<K> implements Comparable<K> {
    public int compareTo(K other) {
        return -1;
    }
}

Et ensuite ...

public class Test {
    public <K extends Comparable<K>> K findMaximum(List<K> values) throws Exception {
        K lowest = (K) new Lowest<K>(); /// XXX DANGER! Losing compile-time safety!!!

        K maximum = lowest;
        for (K value : values) {
            if (maximum.compareTo(value) < 0) {
                maximum = value;
            }
        }

        if (maximum == lowest) {
            throw new Exception("Could not find a maximum value");
        } else {
            return maximum;
        }
    }
}

Answer 4

Vous pouvez créer une classe wrapper que " ajoute " une valeur minimale et maximale pour tous les types. Il ne contient que deux instances statiques qui représentent le minimum et le maximum, puis d'autres instances encapsulent une autre valeur d'un type. Lorsque nous faisons une comparaison, nous vérifions si l’un des éléments est minimum ou maximum et nous renvoyons le résultat correct. et sinon nous faisons juste la même comparaison que le type sous-jacent. Quelque chose comme ça:

class Extended<T extends Comparable<? super T>> implements Comparable<Extended<T>> {
    private Extended() { }

    private static Extended min = new Extended();
    private static Extended max = new Extended();

    @SuppressWarnings("unchecked")
    public static <T extends Comparable<? super T>> Extended<T> getMin() {
        return (Extended<T>)min;
    }
    @SuppressWarnings("unchecked")
    public static <T extends Comparable<? super T>> Extended<T> getMax() {
        return (Extended<T>)max;
    }

    public T value;

    public Extended(T x) { value = x; }

    public int compareTo(Extended<T> other) {
        if (this == other) return 0;
        else if (this == min || other == max) return -1;
        else if (this == max || other == min) return 1;
        else return this.value.compareTo(other.value);
    }
}

Answer 5

euh ... quel est le problème encore?

PriorityQueue , comme tous < a href = "http://java.sun.com/javase/6/docs/api/java/util/Collection.html#remove(java.lang.Object)" rel = "nofollow noreferrer"> Collections , vous permet d'utiliser une instance d'objet pour supprimez-le de la collection.

Answer 6

Euh, cela ne dépend-il pas du type K?

Le point générique est que K peut être n’importe quel type (ou n’importe quelle sous-classe d’un certain type); pour pouvoir appeler des méthodes sur K ou accéder à leurs propriétés, vous devez limiter les limites de type avec des caractères génériques.

Answer 7

Ce n’est pas parce qu’un objet est comparable qu’il doit avoir une valeur minimale. La raison pour laquelle int a une valeur minimale de - (2 ^ (31)) est due au fait que vous avez besoin de 1 bit pour un signe. Par conséquent, 2 ^ 31 est le plus grand (ou le plus petit) nombre entier pouvant être stocké. Pour des choses comme chaîne, cela n’a aucun sens car il n’ya pas de chaîne la plus grande / la plus petite possible, elle est liée à la mémoire.

Answer 8

Vous devrez peut-être créer une interface "IInfinity", et que K étend IInfinity et IInfinity pour avoir une méthode "getInfinityValue ()", puis encapsuler / étendre Integer, Double, BigDecimal, etc. dans une classe. qui met en œuvre IInfinity ... et pouah!

Answer 9

En principe, vous souhaitez que tout type K implémente certaines fonctions statiques dites minimum et maximum, qui obéissent aux propriétés mathématiques standard.

Je suppose que pour que ce sens de plus bas (ou plus haut) soit utilisable, vous voudriez que tout objet Comparable ait ces méthodes. (ou champs statiques). Si vous ne vous intéressez qu'à vos propres objets personnalisés, vous pouvez tout faire en sorte que tout hérite d'un type de données abstrait qui déclare des champs statiques pour MINVALUE et MAX_VALUE, puis que votre type varie. Si vous avez besoin de cette fonctionnalité pour d’autres classes, vous devrez créer une sorte de hashmap externe qui suit ces propriétés pour différentes classes (mais cela deviendrait plutôt moche)

Answer 10

Ne considérez pas que K est générique, mais utilisez une interface qui enveloppe le wrapper primitif (un double wrapper!).

import java.util.HashMap;


public class NodeWrapper<K extends Comparable<K>> implements Comparable<NodeWrapper<K>> {

    private static HashMap<Class, NodeWrapper> minVals = new HashMap<Class, NodeWrapper>();

    private K value;

    private NodeWrapper() {
        super();
    }

    public NodeWrapper(K value, Class<K> clazz) {
        super();
        this.value = value;

        if (minVals.get(clazz)==null) {
            minVals.put(clazz, new NodeWrapper<K>());
        }
    }

    public K getValue() {
        return value;
    }

    public static NodeWrapper getMinValue(Class clazz){
        return minVals.get(clazz);
    }

    public void setValue(K value) {
        this.value = value;
    }

    @Override
    public int compareTo(NodeWrapper<K> o) {
        NodeWrapper min = minVals.get(this.getClass());
        if (this==min && o==min)  {
            return 0;
        } else if (this==min){
            return -1;
        } else if (o==min){
            return 1;
        } else {
            return this.value.compareTo(o.value);
        }
    }

}

En résumé, l’idée est que chaque fois qu’une nouvelle classe est instanciée, une valeur minimale est créée et insérée dans une table de hachage statique qui stocke les valeurs minimales pour chaque classe. (En fait, ces valeurs ne sont RIEN, un objet sentinelle, mais puisque nous utiliserons l'égalité des objets pour déterminer si quelque chose correspond à la valeur min, ce n'est pas du tout un problème.) Il suffit que l'objet enveloppé soit comparable. à d'autres instances d'elle-même en général.

Un inconvénient est que lorsque vous appelez getMinValue , vous recevez des avertissements pour le compilateur, car le type de résultat ne contient aucune information générique. Il y a peut-être une manière plus élégante de contourner cela, mais je ne peux pas y penser maintenant.

Cette idée générale pourrait être plutôt bonne dans l’ensemble. Cependant, je devrais vraiment souligner: cela cassera absolument si vous l'essayez avec un polymorphisme ou un mélange de classes mutuellement comparables. Les longs et les Entiers dans le même arbre vont vous détruire complètement.