lucene-java-3.5.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     // Cannot use FixedBitSet since the range could be long:
 178     final OpenBitSet bits=useBitSet ? new OpenBitSet(upper-lower+1) : null;
 179     final Iterator<Long> neededBounds = (expectedBounds == null) ? null : expectedBounds.iterator();
 180     final Iterator<Integer> neededShifts = (expectedShifts == null) ? null : expectedShifts.iterator();
 181
 182     NumericUtils.splitLongRange(new NumericUtils.LongRangeBuilder() {
 183       @Override
 184       public void addRange(long min, long max, int shift) {
 185         assertTrue("min, max should be inside bounds", min>=lower && min<=upper && max>=lower && max<=upper);
 186         if (useBitSet) for (long l=min; l<=max; l++) {
 187           assertFalse("ranges should not overlap", bits.getAndSet(l-lower) );
 188           // extra exit condition to prevent overflow on MAX_VALUE
 189           if (l == max) break;
 190         }
 191         if (neededBounds == null || neededShifts == null)
 192           return;
 193         // make unsigned longs for easier display and understanding
 194         min ^= 0x8000000000000000L;
 195         max ^= 0x8000000000000000L;
 196         //System.out.println("0x"+Long.toHexString(min>>>shift)+"L,0x"+Long.toHexString(max>>>shift)+"L)/*shift="+shift+"*/,");
 197         assertEquals( "shift", neededShifts.next().intValue(), shift);
 198         assertEquals( "inner min bound", neededBounds.next().longValue(), min>>>shift);
 199         assertEquals( "inner max bound", neededBounds.next().longValue(), max>>>shift);
 200       }
 201     }, precisionStep, lower, upper);
 202
 203     if (useBitSet) {
 204       // after flipping all bits in the range, the cardinality should be zero
 205       bits.flip(0,upper-lower+1);
 206       assertEquals("The sub-range concenated should match the whole range", 0, bits.cardinality());
 207     }
 208   }
 209
 210   /** LUCENE-2541: NumericRangeQuery errors with endpoints near long min and max values */
 211   public void testLongExtremeValues() throws Exception {
 212     // upper end extremes
 213     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 1, true, Arrays.asList(
 214       0xffffffffffffffffL,0xffffffffffffffffL
 215     ), Arrays.asList(
 216       0
 217     ));
 218     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 2, true, Arrays.asList(
 219       0xffffffffffffffffL,0xffffffffffffffffL
 220     ), Arrays.asList(
 221       0
 222     ));
 223     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 4, true, Arrays.asList(
 224       0xffffffffffffffffL,0xffffffffffffffffL
 225     ), Arrays.asList(
 226       0
 227     ));
 228     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 6, true, Arrays.asList(
 229       0xffffffffffffffffL,0xffffffffffffffffL
 230     ), Arrays.asList(
 231       0
 232     ));
 233     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 8, true, Arrays.asList(
 234       0xffffffffffffffffL,0xffffffffffffffffL
 235     ), Arrays.asList(
 236       0
 237     ));
 238     assertLongRangeSplit(Long.MAX_VALUE, Long.MAX_VALUE, 64, true, Arrays.asList(
 239       0xffffffffffffffffL,0xffffffffffffffffL
 240     ), Arrays.asList(
 241       0
 242     ));
 243
 244     assertLongRangeSplit(Long.MAX_VALUE-0xfL, Long.MAX_VALUE, 4, true, Arrays.asList(
 245       0xfffffffffffffffL,0xfffffffffffffffL
 246     ), Arrays.asList(
 247       4
 248     ));
 249     assertLongRangeSplit(Long.MAX_VALUE-0x10L, Long.MAX_VALUE, 4, true, Arrays.asList(
 250       0xffffffffffffffefL,0xffffffffffffffefL,
 251       0xfffffffffffffffL,0xfffffffffffffffL
 252     ), Arrays.asList(
 253       0, 4
 254     ));
 255
 256     // lower end extremes
 257     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 1, true, Arrays.asList(
 258       0x0000000000000000L,0x0000000000000000L
 259     ), Arrays.asList(
 260       0
 261     ));
 262     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 2, true, Arrays.asList(
 263       0x0000000000000000L,0x0000000000000000L
 264     ), Arrays.asList(
 265       0
 266     ));
 267     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 4, true, Arrays.asList(
 268       0x0000000000000000L,0x0000000000000000L
 269     ), Arrays.asList(
 270       0
 271     ));
 272     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 6, true, Arrays.asList(
 273       0x0000000000000000L,0x0000000000000000L
 274     ), Arrays.asList(
 275       0
 276     ));
 277     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 8, true, Arrays.asList(
 278       0x0000000000000000L,0x0000000000000000L
 279     ), Arrays.asList(
 280       0
 281     ));
 282     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE, 64, true, Arrays.asList(
 283       0x0000000000000000L,0x0000000000000000L
 284     ), Arrays.asList(
 285       0
 286     ));
 287
 288     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE+0xfL, 4, true, Arrays.asList(
 289       0x000000000000000L,0x000000000000000L
 290     ), Arrays.asList(
 291       4
 292     ));
 293     assertLongRangeSplit(Long.MIN_VALUE, Long.MIN_VALUE+0x10L, 4, true, Arrays.asList(
 294       0x0000000000000010L,0x0000000000000010L,
 295       0x000000000000000L,0x000000000000000L
 296     ), Arrays.asList(
 297       0, 4
 298     ));
 299   }
 300
 301   public void testRandomSplit() throws Exception {
 302     long num = (long) atLeast(10);
 303     for (long i=0; i < num; i++) {
 304       executeOneRandomSplit(random);
 305     }
 306   }
 307
 308   private void executeOneRandomSplit(final Random random) throws Exception {
 309     long lower = randomLong(random);
 310     long len = random.nextInt(16384*1024); // not too large bitsets, else OOME!
 311     while (lower + len < lower) { // overflow
 312       lower >>= 1;
 313     }
 314     assertLongRangeSplit(lower, lower + len, random.nextInt(64) + 1, true, null, null);
 315   }
 316
 317   private long randomLong(final Random random) {
 318     long val;
 319     switch(random.nextInt(4)) {
 320       case 0:
 321         val = 1L << (random.nextInt(63)); //  patterns like 0x000000100000 (-1 yields patterns like 0x0000fff)
 322         break;
 323       case 1:
 324         val = -1L << (random.nextInt(63)); // patterns like 0xfffff00000
 325         break;
 326       default:
 327         val = random.nextLong();
 328     }
 329
 330     val += random.nextInt(5)-2;
 331
 332     if (random.nextBoolean()) {
 333       if (random.nextBoolean()) val += random.nextInt(100)-50;
 334       if (random.nextBoolean()) val = ~val;
 335       if (random.nextBoolean()) val = val<<1;
 336       if (random.nextBoolean()) val = val>>>1;
 337     }
 338
 339     return val;
 340   }
 341
 342   public void testSplitLongRange() throws Exception {
 343     // a hard-coded "standard" range
 344     assertLongRangeSplit(-5000L, 9500L, 4, true, Arrays.asList(
 345       0x7fffffffffffec78L,0x7fffffffffffec7fL,
 346       0x8000000000002510L,0x800000000000251cL,
 347       0x7fffffffffffec8L, 0x7fffffffffffecfL,
 348       0x800000000000250L, 0x800000000000250L,
 349       0x7fffffffffffedL,  0x7fffffffffffefL,
 350       0x80000000000020L,  0x80000000000024L,
 351       0x7ffffffffffffL,   0x8000000000001L
 352     ), Arrays.asList(
 353       0, 0,
 354       4, 4,
 355       8, 8,
 356       12
 357     ));
 358
 359     // the same with no range splitting
 360     assertLongRangeSplit(-5000L, 9500L, 64, true, Arrays.asList(
 361       0x7fffffffffffec78L,0x800000000000251cL
 362     ), Arrays.asList(
 363       0
 364     ));
 365
 366     // this tests optimized range splitting, if one of the inner bounds
 367     // is also the bound of the next lower precision, it should be used completely
 368     assertLongRangeSplit(0L, 1024L+63L, 4, true, Arrays.asList(
 369       0x800000000000040L, 0x800000000000043L,
 370       0x80000000000000L,  0x80000000000003L
 371     ), Arrays.asList(
 372       4, 8
 373     ));
 374
 375     // the full long range should only consist of a lowest precision range; no bitset testing here, as too much memory needed :-)
 376     assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 8, false, Arrays.asList(
 377       0x00L,0xffL
 378     ), Arrays.asList(
 379       56
 380     ));
 381
 382     // the same with precisionStep=4
 383     assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 4, false, Arrays.asList(
 384       0x0L,0xfL
 385     ), Arrays.asList(
 386       60
 387     ));
 388
 389     // the same with precisionStep=2
 390     assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 2, false, Arrays.asList(
 391       0x0L,0x3L
 392     ), Arrays.asList(
 393       62
 394     ));
 395
 396     // the same with precisionStep=1
 397     assertLongRangeSplit(Long.MIN_VALUE, Long.MAX_VALUE, 1, false, Arrays.asList(
 398       0x0L,0x1L
 399     ), Arrays.asList(
 400       63
 401     ));
 402
 403     // a inverse range should produce no sub-ranges
 404     assertLongRangeSplit(9500L, -5000L, 4, false, Collections.<Long>emptyList(), Collections.<Integer>emptyList());
 405
 406     // a 0-length range should reproduce the range itsself
 407     assertLongRangeSplit(9500L, 9500L, 4, false, Arrays.asList(
 408       0x800000000000251cL,0x800000000000251cL
 409     ), Arrays.asList(
 410       0
 411     ));
 412   }
 413
 414   /** Note: The neededBounds Iterable must be unsigned (easier understanding what's happening) */
 415   private void assertIntRangeSplit(final int lower, final int upper, int precisionStep,
 416     final boolean useBitSet, final Iterable<Integer> expectedBounds, final Iterable<Integer> expectedShifts
 417   ) throws Exception {
 418     final FixedBitSet bits=useBitSet ? new FixedBitSet(upper-lower+1) : null;
 419     final Iterator<Integer> neededBounds = (expectedBounds == null) ? null : expectedBounds.iterator();
 420     final Iterator<Integer> neededShifts = (expectedShifts == null) ? null : expectedShifts.iterator();
 421
 422     NumericUtils.splitIntRange(new NumericUtils.IntRangeBuilder() {
 423       @Override
 424       public void addRange(int min, int max, int shift) {
 425         assertTrue("min, max should be inside bounds", min>=lower && min<=upper && max>=lower && max<=upper);
 426         if (useBitSet) for (int i=min; i<=max; i++) {
 427           assertFalse("ranges should not overlap", bits.getAndSet(i-lower) );
 428           // extra exit condition to prevent overflow on MAX_VALUE
 429           if (i == max) break;
 430         }
 431         if (neededBounds == null)
 432           return;
 433         // make unsigned ints for easier display and understanding
 434         min ^= 0x80000000;
 435         max ^= 0x80000000;
 436         //System.out.println("0x"+Integer.toHexString(min>>>shift)+",0x"+Integer.toHexString(max>>>shift)+")/*shift="+shift+"*/,");
 437         assertEquals( "shift", neededShifts.next().intValue(), shift);
 438         assertEquals( "inner min bound", neededBounds.next().intValue(), min>>>shift);
 439         assertEquals( "inner max bound", neededBounds.next().intValue(), max>>>shift);
 440       }
 441     }, precisionStep, lower, upper);
 442
 443     if (useBitSet) {
 444       // after flipping all bits in the range, the cardinality should be zero
 445       bits.flip(0, upper-lower+1);
 446       assertEquals("The sub-range concenated should match the whole range", 0, bits.cardinality());
 447     }
 448   }
 449
 450   public void testSplitIntRange() throws Exception {
 451     // a hard-coded "standard" range
 452     assertIntRangeSplit(-5000, 9500, 4, true, Arrays.asList(
 453       0x7fffec78,0x7fffec7f,
 454       0x80002510,0x8000251c,
 455       0x7fffec8, 0x7fffecf,
 456       0x8000250, 0x8000250,
 457       0x7fffed,  0x7fffef,
 458       0x800020,  0x800024,
 459       0x7ffff,   0x80001
 460     ), Arrays.asList(
 461       0, 0,
 462       4, 4,
 463       8, 8,
 464       12
 465     ));
 466
 467     // the same with no range splitting
 468     assertIntRangeSplit(-5000, 9500, 32, true, Arrays.asList(
 469       0x7fffec78,0x8000251c
 470     ), Arrays.asList(
 471       0
 472     ));
 473
 474     // this tests optimized range splitting, if one of the inner bounds
 475     // is also the bound of the next lower precision, it should be used completely
 476     assertIntRangeSplit(0, 1024+63, 4, true, Arrays.asList(
 477       0x8000040, 0x8000043,
 478       0x800000,  0x800003
 479     ), Arrays.asList(
 480       4, 8
 481     ));
 482
 483     // the full int range should only consist of a lowest precision range; no bitset testing here, as too much memory needed :-)
 484     assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 8, false, Arrays.asList(
 485       0x00,0xff
 486     ), Arrays.asList(
 487       24
 488     ));
 489
 490     // the same with precisionStep=4
 491     assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 4, false, Arrays.asList(
 492       0x0,0xf
 493     ), Arrays.asList(
 494       28
 495     ));
 496
 497     // the same with precisionStep=2
 498     assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 2, false, Arrays.asList(
 499       0x0,0x3
 500     ), Arrays.asList(
 501       30
 502     ));
 503
 504     // the same with precisionStep=1
 505     assertIntRangeSplit(Integer.MIN_VALUE, Integer.MAX_VALUE, 1, false, Arrays.asList(
 506       0x0,0x1
 507     ), Arrays.asList(
 508       31
 509     ));
 510
 511     // a inverse range should produce no sub-ranges
 512     assertIntRangeSplit(9500, -5000, 4, false, Collections.<Integer>emptyList(), Collections.<Integer>emptyList());
 513
 514     // a 0-length range should reproduce the range itsself
 515     assertIntRangeSplit(9500, 9500, 4, false, Arrays.asList(
 516       0x8000251c,0x8000251c
 517     ), Arrays.asList(
 518       0
 519     ));
 520   }
 521
 522 }