util/PriorityQueue/PriorityQueueSort.java

/*
 * @test %I% %E%
 * @bug 4486658
 * @compile -source 1.5 PriorityQueueSort.java
 * @run main PriorityQueueSort
 * @summary Checks that a priority queue returns elements in sorted order across various operations
 */

import java.util.*;

public class PriorityQueueSort {

    static class MyComparator implements Comparator<Integer> { 
        public int compare(Integer x, Integer y) {
            int i = ((Integer)x).intValue();
            int j = ((Integer)y).intValue();
            if (i < j) return -1;
            if (i > j) return 1;
            return 0;
        }
    }

    public static void main(String[] args) {
        int n = 10000;
        if (args.length > 0)
            n = Integer.parseInt(args[0]);
        
        List<Integer> sorted = new ArrayList<Integer>(n);
        for (int i = 0; i < n; i++)
            sorted.add(new Integer(i));
        List<Integer> shuffled = new ArrayList<Integer>(sorted);
        Collections.shuffle(shuffled);

        Queue<Integer> pq = new PriorityQueue<Integer>(n, new MyComparator());
        for (Iterator<Integer> i = shuffled.iterator(); i.hasNext(); )
            pq.add(i.next());

        List<Integer> recons = new ArrayList<Integer>();
        while (!pq.isEmpty())
            recons.add(pq.remove());
        if (!recons.equals(sorted))
            throw new RuntimeException("Sort test failed");

        recons.clear();
        pq = new PriorityQueue<Integer>(shuffled);
        while (!pq.isEmpty())
            recons.add(pq.remove());
        if (!recons.equals(sorted))
            throw new RuntimeException("Sort test failed");

        // Remove all odd elements from queue
        pq = new PriorityQueue<Integer>(shuffled);
        for (Iterator<Integer> i = pq.iterator(); i.hasNext(); )
            if ((i.next().intValue() & 1) == 1)
                i.remove();
        recons.clear();
        while (!pq.isEmpty())
            recons.add(pq.remove());

        for (Iterator<Integer> i = sorted.iterator(); i.hasNext(); )
            if ((i.next().intValue() & 1) == 1)
                i.remove();

        if (!recons.equals(sorted))
            throw new RuntimeException("Iterator remove test failed.");
    }
}

Revision:	1.3
Committed:	Mon Sep 1 21:38:20 2003 UTC (20 years, 9 months ago) by jsr166
Branch:	MAIN
CVS Tags:	JSR166_NOV3_FREEZE, JSR166_PFD, JSR166_DEC9_PRE_ES_SUBMIT, JSR166_DEC9_POST_ES_SUBMIT
Changes since 1.2:	+1 -2 lines
Log Message:	Correct @run timeouts. Avoid @run "run-ons"
#	User	Rev	Content
1	dl	1.1	/*
2	jsr166	1.2	* @test %I% %E%
3			* @bug 4486658
4			* @compile -source 1.5 PriorityQueueSort.java
5			* @run main PriorityQueueSort
6	jsr166	1.3	* @summary Checks that a priority queue returns elements in sorted order across various operations
7	dl	1.1	*/
8
9			import java.util.*;
10
11			public class PriorityQueueSort {
12
13			static class MyComparator implements Comparator<Integer> {
14			public int compare(Integer x, Integer y) {
15			int i = ((Integer)x).intValue();
16			int j = ((Integer)y).intValue();
17			if (i < j) return -1;
18			if (i > j) return 1;
19			return 0;
20			}
21			}
22
23			public static void main(String[] args) {
24			int n = 10000;
25			if (args.length > 0)
26			n = Integer.parseInt(args[0]);
27
28			List<Integer> sorted = new ArrayList<Integer>(n);
29			for (int i = 0; i < n; i++)
30			sorted.add(new Integer(i));
31			List<Integer> shuffled = new ArrayList<Integer>(sorted);
32			Collections.shuffle(shuffled);
33
34			Queue<Integer> pq = new PriorityQueue<Integer>(n, new MyComparator());
35			for (Iterator<Integer> i = shuffled.iterator(); i.hasNext(); )
36			pq.add(i.next());
37
38			List<Integer> recons = new ArrayList<Integer>();
39			while (!pq.isEmpty())
40			recons.add(pq.remove());
41			if (!recons.equals(sorted))
42			throw new RuntimeException("Sort test failed");
43
44			recons.clear();
45			pq = new PriorityQueue<Integer>(shuffled);
46			while (!pq.isEmpty())
47			recons.add(pq.remove());
48			if (!recons.equals(sorted))
49			throw new RuntimeException("Sort test failed");
50
51			// Remove all odd elements from queue
52			pq = new PriorityQueue<Integer>(shuffled);
53			for (Iterator<Integer> i = pq.iterator(); i.hasNext(); )
54			if ((i.next().intValue() & 1) == 1)
55			i.remove();
56			recons.clear();
57			while (!pq.isEmpty())
58			recons.add(pq.remove());
59
60			for (Iterator<Integer> i = sorted.iterator(); i.hasNext(); )
61			if ((i.next().intValue() & 1) == 1)
62			i.remove();
63
64			if (!recons.equals(sorted))
65			throw new RuntimeException("Iterator remove test failed.");
66			}
67			}
68