lucene-java-3.5.0/lucene/src/test/org/apache/lucene/util/TestSortedVIntList.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.io.IOException;
  21 import java.util.BitSet;
  22
  23 import junit.framework.TestSuite;
  24 import junit.textui.TestRunner;
  25
  26 import org.apache.lucene.search.DocIdSetIterator;
  27
  28 public class TestSortedVIntList extends LuceneTestCase {
  29   /** Main for running test case by itself. */
  30   public static void main(String args[]) {
  31     TestRunner.run(new TestSuite(TestSortedVIntList.class));
  32   }
  33
  34   void tstIterator (
  35           SortedVIntList vintList,
  36           int[] ints) throws IOException {
  37     for (int i = 0; i < ints.length; i++) {
  38       if ((i > 0) && (ints[i-1] == ints[i])) {
  39         return; // DocNrSkipper should not skip to same document.
  40       }
  41     }
  42     DocIdSetIterator m = vintList.iterator();
  43     for (int i = 0; i < ints.length; i++) {
  44       assertTrue("No end of Matcher at: " + i, m.nextDoc() != DocIdSetIterator.NO_MORE_DOCS);
  45       assertEquals(ints[i], m.docID());
  46     }
  47     assertTrue("End of Matcher", m.nextDoc() == DocIdSetIterator.NO_MORE_DOCS);
  48   }
  49
  50   void tstVIntList(
  51           SortedVIntList vintList,
  52           int[] ints,
  53           int expectedByteSize) throws IOException {
  54     assertEquals("Size", ints.length, vintList.size());
  55     assertEquals("Byte size", expectedByteSize, vintList.getByteSize());
  56     tstIterator(vintList, ints);
  57   }
  58
  59   public void tstViaBitSet(int [] ints, int expectedByteSize) throws IOException {
  60     final int MAX_INT_FOR_BITSET = 1024 * 1024;
  61     BitSet bs = new BitSet();
  62     for (int i = 0; i < ints.length; i++) {
  63       if (ints[i] > MAX_INT_FOR_BITSET) {
  64         return; // BitSet takes too much memory
  65       }
  66       if ((i > 0) && (ints[i-1] == ints[i])) {
  67         return; // BitSet cannot store duplicate.
  68       }
  69       bs.set(ints[i]);
  70     }
  71     SortedVIntList svil = new SortedVIntList(bs);
  72     tstVIntList(svil, ints, expectedByteSize);
  73     tstVIntList(new SortedVIntList(svil.iterator()), ints, expectedByteSize);
  74   }
  75
  76   private static final int VB1 = 0x7F;
  77   private static final int BIT_SHIFT = 7;
  78   private static final int VB2 = (VB1 << BIT_SHIFT) | VB1;
  79   private static final int VB3 = (VB2 << BIT_SHIFT) | VB1;
  80   private static final int VB4 = (VB3 << BIT_SHIFT) | VB1;
  81
  82   private int vIntByteSize(int i) {
  83     assert i >= 0;
  84     if (i <= VB1) return 1;
  85     if (i <= VB2) return 2;
  86     if (i <= VB3) return 3;
  87     if (i <= VB4) return 4;
  88     return 5;
  89   }
  90
  91   private int vIntListByteSize(int [] ints) {
  92     int byteSize = 0;
  93     int last = 0;
  94     for (int i = 0; i < ints.length; i++) {
  95       byteSize += vIntByteSize(ints[i] - last);
  96       last = ints[i];
  97     }
  98     return byteSize;
  99   }
 100
 101   public void tstInts(int [] ints) {
 102     int expectedByteSize = vIntListByteSize(ints);
 103     try {
 104       tstVIntList(new SortedVIntList(ints), ints, expectedByteSize);
 105       tstViaBitSet(ints, expectedByteSize);
 106     } catch (IOException ioe) {
 107       throw new Error(ioe);
 108     }
 109   }
 110
 111   public void tstIllegalArgExc(int [] ints) {
 112     try {
 113       new SortedVIntList(ints);
 114     }
 115     catch (IllegalArgumentException e) {
 116       return;
 117     }
 118     fail("Expected IllegalArgumentException");
 119   }
 120
 121   private int[] fibArray(int a, int b, int size) {
 122     final int[] fib = new int[size];
 123     fib[0] = a;
 124     fib[1] = b;
 125     for (int i = 2; i < size; i++) {
 126       fib[i] = fib[i-1] + fib[i-2];
 127     }
 128     return fib;
 129   }
 130
 131   private int[] reverseDiffs(int []ints) { // reverse the order of the successive differences
 132     final int[] res = new int[ints.length];
 133     for (int i = 0; i < ints.length; i++) {
 134       res[i] = ints[ints.length - 1] + (ints[0] - ints[ints.length - 1 - i]);
 135     }
 136     return res;
 137   }
 138
 139   public void test01() {
 140     tstInts(new int[] {});
 141   }
 142   public void test02() {
 143     tstInts(new int[] {0});
 144   }
 145   public void test04a() {
 146     tstInts(new int[] {0, VB2 - 1});
 147   }
 148   public void test04b() {
 149     tstInts(new int[] {0, VB2});
 150   }
 151   public void test04c() {
 152     tstInts(new int[] {0, VB2 + 1});
 153   }
 154   public void test05() {
 155     tstInts(fibArray(0,1,7)); // includes duplicate value 1
 156   }
 157   public void test05b() {
 158     tstInts(reverseDiffs(fibArray(0,1,7)));
 159   }
 160   public void test06() {
 161     tstInts(fibArray(1,2,45)); // no duplicates, size 46 exceeds max int.
 162   }
 163   public void test06b() {
 164     tstInts(reverseDiffs(fibArray(1,2,45)));
 165   }
 166   public void test07a() {
 167     tstInts(new int[] {0, VB3});
 168   }
 169   public void test07b() {
 170     tstInts(new int[] {1, VB3 + 2});
 171   }
 172   public void test07c() {
 173     tstInts(new int[] {2, VB3 + 4});
 174   }
 175   public void test08a() {
 176     tstInts(new int[] {0, VB4 + 1});
 177   }
 178   public void test08b() {
 179     tstInts(new int[] {1, VB4 + 1});
 180   }
 181   public void test08c() {
 182     tstInts(new int[] {2, VB4 + 1});
 183   }
 184
 185   public void test10() {
 186     tstIllegalArgExc(new int[] {-1});
 187   }
 188   public void test11() {
 189     tstIllegalArgExc(new int[] {1,0});
 190   }
 191   public void test12() {
 192    tstIllegalArgExc(new int[] {0,1,1,2,3,5,8,0});
 193   }
 194   public void test13Allocation() throws Exception {
 195     int [] a = new int[2000]; // SortedVIntList initial byte size is 128
 196     for (int i = 0; i < a.length; i++) {
 197       a[i] = (107 + i) * i;
 198     }
 199     tstIterator(new SortedVIntList(a), a);
 200   }
 201 }