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;
+ }
+
}