Index: src/java/org/apache/lucene/search/TestIteratorPerf.java
===================================================================
--- src/java/org/apache/lucene/search/TestIteratorPerf.java	(revision 0)
+++ src/java/org/apache/lucene/search/TestIteratorPerf.java	(revision 0)
@@ -0,0 +1,309 @@
+package org.apache.lucene.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+import org.apache.lucene.search.docsets.AndDocIdSetIterator;
+import org.apache.lucene.search.docsets.OrDocIdSetIterator;
+import org.apache.lucene.util.OpenBitSet;
+import org.apache.lucene.util.OpenBitSetIterator;
+import org.apache.lucene.util.OpenBitSetIteratorExperiment;
+
+/**
+ * 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.
+ */
+
+/**
+ *
+ * @version $Id$
+ */
+public class TestIteratorPerf  {
+  //Random r = new Random(0);
+  static final int ITER = 10;
+  static final int ITERATOR_SIZE = 10000000;
+  static final double DENSITY = 1.0;//Gaussian... 1.0 != 100%
+  
+ private static final Random random  = new Random(7);
+  
+  public int doOld(int iter, OpenBitSet bs) {
+    int doc=-1;
+    for (int i=0; i<iter; i++) {
+      OpenBitSetIterator it = new OpenBitSetIterator(bs);
+      while(it.next()){
+        doc = it.doc();
+        if(doc++ <-200) break; //avoid optimization
+      }
+      
+    }
+    return doc;
+  }
+
+ 
+  public int doNew(int iter, OpenBitSet bs){
+    int doc=-1;
+    for (int i=0; i<iter; i++) {
+      OpenBitSetIteratorExperiment it = new OpenBitSetIteratorExperiment(bs);
+      while(-1!=(doc=it.next())){
+        if(doc++ <-200) break; //avoid optimization
+      }
+      
+    }
+    return doc;
+  }
+
+
+  public long testOld(OpenBitSet bs) {
+    long total=0;
+    for (int i=0; i<ITER ; i++) {
+      long start = System.currentTimeMillis();
+      doOld(ITER, bs );
+      long end = System.currentTimeMillis();
+      total+=(end-start);
+      System.out.println("old  milliseconds="+(end-start));
+    }
+    System.out.println("old total milliseconds="+total+"\n");
+    return total;
+  }
+
+  public long testNew(OpenBitSet bs) {
+    long total=0;
+    for (int i=0; i<ITER ; i++) {
+      long start = System.currentTimeMillis();
+      doNew(ITER, bs );
+      long end = System.currentTimeMillis();
+      total+=(end-start);
+      System.out.println("new  milliseconds="+(end-start));
+    }
+    System.out.println("new total milliseconds="+total);
+    return total;
+  }
+  
+  public void doIter(DocIdSetIterator it) throws IOException{
+	  while(it.next()){
+	    it.doc();
+	  }
+  }
+  
+  public long testDisjunctionSumScorer(List<OpenBitSet> bs) throws IOException{
+	long total=0;
+	Similarity sim = new DefaultSimilarity();
+	
+	for (int i=0; i<ITER ; i++) {
+	  ArrayList<Scorer> scorerList = new ArrayList<Scorer>(bs.size());
+	  for (OpenBitSet set : bs)
+	  {
+		scorerList.add(new IteratorScorer(sim,new OpenBitSetIterator(set)));
+	  }
+	  DisjunctionSumScorer scorer = new DisjunctionSumScorer(scorerList);
+	  long start = System.currentTimeMillis();
+	  doIter(scorer);
+	  long end = System.currentTimeMillis();
+	  total+=(end-start);
+	  System.out.println("DisjunctionSumScorer  milliseconds="+(end-start));
+	}
+	System.out.println("DisjunctionSumScorer total milliseconds="+total);
+	return total;
+  }
+  
+  public long testDisjunctionMaxScorer(List<OpenBitSet> bs) throws IOException{
+	long total=0;
+	Similarity sim = new DefaultSimilarity();
+	
+	for (int i=0; i<ITER ; i++) {
+	  DisjunctionMaxScorer scorer = new DisjunctionMaxScorer(0.0f,sim);
+	  for (OpenBitSet set : bs)
+	  {
+		scorer.add(new IteratorScorer(sim,new OpenBitSetIterator(set)));
+	  }
+	  
+	  long start = System.currentTimeMillis();
+	  doIter(scorer);
+	  long end = System.currentTimeMillis();
+	  total+=(end-start);
+	  System.out.println("DisjunctionMaxScorer  milliseconds="+(end-start));
+	}
+	System.out.println("DisjunctionMaxScorer total milliseconds="+total);
+	return total;
+  }
+  
+  public long testNewOrIterator(List<OpenBitSet> bs) throws IOException{
+	long total=0;
+	final Similarity sim = new DefaultSimilarity();
+	
+	for (int i=0; i<ITER ; i++) {
+	  ArrayList<DocIdSet> scorerList = new ArrayList<DocIdSet>(bs.size());
+	  for (final OpenBitSet set : bs)
+	  {		  
+		scorerList.add(new DocIdSet(){
+			@Override
+			public DocIdSetIterator iterator() {
+				return new  IteratorScorer(sim,new OpenBitSetIterator(set));	// no need to wrapper for Scorer, but to make test comparable
+			}
+			
+		});
+	  }
+	  OrDocIdSetIterator scorer = new OrDocIdSetIterator(scorerList);
+	  long start = System.currentTimeMillis();
+	  doIter(scorer);
+	  long end = System.currentTimeMillis();
+	  total+=(end-start);
+	  System.out.println("OrDocIdSetIterator  milliseconds="+(end-start));
+	}
+	System.out.println("OrDocIdSetIterator total milliseconds="+total);
+	return total;
+  }
+  
+  public long testConjunctionScorer(List<OpenBitSet> bs) throws IOException{
+	long total=0;
+	Similarity sim = new DefaultSimilarity();
+	
+	for (int i=0; i<ITER ; i++) {
+	  ArrayList<Scorer> scorerList = new ArrayList<Scorer>(bs.size());
+	  for (OpenBitSet set : bs)
+	  {
+		scorerList.add(new IteratorScorer(sim,new OpenBitSetIterator(set)));
+	  }
+	  ConjunctionScorer scorer = new ConjunctionScorer(sim,scorerList);
+	  long start = System.currentTimeMillis();
+	  doIter(scorer);
+	  long end = System.currentTimeMillis();
+	  total+=(end-start);
+	  System.out.println("ConjunctionScorer  milliseconds="+(end-start));
+	}
+	System.out.println("ConjunctionScorer total milliseconds="+total);
+	return total;
+  }
+  
+  public long testNewAndIterator(List<OpenBitSet> bs) throws IOException{
+	long total=0;
+	final Similarity sim = new DefaultSimilarity();
+	
+	for (int i=0; i<ITER ; i++) {
+	  ArrayList<DocIdSet> scorerList = new ArrayList<DocIdSet>(bs.size());
+	  for (final OpenBitSet set : bs)
+	  {		  
+		scorerList.add(new DocIdSet(){
+			@Override
+			public DocIdSetIterator iterator() {
+				return new  IteratorScorer(sim,new OpenBitSetIterator(set));	// no need to wrapper for Scorer, but to make test comparable
+			}
+			
+		});
+	  }
+	  AndDocIdSetIterator scorer = new AndDocIdSetIterator(scorerList);
+	  long start = System.currentTimeMillis();
+	  doIter(scorer);
+	  long end = System.currentTimeMillis();
+	  total+=(end-start);
+	  System.out.println("AndDocIdSetIterator  milliseconds="+(end-start));
+	}
+	System.out.println("AndDocIdSetIterator total milliseconds="+total);
+	return total;
+  }
+  
+  private static class IteratorScorer extends Scorer 
+  {
+    private final DocIdSetIterator _iter;
+	public IteratorScorer(Similarity similarity,DocIdSetIterator iter) {
+		super(similarity);
+		_iter = iter;
+	}
+	
+	@Override
+	public Explanation explain(int doc) throws IOException {
+		return null;
+	}
+	
+	@Override
+	public final float score() throws IOException {
+		return 1.0f;
+	}
+	
+	@Override
+	public final int doc() {
+		return _iter.doc();
+	}
+	@Override
+	public final boolean next() throws IOException {
+		return _iter.next();
+	}
+	@Override
+	public final boolean skipTo(int target) throws IOException {
+		return _iter.skipTo(target);
+	}
+	  
+  }
+
+
+  public static void main(String[] argc) throws Exception{
+    TestIteratorPerf t = new TestIteratorPerf();
+    OpenBitSet bs = new OpenBitSet(ITERATOR_SIZE);
+    for(int i=0; i<=ITERATOR_SIZE;i++){
+      if(Math.abs(random.nextGaussian())<DENSITY) 
+        bs.set(i);
+    }
+    //System.out.println(bs.cardinality());
+    System.gc();
+    Thread.sleep(200);
+    long newT = t.testNew(bs);
+    System.gc();
+    Thread.sleep(200);
+    long oldT = t.testOld(bs);
+    
+    System.out.println("New/Old Time " + newT + "/" + oldT +" (" + 100.0f*newT/oldT +"%)");
+    
+    int numBS = 5;
+    ArrayList<OpenBitSet> bsList = new ArrayList<OpenBitSet>(numBS);
+    for (int i=0;i<numBS;++i){
+    	OpenBitSet bits = new OpenBitSet(ITERATOR_SIZE);
+        for(int k=0; k<=ITERATOR_SIZE;k++){
+          if(Math.abs(random.nextGaussian())<DENSITY) 
+        	bits.set(k);
+        }
+    	bsList.add(bits);
+    }
+    
+    System.gc();
+    Thread.sleep(200);
+    newT = t.testNewOrIterator(bsList);
+    System.gc();
+    Thread.sleep(200);
+    oldT = t.testDisjunctionMaxScorer(bsList);
+    
+    System.out.println("Or/DisjunctionMax Time " + newT + "/" + oldT +" (" + 100.0f*newT/oldT +"%)");
+    
+    System.gc();
+    Thread.sleep(200);
+    newT = t.testNewOrIterator(bsList);
+    System.gc();
+    Thread.sleep(200);
+    oldT = t.testDisjunctionSumScorer(bsList);
+    
+    System.out.println("Or/DisjunctionSum Time " + newT + "/" + oldT +" (" + 100.0f*newT/oldT +"%)");
+    
+    System.gc();
+    Thread.sleep(200);
+    newT = t.testNewAndIterator(bsList);
+    System.gc();
+    Thread.sleep(200);
+    oldT = t.testConjunctionScorer(bsList);
+    
+    System.out.println("And/Conjunction Time " + newT + "/" + oldT +" (" + 100.0f*newT/oldT +"%)");
+  }
+
+}
Index: src/java/org/apache/lucene/util/OpenBitSetIteratorExperiment.java
===================================================================
--- src/java/org/apache/lucene/util/OpenBitSetIteratorExperiment.java	(revision 0)
+++ src/java/org/apache/lucene/util/OpenBitSetIteratorExperiment.java	(revision 0)
@@ -0,0 +1,160 @@
+/**
+ * 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;
+
+
+/** An iterator to iterate over set bits in an OpenBitSet.
+ * This is faster than nextSetBit() for iterating over the complete set of bits,
+ * especially when the density of the bits set is high.
+ *
+ * @version $Id$
+ */
+public class OpenBitSetIteratorExperiment  {
+
+  // The General Idea: instead of having an array per byte that has
+  // the offsets of the next set bit, that array could be
+  // packed inside a 32 bit integer (8 4 bit numbers).  That
+  // should be faster than accessing an array for each index, and
+  // the total array size is kept smaller (256*sizeof(int))=1K
+  protected final static int[] bitlist={
+    0x0,0x1,0x2,0x21,0x3,0x31,0x32,0x321,0x4,0x41,0x42,0x421,0x43,0x431,0x432,0x4321,0x5,0x51,0x52,0x521,0x53,0x531,0x532,0x5321,0x54,0x541,0x542,0x5421,0x543,0x5431,0x5432,0x54321,0x6,0x61,0x62,0x621,0x63,0x631,0x632,0x6321,0x64,0x641,0x642,0x6421,0x643,0x6431,0x6432,0x64321,0x65,0x651,0x652,0x6521,0x653,0x6531,0x6532,0x65321,0x654,0x6541,0x6542,0x65421,0x6543,0x65431,0x65432,0x654321,0x7,0x71,0x72,0x721,0x73,0x731,0x732,0x7321,0x74,0x741,0x742,0x7421,0x743,0x7431,0x7432,0x74321,0x75,0x751,0x752,0x7521,0x753,0x7531,0x7532,0x75321,0x754,0x7541,0x7542,0x75421,0x7543,0x75431,0x75432,0x754321,0x76,0x761,0x762,0x7621,0x763,0x7631,0x7632,0x76321,0x764,0x7641,0x7642,0x76421,0x7643,0x76431,0x76432,0x764321,0x765,0x7651,0x7652,0x76521,0x7653,0x76531,0x76532,0x765321,0x7654,0x76541,0x76542,0x765421,0x76543,0x765431,0x765432,0x7654321,0x8,0x81,0x82,0x821,0x83,0x831,0x832,0x8321,0x84,0x841,0x842,0x8421,0x843,0x8431,0x8432,0x84321,0x85,0x851,0x852,0x8521,0x853,0x8531,0x8532,0x85321,0x854,0x8541,0x8542,0x85421,0x8543,0x85431,0x85432,0x854321,0x86,0x861,0x862,0x8621,0x863,0x8631,0x8632,0x86321,0x864,0x8641,0x8642,0x86421,0x8643,0x86431,0x86432,0x864321,0x865,0x8651,0x8652,0x86521,0x8653,0x86531,0x86532,0x865321,0x8654,0x86541,0x86542,0x865421,0x86543,0x865431,0x865432,0x8654321,0x87,0x871,0x872,0x8721,0x873,0x8731,0x8732,0x87321,0x874,0x8741,0x8742,0x87421,0x8743,0x87431,0x87432,0x874321,0x875,0x8751,0x8752,0x87521,0x8753,0x87531,0x87532,0x875321,0x8754,0x87541,0x87542,0x875421,0x87543,0x875431,0x875432,0x8754321,0x876,0x8761,0x8762,0x87621,0x8763,0x87631,0x87632,0x876321,0x8764,0x87641,0x87642,0x876421,0x87643,0x876431,0x876432,0x8764321,0x8765,0x87651,0x87652,0x876521,0x87653,0x876531,0x876532,0x8765321,0x87654,0x876541,0x876542,0x8765421,0x876543,0x8765431,0x8765432,0x87654321
+  };
+  /***** the python code that generated bitlist
+  def bits2int(val):
+  arr=0
+  for shift in range(8,0,-1):
+    if val & 0x80:
+      arr = (arr << 4) | shift
+    val = val << 1
+  return arr
+
+  def int_table():
+    tbl = [ hex(bits2int(val)).strip('L') for val in range(256) ]
+    return ','.join(tbl)
+  ******/
+
+  // hmmm, what about an iterator that finds zeros though,
+  // or a reverse iterator... should they be separate classes
+  // for efficiency, or have a common root interface?  (or
+  // maybe both?  could ask for a SetBitsIterator, etc...
+
+
+  private final long[] arr;
+  private final int words;
+  private int i=-1;
+  private long word;
+  private int wordShift;
+  private int indexArray;
+
+  public OpenBitSetIteratorExperiment(OpenBitSet obs) {
+    this(obs.getBits(), obs.getNumWords());
+  }
+
+  public OpenBitSetIteratorExperiment(long[] bits, int numWords) {
+    arr = bits;
+    words = numWords;
+  }
+
+  // 64 bit shifts
+  private void shift() {
+    if ((int)word ==0) {wordShift +=32; word = word >>>32; }
+    if ((word & 0x0000FFFF) == 0) { wordShift +=16; word >>>=16; }
+    if ((word & 0x000000FF) == 0) { wordShift +=8; word >>>=8; }
+    indexArray = bitlist[(int)word & 0xff];
+  }
+
+  /***** alternate shift implementations
+  // 32 bit shifts, but a long shift needed at the end
+  private void shift2() {
+    int y = (int)word;
+    if (y==0) {wordShift +=32; y = (int)(word >>>32); }
+    if ((y & 0x0000FFFF) == 0) { wordShift +=16; y>>>=16; }
+    if ((y & 0x000000FF) == 0) { wordShift +=8; y>>>=8; }
+    indexArray = bitlist[y & 0xff];
+    word >>>= (wordShift +1);
+  }
+
+  private void shift3() {
+    int lower = (int)word;
+    int lowByte = lower & 0xff;
+    if (lowByte != 0) {
+      indexArray=bitlist[lowByte];
+      return;
+    }
+    shift();
+  }
+  ******/
+
+  public int next(){
+    if (indexArray==0) {
+      if (word!=0) {
+        word >>>= 8;
+        wordShift += 8;
+      }
+
+      while (word==0) {
+        if (++i >= words) {
+          return -1;
+        }
+        word = arr[i];
+        wordShift =-1;  // loop invariant code motion should move this
+      }
+
+      // after the first time, should I go with a linear search, or
+      // stick with the binary search in shift?
+      shift();
+    }
+
+    int bitIndex = (indexArray & 0x0f) + wordShift;
+    indexArray >>>= 4;
+    // should i<<6 be cached as a separate variable?
+    // it would only save one cycle in the best circumstances.
+    return (i<<6) + bitIndex;
+  }
+
+  public int skipTo(int target) {
+    indexArray=0;
+    i = target >> 6;
+    if (i>=words) {
+      word =0; // setup so next() will also return -1
+      return -1;
+    }
+    wordShift = target & 0x3f;
+    word = arr[i] >>> wordShift;
+    if (word !=0) {
+      wordShift--; // compensate for 1 based arrIndex
+    } else {
+      while (word ==0) {
+        if (++i >= words) {
+          return -1;
+        }
+        word = arr[i];
+      }
+      wordShift =-1;
+    }
+
+    shift();
+
+    int bitIndex = (indexArray & 0x0f) + wordShift;
+    indexArray >>>= 4;
+    // should i<<6 be cached as a separate variable?
+    // it would only save one cycle in the best circumstances.
+    return (i<<6) + bitIndex;
+  }
+  
+}
Index: src/test/org/apache/lucene/search/docsets/AndDocIdSet.java
===================================================================
--- src/test/org/apache/lucene/search/docsets/AndDocIdSet.java	(revision 0)
+++ src/test/org/apache/lucene/search/docsets/AndDocIdSet.java	(revision 0)
@@ -0,0 +1,28 @@
+package org.apache.lucene.search.docsets;
+
+import java.io.Serializable;
+import java.util.List;
+
+import org.apache.lucene.search.DocIdSet;
+import org.apache.lucene.search.DocIdSetIterator;
+
+public class AndDocIdSet extends DocIdSet implements Serializable {
+  private static final long serialVersionUID = 1L;
+
+  private List<DocIdSet> _sets = null;
+  
+  public AndDocIdSet(List<DocIdSet> docSets) {
+    this._sets = docSets;
+    int size = 0;
+    if (_sets != null) {
+      for(DocIdSet set : _sets) {
+        if(set != null) size++;
+      }
+    }
+  }
+
+  public final DocIdSetIterator iterator() {
+    //return new AndDocIdSetIterator(_sets);
+	  return new AndDocIdSetIterator(_sets);
+  }
+}
Index: src/test/org/apache/lucene/search/docsets/AndDocIdSetIterator.java
===================================================================
--- src/test/org/apache/lucene/search/docsets/AndDocIdSetIterator.java	(revision 0)
+++ src/test/org/apache/lucene/search/docsets/AndDocIdSetIterator.java	(revision 0)
@@ -0,0 +1,105 @@
+package org.apache.lucene.search.docsets;
+
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+import org.apache.lucene.search.DocIdSet;
+import org.apache.lucene.search.DocIdSetIterator;
+
+public final class AndDocIdSetIterator extends DocIdSetIterator {
+	private DocIdSetIterator[] iterators = null;
+    private boolean firstTime=true;
+    private boolean more;
+    private int lastDoc=-1;
+    private int lastindex;
+
+    public AndDocIdSetIterator(List<DocIdSet> sets) {
+    	iterators = new DocIdSetIterator[sets.size()];
+        int j = 0;
+        for (DocIdSet set : sets) {
+          if (set != null) {
+            DocIdSetIterator dcit = set.iterator();
+            iterators[j++] = dcit;
+          }
+        }
+        lastindex=iterators.length - 1;
+    }
+    
+    private final boolean doNext() throws IOException {
+	    int first=0;
+	    DocIdSetIterator lastIter = iterators[lastindex];
+	    DocIdSetIterator firstIter;
+	    while (more && (firstIter=iterators[first]).doc() < (lastDoc=lastIter.doc())) {
+	      more = firstIter.skipTo(lastDoc);
+	      lastIter = firstIter;
+	      first = (first == (lastindex)) ? 0 : first+1;
+	    }
+	    return more;
+	  }
+    
+	@Override
+	public final int doc() {
+		return lastDoc;
+	}
+
+	@Override
+	public final boolean next() throws IOException {
+		if (firstTime)
+	      return init(0);
+	    else if (more)
+	      more = iterators[lastindex].next();
+	    return doNext();
+	}
+	
+	// Note... most of this could be done in the constructor
+	  // thus skipping a check for firstTime per call to next() and skipTo()
+	  private final boolean init(int target) throws IOException {
+	    firstTime=false;
+	    more = iterators.length>1;
+	    for (int i=0; i<iterators.length; i++) {
+	      more = target==0 ? iterators[i].next() : iterators[i].skipTo(target);
+	      if (!more)
+	        return false;
+	    }
+
+	    // Sort the array the first time...
+	    // We don't need to sort the array in any future calls because we know
+	    // it will already start off sorted (all scorers on same doc).
+
+	    // note that this comparator is not consistent with equals!
+	    Arrays.sort(iterators, new Comparator<DocIdSetIterator>() {         // sort the array
+	        public int compare(DocIdSetIterator o1, DocIdSetIterator o2) {
+	          return o1.doc() - o2.doc();
+	        }
+	      });
+
+	    doNext();
+
+	    // If first-time skip distance is any predictor of
+	    // scorer sparseness, then we should always try to skip first on
+	    // those scorers.
+	    // Keep last scorer in it's last place (it will be the first
+	    // to be skipped on), but reverse all of the others so that
+	    // they will be skipped on in order of original high skip.
+	    int end=lastindex;
+	    for (int i=0; i<(end>>1); i++) {
+	      DocIdSetIterator tmp = iterators[i];
+	      iterators[i] = iterators[end-i-1];
+	      iterators[end-i-1] = tmp;
+	    }
+
+	    return more;
+	  }
+
+	@Override
+	public boolean skipTo(int target) throws IOException {
+		if (firstTime)
+	      return init(target);
+	    else if (more)
+	      more = iterators[lastindex].skipTo(target);
+	    return doNext();
+	}
+
+}
Index: src/test/org/apache/lucene/search/docsets/NotDocIdSet.java
===================================================================
--- src/test/org/apache/lucene/search/docsets/NotDocIdSet.java	(revision 0)
+++ src/test/org/apache/lucene/search/docsets/NotDocIdSet.java	(revision 0)
@@ -0,0 +1,27 @@
+package org.apache.lucene.search.docsets;
+
+import java.io.Serializable;
+
+import org.apache.lucene.search.DocIdSet;
+import org.apache.lucene.search.DocIdSetIterator;
+
+
+public class NotDocIdSet extends DocIdSet implements Serializable {
+
+  private static final long serialVersionUID = 1L;
+
+  private DocIdSet innerSet = null;
+
+  private int max = -1;
+
+  public NotDocIdSet(DocIdSet docSet, int maxVal) {
+	innerSet = docSet;
+    max = maxVal;
+   
+  }
+
+  @Override
+  public DocIdSetIterator iterator() {
+    return new NotDocIdSetIterator(innerSet,max);
+  }
+}
Index: src/test/org/apache/lucene/search/docsets/NotDocIdSetIterator.java
===================================================================
--- src/test/org/apache/lucene/search/docsets/NotDocIdSetIterator.java	(revision 0)
+++ src/test/org/apache/lucene/search/docsets/NotDocIdSetIterator.java	(revision 0)
@@ -0,0 +1,63 @@
+package org.apache.lucene.search.docsets;
+
+import java.io.IOException;
+
+import org.apache.lucene.search.DocIdSet;
+import org.apache.lucene.search.DocIdSetIterator;
+
+public  class NotDocIdSetIterator extends DocIdSetIterator {
+    int lastReturn = -1;
+    private DocIdSetIterator it1 = null;
+    private final DocIdSet innerSet;
+    private final int max;
+    public NotDocIdSetIterator(DocIdSet set,int max) {
+      innerSet = set;
+      this.max = max;
+      initialize();
+    }
+
+    private void initialize() {
+      it1 = innerSet.iterator();
+
+      try {
+        if (!it1.next()) it1 = null;
+      } catch (IOException e) {
+        e.printStackTrace();
+      }
+    }
+
+    @Override
+    public int doc() {
+      return lastReturn;
+    }
+
+    @Override
+    public boolean next() throws IOException {
+      return skipTo(lastReturn + 1);
+    }
+
+    @Override
+    public boolean skipTo(int target) throws IOException {
+      
+      if (target <= lastReturn) target = lastReturn + 1;
+      
+      lastReturn = target;
+      
+      if (lastReturn >= max) return false;
+
+      if (it1 != null && it1.doc() < lastReturn) {
+        if (!it1.skipTo(lastReturn)) {
+          it1 = null;
+        }
+      }
+      
+      while (it1 != null && it1.doc() == lastReturn) {
+        lastReturn++;
+        if (lastReturn >= max) return false;
+        if (!it1.skipTo(lastReturn)) {
+          it1 = null;
+        }
+      }
+      return true;
+    }
+  }
\ No newline at end of file
Index: src/test/org/apache/lucene/search/docsets/OrDocIdSet.java
===================================================================
--- src/test/org/apache/lucene/search/docsets/OrDocIdSet.java	(revision 0)
+++ src/test/org/apache/lucene/search/docsets/OrDocIdSet.java	(revision 0)
@@ -0,0 +1,29 @@
+package org.apache.lucene.search.docsets;
+
+import java.io.Serializable;
+import java.util.List;
+
+import org.apache.lucene.search.DocIdSet;
+import org.apache.lucene.search.DocIdSetIterator;
+
+
+public class OrDocIdSet extends DocIdSet implements Serializable {
+  private static final long serialVersionUID = 1L;
+
+  private List<DocIdSet> sets = null;
+  
+  public OrDocIdSet(List<DocIdSet> docSets) {
+    this.sets = docSets;
+    int size = 0;
+    if (sets != null) {
+      for(DocIdSet set : sets) {
+        if(set != null) size++;
+      }
+    }
+  }
+  
+  @Override
+  public DocIdSetIterator iterator() {
+    return new OrDocIdSetIterator(sets);
+  }
+}
Index: src/test/org/apache/lucene/search/docsets/OrDocIdSetIterator.java
===================================================================
--- src/test/org/apache/lucene/search/docsets/OrDocIdSetIterator.java	(revision 0)
+++ src/test/org/apache/lucene/search/docsets/OrDocIdSetIterator.java	(revision 0)
@@ -0,0 +1,156 @@
+package org.apache.lucene.search.docsets;
+
+import java.io.IOException;
+import java.util.List;
+
+import org.apache.lucene.search.DocIdSet;
+import org.apache.lucene.search.DocIdSetIterator;
+
+public class OrDocIdSetIterator extends DocIdSetIterator {
+
+  private final class Item
+  {
+    public final DocIdSetIterator iter;
+    public int doc;
+    public Item(DocIdSetIterator iter)
+    {
+      this.iter = iter;
+      this.doc = -1;
+    }
+  }
+  private int _curDoc;
+  private final Item[] _heap;
+  private int _size;
+ 
+  public OrDocIdSetIterator(List<DocIdSet> sets)
+  {
+    _curDoc = -1;
+    _heap = new Item[sets.size()];
+    _size = 0;
+    for(DocIdSet set : sets)
+    {
+      _heap[_size++] = new Item(set.iterator());
+    }
+  }
+  
+  @Override
+  public final int doc() {
+    return _curDoc;
+  }
+
+  @Override
+  public final boolean next() throws IOException
+  {
+    if(_size <= 0) return false;
+
+    Item top = _heap[0];
+    while(true)
+    {
+      DocIdSetIterator topIter = top.iter;
+      if(topIter.next())
+      {
+        top.doc = topIter.doc();
+        heapAdjust();
+      }
+      else
+      {
+        heapRemoveRoot();
+        if(_size == 0) return false;
+      }
+      top = _heap[0];
+      int topDoc = top.doc;
+      if(topDoc > _curDoc)
+      {
+        _curDoc = topDoc;
+        return true;
+      }
+    }
+  }
+
+  @Override
+  public final boolean skipTo(int target) throws IOException
+  {
+    if(_size <= 0) return false;
+
+    if(target <= _curDoc) target = _curDoc + 1;
+     
+    Item top = _heap[0];
+    while(true)
+    {
+      DocIdSetIterator topIter = top.iter;
+      if(topIter.skipTo(target))
+      {
+        top.doc = topIter.doc();
+        heapAdjust();
+      }
+      else
+      {
+        heapRemoveRoot();
+        if (_size == 0) return false;
+      }
+      top = _heap[0];
+      int topDoc = top.doc;
+      if(topDoc >= target)
+      {
+        _curDoc = topDoc;
+        return true;
+      }
+    }
+  }
+  
+  /* The subtree of subScorers at root is a min heap except possibly for its root element.
+   * Bubble the root down as required to make the subtree a heap.
+   */
+  private final void heapAdjust()
+  {
+    final Item[] heap = _heap;
+    final Item top = heap[0];
+    final int doc = top.doc;
+    final int size = _size;
+    int i = 0;
+    
+    while(true)
+    {
+      int lchild = (i<<1)+1;
+      if(lchild >= size) break;
+      
+      Item left = heap[lchild];
+      int ldoc = left.doc;
+      
+      int rchild = lchild+1;
+      if(rchild < size){
+        Item right = heap[rchild];
+        int rdoc = right.doc;
+        
+        if(rdoc <= ldoc)
+        {
+          if(doc <= rdoc) break;
+          
+          heap[i] = right;
+          i = rchild;
+          continue;
+        }
+      }
+      
+      if(doc <= ldoc) break;
+      
+      heap[i] = left;
+      i = lchild;
+    }
+    heap[i] = top;
+  }
+
+  // Remove the root Scorer from subScorers and re-establish it as a heap
+  private final void heapRemoveRoot()
+  {
+    _size--;
+    if (_size > 0)
+    {
+      Item tmp = _heap[0];
+      _heap[0] = _heap[_size];
+      _heap[_size] = tmp; // keep the finished iterator at the end for debugging
+      heapAdjust();
+    }
+  }
+
+}