1/*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation.
7 *
8 * This code is distributed in the hope that it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
11 * version 2 for more details (a copy is included in the LICENSE file that
12 * accompanied this code).
13 *
14 * You should have received a copy of the GNU General Public License version
15 * 2 along with this work; if not, write to the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
17 *
18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
19 * or visit www.oracle.com if you need additional information or have any
20 * questions.
21 */
22
23/*
24 * This file is available under and governed by the GNU General Public
25 * License version 2 only, as published by the Free Software Foundation.
26 * However, the following notice accompanied the original version of this
27 * file:
28 *
29 * Written by Doug Lea with assistance from members of JCP JSR-166
30 * Expert Group and released to the public domain, as explained at
31 * http://creativecommons.org/publicdomain/zero/1.0/
32 */
33
34/*
35 * @test
36 * @bug 4486658
37 * @summary Checks that a priority queue returns elements in sorted order across various operations
38 */
39
40import java.util.ArrayList;
41import java.util.Collections;
42import java.util.Comparator;
43import java.util.Iterator;
44import java.util.List;
45import java.util.Queue;
46import java.util.PriorityQueue;
47
48public class PriorityQueueSort {
49
50    static class MyComparator implements Comparator<Integer> {
51        public int compare(Integer x, Integer y) {
52            int i = x.intValue();
53            int j = y.intValue();
54            if (i < j) return -1;
55            if (i > j) return 1;
56            return 0;
57        }
58    }
59
60    public static void main(String[] args) {
61        int n = 10000;
62        if (args.length > 0)
63            n = Integer.parseInt(args[0]);
64
65        List<Integer> sorted = new ArrayList<>(n);
66        for (int i = 0; i < n; i++)
67            sorted.add(new Integer(i));
68        List<Integer> shuffled = new ArrayList<>(sorted);
69        Collections.shuffle(shuffled);
70
71        Queue<Integer> pq = new PriorityQueue<>(n, new MyComparator());
72        for (Iterator<Integer> i = shuffled.iterator(); i.hasNext(); )
73            pq.add(i.next());
74
75        List<Integer> recons = new ArrayList<>();
76        while (!pq.isEmpty())
77            recons.add(pq.remove());
78        if (!recons.equals(sorted))
79            throw new RuntimeException("Sort test failed");
80
81        recons.clear();
82        pq = new PriorityQueue<>(shuffled);
83        while (!pq.isEmpty())
84            recons.add(pq.remove());
85        if (!recons.equals(sorted))
86            throw new RuntimeException("Sort test failed");
87
88        // Remove all odd elements from queue
89        pq = new PriorityQueue<>(shuffled);
90        for (Iterator<Integer> i = pq.iterator(); i.hasNext(); )
91            if ((i.next().intValue() & 1) == 1)
92                i.remove();
93        recons.clear();
94        while (!pq.isEmpty())
95            recons.add(pq.remove());
96
97        for (Iterator<Integer> i = sorted.iterator(); i.hasNext(); )
98            if ((i.next().intValue() & 1) == 1)
99                i.remove();
100
101        if (!recons.equals(sorted))
102            throw new RuntimeException("Iterator remove test failed.");
103    }
104}
105