Java Generics и Infinity (сопоставимые) - PullRequest
5 голосов
/ 29 апреля 2009

С типом Integer вы можете сделать это:

int lowest = Integer.MIN_VALUE;

Что я могу сделать, если я использую дженерики?

K lowest = <...>;

Мне это нужно для реализации чего-то похожего на PriorityQueue. У меня есть доступ к узлу, который я хочу удалить из очереди, но это не мин.

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

Я застрял на первом шаге. Единственное, что я могу сделать, это установить ключ узла на текущий минимум. Не уверен, что этого достаточно.

Ответы [ 10 ]

4 голосов
/ 29 апреля 2009

Не существует общей формы MIN_VALUE или MAX_VALUE для всех сопоставимых типов.

Подумайте о Time классе, который реализует сопоставимые. Времени не существует MAX_VALUE, хотя оно сопоставимо.

4 голосов
/ 29 апреля 2009

Я пытаюсь представить, какой сценарий потребует такого поведения. Это лучшее, что я могу придумать ...

ВНИМАНИЕ: Этот код опасен. Пожалуйста, будь милостив ко мне за публикацию такой мерзости. Это только подтверждение концепции.

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

А потом ...

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;
        }
    }
}
4 голосов
/ 29 апреля 2009

Это не имеет никакого смысла ...

Учитывая, что вы не знаете, что такое K на тот момент, (т.е. вы реализуете его в общем ... дух!), Вы не можете указать минимальную / максимальную границы для него.

в случае, когда K может быть объектом типа int, long, string OR, вы не могли бы разумно предположить использовать

Integer.MIN_VALUE, "" OR NULL.

Полагаю, вы ищете K.MIN_VALUE_OF_EVENTUAL_TYPE, но его не существует.

3 голосов
/ 30 апреля 2009

Вы можете создать класс-оболочку, который «добавляет» минимальное и максимальное значение ко всем типам. Он просто имеет два статических экземпляра, которые представляют минимальный и максимальный значения, а затем другие экземпляры переносят какое-то другое значение некоторого типа. Когда мы делаем сравнение, мы проверяем, является ли одна из вещей минимальным или максимальным, и возвращаем правильный результат; и иначе мы просто делаем то же самое сравнение как базовый тип. Примерно так:

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);
    }
}
2 голосов
/ 30 апреля 2009

э-э ... в чем проблема?

PriorityQueue , как и все Коллекции , позволяет использовать экземпляр объекта для удаления его из коллекции.

1 голос
/ 30 апреля 2009

Не стоит делать K универсальным, а использовать интерфейс, который обертывает примитивную оболочку (двойную оболочку!).

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);
        }
    }

}

Вкратце, идея заключается в том, что всякий раз, когда создается новый класс, создается минимальное значение и помещается в статическую хэш-карту, в которой хранятся минимальные значения для каждого класса. (На самом деле, эти значения вообще НИЧЕГО, просто объект-страж, но поскольку мы будем использовать равенство объектов, чтобы определить, является ли что-то минимальным значением, это вообще не проблема.) Все, что необходимо, - это сопоставить упакованный объект в других случаях сам по себе в целом.

Один недостаток заключается в том, что при вызове getMinValue вы будете получать предупреждения компилятора, поскольку тип возвращаемого значения не будет иметь общей информации. Может быть, есть более изящный способ обойти это, но я не могу сейчас об этом думать.

Эта общая идея может быть довольно хорошей в целом. Тем не менее, я должен действительно подчеркнуть: это будет абсолютно сломано, если вы попробуете это с любым полиморфизмом или любым смешением взаимно сопоставимых классов. Long s и Integer s в одном и том же дереве полностью уничтожат вас.

1 голос
/ 29 апреля 2009

По сути, вы хотите, чтобы любой тип K реализовывал некоторые статические функции, скажем, самые низкие и самые высокие, которые подчиняются стандартным математическим свойствам.

Я предполагаю, что для того, чтобы использовать это чувство самого низкого (или самого высокого) значения, вы бы хотели, чтобы у любого сопоставимого объекта были эти методы. (или статические поля). Если вас интересуют только ваши собственные пользовательские объекты, способ сделать это состоял бы в том, чтобы все наследовало от абстрактного типа данных, который объявил статические поля для MINVALUE и MAX_VALUE, а затем ваш тип varaible. Если вам нужна эта функциональность для других классов, вам нужно создать какой-нибудь внешний хэш-файл, который отслеживает эти свойства для разных классов (но это может быть довольно уродливо)

1 голос
/ 29 апреля 2009

Возможно, вам придется создать интерфейс "IInfinity", и иметь K, расширяющий IInfinity и IInfinity, чтобы иметь метод "getInfinityValue ()", а затем обернуть / расширить Integer, Double, BigDecimal и т. Д. В классе, который реализует IInfinity ... и тьфу!

1 голос
/ 29 апреля 2009

только потому, что объект сопоставим, не означает, что он должен иметь минимальное значение. Причина, по которой int имеет минимальное значение - (2 ^ (31)), заключается в том, что для знака требуется 1 бит, поэтому 2 ^ 31 - это наибольшее (или наименьшее) возможное целое число, которое можно сохранить. Для таких вещей, как строка, это не имеет никакого смысла, так как нет наибольшей / наименьшей возможной строки, она ограничена памятью.

1 голос
/ 29 апреля 2009

Э-э, это не зависит от типа К?

Смысл Обобщения заключается в том, что K может быть любого типа (или любого подкласса определенного типа); чтобы иметь возможность вызывать методы для K или обращаться к его свойствам, вам нужно ограничить границы его типов с помощью подстановочных знаков.

...