package org.apache.lucene.util;
/**
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
import java.util.Random;
public class TestPriorityQueue extends LuceneTestCase {
private static class IntegerQueue extends PriorityQueue<Integer> {
public IntegerQueue(int count) {
super();
initialize(count);
}
@Override
protected boolean lessThan(Integer a, Integer b) {
return (a < b);
}
}
public void testPQ() throws Exception {
testPQ(atLeast(10000), random);
}
public static void testPQ(int count, Random gen) {
PriorityQueue<Integer> pq = new IntegerQueue(count);
int sum = 0, sum2 = 0;
for (int i = 0; i < count; i++)
{
int next = gen.nextInt();
sum += next;
pq.add(next);
}
// Date end = new Date();
// System.out.print(((float)(end.getTime()-start.getTime()) / count) * 1000);
// System.out.println(" microseconds/put");
// start = new Date();
int last = Integer.MIN_VALUE;
for (int i = 0; i < count; i++)
{
Integer next = pq.pop();
assertTrue(next.intValue() >= last);
last = next.intValue();
sum2 += last;
}
assertEquals(sum, sum2);
// end = new Date();
// System.out.print(((float)(end.getTime()-start.getTime()) / count) * 1000);
// System.out.println(" microseconds/pop");
}
public void testClear() {
PriorityQueue<Integer> pq = new IntegerQueue(3);
pq.add(2);
pq.add(3);
pq.add(1);
assertEquals(3, pq.size());
pq.clear();
assertEquals(0, pq.size());
}
public void testFixedSize() {
PriorityQueue<Integer> pq = new IntegerQueue(3);
pq.insertWithOverflow(2);
pq.insertWithOverflow(3);
pq.insertWithOverflow(1);
pq.insertWithOverflow(5);
pq.insertWithOverflow(7);
pq.insertWithOverflow(1);
assertEquals(3, pq.size());
assertEquals((Integer) 3, pq.top());
}
public void testInsertWithOverflow() {
int size = 4;
PriorityQueue<Integer> pq = new IntegerQueue(size);
Integer i1 = 2;
Integer i2 = 3;
Integer i3 = 1;
Integer i4 = 5;
Integer i5 = 7;
Integer i6 = 1;
assertNull(pq.insertWithOverflow(i1));
assertNull(pq.insertWithOverflow(i2));
assertNull(pq.insertWithOverflow(i3));
assertNull(pq.insertWithOverflow(i4));
assertTrue(pq.insertWithOverflow(i5) == i3); // i3 should have been dropped
assertTrue(pq.insertWithOverflow(i6) == i6); // i6 should not have been inserted
assertEquals(size, pq.size());
assertEquals((Integer) 2, pq.top());
}
}