util/PriorityQueue/PriorityQueueSort.java

/*
 * 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/publicdomain/zero/1.0/
 */

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

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueSort {

    static class MyComparator implements Comparator<Integer> {
        public int compare(Integer x, Integer y) {
            return Integer.compare(x.intValue(), y.intValue());
        }
    }

    public static void main(String[] args) {
        int n = 10000;
        if (args.length > 0)
            n = Integer.parseInt(args[0]);

        List<Integer> sorted = new ArrayList<>(n);
        for (int i = 0; i < n; i++)
            sorted.add(new Integer(i));
        List<Integer> shuffled = new ArrayList<>(sorted);
        Collections.shuffle(shuffled);

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

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

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