util/PriorityQueue/PriorityQueueSort.java

/*
 * @test %I% %E%
 * @bug 4486658
 * @summary Checks that a priority queue returns elements in sorted order across various operations
 */

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/licenses/publicdomain
 */

import java.util.*;

public class PriorityQueueSort {

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