Return-Path: Delivered-To: apmail-lucene-java-commits-archive@www.apache.org Received: (qmail 2042 invoked from network); 2 Oct 2009 17:28:30 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3) by minotaur.apache.org with SMTP; 2 Oct 2009 17:28:30 -0000 Received: (qmail 21259 invoked by uid 500); 2 Oct 2009 17:28:30 -0000 Delivered-To: apmail-lucene-java-commits-archive@lucene.apache.org Received: (qmail 21190 invoked by uid 500); 2 Oct 2009 17:28:29 -0000 Mailing-List: contact java-commits-help@lucene.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: java-dev@lucene.apache.org Delivered-To: mailing list java-commits@lucene.apache.org Received: (qmail 21181 invoked by uid 99); 2 Oct 2009 17:28:29 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 02 Oct 2009 17:28:29 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=10.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 02 Oct 2009 17:28:25 +0000 Received: by eris.apache.org (Postfix, from userid 65534) id 160172388892; Fri, 2 Oct 2009 17:28:04 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r821104 - in /lucene/java/trunk/src: java/org/apache/lucene/util/PriorityQueue.java test/org/apache/lucene/util/TestPriorityQueue.java Date: Fri, 02 Oct 2009 17:28:03 -0000 To: java-commits@lucene.apache.org From: uschindler@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20091002172804.160172388892@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: uschindler Date: Fri Oct 2 17:28:03 2009 New Revision: 821104 URL: http://svn.apache.org/viewvc?rev=821104&view=rev Log: LUCENE-1935: Generify PriorityQueue Modified: lucene/java/trunk/src/java/org/apache/lucene/util/PriorityQueue.java lucene/java/trunk/src/test/org/apache/lucene/util/TestPriorityQueue.java Modified: lucene/java/trunk/src/java/org/apache/lucene/util/PriorityQueue.java URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/util/PriorityQueue.java?rev=821104&r1=821103&r2=821104&view=diff ============================================================================== --- lucene/java/trunk/src/java/org/apache/lucene/util/PriorityQueue.java (original) +++ lucene/java/trunk/src/java/org/apache/lucene/util/PriorityQueue.java Fri Oct 2 17:28:03 2009 @@ -25,14 +25,14 @@ * length maxSize+1, in {@link #initialize}. * */ -public abstract class PriorityQueue { +public abstract class PriorityQueue { private int size; private int maxSize; - protected Object[] heap; + protected T[] heap; /** Determines the ordering of objects in this priority queue. Subclasses must define this one method. */ - protected abstract boolean lessThan(Object a, Object b); + protected abstract boolean lessThan(T a, T b); /** * This method can be overridden by extending classes to return a sentinel @@ -41,7 +41,7 @@ * change the top without attempting to insert any new object.
* * Those sentinel values should always compare worse than any non-sentinel - * value (i.e., {@link #lessThan(Object, Object)} should always favor the + * value (i.e., {@link #lessThan(T, T)} should always favor the * non-sentinel values).
* * By default, this method returns false, which means the queue will not be @@ -53,9 +53,9 @@ * *

    * // extends getSentinelObject() to return a non-null value.
-   * PriorityQueue pq = new MyQueue(numHits);
+   * PriorityQueue pq = new MyQueue(numHits);
    * // save the 'top' element, which is guaranteed to not be null.
-   * MyObject pqTop = (MyObject) pq.top();
+   * MyObject pqTop = pq.top();
    * <...>
    * // now in order to add a new element, which is 'better' than top (after 
    * // you've verified it is better), it is as simple as:
@@ -73,11 +73,12 @@
    * @return the sentinel object to use to pre-populate the queue, or null if
    *         sentinel objects are not supported.
    */
-  protected Object getSentinelObject() {
+  protected T getSentinelObject() {
     return null;
   }
 
   /** Subclass constructors must call this. */
+  @SuppressWarnings("unchecked")
   protected final void initialize(int maxSize) {
     size = 0;
     int heapSize;
@@ -86,11 +87,11 @@
       heapSize = 2;
     else
       heapSize = maxSize + 1;
-    heap = new Object[heapSize];
+    heap = (T[]) new Object[heapSize]; // T is unbounded type, so this unchecked cast works always
     this.maxSize = maxSize;
     
     // If sentinel objects are supported, populate the queue with them
-    Object sentinel = getSentinelObject();
+    T sentinel = getSentinelObject();
     if (sentinel != null) {
       heap[1] = sentinel;
       for (int i = 2; i < heap.length; i++) {
@@ -105,10 +106,10 @@
    * more objects than maxSize from initialize a RuntimeException
    * (ArrayIndexOutOfBound) is thrown.
    * 
-   * @deprecated use {@link #add(Object)} which returns the new top object,
+   * @deprecated use {@link #add(T)} which returns the new top object,
    *             saving an additional call to {@link #top()}.
    */
-  public final void put(Object element) {
+  public final void put(T element) {
     size++;
     heap[size] = element;
     upHeap();
@@ -121,7 +122,7 @@
    * 
    * @return the new 'top' element in the queue.
    */
-  public final Object add(Object element) {
+  public final T add(T element) {
     size++;
     heap[size] = element;
     upHeap();
@@ -134,10 +135,10 @@
    * 
    * @param element
    * @return true if element is added, false otherwise.
-   * @deprecated use {@link #insertWithOverflow(Object)} instead, which
+   * @deprecated use {@link #insertWithOverflow(T)} instead, which
    *             encourages objects reuse.
    */
-  public boolean insert(Object element) {
+  public boolean insert(T element) {
     return insertWithOverflow(element) != element;
   }
 
@@ -151,12 +152,12 @@
    * heap and now has been replaced by a larger one, or null
    * if the queue wasn't yet full with maxSize elements.
    */
-  public Object insertWithOverflow(Object element) {
+  public T insertWithOverflow(T element) {
     if (size < maxSize) {
       put(element);
       return null;
     } else if (size > 0 && !lessThan(element, heap[1])) {
-      Object ret = heap[1];
+      T ret = heap[1];
       heap[1] = element;
       adjustTop();
       return ret;
@@ -166,7 +167,7 @@
   }
 
   /** Returns the least element of the PriorityQueue in constant time. */
-  public final Object top() {
+  public final T top() {
     // We don't need to check size here: if maxSize is 0,
     // then heap is length 2 array with both entries null.
     // If size is 0 then heap[1] is already null.
@@ -175,9 +176,9 @@
 
   /** Removes and returns the least element of the PriorityQueue in log(size)
     time. */
-  public final Object pop() {
+  public final T pop() {
     if (size > 0) {
-      Object result = heap[1];			  // save first value
+      T result = heap[1];			  // save first value
       heap[1] = heap[size];			  // move last to first
       heap[size] = null;			  // permit GC of objects
       size--;
@@ -230,7 +231,7 @@
    * 
    * @return the new 'top' element.
    */
-  public final Object updateTop() {
+  public final T updateTop() {
     downHeap();
     return heap[1];
   }
@@ -250,7 +251,7 @@
 
   private final void upHeap() {
     int i = size;
-    Object node = heap[i];			  // save bottom node
+    T node = heap[i];			  // save bottom node
     int j = i >>> 1;
     while (j > 0 && lessThan(node, heap[j])) {
       heap[i] = heap[j];			  // shift parents down
@@ -262,7 +263,7 @@
 
   private final void downHeap() {
     int i = 1;
-    Object node = heap[i];			  // save top node
+    T node = heap[i];			  // save top node
     int j = i << 1;				  // find smaller child
     int k = j + 1;
     if (k <= size && lessThan(heap[k], heap[j])) {

Modified: lucene/java/trunk/src/test/org/apache/lucene/util/TestPriorityQueue.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/test/org/apache/lucene/util/TestPriorityQueue.java?rev=821104&r1=821103&r2=821104&view=diff
==============================================================================
--- lucene/java/trunk/src/test/org/apache/lucene/util/TestPriorityQueue.java (original)
+++ lucene/java/trunk/src/test/org/apache/lucene/util/TestPriorityQueue.java Fri Oct  2 17:28:03 2009
@@ -19,111 +19,100 @@
 
 import java.util.Random;
 
-public class TestPriorityQueue
-    extends LuceneTestCase
-{
-    public TestPriorityQueue(String name)
-    {
-	super(name);
-    }
-
-    private static class IntegerQueue
-	extends PriorityQueue
-    {
-	public IntegerQueue(int count)
-	{
-	    super();
-	    initialize(count);
-	}
-
-	protected boolean lessThan(Object a, Object b)
-	{
-	    return ((Integer) a).intValue() < ((Integer) b).intValue();
-	}
-    }
-
-    public void testPQ()
-	throws Exception
-    {
-	testPQ(10000, newRandom());
-    }
-
-  public static void testPQ(int count, Random gen)
-    {
-	PriorityQueue pq = new IntegerQueue(count);
-	int sum = 0, sum2 = 0;
-
-	for (int i = 0; i < count; i++)
-	{
-	    int next = gen.nextInt();
-	    sum += next;
-	    pq.put(new Integer(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 = (Integer)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 pq = new IntegerQueue(3);
-	pq.put(new Integer(2));
-	pq.put(new Integer(3));
-	pq.put(new Integer(1));
-	assertEquals(3, pq.size());
-	pq.clear();
-	assertEquals(0, pq.size());
+public class TestPriorityQueue extends LuceneTestCase {
+    public TestPriorityQueue(String name) {
+        super(name);
     }
-    
-    public void testFixedSize(){
-        PriorityQueue pq = new IntegerQueue(3);
-        pq.insert(new Integer(2));
-        pq.insert(new Integer(3));
-        pq.insert(new Integer(1));
-        pq.insert(new Integer(5));
-        pq.insert(new Integer(7));
-        pq.insert(new Integer(1));
+
+    private static class IntegerQueue extends PriorityQueue {
+        public IntegerQueue(int count) {
+            super();
+            initialize(count);
+        }
+
+        protected boolean lessThan(Integer a, Integer b) {
+            return (a < b);
+        }
+    }
+
+    public void testPQ() throws Exception {
+        testPQ(10000, newRandom());
+    }
+
+    public static void testPQ(int count, Random gen) {
+        PriorityQueue pq = new IntegerQueue(count);
+        int sum = 0, sum2 = 0;
+
+        for (int i = 0; i < count; i++)
+        {
+            int next = gen.nextInt();
+            sum += next;
+            pq.put(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 = (Integer)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 pq = new IntegerQueue(3);
+        pq.put(2);
+        pq.put(3);
+        pq.put(1);
         assertEquals(3, pq.size());
-        assertEquals(3, ((Integer) pq.top()).intValue());
+        pq.clear();
+        assertEquals(0, pq.size());
     }
     
-  public void testInsertWithOverflow() {
-    int size = 4;
-    PriorityQueue pq = new IntegerQueue(size);
-    Integer i1 = new Integer(2);
-    Integer i2 = new Integer(3);
-    Integer i3 = new Integer(1);
-    Integer i4 = new Integer(5);
-    Integer i5 = new Integer(7);
-    Integer i6 = new Integer(1);
+    public void testFixedSize() {
+        PriorityQueue pq = new IntegerQueue(3);
+        pq.insert(2);
+        pq.insert(3);
+        pq.insert(1);
+        pq.insert(5);
+        pq.insert(7);
+        pq.insert(1);
+        assertEquals(3, pq.size());
+        assertEquals((Integer) 3, pq.top());
+    }
     
-    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(2, ((Integer) pq.top()).intValue());
-  }
+    public void testInsertWithOverflow() {
+      int size = 4;
+      PriorityQueue 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());
+    }
   
 }