Class SortedIntDocSet

solr/core/src/java/org/apache/solr/search/SortedIntDocSet.java:32–787

A simple sorted int[] array implementation of DocSet, good for small sets.

/** A simple sorted int[] array implementation of {@link DocSet}, good for small sets. */
public class SortedIntDocSet extends DocSet {
  private static final long BASE_RAM_BYTES_USED =
      RamUsageEstimator.shallowSizeOfInstance(SortedIntDocSet.class)
          + RamUsageEstimator.NUM_BYTES_ARRAY_HEADER;

  protected final int[] docs;

  /**
   * @param docs Sorted list of ids
   */
  public SortedIntDocSet(int[] docs) {
    this.docs = docs;
  }

  /**
   * @param docs Sorted list of ids
   * @param len Number of ids in the list
   */
  public SortedIntDocSet(int[] docs, int len) {
    this(shrink(docs, len));
  }

  public int[] getDocs() {
    return docs;
  }

  @Override
  public int size() {
    return docs.length;
  }

  public static int[] zeroInts = new int[0];
  public static SortedIntDocSet zero = new SortedIntDocSet(zeroInts);

  public static int[] shrink(int[] arr, int newSize) {
    if (arr.length == newSize) return arr;
    int[] newArr = new int[newSize];
    System.arraycopy(arr, 0, newArr, 0, newSize);
    return newArr;
  }

  public static int intersectionSize(int[] smallerSortedList, int[] biggerSortedList) {
    final int a[] = smallerSortedList;
    final int b[] = biggerSortedList;

    // The next doc we are looking for will be much closer to the last position we tried
    // than it will be to the midpoint between last and high... so probe ahead using
    // a function of the ratio of the sizes of the sets.
    int step = (b.length / a.length) + 1;

    // Since the majority of probes should be misses, we'll already be above the last probe
    // and shouldn't need to move larger than the step size on average to step over our target (and
    // thus lower the high upper bound a lot.)... but if we don't go over our target, it's a big
    // miss... so double it.
    step = step + step;

    // FUTURE: come up with a density such that target * density == likely position?
    // then check step on one side or the other?