You are viewing a plain text version of this content. The canonical link for it is here.
Posted to java-commits@lucene.apache.org by mi...@apache.org on 2009/04/16 16:29:27 UTC

svn commit: r765649 - in /lucene/java/trunk: CHANGES.txt src/java/org/apache/lucene/util/BitVector.java src/test/org/apache/lucene/util/TestBitVector.java

Author: mikemccand
Date: Thu Apr 16 14:29:26 2009
New Revision: 765649

URL: http://svn.apache.org/viewvc?rev=765649&view=rev
Log:
LUCENE-1605: add BitVector.subset

Modified:
    lucene/java/trunk/CHANGES.txt
    lucene/java/trunk/src/java/org/apache/lucene/util/BitVector.java
    lucene/java/trunk/src/test/org/apache/lucene/util/TestBitVector.java

Modified: lucene/java/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/java/trunk/CHANGES.txt?rev=765649&r1=765648&r2=765649&view=diff
==============================================================================
--- lucene/java/trunk/CHANGES.txt (original)
+++ lucene/java/trunk/CHANGES.txt Thu Apr 16 14:29:26 2009
@@ -285,6 +285,9 @@
     during rewrite (getTotalNumberOfTerms).  FilteredTermEnum is also
     more friendly to subclassing.  (Uwe Schindler via Mike McCandless)
 
+22. LUCENE-1605: Added BitVector.subset().  (Jeremy Volkman via Mike
+    McCandless)
+
 Optimizations
 
  1. LUCENE-1427: Fixed QueryWrapperFilter to not waste time computing

Modified: lucene/java/trunk/src/java/org/apache/lucene/util/BitVector.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/util/BitVector.java?rev=765649&r1=765648&r2=765649&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/util/BitVector.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/util/BitVector.java Thu Apr 16 14:29:26 2009
@@ -238,5 +238,30 @@
       n -= BYTE_COUNTS[bits[last] & 0xFF];
     }          
   }
-  
+
+  /**
+   * Retrieve a subset of this BitVector.
+   * 
+   * @param start
+   *            starting index, inclusive
+   * @param end
+   *            ending index, exclusive
+   * @return subset
+   */
+  public BitVector subset(int start, int end) {
+    if (start < 0 || end > size() || end < start)
+      throw new IndexOutOfBoundsException();
+    // Special case -- return empty vector is start == end
+    if (end == start) return new BitVector(0);
+    byte[] bits = new byte[((end - start - 1) >>> 3) + 1];
+    int s = start >>> 3;
+    for (int i = 0; i < bits.length; i++) {
+      int cur = 0xFF & this.bits[i + s];
+      int next = i + s + 1 >= this.bits.length ? 0 : 0xFF & this.bits[i + s + 1];
+      bits[i] = (byte) ((cur >>> (start & 7)) | ((next << (8 - (start & 7)))));
+    }
+    int bitsToClear = (bits.length * 8 - (end - start)) % 8;
+    bits[bits.length - 1] &= ~(0xFF << (8 - bitsToClear));
+    return new BitVector(bits, end - start);
+  }
 }

Modified: lucene/java/trunk/src/test/org/apache/lucene/util/TestBitVector.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/test/org/apache/lucene/util/TestBitVector.java?rev=765649&r1=765648&r2=765649&view=diff
==============================================================================
--- lucene/java/trunk/src/test/org/apache/lucene/util/TestBitVector.java (original)
+++ lucene/java/trunk/src/test/org/apache/lucene/util/TestBitVector.java Thu Apr 16 14:29:26 2009
@@ -218,4 +218,70 @@
         }
         return equal;
     }
+    
+    private static int[] subsetPattern = new int[] { 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1 };
+    
+    /**
+     * Tests BitVector.subset() against the above pattern
+     */
+    public void testSubset() {
+    	doTestSubset(0, 0);
+    	doTestSubset(0, 20);
+    	doTestSubset(0, 7);
+    	doTestSubset(0, 8);
+    	doTestSubset(0, 9);
+    	doTestSubset(0, 15);
+    	doTestSubset(0, 16);
+    	doTestSubset(0, 17);
+    	doTestSubset(1, 7);
+    	doTestSubset(1, 8);
+    	doTestSubset(1, 9);
+    	doTestSubset(1, 15);
+    	doTestSubset(1, 16);
+    	doTestSubset(1, 17);
+    	doTestSubset(2, 20);
+    	doTestSubset(3, 20);
+    	doTestSubset(4, 20);
+    	doTestSubset(5, 20);
+    	doTestSubset(6, 20);
+    	doTestSubset(7, 14);
+    	doTestSubset(7, 15);
+    	doTestSubset(7, 16);
+    	doTestSubset(8, 15);
+    	doTestSubset(9, 20);
+    	doTestSubset(10, 20);
+    	doTestSubset(11, 20);
+    	doTestSubset(12, 20);
+    	doTestSubset(13, 20);
+    }
+    
+    /**
+     * Compare a subset against the corresponding portion of the test pattern
+     */
+    private void doTestSubset(int start, int end) {
+    	BitVector full = createSubsetTestVector();
+    	BitVector subset = full.subset(start, end);
+    	assertEquals(end - start, subset.size());
+    	int count = 0;
+    	for (int i = start, j = 0; i < end; i++, j++) {
+    		if (subsetPattern[i] == 1) {
+    			count++;
+    			assertTrue(subset.get(j));
+    		} else {
+    			assertFalse(subset.get(j));
+    		}
+    	}
+    	assertEquals(count, subset.count());
+    }
+    
+    private BitVector createSubsetTestVector() {
+    	BitVector bv = new BitVector(subsetPattern.length);
+    	for (int i = 0; i < subsetPattern.length; i++) {
+    		if (subsetPattern[i] == 1) {
+    			bv.set(i);
+    		}
+    	}
+    	return bv;
+    }
+    
 }