Сортировка дженериков в Java - PullRequest
Новая
       24

Сортировка дженериков в Java

1 голос
/ 16 апреля 2011

Я должен реализовать общее дерево AVL в качестве домашней работы. Это определяется следующим образом: 

public class AVL<Key,Elem>;

Проблема в том, что я предполагаю, что в какой-то момент мне придется сравнивать ключи, чтобы решить, на какой стороне узла я выделяю элемент. Для выполнения этой домашней работы в качестве ключей будут использоваться целые числа.

Поскольку никаких других ограничений или информации об этом не дано, я сначала подумал о том, что ключ всегда будет целым числом. Однако это делает общий «Ключ» излишним, и я не думаю, что учителя этого ожидают. Итак, я думаю, что лучшее решение состоит в том, чтобы заставить все, что передается как Key, реализовать Comparator, или что-то в этом роде (я действительно никогда не работал с Comparator, просто догадываясь), а затем использовать этот компаратор для сравнения ключей вместо используя операторы ==, <,> и! =. Тем не менее, я понятия не имею, как это сделать. Есть намеки?

Заранее спасибо.

Ответы [ 2 ]

4 голосов
/ 16 апреля 2011

Попробуйте public class AVL<Key extends Comparable<Key>,Elem>; и используйте метод compareTo(), который требуется для интерфейса Comparable<T> и который реализуется Integer.

2 голосов
/ 16 апреля 2011

Реализации SortedMap и SortedSet в стандартном API Java либо используют Comparator<Key> и вызывают его метод compare(k1, k2), либо предполагают, что ключи реализуют Comparable<Key>, и вызывают k1.compareTo(k2).Большинство предлагают оба, в зависимости от того, какой конструктор используется.(EnumMap / EnumSet этого не делают, поскольку они поддерживают только встроенное упорядочение значений enum по порядку объявления.)

Подход Comparable требует, чтобы ключи всегда сортировались одинаково, ибудет использоваться для ключей, которые имеют каноническое упорядочение (например, целые числа), где вы хотите использовать это упорядочение.

Подход Comparator является более гибким, поскольку вы можете использовать одни и те же ключевые объекты для разных карт, гдеони упорядочены по-разному, и вы можете использовать его для ключей, над которыми у вас нет контроля, или у которых нет канонического порядка (например, Список, деревья / графики и т. д.). Вы также можете использовать его для сортировки ключей строк по другим критериям.чем чистое значение Unicode (например, на основе локали), используя Collator (это класс, реализующий Comparator).

Оба требуют полного порядка для ваших ключей, но я полагаю, что это необходимо для вашего дерева AVL,тоже.

Вот реализация Comparator, которая работает с любыми сопоставимыми объектами, поэтому вы можете использовать ее (возможно, внутри) в качестве адаптерадля сопоставимого варианта. 

 public static <X extends Comparable<X>> Comparator<X> makeComparator() {
     return new Comparator<X>() {
         public int compare(X left, X right) {
             return left.compareTo(right);
         }
     };
 }
...