test/loops/PriorityQueueSort.java

/*
 * Written by Josh Bloch and Doug Lea with assistance from members of
 * JCP JSR-166 Expert Group and released to the public domain, as
 * explained at http://creativecommons.org/publicdomain/zero/1.0/
 */
/*
 * @test
 * @synopsis 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 = x;
            int j = y;
            if (i < j) return -1;
            if (i > j) return 1;
            return 0;
        }
    }

    public static void main(String[] args) {
        int n = 100000;
        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.6
Committed:	Tue Mar 15 19:47:05 2011 UTC (13 years, 2 months ago) by jsr166
Branch:	MAIN
CVS Tags:	release-1_7_0, HEAD
Changes since 1.5:	+1 -1 lines
Log Message:	Update Creative Commons license URL in legal notices
#	User	Rev	Content
1	dl	1.1	/*
2	dl	1.2	* Written by Josh Bloch and Doug Lea with assistance from members of
3			* JCP JSR-166 Expert Group and released to the public domain, as
4	jsr166	1.6	* explained at http://creativecommons.org/publicdomain/zero/1.0/
5	dl	1.2	*/
6			/*
7	dl	1.1	* @test
8			* @synopsis Checks that a priority queue returns elements in sorted order across various operations
9			*/
10
11			import java.util.*;
12
13			public class PriorityQueueSort {
14
15	jsr166	1.4	static class MyComparator implements Comparator<Integer> {
16	dl	1.1	public int compare(Integer x, Integer y) {
17	jsr166	1.5	int i = x;
18			int j = y;
19	dl	1.1	if (i < j) return -1;
20			if (i > j) return 1;
21			return 0;
22			}
23			}
24
25			public static void main(String[] args) {
26	dl	1.3	int n = 100000;
27	dl	1.1	if (args.length > 0)
28			n = Integer.parseInt(args[0]);
29	jsr166	1.4
30	dl	1.1	List<Integer> sorted = new ArrayList<Integer>(n);
31			for (int i = 0; i < n; i++)
32			sorted.add(new Integer(i));
33			List<Integer> shuffled = new ArrayList<Integer>(sorted);
34			Collections.shuffle(shuffled);
35
36			Queue<Integer> pq = new PriorityQueue<Integer>(n, new MyComparator());
37			for (Iterator<Integer> i = shuffled.iterator(); i.hasNext(); )
38			pq.add(i.next());
39
40			List<Integer> recons = new ArrayList<Integer>();
41			while (!pq.isEmpty())
42			recons.add(pq.remove());
43			if (!recons.equals(sorted))
44			throw new RuntimeException("Sort test failed");
45
46			recons.clear();
47			pq = new PriorityQueue<Integer>(shuffled);
48			while (!pq.isEmpty())
49			recons.add(pq.remove());
50			if (!recons.equals(sorted))
51			throw new RuntimeException("Sort test failed");
52
53			// Remove all odd elements from queue
54			pq = new PriorityQueue<Integer>(shuffled);
55			for (Iterator<Integer> i = pq.iterator(); i.hasNext(); )
56			if ((i.next().intValue() & 1) == 1)
57			i.remove();
58			recons.clear();
59			while (!pq.isEmpty())
60			recons.add(pq.remove());
61
62			for (Iterator<Integer> i = sorted.iterator(); i.hasNext(); )
63			if ((i.next().intValue() & 1) == 1)
64			i.remove();
65
66			if (!recons.equals(sorted))
67			throw new RuntimeException("Iterator remove test failed.");
68			}
69			}