| 1 |
import java.util.*; |
| 2 |
import java.util.Queue; |
| 3 |
import java.util.PriorityQueue; |
| 4 |
|
| 5 |
import junit.framework.TestCase; |
| 6 |
|
| 7 |
/** |
| 8 |
* Tests the PriorityQueue implementation. |
| 9 |
*/ |
| 10 |
public class PriorityQueueTest extends TestCase { |
| 11 |
|
| 12 |
private static final long SEED = 37L; |
| 13 |
|
| 14 |
private static final int N = 100000; |
| 15 |
|
| 16 |
private final Random random = new Random(SEED); |
| 17 |
private final List<Integer> unsorted = new ArrayList<Integer>(N); |
| 18 |
{ |
| 19 |
for (int i = 0; i < N; ++i) { |
| 20 |
unsorted.add(new Integer(random.nextInt(N))); |
| 21 |
} |
| 22 |
} |
| 23 |
|
| 24 |
|
| 25 |
public void testSortedOrder () { |
| 26 |
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); |
| 27 |
List<Integer> expected = new ArrayList<Integer>(unsorted); |
| 28 |
Collections.sort(expected); |
| 29 |
doTest(pq, expected); |
| 30 |
} |
| 31 |
|
| 32 |
public void testReverseOrder () { |
| 33 |
Comparator<Integer> rev = new Comparator<Integer>() { |
| 34 |
public int compare (Integer a, Integer b) { |
| 35 |
return b.compareTo(a); |
| 36 |
} |
| 37 |
}; |
| 38 |
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(N, rev); |
| 39 |
List<Integer> expected = new ArrayList<Integer>(unsorted); |
| 40 |
Collections.sort(expected, rev); |
| 41 |
doTest(pq, expected); |
| 42 |
} |
| 43 |
|
| 44 |
private void doTest (PriorityQueue<Integer> pq, List<Integer> expected) { |
| 45 |
|
| 46 |
assertEquals("new pqueue should be empty", 0, pq.size()); |
| 47 |
|
| 48 |
for (Iterator<Integer> it = unsorted.iterator(); it.hasNext(); ) { |
| 49 |
pq.add(it.next()); |
| 50 |
} |
| 51 |
|
| 52 |
assertEquals("new pqueue should have N elements", N, pq.size()); |
| 53 |
|
| 54 |
List<Integer> sorted = new ArrayList<Integer>(N); |
| 55 |
for (Integer k; (k = pq.poll()) != null; ) { |
| 56 |
sorted.add(k); |
| 57 |
} |
| 58 |
|
| 59 |
assertEquals("pqueue should return elements in sorted order", |
| 60 |
expected, |
| 61 |
sorted); |
| 62 |
|
| 63 |
//System.out.println(unsorted.subList(0, 10)); |
| 64 |
//System.out.println(sorted.subList(0, 10)); |
| 65 |
} |
| 66 |
} |
