lucene-java-3.4.0/lucene/backwards/src/test/org/apache/lucene/util/TestNumericUtils.java

   1 package org.apache.lucene.util;
   2
   3 /**
   4 * Licensed to the Apache Software Foundation (ASF) under one or more
   5 * contributor license agreements.  See the NOTICE file distributed with
   6 * this work for additional information regarding copyright ownership.
   7 * The ASF licenses this file to You under the Apache License, Version 2.0
   8 * (the "License"); you may not use this file except in compliance with
   9 * the License.  You may obtain a copy of the License at
  10 *
  11 *     http://www.apache.org/licenses/LICENSE-2.0
  12 *
  13 * Unless required by applicable law or agreed to in writing, software
  14 * distributed under the License is distributed on an "AS IS" BASIS,
  15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16 * See the License for the specific language governing permissions and
  17 * limitations under the License.
  18 */
  19
  20 import java.util.Arrays;
  21 import java.util.Collections;
  22 import java.util.Iterator;
  23 import java.util.Random;
  24
  25 public class TestNumericUtils extends LuceneTestCase {
  26
  27   public void testLongConversionAndOrdering() throws Exception {
  28     // generate a series of encoded longs, each numerical one bigger than the one before
  29     String last=null;
  30     for (long l=-100000L; l<100000L; l++) {
  31       String act=NumericUtils.longToPrefixCoded(l);
  32       if (last!=null) {
  33         // test if smaller
  34         assertTrue("actual bigger than last", last.compareTo(act) < 0 );
  35       }
  36       // test is back and forward conversion works
  37       assertEquals("forward and back conversion should generate same long", l, NumericUtils.prefixCodedToLong(act));
  38       // next step
  39       last=act;
  40     }
  41   }
  42
  43   public void testIntConversionAndOrdering() throws Exception {
  44     // generate a series of encoded ints, each numerical one bigger than the one before
  45     String last=null;
  46     for (int i=-100000; i<100000; i++) {
  47       String act=NumericUtils.intToPrefixCoded(i);
  48       if (last!=null) {
  49         // test if smaller
  50         assertTrue("actual bigger than last", last.compareTo(act) < 0 );
  51       }
  52       // test is back and forward conversion works
  53       assertEquals("forward and back conversion should generate same int", i, NumericUtils.prefixCodedToInt(act));
  54       // next step
  55       last=act;
  56     }
  57   }
  58
  59   public void testLongSpecialValues() throws Exception {
  60     long[] vals=new long[]{
  61       Long.MIN_VALUE, Long.MIN_VALUE+1, Long.MIN_VALUE+2, -5003400000000L,
  62       -4000L, -3000L, -2000L, -1000L, -1L, 0L, 1L, 10L, 300L, 50006789999999999L, Long.MAX_VALUE-2, Long.MAX_VALUE-1, Long.MAX_VALUE
  63     };
  64     String[] prefixVals=new String[vals.length];
  65
  66     for (int i=0; i<vals.length; i++) {
  67       prefixVals[i]=NumericUtils.longToPrefixCoded(vals[i]);
  68
  69       // check forward and back conversion
  70       assertEquals( "forward and back conversion should generate same long", vals[i], NumericUtils.prefixCodedToLong(prefixVals[i]) );
  71
  72       // test if decoding values as int fails correctly
  73       try {
  74         NumericUtils.prefixCodedToInt(prefixVals[i]);
  75         fail("decoding a prefix coded long value as int should fail");
  76       } catch (NumberFormatException e) {
  77         // worked
  78       }
  79     }
  80
  81     // check sort order (prefixVals should be ascending)
  82     for (int i=1; i<prefixVals.length; i++) {
  83       assertTrue( "check sort order", prefixVals[i-1].compareTo( prefixVals[i] ) < 0 );
  84     }
  85
  86     // check the prefix encoding, lower precision should have the difference to original value equal to the lower removed bits
  87     for (int i=0; i<vals.length; i++) {
  88       for (int j=0; j<64; j++) {
  89         long prefixVal=NumericUtils.prefixCodedToLong(NumericUtils.longToPrefixCoded(vals[i], j));
  90         long mask=(1L << j) - 1L;
  91         assertEquals( "difference between prefix val and original value for "+vals[i]+" with shift="+j, vals[i] & mask, vals[i]-prefixVal );
  92       }
  93     }
  94   }
  95
  96   public void testIntSpecialValues() throws Exception {
  97     int[] vals=new int[]{
  98       Integer.MIN_VALUE, Integer.MIN_VALUE+1, Integer.MIN_VALUE+2, -64765767,
  99       -4000, -3000, -2000, -1000, -1, 0, 1, 10, 300, 765878989, Integer.MAX_VALUE-2, Integer.MAX_VALUE-1, Integer.MAX_VALUE
 100     };
 101     String[] prefixVals=new String[vals.length];
 102
 103     for (int i=0; i<vals.length; i++) {
 104       prefixVals[i]=NumericUtils.intToPrefixCoded(vals[i]);
 105
 106       // check forward and back conversion
 107       assertEquals( "forward and back conversion should generate same int", vals[i], NumericUtils.prefixCodedToInt(prefixVals[i]) );
 108
 109       // test if decoding values as long fails correctly
 110       try {
 111         NumericUtils.prefixCodedToLong(prefixVals[i]);
 112         fail("decoding a prefix coded int value as long should fail");
 113       } catch (NumberFormatException e) {
 114         // worked
 115       }
 116     }
 117
 118     // check sort order (prefixVals should be ascending)
 119     for (int i=1; i<prefixVals.length; i++) {
 120       assertTrue( "check sort order", prefixVals[i-1].compareTo( prefixVals[i] ) < 0 );
 121     }
 122
 123     // check the prefix encoding, lower precision should have the difference to original value equal to the lower removed bits
 124     for (int i=0; i<vals.length; i++) {
 125       for (int j=0; j<32; j++) {
 126         int prefixVal=NumericUtils.prefixCodedToInt(NumericUtils.intToPrefixCoded(vals[i], j));
 127         int mask=(1 << j) - 1;
 128         assertEquals( "difference between prefix val and original value for "+vals[i]+" with shift="+j, vals[i] & mask, vals[i]-prefixVal );
 129       }
 130     }
 131   }
 132
 133   public void testDoubles() throws Exception {
 134     double[] vals=new double[]{
 135       Double.NEGATIVE_INFINITY, -2.3E25, -1.0E15, -1.0, -1.0E-1, -1.0E-2, -0.0,
 136       +0.0, 1.0E-2, 1.0E-1, 1.0, 1.0E15, 2.3E25, Double.POSITIVE_INFINITY
 137     };
 138     long[] longVals=new long[vals.length];
 139
 140     // check forward and back conversion
 141     for (int i=0; i<vals.length; i++) {
 142       longVals[i]=NumericUtils.doubleToSortableLong(vals[i]);
 143       assertTrue( "forward and back conversion should generate same double", Double.compare(vals[i], NumericUtils.sortableLongToDouble(longVals[i]))==0 );
 144     }
 145
 146     // check sort order (prefixVals should be ascending)
 147     for (int i=1; i<longVals.length; i++) {
 148       assertTrue( "check sort order", longVals[i-1] < longVals[i] );
 149     }
 150   }
 151
 152   public void testFloats() throws Exception {
 153     float[] vals=new float[]{
 154       Float.NEGATIVE_INFINITY, -2.3E25f, -1.0E15f, -1.0f, -1.0E-1f, -1.0E-2f, -0.0f,
 155       +0.0f, 1.0E-2f, 1.0E-1f, 1.0f, 1.0E15f, 2.3E25f, Float.POSITIVE_INFINITY
 156     };
 157     int[] intVals=new int[vals.length];
 158
 159     // check forward and back conversion
 160     for (int i=0; i<vals.length; i++) {
 161       intVals[i]=NumericUtils.floatToSortableInt(vals[i]);
 162       assertTrue( "forward and back conversion should generate same double", Float.compare(vals[i], NumericUtils.sortableIntToFloat(intVals[i]))==0 );
 163     }
 164
 165     // check sort order (prefixVals should be ascending)
 166     for (int i=1; i<intVals.length; i++) {
 167       assertTrue( "check sort order", intVals[i-1] < intVals[i] );
 168     }
 169   }
 170
 171   // INFO: Tests for trieCodeLong()/trieCodeInt() not needed because implicitely tested by range filter tests
 172
 173   /** Note: The neededBounds Iterable must be unsigned (easier understanding what's happening) */
 174   private void assertLongRangeSplit(final long lower, final long upper, int precisionStep,
 175     final boolean useBitSet, final Iterable<Long> expectedBounds, final Iterable<Integer> expectedShifts
 176   ) throws Exception {
 177     final OpenBitSet bits=useBitSet ? new OpenBitSet(upper-lower+1) : null;
 178     final Iterator<Long> neededBounds = (expectedBounds == null) ? null : expectedBounds.iterator();
 179     final Iterator<Integer> neededShifts = (expectedShifts == null) ? null : expectedShifts.iterator();
 180
 181     NumericUtils.splitLongRange(new NumericUtils.LongRangeBuilder() {
 182       @Override
 183       public void addRange(long min, long max, int shift) {
 184         assertTrue("min, max should be inside bounds", min>=lower && min<=upper && max>=lower && max<=upper);
 185         if (useBitSet) for (long l=min; l<=max; l++) {
 186           assertFalse("ranges should not overlap", bits.getAndSet(l-lower) );
 187           // extra exit condition to prevent overflow on MAX_VALUE
 188           if (l == max) break;
 189         }
 190         if (neededBounds == null || neededShifts == null)
 191           return;
 192         // make unsigned longs for easier display and understanding
 193         min ^= 0x8000000000000000L;
 194         max ^= 0x8000000000000000L;
 195         //System.out.println("0x"+Long.toHexString(min>>>shift)+"L,0x"+Long.toHexString(max>>>shift)+"L)/*shift="+shift+"*/,");
 196         assertEquals( "shift", neededShifts.next().intValue(), shift);
 197         assertEquals( "inner min bound", neededBounds.next().longValue(), min>>>shift);
 198         assertEquals( "inner max bound", neededBounds.next().longValue(), max>>>shift);
 199       }
 200     }, precisionStep, lower, upper);
 201
 202     if (useBitSet) {
 203       // after flipping all bits in the range, the cardinality should be zero
 204       bits.flip(0,upper-lower+1);
 205       assertTrue("The sub-range concenated should match the whole range", bits.isEmpty());
 206     }
 207   }
 208
 209   /** LUCENE-2541: NumericRangeQuery errors with endpoints near long min and max values */
 210   public void testLongExtremeValues() throws Exception {
 211     // upper end extremes
 212     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 1, true, Arrays.asList(
 213       0xffffffffffffffffL,0xffffffffffffffffL
 214     ), Arrays.asList(
 215       0
 216     ));
 217     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 2, true, Arrays.asList(
 218       0xffffffffffffffffL,0xffffffffffffffffL
 219     ), Arrays.asList(
 220       0
 221     ));
 222     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 4, true, Arrays.asList(
 223       0xffffffffffffffffL,0xffffffffffffffffL
 224     ), Arrays.asList(
 225       0
 226     ));
 227     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 6, true, Arrays.asList(
 228       0xffffffffffffffffL,0xffffffffffffffffL
 229     ), Arrays.asList(
 230       0
 231     ));
 232     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 8, true, Arrays.asList(
 233       0xffffffffffffffffL,0xffffffffffffffffL
 234     ), Arrays.asList(
 235       0
 236     ));
 237     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 64, true, Arrays.asList(
 238       0xffffffffffffffffL,0xffffffffffffffffL
 239     ), Arrays.asList(
 240       0
 241     ));
 242
 243     assertLongRangeSplit(Long.MAX_VALUE-0xfL, Long.MAX_VALUE, 4, true, Arrays.asList(
 244       0xfffffffffffffffL,0xfffffffffffffffL
 245     ), Arrays.asList(
 246       4
 247     ));
 248     assertLongRangeSplit(Long.MAX_VALUE-0x10L, Long.MAX_VALUE, 4, true, Arrays.asList(
 249       0xffffffffffffffefL,0xffffffffffffffefL,
 250       0xfffffffffffffffL,0xfffffffffffffffL
 251     ), Arrays.asList(
 252       0, 4
 253     ));
 254
 255     // lower end extremes
 256     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 1, true, Arrays.asList(
 257       0x0000000000000000L,0x0000000000000000L
 258     ), Arrays.asList(
 259       0
 260     ));
 261     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 2, true, Arrays.asList(
 262       0x0000000000000000L,0x0000000000000000L
 263     ), Arrays.asList(
 264       0
 265     ));
 266     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 4, true, Arrays.asList(
 267       0x0000000000000000L,0x0000000000000000L
 268     ), Arrays.asList(
 269       0
 270     ));
 271     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 6, true, Arrays.asList(
 272       0x0000000000000000L,0x0000000000000000L
 273     ), Arrays.asList(
 274       0
 275     ));
 276     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 8, true, Arrays.asList(
 277       0x0000000000000000L,0x0000000000000000L
 278     ), Arrays.asList(
 279       0
 280     ));
 281     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 64, true, Arrays.asList(
 282       0x0000000000000000L,0x0000000000000000L
 283     ), Arrays.asList(
 284       0
 285     ));
 286
 287     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE+0xfL, 4, true, Arrays.asList(
 288       0x000000000000000L,0x000000000000000L
 289     ), Arrays.asList(
 290       4
 291     ));
 292     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE+0x10L, 4, true, Arrays.asList(
 293       0x0000000000000010L,0x0000000000000010L,
 294       0x000000000000000L,0x000000000000000L
 295     ), Arrays.asList(
 296       0, 4
 297     ));
 298   }
 299
 300   public void testRandomSplit() throws Exception {
 301     long num = (long) atLeast(10);
 302     for (long i=0; i < num; i++) {
 303       executeOneRandomSplit(random);
 304     }
 305   }
 306
 307   private void executeOneRandomSplit(final Random random) throws Exception {
 308     long lower = randomLong(random);
 309     long len = random.nextInt(16384*1024); // not too large bitsets, else OOME!
 310     while (lower + len < lower) { // overflow
 311       lower >>= 1;
 312     }
 313     assertLongRangeSplit(lower, lower + len, random.nextInt(64) + 1, true, null, null);
 314   }
 315
 316   private long randomLong(final Random random) {
 317     long val;
 318     switch(random.nextInt(4)) {
 319       case 0:
 320         val = 1L << (random.nextInt(63)); //  patterns like 0x000000100000 (-1 yields patterns like 0x0000fff)
 321         break;
 322       case 1:
 323         val = -1L << (random.nextInt(63)); // patterns like 0xfffff00000
 324         break;
 325       default:
 326         val = random.nextLong();
 327     }
 328
 329     val += random.nextInt(5)-2;
 330
 331     if (random.nextBoolean()) {
 332       if (random.nextBoolean()) val += random.nextInt(100)-50;
 333       if (random.nextBoolean()) val = ~val;
 334       if (random.nextBoolean()) val = val<<1;
 335       if (random.nextBoolean()) val = val>>>1;
 336     }
 337
 338     return val;
 339   }
 340
 341   public void testSplitLongRange() throws Exception {
 342     // a hard-coded "standard" range
 343     assertLongRangeSplit(-5000L, 9500L, 4, true, Arrays.asList(
 344       0x7fffffffffffec78L,0x7fffffffffffec7fL,
 345       0x8000000000002510L,0x800000000000251cL,
 346       0x7fffffffffffec8L, 0x7fffffffffffecfL,
 347       0x800000000000250L, 0x800000000000250L,
 348       0x7fffffffffffedL,  0x7fffffffffffefL,
 349       0x80000000000020L,  0x80000000000024L,
 350       0x7ffffffffffffL,   0x8000000000001L
 351     ), Arrays.asList(
 352       0, 0,
 353       4, 4,
 354       8, 8,
 355       12
 356     ));
 357
 358     // the same with no range splitting
 359     assertLongRangeSplit(-5000L, 9500L, 64, true, Arrays.asList(
 360       0x7fffffffffffec78L,0x800000000000251cL
 361     ), Arrays.asList(
 362       0
 363     ));
 364
 365     // this tests optimized range splitting, if one of the inner bounds
 366     // is also the bound of the next lower precision, it should be used completely
 367     assertLongRangeSplit(0L, 1024L+63L, 4, true, Arrays.asList(
 368       0x800000000000040L, 0x800000000000043L,
 369       0x80000000000000L,  0x80000000000003L
 370     ), Arrays.asList(
 371       4, 8
 372     ));
 373
 374     // the full long range should only consist of a lowest precision range; no bitset testing here, as too much memory needed :-)
 375     assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 8, false, Arrays.asList(
 376       0x00L,0xffL
 377     ), Arrays.asList(
 378       56
 379     ));
 380
 381     // the same with precisionStep=4
 382     assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 4, false, Arrays.asList(
 383       0x0L,0xfL
 384     ), Arrays.asList(
 385       60
 386     ));
 387
 388     // the same with precisionStep=2
 389     assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 2, false, Arrays.asList(
 390       0x0L,0x3L
 391     ), Arrays.asList(
 392       62
 393     ));
 394
 395     // the same with precisionStep=1
 396     assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 1, false, Arrays.asList(
 397       0x0L,0x1L
 398     ), Arrays.asList(
 399       63
 400     ));
 401
 402     // a inverse range should produce no sub-ranges
 403     assertLongRangeSplit(9500L, -5000L, 4, false, Collections.<Long>emptyList(), Collections.<Integer>emptyList());
 404
 405     // a 0-length range should reproduce the range itsself
 406     assertLongRangeSplit(9500L, 9500L, 4, false, Arrays.asList(
 407       0x800000000000251cL,0x800000000000251cL
 408     ), Arrays.asList(
 409       0
 410     ));
 411   }
 412
 413   /** Note: The neededBounds Iterable must be unsigned (easier understanding what's happening) */
 414   private void assertIntRangeSplit(final int lower, final int upper, int precisionStep,
 415     final boolean useBitSet, final Iterable<Integer> expectedBounds, final Iterable<Integer> expectedShifts
 416   ) throws Exception {
 417     final OpenBitSet bits=useBitSet ? new OpenBitSet(upper-lower+1) : null;
 418     final Iterator<Integer> neededBounds = (expectedBounds == null) ? null : expectedBounds.iterator();
 419     final Iterator<Integer> neededShifts = (expectedShifts == null) ? null : expectedShifts.iterator();
 420
 421     NumericUtils.splitIntRange(new NumericUtils.IntRangeBuilder() {
 422       @Override
 423       public void addRange(int min, int max, int shift) {
 424         assertTrue("min, max should be inside bounds", min>=lower && min<=upper && max>=lower && max<=upper);
 425         if (useBitSet) for (int i=min; i<=max; i++) {
 426           assertFalse("ranges should not overlap", bits.getAndSet(i-lower) );
 427           // extra exit condition to prevent overflow on MAX_VALUE
 428           if (i == max) break;
 429         }
 430         if (neededBounds == null)
 431           return;
 432         // make unsigned ints for easier display and understanding
 433         min ^= 0x80000000;
 434         max ^= 0x80000000;
 435         //System.out.println("0x"+Integer.toHexString(min>>>shift)+",0x"+Integer.toHexString(max>>>shift)+")/*shift="+shift+"*/,");
 436         assertEquals( "shift", neededShifts.next().intValue(), shift);
 437         assertEquals( "inner min bound", neededBounds.next().intValue(), min>>>shift);
 438         assertEquals( "inner max bound", neededBounds.next().intValue(), max>>>shift);
 439       }
 440     }, precisionStep, lower, upper);
 441
 442     if (useBitSet) {
 443       // after flipping all bits in the range, the cardinality should be zero
 444       bits.flip(0,upper-lower+1);
 445       assertTrue("The sub-range concenated should match the whole range", bits.isEmpty());
 446     }
 447   }
 448
 449   public void testSplitIntRange() throws Exception {
 450     // a hard-coded "standard" range
 451     assertIntRangeSplit(-5000, 9500, 4, true, Arrays.asList(
 452       0x7fffec78,0x7fffec7f,
 453       0x80002510,0x8000251c,
 454       0x7fffec8, 0x7fffecf,
 455       0x8000250, 0x8000250,
 456       0x7fffed,  0x7fffef,
 457       0x800020,  0x800024,
 458       0x7ffff,   0x80001
 459     ), Arrays.asList(
 460       0, 0,
 461       4, 4,
 462       8, 8,
 463       12
 464     ));
 465
 466     // the same with no range splitting
 467     assertIntRangeSplit(-5000, 9500, 32, true, Arrays.asList(
 468       0x7fffec78,0x8000251c
 469     ), Arrays.asList(
 470       0
 471     ));
 472
 473     // this tests optimized range splitting, if one of the inner bounds
 474     // is also the bound of the next lower precision, it should be used completely
 475     assertIntRangeSplit(0, 1024+63, 4, true, Arrays.asList(
 476       0x8000040, 0x8000043,
 477       0x800000,  0x800003
 478     ), Arrays.asList(
 479       4, 8
 480     ));
 481
 482     // the full int range should only consist of a lowest precision range; no bitset testing here, as too much memory needed :-)
 483     assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 8, false, Arrays.asList(
 484       0x00,0xff
 485     ), Arrays.asList(
 486       24
 487     ));
 488
 489     // the same with precisionStep=4
 490     assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 4, false, Arrays.asList(
 491       0x0,0xf
 492     ), Arrays.asList(
 493       28
 494     ));
 495
 496     // the same with precisionStep=2
 497     assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 2, false, Arrays.asList(
 498       0x0,0x3
 499     ), Arrays.asList(
 500       30
 501     ));
 502
 503     // the same with precisionStep=1
 504     assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 1, false, Arrays.asList(
 505       0x0,0x1
 506     ), Arrays.asList(
 507       31
 508     ));
 509
 510     // a inverse range should produce no sub-ranges
 511     assertIntRangeSplit(9500, -5000, 4, false, Collections.<Integer>emptyList(), Collections.<Integer>emptyList());
 512
 513     // a 0-length range should reproduce the range itsself
 514     assertIntRangeSplit(9500, 9500, 4, false, Arrays.asList(
 515       0x8000251c,0x8000251c
 516     ), Arrays.asList(
 517       0
 518     ));
 519   }
 520
 521 }