lucene-java-3.5.0/lucene/src/test/org/apache/lucene/util/packed/TestPackedInts.java

   1 package org.apache.lucene.util.packed;
   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 org.apache.lucene.store.*;
  21 import org.apache.lucene.util.LuceneTestCase;
  22
  23 import java.util.ArrayList;
  24 import java.util.List;
  25 import java.util.Random;
  26 import java.io.IOException;
  27
  28 public class TestPackedInts extends LuceneTestCase {
  29   public void testBitsRequired() throws Exception {
  30     assertEquals(61, PackedInts.bitsRequired((long)Math.pow(2, 61)-1));
  31     assertEquals(61, PackedInts.bitsRequired(0x1FFFFFFFFFFFFFFFL));
  32     assertEquals(62, PackedInts.bitsRequired(0x3FFFFFFFFFFFFFFFL));
  33     assertEquals(63, PackedInts.bitsRequired(0x7FFFFFFFFFFFFFFFL));
  34   }
  35
  36   public void testMaxValues() throws Exception {
  37     assertEquals("1 bit -> max == 1",
  38             1, PackedInts.maxValue(1));
  39     assertEquals("2 bit -> max == 3",
  40             3, PackedInts.maxValue(2));
  41     assertEquals("8 bit -> max == 255",
  42             255, PackedInts.maxValue(8));
  43     assertEquals("63 bit -> max == Long.MAX_VALUE",
  44             Long.MAX_VALUE, PackedInts.maxValue(63));
  45     assertEquals("64 bit -> max == Long.MAX_VALUE (same as for 63 bit)",
  46             Long.MAX_VALUE, PackedInts.maxValue(64));
  47   }
  48
  49   public void testPackedInts() throws IOException {
  50     int num = atLeast(5);
  51     for (int iter = 0; iter < num; iter++) {
  52       long ceil = 2;
  53       for(int nbits=1;nbits<63;nbits++) {
  54         final int valueCount = 100+random.nextInt(500);
  55         final Directory d = newDirectory();
  56
  57         IndexOutput out = d.createOutput("out.bin");
  58         PackedInts.Writer w = PackedInts.getWriter(
  59                 out, valueCount, nbits);
  60
  61         final long[] values = new long[valueCount];
  62         for(int i=0;i<valueCount;i++) {
  63           long v = random.nextLong() % ceil;
  64           if (v < 0) {
  65             v = -v;
  66           }
  67           values[i] = v;
  68           w.add(values[i]);
  69         }
  70         w.finish();
  71         final long fp = out.getFilePointer();
  72         out.close();
  73         {// test reader
  74           IndexInput in = d.openInput("out.bin");
  75           PackedInts.Reader r = PackedInts.getReader(in);
  76           assertEquals(fp, in.getFilePointer());
  77           for(int i=0;i<valueCount;i++) {
  78             assertEquals("index=" + i + " ceil=" + ceil + " valueCount="
  79                     + valueCount + " nbits=" + nbits + " for "
  80                     + r.getClass().getSimpleName(), values[i], r.get(i));
  81           }
  82           in.close();
  83         }
  84         ceil *= 2;
  85         d.close();
  86       }
  87     }
  88   }
  89
  90   public void testControlledEquality() {
  91     final int VALUE_COUNT = 255;
  92     final int BITS_PER_VALUE = 8;
  93
  94     List<PackedInts.Mutable> packedInts =
  95             createPackedInts(VALUE_COUNT, BITS_PER_VALUE);
  96     for (PackedInts.Mutable packedInt: packedInts) {
  97       for (int i = 0 ; i < packedInt.size() ; i++) {
  98         packedInt.set(i, i+1);
  99       }
 100     }
 101     assertListEquality(packedInts);
 102   }
 103
 104   public void testRandomEquality() {
 105     final int[] VALUE_COUNTS = new int[]{0, 1, 5, 8, 100, 500};
 106     final int MIN_BITS_PER_VALUE = 1;
 107     final int MAX_BITS_PER_VALUE = 64;
 108
 109     for (int valueCount: VALUE_COUNTS) {
 110       for (int bitsPerValue = MIN_BITS_PER_VALUE ;
 111            bitsPerValue <= MAX_BITS_PER_VALUE ;
 112            bitsPerValue++) {
 113         assertRandomEquality(valueCount, bitsPerValue, random.nextLong());
 114       }
 115     }
 116   }
 117
 118   private void assertRandomEquality(int valueCount, int bitsPerValue, long randomSeed) {
 119     List<PackedInts.Mutable> packedInts = createPackedInts(valueCount, bitsPerValue);
 120     for (PackedInts.Mutable packedInt: packedInts) {
 121       try {
 122         fill(packedInt, (long)(Math.pow(2, bitsPerValue)-1), randomSeed);
 123       } catch (Exception e) {
 124         e.printStackTrace(System.err);
 125         fail(String.format(
 126                 "Exception while filling %s: valueCount=%d, bitsPerValue=%s",
 127                 packedInt.getClass().getSimpleName(),
 128                 valueCount, bitsPerValue));
 129       }
 130     }
 131     assertListEquality(packedInts);
 132   }
 133
 134   private List<PackedInts.Mutable> createPackedInts(
 135           int valueCount, int bitsPerValue) {
 136     List<PackedInts.Mutable> packedInts = new ArrayList<PackedInts.Mutable>();
 137     if (bitsPerValue <= 8) {
 138       packedInts.add(new Direct8(valueCount));
 139     }
 140     if (bitsPerValue <= 16) {
 141       packedInts.add(new Direct16(valueCount));
 142     }
 143     if (bitsPerValue <= 31) {
 144       packedInts.add(new Packed32(valueCount, bitsPerValue));
 145     }
 146     if (bitsPerValue <= 32) {
 147       packedInts.add(new Direct32(valueCount));
 148     }
 149     if (bitsPerValue <= 63) {
 150       packedInts.add(new Packed64(valueCount, bitsPerValue));
 151     }
 152     packedInts.add(new Direct64(valueCount));
 153     return packedInts;
 154   }
 155
 156   private void fill(PackedInts.Mutable packedInt, long maxValue, long randomSeed) {
 157     Random rnd2 = new Random(randomSeed);
 158     maxValue++;
 159     for (int i = 0 ; i < packedInt.size() ; i++) {
 160       long value = Math.abs(rnd2.nextLong() % maxValue);
 161       packedInt.set(i, value);
 162       assertEquals(String.format(
 163               "The set/get of the value at index %d should match for %s",
 164               i, packedInt.getClass().getSimpleName()),
 165               value, packedInt.get(i));
 166     }
 167   }
 168
 169   private void assertListEquality(
 170           List<? extends PackedInts.Reader> packedInts) {
 171     assertListEquality("", packedInts);
 172   }
 173
 174   private void assertListEquality(
 175             String message, List<? extends PackedInts.Reader> packedInts) {
 176     if (packedInts.size() == 0) {
 177       return;
 178     }
 179     PackedInts.Reader base = packedInts.get(0);
 180     int valueCount = base.size();
 181     for (PackedInts.Reader packedInt: packedInts) {
 182       assertEquals(message + ". The number of values should be the same ",
 183               valueCount, packedInt.size());
 184     }
 185     for (int i = 0 ; i < valueCount ; i++) {
 186       for (int j = 1 ; j < packedInts.size() ; j++) {
 187         assertEquals(String.format(
 188                 "%s. The value at index %d should be the same for %s and %s",
 189                 message, i, base.getClass().getSimpleName(),
 190                 packedInts.get(j).getClass().getSimpleName()),
 191                 base.get(i), packedInts.get(j).get(i));
 192       }
 193     }
 194   }
 195
 196   public void testSingleValue() throws Exception {
 197     Directory dir = newDirectory();
 198     IndexOutput out = dir.createOutput("out");
 199     PackedInts.Writer w = PackedInts.getWriter(out, 1, 8);
 200     w.add(17);
 201     w.finish();
 202     final long end = out.getFilePointer();
 203     out.close();
 204
 205     IndexInput in = dir.openInput("out");
 206     PackedInts.getReader(in);
 207     assertEquals(end, in.getFilePointer());
 208     in.close();
 209
 210     dir.close();
 211   }
 212
 213   public void testSecondaryBlockChange() throws IOException {
 214     PackedInts.Mutable mutable = new Packed64(26, 5);
 215     mutable.set(24, 31);
 216     assertEquals("The value #24 should be correct", 31, mutable.get(24));
 217     mutable.set(4, 16);
 218     assertEquals("The value #24 should remain unchanged", 31, mutable.get(24));
 219   }
 220
 221   /*
 222     Check if the structures properly handle the case where
 223     index * bitsPerValue > Integer.MAX_VALUE
 224
 225     NOTE: this test allocates 256 MB
 226    */
 227   public void testIntOverflow() {
 228     int INDEX = (int)Math.pow(2, 30)+1;
 229     int BITS = 2;
 230
 231     Packed32 p32 = new Packed32(INDEX, BITS);
 232     p32.set(INDEX-1, 1);
 233     assertEquals("The value at position " + (INDEX-1)
 234         + " should be correct for Packed32", 1, p32.get(INDEX-1));
 235     p32 = null; // To free the 256MB used
 236
 237     Packed64 p64 = new Packed64(INDEX, BITS);
 238     p64.set(INDEX-1, 1);
 239     assertEquals("The value at position " + (INDEX-1)
 240         + " should be correct for Packed64", 1, p64.get(INDEX-1));
 241   }
 242 }