lucene-java-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From busc...@apache.org
Subject svn commit: r617859 [1/2] - in /lucene/java/trunk: ./ contrib/miscellaneous/src/test/org/apache/lucene/misc/ contrib/xml-query-parser/src/java/org/apache/lucene/xmlparser/builders/ src/java/org/apache/lucene/search/ src/java/org/apache/lucene/util/ src...
Date Sat, 02 Feb 2008 19:04:09 GMT
Author: buschmi
Date: Sat Feb  2 11:04:03 2008
New Revision: 617859

URL: http://svn.apache.org/viewvc?rev=617859&view=rev
Log:
LUCENE-584: Changed Filter API to return a DocIdSet instead of a java.util.BitSet. This allows using more efficient data structures for Filters and makes them more flexible.

Added:
    lucene/java/trunk/src/java/org/apache/lucene/search/DocIdSet.java   (with props)
    lucene/java/trunk/src/java/org/apache/lucene/search/DocIdSetIterator.java   (with props)
    lucene/java/trunk/src/java/org/apache/lucene/util/BitUtil.java   (with props)
    lucene/java/trunk/src/java/org/apache/lucene/util/DocIdBitSet.java   (with props)
    lucene/java/trunk/src/java/org/apache/lucene/util/OpenBitSet.java   (with props)
    lucene/java/trunk/src/java/org/apache/lucene/util/OpenBitSetIterator.java   (with props)
    lucene/java/trunk/src/java/org/apache/lucene/util/SortedVIntList.java   (with props)
    lucene/java/trunk/src/test/org/apache/lucene/util/TestOpenBitSet.java   (with props)
    lucene/java/trunk/src/test/org/apache/lucene/util/TestSortedVIntList.java   (with props)
Modified:
    lucene/java/trunk/CHANGES.txt
    lucene/java/trunk/contrib/miscellaneous/src/test/org/apache/lucene/misc/ChainedFilterTest.java
    lucene/java/trunk/contrib/xml-query-parser/src/java/org/apache/lucene/xmlparser/builders/CachedFilterBuilder.java
    lucene/java/trunk/src/java/org/apache/lucene/search/CachingSpanFilter.java
    lucene/java/trunk/src/java/org/apache/lucene/search/CachingWrapperFilter.java
    lucene/java/trunk/src/java/org/apache/lucene/search/ConstantScoreQuery.java
    lucene/java/trunk/src/java/org/apache/lucene/search/Filter.java
    lucene/java/trunk/src/java/org/apache/lucene/search/FilteredQuery.java
    lucene/java/trunk/src/java/org/apache/lucene/search/IndexSearcher.java
    lucene/java/trunk/src/java/org/apache/lucene/search/PrefixFilter.java
    lucene/java/trunk/src/java/org/apache/lucene/search/QueryWrapperFilter.java
    lucene/java/trunk/src/java/org/apache/lucene/search/RangeFilter.java
    lucene/java/trunk/src/java/org/apache/lucene/search/RemoteCachingWrapperFilter.java
    lucene/java/trunk/src/java/org/apache/lucene/search/Scorer.java
    lucene/java/trunk/src/java/org/apache/lucene/search/Searchable.java
    lucene/java/trunk/src/java/org/apache/lucene/search/Searcher.java
    lucene/java/trunk/src/java/org/apache/lucene/search/SpanFilter.java
    lucene/java/trunk/src/java/org/apache/lucene/search/SpanFilterResult.java
    lucene/java/trunk/src/java/org/apache/lucene/search/SpanQueryFilter.java
    lucene/java/trunk/src/test/org/apache/lucene/search/CachingWrapperFilterHelper.java
    lucene/java/trunk/src/test/org/apache/lucene/search/MockFilter.java
    lucene/java/trunk/src/test/org/apache/lucene/search/RemoteCachingWrapperFilterHelper.java
    lucene/java/trunk/src/test/org/apache/lucene/search/SingleDocTestFilter.java
    lucene/java/trunk/src/test/org/apache/lucene/search/TestCachingWrapperFilter.java
    lucene/java/trunk/src/test/org/apache/lucene/search/TestExplanations.java
    lucene/java/trunk/src/test/org/apache/lucene/search/TestFilteredQuery.java
    lucene/java/trunk/src/test/org/apache/lucene/search/TestRemoteCachingWrapperFilter.java
    lucene/java/trunk/src/test/org/apache/lucene/search/TestRemoteSearchable.java
    lucene/java/trunk/src/test/org/apache/lucene/search/TestScorerPerf.java
    lucene/java/trunk/src/test/org/apache/lucene/search/TestSort.java
    lucene/java/trunk/src/test/org/apache/lucene/search/TestSpanQueryFilter.java

Modified: lucene/java/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/java/trunk/CHANGES.txt?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/CHANGES.txt (original)
+++ lucene/java/trunk/CHANGES.txt Sat Feb  2 11:04:03 2008
@@ -15,12 +15,16 @@
  2. LUCENE-1150: Re-expose StandardTokenizer's constants publicly;
     this was accidentally lost with LUCENE-966.  (Nicolas Lalevée via
     Mike McCandless)
+	
+ 3. LUCENE-584: Changed Filter API to return a DocIdSet instead of a
+    java.util.BitSet. This allows using more efficient data structures
+    for Filters and makes them more flexible. (Paul Elschot, Michael Busch)
 
 Bug fixes
     
 New features
 
-1. LUCENE-1137: Added Token.set/getFlags() accessors for passing more information about a Token through the analysis
+ 1. LUCENE-1137: Added Token.set/getFlags() accessors for passing more information about a Token through the analysis
     process.  The flag is not indexed/stored and is thus only used by analysis.
 
  2. LUCENE-1147: Add -segment option to CheckIndex tool so you can
@@ -28,6 +32,12 @@
     McCandless)
 
  3. LUCENE-1045: Reopened this issue to add support for short and bytes. 
+ 
+ 4. LUCENE-584: Added new data structures to o.a.l.util, such as 
+    OpenBitSet and SortedVIntList. These extend DocIdSet and can 
+    directly be used for Filters with the new Filter API. Also changed
+    the core Filters to use OpenBitSet instead of java.util.BitSet.
+    (Paul Elschot, Michael Busch)
 
 Optimizations
 

Modified: lucene/java/trunk/contrib/miscellaneous/src/test/org/apache/lucene/misc/ChainedFilterTest.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/miscellaneous/src/test/org/apache/lucene/misc/ChainedFilterTest.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/contrib/miscellaneous/src/test/org/apache/lucene/misc/ChainedFilterTest.java (original)
+++ lucene/java/trunk/contrib/miscellaneous/src/test/org/apache/lucene/misc/ChainedFilterTest.java Sat Feb  2 11:04:03 2008
@@ -37,8 +37,8 @@
   private Query query;
   // private DateFilter dateFilter;   DateFilter was deprecated and removed
   private RangeFilter dateFilter;
-  private QueryFilter bobFilter;
-  private QueryFilter sueFilter;
+  private QueryWrapperFilter bobFilter;
+  private QueryWrapperFilter sueFilter;
 
   public void setUp() throws Exception {
     directory = new RAMDirectory();
@@ -74,9 +74,9 @@
     // just treat dates as strings and select the whole range for now...
     dateFilter = new RangeFilter("date","","ZZZZ",true,true);
 
-    bobFilter = new QueryFilter(
+    bobFilter = new QueryWrapperFilter(
         new TermQuery(new Term("owner", "bob")));
-    sueFilter = new QueryFilter(
+    sueFilter = new QueryWrapperFilter(
         new TermQuery(new Term("owner", "sue")));
   }
 

Modified: lucene/java/trunk/contrib/xml-query-parser/src/java/org/apache/lucene/xmlparser/builders/CachedFilterBuilder.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/xml-query-parser/src/java/org/apache/lucene/xmlparser/builders/CachedFilterBuilder.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/contrib/xml-query-parser/src/java/org/apache/lucene/xmlparser/builders/CachedFilterBuilder.java (original)
+++ lucene/java/trunk/contrib/xml-query-parser/src/java/org/apache/lucene/xmlparser/builders/CachedFilterBuilder.java Sat Feb  2 11:04:03 2008
@@ -8,7 +8,7 @@
 import org.apache.lucene.search.CachingWrapperFilter;
 import org.apache.lucene.search.Filter;
 import org.apache.lucene.search.Query;
-import org.apache.lucene.search.QueryFilter;
+import org.apache.lucene.search.QueryWrapperFilter;
 import org.apache.lucene.xmlparser.DOMUtils;
 import org.apache.lucene.xmlparser.FilterBuilder;
 import org.apache.lucene.xmlparser.FilterBuilderFactory;
@@ -105,7 +105,7 @@
 		//cache miss
 		if (qb != null)
 		{
-			cachedFilter = new QueryFilter(q);
+			cachedFilter = new QueryWrapperFilter(q);
 		} else
 		{
 			cachedFilter = new CachingWrapperFilter(f);

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/CachingSpanFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/CachingSpanFilter.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/CachingSpanFilter.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/CachingSpanFilter.java Sat Feb  2 11:04:03 2008
@@ -43,11 +43,19 @@
     this.filter = filter;
   }
 
+  /**
+   * @deprecated Use {@link #getDocIdSet(IndexReader)} instead.
+   */
   public BitSet bits(IndexReader reader) throws IOException {
     SpanFilterResult result = getCachedResult(reader);
     return result != null ? result.getBits() : null;
   }
-
+  
+  public DocIdSet getDocIdSet(IndexReader reader) throws IOException {
+    SpanFilterResult result = getCachedResult(reader);
+    return result != null ? result.getDocIdSet() : null;
+  }
+  
   private SpanFilterResult getCachedResult(IndexReader reader) throws IOException {
     SpanFilterResult result = null;
     if (cache == null) {

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/CachingWrapperFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/CachingWrapperFilter.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/CachingWrapperFilter.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/CachingWrapperFilter.java Sat Feb  2 11:04:03 2008
@@ -43,6 +43,9 @@
     this.filter = filter;
   }
 
+  /**
+   * @deprecated Use {@link #getDocIdSet(IndexReader)} instead.
+   */
   public BitSet bits(IndexReader reader) throws IOException {
     if (cache == null) {
       cache = new WeakHashMap();
@@ -62,6 +65,28 @@
     }
 
     return bits;
+  }
+  
+  public DocIdSet getDocIdSet(IndexReader reader) throws IOException {
+    if (cache == null) {
+      cache = new WeakHashMap();
+    }
+
+    synchronized (cache) {  // check cache
+      DocIdSet cached = (DocIdSet) cache.get(reader);
+      if (cached != null) {
+        return cached;
+      }
+    }
+
+    final DocIdSet docIdSet = filter.getDocIdSet(reader);
+
+    synchronized (cache) {  // update cache
+      cache.put(reader, docIdSet);
+    }
+
+    return docIdSet;
+    
   }
 
   public String toString() {

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/ConstantScoreQuery.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/ConstantScoreQuery.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/ConstantScoreQuery.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/ConstantScoreQuery.java Sat Feb  2 11:04:03 2008
@@ -85,7 +85,7 @@
     public Explanation explain(IndexReader reader, int doc) throws IOException {
 
       ConstantScorer cs = (ConstantScorer)scorer(reader);
-      boolean exists = cs.bits.get(doc);
+      boolean exists = cs.docIdSetIterator.skipTo(doc) && (cs.docIdSetIterator.doc() == doc);
 
       ComplexExplanation result = new ComplexExplanation();
 
@@ -107,23 +107,22 @@
   }
 
   protected class ConstantScorer extends Scorer {
-    final BitSet bits;
+    final DocIdSetIterator docIdSetIterator;
     final float theScore;
     int doc=-1;
 
     public ConstantScorer(Similarity similarity, IndexReader reader, Weight w) throws IOException {
       super(similarity);
       theScore = w.getValue();
-      bits = filter.bits(reader);
+      docIdSetIterator = filter.getDocIdSet(reader).iterator();
     }
 
     public boolean next() throws IOException {
-      doc = bits.nextSetBit(doc+1);
-      return doc >= 0;
+      return docIdSetIterator.next();
     }
 
     public int doc() {
-      return doc;
+      return docIdSetIterator.doc();
     }
 
     public float score() throws IOException {
@@ -131,8 +130,7 @@
     }
 
     public boolean skipTo(int target) throws IOException {
-      doc = bits.nextSetBit(target);  // requires JDK 1.4
-      return doc >= 0;
+      return docIdSetIterator.skipTo(target);
     }
 
     public Explanation explain(int doc) throws IOException {
@@ -168,5 +166,6 @@
   }
 
 }
+
 
 

Added: lucene/java/trunk/src/java/org/apache/lucene/search/DocIdSet.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/DocIdSet.java?rev=617859&view=auto
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/DocIdSet.java (added)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/DocIdSet.java Sat Feb  2 11:04:03 2008
@@ -0,0 +1,27 @@
+package org.apache.lucene.search;
+
+/**
+ * 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.
+ */
+
+
+/**
+ * A DocIdSet contains a set of doc ids. Implementing classes must provide
+ * a {@link DocIdSetIterator} to access the set. 
+ */
+public abstract class DocIdSet {
+	public abstract DocIdSetIterator iterator();
+}

Propchange: lucene/java/trunk/src/java/org/apache/lucene/search/DocIdSet.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/java/trunk/src/java/org/apache/lucene/search/DocIdSetIterator.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/DocIdSetIterator.java?rev=617859&view=auto
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/DocIdSetIterator.java (added)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/DocIdSetIterator.java Sat Feb  2 11:04:03 2008
@@ -0,0 +1,49 @@
+package org.apache.lucene.search;
+
+/**
+ * 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.
+ */
+
+import java.io.IOException;
+
+/**
+ * This abstract class defines methods to iterate over a set of
+ * non-decreasing doc ids.
+ */
+public abstract class DocIdSetIterator {
+    /** Returns the current document number.  <p> This is invalid until {@link
+    #next()} is called for the first time.*/
+    public abstract int doc();
+    
+    /** Moves to the next docId in the set. Returns true, iff
+     * there is such a docId. */
+    public abstract boolean next() throws IOException;
+    
+    /** Skips entries to the first beyond the current whose document number is
+     * greater than or equal to <i>target</i>. <p>Returns true iff there is such
+     * an entry.  <p>Behaves as if written: <pre>
+     *   boolean skipTo(int target) {
+     *     do {
+     *       if (!next())
+     *         return false;
+     *     } while (target > doc());
+     *     return true;
+     *   }
+     * </pre>
+     * Some implementations are considerably more efficient than that.
+     */
+    public abstract boolean skipTo(int target) throws IOException;
+}

Propchange: lucene/java/trunk/src/java/org/apache/lucene/search/DocIdSetIterator.java
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/Filter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/Filter.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/Filter.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/Filter.java Sat Feb  2 11:04:03 2008
@@ -20,11 +20,32 @@
 import java.util.BitSet;
 import java.io.IOException;
 import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.util.DocIdBitSet;
 
-/** Abstract base class providing a mechanism to restrict searches to a subset
- of an index. */
+/** Abstract base class providing a mechanism to use a subset of an index
+ *  for restriction or permission of index search results.
+ *  <p>
+ *  <b>Note:</b> In Lucene 3.0 {@link #bits(IndexReader)} will be removed
+ *  and {@link #getDocIdSet(IndexReader)} will be defined as abstract.
+ *  All implementing classes must therefore implement {@link #getDocIdSet(IndexReader)}
+ *  in order to work with Lucene 3.0.
+ */
 public abstract class Filter implements java.io.Serializable {
-  /** Returns a BitSet with true for documents which should be permitted in
-    search results, and false for those that should not. */
-  public abstract BitSet bits(IndexReader reader) throws IOException;
+  /**
+   * @return A BitSet with true for documents which should be permitted in
+   * search results, and false for those that should not.
+   * @deprecated Use {@link #getDocIdSet(IndexReader)} instead.
+   */
+  public BitSet bits(IndexReader reader) throws IOException {
+    return null;
+  }
+	
+  /**
+   * @return a DocIdSet that provides the documents which should be
+   * permitted or prohibited in search results.
+   * @see DocIdBitSet
+   */
+  public DocIdSet getDocIdSet(IndexReader reader) throws IOException {
+    return new DocIdBitSet(bits(reader));
+  }
 }

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/FilteredQuery.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/FilteredQuery.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/FilteredQuery.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/FilteredQuery.java Sat Feb  2 11:04:03 2008
@@ -21,7 +21,6 @@
 import org.apache.lucene.util.ToStringUtils;
 
 import java.io.IOException;
-import java.util.BitSet;
 import java.util.Set;
 
 
@@ -47,7 +46,7 @@
 
   /**
    * Constructs a new query which applies a filter to the results of the original query.
-   * Filter.bits() will be called every time this query is used in a search.
+   * Filter.getDocIdSet() will be called every time this query is used in a search.
    * @param query  Query to be filtered, cannot be <code>null</code>.
    * @param filter Filter to apply to query results, cannot be <code>null</code>.
    */
@@ -86,13 +85,15 @@
           inner.addDetail(preBoost);
         }
         Filter f = FilteredQuery.this.filter;
-        BitSet matches = f.bits(ir);
-        if (matches.get(i))
+        DocIdSetIterator docIdSetIterator = f.getDocIdSet(ir).iterator();
+        if (docIdSetIterator.skipTo(i) && (docIdSetIterator.doc() == i)) {
           return inner;
-        Explanation result = new Explanation
-          (0.0f, "failure to match filter: " + f.toString());
-        result.addDetail(inner);
-        return result;
+        } else {
+          Explanation result = new Explanation
+            (0.0f, "failure to match filter: " + f.toString());
+          result.addDetail(inner);
+          return result;
+        }
       }
 
       // return this query
@@ -100,50 +101,49 @@
 
       // return a filtering scorer
        public Scorer scorer (IndexReader indexReader) throws IOException {
-        final Scorer scorer = weight.scorer (indexReader);
-        final BitSet bitset = filter.bits (indexReader);
-        return new Scorer (similarity) {
+        final Scorer scorer = weight.scorer(indexReader);
+        final DocIdSetIterator docIdSetIterator = filter.getDocIdSet(indexReader).iterator();
 
-          public boolean next() throws IOException {
-            do {
-              if (! scorer.next()) {
+        return new Scorer(similarity) {
+
+          private boolean advanceToCommon() throws IOException {
+            while (scorer.doc() != docIdSetIterator.doc()) {
+              if (scorer.doc() < docIdSetIterator.doc()) {
+                if (!scorer.skipTo(docIdSetIterator.doc())) {
+                  return false;
+                }
+              } else if (!docIdSetIterator.skipTo(scorer.doc())) {
                 return false;
               }
-            } while (! bitset.get(scorer.doc()));
-            /* When skipTo() is allowed on scorer it should be used here
-             * in combination with bitset.nextSetBit(...)
-             * See the while loop in skipTo() below.
-             */
+            }
             return true;
           }
+
+          public boolean next() throws IOException {
+            return docIdSetIterator.next() && scorer.next() && advanceToCommon();
+          }
+
           public int doc() { return scorer.doc(); }
 
           public boolean skipTo(int i) throws IOException {
-            if (! scorer.skipTo(i)) {
-              return false;
-            }
-            while (! bitset.get(scorer.doc())) {
-              int nextFiltered = bitset.nextSetBit(scorer.doc() + 1);
-              if (nextFiltered == -1) {
-                return false;
-              } else if (! scorer.skipTo(nextFiltered)) {
-                return false;
-              }
-            }
-            return true;
-           }
+            return docIdSetIterator.skipTo(i)
+                && scorer.skipTo(docIdSetIterator.doc())
+                && advanceToCommon();
+          }
 
           public float score() throws IOException { return getBoost() * scorer.score(); }
 
           // add an explanation about whether the document was filtered
           public Explanation explain (int i) throws IOException {
-            Explanation exp = scorer.explain (i);
-            exp.setValue(getBoost() * exp.getValue());
+            Explanation exp = scorer.explain(i);
             
-            if (bitset.get(i))
+            if (docIdSetIterator.skipTo(i) && (docIdSetIterator.doc() == i)) {
               exp.setDescription ("allowed by filter: "+exp.getDescription());
-            else
+              exp.setValue(getBoost() * exp.getValue());
+            } else {
               exp.setDescription ("removed by filter: "+exp.getDescription());
+              exp.setValue(0.0f);
+            }
             return exp;
           }
         };

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/IndexSearcher.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/IndexSearcher.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/IndexSearcher.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/IndexSearcher.java Sat Feb  2 11:04:03 2008
@@ -128,22 +128,33 @@
   // inherit javadoc
   public void search(Weight weight, Filter filter,
                      final HitCollector results) throws IOException {
-    HitCollector collector = results;
-    if (filter != null) {
-      final BitSet bits = filter.bits(reader);
-      collector = new HitCollector() {
-          public final void collect(int doc, float score) {
-            if (bits.get(doc)) {                  // skip docs not in bits
-              results.collect(doc, score);
-            }
-          }
-        };
-    }
 
     Scorer scorer = weight.scorer(reader);
     if (scorer == null)
       return;
-    scorer.score(collector);
+
+    if (filter == null) {
+      scorer.score(results);
+      return;
+    }
+
+    DocIdSetIterator docIdSetIterator = filter.getDocIdSet(reader).iterator(); // CHECKME: use ConjunctionScorer here?
+    boolean more = docIdSetIterator.next();
+    while (more) {
+      int filterDocId = docIdSetIterator.doc();
+      if (! scorer.skipTo(filterDocId)) {
+        more = false;
+      } else {
+        int scorerDocId = scorer.doc();
+        if (scorerDocId == filterDocId) { // permitted by filter
+          results.collect(scorerDocId, scorer.score());
+          more = docIdSetIterator.skipTo(scorerDocId + 1);
+        } else {
+          more = docIdSetIterator.skipTo(scorerDocId);
+        }
+      }
+    }
+
   }
 
   public Query rewrite(Query original) throws IOException {

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/PrefixFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/PrefixFilter.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/PrefixFilter.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/PrefixFilter.java Sat Feb  2 11:04:03 2008
@@ -18,6 +18,7 @@
  */
 
 import org.apache.lucene.search.Filter;
+import org.apache.lucene.util.OpenBitSet;
 import org.apache.lucene.index.Term;
 import org.apache.lucene.index.IndexReader;
 import org.apache.lucene.index.TermEnum;
@@ -39,6 +40,9 @@
 
   public Term getPrefix() { return prefix; }
 
+  /**
+   * @deprecated Use {@link #getDocIdSet(IndexReader)} instead.
+   */  
   public BitSet bits(IndexReader reader) throws IOException {
     final BitSet bitSet = new BitSet(reader.maxDoc());
     new PrefixGenerator(prefix) {
@@ -48,6 +52,16 @@
     }.generate(reader);
     return bitSet;
   }
+  
+  public DocIdSet getDocIdSet(IndexReader reader) throws IOException {
+    final OpenBitSet bitSet = new OpenBitSet(reader.maxDoc());
+    new PrefixGenerator(prefix) {
+      public void handleDoc(int doc) {
+        bitSet.set(doc);
+      }
+    }.generate(reader);
+    return bitSet;
+  }
 
   /** Prints a user-readable version of this query. */
   public String toString () {
@@ -103,5 +117,6 @@
     }
   }
 }
+
 
 

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/QueryWrapperFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/QueryWrapperFilter.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/QueryWrapperFilter.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/QueryWrapperFilter.java Sat Feb  2 11:04:03 2008
@@ -21,6 +21,7 @@
 import java.util.BitSet;
 
 import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.util.OpenBitSet;
 
 /** 
  * Constrains search results to only match those which also match a provided
@@ -44,8 +45,22 @@
     this.query = query;
   }
 
+  /**
+   * @deprecated Use {@link #getDocIdSet(IndexReader)} instead.
+   */
   public BitSet bits(IndexReader reader) throws IOException {
     final BitSet bits = new BitSet(reader.maxDoc());
+
+    new IndexSearcher(reader).search(query, new HitCollector() {
+      public final void collect(int doc, float score) {
+        bits.set(doc);  // set bit for hit
+      }
+    });
+    return bits;
+  }
+  
+  public DocIdSet getDocIdSet(IndexReader reader) throws IOException {
+    final OpenBitSet bits = new OpenBitSet(reader.maxDoc());
 
     new IndexSearcher(reader).search(query, new HitCollector() {
       public final void collect(int doc, float score) {

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/RangeFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/RangeFilter.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/RangeFilter.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/RangeFilter.java Sat Feb  2 11:04:03 2008
@@ -21,6 +21,7 @@
 import org.apache.lucene.index.Term;
 import org.apache.lucene.index.TermDocs;
 import org.apache.lucene.index.TermEnum;
+import org.apache.lucene.util.OpenBitSet;
 
 import java.io.IOException;
 import java.util.BitSet;
@@ -94,9 +95,72 @@
      * Returns a BitSet with true for documents which should be
      * permitted in search results, and false for those that should
      * not.
+     * @deprecated Use {@link #getDocIdSet(IndexReader)} instead.
      */
     public BitSet bits(IndexReader reader) throws IOException {
         BitSet bits = new BitSet(reader.maxDoc());
+        TermEnum enumerator =
+            (null != lowerTerm
+             ? reader.terms(new Term(fieldName, lowerTerm))
+             : reader.terms(new Term(fieldName,"")));
+        
+        try {
+            
+            if (enumerator.term() == null) {
+                return bits;
+            }
+            
+            boolean checkLower = false;
+            if (!includeLower) // make adjustments to set to exclusive
+                checkLower = true;
+        
+            TermDocs termDocs = reader.termDocs();
+            try {
+                
+                do {
+                    Term term = enumerator.term();
+                    if (term != null && term.field().equals(fieldName)) {
+                        if (!checkLower || null==lowerTerm || term.text().compareTo(lowerTerm) > 0) {
+                            checkLower = false;
+                            if (upperTerm != null) {
+                                int compare = upperTerm.compareTo(term.text());
+                                /* if beyond the upper term, or is exclusive and
+                                 * this is equal to the upper term, break out */
+                                if ((compare < 0) ||
+                                    (!includeUpper && compare==0)) {
+                                    break;
+                                }
+                            }
+                            /* we have a good term, find the docs */
+                            
+                            termDocs.seek(enumerator.term());
+                            while (termDocs.next()) {
+                                bits.set(termDocs.doc());
+                            }
+                        }
+                    } else {
+                        break;
+                    }
+                }
+                while (enumerator.next());
+                
+            } finally {
+                termDocs.close();
+            }
+        } finally {
+            enumerator.close();
+        }
+
+        return bits;
+    }
+    
+    /**
+     * Returns a DocIdSet with documents that should be
+     * permitted in search results.
+     */
+    public DocIdSet getDocIdSet(IndexReader reader) throws IOException {
+        OpenBitSet bits = new OpenBitSet(reader.maxDoc());
+        
         TermEnum enumerator =
             (null != lowerTerm
              ? reader.terms(new Term(fieldName, lowerTerm))

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/RemoteCachingWrapperFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/RemoteCachingWrapperFilter.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/RemoteCachingWrapperFilter.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/RemoteCachingWrapperFilter.java Sat Feb  2 11:04:03 2008
@@ -50,9 +50,21 @@
    * searcher side of a remote connection.
    * @param reader the index reader for the Filter
    * @return the bitset
+   * @deprecated Use {@link #getDocIdSet(IndexReader)} instead.
    */
   public BitSet bits(IndexReader reader) throws IOException {
     Filter cachedFilter = FilterManager.getInstance().getFilter(filter);
     return cachedFilter.bits(reader);
+  }
+  
+  /**
+   * Uses the {@link FilterManager} to keep the cache for a filter on the 
+   * searcher side of a remote connection.
+   * @param reader the index reader for the Filter
+   * @return the DocIdSet
+   */
+  public DocIdSet getDocIdSet(IndexReader reader) throws IOException {
+    Filter cachedFilter = FilterManager.getInstance().getFilter(filter);
+    return cachedFilter.getDocIdSet(reader);
   }
 }

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/Scorer.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/Scorer.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/Scorer.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/Scorer.java Sat Feb  2 11:04:03 2008
@@ -33,7 +33,7 @@
  * </p>
  * @see BooleanQuery#setAllowDocsOutOfOrder
  */
-public abstract class Scorer {
+public abstract class Scorer extends DocIdSetIterator {
   private Similarity similarity;
 
   /** Constructs a Scorer.
@@ -76,64 +76,11 @@
     return true;
   }
 
-  /**
-   * Advances to the document matching this Scorer with the lowest doc Id
-   * greater than the current value of {@link #doc()} (or to the matching
-   * document with the lowest doc Id if next has never been called on
-   * this Scorer).
-   *
-   * <p>
-   * When this method is used the {@link #explain(int)} method should not
-   * be used.
-   * </p>
-   *
-   * @return true iff there is another document matching the query.
-   * @see BooleanQuery#setAllowDocsOutOfOrder
-   */
-  public abstract boolean next() throws IOException;
-
-  /** Returns the current document number matching the query.
-   * Initially invalid, until {@link #next()} is called the first time.
-   */
-  public abstract int doc();
-
   /** Returns the score of the current document matching the query.
    * Initially invalid, until {@link #next()} or {@link #skipTo(int)}
    * is called the first time.
    */
   public abstract float score() throws IOException;
-
-  /**
-   * Skips to the document matching this Scorer with the lowest doc Id
-   * greater than or equal to a given target.
-   *
-   * <p>
-   * The behavior of this method is undefined if the target specified is
-   * less than or equal to the current value of {@link #doc()}.
-   * <p>
-   * Behaves as if written:
-   * <pre>
-   *   boolean skipTo(int target) {
-   *     do {
-   *       if (!next())
-   * 	     return false;
-   *     } while (target > doc());
-   *     return true;
-   *   }
-   * </pre>
-   * Most implementations are considerably more efficient than that.
-   * </p>
-   *
-   * <p>
-   * When this method is used the {@link #explain(int)} method should not
-   * be used.
-   * </p>
-   *
-   * @param target The target document number.
-   * @return true iff there is such a match.
-   * @see BooleanQuery#setAllowDocsOutOfOrder
-   */
-  public abstract boolean skipTo(int target) throws IOException;
 
   /** Returns an explanation of the score for a document.
    * <br>When this method is used, the {@link #next()}, {@link #skipTo(int)} and

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/Searchable.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/Searchable.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/Searchable.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/Searchable.java Sat Feb  2 11:04:03 2008
@@ -48,7 +48,7 @@
    * non-high-scoring hits.
    *
    * @param weight to match documents
-   * @param filter if non-null, a bitset used to eliminate some documents
+   * @param filter if non-null, used to permit documents to be collected.
    * @param results to receive hits
    * @throws BooleanQuery.TooManyClauses
    */

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/Searcher.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/Searcher.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/Searcher.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/Searcher.java Sat Feb  2 11:04:03 2008
@@ -109,7 +109,7 @@
    * non-high-scoring hits.
    *
    * @param query to match documents
-   * @param filter if non-null, a bitset used to eliminate some documents
+   * @param filter if non-null, used to permit documents to be collected.
    * @param results to receive hits
    * @throws BooleanQuery.TooManyClauses
    */

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/SpanFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/SpanFilter.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/SpanFilter.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/SpanFilter.java Sat Feb  2 11:04:03 2008
@@ -30,7 +30,7 @@
 public abstract class SpanFilter extends Filter{
   /** Returns a SpanFilterResult with true for documents which should be permitted in
     search results, and false for those that should not and Spans for where the true docs match.
-   * @param reader The {@link org.apache.lucene.index.IndexReader} to load position and bitset information from
+   * @param reader The {@link org.apache.lucene.index.IndexReader} to load position and DocIdSet information from
    * @return A {@link SpanFilterResult}
    * @throws java.io.IOException if there was an issue accessing the necessary information
    * */

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/SpanFilterResult.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/SpanFilterResult.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/SpanFilterResult.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/SpanFilterResult.java Sat Feb  2 11:04:03 2008
@@ -28,19 +28,33 @@
  *
  **/
 public class SpanFilterResult {
+  /** @deprecated */
   private BitSet bits;
+  
+  private DocIdSet docIdSet;
   private List positions;//Spans spans;
 
   /**
    *
    * @param bits The bits for the Filter
    * @param positions A List of {@link org.apache.lucene.search.SpanFilterResult.PositionInfo} objects
+   * @deprecated Use {@link #SpanFilterResult(DocIdSet, List)} instead
    */
   public SpanFilterResult(BitSet bits, List positions) {
     this.bits = bits;
     this.positions = positions;
   }
-
+  
+  /**
+  *
+  * @param docIdSet The DocIdSet for the Filter
+  * @param positions A List of {@link org.apache.lucene.search.SpanFilterResult.PositionInfo} objects
+  */
+  public SpanFilterResult(DocIdSet docIdSet, List positions) {
+    this.docIdSet = docIdSet;
+    this.positions = positions;
+  }
+  
   /**
    * The first entry in the array corresponds to the first "on" bit.
    * Entries are increasing by document order
@@ -50,11 +64,17 @@
     return positions;
   }
 
+  /** 
+   * @deprecated Use {@link #getDocIdSet()}
+   */
   public BitSet getBits() {
     return bits;
   }
-
   
+  /** Returns the docIdSet */
+  public DocIdSet getDocIdSet() {
+    return docIdSet;
+  }
 
   public static class PositionInfo {
     private int doc;
@@ -113,5 +133,6 @@
 
   }
 }
+
 
 

Modified: lucene/java/trunk/src/java/org/apache/lucene/search/SpanQueryFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/search/SpanQueryFilter.java?rev=617859&r1=617858&r2=617859&view=diff
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/search/SpanQueryFilter.java (original)
+++ lucene/java/trunk/src/java/org/apache/lucene/search/SpanQueryFilter.java Sat Feb  2 11:04:03 2008
@@ -19,6 +19,7 @@
 import org.apache.lucene.index.IndexReader;
 import org.apache.lucene.search.spans.SpanQuery;
 import org.apache.lucene.search.spans.Spans;
+import org.apache.lucene.util.OpenBitSet;
 
 import java.io.IOException;
 import java.util.ArrayList;
@@ -54,15 +55,14 @@
     this.query = query;
   }
 
-  public BitSet bits(IndexReader reader) throws IOException {
+  public DocIdSet getDocIdSet(IndexReader reader) throws IOException {
     SpanFilterResult result = bitSpans(reader);
-    return result.getBits();
+    return result.getDocIdSet();
   }
 
-
   public SpanFilterResult bitSpans(IndexReader reader) throws IOException {
 
-    final BitSet bits = new BitSet(reader.maxDoc());
+    final OpenBitSet bits = new OpenBitSet(reader.maxDoc());
     Spans spans = query.getSpans(reader);
     List tmp = new ArrayList(20);
     int currentDoc = -1;

Added: lucene/java/trunk/src/java/org/apache/lucene/util/BitUtil.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/util/BitUtil.java?rev=617859&view=auto
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/util/BitUtil.java (added)
+++ lucene/java/trunk/src/java/org/apache/lucene/util/BitUtil.java Sat Feb  2 11:04:03 2008
@@ -0,0 +1,799 @@
+/**
+ * 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; // from org.apache.solr.util rev 555343
+
+/**  A variety of high efficiencly bit twiddling routines.
+ *
+ * @version $Id$
+ */
+public class BitUtil {
+
+  /** Returns the number of bits set in the long */
+  public static int pop(long x) {
+  /* Hacker's Delight 32 bit pop function:
+   * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
+   *
+  int pop(unsigned x) {
+     x = x - ((x >> 1) & 0x55555555);
+     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
+     x = (x + (x >> 4)) & 0x0F0F0F0F;
+     x = x + (x >> 8);
+     x = x + (x >> 16);
+     return x & 0x0000003F;
+    }
+  ***/
+
+    // 64 bit java version of the C function from above
+    x = x - ((x >>> 1) & 0x5555555555555555L);
+    x = (x & 0x3333333333333333L) + ((x >>>2 ) & 0x3333333333333333L);
+    x = (x + (x >>> 4)) & 0x0F0F0F0F0F0F0F0FL;
+    x = x + (x >>> 8);
+    x = x + (x >>> 16);
+    x = x + (x >>> 32);
+    return ((int)x) & 0x7F;
+  }
+
+  /*** Returns the number of set bits in an array of longs. */
+  public static long pop_array(long A[], int wordOffset, int numWords) {
+    /*
+    * Robert Harley and David Seal's bit counting algorithm, as documented
+    * in the revisions of Hacker's Delight
+    * http://www.hackersdelight.org/revisions.pdf
+    * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
+    *
+    * This function was adapted to Java, and extended to use 64 bit words.
+    * if only we had access to wider registers like SSE from java...
+    *
+    * This function can be transformed to compute the popcount of other functions
+    * on bitsets via something like this:
+    * sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
+    *
+    */
+    int n = wordOffset+numWords;
+    long tot=0, tot8=0;
+    long ones=0, twos=0, fours=0;
+
+    int i;
+    for (i = wordOffset; i <= n - 8; i+=8) {
+      /***  C macro from Hacker's Delight
+       #define CSA(h,l, a,b,c) \
+       {unsigned u = a ^ b; unsigned v = c; \
+       h = (a & b) | (u & v); l = u ^ v;}
+       ***/
+
+      long twosA,twosB,foursA,foursB,eights;
+
+      // CSA(twosA, ones, ones, A[i], A[i+1])
+      {
+        long b=A[i], c=A[i+1];
+        long u=ones ^ b;
+        twosA=(ones & b)|( u & c);
+        ones=u^c;
+      }
+      // CSA(twosB, ones, ones, A[i+2], A[i+3])
+      {
+        long b=A[i+2], c=A[i+3];
+        long u=ones^b;
+        twosB =(ones&b)|(u&c);
+        ones=u^c;
+      }
+      //CSA(foursA, twos, twos, twosA, twosB)
+      {
+        long u=twos^twosA;
+        foursA=(twos&twosA)|(u&twosB);
+        twos=u^twosB;
+      }
+      //CSA(twosA, ones, ones, A[i+4], A[i+5])
+      {
+        long b=A[i+4], c=A[i+5];
+        long u=ones^b;
+        twosA=(ones&b)|(u&c);
+        ones=u^c;
+      }
+      // CSA(twosB, ones, ones, A[i+6], A[i+7])
+      {
+        long b=A[i+6], c=A[i+7];
+        long u=ones^b;
+        twosB=(ones&b)|(u&c);
+        ones=u^c;
+      }
+      //CSA(foursB, twos, twos, twosA, twosB)
+      {
+        long u=twos^twosA;
+        foursB=(twos&twosA)|(u&twosB);
+        twos=u^twosB;
+      }
+
+      //CSA(eights, fours, fours, foursA, foursB)
+      {
+        long u=fours^foursA;
+        eights=(fours&foursA)|(u&foursB);
+        fours=u^foursB;
+      }
+      tot8 += pop(eights);
+    }
+
+    // handle trailing words in a binary-search manner...
+    // derived from the loop above by setting specific elements to 0.
+    // the original method in Hackers Delight used a simple for loop:
+    //   for (i = i; i < n; i++)      // Add in the last elements
+    //  tot = tot + pop(A[i]);
+
+    if (i<=n-4) {
+      long twosA, twosB, foursA, eights;
+      {
+        long b=A[i], c=A[i+1];
+        long u=ones ^ b;
+        twosA=(ones & b)|( u & c);
+        ones=u^c;
+      }
+      {
+        long b=A[i+2], c=A[i+3];
+        long u=ones^b;
+        twosB =(ones&b)|(u&c);
+        ones=u^c;
+      }
+      {
+        long u=twos^twosA;
+        foursA=(twos&twosA)|(u&twosB);
+        twos=u^twosB;
+      }
+      eights=fours&foursA;
+      fours=fours^foursA;
+
+      tot8 += pop(eights);
+      i+=4;
+    }
+
+    if (i<=n-2) {
+      long b=A[i], c=A[i+1];
+      long u=ones ^ b;
+      long twosA=(ones & b)|( u & c);
+      ones=u^c;
+
+      long foursA=twos&twosA;
+      twos=twos^twosA;
+
+      long eights=fours&foursA;
+      fours=fours^foursA;
+
+      tot8 += pop(eights);
+      i+=2;
+    }
+
+    if (i<n) {
+      tot += pop(A[i]);
+    }
+
+    tot += (pop(fours)<<2)
+            + (pop(twos)<<1)
+            + pop(ones)
+            + (tot8<<3);
+
+    return tot;
+  }
+
+  /** Returns the popcount or cardinality of the two sets after an intersection.
+   * Neither array is modified.
+   */
+  public static long pop_intersect(long A[], long B[], int wordOffset, int numWords) {
+    // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
+    int n = wordOffset+numWords;
+    long tot=0, tot8=0;
+    long ones=0, twos=0, fours=0;
+
+    int i;
+    for (i = wordOffset; i <= n - 8; i+=8) {
+      long twosA,twosB,foursA,foursB,eights;
+
+      // CSA(twosA, ones, ones, (A[i] & B[i]), (A[i+1] & B[i+1]))
+      {
+        long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
+        long u=ones ^ b;
+        twosA=(ones & b)|( u & c);
+        ones=u^c;
+      }
+      // CSA(twosB, ones, ones, (A[i+2] & B[i+2]), (A[i+3] & B[i+3]))
+      {
+        long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
+        long u=ones^b;
+        twosB =(ones&b)|(u&c);
+        ones=u^c;
+      }
+      //CSA(foursA, twos, twos, twosA, twosB)
+      {
+        long u=twos^twosA;
+        foursA=(twos&twosA)|(u&twosB);
+        twos=u^twosB;
+      }
+      //CSA(twosA, ones, ones, (A[i+4] & B[i+4]), (A[i+5] & B[i+5]))
+      {
+        long b=(A[i+4] & B[i+4]), c=(A[i+5] & B[i+5]);
+        long u=ones^b;
+        twosA=(ones&b)|(u&c);
+        ones=u^c;
+      }
+      // CSA(twosB, ones, ones, (A[i+6] & B[i+6]), (A[i+7] & B[i+7]))
+      {
+        long b=(A[i+6] & B[i+6]), c=(A[i+7] & B[i+7]);
+        long u=ones^b;
+        twosB=(ones&b)|(u&c);
+        ones=u^c;
+      }
+      //CSA(foursB, twos, twos, twosA, twosB)
+      {
+        long u=twos^twosA;
+        foursB=(twos&twosA)|(u&twosB);
+        twos=u^twosB;
+      }
+
+      //CSA(eights, fours, fours, foursA, foursB)
+      {
+        long u=fours^foursA;
+        eights=(fours&foursA)|(u&foursB);
+        fours=u^foursB;
+      }
+      tot8 += pop(eights);
+    }
+
+
+    if (i<=n-4) {
+      long twosA, twosB, foursA, eights;
+      {
+        long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
+        long u=ones ^ b;
+        twosA=(ones & b)|( u & c);
+        ones=u^c;
+      }
+      {
+        long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
+        long u=ones^b;
+        twosB =(ones&b)|(u&c);
+        ones=u^c;
+      }
+      {
+        long u=twos^twosA;
+        foursA=(twos&twosA)|(u&twosB);
+        twos=u^twosB;
+      }
+      eights=fours&foursA;
+      fours=fours^foursA;
+
+      tot8 += pop(eights);
+      i+=4;
+    }
+
+    if (i<=n-2) {
+      long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
+      long u=ones ^ b;
+      long twosA=(ones & b)|( u & c);
+      ones=u^c;
+
+      long foursA=twos&twosA;
+      twos=twos^twosA;
+
+      long eights=fours&foursA;
+      fours=fours^foursA;
+
+      tot8 += pop(eights);
+      i+=2;
+    }
+
+    if (i<n) {
+      tot += pop((A[i] & B[i]));
+    }
+
+    tot += (pop(fours)<<2)
+            + (pop(twos)<<1)
+            + pop(ones)
+            + (tot8<<3);
+
+    return tot;
+  }
+
+  /** Returns the popcount or cardinality of the union of two sets.
+    * Neither array is modified.
+    */
+   public static long pop_union(long A[], long B[], int wordOffset, int numWords) {
+     // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \| B[\1]\)/g'
+     int n = wordOffset+numWords;
+     long tot=0, tot8=0;
+     long ones=0, twos=0, fours=0;
+
+     int i;
+     for (i = wordOffset; i <= n - 8; i+=8) {
+       /***  C macro from Hacker's Delight
+        #define CSA(h,l, a,b,c) \
+        {unsigned u = a ^ b; unsigned v = c; \
+        h = (a & b) | (u & v); l = u ^ v;}
+        ***/
+
+       long twosA,twosB,foursA,foursB,eights;
+
+       // CSA(twosA, ones, ones, (A[i] | B[i]), (A[i+1] | B[i+1]))
+       {
+         long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
+         long u=ones ^ b;
+         twosA=(ones & b)|( u & c);
+         ones=u^c;
+       }
+       // CSA(twosB, ones, ones, (A[i+2] | B[i+2]), (A[i+3] | B[i+3]))
+       {
+         long b=(A[i+2] | B[i+2]), c=(A[i+3] | B[i+3]);
+         long u=ones^b;
+         twosB =(ones&b)|(u&c);
+         ones=u^c;
+       }
+       //CSA(foursA, twos, twos, twosA, twosB)
+       {
+         long u=twos^twosA;
+         foursA=(twos&twosA)|(u&twosB);
+         twos=u^twosB;
+       }
+       //CSA(twosA, ones, ones, (A[i+4] | B[i+4]), (A[i+5] | B[i+5]))
+       {
+         long b=(A[i+4] | B[i+4]), c=(A[i+5] | B[i+5]);
+         long u=ones^b;
+         twosA=(ones&b)|(u&c);
+         ones=u^c;
+       }
+       // CSA(twosB, ones, ones, (A[i+6] | B[i+6]), (A[i+7] | B[i+7]))
+       {
+         long b=(A[i+6] | B[i+6]), c=(A[i+7] | B[i+7]);
+         long u=ones^b;
+         twosB=(ones&b)|(u&c);
+         ones=u^c;
+       }
+       //CSA(foursB, twos, twos, twosA, twosB)
+       {
+         long u=twos^twosA;
+         foursB=(twos&twosA)|(u&twosB);
+         twos=u^twosB;
+       }
+
+       //CSA(eights, fours, fours, foursA, foursB)
+       {
+         long u=fours^foursA;
+         eights=(fours&foursA)|(u&foursB);
+         fours=u^foursB;
+       }
+       tot8 += pop(eights);
+     }
+
+
+     if (i<=n-4) {
+       long twosA, twosB, foursA, eights;
+       {
+         long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
+         long u=ones ^ b;
+         twosA=(ones & b)|( u & c);
+         ones=u^c;
+       }
+       {
+         long b=(A[i+2] | B[i+2]), c=(A[i+3] | B[i+3]);
+         long u=ones^b;
+         twosB =(ones&b)|(u&c);
+         ones=u^c;
+       }
+       {
+         long u=twos^twosA;
+         foursA=(twos&twosA)|(u&twosB);
+         twos=u^twosB;
+       }
+       eights=fours&foursA;
+       fours=fours^foursA;
+
+       tot8 += pop(eights);
+       i+=4;
+     }
+
+     if (i<=n-2) {
+       long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
+       long u=ones ^ b;
+       long twosA=(ones & b)|( u & c);
+       ones=u^c;
+
+       long foursA=twos&twosA;
+       twos=twos^twosA;
+
+       long eights=fours&foursA;
+       fours=fours^foursA;
+
+       tot8 += pop(eights);
+       i+=2;
+     }
+
+     if (i<n) {
+       tot += pop((A[i] | B[i]));
+     }
+
+     tot += (pop(fours)<<2)
+             + (pop(twos)<<1)
+             + pop(ones)
+             + (tot8<<3);
+
+     return tot;
+   }
+
+  /** Returns the popcount or cardinality of A & ~B
+   * Neither array is modified.
+   */
+  public static long pop_andnot(long A[], long B[], int wordOffset, int numWords) {
+    // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& ~B[\1]\)/g'
+    int n = wordOffset+numWords;
+    long tot=0, tot8=0;
+    long ones=0, twos=0, fours=0;
+
+    int i;
+    for (i = wordOffset; i <= n - 8; i+=8) {
+      /***  C macro from Hacker's Delight
+       #define CSA(h,l, a,b,c) \
+       {unsigned u = a ^ b; unsigned v = c; \
+       h = (a & b) | (u & v); l = u ^ v;}
+       ***/
+
+      long twosA,twosB,foursA,foursB,eights;
+
+      // CSA(twosA, ones, ones, (A[i] & ~B[i]), (A[i+1] & ~B[i+1]))
+      {
+        long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
+        long u=ones ^ b;
+        twosA=(ones & b)|( u & c);
+        ones=u^c;
+      }
+      // CSA(twosB, ones, ones, (A[i+2] & ~B[i+2]), (A[i+3] & ~B[i+3]))
+      {
+        long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
+        long u=ones^b;
+        twosB =(ones&b)|(u&c);
+        ones=u^c;
+      }
+      //CSA(foursA, twos, twos, twosA, twosB)
+      {
+        long u=twos^twosA;
+        foursA=(twos&twosA)|(u&twosB);
+        twos=u^twosB;
+      }
+      //CSA(twosA, ones, ones, (A[i+4] & ~B[i+4]), (A[i+5] & ~B[i+5]))
+      {
+        long b=(A[i+4] & ~B[i+4]), c=(A[i+5] & ~B[i+5]);
+        long u=ones^b;
+        twosA=(ones&b)|(u&c);
+        ones=u^c;
+      }
+      // CSA(twosB, ones, ones, (A[i+6] & ~B[i+6]), (A[i+7] & ~B[i+7]))
+      {
+        long b=(A[i+6] & ~B[i+6]), c=(A[i+7] & ~B[i+7]);
+        long u=ones^b;
+        twosB=(ones&b)|(u&c);
+        ones=u^c;
+      }
+      //CSA(foursB, twos, twos, twosA, twosB)
+      {
+        long u=twos^twosA;
+        foursB=(twos&twosA)|(u&twosB);
+        twos=u^twosB;
+      }
+
+      //CSA(eights, fours, fours, foursA, foursB)
+      {
+        long u=fours^foursA;
+        eights=(fours&foursA)|(u&foursB);
+        fours=u^foursB;
+      }
+      tot8 += pop(eights);
+    }
+
+
+    if (i<=n-4) {
+      long twosA, twosB, foursA, eights;
+      {
+        long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
+        long u=ones ^ b;
+        twosA=(ones & b)|( u & c);
+        ones=u^c;
+      }
+      {
+        long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
+        long u=ones^b;
+        twosB =(ones&b)|(u&c);
+        ones=u^c;
+      }
+      {
+        long u=twos^twosA;
+        foursA=(twos&twosA)|(u&twosB);
+        twos=u^twosB;
+      }
+      eights=fours&foursA;
+      fours=fours^foursA;
+
+      tot8 += pop(eights);
+      i+=4;
+    }
+
+    if (i<=n-2) {
+      long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
+      long u=ones ^ b;
+      long twosA=(ones & b)|( u & c);
+      ones=u^c;
+
+      long foursA=twos&twosA;
+      twos=twos^twosA;
+
+      long eights=fours&foursA;
+      fours=fours^foursA;
+
+      tot8 += pop(eights);
+      i+=2;
+    }
+
+    if (i<n) {
+      tot += pop((A[i] & ~B[i]));
+    }
+
+    tot += (pop(fours)<<2)
+            + (pop(twos)<<1)
+            + pop(ones)
+            + (tot8<<3);
+
+    return tot;
+  }
+
+  public static long pop_xor(long A[], long B[], int wordOffset, int numWords) {
+    int n = wordOffset+numWords;
+    long tot=0, tot8=0;
+    long ones=0, twos=0, fours=0;
+
+    int i;
+    for (i = wordOffset; i <= n - 8; i+=8) {
+      /***  C macro from Hacker's Delight
+       #define CSA(h,l, a,b,c) \
+       {unsigned u = a ^ b; unsigned v = c; \
+       h = (a & b) | (u & v); l = u ^ v;}
+       ***/
+
+      long twosA,twosB,foursA,foursB,eights;
+
+      // CSA(twosA, ones, ones, (A[i] ^ B[i]), (A[i+1] ^ B[i+1]))
+      {
+        long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
+        long u=ones ^ b;
+        twosA=(ones & b)|( u & c);
+        ones=u^c;
+      }
+      // CSA(twosB, ones, ones, (A[i+2] ^ B[i+2]), (A[i+3] ^ B[i+3]))
+      {
+        long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
+        long u=ones^b;
+        twosB =(ones&b)|(u&c);
+        ones=u^c;
+      }
+      //CSA(foursA, twos, twos, twosA, twosB)
+      {
+        long u=twos^twosA;
+        foursA=(twos&twosA)|(u&twosB);
+        twos=u^twosB;
+      }
+      //CSA(twosA, ones, ones, (A[i+4] ^ B[i+4]), (A[i+5] ^ B[i+5]))
+      {
+        long b=(A[i+4] ^ B[i+4]), c=(A[i+5] ^ B[i+5]);
+        long u=ones^b;
+        twosA=(ones&b)|(u&c);
+        ones=u^c;
+      }
+      // CSA(twosB, ones, ones, (A[i+6] ^ B[i+6]), (A[i+7] ^ B[i+7]))
+      {
+        long b=(A[i+6] ^ B[i+6]), c=(A[i+7] ^ B[i+7]);
+        long u=ones^b;
+        twosB=(ones&b)|(u&c);
+        ones=u^c;
+      }
+      //CSA(foursB, twos, twos, twosA, twosB)
+      {
+        long u=twos^twosA;
+        foursB=(twos&twosA)|(u&twosB);
+        twos=u^twosB;
+      }
+
+      //CSA(eights, fours, fours, foursA, foursB)
+      {
+        long u=fours^foursA;
+        eights=(fours&foursA)|(u&foursB);
+        fours=u^foursB;
+      }
+      tot8 += pop(eights);
+    }
+
+
+    if (i<=n-4) {
+      long twosA, twosB, foursA, eights;
+      {
+        long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
+        long u=ones ^ b;
+        twosA=(ones & b)|( u & c);
+        ones=u^c;
+      }
+      {
+        long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
+        long u=ones^b;
+        twosB =(ones&b)|(u&c);
+        ones=u^c;
+      }
+      {
+        long u=twos^twosA;
+        foursA=(twos&twosA)|(u&twosB);
+        twos=u^twosB;
+      }
+      eights=fours&foursA;
+      fours=fours^foursA;
+
+      tot8 += pop(eights);
+      i+=4;
+    }
+
+    if (i<=n-2) {
+      long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
+      long u=ones ^ b;
+      long twosA=(ones & b)|( u & c);
+      ones=u^c;
+
+      long foursA=twos&twosA;
+      twos=twos^twosA;
+
+      long eights=fours&foursA;
+      fours=fours^foursA;
+
+      tot8 += pop(eights);
+      i+=2;
+    }
+
+    if (i<n) {
+      tot += pop((A[i] ^ B[i]));
+    }
+
+    tot += (pop(fours)<<2)
+            + (pop(twos)<<1)
+            + pop(ones)
+            + (tot8<<3);
+
+    return tot;
+  }
+
+  /* python code to generate ntzTable
+  def ntz(val):
+    if val==0: return 8
+    i=0
+    while (val&0x01)==0:
+      i = i+1
+      val >>= 1
+    return i
+  print ','.join([ str(ntz(i)) for i in range(256) ])
+  ***/
+  /** table of number of trailing zeros in a byte */
+  public static final byte[] ntzTable = {8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0};
+
+
+  /** Returns number of trailing zeros in the 64 bit long value. */
+  public static int ntz(long val) {
+    // A full binary search to determine the low byte was slower than
+    // a linear search for nextSetBit().  This is most likely because
+    // the implementation of nextSetBit() shifts bits to the right, increasing
+    // the probability that the first non-zero byte is in the rhs.
+    //
+    // This implementation does a single binary search at the top level only
+    // so that all other bit shifting can be done on ints instead of longs to
+    // remain friendly to 32 bit architectures.  In addition, the case of a
+    // non-zero first byte is checked for first because it is the most common
+    // in dense bit arrays.
+
+    int lower = (int)val;
+    int lowByte = lower & 0xff;
+    if (lowByte != 0) return ntzTable[lowByte];
+
+    if (lower!=0) {
+      lowByte = (lower>>>8) & 0xff;
+      if (lowByte != 0) return ntzTable[lowByte] + 8;
+      lowByte = (lower>>>16) & 0xff;
+      if (lowByte != 0) return ntzTable[lowByte] + 16;
+      // no need to mask off low byte for the last byte in the 32 bit word
+      // no need to check for zero on the last byte either.
+      return ntzTable[lower>>>24] + 24;
+    } else {
+      // grab upper 32 bits
+      int upper=(int)(val>>32);
+      lowByte = upper & 0xff;
+      if (lowByte != 0) return ntzTable[lowByte] + 32;
+      lowByte = (upper>>>8) & 0xff;
+      if (lowByte != 0) return ntzTable[lowByte] + 40;
+      lowByte = (upper>>>16) & 0xff;
+      if (lowByte != 0) return ntzTable[lowByte] + 48;
+      // no need to mask off low byte for the last byte in the 32 bit word
+      // no need to check for zero on the last byte either.
+      return ntzTable[upper>>>24] + 56;
+    }
+  }
+
+  /** returns 0 based index of first set bit
+   * (only works for x!=0)
+   * <br/> This is an alternate implementation of ntz()
+   */
+  public static int ntz2(long x) {
+   int n = 0;
+   int y = (int)x;
+   if (y==0) {n+=32; y = (int)(x>>>32); }   // the only 64 bit shift necessary
+   if ((y & 0x0000FFFF) == 0) { n+=16; y>>>=16; }
+   if ((y & 0x000000FF) == 0) { n+=8; y>>>=8; }
+   return (ntzTable[ y & 0xff ]) + n;
+  }
+
+  /** returns 0 based index of first set bit
+   * <br/> This is an alternate implementation of ntz()
+   */
+  public static int ntz3(long x) {
+   // another implementation taken from Hackers Delight, extended to 64 bits
+   // and converted to Java.
+   // Many 32 bit ntz algorithms are at http://www.hackersdelight.org/HDcode/ntz.cc
+   int n = 1;
+
+   // do the first step as a long, all others as ints.
+   int y = (int)x;
+   if (y==0) {n+=32; y = (int)(x>>>32); }
+   if ((y & 0x0000FFFF) == 0) { n+=16; y>>>=16; }
+   if ((y & 0x000000FF) == 0) { n+=8; y>>>=8; }
+   if ((y & 0x0000000F) == 0) { n+=4; y>>>=4; }
+   if ((y & 0x00000003) == 0) { n+=2; y>>>=2; }
+   return n - (y & 1);
+  }
+
+
+  /** returns true if v is a power of two or zero*/
+  public static boolean isPowerOfTwo(int v) {
+    return ((v & (v-1)) == 0);
+  }
+
+  /** returns true if v is a power of two or zero*/
+  public static boolean isPowerOfTwo(long v) {
+    return ((v & (v-1)) == 0);
+  }
+
+  /** returns the next highest power of two, or the current value if it's already a power of two or zero*/
+  public static int nextHighestPowerOfTwo(int v) {
+    v--;
+    v |= v >> 1;
+    v |= v >> 2;
+    v |= v >> 4;
+    v |= v >> 8;
+    v |= v >> 16;
+    v++;
+    return v;
+  }
+
+  /** returns the next highest power of two, or the current value if it's already a power of two or zero*/
+   public static long nextHighestPowerOfTwo(long v) {
+    v--;
+    v |= v >> 1;
+    v |= v >> 2;
+    v |= v >> 4;
+    v |= v >> 8;
+    v |= v >> 16;
+    v |= v >> 32;
+    v++;
+    return v;
+  }
+
+}

Propchange: lucene/java/trunk/src/java/org/apache/lucene/util/BitUtil.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/java/trunk/src/java/org/apache/lucene/util/DocIdBitSet.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/src/java/org/apache/lucene/util/DocIdBitSet.java?rev=617859&view=auto
==============================================================================
--- lucene/java/trunk/src/java/org/apache/lucene/util/DocIdBitSet.java (added)
+++ lucene/java/trunk/src/java/org/apache/lucene/util/DocIdBitSet.java Sat Feb  2 11:04:03 2008
@@ -0,0 +1,77 @@
+package org.apache.lucene.util;
+
+/**
+ * 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.
+ */
+
+import java.util.BitSet;
+import org.apache.lucene.search.DocIdSet;
+import org.apache.lucene.search.DocIdSetIterator;
+
+
+/** Simple DocIdSet and DocIdSetIterator backed by a BitSet */
+public class DocIdBitSet extends DocIdSet {
+  private BitSet bitSet;
+    
+  public DocIdBitSet(BitSet bitSet) {
+    this.bitSet = bitSet;
+  }
+
+  public DocIdSetIterator iterator() {
+    return new DocIdBitSetIterator(bitSet);
+  }
+  
+  /**
+   * Returns the underlying BitSet. 
+   */
+  public BitSet getBitSet() {
+	return this.bitSet;
+  }
+  
+  private static class DocIdBitSetIterator extends DocIdSetIterator {
+    private int docId;
+    private BitSet bitSet;
+    
+    DocIdBitSetIterator(BitSet bitSet) {
+      this.bitSet = bitSet;
+      this.docId = -1;
+    }
+    
+    public int doc() {
+      assert docId != -1;
+      return docId;
+    }
+    
+    public boolean next() {
+      // (docId + 1) on next line requires -1 initial value for docNr:
+      return checkNextDocId(bitSet.nextSetBit(docId + 1));
+    }
+  
+    public boolean skipTo(int skipDocNr) {
+      return checkNextDocId( bitSet.nextSetBit(skipDocNr));
+    }
+  
+    private boolean checkNextDocId(int d) {
+      if (d == -1) { // -1 returned by BitSet.nextSetBit() when exhausted
+        docId = Integer.MAX_VALUE;
+        return false;
+      } else {
+        docId = d;
+        return true;
+      }
+    }
+  }
+}

Propchange: lucene/java/trunk/src/java/org/apache/lucene/util/DocIdBitSet.java
------------------------------------------------------------------------------
    svn:eol-style = native



Mime
View raw message