lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java - lucene-solr - Git at Google

 /*
  * 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.search;


 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.List;

 import org.apache.lucene.search.spans.Spans;
 import org.apache.lucene.util.ArrayUtil;
 import org.apache.lucene.util.BitSet;
 import org.apache.lucene.util.BitSetIterator;
 import org.apache.lucene.util.CollectionUtil;

 /** A conjunction of DocIdSetIterators.
  * Requires that all of its sub-iterators must be on the same document all the time.
  * This iterates over the doc ids that are present in each given DocIdSetIterator.
  * <br>Public only for use in {@link org.apache.lucene.search.spans}.
  * @lucene.internal
  */
 public final class ConjunctionDISI extends DocIdSetIterator {

   /** Create a conjunction over the provided {@link Scorer}s. Note that the
    * returned {@link DocIdSetIterator} might leverage two-phase iteration in
    * which case it is possible to retrieve the {@link TwoPhaseIterator} using
    * {@link TwoPhaseIterator#unwrap}. */
   public static DocIdSetIterator intersectScorers(Collection<Scorer> scorers) {
     if (scorers.size() < 2) {
       throw new IllegalArgumentException("Cannot make a ConjunctionDISI of less than 2 iterators");
     }
     final List<DocIdSetIterator> allIterators = new ArrayList<>();
     final List<TwoPhaseIterator> twoPhaseIterators = new ArrayList<>();
     for (Scorer scorer : scorers) {
       addScorer(scorer, allIterators, twoPhaseIterators);
     }

     return createConjunction(allIterators, twoPhaseIterators);
   }

   /** Create a conjunction over the provided DocIdSetIterators. Note that the
    * returned {@link DocIdSetIterator} might leverage two-phase iteration in
    * which case it is possible to retrieve the {@link TwoPhaseIterator} using
    * {@link TwoPhaseIterator#unwrap}. */
   public static DocIdSetIterator intersectIterators(List<DocIdSetIterator> iterators) {
     if (iterators.size() < 2) {
       throw new IllegalArgumentException("Cannot make a ConjunctionDISI of less than 2 iterators");
     }
     final List<DocIdSetIterator> allIterators = new ArrayList<>();
     final List<TwoPhaseIterator> twoPhaseIterators = new ArrayList<>();
     for (DocIdSetIterator iterator : iterators) {
       addIterator(iterator, allIterators, twoPhaseIterators);
     }

     return createConjunction(allIterators, twoPhaseIterators);
   }

   /** Create a conjunction over the provided {@link Spans}. Note that the
    * returned {@link DocIdSetIterator} might leverage two-phase iteration in
    * which case it is possible to retrieve the {@link TwoPhaseIterator} using
    * {@link TwoPhaseIterator#unwrap}. */
   public static DocIdSetIterator intersectSpans(List<Spans> spanList) {
     if (spanList.size() < 2) {
       throw new IllegalArgumentException("Cannot make a ConjunctionDISI of less than 2 iterators");
     }
     final List<DocIdSetIterator> allIterators = new ArrayList<>();
     final List<TwoPhaseIterator> twoPhaseIterators = new ArrayList<>();
     for (Spans spans : spanList) {
       addSpans(spans, allIterators, twoPhaseIterators);
     }

     return createConjunction(allIterators, twoPhaseIterators);
   }

   /** Adds the scorer, possibly splitting up into two phases or collapsing if it is another conjunction */
   private static void addScorer(Scorer scorer, List<DocIdSetIterator> allIterators, List<TwoPhaseIterator> twoPhaseIterators) {
     TwoPhaseIterator twoPhaseIter = scorer.twoPhaseIterator();
     if (twoPhaseIter != null) {
       addTwoPhaseIterator(twoPhaseIter, allIterators, twoPhaseIterators);
     } else { // no approximation support, use the iterator as-is
       addIterator(scorer.iterator(), allIterators, twoPhaseIterators);
     }
   }

   /** Adds the Spans. */
   private static void addSpans(Spans spans, List<DocIdSetIterator> allIterators, List<TwoPhaseIterator> twoPhaseIterators) {
     TwoPhaseIterator twoPhaseIter = spans.asTwoPhaseIterator();
     if (twoPhaseIter != null) {
       addTwoPhaseIterator(twoPhaseIter, allIterators, twoPhaseIterators);
     } else { // no approximation support, use the iterator as-is
       addIterator(spans, allIterators, twoPhaseIterators);
     }
   }

   private static void addIterator(DocIdSetIterator disi, List<DocIdSetIterator> allIterators, List<TwoPhaseIterator> twoPhaseIterators) {
     TwoPhaseIterator twoPhase = TwoPhaseIterator.unwrap(disi);
     if (twoPhase != null) {
       addTwoPhaseIterator(twoPhase, allIterators, twoPhaseIterators);
     } else if (disi.getClass() == ConjunctionDISI.class) { // Check for exactly this class for collapsing
       ConjunctionDISI conjunction = (ConjunctionDISI) disi;
       // subconjuctions have already split themselves into two phase iterators and others, so we can take those
       // iterators as they are and move them up to this conjunction
       allIterators.add(conjunction.lead1);
       allIterators.add(conjunction.lead2);
       Collections.addAll(allIterators, conjunction.others);
     } else if (disi.getClass() == BitSetConjunctionDISI.class) {
       BitSetConjunctionDISI conjunction = (BitSetConjunctionDISI) disi;
       allIterators.add(conjunction.lead);
       Collections.addAll(allIterators, conjunction.bitSetIterators);
     } else {
       allIterators.add(disi);
     }
   }

   private static void addTwoPhaseIterator(TwoPhaseIterator twoPhaseIter, List<DocIdSetIterator> allIterators, List<TwoPhaseIterator> twoPhaseIterators) {
     addIterator(twoPhaseIter.approximation(), allIterators, twoPhaseIterators);
     if (twoPhaseIter.getClass() == ConjunctionTwoPhaseIterator.class) { // Check for exactly this class for collapsing
       Collections.addAll(twoPhaseIterators, ((ConjunctionTwoPhaseIterator) twoPhaseIter).twoPhaseIterators);
     } else {
       twoPhaseIterators.add(twoPhaseIter);
     }
   }

   private static DocIdSetIterator createConjunction(
       List<DocIdSetIterator> allIterators,
       List<TwoPhaseIterator> twoPhaseIterators) {

     // check that all sub-iterators are on the same doc ID
     int curDoc = allIterators.size() > 0 ? allIterators.get(0).docID() : twoPhaseIterators.get(0).approximation.docID();
     boolean iteratorsOnTheSameDoc = allIterators.stream().allMatch(it -> it.docID() == curDoc);
     iteratorsOnTheSameDoc = iteratorsOnTheSameDoc && twoPhaseIterators.stream().allMatch(it -> it.approximation().docID() == curDoc);
     if (iteratorsOnTheSameDoc == false) {
       throw new IllegalArgumentException("Sub-iterators of ConjunctionDISI are not on the same document!");
     }

     long minCost = allIterators.stream().mapToLong(DocIdSetIterator::cost).min().getAsLong();
     List<BitSetIterator> bitSetIterators = new ArrayList<>();
     List<DocIdSetIterator> iterators = new ArrayList<>();
     for (DocIdSetIterator iterator : allIterators) {
       if (iterator.cost() > minCost && iterator instanceof BitSetIterator) {
         // we put all bitset iterators into bitSetIterators
         // except if they have the minimum cost, since we need
         // them to lead the iteration in that case
         bitSetIterators.add((BitSetIterator) iterator);
       } else {
         iterators.add(iterator);
       }
     }

     DocIdSetIterator disi;
     if (iterators.size() == 1) {
       disi = iterators.get(0);
     } else {
       disi = new ConjunctionDISI(iterators);
     }

     if (bitSetIterators.size() > 0) {
       disi = new BitSetConjunctionDISI(disi, bitSetIterators);
     }

     if (twoPhaseIterators.isEmpty() == false) {
       disi = TwoPhaseIterator.asDocIdSetIterator(new ConjunctionTwoPhaseIterator(disi, twoPhaseIterators));
     }

     return disi;
   }

   final DocIdSetIterator lead1, lead2;
   final DocIdSetIterator[] others;

   private ConjunctionDISI(List<? extends DocIdSetIterator> iterators) {
     assert iterators.size() >= 2;

     // Sort the array the first time to allow the least frequent DocsEnum to
     // lead the matching.
     CollectionUtil.timSort(iterators, new Comparator<DocIdSetIterator>() {
       @Override
       public int compare(DocIdSetIterator o1, DocIdSetIterator o2) {
         return Long.compare(o1.cost(), o2.cost());
       }
     });
     lead1 = iterators.get(0);
     lead2 = iterators.get(1);
     others = iterators.subList(2, iterators.size()).toArray(new DocIdSetIterator[0]);
   }

   private int doNext(int doc) throws IOException {
     advanceHead: for(;;) {
       assert doc == lead1.docID();

       // find agreement between the two iterators with the lower costs
       // we special case them because they do not need the
       // 'other.docID() < doc' check that the 'others' iterators need
       final int next2 = lead2.advance(doc);
       if (next2 != doc) {
         doc = lead1.advance(next2);
         if (next2 != doc) {
           continue;
         }
       }

       // then find agreement with other iterators
       for (DocIdSetIterator other : others) {
         // other.doc may already be equal to doc if we "continued advanceHead"
         // on the previous iteration and the advance on the lead scorer exactly matched.
         if (other.docID() < doc) {
           final int next = other.advance(doc);

           if (next > doc) {
             // iterator beyond the current doc - advance lead and continue to the new highest doc.
             doc = lead1.advance(next);
             continue advanceHead;
           }
         }
       }

       // success - all iterators are on the same doc
       return doc;
     }
   }

   @Override
   public int advance(int target) throws IOException {
     assert assertItersOnSameDoc() : "Sub-iterators of ConjunctionDISI are not one the same document!";
     return doNext(lead1.advance(target));
   }

   @Override
   public int docID() {
     return lead1.docID();
   }

   @Override
   public int nextDoc() throws IOException {
     assert assertItersOnSameDoc() : "Sub-iterators of ConjunctionDISI are not on the same document!";
     return doNext(lead1.nextDoc());
   }

   @Override
   public long cost() {
     return lead1.cost(); // overestimate
   }

   // Returns {@code true} if all sub-iterators are on the same doc ID, {@code false} otherwise
   private boolean assertItersOnSameDoc() {
     int curDoc = lead1.docID();
     boolean iteratorsOnTheSameDoc = (lead2.docID() == curDoc);
     for (int i = 0; (i < others.length && iteratorsOnTheSameDoc); i++) {
       iteratorsOnTheSameDoc = iteratorsOnTheSameDoc && (others[i].docID() == curDoc);
     }
     return iteratorsOnTheSameDoc;
   }

   /** Conjunction between a {@link DocIdSetIterator} and one or more {@link BitSetIterator}s. */
   private static class BitSetConjunctionDISI extends DocIdSetIterator {

     private final DocIdSetIterator lead;
     private final BitSetIterator[] bitSetIterators;
     private final BitSet[] bitSets;
     private final int minLength;

     BitSetConjunctionDISI(DocIdSetIterator lead, Collection<BitSetIterator> bitSetIterators) {
       this.lead = lead;
       assert bitSetIterators.size() > 0;

       this.bitSetIterators = bitSetIterators.toArray(new BitSetIterator[0]);
       // Put the least costly iterators first so that we exit as soon as possible
       ArrayUtil.timSort(this.bitSetIterators, (a, b) -> Long.compare(a.cost(), b.cost()));
       this.bitSets = new BitSet[this.bitSetIterators.length];
       int minLen = Integer.MAX_VALUE;
       for (int i = 0; i < this.bitSetIterators.length; ++i) {
         BitSet bitSet = this.bitSetIterators[i].getBitSet();
         this.bitSets[i] = bitSet;
         minLen = Math.min(minLen, bitSet.length());
       }
       this.minLength = minLen;
     }

     @Override
     public int docID() {
       return lead.docID();
     }

     @Override
     public int nextDoc() throws IOException {
       assert assertItersOnSameDoc() : "Sub-iterators of ConjunctionDISI are not on the same document!";
       return doNext(lead.nextDoc());
     }

     @Override
     public int advance(int target) throws IOException {
       assert assertItersOnSameDoc() : "Sub-iterators of ConjunctionDISI are not on the same document!";
       return doNext(lead.advance(target));
     }

     private int doNext(int doc) throws IOException {
       advanceLead: for (;; doc = lead.nextDoc()) {
         if (doc >= minLength) {
           return NO_MORE_DOCS;
         }
         for (BitSet bitSet : bitSets) {
           if (bitSet.get(doc) == false) {
             continue advanceLead;
           }
         }
         for (BitSetIterator iterator : bitSetIterators) {
           iterator.setDocId(doc);
         }
         return doc;
       }
     }

     @Override
     public long cost() {
       return lead.cost();
     }

     // Returns {@code true} if all sub-iterators are on the same doc ID, {@code false} otherwise
     private boolean assertItersOnSameDoc() {
       int curDoc = lead.docID();
       boolean iteratorsOnTheSameDoc = true;
       for (int i = 0; (i < bitSetIterators.length && iteratorsOnTheSameDoc); i++) {
         iteratorsOnTheSameDoc = iteratorsOnTheSameDoc && (bitSetIterators[i].docID() == curDoc);
       }
       return iteratorsOnTheSameDoc;
     }

   }

   /**
    * {@link TwoPhaseIterator} implementing a conjunction.
    */
   private static final class ConjunctionTwoPhaseIterator extends TwoPhaseIterator {

     private final TwoPhaseIterator[] twoPhaseIterators;
     private final float matchCost;

     private ConjunctionTwoPhaseIterator(DocIdSetIterator approximation,
         List<? extends TwoPhaseIterator> twoPhaseIterators) {
       super(approximation);
       assert twoPhaseIterators.size() > 0;

       CollectionUtil.timSort(twoPhaseIterators, new Comparator<TwoPhaseIterator>() {
         @Override
         public int compare(TwoPhaseIterator o1, TwoPhaseIterator o2) {
           return Float.compare(o1.matchCost(), o2.matchCost());
         }
       });

       this.twoPhaseIterators = twoPhaseIterators.toArray(new TwoPhaseIterator[twoPhaseIterators.size()]);

       // Compute the matchCost as the total matchCost of the sub iterators.
       // TODO: This could be too high because the matching is done cheapest first: give the lower matchCosts a higher weight.
       float totalMatchCost = 0;
       for (TwoPhaseIterator tpi : twoPhaseIterators) {
         totalMatchCost += tpi.matchCost();
       }
       matchCost = totalMatchCost;
     }

     @Override
     public boolean matches() throws IOException {
       for (TwoPhaseIterator twoPhaseIterator : twoPhaseIterators) { // match cheapest first
         if (twoPhaseIterator.matches() == false) {
           return false;
         }
       }
       return true;
     }

     @Override
     public float matchCost() {
       return matchCost;
     }

   }

 }
	/*
	* 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.search;


	import java.io.IOException;
	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.List;

	import org.apache.lucene.search.spans.Spans;
	import org.apache.lucene.util.ArrayUtil;
	import org.apache.lucene.util.BitSet;
	import org.apache.lucene.util.BitSetIterator;
	import org.apache.lucene.util.CollectionUtil;

	/** A conjunction of DocIdSetIterators.
	* Requires that all of its sub-iterators must be on the same document all the time.
	* This iterates over the doc ids that are present in each given DocIdSetIterator.
	* <br>Public only for use in {@link org.apache.lucene.search.spans}.
	* @lucene.internal
	*/
	public final class ConjunctionDISI extends DocIdSetIterator {

	/** Create a conjunction over the provided {@link Scorer}s. Note that the
	* returned {@link DocIdSetIterator} might leverage two-phase iteration in
	* which case it is possible to retrieve the {@link TwoPhaseIterator} using
	* {@link TwoPhaseIterator#unwrap}. */
	public static DocIdSetIterator intersectScorers(Collection<Scorer> scorers) {
	if (scorers.size() < 2) {
	throw new IllegalArgumentException("Cannot make a ConjunctionDISI of less than 2 iterators");
	}
	final List<DocIdSetIterator> allIterators = new ArrayList<>();
	final List<TwoPhaseIterator> twoPhaseIterators = new ArrayList<>();
	for (Scorer scorer : scorers) {
	addScorer(scorer, allIterators, twoPhaseIterators);
	}

	return createConjunction(allIterators, twoPhaseIterators);
	}

	/** Create a conjunction over the provided DocIdSetIterators. Note that the
	* returned {@link DocIdSetIterator} might leverage two-phase iteration in
	* which case it is possible to retrieve the {@link TwoPhaseIterator} using
	* {@link TwoPhaseIterator#unwrap}. */
	public static DocIdSetIterator intersectIterators(List<DocIdSetIterator> iterators) {
	if (iterators.size() < 2) {
	throw new IllegalArgumentException("Cannot make a ConjunctionDISI of less than 2 iterators");
	}
	final List<DocIdSetIterator> allIterators = new ArrayList<>();
	final List<TwoPhaseIterator> twoPhaseIterators = new ArrayList<>();
	for (DocIdSetIterator iterator : iterators) {
	addIterator(iterator, allIterators, twoPhaseIterators);
	}

	return createConjunction(allIterators, twoPhaseIterators);
	}

	/** Create a conjunction over the provided {@link Spans}. Note that the
	* returned {@link DocIdSetIterator} might leverage two-phase iteration in
	* which case it is possible to retrieve the {@link TwoPhaseIterator} using
	* {@link TwoPhaseIterator#unwrap}. */
	public static DocIdSetIterator intersectSpans(List<Spans> spanList) {
	if (spanList.size() < 2) {
	throw new IllegalArgumentException("Cannot make a ConjunctionDISI of less than 2 iterators");
	}
	final List<DocIdSetIterator> allIterators = new ArrayList<>();
	final List<TwoPhaseIterator> twoPhaseIterators = new ArrayList<>();
	for (Spans spans : spanList) {
	addSpans(spans, allIterators, twoPhaseIterators);
	}

	return createConjunction(allIterators, twoPhaseIterators);
	}

	/** Adds the scorer, possibly splitting up into two phases or collapsing if it is another conjunction */
	private static void addScorer(Scorer scorer, List<DocIdSetIterator> allIterators, List<TwoPhaseIterator> twoPhaseIterators) {
	TwoPhaseIterator twoPhaseIter = scorer.twoPhaseIterator();
	if (twoPhaseIter != null) {
	addTwoPhaseIterator(twoPhaseIter, allIterators, twoPhaseIterators);
	} else { // no approximation support, use the iterator as-is
	addIterator(scorer.iterator(), allIterators, twoPhaseIterators);
	}
	}

	/** Adds the Spans. */
	private static void addSpans(Spans spans, List<DocIdSetIterator> allIterators, List<TwoPhaseIterator> twoPhaseIterators) {
	TwoPhaseIterator twoPhaseIter = spans.asTwoPhaseIterator();
	if (twoPhaseIter != null) {
	addTwoPhaseIterator(twoPhaseIter, allIterators, twoPhaseIterators);
	} else { // no approximation support, use the iterator as-is
	addIterator(spans, allIterators, twoPhaseIterators);
	}
	}

	private static void addIterator(DocIdSetIterator disi, List<DocIdSetIterator> allIterators, List<TwoPhaseIterator> twoPhaseIterators) {
	TwoPhaseIterator twoPhase = TwoPhaseIterator.unwrap(disi);
	if (twoPhase != null) {
	addTwoPhaseIterator(twoPhase, allIterators, twoPhaseIterators);
	} else if (disi.getClass() == ConjunctionDISI.class) { // Check for exactly this class for collapsing
	ConjunctionDISI conjunction = (ConjunctionDISI) disi;
	// subconjuctions have already split themselves into two phase iterators and others, so we can take those
	// iterators as they are and move them up to this conjunction
	allIterators.add(conjunction.lead1);
	allIterators.add(conjunction.lead2);
	Collections.addAll(allIterators, conjunction.others);
	} else if (disi.getClass() == BitSetConjunctionDISI.class) {
	BitSetConjunctionDISI conjunction = (BitSetConjunctionDISI) disi;
	allIterators.add(conjunction.lead);
	Collections.addAll(allIterators, conjunction.bitSetIterators);
	} else {
	allIterators.add(disi);
	}
	}

	private static void addTwoPhaseIterator(TwoPhaseIterator twoPhaseIter, List<DocIdSetIterator> allIterators, List<TwoPhaseIterator> twoPhaseIterators) {
	addIterator(twoPhaseIter.approximation(), allIterators, twoPhaseIterators);
	if (twoPhaseIter.getClass() == ConjunctionTwoPhaseIterator.class) { // Check for exactly this class for collapsing
	Collections.addAll(twoPhaseIterators, ((ConjunctionTwoPhaseIterator) twoPhaseIter).twoPhaseIterators);
	} else {
	twoPhaseIterators.add(twoPhaseIter);
	}
	}

	private static DocIdSetIterator createConjunction(
	List<DocIdSetIterator> allIterators,
	List<TwoPhaseIterator> twoPhaseIterators) {

	// check that all sub-iterators are on the same doc ID
	int curDoc = allIterators.size() > 0 ? allIterators.get(0).docID() : twoPhaseIterators.get(0).approximation.docID();
	boolean iteratorsOnTheSameDoc = allIterators.stream().allMatch(it -> it.docID() == curDoc);
	iteratorsOnTheSameDoc = iteratorsOnTheSameDoc && twoPhaseIterators.stream().allMatch(it -> it.approximation().docID() == curDoc);
	if (iteratorsOnTheSameDoc == false) {
	throw new IllegalArgumentException("Sub-iterators of ConjunctionDISI are not on the same document!");
	}

	long minCost = allIterators.stream().mapToLong(DocIdSetIterator::cost).min().getAsLong();
	List<BitSetIterator> bitSetIterators = new ArrayList<>();
	List<DocIdSetIterator> iterators = new ArrayList<>();
	for (DocIdSetIterator iterator : allIterators) {
	if (iterator.cost() > minCost && iterator instanceof BitSetIterator) {
	// we put all bitset iterators into bitSetIterators
	// except if they have the minimum cost, since we need
	// them to lead the iteration in that case
	bitSetIterators.add((BitSetIterator) iterator);
	} else {
	iterators.add(iterator);
	}
	}

	DocIdSetIterator disi;
	if (iterators.size() == 1) {
	disi = iterators.get(0);
	} else {
	disi = new ConjunctionDISI(iterators);
	}

	if (bitSetIterators.size() > 0) {
	disi = new BitSetConjunctionDISI(disi, bitSetIterators);
	}

	if (twoPhaseIterators.isEmpty() == false) {
	disi = TwoPhaseIterator.asDocIdSetIterator(new ConjunctionTwoPhaseIterator(disi, twoPhaseIterators));
	}

	return disi;
	}

	final DocIdSetIterator lead1, lead2;
	final DocIdSetIterator[] others;

	private ConjunctionDISI(List<? extends DocIdSetIterator> iterators) {
	assert iterators.size() >= 2;

	// Sort the array the first time to allow the least frequent DocsEnum to
	// lead the matching.
	CollectionUtil.timSort(iterators, new Comparator<DocIdSetIterator>() {
	@Override
	public int compare(DocIdSetIterator o1, DocIdSetIterator o2) {
	return Long.compare(o1.cost(), o2.cost());
	}
	});
	lead1 = iterators.get(0);
	lead2 = iterators.get(1);
	others = iterators.subList(2, iterators.size()).toArray(new DocIdSetIterator[0]);
	}

	private int doNext(int doc) throws IOException {
	advanceHead: for(;;) {
	assert doc == lead1.docID();

	// find agreement between the two iterators with the lower costs
	// we special case them because they do not need the
	// 'other.docID() < doc' check that the 'others' iterators need
	final int next2 = lead2.advance(doc);
	if (next2 != doc) {
	doc = lead1.advance(next2);
	if (next2 != doc) {
	continue;
	}
	}

	// then find agreement with other iterators
	for (DocIdSetIterator other : others) {
	// other.doc may already be equal to doc if we "continued advanceHead"
	// on the previous iteration and the advance on the lead scorer exactly matched.
	if (other.docID() < doc) {
	final int next = other.advance(doc);

	if (next > doc) {
	// iterator beyond the current doc - advance lead and continue to the new highest doc.
	doc = lead1.advance(next);
	continue advanceHead;
	}
	}
	}

	// success - all iterators are on the same doc
	return doc;
	}
	}

	@Override
	public int advance(int target) throws IOException {
	assert assertItersOnSameDoc() : "Sub-iterators of ConjunctionDISI are not one the same document!";
	return doNext(lead1.advance(target));
	}

	@Override
	public int docID() {
	return lead1.docID();
	}

	@Override
	public int nextDoc() throws IOException {
	assert assertItersOnSameDoc() : "Sub-iterators of ConjunctionDISI are not on the same document!";
	return doNext(lead1.nextDoc());
	}

	@Override
	public long cost() {
	return lead1.cost(); // overestimate
	}

	// Returns {@code true} if all sub-iterators are on the same doc ID, {@code false} otherwise
	private boolean assertItersOnSameDoc() {
	int curDoc = lead1.docID();
	boolean iteratorsOnTheSameDoc = (lead2.docID() == curDoc);
	for (int i = 0; (i < others.length && iteratorsOnTheSameDoc); i++) {
	iteratorsOnTheSameDoc = iteratorsOnTheSameDoc && (others[i].docID() == curDoc);
	}
	return iteratorsOnTheSameDoc;
	}

	/** Conjunction between a {@link DocIdSetIterator} and one or more {@link BitSetIterator}s. */
	private static class BitSetConjunctionDISI extends DocIdSetIterator {

	private final DocIdSetIterator lead;
	private final BitSetIterator[] bitSetIterators;
	private final BitSet[] bitSets;
	private final int minLength;

	BitSetConjunctionDISI(DocIdSetIterator lead, Collection<BitSetIterator> bitSetIterators) {
	this.lead = lead;
	assert bitSetIterators.size() > 0;

	this.bitSetIterators = bitSetIterators.toArray(new BitSetIterator[0]);
	// Put the least costly iterators first so that we exit as soon as possible
	ArrayUtil.timSort(this.bitSetIterators, (a, b) -> Long.compare(a.cost(), b.cost()));
	this.bitSets = new BitSet[this.bitSetIterators.length];
	int minLen = Integer.MAX_VALUE;
	for (int i = 0; i < this.bitSetIterators.length; ++i) {
	BitSet bitSet = this.bitSetIterators[i].getBitSet();
	this.bitSets[i] = bitSet;
	minLen = Math.min(minLen, bitSet.length());
	}
	this.minLength = minLen;
	}

	@Override
	public int docID() {
	return lead.docID();
	}

	@Override
	public int nextDoc() throws IOException {
	assert assertItersOnSameDoc() : "Sub-iterators of ConjunctionDISI are not on the same document!";
	return doNext(lead.nextDoc());
	}

	@Override
	public int advance(int target) throws IOException {
	assert assertItersOnSameDoc() : "Sub-iterators of ConjunctionDISI are not on the same document!";
	return doNext(lead.advance(target));
	}

	private int doNext(int doc) throws IOException {
	advanceLead: for (;; doc = lead.nextDoc()) {
	if (doc >= minLength) {
	return NO_MORE_DOCS;
	}
	for (BitSet bitSet : bitSets) {
	if (bitSet.get(doc) == false) {
	continue advanceLead;
	}
	}
	for (BitSetIterator iterator : bitSetIterators) {
	iterator.setDocId(doc);
	}
	return doc;
	}
	}

	@Override
	public long cost() {
	return lead.cost();
	}

	// Returns {@code true} if all sub-iterators are on the same doc ID, {@code false} otherwise
	private boolean assertItersOnSameDoc() {
	int curDoc = lead.docID();
	boolean iteratorsOnTheSameDoc = true;
	for (int i = 0; (i < bitSetIterators.length && iteratorsOnTheSameDoc); i++) {
	iteratorsOnTheSameDoc = iteratorsOnTheSameDoc && (bitSetIterators[i].docID() == curDoc);
	}
	return iteratorsOnTheSameDoc;
	}

	}

	/**
	* {@link TwoPhaseIterator} implementing a conjunction.
	*/
	private static final class ConjunctionTwoPhaseIterator extends TwoPhaseIterator {

	private final TwoPhaseIterator[] twoPhaseIterators;
	private final float matchCost;

	private ConjunctionTwoPhaseIterator(DocIdSetIterator approximation,
	List<? extends TwoPhaseIterator> twoPhaseIterators) {
	super(approximation);
	assert twoPhaseIterators.size() > 0;

	CollectionUtil.timSort(twoPhaseIterators, new Comparator<TwoPhaseIterator>() {
	@Override
	public int compare(TwoPhaseIterator o1, TwoPhaseIterator o2) {
	return Float.compare(o1.matchCost(), o2.matchCost());
	}
	});

	this.twoPhaseIterators = twoPhaseIterators.toArray(new TwoPhaseIterator[twoPhaseIterators.size()]);

	// Compute the matchCost as the total matchCost of the sub iterators.
	// TODO: This could be too high because the matching is done cheapest first: give the lower matchCosts a higher weight.
	float totalMatchCost = 0;
	for (TwoPhaseIterator tpi : twoPhaseIterators) {
	totalMatchCost += tpi.matchCost();
	}
	matchCost = totalMatchCost;
	}

	@Override
	public boolean matches() throws IOException {
	for (TwoPhaseIterator twoPhaseIterator : twoPhaseIterators) { // match cheapest first
	if (twoPhaseIterator.matches() == false) {
	return false;
	}
	}
	return true;
	}

	@Override
	public float matchCost() {
	return matchCost;
	}

	}

	}