Как создать PQ, отсортированный по естественному порядку списка? - PullRequest
Новая
       22

Как создать PQ, отсортированный по естественному порядку списка?

0 голосов
/ 24 ноября 2010

Мой SSCE: 

public class ComparableItem implements Comparable<ComparableItem> {

    private final int itemNo;

    public ComparableItem(final int itemNo) {
        this.itemNo = itemNo;
    }

    @Override
    public int compareTo(ComparableItem o) {
        if (this.itemNo < o.itemNo) {
            return -1;
        } else if (this.itemNo > o.itemNo) {
            return 1;
        }
        return 0;
    }
}

Вот тест, который демонстрирует проблему.Код нарушается после создания PQ.Вышеприведенные строки должны доказать, что естественный порядок, определенный методом CompareTo (..), работает так, как ожидалось.Печать элементов PQ они: 14,9,15,5,6,3 против ожидаемых 15,14,9,6,5,3.Может кто-нибудь объяснить мне, почему это так? 

import org.junit.Test;
import java.util.*;
import static org.junit.Assert.*;

public class CompTest{

@Test
public void aTest() {

    Integer[] order = {9, 3, 14, 15, 6, 5};
    List<ComparableItem> items = new ArrayList<ComparableItem>(order.length);
    for (int i = 0; i < order.length; i++) {
        items.add(new ComparableItem(order[i]));
    }

    List<ComparableItem> greater = new ArrayList<ComparableItem>();
    testCompare(items, items.get(3), greater, true);
    testCompare(items, items.get(2), greater, true);
    testCompare(items, items.get(0), greater, true);
    testCompare(items, items.get(4), greater, true);
    testCompare(items, items.get(5), greater, true);
    testCompare(items, items.get(1), greater, true);

    final PriorityQueue<ComparableItem> itemsQueue = new PriorityQueue<ComparableItem>(items);
    greater = new ArrayList<ComparableItem>();
    for (ComparableItem c : itemsQueue) {
        testCompare(itemsQueue, c, greater, false);
    }
}

public static void testCompare(final Collection<ComparableItem> items, final ComparableItem item, final List<ComparableItem> greater, boolean bigger) {
    final int exp = (bigger)? -1:1;
    for (ComparableItem c : items) {
        final int expected = c.equals(item) ? 0 : greater.contains(c) ? exp : exp*-1;
        assertEquals(expected, item.compareTo(c));
        assertEquals(expected * -1, c.compareTo(item));
    }
    greater.add(item);
}

} 

new PriorityQueue<ComparableItem>(items);

Создает PriorityQueue, содержащий элементы в указанной коллекции.Если указанная коллекция является экземпляром SortedSet или другим PriorityQueue, эта очередь приоритетов будет упорядочена в соответствии с тем же порядком.В противном случае эта приоритетная очередь будет упорядочена в соответствии с естественным порядком ее элементов.

1 Ответ

2 голосов
/ 24 ноября 2010

Я думаю, что проблема не в очереди, а в том, как вы ее тестируете.В частности, Javadoc для PriorityQueue.iterator() сообщает:

Возвращает итератор для элементов в этой очереди.Итератор не возвращает элементы в каком-либо определенном порядке.

И класс javadoc говорит следующее:

Итератор, предоставленный в методе iterator (), не гарантирует прохожденияэлементы очереди с приоритетами в любом конкретном порядке.Если вам нужен упорядоченный обход, рассмотрите возможность использования Arrays.sort (pq.toArray ()).

...