lucene/core/src/java/org/apache/lucene/search/DocIdSetIterator.java

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

/**
 * This abstract class defines methods to iterate over a set of non-decreasing doc ids. Note that
 * this class assumes it iterates on doc Ids, and therefore {@link #NO_MORE_DOCS} is set to {@value
 * #NO_MORE_DOCS} in order to be used as a sentinel object. Implementations of this class are
 * expected to consider {@link Integer#MAX_VALUE} as an invalid value.
 */
public abstract class DocIdSetIterator {

  /** An empty {@code DocIdSetIterator} instance */
  public static final DocIdSetIterator empty() {
    return new DocIdSetIterator() {
      boolean exhausted = false;

      @Override
      public int advance(int target) {
        assert !exhausted;
        assert target >= 0;
        exhausted = true;
        return NO_MORE_DOCS;
      }

      @Override
      public int docID() {
        return exhausted ? NO_MORE_DOCS : -1;
      }

      @Override
      public int nextDoc() {
        assert !exhausted;
        exhausted = true;
        return NO_MORE_DOCS;
      }

      @Override
      public long cost() {
        return 0;
      }
    };
  }

  /** A {@link DocIdSetIterator} that matches all documents up to {@code maxDoc - 1}. */
  public static final DocIdSetIterator all(int maxDoc) {
    return new DocIdSetIterator() {
      int doc = -1;

      @Override
      public int docID() {
        return doc;
      }

      @Override
      public int nextDoc() throws IOException {
        return advance(doc + 1);
      }

      @Override
      public int advance(int target) throws IOException {
        doc = target;
        if (doc >= maxDoc) {
          doc = NO_MORE_DOCS;
        }
        return doc;
      }

      @Override
      public long cost() {
        return maxDoc;
      }
    };
  }

  /**
   * A {@link DocIdSetIterator} that matches a range documents from minDocID (inclusive) to maxDocID
   * (exclusive).
   */
  public static final DocIdSetIterator range(int minDoc, int maxDoc) {
    if (minDoc >= maxDoc) {
      throw new IllegalArgumentException(
          "minDoc must be < maxDoc but got minDoc=" + minDoc + " maxDoc=" + maxDoc);
    }
    if (minDoc < 0) {
      throw new IllegalArgumentException("minDoc must be >= 0 but got minDoc=" + minDoc);
    }
    return new DocIdSetIterator() {
      private int doc = -1;

      @Override
      public int docID() {
        return doc;
      }

      @Override
      public int nextDoc() throws IOException {
        return advance(doc + 1);
      }

      @Override
      public int advance(int target) throws IOException {
        if (target < minDoc) {
          doc = minDoc;
        } else if (target >= maxDoc) {
          doc = NO_MORE_DOCS;
        } else {
          doc = target;
        }
        return doc;
      }

      @Override
      public long cost() {
        return maxDoc - minDoc;
      }
    };
  }

  /**
   * When returned by {@link #nextDoc()}, {@link #advance(int)} and {@link #docID()} it means there
   * are no more docs in the iterator.
   */
  public static final int NO_MORE_DOCS = Integer.MAX_VALUE;

  /**
   * Returns the following:
   *
   * <ul>
   *   <li><code>-1</code> if {@link #nextDoc()} or {@link #advance(int)} were not called yet.
   *   <li>{@link #NO_MORE_DOCS} if the iterator has exhausted.
   *   <li>Otherwise it should return the doc ID it is currently on.
   * </ul>
   *
   * @since 2.9
   */
  public abstract int docID();

  /**
   * Advances to the next document in the set and returns the doc it is currently on, or {@link
   * #NO_MORE_DOCS} if there are no more docs in the set.<br>
   * <b>NOTE:</b> after the iterator has exhausted you should not call this method, as it may result
   * in unpredicted behavior.
   *
   * @since 2.9
   */
  public abstract int nextDoc() throws IOException;

  /**
   * Advances to the first beyond the current whose document number is greater than or equal to
   * <i>target</i>, and returns the document number itself. Exhausts the iterator and returns {@link
   * #NO_MORE_DOCS} if <i>target</i> is greater than the highest document number in the set.
   *
   * <p>The behavior of this method is <b>undefined</b> when called with <code> target &le; current
   * </code>, or after the iterator has exhausted. Both cases may result in unpredicted behavior.
   *
   * <p>When <code> target &gt; current</code> it behaves as if written:
   *
   * <pre class="prettyprint">
   * int advance(int target) {
   *   int doc;
   *   while ((doc = nextDoc()) &lt; target) {
   *   }
   *   return doc;
   * }
   * </pre>
   *
   * Some implementations are considerably more efficient than that.
   *
   * <p><b>NOTE:</b> this method may be called with {@link #NO_MORE_DOCS} for efficiency by some
   * Scorers. If your implementation cannot efficiently determine that it should exhaust, it is
   * recommended that you check for that value in each call to this method.
   *
   * @since 2.9
   */
  public abstract int advance(int target) throws IOException;

  /**
   * Slow (linear) implementation of {@link #advance} relying on {@link #nextDoc()} to advance
   * beyond the target position.
   */
  protected final int slowAdvance(int target) throws IOException {
    assert docID() < target;
    int doc;
    do {
      doc = nextDoc();
    } while (doc < target);
    return doc;
  }

  /**
   * Returns the estimated cost of this {@link DocIdSetIterator}.
   *
   * <p>This is generally an upper bound of the number of documents this iterator might match, but
   * may be a rough heuristic, hardcoded value, or otherwise completely inaccurate.
   */
  public abstract long cost();
}