content: package org.apache.solr.util;
  /**
   * 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.
   */
  
  /** 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));
    }
  }
  