Return-Path: Delivered-To: apmail-lucene-dev-archive@www.apache.org Received: (qmail 18127 invoked from network); 3 Sep 2010 18:25:23 -0000 Received: from unknown (HELO mail.apache.org) (140.211.11.3) by 140.211.11.9 with SMTP; 3 Sep 2010 18:25:23 -0000 Received: (qmail 17644 invoked by uid 500); 3 Sep 2010 18:25:22 -0000 Delivered-To: apmail-lucene-dev-archive@lucene.apache.org Received: (qmail 17567 invoked by uid 500); 3 Sep 2010 18:25:21 -0000 Mailing-List: contact dev-help@lucene.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@lucene.apache.org Delivered-To: mailing list dev@lucene.apache.org Received: (qmail 17560 invoked by uid 99); 3 Sep 2010 18:25:21 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 03 Sep 2010 18:25:21 +0000 X-ASF-Spam-Status: No, hits=2.2 required=10.0 tests=FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_NONE,SPF_PASS,T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: apache.org Received-SPF: pass (nike.apache.org: domain of rcmuir@gmail.com designates 209.85.216.48 as permitted sender) Received: from [209.85.216.48] (HELO mail-qw0-f48.google.com) (209.85.216.48) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 03 Sep 2010 18:25:11 +0000 Received: by qwk3 with SMTP id 3so2578778qwk.35 for ; Fri, 03 Sep 2010 11:24:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:mime-version:received:in-reply-to :references:from:date:message-id:subject:to:content-type; bh=jpnEaZ7vZSi6Lsu8hGms98o17cOQ6AEsEOL0skHv5yI=; b=gwtB+kgNlE78YkgmNxoRr14WzKbEZfvtpmgG5k2/PQtqBdoc6TOPnptqNWZUVV8JVg +foay+5W3n0XU/uqNnLSnba57QcETLrCyHbwsHoTQeEBx88JmOI9Rw5AO1yqrFScU6Zr GXyspQHfPNQOYt0gYCRgXoZWPCX7SZ8uOo9K8= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; b=OKDHd5vnkA2Gs/zPT5C6hX3Yhdwid1YVBNIvxFk0Z20IHQ/VhewD1mR5fEYhUSrP49 Vdvf06ekOIq/xHZt4Ydq2zLteRwP0AX5a2hvm79N6bUnoAoGWhPqstsVO1c36gWUkrk5 Acc5X5qZ9xtU6FBeOyM8WoainqcHdRB7r9dLc= Received: by 10.224.80.133 with SMTP id t5mr276900qak.42.1283538289102; Fri, 03 Sep 2010 11:24:49 -0700 (PDT) MIME-Version: 1.0 Received: by 10.224.73.137 with HTTP; Fri, 3 Sep 2010 11:24:28 -0700 (PDT) In-Reply-To: <20100903171226.8E4C8238897D@eris.apache.org> References: <20100903171226.8E4C8238897D@eris.apache.org> From: Robert Muir Date: Fri, 3 Sep 2010 14:24:28 -0400 Message-ID: Subject: Re: svn commit: r992382 - in /lucene/dev/trunk/solr: ./ src/java/org/apache/solr/request/ src/java/org/apache/solr/util/ src/test/org/apache/solr/util/ To: dev@lucene.apache.org Content-Type: multipart/alternative; boundary=0015175ccf9ac71d7d048f5f0bc6 X-Virus-Checked: Checked by ClamAV on apache.org --0015175ccf9ac71d7d048f5f0bc6 Content-Type: text/plain; charset=UTF-8 Does SimpleFacetsTest fail for you? I svn up'ed and i see a few failures On Fri, Sep 3, 2010 at 1:12 PM, wrote: > Author: yonik > Date: Fri Sep 3 17:12:26 2010 > New Revision: 992382 > > URL: http://svn.apache.org/viewvc?rev=992382&view=rev > Log: > SOLR-2092: use native long PQ to order facet results > > Added: > > lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorityQueue.java > (with props) > Modified: > lucene/dev/trunk/solr/CHANGES.txt > lucene/dev/trunk/solr/src/java/org/apache/solr/request/SimpleFacets.java > > lucene/dev/trunk/solr/src/java/org/apache/solr/request/UnInvertedField.java > lucene/dev/trunk/solr/src/test/org/apache/solr/util/PrimUtilsTest.java > > Modified: lucene/dev/trunk/solr/CHANGES.txt > URL: > http://svn.apache.org/viewvc/lucene/dev/trunk/solr/CHANGES.txt?rev=992382&r1=992381&r2=992382&view=diff > > ============================================================================== > --- lucene/dev/trunk/solr/CHANGES.txt (original) > +++ lucene/dev/trunk/solr/CHANGES.txt Fri Sep 3 17:12:26 2010 > @@ -288,6 +288,12 @@ Optimizations > * SOLR-2046: Simplify legacy replication scripts by adding common > functions > to scripts-util. (koji) > > +* SOLR-2092: Speed up single-valued and multi-valued "fc" faceting. > Typical > + improvement is 5%, but can be much greater (up to 10x faster) when > facet.offset > + is very large (deep paging). (yonik) > + > + > + > Bug Fixes > ---------------------- > > > Modified: > lucene/dev/trunk/solr/src/java/org/apache/solr/request/SimpleFacets.java > URL: > http://svn.apache.org/viewvc/lucene/dev/trunk/solr/src/java/org/apache/solr/request/SimpleFacets.java?rev=992382&r1=992381&r2=992382&view=diff > > ============================================================================== > --- > lucene/dev/trunk/solr/src/java/org/apache/solr/request/SimpleFacets.java > (original) > +++ > lucene/dev/trunk/solr/src/java/org/apache/solr/request/SimpleFacets.java Fri > Sep 3 17:12:26 2010 > @@ -44,6 +44,7 @@ import org.apache.solr.util.BoundedTreeS > import org.apache.solr.util.ByteUtils; > import org.apache.solr.util.DateMathParser; > import org.apache.solr.handler.component.ResponseBuilder; > +import org.apache.solr.util.LongPriorityQueue; > > import java.io.IOException; > import java.util.*; > @@ -416,9 +417,9 @@ public class SimpleFacets { > } > > final int nTerms=endTermIndex-startTermIndex; > + int missingCount = -1; > > CharArr spare = new CharArr(); > - > if (nTerms>0 && docs.size() >= mincount) { > > // count collection array only needs to be as big as the number of > terms we are > @@ -475,6 +476,10 @@ public class SimpleFacets { > } > } > > + if (startTermIndex == 0) { > + missingCount = counts[0]; > + } > + > // IDEA: we could also maintain a count of "other"... everything that > fell outside > // of the top 'N' > > @@ -484,7 +489,8 @@ public class SimpleFacets { > if (sort.equals(FacetParams.FACET_SORT_COUNT) || > sort.equals(FacetParams.FACET_SORT_COUNT_LEGACY)) { > int maxsize = limit>0 ? offset+limit : Integer.MAX_VALUE-1; > maxsize = Math.min(maxsize, nTerms); > - final BoundedTreeSet> queue = new > BoundedTreeSet>(maxsize); > + LongPriorityQueue queue = new > LongPriorityQueue(Math.min(maxsize,1000), maxsize, Long.MIN_VALUE); > + > int min=mincount-1; // the smallest value in the top 'N' values > for (int i=(startTermIndex==0)?1:0; i int c = counts[i]; > @@ -492,18 +498,33 @@ public class SimpleFacets { > // NOTE: we use c>min rather than c>=min as an optimization > because we are going in > // index order, so we already know that the keys are ordered. > This can be very > // important if a lot of the counts are repeated (like zero > counts would be). > - queue.add(new > CountPair(si.lookup(startTermIndex+i, new BytesRef()), > c)); > - if (queue.size()>=maxsize) min=queue.last().val; > + > + // smaller term numbers sort higher, so subtract the term > number instead > + long pair = (((long)c)<<32) + (Integer.MAX_VALUE - i); > + boolean displaced = queue.insert(pair); > + if (displaced) min=(int)(queue.top() >>> 32); > } > } > - // now select the right page from the results > - for (CountPair p : queue) { > - if (--off>=0) continue; > - if (--lim<0) break; > + > + // if we are deep paging, we don't have to order the highest > "offset" counts. > + int collectCount = Math.max(0, queue.size() - off); > + assert collectCount < lim; > + > + // the start and end indexes of our list "sorted" (starting with > the highest value) > + int sortedIdxStart = queue.size() - (collectCount - 1); > + int sortedIdxEnd = queue.size() + 1; > + final long[] sorted = queue.sort(collectCount); > + > + for (int i=sortedIdxStart; i + long pair = sorted[i]; > + int c = (int)(pair >>> 32); > + int tnum = Integer.MAX_VALUE - (int)pair; > + > spare.reset(); > - ft.indexedToReadable(p.key, spare); > - res.add(spare.toString(), p.val); > + ft.indexedToReadable(si.lookup(startTermIndex+tnum, br), spare); > + res.add(spare.toString(), c); > } > + > } else { > // add results in index order > int i=(startTermIndex==0)?1:0; > @@ -526,7 +547,10 @@ public class SimpleFacets { > } > > if (missing) { > - res.add(null, getFieldMissingCount(searcher,docs,fieldName)); > + if (missingCount < 0) { > + missingCount = getFieldMissingCount(searcher,docs,fieldName); > + } > + res.add(null, missingCount); > } > > return res; > > Modified: > lucene/dev/trunk/solr/src/java/org/apache/solr/request/UnInvertedField.java > URL: > http://svn.apache.org/viewvc/lucene/dev/trunk/solr/src/java/org/apache/solr/request/UnInvertedField.java?rev=992382&r1=992381&r2=992382&view=diff > > ============================================================================== > --- > lucene/dev/trunk/solr/src/java/org/apache/solr/request/UnInvertedField.java > (original) > +++ > lucene/dev/trunk/solr/src/java/org/apache/solr/request/UnInvertedField.java > Fri Sep 3 17:12:26 2010 > @@ -37,6 +37,7 @@ import org.apache.solr.core.SolrCore; > import org.apache.solr.schema.FieldType; > import org.apache.solr.schema.TrieField; > import org.apache.solr.search.*; > +import org.apache.solr.util.LongPriorityQueue; > import org.apache.solr.util.PrimUtils; > import org.apache.solr.util.BoundedTreeSet; > import org.apache.solr.handler.component.StatsValues; > @@ -470,7 +471,9 @@ public class UnInvertedField { > if (baseSize >= mincount) { > > final int[] index = this.index; > - final int[] counts = new int[numTermsInField]; > + // tricky: we add more more element than we need because we will > reuse this array later > + // for ordering term ords before converting to term labels. > + final int[] counts = new int[numTermsInField + 1]; > > // > // If there is prefix, find it's start and end term numbers > @@ -575,7 +578,8 @@ public class UnInvertedField { > if (sort.equals(FacetParams.FACET_SORT_COUNT) || > sort.equals(FacetParams.FACET_SORT_COUNT_LEGACY)) { > int maxsize = limit>0 ? offset+limit : Integer.MAX_VALUE-1; > maxsize = Math.min(maxsize, numTermsInField); > - final BoundedTreeSet queue = new > BoundedTreeSet(maxsize); > + LongPriorityQueue queue = new > LongPriorityQueue(Math.min(maxsize,1000), maxsize, Long.MIN_VALUE); > + > int min=mincount-1; // the smallest value in the top 'N' values > for (int i=startTerm; i int c = doNegative ? maxTermCounts[i] - counts[i] : counts[i]; > @@ -584,55 +588,63 @@ public class UnInvertedField { > // index order, so we already know that the keys are ordered. > This can be very > // important if a lot of the counts are repeated (like zero > counts would be). > > - // minimize object creation and speed comparison by creating a > long that > - // encompasses both count and term number. > - // Since smaller values are kept in the TreeSet, make higher > counts smaller. > - // > - // for equal counts, lower term numbers > - // should come first and hence be "greater" > - > - //long pair = (((long)c)<<32) | (0x7fffffff-i) ; // use if > priority queue > - long pair = (((long)-c)<<32) | i; > - queue.add(new Long(pair)); > - if (queue.size()>=maxsize) min=-(int)(queue.last().longValue() > >>> 32); > + // smaller term numbers sort higher, so subtract the term > number instead > + long pair = (((long)c)<<32) + (Integer.MAX_VALUE - i); > + boolean displaced = queue.insert(pair); > + if (displaced) min=(int)(queue.top() >>> 32); > } > } > + > // now select the right page from the results > > + // if we are deep paging, we don't have to order the highest > "offset" counts. > + int collectCount = Math.max(0, queue.size() - off); > + assert collectCount < lim; > + > + // the start and end indexes of our list "sorted" (starting with > the highest value) > + int sortedIdxStart = queue.size() - (collectCount - 1); > + int sortedIdxEnd = queue.size() + 1; > + final long[] sorted = queue.sort(collectCount); > > - final int[] tnums = new int[Math.min(Math.max(0, > queue.size()-off), lim)]; > final int[] indirect = counts; // reuse the counts array for the > index into the tnums array > - assert indirect.length >= tnums.length; > - > - int tnumCount = 0; > + assert indirect.length >= sortedIdxEnd; > + > + for (int i=sortedIdxStart; i + long pair = sorted[i]; > + int c = (int)(pair >>> 32); > + int tnum = Integer.MAX_VALUE - (int)pair; > + > + indirect[i] = i; // store the index for indirect sorting > + sorted[i] = tnum; // reuse the "sorted" array to store the term > numbers for indirect sorting > > - for (Long p : queue) { > - if (--off>=0) continue; > - if (--lim<0) break; > - int c = -(int)(p.longValue() >>> 32); > - //int tnum = 0x7fffffff - (int)p.longValue(); // use if > priority queue > - int tnum = (int)p.longValue(); > - indirect[tnumCount] = tnumCount; > - tnums[tnumCount++] = tnum; > - // String label = ft.indexedToReadable(getTermText(te, tnum)); > // add a null label for now... we'll fill it in later. > res.add(null, c); > } > > // now sort the indexes by the term numbers > - PrimUtils.sort(0, tnumCount, indirect, new > PrimUtils.IntComparator() { > + PrimUtils.sort(sortedIdxStart, sortedIdxEnd, indirect, new > PrimUtils.IntComparator() { > @Override > public int compare(int a, int b) { > - return tnums[a] - tnums[b]; > + return (int)sorted[a] - (int)sorted[b]; > + } > + > + @Override > + public boolean lessThan(int a, int b) { > + return sorted[a] < sorted[b]; > + } > + > + @Override > + public boolean equals(int a, int b) { > + return sorted[a] == sorted[b]; > } > }); > > // convert the term numbers to term values and set as the label > - for (int i=0; i + for (int i=sortedIdxStart; i int idx = indirect[i]; > - int tnum = tnums[idx]; > - String label = getReadableValue(getTermValue(te, tnum), ft, > spare); > - res.setName(idx, label); > + int tnum = (int)sorted[idx]; > + String label = getReadableValue(getTermValue(te, tnum), ft, > spare); > + res.setName(idx - sortedIdxStart, label); > } > > } else { > > Added: > lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorityQueue.java > URL: > http://svn.apache.org/viewvc/lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorityQueue.java?rev=992382&view=auto > > ============================================================================== > --- > lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorityQueue.java > (added) > +++ > lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorityQueue.java > Fri Sep 3 17:12:26 2010 > @@ -0,0 +1,235 @@ > +package org.apache.solr.util; > + > +import java.util.Arrays; > + > +/** > + * 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. > + */ > + > +/** A native long priority queue. > + * > + * @lucene.internal > +*/ > +public class LongPriorityQueue { > + protected int size; // number of elements currently in the > queue > + protected int currentCapacity; // number of elements the queue can hold > w/o expanding > + protected int maxSize; // max number of elements allowed in the > queue > + protected long[] heap; > + protected final long sentinel; // represents a null return value > + > + public LongPriorityQueue(int initialSize, int maxSize, long sentinel) { > + this.maxSize = maxSize; > + this.sentinel = sentinel; > + initialize(initialSize); > + } > + > + > + protected void initialize(int sz) { > + int heapSize; > + if (0 == sz) > + // We allocate 1 extra to avoid if statement in top() > + heapSize = 2; > + else { > + // NOTE: we add +1 because all access to heap is > + // 1-based not 0-based. heap[0] is unused. > + heapSize = Math.max(sz, sz + 1); // handle overflow > + } > + heap = new long[heapSize]; > + currentCapacity = sz; > + } > + > + public int getCurrentCapacity() { > + return currentCapacity; > + } > + > + public void resize(int sz) { > + int heapSize; > + if (sz > maxSize) { > + maxSize = sz; > + } > + if (0 == sz) > + // We allocate 1 extra to avoid if statement in top() > + heapSize = 2; > + else { > + heapSize = Math.max(sz, sz + 1); // handle overflow > + } > + heap = Arrays.copyOf(heap, heapSize); > + currentCapacity = sz; > + } > + > + /** > + * Adds an object to a PriorityQueue in log(size) time. If one tries to > add > + * more objects than maxSize from initialize an > + * {@link ArrayIndexOutOfBoundsException} is thrown. > + * > + * @return the new 'top' element in the queue. > + */ > + public long add(long element) { > + if (size >= currentCapacity) { > + int newSize = Math.min(currentCapacity <<1, maxSize); > + if (newSize < currentCapacity) newSize = Integer.MAX_VALUE; // > handle overflow > + resize(newSize); > + } > + size++; > + heap[size] = element; > + upHeap(); > + return heap[1]; > + } > + > + /** > + * Adds an object to a PriorityQueue in log(size) time. If one tries to > add > + * more objects than the current capacity, an > + * {@link ArrayIndexOutOfBoundsException} is thrown. > + */ > + public void addNoCheck(long element) { > + ++size; > + heap[size] = element; > + upHeap(); > + } > + > + /** > + * Adds an object to a PriorityQueue in log(size) time. > + * It returns the smallest object (if any) that was > + * dropped off the heap because it was full, or > + * the sentinel value. > + * > + * This can be > + * the given parameter (in case it is smaller than the > + * full heap's minimum, and couldn't be added), or another > + * object that was previously the smallest value in the > + * heap and now has been replaced by a larger one, or null > + * if the queue wasn't yet full with maxSize elements. > + */ > + public long insertWithOverflow(long element) { > + if (size < maxSize) { > + add(element); > + return sentinel; > + } else if (element > heap[1]) { > + long ret = heap[1]; > + heap[1] = element; > + updateTop(); > + return ret; > + } else { > + return element; > + } > + } > + > + /** inserts the element and returns true if this element caused another > element > + * to be dropped from the queue. */ > + public boolean insert(long element) { > + if (size < maxSize) { > + add(element); > + return false; > + } else if (element > heap[1]) { > + // long ret = heap[1]; > + heap[1] = element; > + updateTop(); > + return true; > + } else { > + return false; > + } > + } > + > + /** Returns the least element of the PriorityQueue in constant time. */ > + public long top() { > + return heap[1]; > + } > + > + /** Removes and returns the least element of the PriorityQueue in > log(size) > + time. Only valid if size() > 0. > + */ > + public long pop() { > + long result = heap[1]; // save first value > + heap[1] = heap[size]; // move last to first > + size--; > + downHeap(); // adjust heap > + return result; > + } > + > + /** > + * Should be called when the Object at top changes values. > + * @return the new 'top' element. > + */ > + public long updateTop() { > + downHeap(); > + return heap[1]; > + } > + > + /** Returns the number of elements currently stored in the > PriorityQueue. */ > + public int size() { > + return size; > + } > + > + /** Returns the array used to hold the heap, with the smallest item at > array[1] > + * and the last (but not necessarily largest) at array[size()]. This > is *not* > + * fully sorted. > + */ > + public long[] getInternalArray() { > + return heap; > + } > + > + /** Pops the smallest n items from the heap, placing them in the > internal array at > + * arr[size] through arr[size-(n-1)] with the smallest (first element > popped) > + * being at arr[size]. The internal array is returned. > + */ > + public long[] sort(int n) { > + while (--n >= 0) { > + long result = heap[1]; // save first value > + heap[1] = heap[size]; // move last to first > + heap[size] = result; // place it last > + size--; > + downHeap(); // adjust heap > + } > + return heap; > + } > + > + /** Removes all entries from the PriorityQueue. */ > + public void clear() { > + size = 0; > + } > + > + private void upHeap() { > + int i = size; > + long node = heap[i]; // save bottom node > + int j = i >>> 1; > + while (j > 0 && node < heap[j]) { > + heap[i] = heap[j]; // shift parents down > + i = j; > + j = j >>> 1; > + } > + heap[i] = node; // install saved node > + } > + > + private void downHeap() { > + int i = 1; > + long node = heap[i]; // save top node > + int j = i << 1; // find smaller child > + int k = j + 1; > + if (k <= size && heap[k] < heap[j]) { > + j = k; > + } > + while (j <= size && heap[j] < node) { > + heap[i] = heap[j]; // shift up child > + i = j; > + j = i << 1; > + k = j + 1; > + if (k <= size && heap[k] < heap[j]) { > + j = k; > + } > + } > + heap[i] = node; // install saved node > + } > +} > > Propchange: > lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorityQueue.java > > ------------------------------------------------------------------------------ > svn:eol-style = native > > Propchange: > lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorityQueue.java > > ------------------------------------------------------------------------------ > svn:executable = * > > Propchange: > lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorityQueue.java > > ------------------------------------------------------------------------------ > svn:keywords = Date Author Id Revision HeadURL > > Modified: > lucene/dev/trunk/solr/src/test/org/apache/solr/util/PrimUtilsTest.java > URL: > http://svn.apache.org/viewvc/lucene/dev/trunk/solr/src/test/org/apache/solr/util/PrimUtilsTest.java?rev=992382&r1=992381&r2=992382&view=diff > > ============================================================================== > --- lucene/dev/trunk/solr/src/test/org/apache/solr/util/PrimUtilsTest.java > (original) > +++ lucene/dev/trunk/solr/src/test/org/apache/solr/util/PrimUtilsTest.java > Fri Sep 3 17:12:26 2010 > @@ -51,4 +51,44 @@ public class PrimUtilsTest extends Lucen > } > } > > + public void testLongPriorityQueue() { > + int maxSize = 100; > + long[] a = new long[maxSize]; > + long[] discards = new long[maxSize]; > + > + for (int iter=0; iter<100; iter++) { > + int discardCount = 0; > + int startSize = r.nextInt(maxSize) + 1; > + int endSize = startSize==maxSize ? maxSize : startSize + > r.nextInt(maxSize-startSize); > + int adds = r.nextInt(maxSize+1); > + // System.out.println("startSize=" + startSize + " endSize=" + > endSize + " adds="+adds); > + LongPriorityQueue pq = new LongPriorityQueue(startSize, endSize, > Long.MIN_VALUE); > + > + for (int i=0; i + long v = r.nextLong(); > + a[i] = v; > + long out = pq.insertWithOverflow(v); > + if (i < endSize) { > + assertEquals(out, Long.MIN_VALUE); > + } else { > + discards[discardCount++] = out; > + } > + } > + assertEquals(Math.min(adds,endSize), pq.size()); > + assertEquals(adds, pq.size() + discardCount); > + > + Arrays.sort(a, 0, adds); > + Arrays.sort(discards, 0, discardCount); > + for (int i=0; i + assertEquals(a[i], discards[i]); > + } > + > + for (int i=discardCount; i + assertEquals(a[i], pq.pop()); > + } > + > + assertEquals(0, pq.size()); > + } > + } > + > } > \ No newline at end of file > > > -- Robert Muir rcmuir@gmail.com --0015175ccf9ac71d7d048f5f0bc6 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Does SimpleFacetsTest fail for you?

I svn up'ed and = i see a few failures

On Fri, Sep 3, 2010 = at 1:12 PM, <yoni= k@apache.org> wrote:
Author: yonik
Date: Fri Sep =C2=A03 17:12:26 2010
New Revision: 992382

URL: http://svn.apache.org/viewvc?rev=3D992382&view=3Drev
Log:
SOLR-2092: use native long PQ to order facet results

Added:
=C2=A0 =C2=A0lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPrior= ityQueue.java =C2=A0 (with props)
Modified:
=C2=A0 =C2=A0lucene/dev/trunk/solr/CHANGES.txt
=C2=A0 =C2=A0lucene/dev/trunk/solr/src/java/org/apache/solr/request/Simple= Facets.java
=C2=A0 =C2=A0lucene/dev/trunk/solr/src/java/org/apache/solr/request/UnInve= rtedField.java
=C2=A0 =C2=A0lucene/dev/trunk/solr/src/test/org/apache/solr/util/PrimUtils= Test.java

Modified: lucene/dev/trunk/solr/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/solr/CHANGES.txt?rev= =3D992382&r1=3D992381&r2=3D992382&view=3Ddiff
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D
--- lucene/dev/trunk/solr/CHANGES.txt (original)
+++ lucene/dev/trunk/solr/CHANGES.txt Fri Sep =C2=A03 17:12:26 2010
@@ -288,6 +288,12 @@ Optimizations
=C2=A0* SOLR-2046: Simplify legacy replication scripts by adding common fun= ctions
=C2=A0 to scripts-util. (koji)

+* SOLR-2092: Speed up single-valued and multi-valued "fc" faceti= ng. Typical
+ =C2=A0improvement is 5%, but can be much greater (up to 10x faster) when = facet.offset
+ =C2=A0is very large (deep paging). (yonik)
+
+
+
=C2=A0Bug Fixes
=C2=A0----------------------


Modified: lucene/dev/trunk/solr/src/java/org/apache/solr/request/SimpleFace= ts.java
URL: http://svn.apache.org/viewv= c/lucene/dev/trunk/solr/src/java/org/apache/solr/request/SimpleFacets.java?= rev=3D992382&r1=3D992381&r2=3D992382&view=3Ddiff
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D
--- lucene/dev/trunk/solr/src/java/org/apache/solr/request/SimpleFacets.jav= a (original)
+++ lucene/dev/trunk/solr/src/java/org/apache/solr/request/SimpleFacets.jav= a Fri Sep =C2=A03 17:12:26 2010
@@ -44,6 +44,7 @@ import org.apache.solr.util.BoundedTreeS
=C2=A0import org.apache.solr.util.ByteUtils;
=C2=A0import org.apache.solr.util.DateMathParser;
=C2=A0import org.apache.solr.handler.component.ResponseBuilder;
+import org.apache.solr.util.LongPriorityQueue;

=C2=A0import java.io.IOException;
=C2=A0import java.util.*;
@@ -416,9 +417,9 @@ public class SimpleFacets {
=C2=A0 =C2=A0 }

=C2=A0 =C2=A0 final int nTerms=3DendTermIndex-startTermIndex;
+ =C2=A0 =C2=A0int missingCount =3D -1;

=C2=A0 =C2=A0 CharArr spare =3D new CharArr();
-
=C2=A0 =C2=A0 if (nTerms>0 && docs.size() >=3D mincount) {
=C2=A0 =C2=A0 =C2=A0 // count collection array only needs to be as big as = the number of terms we are
@@ -475,6 +476,10 @@ public class SimpleFacets {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
=C2=A0 =C2=A0 =C2=A0 }

+ =C2=A0 =C2=A0 =C2=A0if (startTermIndex =3D=3D 0) {
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0missingCount =3D counts[0];
+ =C2=A0 =C2=A0 =C2=A0}
+
=C2=A0 =C2=A0 =C2=A0 // IDEA: we could also maintain a count of "othe= r"... everything that fell outside
=C2=A0 =C2=A0 =C2=A0 // of the top 'N'

@@ -484,7 +489,8 @@ public class SimpleFacets {
=C2=A0 =C2=A0 =C2=A0 if (sort.equals(FacetParams.FACET_SORT_COUNT) || sort= .equals(FacetParams.FACET_SORT_COUNT_LEGACY)) {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 int maxsize =3D limit>0 ? offset+limit : In= teger.MAX_VALUE-1;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 maxsize =3D Math.min(maxsize, nTerms);
- =C2=A0 =C2=A0 =C2=A0 =C2=A0final BoundedTreeSet<CountPair<BytesRef,= Integer>> queue =3D new BoundedTreeSet<CountPair<BytesRef,Integ= er>>(maxsize);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0LongPriorityQueue queue =3D new LongPriorityQu= eue(Math.min(maxsize,1000), maxsize, Long.MIN_VALUE);
+
=C2=A0 =C2=A0 =C2=A0 =C2=A0 int min=3Dmincount-1; =C2=A0// the smallest va= lue in the top 'N' values
=C2=A0 =C2=A0 =C2=A0 =C2=A0 for (int i=3D(startTermIndex=3D=3D0)?1:0; i<= ;nTerms; i++) {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 int c =3D counts[i];
@@ -492,18 +498,33 @@ public class SimpleFacets {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // NOTE: we use c>min rather = than c>=3Dmin as an optimization because we are going in
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // index order, so we already kn= ow that the keys are ordered. =C2=A0This can be very
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // important if a lot of the cou= nts are repeated (like zero counts would be).
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0queue.add(new CountPair<Bytes= Ref,Integer>(si.lookup(startTermIndex+i, new BytesRef()), c));
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (queue.size()>=3Dmaxsize) = min=3Dqueue.last().val;
+
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// smaller term numbers sort hig= her, so subtract the term number instead
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0long pair =3D (((long)c)<<= 32) + (Integer.MAX_VALUE - i);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0boolean displaced =3D queue.inse= rt(pair);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (displaced) min=3D(int)(queue= .top() >>> 32);
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }
=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
- =C2=A0 =C2=A0 =C2=A0 =C2=A0// now select the right page from the results<= br> - =C2=A0 =C2=A0 =C2=A0 =C2=A0for (CountPair<BytesRef,Integer> p : que= ue) {
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (--off>=3D0) continue;
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (--lim<0) break;
+
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0// if we are deep paging, we don't have to= order the highest "offset" counts.
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0int collectCount =3D Math.max(0, queue.size() = - off);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0assert collectCount < lim;
+
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0// the start and end indexes of our list "= ;sorted" (starting with the highest value)
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0int sortedIdxStart =3D queue.size() - (collect= Count - 1);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0int sortedIdxEnd =3D queue.size() + 1;
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0final long[] sorted =3D queue.sort(collectCoun= t);
+
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0for (int i=3DsortedIdxStart; i<sortedIdxEnd= ; i++) {
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0long pair =3D sorted[i];
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0int c =3D (int)(pair >>> 32);<= br> + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0int tnum =3D Integer.MAX_VALUE - (int)p= air;
+
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 spare.reset();
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0ft.indexedToReadable(p.key, spare);
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0res.add(spare.toString(), p.val);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0ft.indexedToReadable(si.lookup(startTer= mIndex+tnum, br), spare);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0res.add(spare.toString(), c);
=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
+
=C2=A0 =C2=A0 =C2=A0 } else {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 // add results in index order
=C2=A0 =C2=A0 =C2=A0 =C2=A0 int i=3D(startTermIndex=3D=3D0)?1:0;
@@ -526,7 +547,10 @@ public class SimpleFacets {
=C2=A0 =C2=A0 }

=C2=A0 =C2=A0 if (missing) {
- =C2=A0 =C2=A0 =C2=A0res.add(null, getFieldMissingCount(searcher,docs,fiel= dName));
+ =C2=A0 =C2=A0 =C2=A0if (missingCount < 0) {
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0missingCount =3D getFieldMissingCount(searcher= ,docs,fieldName);
+ =C2=A0 =C2=A0 =C2=A0}
+ =C2=A0 =C2=A0 =C2=A0res.add(null, missingCount);
=C2=A0 =C2=A0 }

=C2=A0 =C2=A0 return res;

Modified: lucene/dev/trunk/solr/src/java/org/apache/solr/request/UnInverted= Field.java
URL: http://svn.apache.org/vi= ewvc/lucene/dev/trunk/solr/src/java/org/apache/solr/request/UnInvertedField= .java?rev=3D992382&r1=3D992381&r2=3D992382&view=3Ddiff
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D
--- lucene/dev/trunk/solr/src/java/org/apache/solr/request/UnInvertedField.= java (original)
+++ lucene/dev/trunk/solr/src/java/org/apache/solr/request/UnInvertedField.= java Fri Sep =C2=A03 17:12:26 2010
@@ -37,6 +37,7 @@ import org.apache.solr.core.SolrCore;
=C2=A0import org.apache.solr.schema.FieldType;
=C2=A0import org.apache.solr.schema.TrieField;
=C2=A0import org.apache.solr.search.*;
+import org.apache.solr.util.LongPriorityQueue;
=C2=A0import org.apache.solr.util.PrimUtils;
=C2=A0import org.apache.solr.util.BoundedTreeSet;
=C2=A0import org.apache.solr.handler.component.StatsValues;
@@ -470,7 +471,9 @@ public class UnInvertedField {
=C2=A0 =C2=A0 if (baseSize >=3D mincount) {

=C2=A0 =C2=A0 =C2=A0 final int[] index =3D this.index;
- =C2=A0 =C2=A0 =C2=A0final int[] counts =3D new int[numTermsInField];
+ =C2=A0 =C2=A0 =C2=A0// tricky: we add more more element than we need beca= use we will reuse this array later
+ =C2=A0 =C2=A0 =C2=A0// for ordering term ords before converting to term l= abels.
+ =C2=A0 =C2=A0 =C2=A0final int[] counts =3D new int[numTermsInField + 1];<= br>
=C2=A0 =C2=A0 =C2=A0 //
=C2=A0 =C2=A0 =C2=A0 // If there is prefix, find it's start and end te= rm numbers
@@ -575,7 +578,8 @@ public class UnInvertedField {
=C2=A0 =C2=A0 =C2=A0 if (sort.equals(FacetParams.FACET_SORT_COUNT) || sort= .equals(FacetParams.FACET_SORT_COUNT_LEGACY)) {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 int maxsize =3D limit>0 ? offset+limit : In= teger.MAX_VALUE-1;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 maxsize =3D Math.min(maxsize, numTermsInField)= ;
- =C2=A0 =C2=A0 =C2=A0 =C2=A0final BoundedTreeSet<Long> queue =3D new= BoundedTreeSet<Long>(maxsize);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0LongPriorityQueue queue =3D new LongPriorityQu= eue(Math.min(maxsize,1000), maxsize, Long.MIN_VALUE);
+
=C2=A0 =C2=A0 =C2=A0 =C2=A0 int min=3Dmincount-1; =C2=A0// the smallest va= lue in the top 'N' values
=C2=A0 =C2=A0 =C2=A0 =C2=A0 for (int i=3DstartTerm; i<endTerm; i++) { =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 int c =3D doNegative ? maxTermCounts[i]= - counts[i] : counts[i];
@@ -584,55 +588,63 @@ public class UnInvertedField {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // index order, so we already kn= ow that the keys are ordered. =C2=A0This can be very
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // important if a lot of the cou= nts are repeated (like zero counts would be).

- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// minimize object creation and = speed comparison by creating a long that
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// encompasses both count and te= rm number.
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// Since smaller values are kept= in the TreeSet, make higher counts smaller.
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0//
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// =C2=A0 for equal counts, lowe= r term numbers
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// should come first and hence b= e "greater"
-
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0//long pair =3D (((long)c)<&l= t;32) | (0x7fffffff-i) ; =C2=A0 // use if priority queue
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0long pair =3D (((long)-c)<<= ;32) | i;
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0queue.add(new Long(pair));
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (queue.size()>=3Dmaxsize) = min=3D-(int)(queue.last().longValue() >>> 32);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// smaller term numbers sort hig= her, so subtract the term number instead
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0long pair =3D (((long)c)<<= 32) + (Integer.MAX_VALUE - i);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0boolean displaced =3D queue.inse= rt(pair);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (displaced) min=3D(int)(queue= .top() >>> 32);
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }
=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
+
=C2=A0 =C2=A0 =C2=A0 =C2=A0 // now select the right page from the results<= br>
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0// if we are deep paging, we don't have to= order the highest "offset" counts.
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0int collectCount =3D Math.max(0, queue.size() = - off);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0assert collectCount < lim;
+
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0// the start and end indexes of our list "= ;sorted" (starting with the highest value)
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0int sortedIdxStart =3D queue.size() - (collect= Count - 1);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0int sortedIdxEnd =3D queue.size() + 1;
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0final long[] sorted =3D queue.sort(collectCoun= t);

- =C2=A0 =C2=A0 =C2=A0 =C2=A0final int[] tnums =3D new int[Math.min(Math.ma= x(0, queue.size()-off), lim)];
=C2=A0 =C2=A0 =C2=A0 =C2=A0 final int[] indirect =3D counts; =C2=A0// reus= e the counts array for the index into the tnums array
- =C2=A0 =C2=A0 =C2=A0 =C2=A0assert indirect.length >=3D tnums.length; -
- =C2=A0 =C2=A0 =C2=A0 =C2=A0int tnumCount =3D 0;
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0assert indirect.length >=3D sortedIdxEnd; +
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0for (int i=3DsortedIdxStart; i<sortedIdxEnd= ; i++) {
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0long pair =3D sorted[i];
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0int c =3D (int)(pair >>> 32);<= br> + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0int tnum =3D Integer.MAX_VALUE - (int)p= air;
+
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0indirect[i] =3D i; =C2=A0 // store the = index for indirect sorting
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0sorted[i] =3D tnum; =C2=A0// reuse the = "sorted" array to store the term numbers for indirect sorting

- =C2=A0 =C2=A0 =C2=A0 =C2=A0for (Long p : queue) {
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (--off>=3D0) continue;
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (--lim<0) break;
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0int c =3D -(int)(p.longValue() >>= > 32);
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0//int tnum =3D 0x7fffffff - (int)p.long= Value(); =C2=A0// use if priority queue
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0int tnum =3D (int)p.longValue();
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0indirect[tnumCount] =3D tnumCount;
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0tnums[tnumCount++] =3D tnum;
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// String label =3D ft.indexedToReadabl= e(getTermText(te, tnum));
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // add a null label for now... we'l= l fill it in later.
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 res.add(null, c);
=C2=A0 =C2=A0 =C2=A0 =C2=A0 }

=C2=A0 =C2=A0 =C2=A0 =C2=A0 // now sort the indexes by the term numbers - =C2=A0 =C2=A0 =C2=A0 =C2=A0PrimUtils.sort(0, tnumCount, indirect, new Pri= mUtils.IntComparator() {
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0PrimUtils.sort(sortedIdxStart, sortedIdxEnd, i= ndirect, new PrimUtils.IntComparator() {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 @Override
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 public int compare(int a, int b) {
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return tnums[a] - tnums[b];
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return (int)sorted[a] - (int)sor= ted[b];
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0}
+
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0@Override
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0public boolean lessThan(int a, int b) {=
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return sorted[a] < sorted[b];=
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0}
+
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0@Override
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0public boolean equals(int a, int b) { + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return sorted[a] =3D=3D sorted[b= ];
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 }
=C2=A0 =C2=A0 =C2=A0 =C2=A0 });

=C2=A0 =C2=A0 =C2=A0 =C2=A0 // convert the term numbers to term values and= set as the label
- =C2=A0 =C2=A0 =C2=A0 =C2=A0for (int i=3D0; i<tnumCount; i++) {
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0for (int i=3DsortedIdxStart; i<sortedIdxEnd= ; i++) {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 int idx =3D indirect[i];
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0int tnum =3D tnums[idx];
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0String label =3D getReadableValue(getTe= rmValue(te, tnum), ft, spare);
- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0res.setName(idx, label);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0int tnum =3D (int)sorted[idx];
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0String label =3D getReadableValue(getTe= rmValue(te, tnum), ft, spare);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0res.setName(idx - sortedIdxStart, label= );
=C2=A0 =C2=A0 =C2=A0 =C2=A0 }

=C2=A0 =C2=A0 =C2=A0 } else {

Added: lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorityQueu= e.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/solr/src/ja= va/org/apache/solr/util/LongPriorityQueue.java?rev=3D992382&view=3Dauto=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D
--- lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorityQueue.j= ava (added)
+++ lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorityQueue.j= ava Fri Sep =C2=A03 17:12:26 2010
@@ -0,0 +1,235 @@
+package org.apache.solr.util;
+
+import java.util.Arrays;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. =C2=A0See the NOTICE file distributed w= ith
+ * 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 complian= ce with
+ * the License. =C2=A0You may obtain a copy of the License at
+ *
+ * =C2=A0 =C2=A0 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" BA= SIS,
+ * 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.
+ */
+
+/** A native long priority queue.
+ *
+ * @lucene.internal
+*/
+public class LongPriorityQueue {
+ =C2=A0protected int size; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // nu= mber of elements currently in the queue
+ =C2=A0protected int currentCapacity; =C2=A0// number of elements the queu= e can hold w/o expanding
+ =C2=A0protected int maxSize; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// max num= ber of elements allowed in the queue
+ =C2=A0protected long[] heap;
+ =C2=A0protected final long sentinel; =C2=A0 // represents a null return v= alue
+
+ =C2=A0public LongPriorityQueue(int initialSize, int maxSize, long sentine= l) {
+ =C2=A0 =C2=A0this.maxSize =3D maxSize;
+ =C2=A0 =C2=A0this.sentinel =3D sentinel;
+ =C2=A0 =C2=A0initialize(initialSize);
+ =C2=A0}
+
+
+ =C2=A0protected void initialize(int sz) {
+ =C2=A0 =C2=A0int heapSize;
+ =C2=A0 =C2=A0if (0 =3D=3D sz)
+ =C2=A0 =C2=A0 =C2=A0// We allocate 1 extra to avoid if statement in top()=
+ =C2=A0 =C2=A0 =C2=A0heapSize =3D 2;
+ =C2=A0 =C2=A0else {
+ =C2=A0 =C2=A0 =C2=A0// NOTE: we add +1 because all access to heap is
+ =C2=A0 =C2=A0 =C2=A0// 1-based not 0-based. =C2=A0heap[0] is unused.
+ =C2=A0 =C2=A0 =C2=A0heapSize =3D Math.max(sz, sz + 1); // handle overflow=
+ =C2=A0 =C2=A0}
+ =C2=A0 =C2=A0heap =3D new long[heapSize];
+ =C2=A0 =C2=A0currentCapacity =3D sz;
+ =C2=A0}
+
+ =C2=A0public int getCurrentCapacity() {
+ =C2=A0 =C2=A0return currentCapacity;
+ =C2=A0}
+
+ =C2=A0public void resize(int sz) {
+ =C2=A0 =C2=A0int heapSize;
+ =C2=A0 =C2=A0if (sz > maxSize) {
+ =C2=A0 =C2=A0 =C2=A0maxSize =3D sz;
+ =C2=A0 =C2=A0}
+ =C2=A0 =C2=A0if (0 =3D=3D sz)
+ =C2=A0 =C2=A0 =C2=A0// We allocate 1 extra to avoid if statement in top()=
+ =C2=A0 =C2=A0 =C2=A0heapSize =3D 2;
+ =C2=A0 =C2=A0else {
+ =C2=A0 =C2=A0 =C2=A0heapSize =3D Math.max(sz, sz + 1); // handle overflow=
+ =C2=A0 =C2=A0}
+ =C2=A0 =C2=A0heap =3D Arrays.copyOf(heap, heapSize);
+ =C2=A0 =C2=A0currentCapacity =3D sz;
+ =C2=A0}
+
+ =C2=A0/**
+ =C2=A0 * Adds an object to a PriorityQueue in log(size) time. If one trie= s to add
+ =C2=A0 * more objects than maxSize from initialize an
+ =C2=A0 * {@link ArrayIndexOutOfBoundsException} is thrown.
+ =C2=A0 *
+ =C2=A0 * @return the new 'top' element in the queue.
+ =C2=A0 */
+ =C2=A0public long add(long element) {
+ =C2=A0 =C2=A0if (size >=3D currentCapacity) {
+ =C2=A0 =C2=A0 =C2=A0int newSize =3D Math.min(currentCapacity <<1, m= axSize);
+ =C2=A0 =C2=A0 =C2=A0if (newSize < currentCapacity) newSize =3D Integer= .MAX_VALUE; =C2=A0// handle overflow
+ =C2=A0 =C2=A0 =C2=A0resize(newSize);
+ =C2=A0 =C2=A0}
+ =C2=A0 =C2=A0size++;
+ =C2=A0 =C2=A0heap[size] =3D element;
+ =C2=A0 =C2=A0upHeap();
+ =C2=A0 =C2=A0return heap[1];
+ =C2=A0}
+
+ /**
+ =C2=A0 * Adds an object to a PriorityQueue in log(size) time. If one trie= s to add
+ =C2=A0 * more objects than the current capacity, an
+ =C2=A0 * {@link ArrayIndexOutOfBoundsException} is thrown.
+ =C2=A0 */
+ =C2=A0public void addNoCheck(long element) {
+ =C2=A0 =C2=A0++size;
+ =C2=A0 =C2=A0heap[size] =3D element;
+ =C2=A0 =C2=A0upHeap();
+ =C2=A0}
+
+ =C2=A0/**
+ =C2=A0 * Adds an object to a PriorityQueue in log(size) time.
+ =C2=A0 * It returns the smallest object (if any) that was
+ =C2=A0 * dropped off the heap because it was full, or
+ =C2=A0 * the sentinel value.
+ =C2=A0 *
+ =C2=A0 * =C2=A0This can be
+ =C2=A0 * the given parameter (in case it is smaller than the
+ =C2=A0 * full heap's minimum, and couldn't be added), or another<= br> + =C2=A0 * object that was previously the smallest value in the
+ =C2=A0 * heap and now has been replaced by a larger one, or null
+ =C2=A0 * if the queue wasn't yet full with maxSize elements.
+ =C2=A0 */
+ =C2=A0public long insertWithOverflow(long element) {
+ =C2=A0 =C2=A0if (size < maxSize) {
+ =C2=A0 =C2=A0 =C2=A0add(element);
+ =C2=A0 =C2=A0 =C2=A0return sentinel;
+ =C2=A0 =C2=A0} else if (element > heap[1]) {
+ =C2=A0 =C2=A0 =C2=A0long ret =3D heap[1];
+ =C2=A0 =C2=A0 =C2=A0heap[1] =3D element;
+ =C2=A0 =C2=A0 =C2=A0updateTop();
+ =C2=A0 =C2=A0 =C2=A0return ret;
+ =C2=A0 =C2=A0} else {
+ =C2=A0 =C2=A0 =C2=A0return element;
+ =C2=A0 =C2=A0}
+ =C2=A0}
+
+ =C2=A0/** inserts the element and returns true if this element caused ano= ther element
+ =C2=A0 * to be dropped from the queue. */
+ =C2=A0public boolean insert(long element) {
+ =C2=A0 =C2=A0if (size < maxSize) {
+ =C2=A0 =C2=A0 =C2=A0add(element);
+ =C2=A0 =C2=A0 =C2=A0return false;
+ =C2=A0 =C2=A0} else if (element > heap[1]) {
+ =C2=A0 =C2=A0 =C2=A0// long ret =3D heap[1];
+ =C2=A0 =C2=A0 =C2=A0heap[1] =3D element;
+ =C2=A0 =C2=A0 =C2=A0updateTop();
+ =C2=A0 =C2=A0 =C2=A0return true;
+ =C2=A0 =C2=A0} else {
+ =C2=A0 =C2=A0 =C2=A0return false;
+ =C2=A0 =C2=A0}
+ =C2=A0}
+
+ =C2=A0/** Returns the least element of the PriorityQueue in constant time= . */
+ =C2=A0public long top() {
+ =C2=A0 =C2=A0return heap[1];
+ =C2=A0}
+
+ =C2=A0/** Removes and returns the least element of the PriorityQueue in l= og(size)
+ =C2=A0 =C2=A0time. =C2=A0Only valid if size() > 0.
+ =C2=A0 */
+ =C2=A0public long pop() {
+ =C2=A0 =C2=A0long result =3D heap[1]; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 // save first value
+ =C2=A0 =C2=A0heap[1] =3D heap[size]; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0// move last to first
+ =C2=A0 =C2=A0size--;
+ =C2=A0 =C2=A0downHeap(); =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// ad= just heap
+ =C2=A0 =C2=A0return result;
+ =C2=A0}
+
+ =C2=A0/**
+ =C2=A0 * Should be called when the Object at top changes values.
+ =C2=A0 * @return the new 'top' element.
+ =C2=A0 */
+ =C2=A0public long updateTop() {
+ =C2=A0 =C2=A0downHeap();
+ =C2=A0 =C2=A0return heap[1];
+ =C2=A0}
+
+ =C2=A0/** Returns the number of elements currently stored in the Priority= Queue. */
+ =C2=A0public int size() {
+ =C2=A0 =C2=A0return size;
+ =C2=A0}
+
+ =C2=A0/** Returns the array used to hold the heap, with the smallest item= at array[1]
+ =C2=A0 * =C2=A0and the last (but not necessarily largest) at array[size()= ]. =C2=A0This is *not*
+ =C2=A0 * =C2=A0fully sorted.
+ =C2=A0 */
+ =C2=A0public long[] getInternalArray() {
+ =C2=A0 =C2=A0return heap;
+ =C2=A0}
+
+ =C2=A0/** Pops the smallest n items from the heap, placing them in the in= ternal array at
+ =C2=A0 * =C2=A0arr[size] through arr[size-(n-1)] with the smallest (first= element popped)
+ =C2=A0 * =C2=A0being at arr[size]. =C2=A0The internal array is returned.<= br> + =C2=A0 */
+ =C2=A0public long[] sort(int n) {
+ =C2=A0 =C2=A0while (--n >=3D 0) {
+ =C2=A0 =C2=A0 =C2=A0long result =3D heap[1]; =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 // save first value
+ =C2=A0 =C2=A0 =C2=A0heap[1] =3D heap[size]; =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0// move last to first
+ =C2=A0 =C2=A0 =C2=A0heap[size] =3D result; =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// place it last
+ =C2=A0 =C2=A0 =C2=A0size--;
+ =C2=A0 =C2=A0 =C2=A0downHeap(); =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// ad= just heap
+ =C2=A0 =C2=A0}
+ =C2=A0 =C2=A0return heap;
+ =C2=A0}
+
+ =C2=A0/** Removes all entries from the PriorityQueue. */
+ =C2=A0public void clear() {
+ =C2=A0 =C2=A0size =3D 0;
+ =C2=A0}
+
+ =C2=A0private void upHeap() {
+ =C2=A0 =C2=A0int i =3D size;
+ =C2=A0 =C2=A0long node =3D heap[i]; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // save bottom node
+ =C2=A0 =C2=A0int j =3D i >>> 1;
+ =C2=A0 =C2=A0while (j > 0 && node < heap[j]) {
+ =C2=A0 =C2=A0 =C2=A0heap[i] =3D heap[j]; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // shift parents down<= br> + =C2=A0 =C2=A0 =C2=A0i =3D j;
+ =C2=A0 =C2=A0 =C2=A0j =3D j >>> 1;
+ =C2=A0 =C2=A0}
+ =C2=A0 =C2=A0heap[i] =3D node; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// install sa= ved node
+ =C2=A0}
+
+ =C2=A0private void downHeap() {
+ =C2=A0 =C2=A0int i =3D 1;
+ =C2=A0 =C2=A0long node =3D heap[i]; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // save top node
+ =C2=A0 =C2=A0int j =3D i << 1; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// fin= d smaller child
+ =C2=A0 =C2=A0int k =3D j + 1;
+ =C2=A0 =C2=A0if (k <=3D size && heap[k] < heap[j]) {
+ =C2=A0 =C2=A0 =C2=A0j =3D k;
+ =C2=A0 =C2=A0}
+ =C2=A0 =C2=A0while (j <=3D size && heap[j] < node) {
+ =C2=A0 =C2=A0 =C2=A0heap[i] =3D heap[j]; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // shift up child
+ =C2=A0 =C2=A0 =C2=A0i =3D j;
+ =C2=A0 =C2=A0 =C2=A0j =3D i << 1;
+ =C2=A0 =C2=A0 =C2=A0k =3D j + 1;
+ =C2=A0 =C2=A0 =C2=A0if (k <=3D size && heap[k] < heap[j]) {=
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0j =3D k;
+ =C2=A0 =C2=A0 =C2=A0}
+ =C2=A0 =C2=A0}
+ =C2=A0 =C2=A0heap[i] =3D node; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// install sa= ved node
+ =C2=A0}
+}

Propchange: lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorit= yQueue.java
---------------------------------------------------------------------------= ---
=C2=A0 =C2=A0svn:eol-style =3D native

Propchange: lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorit= yQueue.java
---------------------------------------------------------------------------= ---
=C2=A0 =C2=A0svn:executable =3D *

Propchange: lucene/dev/trunk/solr/src/java/org/apache/solr/util/LongPriorit= yQueue.java
---------------------------------------------------------------------------= ---
=C2=A0 =C2=A0svn:keywords =3D Date Author Id Revision HeadURL

Modified: lucene/dev/trunk/solr/src/test/org/apache/solr/util/PrimUtilsTest= .java
URL: http://svn.apache.org/viewvc/= lucene/dev/trunk/solr/src/test/org/apache/solr/util/PrimUtilsTest.java?rev= =3D992382&r1=3D992381&r2=3D992382&view=3Ddiff
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D
--- lucene/dev/trunk/solr/src/test/org/apache/solr/util/PrimUtilsTest.java = (original)
+++ lucene/dev/trunk/solr/src/test/org/apache/solr/util/PrimUtilsTest.java = Fri Sep =C2=A03 17:12:26 2010
@@ -51,4 +51,44 @@ public class PrimUtilsTest extends Lucen
=C2=A0 =C2=A0 }
=C2=A0 }

+ =C2=A0public void testLongPriorityQueue() {
+ =C2=A0 =C2=A0int maxSize =3D 100;
+ =C2=A0 =C2=A0long[] a =3D new long[maxSize];
+ =C2=A0 =C2=A0long[] discards =3D new long[maxSize];
+
+ =C2=A0 =C2=A0for (int iter=3D0; iter<100; iter++) {
+ =C2=A0 =C2=A0 =C2=A0int discardCount =3D 0;
+ =C2=A0 =C2=A0 =C2=A0int startSize =3D r.nextInt(maxSize) + 1;
+ =C2=A0 =C2=A0 =C2=A0int endSize =3D startSize=3D=3DmaxSize ? maxSize : st= artSize + r.nextInt(maxSize-startSize);
+ =C2=A0 =C2=A0 =C2=A0int adds =3D r.nextInt(maxSize+1);
+ =C2=A0 =C2=A0 =C2=A0// System.out.println("startSize=3D" + star= tSize + " endSize=3D" + endSize + " adds=3D"+adds);
+ =C2=A0 =C2=A0 =C2=A0LongPriorityQueue pq =3D new LongPriorityQueue(startS= ize, endSize, Long.MIN_VALUE);
+
+ =C2=A0 =C2=A0 =C2=A0for (int i=3D0; i<adds; i++) {
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0long v =3D r.nextLong();
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0a[i] =3D v;
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0long out =3D pq.insertWithOverflow(v);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0if (i < endSize) {
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0assertEquals(out, Long.MIN_VALUE);
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0} else {
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0discards[discardCount++] =3D out;
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0}
+ =C2=A0 =C2=A0 =C2=A0}
+ =C2=A0 =C2=A0 =C2=A0assertEquals(Math.min(adds,endSize), pq.size());
+ =C2=A0 =C2=A0 =C2=A0assertEquals(adds, pq.size() + discardCount);
+
+ =C2=A0 =C2=A0 =C2=A0Arrays.sort(a, 0, adds);
+ =C2=A0 =C2=A0 =C2=A0Arrays.sort(discards, 0, discardCount);
+ =C2=A0 =C2=A0 =C2=A0for (int i=3D0; i<discardCount; i++) {
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0assertEquals(a[i], discards[i]);
+ =C2=A0 =C2=A0 =C2=A0}
+
+ =C2=A0 =C2=A0 =C2=A0for (int i=3DdiscardCount; i<adds; i++) {
+ =C2=A0 =C2=A0 =C2=A0 =C2=A0assertEquals(a[i], pq.pop());
+ =C2=A0 =C2=A0 =C2=A0}
+
+ =C2=A0 =C2=A0 =C2=A0assertEquals(0, pq.size());
+ =C2=A0 =C2=A0}
+ =C2=A0}
+
=C2=A0}
\ No newline at end of file





--
Robert Muir
rcmuir@gmail.com
--0015175ccf9ac71d7d048f5f0bc6--