1 package org.apache.lucene.util;
4 * Licensed to the Apache Software Foundation (ASF) under one or more
5 * contributor license agreements. See the NOTICE file distributed with
6 * this work for additional information regarding copyright ownership.
7 * The ASF licenses this file to You under the Apache License, Version 2.0
8 * (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
11 * http://www.apache.org/licenses/LICENSE-2.0
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
20 import java.util.Random;
22 public class TestPriorityQueue extends LuceneTestCase {
24 private static class IntegerQueue extends PriorityQueue<Integer> {
25 public IntegerQueue(int count) {
31 protected boolean lessThan(Integer a, Integer b) {
36 public void testPQ() throws Exception {
37 testPQ(atLeast(10000), random);
40 public static void testPQ(int count, Random gen) {
41 PriorityQueue<Integer> pq = new IntegerQueue(count);
42 int sum = 0, sum2 = 0;
44 for (int i = 0; i < count; i++)
46 int next = gen.nextInt();
51 // Date end = new Date();
53 // System.out.print(((float)(end.getTime()-start.getTime()) / count) * 1000);
54 // System.out.println(" microseconds/put");
56 // start = new Date();
58 int last = Integer.MIN_VALUE;
59 for (int i = 0; i < count; i++)
61 Integer next = pq.pop();
62 assertTrue(next.intValue() >= last);
63 last = next.intValue();
67 assertEquals(sum, sum2);
70 // System.out.print(((float)(end.getTime()-start.getTime()) / count) * 1000);
71 // System.out.println(" microseconds/pop");
74 public void testClear() {
75 PriorityQueue<Integer> pq = new IntegerQueue(3);
79 assertEquals(3, pq.size());
81 assertEquals(0, pq.size());
84 public void testFixedSize() {
85 PriorityQueue<Integer> pq = new IntegerQueue(3);
86 pq.insertWithOverflow(2);
87 pq.insertWithOverflow(3);
88 pq.insertWithOverflow(1);
89 pq.insertWithOverflow(5);
90 pq.insertWithOverflow(7);
91 pq.insertWithOverflow(1);
92 assertEquals(3, pq.size());
93 assertEquals((Integer) 3, pq.top());
96 public void testInsertWithOverflow() {
98 PriorityQueue<Integer> pq = new IntegerQueue(size);
106 assertNull(pq.insertWithOverflow(i1));
107 assertNull(pq.insertWithOverflow(i2));
108 assertNull(pq.insertWithOverflow(i3));
109 assertNull(pq.insertWithOverflow(i4));
110 assertTrue(pq.insertWithOverflow(i5) == i3); // i3 should have been dropped
111 assertTrue(pq.insertWithOverflow(i6) == i6); // i6 should not have been inserted
112 assertEquals(size, pq.size());
113 assertEquals((Integer) 2, pq.top());