lucene-java-3.5.0/lucene/backwards/src/test/org/apache/lucene/util/TestPriorityQueue.java

   1 package org.apache.lucene.util;
   2
   3 /**
   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
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  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.
  18  */
  19
  20 import java.util.Random;
  21
  22 public class TestPriorityQueue extends LuceneTestCase {
  23
  24     private static class IntegerQueue extends PriorityQueue<Integer> {
  25         public IntegerQueue(int count) {
  26             super();
  27             initialize(count);
  28         }
  29
  30         @Override
  31         protected boolean lessThan(Integer a, Integer b) {
  32             return (a < b);
  33         }
  34     }
  35
  36     public void testPQ() throws Exception {
  37         testPQ(atLeast(10000), random);
  38     }
  39
  40     public static void testPQ(int count, Random gen) {
  41         PriorityQueue<Integer> pq = new IntegerQueue(count);
  42         int sum = 0, sum2 = 0;
  43
  44         for (int i = 0; i < count; i++)
  45         {
  46             int next = gen.nextInt();
  47             sum += next;
  48             pq.add(next);
  49         }
  50
  51         //      Date end = new Date();
  52
  53         //      System.out.print(((float)(end.getTime()-start.getTime()) / count) * 1000);
  54         //      System.out.println(" microseconds/put");
  55
  56         //      start = new Date();
  57
  58         int last = Integer.MIN_VALUE;
  59         for (int i = 0; i < count; i++)
  60         {
  61             Integer next = pq.pop();
  62             assertTrue(next.intValue() >= last);
  63             last = next.intValue();
  64             sum2 += last;
  65         }
  66
  67         assertEquals(sum, sum2);
  68         //      end = new Date();
  69
  70         //      System.out.print(((float)(end.getTime()-start.getTime()) / count) * 1000);
  71         //      System.out.println(" microseconds/pop");
  72     }
  73
  74     public void testClear() {
  75         PriorityQueue<Integer> pq = new IntegerQueue(3);
  76         pq.add(2);
  77         pq.add(3);
  78         pq.add(1);
  79         assertEquals(3, pq.size());
  80         pq.clear();
  81         assertEquals(0, pq.size());
  82     }
  83
  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());
  94     }
  95
  96     public void testInsertWithOverflow() {
  97       int size = 4;
  98       PriorityQueue<Integer> pq = new IntegerQueue(size);
  99       Integer i1 = 2;
 100       Integer i2 = 3;
 101       Integer i3 = 1;
 102       Integer i4 = 5;
 103       Integer i5 = 7;
 104       Integer i6 = 1;
 105
 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());
 114     }
 115
 116 }