lucene/core/src/java/org/apache/lucene/util/Sorter.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.util;


import java.util.Comparator;

/** Base class for sorting algorithms implementations.
 * @lucene.internal */
public abstract class Sorter {

  static final int BINARY_SORT_THRESHOLD = 20;

  /** Below this size threshold, the sub-range is sorted using Insertion sort. */
  static final int INSERTION_SORT_THRESHOLD = 16;

  /** Sole constructor, used for inheritance. */
  protected Sorter() {}

  /** Compare entries found in slots <code>i</code> and <code>j</code>.
   *  The contract for the returned value is the same as
   *  {@link Comparator#compare(Object, Object)}. */
  protected abstract int compare(int i, int j);

  /** Swap values at slots <code>i</code> and <code>j</code>. */
  protected abstract void swap(int i, int j);

  private int pivotIndex;

  /** Save the value at slot <code>i</code> so that it can later be used as a
   * pivot, see {@link #comparePivot(int)}. */
  protected void setPivot(int i) {
    pivotIndex = i;
  }

  /** Compare the pivot with the slot at <code>j</code>, similarly to
   *  {@link #compare(int, int) compare(i, j)}. */
  protected int comparePivot(int j) {
    return compare(pivotIndex, j);
  }

  /** Sort the slice which starts at <code>from</code> (inclusive) and ends at
   *  <code>to</code> (exclusive). */
  public abstract void sort(int from, int to);

  void checkRange(int from, int to) {
    if (to < from) {
      throw new IllegalArgumentException("'to' must be >= 'from', got from=" + from + " and to=" + to);
    }
  }

  void mergeInPlace(int from, int mid, int to) {
    if (from == mid || mid == to || compare(mid - 1, mid) <= 0) {
      return;
    } else if (to - from == 2) {
      swap(mid - 1, mid);
      return;
    }
    while (compare(from, mid) <= 0) {
      ++from;
    }
    while (compare(mid - 1, to - 1) <= 0) {
      --to;
    }
    int first_cut, second_cut;
    int len11, len22;
    if (mid - from > to - mid) {
      len11 = (mid - from) >>> 1;
      first_cut = from + len11;
      second_cut = lower(mid, to, first_cut);
      len22 = second_cut - mid;
    } else {
      len22 = (to - mid) >>> 1;
      second_cut = mid + len22;
      first_cut = upper(from, mid, second_cut);
      len11 = first_cut - from;
    }
    rotate(first_cut, mid, second_cut);
    final int new_mid = first_cut + len22;
    mergeInPlace(from, first_cut, new_mid);
    mergeInPlace(new_mid, second_cut, to);
  }

  int lower(int from, int to, int val) {
    int len = to - from;
    while (len > 0) {
      final int half = len >>> 1;
      final int mid = from + half;
      if (compare(mid, val) < 0) {
        from = mid + 1;
        len = len - half -1;
      } else {
        len = half;
      }
    }
    return from;
  }

  int upper(int from, int to, int val) {
    int len = to - from;
    while (len > 0) {
      final int half = len >>> 1;
      final int mid = from + half;
      if (compare(val, mid) < 0) {
        len = half;
      } else {
        from = mid + 1;
        len = len - half -1;
      }
    }
    return from;
  }

  // faster than lower when val is at the end of [from:to[
  int lower2(int from, int to, int val) {
    int f = to - 1, t = to;
    while (f > from) {
      if (compare(f, val) < 0) {
        return lower(f, t, val);
      }
      final int delta = t - f;
      t = f;
      f -= delta << 1;
    }
    return lower(from, t, val);
  }

  // faster than upper when val is at the beginning of [from:to[
  int upper2(int from, int to, int val) {
    int f = from, t = f + 1;
    while (t < to) {
      if (compare(t, val) > 0) {
        return upper(f, t, val);
      }
      final int delta = t - f;
      f = t;
      t += delta << 1;
    }
    return upper(f, to, val);
  }

  final void reverse(int from, int to) {
    for (--to; from < to; ++from, --to) {
      swap(from, to);
    }
  }

  final void rotate(int lo, int mid, int hi) {
    assert lo <= mid && mid <= hi;
    if (lo == mid || mid == hi) {
      return;
    }
    doRotate(lo, mid, hi);
  }

  void doRotate(int lo, int mid, int hi) {
    if (mid - lo == hi - mid) {
      // happens rarely but saves n/2 swaps
      while (mid < hi) {
        swap(lo++, mid++);
      }
    } else {
      reverse(lo, mid);
      reverse(mid, hi);
      reverse(lo, hi);
    }
  }

  /**
   * A binary sort implementation. This performs {@code O(n*log(n))} comparisons
   * and {@code O(n^2)} swaps. It is typically used by more sophisticated
   * implementations as a fall-back when the number of items to sort has become
   * less than {@value #BINARY_SORT_THRESHOLD}.
   */
  void binarySort(int from, int to) {
    binarySort(from, to, from + 1);
  }

  void binarySort(int from, int to, int i) {
    for ( ; i < to; ++i) {
      setPivot(i);
      int l = from;
      int h = i - 1;
      while (l <= h) {
        final int mid = (l + h) >>> 1;
        final int cmp = comparePivot(mid);
        if (cmp < 0) {
          h = mid - 1;
        } else {
          l = mid + 1;
        }
      }
      for (int j = i; j > l; --j) {
        swap(j - 1, j);
      }
    }
  }

  /**
   * Sorts between from (inclusive) and to (exclusive) with insertion sort. Runs in {@code O(n^2)}.
   * It is typically used by more sophisticated implementations as a fall-back when the number of
   * items to sort becomes less than {@value #INSERTION_SORT_THRESHOLD}.
   */
  void insertionSort(int from, int to) {
    for (int i = from + 1; i < to; ) {
      int current = i++;
      int previous;
      while (compare((previous = current - 1), current) > 0) {
        swap(previous, current);
        if (previous == from) {
          break;
        }
        current = previous;
      }
    }
  }

  /**
   * Use heap sort to sort items between {@code from} inclusive and {@code to}
   * exclusive. This runs in {@code O(n*log(n))} and is used as a fall-back by
   * {@link IntroSorter}.
   */
  void heapSort(int from, int to) {
    if (to - from <= 1) {
      return;
    }
    heapify(from, to);
    for (int end = to - 1; end > from; --end) {
      swap(from, end);
      siftDown(from, from, end);
    }
  }

  void heapify(int from, int to) {
    for (int i = heapParent(from, to - 1); i >= from; --i) {
      siftDown(i, from, to);
    }
  }

  void siftDown(int i, int from, int to) {
    for (int leftChild = heapChild(from, i); leftChild < to; leftChild = heapChild(from, i)) {
      final int rightChild = leftChild + 1;
      if (compare(i, leftChild) < 0) {
        if (rightChild < to && compare(leftChild, rightChild) < 0) {
          swap(i, rightChild);
          i = rightChild;
        } else {
          swap(i, leftChild);
          i = leftChild;
        }
      } else if (rightChild < to && compare(i, rightChild) < 0) {
        swap(i, rightChild);
        i = rightChild;
      } else {
        break;
      }
    }
  }

  static int heapParent(int from, int i) {
    return ((i - 1 - from) >>> 1) + from;
  }

  static int heapChild(int from, int i) {
    return ((i - from) << 1) + 1 + from;
  }

}