001: package org.apache.lucene.util;
002:
003: /**
004: * Licensed to the Apache Software Foundation (ASF) under one or more
005: * contributor license agreements. See the NOTICE file distributed with
006: * this work for additional information regarding copyright ownership.
007: * The ASF licenses this file to You under the Apache License, Version 2.0
008: * (the "License"); you may not use this file except in compliance with
009: * the License. You may obtain a copy of the License at
010: *
011: * http://www.apache.org/licenses/LICENSE-2.0
012: *
013: * Unless required by applicable law or agreed to in writing, software
014: * distributed under the License is distributed on an "AS IS" BASIS,
015: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
016: * See the License for the specific language governing permissions and
017: * limitations under the License.
018: */
019:
020: import java.util.Random;
021:
022: public class TestPriorityQueue extends LuceneTestCase {
023: public TestPriorityQueue(String name) {
024: super (name);
025: }
026:
027: private static class IntegerQueue extends PriorityQueue {
028: public IntegerQueue(int count) {
029: super ();
030: initialize(count);
031: }
032:
033: protected boolean lessThan(Object a, Object b) {
034: return ((Integer) a).intValue() < ((Integer) b).intValue();
035: }
036: }
037:
038: public void testPQ() throws Exception {
039: testPQ(10000);
040: }
041:
042: public static void testPQ(int count) {
043: PriorityQueue pq = new IntegerQueue(count);
044: Random gen = new Random();
045: int sum = 0, sum2 = 0;
046:
047: for (int i = 0; i < count; i++) {
048: int next = gen.nextInt();
049: sum += next;
050: pq.put(new Integer(next));
051: }
052:
053: // Date end = new Date();
054:
055: // System.out.print(((float)(end.getTime()-start.getTime()) / count) * 1000);
056: // System.out.println(" microseconds/put");
057:
058: // start = new Date();
059:
060: int last = Integer.MIN_VALUE;
061: for (int i = 0; i < count; i++) {
062: Integer next = (Integer) pq.pop();
063: assertTrue(next.intValue() >= last);
064: last = next.intValue();
065: sum2 += last;
066: }
067:
068: assertEquals(sum, sum2);
069: // end = new Date();
070:
071: // System.out.print(((float)(end.getTime()-start.getTime()) / count) * 1000);
072: // System.out.println(" microseconds/pop");
073: }
074:
075: public void testClear() {
076: PriorityQueue pq = new IntegerQueue(3);
077: pq.put(new Integer(2));
078: pq.put(new Integer(3));
079: pq.put(new Integer(1));
080: assertEquals(3, pq.size());
081: pq.clear();
082: assertEquals(0, pq.size());
083: }
084:
085: public void testFixedSize() {
086: PriorityQueue pq = new IntegerQueue(3);
087: pq.insert(new Integer(2));
088: pq.insert(new Integer(3));
089: pq.insert(new Integer(1));
090: pq.insert(new Integer(5));
091: pq.insert(new Integer(7));
092: pq.insert(new Integer(1));
093: assertEquals(3, pq.size());
094: assertEquals(3, ((Integer) pq.top()).intValue());
095: }
096:
097: public void testInsertWithOverflow() {
098: int size = 4;
099: PriorityQueue pq = new IntegerQueue(size);
100: Integer i1 = new Integer(2);
101: Integer i2 = new Integer(3);
102: Integer i3 = new Integer(1);
103: Integer i4 = new Integer(5);
104: Integer i5 = new Integer(7);
105: Integer i6 = new Integer(1);
106:
107: assertNull(pq.insertWithOverflow(i1));
108: assertNull(pq.insertWithOverflow(i2));
109: assertNull(pq.insertWithOverflow(i3));
110: assertNull(pq.insertWithOverflow(i4));
111: assertTrue(pq.insertWithOverflow(i5) == i3); // i3 should have been dropped
112: assertTrue(pq.insertWithOverflow(i6) == i6); // i6 should not have been inserted
113: assertEquals(size, pq.size());
114: assertEquals(2, ((Integer) pq.top()).intValue());
115: }
116:
117: }
|