1 package org.apache.lucene.util;
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
11 * http://www.apache.org/licenses/LICENSE-2.0
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.
20 import java.io.IOException;
21 import java.util.BitSet;
23 import junit.framework.TestSuite;
24 import junit.textui.TestRunner;
26 import org.apache.lucene.search.DocIdSetIterator;
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));
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.
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());
47 assertTrue("End of Matcher", m.nextDoc() == DocIdSetIterator.NO_MORE_DOCS);
51 SortedVIntList vintList,
53 int expectedByteSize) throws IOException {
54 assertEquals("Size", ints.length, vintList.size());
55 assertEquals("Byte size", expectedByteSize, vintList.getByteSize());
56 tstIterator(vintList, ints);
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
66 if ((i > 0) && (ints[i-1] == ints[i])) {
67 return; // BitSet cannot store duplicate.
71 SortedVIntList svil = new SortedVIntList(bs);
72 tstVIntList(svil, ints, expectedByteSize);
73 tstVIntList(new SortedVIntList(svil.iterator()), ints, expectedByteSize);
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;
82 private int vIntByteSize(int i) {
84 if (i <= VB1) return 1;
85 if (i <= VB2) return 2;
86 if (i <= VB3) return 3;
87 if (i <= VB4) return 4;
91 private int vIntListByteSize(int [] ints) {
94 for (int i = 0; i < ints.length; i++) {
95 byteSize += vIntByteSize(ints[i] - last);
101 public void tstInts(int [] ints) {
102 int expectedByteSize = vIntListByteSize(ints);
104 tstVIntList(new SortedVIntList(ints), ints, expectedByteSize);
105 tstViaBitSet(ints, expectedByteSize);
106 } catch (IOException ioe) {
107 throw new Error(ioe);
111 public void tstIllegalArgExc(int [] ints) {
113 new SortedVIntList(ints);
115 catch (IllegalArgumentException e) {
118 fail("Expected IllegalArgumentException");
121 private int[] fibArray(int a, int b, int size) {
122 final int[] fib = new int[size];
125 for (int i = 2; i < size; i++) {
126 fib[i] = fib[i-1] + fib[i-2];
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]);
139 public void test01() {
140 tstInts(new int[] {});
142 public void test02() {
143 tstInts(new int[] {0});
145 public void test04a() {
146 tstInts(new int[] {0, VB2 - 1});
148 public void test04b() {
149 tstInts(new int[] {0, VB2});
151 public void test04c() {
152 tstInts(new int[] {0, VB2 + 1});
154 public void test05() {
155 tstInts(fibArray(0,1,7)); // includes duplicate value 1
157 public void test05b() {
158 tstInts(reverseDiffs(fibArray(0,1,7)));
160 public void test06() {
161 tstInts(fibArray(1,2,45)); // no duplicates, size 46 exceeds max int.
163 public void test06b() {
164 tstInts(reverseDiffs(fibArray(1,2,45)));
166 public void test07a() {
167 tstInts(new int[] {0, VB3});
169 public void test07b() {
170 tstInts(new int[] {1, VB3 + 2});
172 public void test07c() {
173 tstInts(new int[] {2, VB3 + 4});
175 public void test08a() {
176 tstInts(new int[] {0, VB4 + 1});
178 public void test08b() {
179 tstInts(new int[] {1, VB4 + 1});
181 public void test08c() {
182 tstInts(new int[] {2, VB4 + 1});
185 public void test10() {
186 tstIllegalArgExc(new int[] {-1});
188 public void test11() {
189 tstIllegalArgExc(new int[] {1,0});
191 public void test12() {
192 tstIllegalArgExc(new int[] {0,1,1,2,3,5,8,0});
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;
199 tstIterator(new SortedVIntList(a), a);