test/loops/PriorityQueueSort.java

/*
 * @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 = ((Integer)x).intValue();
            int j = ((Integer)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.1
Committed:	Mon May 2 19:19:38 2005 UTC (19 years ago) by dl
Branch:	MAIN
Log Message:	Put misc performance tests into CVS
#	User	Rev	Content
1	dl	1.1	/*
2			* @test
3			* @synopsis Checks that a priority queue returns elements in sorted order across various operations
4			*/
5
6			import java.util.*;
7
8			public class PriorityQueueSort {
9
10			static class MyComparator implements Comparator<Integer> {
11			public int compare(Integer x, Integer y) {
12			int i = ((Integer)x).intValue();
13			int j = ((Integer)y).intValue();
14			if (i < j) return -1;
15			if (i > j) return 1;
16			return 0;
17			}
18			}
19
20			public static void main(String[] args) {
21			int n = 10000;
22			if (args.length > 0)
23			n = Integer.parseInt(args[0]);
24
25			List<Integer> sorted = new ArrayList<Integer>(n);
26			for (int i = 0; i < n; i++)
27			sorted.add(new Integer(i));
28			List<Integer> shuffled = new ArrayList<Integer>(sorted);
29			Collections.shuffle(shuffled);
30
31			Queue<Integer> pq = new PriorityQueue<Integer>(n, new MyComparator());
32			for (Iterator<Integer> i = shuffled.iterator(); i.hasNext(); )
33			pq.add(i.next());
34
35			List<Integer> recons = new ArrayList<Integer>();
36			while (!pq.isEmpty())
37			recons.add(pq.remove());
38			if (!recons.equals(sorted))
39			throw new RuntimeException("Sort test failed");
40
41			recons.clear();
42			pq = new PriorityQueue<Integer>(shuffled);
43			while (!pq.isEmpty())
44			recons.add(pq.remove());
45			if (!recons.equals(sorted))
46			throw new RuntimeException("Sort test failed");
47
48			// Remove all odd elements from queue
49			pq = new PriorityQueue<Integer>(shuffled);
50			for (Iterator<Integer> i = pq.iterator(); i.hasNext(); )
51			if ((i.next().intValue() & 1) == 1)
52			i.remove();
53			recons.clear();
54			while (!pq.isEmpty())
55			recons.add(pq.remove());
56
57			for (Iterator<Integer> i = sorted.iterator(); i.hasNext(); )
58			if ((i.next().intValue() & 1) == 1)
59			i.remove();
60
61			if (!recons.equals(sorted))
62			throw new RuntimeException("Iterator remove test failed.");
63			}
64			}
65