← Back to branch summary

~slub.team/goobi-indexserver/3.x

« back to all changes in this revision

Viewing changes to lucene/src/test/org/apache/lucene/util/TestNumericUtils.java

  • Committer: Sebastian Meyer
  • Date: 2012-08-03 09:12:40 UTC
  • Revision ID: sebastian.meyer@slub-dresden.de-20120803091240-x6861b0vabq1xror
https://launchpad.net/bugs/985487
Remove Lucene and Solr source code and add patches instead
Fix Bug #985487: Auto-suggestion for the search interface

Show diffs side-by-side

added added

removed removed

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