lucene/backwards/src/test/org/apache/lucene/util/TestNumericUtils.java - manifoldcf-integration-solr-3.x - Git at Google

 package org.apache.lucene.util;

 /**
 * 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.
 */

 import java.util.Arrays;
 import java.util.Collections;
 import java.util.Iterator;
 import java.util.Random;

 public class TestNumericUtils extends LuceneTestCase {

   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=NumericUtils.longToPrefixCoded(l);
       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 long", l, NumericUtils.prefixCodedToLong(act));
       // next step
       last=act;
     }
   }

   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=NumericUtils.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, NumericUtils.prefixCodedToInt(act));
       // next step
       last=act;
     }
   }

   public void testLongSpecialValues() throws Exception {
     long[] vals=new long[]{
       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[] prefixVals=new String[vals.length];

     for (int i=0; i<vals.length; i++) {
       prefixVals[i]=NumericUtils.longToPrefixCoded(vals[i]);

       // check forward and back conversion
       assertEquals( "forward and back conversion should generate same long", vals[i], NumericUtils.prefixCodedToLong(prefixVals[i]) );

       // test if decoding values as int fails correctly
       try {
         NumericUtils.prefixCodedToInt(prefixVals[i]);
         fail("decoding a prefix coded long value as int 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<64; j++) {
         long prefixVal=NumericUtils.prefixCodedToLong(NumericUtils.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 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]=NumericUtils.intToPrefixCoded(vals[i]);

       // check forward and back conversion
       assertEquals( "forward and back conversion should generate same int", vals[i], NumericUtils.prefixCodedToInt(prefixVals[i]) );

       // test if decoding values as long fails correctly
       try {
         NumericUtils.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=NumericUtils.prefixCodedToInt(NumericUtils.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 );
       }
     }
   }

   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
     };
     long[] longVals=new long[vals.length];

     // check forward and back conversion
     for (int i=0; i<vals.length; i++) {
       longVals[i]=NumericUtils.doubleToSortableLong(vals[i]);
       assertTrue( "forward and back conversion should generate same double", Double.compare(vals[i], NumericUtils.sortableLongToDouble(longVals[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 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
     };
     int[] intVals=new int[vals.length];

     // check forward and back conversion
     for (int i=0; i<vals.length; i++) {
       intVals[i]=NumericUtils.floatToSortableInt(vals[i]);
       assertTrue( "forward and back conversion should generate same double", Float.compare(vals[i], NumericUtils.sortableIntToFloat(intVals[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] );
     }
   }

   // INFO: Tests for trieCodeLong()/trieCodeInt() not needed because implicitely tested by range filter tests

   /** Note: The neededBounds Iterable must be unsigned (easier understanding what's happening) */
   private void assertLongRangeSplit(final long lower, final long upper, int precisionStep,
     final boolean useBitSet, final Iterable<Long> expectedBounds, final Iterable<Integer> expectedShifts
   ) throws Exception {
     // Cannot use FixedBitSet since the range could be long:
     final OpenBitSet bits=useBitSet ? new OpenBitSet(upper-lower+1) : null;
     final Iterator<Long> neededBounds = (expectedBounds == null) ? null : expectedBounds.iterator();
     final Iterator<Integer> neededShifts = (expectedShifts == null) ? null : expectedShifts.iterator();

     NumericUtils.splitLongRange(new NumericUtils.LongRangeBuilder() {
       @Override
       public void addRange(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) );
           // extra exit condition to prevent overflow on MAX_VALUE
           if (l == max) break;
         }
         if (neededBounds == null || neededShifts == null)
           return;
         // make unsigned longs for easier display and understanding
         min ^= 0x8000000000000000L;
         max ^= 0x8000000000000000L;
         //System.out.println("0x"+Long.toHexString(min>>>shift)+"L,0x"+Long.toHexString(max>>>shift)+"L)/*shift="+shift+"*/,");
         assertEquals( "shift", neededShifts.next().intValue(), shift);
         assertEquals( "inner min bound", neededBounds.next().longValue(), min>>>shift);
         assertEquals( "inner max bound", 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);
       assertEquals("The sub-range concenated should match the whole range", 0, bits.cardinality());
     }
   }

   /** LUCENE-2541: NumericRangeQuery errors with endpoints near long min and max values */
   public void testLongExtremeValues() throws Exception {
     // upper end extremes
     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 1, true, Arrays.asList(
       0xffffffffffffffffL,0xffffffffffffffffL
     ), Arrays.asList(
       0
     ));
     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 2, true, Arrays.asList(
       0xffffffffffffffffL,0xffffffffffffffffL
     ), Arrays.asList(
       0
     ));
     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 4, true, Arrays.asList(
       0xffffffffffffffffL,0xffffffffffffffffL
     ), Arrays.asList(
       0
     ));
     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 6, true, Arrays.asList(
       0xffffffffffffffffL,0xffffffffffffffffL
     ), Arrays.asList(
       0
     ));
     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 8, true, Arrays.asList(
       0xffffffffffffffffL,0xffffffffffffffffL
     ), Arrays.asList(
       0
     ));
     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 64, true, Arrays.asList(
       0xffffffffffffffffL,0xffffffffffffffffL
     ), Arrays.asList(
       0
     ));

     assertLongRangeSplit(Long.MAX_VALUE-0xfL, Long.MAX_VALUE, 4, true, Arrays.asList(
       0xfffffffffffffffL,0xfffffffffffffffL
     ), Arrays.asList(
       4
     ));
     assertLongRangeSplit(Long.MAX_VALUE-0x10L, Long.MAX_VALUE, 4, true, Arrays.asList(
       0xffffffffffffffefL,0xffffffffffffffefL,
       0xfffffffffffffffL,0xfffffffffffffffL
     ), Arrays.asList(
       0, 4
     ));

     // lower end extremes
     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 1, true, Arrays.asList(
       0x0000000000000000L,0x0000000000000000L
     ), Arrays.asList(
       0
     ));
     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 2, true, Arrays.asList(
       0x0000000000000000L,0x0000000000000000L
     ), Arrays.asList(
       0
     ));
     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 4, true, Arrays.asList(
       0x0000000000000000L,0x0000000000000000L
     ), Arrays.asList(
       0
     ));
     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 6, true, Arrays.asList(
       0x0000000000000000L,0x0000000000000000L
     ), Arrays.asList(
       0
     ));
     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 8, true, Arrays.asList(
       0x0000000000000000L,0x0000000000000000L
     ), Arrays.asList(
       0
     ));
     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 64, true, Arrays.asList(
       0x0000000000000000L,0x0000000000000000L
     ), Arrays.asList(
       0
     ));

     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE+0xfL, 4, true, Arrays.asList(
       0x000000000000000L,0x000000000000000L
     ), Arrays.asList(
       4
     ));
     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE+0x10L, 4, true, Arrays.asList(
       0x0000000000000010L,0x0000000000000010L,
       0x000000000000000L,0x000000000000000L
     ), Arrays.asList(
       0, 4
     ));
   }

   public void testRandomSplit() throws Exception {
     long num = (long) atLeast(10);
     for (long i=0; i < num; i++) {
       executeOneRandomSplit(random);
     }
   }

   private void executeOneRandomSplit(final Random random) throws Exception {
     long lower = randomLong(random);
     long len = random.nextInt(16384*1024); // not too large bitsets, else OOME!
     while (lower + len < lower) { // overflow
       lower >>= 1;
     }
     assertLongRangeSplit(lower, lower + len, random.nextInt(64) + 1, true, null, null);
   }

   private long randomLong(final Random random) {
     long val;
     switch(random.nextInt(4)) {
       case 0:
         val = 1L << (random.nextInt(63)); //  patterns like 0x000000100000 (-1 yields patterns like 0x0000fff)
         break;
       case 1:
         val = -1L << (random.nextInt(63)); // patterns like 0xfffff00000
         break;
       default:
         val = random.nextLong();
     }

     val += random.nextInt(5)-2;

     if (random.nextBoolean()) {
       if (random.nextBoolean()) val += random.nextInt(100)-50;
       if (random.nextBoolean()) val = ~val;
       if (random.nextBoolean()) val = val<<1;
       if (random.nextBoolean()) val = val>>>1;
     }

     return val;
   }

   public void testSplitLongRange() throws Exception {
     // a hard-coded "standard" range
     assertLongRangeSplit(-5000L, 9500L, 4, true, Arrays.asList(
       0x7fffffffffffec78L,0x7fffffffffffec7fL,
       0x8000000000002510L,0x800000000000251cL,
       0x7fffffffffffec8L, 0x7fffffffffffecfL,
       0x800000000000250L, 0x800000000000250L,
       0x7fffffffffffedL,  0x7fffffffffffefL,
       0x80000000000020L,  0x80000000000024L,
       0x7ffffffffffffL,   0x8000000000001L
     ), Arrays.asList(
       0, 0,
       4, 4,
       8, 8,
       12
     ));

     // the same with no range splitting
     assertLongRangeSplit(-5000L, 9500L, 64, true, Arrays.asList(
       0x7fffffffffffec78L,0x800000000000251cL
     ), Arrays.asList(
       0
     ));

     // 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(
       0x800000000000040L, 0x800000000000043L,
       0x80000000000000L,  0x80000000000003L
     ), Arrays.asList(
       4, 8
     ));

     // 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(
       0x00L,0xffL
     ), Arrays.asList(
       56
     ));

     // the same with precisionStep=4
     assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 4, false, Arrays.asList(
       0x0L,0xfL
     ), Arrays.asList(
       60
     ));

     // the same with precisionStep=2
     assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 2, false, Arrays.asList(
       0x0L,0x3L
     ), Arrays.asList(
       62
     ));

     // the same with precisionStep=1
     assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 1, false, Arrays.asList(
       0x0L,0x1L
     ), Arrays.asList(
       63
     ));

     // a inverse range should produce no sub-ranges
     assertLongRangeSplit(9500L, -5000L, 4, false, Collections.<Long>emptyList(), Collections.<Integer>emptyList());

     // a 0-length range should reproduce the range itsself
     assertLongRangeSplit(9500L, 9500L, 4, false, Arrays.asList(
       0x800000000000251cL,0x800000000000251cL
     ), Arrays.asList(
       0
     ));
   }

   /** Note: The neededBounds Iterable must be unsigned (easier understanding what's happening) */
   private void assertIntRangeSplit(final int lower, final int upper, int precisionStep,
     final boolean useBitSet, final Iterable<Integer> expectedBounds, final Iterable<Integer> expectedShifts
   ) throws Exception {
     final FixedBitSet bits=useBitSet ? new FixedBitSet(upper-lower+1) : null;
     final Iterator<Integer> neededBounds = (expectedBounds == null) ? null : expectedBounds.iterator();
     final Iterator<Integer> neededShifts = (expectedShifts == null) ? null : expectedShifts.iterator();

     NumericUtils.splitIntRange(new NumericUtils.IntRangeBuilder() {
       @Override
       public void addRange(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) );
           // extra exit condition to prevent overflow on MAX_VALUE
           if (i == max) break;
         }
         if (neededBounds == null)
           return;
         // make unsigned ints for easier display and understanding
         min ^= 0x80000000;
         max ^= 0x80000000;
         //System.out.println("0x"+Integer.toHexString(min>>>shift)+",0x"+Integer.toHexString(max>>>shift)+")/*shift="+shift+"*/,");
         assertEquals( "shift", neededShifts.next().intValue(), shift);
         assertEquals( "inner min bound", neededBounds.next().intValue(), min>>>shift);
         assertEquals( "inner max bound", 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);
       assertEquals("The sub-range concenated should match the whole range", 0, bits.cardinality());
     }
   }

   public void testSplitIntRange() throws Exception {
     // a hard-coded "standard" range
     assertIntRangeSplit(-5000, 9500, 4, true, Arrays.asList(
       0x7fffec78,0x7fffec7f,
       0x80002510,0x8000251c,
       0x7fffec8, 0x7fffecf,
       0x8000250, 0x8000250,
       0x7fffed,  0x7fffef,
       0x800020,  0x800024,
       0x7ffff,   0x80001
     ), Arrays.asList(
       0, 0,
       4, 4,
       8, 8,
       12
     ));

     // the same with no range splitting
     assertIntRangeSplit(-5000, 9500, 32, true, Arrays.asList(
       0x7fffec78,0x8000251c
     ), Arrays.asList(
       0
     ));

     // 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(
       0x8000040, 0x8000043,
       0x800000,  0x800003
     ), Arrays.asList(
       4, 8
     ));

     // 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(
       0x00,0xff
     ), Arrays.asList(
       24
     ));

     // the same with precisionStep=4
     assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 4, false, Arrays.asList(
       0x0,0xf
     ), Arrays.asList(
       28
     ));

     // the same with precisionStep=2
     assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 2, false, Arrays.asList(
       0x0,0x3
     ), Arrays.asList(
       30
     ));

     // the same with precisionStep=1
     assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 1, false, Arrays.asList(
       0x0,0x1
     ), Arrays.asList(
       31
     ));

     // a inverse range should produce no sub-ranges
     assertIntRangeSplit(9500, -5000, 4, false, Collections.<Integer>emptyList(), Collections.<Integer>emptyList());

     // a 0-length range should reproduce the range itsself
     assertIntRangeSplit(9500, 9500, 4, false, Arrays.asList(
       0x8000251c,0x8000251c
     ), Arrays.asList(
       0
     ));
   }

 }
	package org.apache.lucene.util;

	/**
	* 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.
	*/

	import java.util.Arrays;
	import java.util.Collections;
	import java.util.Iterator;
	import java.util.Random;

	public class TestNumericUtils extends LuceneTestCase {

	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=NumericUtils.longToPrefixCoded(l);
	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 long", l, NumericUtils.prefixCodedToLong(act));
	// next step
	last=act;
	}
	}

	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=NumericUtils.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, NumericUtils.prefixCodedToInt(act));
	// next step
	last=act;
	}
	}

	public void testLongSpecialValues() throws Exception {
	long[] vals=new long[]{
	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[] prefixVals=new String[vals.length];

	for (int i=0; i<vals.length; i++) {
	prefixVals[i]=NumericUtils.longToPrefixCoded(vals[i]);

	// check forward and back conversion
	assertEquals( "forward and back conversion should generate same long", vals[i], NumericUtils.prefixCodedToLong(prefixVals[i]) );

	// test if decoding values as int fails correctly
	try {
	NumericUtils.prefixCodedToInt(prefixVals[i]);
	fail("decoding a prefix coded long value as int 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<64; j++) {
	long prefixVal=NumericUtils.prefixCodedToLong(NumericUtils.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 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]=NumericUtils.intToPrefixCoded(vals[i]);

	// check forward and back conversion
	assertEquals( "forward and back conversion should generate same int", vals[i], NumericUtils.prefixCodedToInt(prefixVals[i]) );

	// test if decoding values as long fails correctly
	try {
	NumericUtils.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=NumericUtils.prefixCodedToInt(NumericUtils.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 );
	}
	}
	}

	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
	};
	long[] longVals=new long[vals.length];

	// check forward and back conversion
	for (int i=0; i<vals.length; i++) {
	longVals[i]=NumericUtils.doubleToSortableLong(vals[i]);
	assertTrue( "forward and back conversion should generate same double", Double.compare(vals[i], NumericUtils.sortableLongToDouble(longVals[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 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
	};
	int[] intVals=new int[vals.length];

	// check forward and back conversion
	for (int i=0; i<vals.length; i++) {
	intVals[i]=NumericUtils.floatToSortableInt(vals[i]);
	assertTrue( "forward and back conversion should generate same double", Float.compare(vals[i], NumericUtils.sortableIntToFloat(intVals[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] );
	}
	}

	// INFO: Tests for trieCodeLong()/trieCodeInt() not needed because implicitely tested by range filter tests

	/** Note: The neededBounds Iterable must be unsigned (easier understanding what's happening) */
	private void assertLongRangeSplit(final long lower, final long upper, int precisionStep,
	final boolean useBitSet, final Iterable<Long> expectedBounds, final Iterable<Integer> expectedShifts
	) throws Exception {
	// Cannot use FixedBitSet since the range could be long:
	final OpenBitSet bits=useBitSet ? new OpenBitSet(upper-lower+1) : null;
	final Iterator<Long> neededBounds = (expectedBounds == null) ? null : expectedBounds.iterator();
	final Iterator<Integer> neededShifts = (expectedShifts == null) ? null : expectedShifts.iterator();

	NumericUtils.splitLongRange(new NumericUtils.LongRangeBuilder() {
	@Override
	public void addRange(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) );
	// extra exit condition to prevent overflow on MAX_VALUE
	if (l == max) break;
	}
	if (neededBounds == null \|\| neededShifts == null)
	return;
	// make unsigned longs for easier display and understanding
	min ^= 0x8000000000000000L;
	max ^= 0x8000000000000000L;
	//System.out.println("0x"+Long.toHexString(min>>>shift)+"L,0x"+Long.toHexString(max>>>shift)+"L)/shift="+shift+"/,");
	assertEquals( "shift", neededShifts.next().intValue(), shift);
	assertEquals( "inner min bound", neededBounds.next().longValue(), min>>>shift);
	assertEquals( "inner max bound", 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);
	assertEquals("The sub-range concenated should match the whole range", 0, bits.cardinality());
	}
	}

	/** LUCENE-2541: NumericRangeQuery errors with endpoints near long min and max values */
	public void testLongExtremeValues() throws Exception {
	// upper end extremes
	assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 1, true, Arrays.asList(
	0xffffffffffffffffL,0xffffffffffffffffL
	), Arrays.asList(
	0
	));
	assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 2, true, Arrays.asList(
	0xffffffffffffffffL,0xffffffffffffffffL
	), Arrays.asList(
	0
	));
	assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 4, true, Arrays.asList(
	0xffffffffffffffffL,0xffffffffffffffffL
	), Arrays.asList(
	0
	));
	assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 6, true, Arrays.asList(
	0xffffffffffffffffL,0xffffffffffffffffL
	), Arrays.asList(
	0
	));
	assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 8, true, Arrays.asList(
	0xffffffffffffffffL,0xffffffffffffffffL
	), Arrays.asList(
	0
	));
	assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 64, true, Arrays.asList(
	0xffffffffffffffffL,0xffffffffffffffffL
	), Arrays.asList(
	0
	));

	assertLongRangeSplit(Long.MAX_VALUE-0xfL, Long.MAX_VALUE, 4, true, Arrays.asList(
	0xfffffffffffffffL,0xfffffffffffffffL
	), Arrays.asList(
	4
	));
	assertLongRangeSplit(Long.MAX_VALUE-0x10L, Long.MAX_VALUE, 4, true, Arrays.asList(
	0xffffffffffffffefL,0xffffffffffffffefL,
	0xfffffffffffffffL,0xfffffffffffffffL
	), Arrays.asList(
	0, 4
	));

	// lower end extremes
	assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 1, true, Arrays.asList(
	0x0000000000000000L,0x0000000000000000L
	), Arrays.asList(
	0
	));
	assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 2, true, Arrays.asList(
	0x0000000000000000L,0x0000000000000000L
	), Arrays.asList(
	0
	));
	assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 4, true, Arrays.asList(
	0x0000000000000000L,0x0000000000000000L
	), Arrays.asList(
	0
	));
	assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 6, true, Arrays.asList(
	0x0000000000000000L,0x0000000000000000L
	), Arrays.asList(
	0
	));
	assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 8, true, Arrays.asList(
	0x0000000000000000L,0x0000000000000000L
	), Arrays.asList(
	0
	));
	assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 64, true, Arrays.asList(
	0x0000000000000000L,0x0000000000000000L
	), Arrays.asList(
	0
	));

	assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE+0xfL, 4, true, Arrays.asList(
	0x000000000000000L,0x000000000000000L
	), Arrays.asList(
	4
	));
	assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE+0x10L, 4, true, Arrays.asList(
	0x0000000000000010L,0x0000000000000010L,
	0x000000000000000L,0x000000000000000L
	), Arrays.asList(
	0, 4
	));
	}

	public void testRandomSplit() throws Exception {
	long num = (long) atLeast(10);
	for (long i=0; i < num; i++) {
	executeOneRandomSplit(random);
	}
	}

	private void executeOneRandomSplit(final Random random) throws Exception {
	long lower = randomLong(random);
	long len = random.nextInt(16384*1024); // not too large bitsets, else OOME!
	while (lower + len < lower) { // overflow
	lower >>= 1;
	}
	assertLongRangeSplit(lower, lower + len, random.nextInt(64) + 1, true, null, null);
	}

	private long randomLong(final Random random) {
	long val;
	switch(random.nextInt(4)) {
	case 0:
	val = 1L << (random.nextInt(63)); // patterns like 0x000000100000 (-1 yields patterns like 0x0000fff)
	break;
	case 1:
	val = -1L << (random.nextInt(63)); // patterns like 0xfffff00000
	break;
	default:
	val = random.nextLong();
	}

	val += random.nextInt(5)-2;

	if (random.nextBoolean()) {
	if (random.nextBoolean()) val += random.nextInt(100)-50;
	if (random.nextBoolean()) val = ~val;
	if (random.nextBoolean()) val = val<<1;
	if (random.nextBoolean()) val = val>>>1;
	}

	return val;
	}

	public void testSplitLongRange() throws Exception {
	// a hard-coded "standard" range
	assertLongRangeSplit(-5000L, 9500L, 4, true, Arrays.asList(
	0x7fffffffffffec78L,0x7fffffffffffec7fL,
	0x8000000000002510L,0x800000000000251cL,
	0x7fffffffffffec8L, 0x7fffffffffffecfL,
	0x800000000000250L, 0x800000000000250L,
	0x7fffffffffffedL, 0x7fffffffffffefL,
	0x80000000000020L, 0x80000000000024L,
	0x7ffffffffffffL, 0x8000000000001L
	), Arrays.asList(
	0, 0,
	4, 4,
	8, 8,
	12
	));

	// the same with no range splitting
	assertLongRangeSplit(-5000L, 9500L, 64, true, Arrays.asList(
	0x7fffffffffffec78L,0x800000000000251cL
	), Arrays.asList(
	0
	));

	// 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(
	0x800000000000040L, 0x800000000000043L,
	0x80000000000000L, 0x80000000000003L
	), Arrays.asList(
	4, 8
	));

	// 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(
	0x00L,0xffL
	), Arrays.asList(
	56
	));

	// the same with precisionStep=4
	assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 4, false, Arrays.asList(
	0x0L,0xfL
	), Arrays.asList(
	60
	));

	// the same with precisionStep=2
	assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 2, false, Arrays.asList(
	0x0L,0x3L
	), Arrays.asList(
	62
	));

	// the same with precisionStep=1
	assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 1, false, Arrays.asList(
	0x0L,0x1L
	), Arrays.asList(
	63
	));

	// a inverse range should produce no sub-ranges
	assertLongRangeSplit(9500L, -5000L, 4, false, Collections.<Long>emptyList(), Collections.<Integer>emptyList());

	// a 0-length range should reproduce the range itsself
	assertLongRangeSplit(9500L, 9500L, 4, false, Arrays.asList(
	0x800000000000251cL,0x800000000000251cL
	), Arrays.asList(
	0
	));
	}

	/** Note: The neededBounds Iterable must be unsigned (easier understanding what's happening) */
	private void assertIntRangeSplit(final int lower, final int upper, int precisionStep,
	final boolean useBitSet, final Iterable<Integer> expectedBounds, final Iterable<Integer> expectedShifts
	) throws Exception {
	final FixedBitSet bits=useBitSet ? new FixedBitSet(upper-lower+1) : null;
	final Iterator<Integer> neededBounds = (expectedBounds == null) ? null : expectedBounds.iterator();
	final Iterator<Integer> neededShifts = (expectedShifts == null) ? null : expectedShifts.iterator();

	NumericUtils.splitIntRange(new NumericUtils.IntRangeBuilder() {
	@Override
	public void addRange(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) );
	// extra exit condition to prevent overflow on MAX_VALUE
	if (i == max) break;
	}
	if (neededBounds == null)
	return;
	// make unsigned ints for easier display and understanding
	min ^= 0x80000000;
	max ^= 0x80000000;
	//System.out.println("0x"+Integer.toHexString(min>>>shift)+",0x"+Integer.toHexString(max>>>shift)+")/shift="+shift+"/,");
	assertEquals( "shift", neededShifts.next().intValue(), shift);
	assertEquals( "inner min bound", neededBounds.next().intValue(), min>>>shift);
	assertEquals( "inner max bound", 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);
	assertEquals("The sub-range concenated should match the whole range", 0, bits.cardinality());
	}
	}

	public void testSplitIntRange() throws Exception {
	// a hard-coded "standard" range
	assertIntRangeSplit(-5000, 9500, 4, true, Arrays.asList(
	0x7fffec78,0x7fffec7f,
	0x80002510,0x8000251c,
	0x7fffec8, 0x7fffecf,
	0x8000250, 0x8000250,
	0x7fffed, 0x7fffef,
	0x800020, 0x800024,
	0x7ffff, 0x80001
	), Arrays.asList(
	0, 0,
	4, 4,
	8, 8,
	12
	));

	// the same with no range splitting
	assertIntRangeSplit(-5000, 9500, 32, true, Arrays.asList(
	0x7fffec78,0x8000251c
	), Arrays.asList(
	0
	));

	// 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(
	0x8000040, 0x8000043,
	0x800000, 0x800003
	), Arrays.asList(
	4, 8
	));

	// 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(
	0x00,0xff
	), Arrays.asList(
	24
	));

	// the same with precisionStep=4
	assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 4, false, Arrays.asList(
	0x0,0xf
	), Arrays.asList(
	28
	));

	// the same with precisionStep=2
	assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 2, false, Arrays.asList(
	0x0,0x3
	), Arrays.asList(
	30
	));

	// the same with precisionStep=1
	assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 1, false, Arrays.asList(
	0x0,0x1
	), Arrays.asList(
	31
	));

	// a inverse range should produce no sub-ranges
	assertIntRangeSplit(9500, -5000, 4, false, Collections.<Integer>emptyList(), Collections.<Integer>emptyList());

	// a 0-length range should reproduce the range itsself
	assertIntRangeSplit(9500, 9500, 4, false, Arrays.asList(
	0x8000251c,0x8000251c
	), Arrays.asList(
	0
	));
	}

	}