Silly me... I had implemented an efficient HashDocSet.andNotSize(other), and the I realized that it's simply equivalent to this.size() - this.intersectionSize(other).
-Yonik On 6/10/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
Author: yonik Date: Sat Jun 10 19:18:38 2006 New Revision: 413399 URL: http://svn.apache.org/viewvc?rev=413399&view=rev Log: DocSet.andNot(),andNotSize() Modified: incubator/solr/trunk/CHANGES.txt incubator/solr/trunk/src/java/org/apache/solr/search/BitDocSet.java incubator/solr/trunk/src/java/org/apache/solr/search/DocSet.java incubator/solr/trunk/src/java/org/apache/solr/search/HashDocSet.java incubator/solr/trunk/src/test/org/apache/solr/search/DocSetPerf.java incubator/solr/trunk/src/test/org/apache/solr/search/TestDocSet.java Modified: incubator/solr/trunk/CHANGES.txt URL: http://svn.apache.org/viewvc/incubator/solr/trunk/CHANGES.txt?rev=413399&r1=413398&r2=413399&view=diff ============================================================================== --- incubator/solr/trunk/CHANGES.txt (original) +++ incubator/solr/trunk/CHANGES.txt Sat Jun 10 19:18:38 2006 @@ -17,6 +17,7 @@ 9. Added KeywordTokenizerFactory (hossman) 10. copyField accepts dynamicfield-like names as the source. (Darren Erik Vengroff via yonik, SOLR-21) +11. new DocSet.andNot(), DocSet.andNotSize() (yonik) Changes in runtime behavior 1. classes reorganized into different packages, package names changed to Apache Modified: incubator/solr/trunk/src/java/org/apache/solr/search/BitDocSet.java URL: http://svn.apache.org/viewvc/incubator/solr/trunk/src/java/org/apache/solr/search/BitDocSet.java?rev=413399&r1=413398&r2=413399&view=diff ============================================================================== --- incubator/solr/trunk/src/java/org/apache/solr/search/BitDocSet.java (original) +++ incubator/solr/trunk/src/java/org/apache/solr/search/BitDocSet.java Sat Jun 10 19:18:38 2006 @@ -143,6 +143,7 @@ return bits.get(doc); } + @Override public int intersectionSize(DocSet other) { if (other instanceof BitDocSet) { return (int)OpenBitSet.intersectionCount(this.bits, ((BitDocSet)other).bits); @@ -152,12 +153,25 @@ } } + @Override public int unionSize(DocSet other) { if (other instanceof BitDocSet) { return (int)OpenBitSet.unionCount(this.bits, ((BitDocSet)other).bits); } else { // they had better not call us back! return other.unionSize(this); + } + } + + @Override + public int andNotSize(DocSet other) { + if (other instanceof BitDocSet) { + // if we don't know our current size, this is faster than + // size - intersection_size + return (int)OpenBitSet.andNotCount(this.bits, ((BitDocSet)other).bits); + } else { + // use BaseDocSet's size-intersection_size + return super.andNotSize(other); } } Modified: incubator/solr/trunk/src/java/org/apache/solr/search/DocSet.java URL: http://svn.apache.org/viewvc/incubator/solr/trunk/src/java/org/apache/solr/search/DocSet.java?rev=413399&r1=413398&r2=413399&view=diff ============================================================================== --- incubator/solr/trunk/src/java/org/apache/solr/search/DocSet.java (original) +++ incubator/solr/trunk/src/java/org/apache/solr/search/DocSet.java Sat Jun 10 19:18:38 2006 @@ -124,6 +124,17 @@ */ public int unionSize(DocSet other); + /** + * Returns the documents in this set that are not in the other set. Neither set is modified - a new DocSet is + * created and returned. + * @return a DocSet representing this AND NOT other + */ + public DocSet andNot(DocSet other); + + /** + * Returns the number of documents in this set that are not in the other set. + */ + public int andNotSize(DocSet other); } /** A base class that may be usefull for implementing DocSets */ @@ -208,11 +219,20 @@ return intersection(other).size(); } - // TODO: do an efficient implementation + // subclasses have more efficient implementations public int unionSize(DocSet other) { return union(other).size(); } + public DocSet andNot(DocSet other) { + OpenBitSet newbits = (OpenBitSet)(this.getBits().clone()); + newbits.andNot(other.getBits()); + return new BitDocSet(newbits); + } + + public int andNotSize(DocSet other) { + return this.size() - this.intersectionSize(other); + } } Modified: incubator/solr/trunk/src/java/org/apache/solr/search/HashDocSet.java URL: http://svn.apache.org/viewvc/incubator/solr/trunk/src/java/org/apache/solr/search/HashDocSet.java?rev=413399&r1=413398&r2=413399&view=diff ============================================================================== --- incubator/solr/trunk/src/java/org/apache/solr/search/HashDocSet.java (original) +++ incubator/solr/trunk/src/java/org/apache/solr/search/HashDocSet.java Sat Jun 10 19:18:38 2006 @@ -278,7 +278,7 @@ public int unionSize(DocSet other) { if (other instanceof HashDocSet) { // set "a" to the smallest doc set for the most efficient - // intersection. + // union count. final HashDocSet a = size()<=other.size() ? this : (HashDocSet)other; final HashDocSet b = size()<=other.size() ? (HashDocSet)other : this; @@ -302,5 +302,6 @@ } } - + // don't implement andNotSize() on purpose... if one of the sets is a HashDocSet, + // its easier to get the intersection size and subtract (implementation in BaseDocSet) } Modified: incubator/solr/trunk/src/test/org/apache/solr/search/DocSetPerf.java URL: http://svn.apache.org/viewvc/incubator/solr/trunk/src/test/org/apache/solr/search/DocSetPerf.java?rev=413399&r1=413398&r2=413399&view=diff ============================================================================== --- incubator/solr/trunk/src/test/org/apache/solr/search/DocSetPerf.java (original) +++ incubator/solr/trunk/src/test/org/apache/solr/search/DocSetPerf.java Sat Jun 10 19:18:38 2006 @@ -14,7 +14,7 @@ * limitations under the License. */ -package org.apache.solr.search.test; +package org.apache.solr.search; import org.apache.solr.search.BitDocSet; import org.apache.solr.search.HashDocSet; Modified: incubator/solr/trunk/src/test/org/apache/solr/search/TestDocSet.java URL: http://svn.apache.org/viewvc/incubator/solr/trunk/src/test/org/apache/solr/search/TestDocSet.java?rev=413399&r1=413398&r2=413399&view=diff ============================================================================== --- incubator/solr/trunk/src/test/org/apache/solr/search/TestDocSet.java (original) +++ incubator/solr/trunk/src/test/org/apache/solr/search/TestDocSet.java Sat Jun 10 19:18:38 2006 @@ -64,14 +64,15 @@ OpenBitSet a_and = (OpenBitSet)a1.clone(); a_and.and(a2); OpenBitSet a_or = (OpenBitSet)a1.clone(); a_or.or(a2); // OpenBitSet a_xor = (OpenBitSet)a1.clone(); a_xor.xor(a2); - // OpenBitSet a_andn = (OpenBitSet)a1.clone(); a_andn.andNot(a2); + OpenBitSet a_andn = (OpenBitSet)a1.clone(); a_andn.andNot(a2); checkEqual(a_and, b1.intersection(b2)); checkEqual(a_or, b1.union(b2)); + checkEqual(a_andn, b1.andNot(b2)); assertEquals(a_and.cardinality(), b1.intersectionSize(b2)); assertEquals(a_or.cardinality(), b1.unionSize(b2)); - + assertEquals(a_andn.cardinality(), b1.andNotSize(b2)); }
