solr/core/src/java/org/apache/solr/util/PrimUtils.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.solr.util;
/** Utilities for primitive Java data types. */
public class PrimUtils {

  public static abstract class IntComparator {
    public abstract int compare(int a, int b);
    public boolean lessThan(int a, int b) {
      return compare(a,b) < 0;
    }
    public boolean equals(int a, int b) {
      return compare(a,b) == 0;
    }
  }

  /** Sort the integer array from "start" inclusive to "end" exclusive in ascending order,
   *  using the provided comparator.
   * TODO: is this an unstable sort?
   */
  public static void sort(int start, int end, int[] array, IntComparator comparator) {
    // This code was copied from Apache Harmony's Arrays.sort(double[]) and modified
    // to use a comparator, in addition to other small efficiency enhancements
    // like replacing divisions with shifts.

    int temp;
    int length = end - start;
    if (length < 7) {
      for (int i = start + 1; i < end; i++) {
        for (int j = i; j > start && comparator.lessThan(array[j], array[j - 1]); j--) {
          temp = array[j];
          array[j] = array[j - 1];
          array[j - 1] = temp;
        }
      }
      return;
    }
    int middle = (start + end) >>> 1;
    if (length > 7) {
      int bottom = start;
      int top = end - 1;
      if (length > 40) {
        length >>= 3;
        bottom = med3(array, bottom, bottom + length, bottom
            + (length<<1), comparator);
        middle = med3(array, middle - length, middle, middle + length, comparator);
        top = med3(array, top - (length<<1), top - length, top, comparator);
      }
      middle = med3(array, bottom, middle, top, comparator);
    }
    int partionValue = array[middle];
    int a, b, c, d;
    a = b = start;
    c = d = end - 1;
    while (true) {
      while (b <= c && !comparator.lessThan(partionValue, array[b])) {
        if (comparator.equals(array[b], partionValue)) {
          temp = array[a];
          array[a++] = array[b];
          array[b] = temp;
        }
        b++;
      }
      while (c >= b && !comparator.lessThan(array[c], partionValue)) {
        if (comparator.equals(array[c], partionValue)) {
          temp = array[c];
          array[c] = array[d];
          array[d--] = temp;
        }
        c--;
      }
      if (b > c) {
        break;
      }
      temp = array[b];
      array[b++] = array[c];
      array[c--] = temp;
    }
    length = a - start < b - a ? a - start : b - a;
    int l = start;
    int h = b - length;
    while (length-- > 0) {
      temp = array[l];
      array[l++] = array[h];
      array[h++] = temp;
    }
    length = d - c < end - 1 - d ? d - c : end - 1 - d;
    l = b;
    h = end - length;
    while (length-- > 0) {
      temp = array[l];
      array[l++] = array[h];
      array[h++] = temp;
    }
    if ((length = b - a) > 0) {
      sort(start, start + length, array, comparator);
    }
    if ((length = d - c) > 0) {
      sort(end - length, end, array, comparator);
    }
  }

  private static int med3(int[] array, int a, int b, int c, IntComparator comparator) {
    int x = array[a], y = array[b], z = array[c];
    return comparator.lessThan(x, y) ? (comparator.lessThan(y, z) ? b : (comparator.lessThan(x, z) ? c : a))
        : (comparator.lessThan(z, y) ? b : (comparator.lessThan(z, x) ? c : a));
  }
}