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.Queue;
import java.util.PriorityQueue;

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<>(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.12
Committed:	Wed Jan 4 04:46:19 2017 UTC (7 years, 4 months ago) by jsr166
Branch:	MAIN
Changes since 1.11:	+6 -6 lines
Log Message:	convert to Diamond
#	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			import java.util.Queue;
19			import java.util.PriorityQueue;
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.4	int i = x.intValue();
26			int j = y.intValue();
27	dl	1.1	if (i < j) return -1;
28			if (i > j) return 1;
29			return 0;
30			}
31			}
32
33			public static void main(String[] args) {
34			int n = 10000;
35			if (args.length > 0)
36			n = Integer.parseInt(args[0]);
37	jsr166	1.6
38	jsr166	1.12	List<Integer> sorted = new ArrayList<>(n);
39	dl	1.1	for (int i = 0; i < n; i++)
40			sorted.add(new Integer(i));
41	jsr166	1.12	List<Integer> shuffled = new ArrayList<>(sorted);
42	dl	1.1	Collections.shuffle(shuffled);
43
44	jsr166	1.12	Queue<Integer> pq = new PriorityQueue<>(n, new MyComparator());
45	dl	1.1	for (Iterator<Integer> i = shuffled.iterator(); i.hasNext(); )
46			pq.add(i.next());
47
48	jsr166	1.12	List<Integer> recons = new ArrayList<>();
49	dl	1.1	while (!pq.isEmpty())
50			recons.add(pq.remove());
51			if (!recons.equals(sorted))
52			throw new RuntimeException("Sort test failed");
53
54			recons.clear();
55	jsr166	1.12	pq = new PriorityQueue<>(shuffled);
56	dl	1.1	while (!pq.isEmpty())
57			recons.add(pq.remove());
58			if (!recons.equals(sorted))
59			throw new RuntimeException("Sort test failed");
60
61			// Remove all odd elements from queue
62	jsr166	1.12	pq = new PriorityQueue<>(shuffled);
63	dl	1.1	for (Iterator<Integer> i = pq.iterator(); i.hasNext(); )
64			if ((i.next().intValue() & 1) == 1)
65			i.remove();
66			recons.clear();
67			while (!pq.isEmpty())
68			recons.add(pq.remove());
69
70			for (Iterator<Integer> i = sorted.iterator(); i.hasNext(); )
71			if ((i.next().intValue() & 1) == 1)
72			i.remove();
73
74			if (!recons.equals(sorted))
75			throw new RuntimeException("Iterator remove test failed.");
76			}
77			}