Java Generics и Infinity (сопоставимо)

Question

С типом 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.

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

Answer 1

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

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

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

Integer.MIN_VALUE, "" ИЛИ NULL.

Я предполагаю, что вы ищете K.MIN_VALUE_OF_EVENTUAL_TYPE, но его не существует.

Answer 2

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

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

Answer 3

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

ПРЕДУПРЕЖДЕНИЕ: Этот код опасен.Пожалуйста, будьте милосердны ко мне за публикацию такой мерзости.Это всего лишь подтверждение концепции.

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

Answer 4

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

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

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

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

Answer 6

А разве это не зависит от типа К?

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

Answer 7

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

Answer 8

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

Answer 9

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

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

Answer 10

Подумайте о том, чтобы не делать 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песок Integerна одном дереве полностью вас уничтожит.