You are viewing a plain text version of this content. The canonical link for it is here.
Posted to java-commits@lucene.apache.org by us...@apache.org on 2009/02/13 19:27:02 UTC
svn commit: r744207 [2/2] - in /lucene/java/trunk/contrib/queries/src:
java/org/apache/lucene/search/trie/ test/org/apache/lucene/search/trie/
Copied: lucene/java/trunk/contrib/queries/src/test/org/apache/lucene/search/trie/TestLongTrieRangeFilter.java (from r742792, lucene/java/trunk/contrib/queries/src/test/org/apache/lucene/search/trie/TestTrieRangeQuery.java)
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/queries/src/test/org/apache/lucene/search/trie/TestLongTrieRangeFilter.java?p2=lucene/java/trunk/contrib/queries/src/test/org/apache/lucene/search/trie/TestLongTrieRangeFilter.java&p1=lucene/java/trunk/contrib/queries/src/test/org/apache/lucene/search/trie/TestTrieRangeQuery.java&r1=742792&r2=744207&rev=744207&view=diff
==============================================================================
--- lucene/java/trunk/contrib/queries/src/test/org/apache/lucene/search/trie/TestTrieRangeQuery.java (original)
+++ lucene/java/trunk/contrib/queries/src/test/org/apache/lucene/search/trie/TestLongTrieRangeFilter.java Fri Feb 13 18:27:01 2009
@@ -25,6 +25,7 @@
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriter.MaxFieldLength;
import org.apache.lucene.store.RAMDirectory;
+import org.apache.lucene.search.Query;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.ScoreDoc;
import org.apache.lucene.search.TopDocs;
@@ -32,9 +33,14 @@
import org.apache.lucene.search.RangeQuery;
import org.apache.lucene.util.LuceneTestCase;
-public class TestTrieRangeQuery extends LuceneTestCase
+public class TestLongTrieRangeFilter extends LuceneTestCase
{
- private static final long distance=66666;
+ // distance of entries
+ private static final long distance = 66666L;
+ // shift the starting of the values to the left, to also have negative values:
+ private static final long startOffset = - 1L << 31;
+ // number of docs to generate for testing
+ private static final int noDocs = 10000;
private static final RAMDirectory directory;
private static final IndexSearcher searcher;
@@ -44,29 +50,21 @@
IndexWriter writer = new IndexWriter(directory, new WhitespaceAnalyzer(),
true, MaxFieldLength.UNLIMITED);
- // Add a series of 10000 docs with increasing long values
- for (long l=0L; l<10000L; l++) {
+ // Add a series of noDocs docs with increasing long values
+ for (int l=0; l<noDocs; l++) {
Document doc=new Document();
// add fields, that have a distance to test general functionality
- TrieUtils.VARIANT_8BIT.addLongTrieCodedDocumentField(
- doc, "field8", distance*l, true /*index it*/, Field.Store.YES
- );
- TrieUtils.VARIANT_4BIT.addLongTrieCodedDocumentField(
- doc, "field4", distance*l, true /*index it*/, Field.Store.YES
- );
- TrieUtils.VARIANT_2BIT.addLongTrieCodedDocumentField(
- doc, "field2", distance*l, true /*index it*/, Field.Store.YES
- );
- // add ascending fields with a distance of 1 to test the correct splitting of range and inclusive/exclusive
- TrieUtils.VARIANT_8BIT.addLongTrieCodedDocumentField(
- doc, "ascfield8", l, true /*index it*/, Field.Store.NO
- );
- TrieUtils.VARIANT_4BIT.addLongTrieCodedDocumentField(
- doc, "ascfield4", l, true /*index it*/, Field.Store.NO
- );
- TrieUtils.VARIANT_2BIT.addLongTrieCodedDocumentField(
- doc, "ascfield2", l, true /*index it*/, Field.Store.NO
- );
+ final long val=distance*l+startOffset;
+ TrieUtils.addIndexedFields(doc,"field8", TrieUtils.trieCodeLong(val, 8));
+ doc.add(new Field("field8", TrieUtils.longToPrefixCoded(val), Field.Store.YES, Field.Index.NO));
+ TrieUtils.addIndexedFields(doc,"field4", TrieUtils.trieCodeLong(val, 4));
+ doc.add(new Field("field4", TrieUtils.longToPrefixCoded(val), Field.Store.YES, Field.Index.NO));
+ TrieUtils.addIndexedFields(doc,"field2", TrieUtils.trieCodeLong(val, 2));
+ doc.add(new Field("field2", TrieUtils.longToPrefixCoded(val), Field.Store.YES, Field.Index.NO));
+ // add ascending fields with a distance of 1, beginning at -noDocs/2 to test the correct splitting of range and inclusive/exclusive
+ TrieUtils.addIndexedFields(doc,"ascfield8", TrieUtils.trieCodeLong(l-(noDocs/2), 8));
+ TrieUtils.addIndexedFields(doc,"ascfield4", TrieUtils.trieCodeLong(l-(noDocs/2), 4));
+ TrieUtils.addIndexedFields(doc,"ascfield2", TrieUtils.trieCodeLong(l-(noDocs/2), 2));
writer.addDocument(doc);
}
@@ -78,172 +76,200 @@
}
}
- private void testRange(final TrieUtils variant) throws Exception {
- String field="field"+variant.TRIE_BITS;
+ private void testRange(int precisionStep) throws Exception {
+ String field="field"+precisionStep;
int count=3000;
- long lower=96666L, upper=lower + count*distance + 1234L;
- TrieRangeQuery q=new TrieRangeQuery(field, new Long(lower), new Long(upper), true, true, variant);
- TopDocs topDocs = searcher.search(q, null, 10000, Sort.INDEXORDER);
- System.out.println("Found "+q.getLastNumberOfTerms()+" distinct terms in range for field '"+field+"'.");
+ long lower=(distance*3/2)+startOffset, upper=lower + count*distance + (distance/3);
+ LongTrieRangeFilter f=new LongTrieRangeFilter(field, precisionStep, new Long(lower), new Long(upper), true, true);
+ TopDocs topDocs = searcher.search(f.asQuery(), null, noDocs, Sort.INDEXORDER);
+ System.out.println("Found "+f.getLastNumberOfTerms()+" distinct terms in range for field '"+field+"'.");
ScoreDoc[] sd = topDocs.scoreDocs;
assertNotNull(sd);
- assertEquals("Score docs must match "+count+" docs, found "+sd.length+" docs", sd.length, count );
+ assertEquals("Score doc count", count, sd.length );
Document doc=searcher.doc(sd[0].doc);
- assertEquals("First doc should be "+(2*distance), variant.trieCodedToLong(doc.get(field)), 2*distance );
+ assertEquals("First doc", 2*distance+startOffset, TrieUtils.prefixCodedToLong(doc.get(field)) );
doc=searcher.doc(sd[sd.length-1].doc);
- assertEquals("Last doc should be "+((1+count)*distance), variant.trieCodedToLong(doc.get(field)), (1+count)*distance );
+ assertEquals("Last doc", (1+count)*distance+startOffset, TrieUtils.prefixCodedToLong(doc.get(field)) );
}
public void testRange_8bit() throws Exception {
- testRange(TrieUtils.VARIANT_8BIT);
+ testRange(8);
}
public void testRange_4bit() throws Exception {
- testRange(TrieUtils.VARIANT_4BIT);
+ testRange(4);
}
public void testRange_2bit() throws Exception {
- testRange(TrieUtils.VARIANT_2BIT);
+ testRange(2);
}
- private void testLeftOpenRange(final TrieUtils variant) throws Exception {
- String field="field"+variant.TRIE_BITS;
+ private void testLeftOpenRange(int precisionStep) throws Exception {
+ String field="field"+precisionStep;
int count=3000;
- long upper=(count-1)*distance + 1234L;
- TrieRangeQuery q=new TrieRangeQuery(field, null, new Long(upper), true, true, variant);
- TopDocs topDocs = searcher.search(q, null, 10000, Sort.INDEXORDER);
- System.out.println("Found "+q.getLastNumberOfTerms()+" distinct terms in left open range for field '"+field+"'.");
+ long upper=(count-1)*distance + (distance/3) + startOffset;
+ LongTrieRangeFilter f=new LongTrieRangeFilter(field, precisionStep, null, new Long(upper), true, true);
+ TopDocs topDocs = searcher.search(f.asQuery(), null, noDocs, Sort.INDEXORDER);
+ System.out.println("Found "+f.getLastNumberOfTerms()+" distinct terms in left open range for field '"+field+"'.");
ScoreDoc[] sd = topDocs.scoreDocs;
assertNotNull(sd);
- assertEquals("Score docs must match "+count+" docs, found "+sd.length+" docs", sd.length, count );
+ assertEquals("Score doc count", count, sd.length );
Document doc=searcher.doc(sd[0].doc);
- assertEquals("First doc should be 0", variant.trieCodedToLong(doc.get(field)), 0L );
+ assertEquals("First doc", startOffset, TrieUtils.prefixCodedToLong(doc.get(field)) );
doc=searcher.doc(sd[sd.length-1].doc);
- assertEquals("Last doc should be "+((count-1)*distance), variant.trieCodedToLong(doc.get(field)), (count-1)*distance );
+ assertEquals("Last doc", (count-1)*distance+startOffset, TrieUtils.prefixCodedToLong(doc.get(field)) );
}
public void testLeftOpenRange_8bit() throws Exception {
- testLeftOpenRange(TrieUtils.VARIANT_8BIT);
+ testLeftOpenRange(8);
}
public void testLeftOpenRange_4bit() throws Exception {
- testLeftOpenRange(TrieUtils.VARIANT_4BIT);
+ testLeftOpenRange(4);
}
public void testLeftOpenRange_2bit() throws Exception {
- testLeftOpenRange(TrieUtils.VARIANT_2BIT);
+ testLeftOpenRange(2);
}
- private void testRandomTrieAndClassicRangeQuery(final TrieUtils variant) throws Exception {
+ private void testRightOpenRange(int precisionStep) throws Exception {
+ String field="field"+precisionStep;
+ int count=3000;
+ long lower=(count-1)*distance + (distance/3) +startOffset;
+ LongTrieRangeFilter f=new LongTrieRangeFilter(field, precisionStep, new Long(lower), null, true, true);
+ TopDocs topDocs = searcher.search(f.asQuery(), null, noDocs, Sort.INDEXORDER);
+ System.out.println("Found "+f.getLastNumberOfTerms()+" distinct terms in right open range for field '"+field+"'.");
+ ScoreDoc[] sd = topDocs.scoreDocs;
+ assertNotNull(sd);
+ assertEquals("Score doc count", noDocs-count, sd.length );
+ Document doc=searcher.doc(sd[0].doc);
+ assertEquals("First doc", count*distance+startOffset, TrieUtils.prefixCodedToLong(doc.get(field)) );
+ doc=searcher.doc(sd[sd.length-1].doc);
+ assertEquals("Last doc", (noDocs-1)*distance+startOffset, TrieUtils.prefixCodedToLong(doc.get(field)) );
+ }
+
+ public void testRightOpenRange_8bit() throws Exception {
+ testRightOpenRange(8);
+ }
+
+ public void testRightOpenRange_4bit() throws Exception {
+ testRightOpenRange(4);
+ }
+
+ public void testRightOpenRange_2bit() throws Exception {
+ testRightOpenRange(2);
+ }
+
+ private void testRandomTrieAndClassicRangeQuery(int precisionStep) throws Exception {
final Random rnd=newRandom();
- String field="field"+variant.TRIE_BITS;
+ String field="field"+precisionStep;
// 50 random tests, the tests may also return 0 results, if min>max, but this is ok
for (int i=0; i<50; i++) {
- long lower=(long)(rnd.nextDouble()*10000L*distance);
- long upper=(long)(rnd.nextDouble()*10000L*distance);
+ long lower=(long)(rnd.nextDouble()*noDocs*distance)+startOffset;
+ long upper=(long)(rnd.nextDouble()*noDocs*distance)+startOffset;
// test inclusive range
- TrieRangeQuery tq=new TrieRangeQuery(field, new Long(lower), new Long(upper), true, true, variant);
- RangeQuery cq=new RangeQuery(field, variant.longToTrieCoded(lower), variant.longToTrieCoded(upper), true, true);
+ Query tq=new LongTrieRangeFilter(field, precisionStep, new Long(lower), new Long(upper), true, true).asQuery();
+ RangeQuery cq=new RangeQuery(field, TrieUtils.longToPrefixCoded(lower), TrieUtils.longToPrefixCoded(upper), true, true);
cq.setConstantScoreRewrite(true);
TopDocs tTopDocs = searcher.search(tq, 1);
TopDocs cTopDocs = searcher.search(cq, 1);
- assertEquals("Returned count for TrieRangeQuery and RangeQuery must be equal", tTopDocs.totalHits, cTopDocs.totalHits );
+ assertEquals("Returned count for LongTrieRangeFilter and RangeQuery must be equal", cTopDocs.totalHits, tTopDocs.totalHits );
// test exclusive range
- tq=new TrieRangeQuery(field, new Long(lower), new Long(upper), false, false, variant);
- cq=new RangeQuery(field, variant.longToTrieCoded(lower), variant.longToTrieCoded(upper), false, false);
+ tq=new LongTrieRangeFilter(field, precisionStep, new Long(lower), new Long(upper), false, false).asQuery();
+ cq=new RangeQuery(field, TrieUtils.longToPrefixCoded(lower), TrieUtils.longToPrefixCoded(upper), false, false);
cq.setConstantScoreRewrite(true);
tTopDocs = searcher.search(tq, 1);
cTopDocs = searcher.search(cq, 1);
- assertEquals("Returned count for TrieRangeQuery and RangeQuery must be equal", tTopDocs.totalHits, cTopDocs.totalHits );
+ assertEquals("Returned count for LongTrieRangeFilter and RangeQuery must be equal", cTopDocs.totalHits, tTopDocs.totalHits );
// test left exclusive range
- tq=new TrieRangeQuery(field, new Long(lower), new Long(upper), false, true, variant);
- cq=new RangeQuery(field, variant.longToTrieCoded(lower), variant.longToTrieCoded(upper), false, true);
+ tq=new LongTrieRangeFilter(field, precisionStep, new Long(lower), new Long(upper), false, true).asQuery();
+ cq=new RangeQuery(field, TrieUtils.longToPrefixCoded(lower), TrieUtils.longToPrefixCoded(upper), false, true);
cq.setConstantScoreRewrite(true);
tTopDocs = searcher.search(tq, 1);
cTopDocs = searcher.search(cq, 1);
- assertEquals("Returned count for TrieRangeQuery and RangeQuery must be equal", tTopDocs.totalHits, cTopDocs.totalHits );
+ assertEquals("Returned count for LongTrieRangeFilter and RangeQuery must be equal", cTopDocs.totalHits, tTopDocs.totalHits );
// test right exclusive range
- tq=new TrieRangeQuery(field, new Long(lower), new Long(upper), true, false, variant);
- cq=new RangeQuery(field, variant.longToTrieCoded(lower), variant.longToTrieCoded(upper), true, false);
+ tq=new LongTrieRangeFilter(field, precisionStep, new Long(lower), new Long(upper), true, false).asQuery();
+ cq=new RangeQuery(field, TrieUtils.longToPrefixCoded(lower), TrieUtils.longToPrefixCoded(upper), true, false);
cq.setConstantScoreRewrite(true);
tTopDocs = searcher.search(tq, 1);
cTopDocs = searcher.search(cq, 1);
- assertEquals("Returned count for TrieRangeQuery and RangeQuery must be equal", tTopDocs.totalHits, cTopDocs.totalHits );
+ assertEquals("Returned count for LongTrieRangeFilter and RangeQuery must be equal", cTopDocs.totalHits, tTopDocs.totalHits );
}
}
public void testRandomTrieAndClassicRangeQuery_8bit() throws Exception {
- testRandomTrieAndClassicRangeQuery(TrieUtils.VARIANT_8BIT);
+ testRandomTrieAndClassicRangeQuery(8);
}
public void testRandomTrieAndClassicRangeQuery_4bit() throws Exception {
- testRandomTrieAndClassicRangeQuery(TrieUtils.VARIANT_4BIT);
+ testRandomTrieAndClassicRangeQuery(4);
}
public void testRandomTrieAndClassicRangeQuery_2bit() throws Exception {
- testRandomTrieAndClassicRangeQuery(TrieUtils.VARIANT_2BIT);
+ testRandomTrieAndClassicRangeQuery(2);
}
- private void testRangeSplit(final TrieUtils variant) throws Exception {
+ private void testRangeSplit(int precisionStep) throws Exception {
final Random rnd=newRandom();
- String field="ascfield"+variant.TRIE_BITS;
+ String field="ascfield"+precisionStep;
// 50 random tests
for (int i=0; i<50; i++) {
- long lower=(long)(rnd.nextDouble()*10000L);
- long upper=(long)(rnd.nextDouble()*10000L);
+ long lower=(long)(rnd.nextDouble()*noDocs - noDocs/2);
+ long upper=(long)(rnd.nextDouble()*noDocs - noDocs/2);
if (lower>upper) {
long a=lower; lower=upper; upper=a;
}
// test inclusive range
- TrieRangeQuery tq=new TrieRangeQuery(field, new Long(lower), new Long(upper), true, true, variant);
+ Query tq=new LongTrieRangeFilter(field, precisionStep, new Long(lower), new Long(upper), true, true).asQuery();
TopDocs tTopDocs = searcher.search(tq, 1);
- assertEquals("Returned count of range query must be equal to inclusive range length", tTopDocs.totalHits, upper-lower+1 );
+ assertEquals("Returned count of range query must be equal to inclusive range length", upper-lower+1, tTopDocs.totalHits );
// test exclusive range
- tq=new TrieRangeQuery(field, new Long(lower), new Long(upper), false, false, variant);
+ tq=new LongTrieRangeFilter(field, precisionStep, new Long(lower), new Long(upper), false, false).asQuery();
tTopDocs = searcher.search(tq, 1);
- assertEquals("Returned count of range query must be equal to exclusive range length", tTopDocs.totalHits, Math.max(upper-lower-1, 0) );
+ assertEquals("Returned count of range query must be equal to exclusive range length", Math.max(upper-lower-1, 0), tTopDocs.totalHits );
// test left exclusive range
- tq=new TrieRangeQuery(field, new Long(lower), new Long(upper), false, true, variant);
+ tq=new LongTrieRangeFilter(field, precisionStep, new Long(lower), new Long(upper), false, true).asQuery();
tTopDocs = searcher.search(tq, 1);
- assertEquals("Returned count of range query must be equal to half exclusive range length", tTopDocs.totalHits, upper-lower );
+ assertEquals("Returned count of range query must be equal to half exclusive range length", upper-lower, tTopDocs.totalHits );
// test right exclusive range
- tq=new TrieRangeQuery(field, new Long(lower), new Long(upper), true, false, variant);
+ tq=new LongTrieRangeFilter(field, precisionStep, new Long(lower), new Long(upper), true, false).asQuery();
tTopDocs = searcher.search(tq, 1);
- assertEquals("Returned count of range query must be equal to half exclusive range length", tTopDocs.totalHits, upper-lower );
+ assertEquals("Returned count of range query must be equal to half exclusive range length", upper-lower, tTopDocs.totalHits );
}
}
public void testRangeSplit_8bit() throws Exception {
- testRangeSplit(TrieUtils.VARIANT_8BIT);
+ testRangeSplit(8);
}
public void testRangeSplit_4bit() throws Exception {
- testRangeSplit(TrieUtils.VARIANT_4BIT);
+ testRangeSplit(4);
}
public void testRangeSplit_2bit() throws Exception {
- testRangeSplit(TrieUtils.VARIANT_2BIT);
+ testRangeSplit(2);
}
- private void testSorting(final TrieUtils variant) throws Exception {
+ private void testSorting(int precisionStep) throws Exception {
final Random rnd=newRandom();
- String field="field"+variant.TRIE_BITS;
+ String field="field"+precisionStep;
// 10 random tests, the index order is ascending,
// so using a reverse sort field should retun descending documents
for (int i=0; i<10; i++) {
- long lower=(long)(rnd.nextDouble()*10000L*distance);
- long upper=(long)(rnd.nextDouble()*10000L*distance);
+ long lower=(long)(rnd.nextDouble()*noDocs*distance)+startOffset;
+ long upper=(long)(rnd.nextDouble()*noDocs*distance)+startOffset;
if (lower>upper) {
long a=lower; lower=upper; upper=a;
}
- TrieRangeQuery tq=new TrieRangeQuery(field, new Long(lower), new Long(upper), true, true, variant);
- TopDocs topDocs = searcher.search(tq, null, 10000, new Sort(variant.getSortField(field, true)));
+ Query tq=new LongTrieRangeFilter(field, precisionStep, new Long(lower), new Long(upper), true, true).asQuery();
+ TopDocs topDocs = searcher.search(tq, null, noDocs, new Sort(TrieUtils.getLongSortField(field, true)));
if (topDocs.totalHits==0) continue;
ScoreDoc[] sd = topDocs.scoreDocs;
assertNotNull(sd);
- long last=variant.trieCodedToLong(searcher.doc(sd[0].doc).get(field));
+ long last=TrieUtils.prefixCodedToLong(searcher.doc(sd[0].doc).get(field));
for (int j=1; j<sd.length; j++) {
- long act=variant.trieCodedToLong(searcher.doc(sd[j].doc).get(field));
+ long act=TrieUtils.prefixCodedToLong(searcher.doc(sd[j].doc).get(field));
assertTrue("Docs should be sorted backwards", last>act );
last=act;
}
@@ -251,15 +277,15 @@
}
public void testSorting_8bit() throws Exception {
- testSorting(TrieUtils.VARIANT_8BIT);
+ testSorting(8);
}
public void testSorting_4bit() throws Exception {
- testSorting(TrieUtils.VARIANT_4BIT);
+ testSorting(4);
}
public void testSorting_2bit() throws Exception {
- testSorting(TrieUtils.VARIANT_2BIT);
+ testSorting(2);
}
}
Modified: lucene/java/trunk/contrib/queries/src/test/org/apache/lucene/search/trie/TestTrieUtils.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/queries/src/test/org/apache/lucene/search/trie/TestTrieUtils.java?rev=744207&r1=744206&r2=744207&view=diff
==============================================================================
--- lucene/java/trunk/contrib/queries/src/test/org/apache/lucene/search/trie/TestTrieUtils.java (original)
+++ lucene/java/trunk/contrib/queries/src/test/org/apache/lucene/search/trie/TestTrieUtils.java Fri Feb 13 18:27:01 2009
@@ -17,155 +17,304 @@
* limitations under the License.
*/
-import java.util.Date;
-import java.util.GregorianCalendar;
-
import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.OpenBitSet;
-public class TestTrieUtils extends LuceneTestCase {
+import java.util.Arrays;
+import java.util.Iterator;
- public void testSpecialValues() throws Exception {
- // Variant 8bit values
- assertEquals( TrieUtils.VARIANT_8BIT.TRIE_CODED_NUMERIC_MIN, "\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100");
- assertEquals( TrieUtils.VARIANT_8BIT.TRIE_CODED_NUMERIC_MAX, "\u01ff\u01ff\u01ff\u01ff\u01ff\u01ff\u01ff\u01ff");
- assertEquals( TrieUtils.VARIANT_8BIT.longToTrieCoded(-1), "\u017f\u01ff\u01ff\u01ff\u01ff\u01ff\u01ff\u01ff");
- assertEquals( TrieUtils.VARIANT_8BIT.longToTrieCoded(0), "\u0180\u0100\u0100\u0100\u0100\u0100\u0100\u0100");
- assertEquals( TrieUtils.VARIANT_8BIT.longToTrieCoded(1), "\u0180\u0100\u0100\u0100\u0100\u0100\u0100\u0101");
- // Variant 4bit values
- assertEquals( TrieUtils.VARIANT_4BIT.TRIE_CODED_NUMERIC_MIN, "\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100");
- assertEquals( TrieUtils.VARIANT_4BIT.TRIE_CODED_NUMERIC_MAX, "\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f");
- assertEquals( TrieUtils.VARIANT_4BIT.longToTrieCoded(-1), "\u0107\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f\u010f");
- assertEquals( TrieUtils.VARIANT_4BIT.longToTrieCoded(0), "\u0108\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100");
- assertEquals( TrieUtils.VARIANT_4BIT.longToTrieCoded(1), "\u0108\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0100\u0101");
- // TODO: 2bit tests
- }
+public class TestTrieUtils extends LuceneTestCase {
- private void testBinaryOrderingAndIncrement(TrieUtils variant) throws Exception {
+ public void testLongConversionAndOrdering() throws Exception {
// generate a series of encoded longs, each numerical one bigger than the one before
String last=null;
for (long l=-100000L; l<100000L; l++) {
- String act=variant.longToTrieCoded(l);
+ String act=TrieUtils.longToPrefixCoded(l);
if (last!=null) {
// test if smaller
- assertTrue( last.compareTo(act) < 0 );
- // test the increment method (the last incremented by one should be the actual)
- assertEquals( variant.incrementTrieCoded(last), act );
- // test the decrement method (the actual decremented by one should be the last)
- assertEquals( last, variant.decrementTrieCoded(act) );
+ assertTrue("actual bigger than last", last.compareTo(act) < 0 );
}
+ // test is back and forward conversion works
+ assertEquals("forward and back conversion should generate same long", l, TrieUtils.prefixCodedToLong(act));
// next step
last=act;
}
}
- public void testBinaryOrderingAndIncrement_8bit() throws Exception {
- testBinaryOrderingAndIncrement(TrieUtils.VARIANT_8BIT);
- }
-
- public void testBinaryOrderingAndIncrement_4bit() throws Exception {
- testBinaryOrderingAndIncrement(TrieUtils.VARIANT_8BIT);
- }
-
- public void testBinaryOrderingAndIncrement_2bit() throws Exception {
- testBinaryOrderingAndIncrement(TrieUtils.VARIANT_8BIT);
+ public void testIntConversionAndOrdering() throws Exception {
+ // generate a series of encoded ints, each numerical one bigger than the one before
+ String last=null;
+ for (int i=-100000; i<100000; i++) {
+ String act=TrieUtils.intToPrefixCoded(i);
+ if (last!=null) {
+ // test if smaller
+ assertTrue("actual bigger than last", last.compareTo(act) < 0 );
+ }
+ // test is back and forward conversion works
+ assertEquals("forward and back conversion should generate same int", i, TrieUtils.prefixCodedToInt(act));
+ // next step
+ last=act;
+ }
}
- private void testLongs(TrieUtils variant) throws Exception {
+ public void testLongSpecialValues() throws Exception {
long[] vals=new long[]{
- Long.MIN_VALUE, -5000L, -4000L, -3000L, -2000L, -1000L, 0L,
- 1L, 10L, 300L, 5000L, Long.MAX_VALUE-2, Long.MAX_VALUE-1, Long.MAX_VALUE
+ Long.MIN_VALUE, Long.MIN_VALUE+1, Long.MIN_VALUE+2, -5003400000000L,
+ -4000L, -3000L, -2000L, -1000L, -1L, 0L, 1L, 10L, 300L, 50006789999999999L, Long.MAX_VALUE-2, Long.MAX_VALUE-1, Long.MAX_VALUE
};
- String[] trieVals=new String[vals.length];
+ String[] prefixVals=new String[vals.length];
- // check back and forth conversion
for (int i=0; i<vals.length; i++) {
- trieVals[i]=variant.longToTrieCoded(vals[i]);
- assertEquals( "Back and forth conversion should return same value", vals[i], variant.trieCodedToLong(trieVals[i]) );
- assertEquals( "Automatic back conversion with encoding detection should return same value", vals[i], TrieUtils.trieCodedToLongAuto(trieVals[i]) );
+ prefixVals[i]=TrieUtils.longToPrefixCoded(vals[i]);
+
+ // check forward and back conversion
+ assertEquals( "forward and back conversion should generate same long", vals[i], TrieUtils.prefixCodedToLong(prefixVals[i]) );
+
+ // test if decoding values as int fails correctly
+ try {
+ TrieUtils.prefixCodedToInt(prefixVals[i]);
+ fail("decoding a prefix coded long value as int should fail");
+ } catch (NumberFormatException e) {
+ // worked
+ }
}
- // check sort order (trieVals should be ascending)
- for (int i=1; i<vals.length; i++) {
- assertTrue( trieVals[i-1].compareTo( trieVals[i] ) < 0 );
+ // check sort order (prefixVals should be ascending)
+ for (int i=1; i<prefixVals.length; i++) {
+ assertTrue( "check sort order", prefixVals[i-1].compareTo( prefixVals[i] ) < 0 );
+ }
+
+ // check the prefix encoding, lower precision should have the difference to original value equal to the lower removed bits
+ for (int i=0; i<vals.length; i++) {
+ for (int j=0; j<64; j++) {
+ long prefixVal=TrieUtils.prefixCodedToLong(TrieUtils.longToPrefixCoded(vals[i], j));
+ long mask=(1L << j) - 1L;
+ assertEquals( "difference between prefix val and original value for "+vals[i]+" with shift="+j, vals[i] & mask, vals[i]-prefixVal );
+ }
}
}
- public void testLongs_8bit() throws Exception {
- testLongs(TrieUtils.VARIANT_8BIT);
- }
-
- public void testLongs_4bit() throws Exception {
- testLongs(TrieUtils.VARIANT_4BIT);
- }
-
- public void testLongs_2bit() throws Exception {
- testLongs(TrieUtils.VARIANT_2BIT);
+ public void testIntSpecialValues() throws Exception {
+ int[] vals=new int[]{
+ Integer.MIN_VALUE, Integer.MIN_VALUE+1, Integer.MIN_VALUE+2, -64765767,
+ -4000, -3000, -2000, -1000, -1, 0, 1, 10, 300, 765878989, Integer.MAX_VALUE-2, Integer.MAX_VALUE-1, Integer.MAX_VALUE
+ };
+ String[] prefixVals=new String[vals.length];
+
+ for (int i=0; i<vals.length; i++) {
+ prefixVals[i]=TrieUtils.intToPrefixCoded(vals[i]);
+
+ // check forward and back conversion
+ assertEquals( "forward and back conversion should generate same int", vals[i], TrieUtils.prefixCodedToInt(prefixVals[i]) );
+
+ // test if decoding values as long fails correctly
+ try {
+ TrieUtils.prefixCodedToLong(prefixVals[i]);
+ fail("decoding a prefix coded int value as long should fail");
+ } catch (NumberFormatException e) {
+ // worked
+ }
+ }
+
+ // check sort order (prefixVals should be ascending)
+ for (int i=1; i<prefixVals.length; i++) {
+ assertTrue( "check sort order", prefixVals[i-1].compareTo( prefixVals[i] ) < 0 );
+ }
+
+ // check the prefix encoding, lower precision should have the difference to original value equal to the lower removed bits
+ for (int i=0; i<vals.length; i++) {
+ for (int j=0; j<32; j++) {
+ int prefixVal=TrieUtils.prefixCodedToInt(TrieUtils.intToPrefixCoded(vals[i], j));
+ int mask=(1 << j) - 1;
+ assertEquals( "difference between prefix val and original value for "+vals[i]+" with shift="+j, vals[i] & mask, vals[i]-prefixVal );
+ }
+ }
}
- private void testDoubles(TrieUtils variant) throws Exception {
+ public void testDoubles() throws Exception {
double[] vals=new double[]{
Double.NEGATIVE_INFINITY, -2.3E25, -1.0E15, -1.0, -1.0E-1, -1.0E-2, -0.0,
+0.0, 1.0E-2, 1.0E-1, 1.0, 1.0E15, 2.3E25, Double.POSITIVE_INFINITY
};
- String[] trieVals=new String[vals.length];
+ long[] longVals=new long[vals.length];
- // check back and forth conversion
+ // check forward and back conversion
for (int i=0; i<vals.length; i++) {
- trieVals[i]=variant.doubleToTrieCoded(vals[i]);
- assertTrue( "Back and forth conversion should return same value", vals[i]==variant.trieCodedToDouble(trieVals[i]) );
- assertTrue( "Automatic back conversion with encoding detection should return same value", vals[i]==TrieUtils.trieCodedToDoubleAuto(trieVals[i]) );
+ longVals[i]=TrieUtils.doubleToSortableLong(vals[i]);
+ assertTrue( "forward and back conversion should generate same double", Double.compare(vals[i], TrieUtils.sortableLongToDouble(longVals[i]))==0 );
}
- // check sort order (trieVals should be ascending)
- for (int i=1; i<vals.length; i++) {
- assertTrue( trieVals[i-1].compareTo( trieVals[i] ) < 0 );
+ // check sort order (prefixVals should be ascending)
+ for (int i=1; i<longVals.length; i++) {
+ assertTrue( "check sort order", longVals[i-1] < longVals[i] );
}
}
- public void testDoubles_8bit() throws Exception {
- testDoubles(TrieUtils.VARIANT_8BIT);
- }
-
- public void testDoubles_4bit() throws Exception {
- testDoubles(TrieUtils.VARIANT_4BIT);
- }
-
- public void testDoubles_2bit() throws Exception {
- testDoubles(TrieUtils.VARIANT_2BIT);
- }
-
- private void testDates(TrieUtils variant) throws Exception {
- Date[] vals=new Date[]{
- new GregorianCalendar(1000,1,1).getTime(),
- new GregorianCalendar(1999,1,1).getTime(),
- new GregorianCalendar(2000,1,1).getTime(),
- new GregorianCalendar(2001,1,1).getTime()
+ public void testFloats() throws Exception {
+ float[] vals=new float[]{
+ Float.NEGATIVE_INFINITY, -2.3E25f, -1.0E15f, -1.0f, -1.0E-1f, -1.0E-2f, -0.0f,
+ +0.0f, 1.0E-2f, 1.0E-1f, 1.0f, 1.0E15f, 2.3E25f, Float.POSITIVE_INFINITY
};
- String[] trieVals=new String[vals.length];
+ int[] intVals=new int[vals.length];
- // check back and forth conversion
+ // check forward and back conversion
for (int i=0; i<vals.length; i++) {
- trieVals[i]=variant.dateToTrieCoded(vals[i]);
- assertEquals( "Back and forth conversion should return same value", vals[i], variant.trieCodedToDate(trieVals[i]) );
- assertEquals( "Automatic back conversion with encoding detection should return same value", vals[i], TrieUtils.trieCodedToDateAuto(trieVals[i]) );
+ intVals[i]=TrieUtils.floatToSortableInt(vals[i]);
+ assertTrue( "forward and back conversion should generate same double", Float.compare(vals[i], TrieUtils.sortableIntToFloat(intVals[i]))==0 );
}
- // check sort order (trieVals should be ascending)
- for (int i=1; i<vals.length; i++) {
- assertTrue( trieVals[i-1].compareTo( trieVals[i] ) < 0 );
+ // check sort order (prefixVals should be ascending)
+ for (int i=1; i<intVals.length; i++) {
+ assertTrue( "check sort order", intVals[i-1] < intVals[i] );
}
}
-
- public void testDates_8bit() throws Exception {
- testDates(TrieUtils.VARIANT_8BIT);
+
+ // INFO: Tests for trieCodeLong()/trieCodeInt() not needed because implicitely tested by range filter tests
+
+ /** Note: The neededBounds iterator must be unsigned (easier understanding what's happening) */
+ protected void assertLongRangeSplit(final long lower, final long upper, int precisionStep,
+ final boolean useBitSet, final Iterator neededBounds
+ ) throws Exception {
+ final OpenBitSet bits=useBitSet ? new OpenBitSet(upper-lower+1) : null;
+
+ TrieUtils.splitLongRange(new TrieUtils.LongRangeBuilder() {
+ public void addRange(int precisionStep, long min, long max, int shift) {
+ assertTrue("min, max should be inside bounds", min>=lower && min<=upper && max>=lower && max<=upper);
+ if (useBitSet) for (long l=min; l<=max; l++) {
+ assertFalse("ranges should not overlap", bits.getAndSet(l-lower) );
+ }
+ // make unsigned longs for easier display and understanding
+ min ^= 0x8000000000000000L;
+ max ^= 0x8000000000000000L;
+ //System.out.println("new Long(0x"+Long.toHexString(min>>>shift)+"L),new Long(0x"+Long.toHexString(max>>>shift)+"L),");
+ assertEquals( "inner min bound", ((Long)neededBounds.next()).longValue(), min>>>shift);
+ assertEquals( "inner max bound", ((Long)neededBounds.next()).longValue(), max>>>shift);
+ }
+ }, precisionStep, lower, upper);
+
+ if (useBitSet) {
+ // after flipping all bits in the range, the cardinality should be zero
+ bits.flip(0,upper-lower+1);
+ assertTrue("The sub-range concenated should match the whole range", bits.isEmpty());
+ }
}
-
- public void testDates_4bit() throws Exception {
- testDates(TrieUtils.VARIANT_4BIT);
+
+ public void testSplitLongRange() throws Exception {
+ // a hard-coded "standard" range
+ assertLongRangeSplit(-5000L, 9500L, 4, true, Arrays.asList(new Long[]{
+ new Long(0x7fffffffffffec78L),new Long(0x7fffffffffffec7fL),
+ new Long(0x8000000000002510L),new Long(0x800000000000251cL),
+ new Long(0x7fffffffffffec8L), new Long(0x7fffffffffffecfL),
+ new Long(0x800000000000250L), new Long(0x800000000000250L),
+ new Long(0x7fffffffffffedL), new Long(0x7fffffffffffefL),
+ new Long(0x80000000000020L), new Long(0x80000000000024L),
+ new Long(0x7ffffffffffffL), new Long(0x8000000000001L)
+ }).iterator());
+
+ // the same with no range splitting
+ assertLongRangeSplit(-5000L, 9500L, 64, true, Arrays.asList(new Long[]{
+ new Long(0x7fffffffffffec78L),new Long(0x800000000000251cL)
+ }).iterator());
+
+ // this tests optimized range splitting, if one of the inner bounds
+ // is also the bound of the next lower precision, it should be used completely
+ assertLongRangeSplit(0L, 1024L+63L, 4, true, Arrays.asList(new Long[]{
+ new Long(0x800000000000040L), new Long(0x800000000000043L),
+ new Long(0x80000000000000L), new Long(0x80000000000003L)
+ }).iterator());
+
+ // the full long range should only consist of a lowest precision range; no bitset testing here, as too much memory needed :-)
+ assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 8, false, Arrays.asList(new Long[]{
+ new Long(0x00L),new Long(0xffL)
+ }).iterator());
+
+ // the same with precisionStep=4
+ assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 4, false, Arrays.asList(new Long[]{
+ new Long(0x0L),new Long(0xfL)
+ }).iterator());
+
+ // the same with precisionStep=2
+ assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 2, false, Arrays.asList(new Long[]{
+ new Long(0x0L),new Long(0x3L)
+ }).iterator());
+
+ // the same with precisionStep=1
+ assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 1, false, Arrays.asList(new Long[]{
+ new Long(0x0L),new Long(0x1L)
+ }).iterator());
+ }
+
+ /** Note: The neededBounds iterator must be unsigned (easier understanding what's happening) */
+ protected void assertIntRangeSplit(final int lower, final int upper, int precisionStep,
+ final boolean useBitSet, final Iterator neededBounds
+ ) throws Exception {
+ final OpenBitSet bits=useBitSet ? new OpenBitSet(upper-lower+1) : null;
+
+ TrieUtils.splitIntRange(new TrieUtils.IntRangeBuilder() {
+ public void addRange(int precisionStep, int min, int max, int shift) {
+ assertTrue("min, max should be inside bounds", min>=lower && min<=upper && max>=lower && max<=upper);
+ if (useBitSet) for (int i=min; i<=max; i++) {
+ assertFalse("ranges should not overlap", bits.getAndSet(i-lower) );
+ }
+ // make unsigned ints for easier display and understanding
+ min ^= 0x80000000;
+ max ^= 0x80000000;
+ //System.out.println("new Integer(0x"+Integer.toHexString(min>>>shift)+"),new Integer(0x"+Integer.toHexString(max>>>shift)+"),");
+ assertEquals( "inner min bound", ((Integer)neededBounds.next()).intValue(), min>>>shift);
+ assertEquals( "inner max bound", ((Integer)neededBounds.next()).intValue(), max>>>shift);
+ }
+ }, precisionStep, lower, upper);
+
+ if (useBitSet) {
+ // after flipping all bits in the range, the cardinality should be zero
+ bits.flip(0,upper-lower+1);
+ assertTrue("The sub-range concenated should match the whole range", bits.isEmpty());
+ }
}
-
- public void testDates_2bit() throws Exception {
- testDates(TrieUtils.VARIANT_2BIT);
+
+ public void testSplitIntRange() throws Exception {
+ // a hard-coded "standard" range
+ assertIntRangeSplit(-5000, 9500, 4, true, Arrays.asList(new Integer[]{
+ new Integer(0x7fffec78),new Integer(0x7fffec7f),
+ new Integer(0x80002510),new Integer(0x8000251c),
+ new Integer(0x7fffec8), new Integer(0x7fffecf),
+ new Integer(0x8000250), new Integer(0x8000250),
+ new Integer(0x7fffed), new Integer(0x7fffef),
+ new Integer(0x800020), new Integer(0x800024),
+ new Integer(0x7ffff), new Integer(0x80001)
+ }).iterator());
+
+ // the same with no range splitting
+ assertIntRangeSplit(-5000, 9500, 32, true, Arrays.asList(new Integer[]{
+ new Integer(0x7fffec78),new Integer(0x8000251c)
+ }).iterator());
+
+ // this tests optimized range splitting, if one of the inner bounds
+ // is also the bound of the next lower precision, it should be used completely
+ assertIntRangeSplit(0, 1024+63, 4, true, Arrays.asList(new Integer[]{
+ new Integer(0x8000040), new Integer(0x8000043),
+ new Integer(0x800000), new Integer(0x800003)
+ }).iterator());
+
+ // the full int range should only consist of a lowest precision range; no bitset testing here, as too much memory needed :-)
+ assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 8, false, Arrays.asList(new Integer[]{
+ new Integer(0x00),new Integer(0xff)
+ }).iterator());
+
+ // the same with precisionStep=4
+ assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 4, false, Arrays.asList(new Integer[]{
+ new Integer(0x0),new Integer(0xf)
+ }).iterator());
+
+ // the same with precisionStep=2
+ assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 2, false, Arrays.asList(new Integer[]{
+ new Integer(0x0),new Integer(0x3)
+ }).iterator());
+
+ // the same with precisionStep=1
+ assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 1, false, Arrays.asList(new Integer[]{
+ new Integer(0x0),new Integer(0x1)
+ }).iterator());
}
}