lucene/backwards/src/test/org/apache/lucene/util/TestFixedBitSet.java - manifoldcf-integration-solr-3.x - Git at Google

 /**
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
  * this work for additional information regarding copyright ownership.
  * The ASF licenses this file to You under the Apache License, Version 2.0
  * (the "License"); you may not use this file except in compliance with
  * the License.  You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 package org.apache.lucene.util;

 import java.io.IOException;
 import java.util.BitSet;

 import org.apache.lucene.search.DocIdSetIterator;

 public class TestFixedBitSet extends LuceneTestCase {

   void doGet(BitSet a, FixedBitSet b) {
     int max = b.length();
     for (int i=0; i<max; i++) {
       if (a.get(i) != b.get(i)) {
         fail("mismatch: BitSet=["+i+"]="+a.get(i));
       }
     }
   }

   void doNextSetBit(BitSet a, FixedBitSet b) {
     int aa=-1,bb=-1;
     do {
       aa = a.nextSetBit(aa+1);
       bb = bb < b.length()-1 ? b.nextSetBit(bb+1) : -1;
       assertEquals(aa,bb);
     } while (aa>=0);
   }

   void doPrevSetBit(BitSet a, FixedBitSet b) {
     int aa = a.size() + random.nextInt(100);
     int bb = aa;
     do {
       // aa = a.prevSetBit(aa-1);
       aa--;
       while ((aa >= 0) && (! a.get(aa))) {
       	aa--;
       }
       if (b.length() == 0) {
         bb = -1;
       } else if (bb > b.length()-1) {
         bb = b.prevSetBit(b.length()-1);
       } else if (bb < 1) {
         bb = -1;
       } else {
         bb = bb >= 1 ? b.prevSetBit(bb-1) : -1;
       }
       assertEquals(aa,bb);
     } while (aa>=0);
   }

   // test interleaving different FixedBitSetIterator.next()/skipTo()
   void doIterate(BitSet a, FixedBitSet b, int mode) throws IOException {
     if (mode==1) doIterate1(a, b);
     if (mode==2) doIterate2(a, b);
   }

   void doIterate1(BitSet a, FixedBitSet b) throws IOException {
     int aa=-1,bb=-1;
     DocIdSetIterator iterator = b.iterator();
     do {
       aa = a.nextSetBit(aa+1);
       bb = (bb < b.length() && random.nextBoolean()) ? iterator.nextDoc() : iterator.advance(bb + 1);
       assertEquals(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
     } while (aa>=0);
   }

   void doIterate2(BitSet a, FixedBitSet b) throws IOException {
     int aa=-1,bb=-1;
     DocIdSetIterator iterator = b.iterator();
     do {
       aa = a.nextSetBit(aa+1);
       bb = random.nextBoolean() ? iterator.nextDoc() : iterator.advance(bb + 1);
       assertEquals(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
     } while (aa>=0);
   }

   void doRandomSets(int maxSize, int iter, int mode) throws IOException {
     BitSet a0=null;
     FixedBitSet b0=null;

     for (int i=0; i<iter; i++) {
       int sz = _TestUtil.nextInt(random, 2, maxSize);
       BitSet a = new BitSet(sz);
       FixedBitSet b = new FixedBitSet(sz);

       // test the various ways of setting bits
       if (sz>0) {
         int nOper = random.nextInt(sz);
         for (int j=0; j<nOper; j++) {
           int idx;

           idx = random.nextInt(sz);
           a.set(idx);
           b.set(idx);

           idx = random.nextInt(sz);
           a.clear(idx);
           b.clear(idx);

           idx = random.nextInt(sz);
           a.flip(idx);
           b.flip(idx, idx+1);

           idx = random.nextInt(sz);
           a.flip(idx);
           b.flip(idx, idx+1);

           boolean val2 = b.get(idx);
           boolean val = b.getAndSet(idx);
           assertTrue(val2 == val);
           assertTrue(b.get(idx));

           if (!val) b.clear(idx);
           assertTrue(b.get(idx) == val);
         }
       }

       // test that the various ways of accessing the bits are equivalent
       doGet(a,b);

       // test ranges, including possible extension
       int fromIndex, toIndex;
       fromIndex = random.nextInt(sz/2);
       toIndex = fromIndex + random.nextInt(sz - fromIndex);
       BitSet aa = (BitSet)a.clone(); aa.flip(fromIndex,toIndex);
       FixedBitSet bb = (FixedBitSet)b.clone(); bb.flip(fromIndex,toIndex);

       doIterate(aa,bb, mode);   // a problem here is from flip or doIterate

       fromIndex = random.nextInt(sz/2);
       toIndex = fromIndex + random.nextInt(sz - fromIndex);
       aa = (BitSet)a.clone(); aa.clear(fromIndex,toIndex);
       bb = (FixedBitSet)b.clone(); bb.clear(fromIndex,toIndex);

       doNextSetBit(aa,bb); // a problem here is from clear() or nextSetBit

       doPrevSetBit(aa,bb);

       fromIndex = random.nextInt(sz/2);
       toIndex = fromIndex + random.nextInt(sz - fromIndex);
       aa = (BitSet)a.clone(); aa.set(fromIndex,toIndex);
       bb = (FixedBitSet)b.clone(); bb.set(fromIndex,toIndex);

       doNextSetBit(aa,bb); // a problem here is from set() or nextSetBit

       doPrevSetBit(aa,bb);

       if (b0 != null && b0.length() <= b.length()) {
         assertEquals(a.cardinality(), b.cardinality());

         BitSet a_or = (BitSet) a.clone();
         a_or.or(a0);

         FixedBitSet b_or = (FixedBitSet) b.clone();
         b_or.or(b0);

         assertEquals(a0.cardinality(), b0.cardinality());
         assertEquals(a_or.cardinality(), b_or.cardinality());

         doIterate(a_or, b_or, mode);
       }

       a0=a;
       b0=b;
     }
   }

   // large enough to flush obvious bugs, small enough to run in <.5 sec as part of a
   // larger testsuite.
   public void testSmall() throws IOException {
     doRandomSets(atLeast(1200), atLeast(1000), 1);
     doRandomSets(atLeast(1200), atLeast(1000), 2);
   }

   // uncomment to run a bigger test (~2 minutes).
   /*
   public void testBig() {
     doRandomSets(2000,200000, 1);
     doRandomSets(2000,200000, 2);
   }
   */

   public void testEquals() {
     // This test can't handle numBits==0:
     final int numBits = random.nextInt(2000) + 1;
     FixedBitSet b1 = new FixedBitSet(numBits);
     FixedBitSet b2 = new FixedBitSet(numBits);
     assertTrue(b1.equals(b2));
     assertTrue(b2.equals(b1));
     for(int iter=0;iter<10*RANDOM_MULTIPLIER;iter++) {
       int idx = random.nextInt(numBits);
       if (!b1.get(idx)) {
         b1.set(idx);
         assertFalse(b1.equals(b2));
         assertFalse(b2.equals(b1));
         b2.set(idx);
         assertTrue(b1.equals(b2));
         assertTrue(b2.equals(b1));
       }
     }

     // try different type of object
     assertFalse(b1.equals(new Object()));
   }

   public void testHashCodeEquals() {
     // This test can't handle numBits==0:
     final int numBits = random.nextInt(2000) + 1;
     FixedBitSet b1 = new FixedBitSet(numBits);
     FixedBitSet b2 = new FixedBitSet(numBits);
     assertTrue(b1.equals(b2));
     assertTrue(b2.equals(b1));
     for(int iter=0;iter<10*RANDOM_MULTIPLIER;iter++) {
       int idx = random.nextInt(numBits);
       if (!b1.get(idx)) {
         b1.set(idx);
         assertFalse(b1.equals(b2));
         assertFalse(b1.hashCode() == b2.hashCode());
         b2.set(idx);
         assertEquals(b1, b2);
         assertEquals(b1.hashCode(), b2.hashCode());
       }
     }
   }

   public void testSmallBitSets() {
     // Make sure size 0-10 bit sets are OK:
     for(int numBits=0;numBits<10;numBits++) {
       FixedBitSet b1 = new FixedBitSet(numBits);
       FixedBitSet b2 = new FixedBitSet(numBits);
       assertTrue(b1.equals(b2));
       assertEquals(b1.hashCode(), b2.hashCode());
       assertEquals(0, b1.cardinality());
       if (numBits > 0) {
         b1.set(0, numBits);
         assertEquals(numBits, b1.cardinality());
         b1.flip(0, numBits);
         assertEquals(0, b1.cardinality());
       }
     }
   }

   private FixedBitSet makeFixedBitSet(int[] a, int numBits) {
     FixedBitSet bs = new FixedBitSet(numBits);
     for (int e: a) {
       bs.set(e);
     }
     return bs;
   }

   private BitSet makeBitSet(int[] a) {
     BitSet bs = new BitSet();
     for (int e: a) {
       bs.set(e);
     }
     return bs;
   }

   private void checkPrevSetBitArray(int [] a, int numBits) {
     FixedBitSet obs = makeFixedBitSet(a, numBits);
     BitSet bs = makeBitSet(a);
     doPrevSetBit(bs, obs);
   }

   public void testPrevSetBit() {
     checkPrevSetBitArray(new int[] {}, 0);
     checkPrevSetBitArray(new int[] {0}, 1);
     checkPrevSetBitArray(new int[] {0,2}, 3);
   }
 }
	/**
	* Licensed to the Apache Software Foundation (ASF) under one or more
	* contributor license agreements. See the NOTICE file distributed with
	* this work for additional information regarding copyright ownership.
	* The ASF licenses this file to You under the Apache License, Version 2.0
	* (the "License"); you may not use this file except in compliance with
	* the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	package org.apache.lucene.util;

	import java.io.IOException;
	import java.util.BitSet;

	import org.apache.lucene.search.DocIdSetIterator;

	public class TestFixedBitSet extends LuceneTestCase {

	void doGet(BitSet a, FixedBitSet b) {
	int max = b.length();
	for (int i=0; i<max; i++) {
	if (a.get(i) != b.get(i)) {
	fail("mismatch: BitSet=["+i+"]="+a.get(i));
	}
	}
	}

	void doNextSetBit(BitSet a, FixedBitSet b) {
	int aa=-1,bb=-1;
	do {
	aa = a.nextSetBit(aa+1);
	bb = bb < b.length()-1 ? b.nextSetBit(bb+1) : -1;
	assertEquals(aa,bb);
	} while (aa>=0);
	}

	void doPrevSetBit(BitSet a, FixedBitSet b) {
	int aa = a.size() + random.nextInt(100);
	int bb = aa;
	do {
	// aa = a.prevSetBit(aa-1);
	aa--;
	while ((aa >= 0) && (! a.get(aa))) {
	aa--;
	}
	if (b.length() == 0) {
	bb = -1;
	} else if (bb > b.length()-1) {
	bb = b.prevSetBit(b.length()-1);
	} else if (bb < 1) {
	bb = -1;
	} else {
	bb = bb >= 1 ? b.prevSetBit(bb-1) : -1;
	}
	assertEquals(aa,bb);
	} while (aa>=0);
	}

	// test interleaving different FixedBitSetIterator.next()/skipTo()
	void doIterate(BitSet a, FixedBitSet b, int mode) throws IOException {
	if (mode==1) doIterate1(a, b);
	if (mode==2) doIterate2(a, b);
	}

	void doIterate1(BitSet a, FixedBitSet b) throws IOException {
	int aa=-1,bb=-1;
	DocIdSetIterator iterator = b.iterator();
	do {
	aa = a.nextSetBit(aa+1);
	bb = (bb < b.length() && random.nextBoolean()) ? iterator.nextDoc() : iterator.advance(bb + 1);
	assertEquals(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
	} while (aa>=0);
	}

	void doIterate2(BitSet a, FixedBitSet b) throws IOException {
	int aa=-1,bb=-1;
	DocIdSetIterator iterator = b.iterator();
	do {
	aa = a.nextSetBit(aa+1);
	bb = random.nextBoolean() ? iterator.nextDoc() : iterator.advance(bb + 1);
	assertEquals(aa == -1 ? DocIdSetIterator.NO_MORE_DOCS : aa, bb);
	} while (aa>=0);
	}

	void doRandomSets(int maxSize, int iter, int mode) throws IOException {
	BitSet a0=null;
	FixedBitSet b0=null;

	for (int i=0; i<iter; i++) {
	int sz = _TestUtil.nextInt(random, 2, maxSize);
	BitSet a = new BitSet(sz);
	FixedBitSet b = new FixedBitSet(sz);

	// test the various ways of setting bits
	if (sz>0) {
	int nOper = random.nextInt(sz);
	for (int j=0; j<nOper; j++) {
	int idx;

	idx = random.nextInt(sz);
	a.set(idx);
	b.set(idx);

	idx = random.nextInt(sz);
	a.clear(idx);
	b.clear(idx);

	idx = random.nextInt(sz);
	a.flip(idx);
	b.flip(idx, idx+1);

	idx = random.nextInt(sz);
	a.flip(idx);
	b.flip(idx, idx+1);

	boolean val2 = b.get(idx);
	boolean val = b.getAndSet(idx);
	assertTrue(val2 == val);
	assertTrue(b.get(idx));

	if (!val) b.clear(idx);
	assertTrue(b.get(idx) == val);
	}
	}

	// test that the various ways of accessing the bits are equivalent
	doGet(a,b);

	// test ranges, including possible extension
	int fromIndex, toIndex;
	fromIndex = random.nextInt(sz/2);
	toIndex = fromIndex + random.nextInt(sz - fromIndex);
	BitSet aa = (BitSet)a.clone(); aa.flip(fromIndex,toIndex);
	FixedBitSet bb = (FixedBitSet)b.clone(); bb.flip(fromIndex,toIndex);

	doIterate(aa,bb, mode); // a problem here is from flip or doIterate

	fromIndex = random.nextInt(sz/2);
	toIndex = fromIndex + random.nextInt(sz - fromIndex);
	aa = (BitSet)a.clone(); aa.clear(fromIndex,toIndex);
	bb = (FixedBitSet)b.clone(); bb.clear(fromIndex,toIndex);

	doNextSetBit(aa,bb); // a problem here is from clear() or nextSetBit

	doPrevSetBit(aa,bb);

	fromIndex = random.nextInt(sz/2);
	toIndex = fromIndex + random.nextInt(sz - fromIndex);
	aa = (BitSet)a.clone(); aa.set(fromIndex,toIndex);
	bb = (FixedBitSet)b.clone(); bb.set(fromIndex,toIndex);

	doNextSetBit(aa,bb); // a problem here is from set() or nextSetBit

	doPrevSetBit(aa,bb);

	if (b0 != null && b0.length() <= b.length()) {
	assertEquals(a.cardinality(), b.cardinality());

	BitSet a_or = (BitSet) a.clone();
	a_or.or(a0);

	FixedBitSet b_or = (FixedBitSet) b.clone();
	b_or.or(b0);

	assertEquals(a0.cardinality(), b0.cardinality());
	assertEquals(a_or.cardinality(), b_or.cardinality());

	doIterate(a_or, b_or, mode);
	}

	a0=a;
	b0=b;
	}
	}

	// large enough to flush obvious bugs, small enough to run in <.5 sec as part of a
	// larger testsuite.
	public void testSmall() throws IOException {
	doRandomSets(atLeast(1200), atLeast(1000), 1);
	doRandomSets(atLeast(1200), atLeast(1000), 2);
	}

	// uncomment to run a bigger test (~2 minutes).
	/*
	public void testBig() {
	doRandomSets(2000,200000, 1);
	doRandomSets(2000,200000, 2);
	}
	*/

	public void testEquals() {
	// This test can't handle numBits==0:
	final int numBits = random.nextInt(2000) + 1;
	FixedBitSet b1 = new FixedBitSet(numBits);
	FixedBitSet b2 = new FixedBitSet(numBits);
	assertTrue(b1.equals(b2));
	assertTrue(b2.equals(b1));
	for(int iter=0;iter<10*RANDOM_MULTIPLIER;iter++) {
	int idx = random.nextInt(numBits);
	if (!b1.get(idx)) {
	b1.set(idx);
	assertFalse(b1.equals(b2));
	assertFalse(b2.equals(b1));
	b2.set(idx);
	assertTrue(b1.equals(b2));
	assertTrue(b2.equals(b1));
	}
	}

	// try different type of object
	assertFalse(b1.equals(new Object()));
	}

	public void testHashCodeEquals() {
	// This test can't handle numBits==0:
	final int numBits = random.nextInt(2000) + 1;
	FixedBitSet b1 = new FixedBitSet(numBits);
	FixedBitSet b2 = new FixedBitSet(numBits);
	assertTrue(b1.equals(b2));
	assertTrue(b2.equals(b1));
	for(int iter=0;iter<10*RANDOM_MULTIPLIER;iter++) {
	int idx = random.nextInt(numBits);
	if (!b1.get(idx)) {
	b1.set(idx);
	assertFalse(b1.equals(b2));
	assertFalse(b1.hashCode() == b2.hashCode());
	b2.set(idx);
	assertEquals(b1, b2);
	assertEquals(b1.hashCode(), b2.hashCode());
	}
	}
	}

	public void testSmallBitSets() {
	// Make sure size 0-10 bit sets are OK:
	for(int numBits=0;numBits<10;numBits++) {
	FixedBitSet b1 = new FixedBitSet(numBits);
	FixedBitSet b2 = new FixedBitSet(numBits);
	assertTrue(b1.equals(b2));
	assertEquals(b1.hashCode(), b2.hashCode());
	assertEquals(0, b1.cardinality());
	if (numBits > 0) {
	b1.set(0, numBits);
	assertEquals(numBits, b1.cardinality());
	b1.flip(0, numBits);
	assertEquals(0, b1.cardinality());
	}
	}
	}

	private FixedBitSet makeFixedBitSet(int[] a, int numBits) {
	FixedBitSet bs = new FixedBitSet(numBits);
	for (int e: a) {
	bs.set(e);
	}
	return bs;
	}

	private BitSet makeBitSet(int[] a) {
	BitSet bs = new BitSet();
	for (int e: a) {
	bs.set(e);
	}
	return bs;
	}

	private void checkPrevSetBitArray(int [] a, int numBits) {
	FixedBitSet obs = makeFixedBitSet(a, numBits);
	BitSet bs = makeBitSet(a);
	doPrevSetBit(bs, obs);
	}

	public void testPrevSetBit() {
	checkPrevSetBitArray(new int[] {}, 0);
	checkPrevSetBitArray(new int[] {0}, 1);
	checkPrevSetBitArray(new int[] {0,2}, 3);
	}
	}