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 bu...@apache.org on 2008/02/02 20:04:09 UTC
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...
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