/*
 * 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.calcite.runtime;

import org.apache.calcite.linq4j.function.Function1;
import org.apache.calcite.linq4j.function.Functions;

import java.util.Comparator;

/**
 * Binary search for the implementation of
 * RANGE BETWEEN XXX PRECEDING/FOLLOWING clause.
 *
 */
public class BinarySearch {
  // Even though this is a utility class (all methods are static), we cannot
  // make the constructor private. Because Janino doesn't do static import,
  // generated code is placed in sub-classes.
  protected BinarySearch() {
  }

  /**
   * Performs binary search of the lower bound in the given array.
   * It is assumed that the array is sorted.
   * The method is guaranteed to return the minimal index of the element that is
   * greater or equal to the given key.
   *
   * @param a array that holds the values
   * @param key element to look for
   * @param comparator comparator that compares keys
   * @param <T> the type of elements in array
   * @return minimal index of the element that is
   *   greater or equal to the given key. Returns -1 when all elements exceed
   *   the given key or the array is empty. Returns {@code a.length} when all
   *   elements are less than the given key.
   */
  public static <T> int lowerBound(T[] a, T key, Comparator<T> comparator) {
    return lowerBound(a, key, 0, a.length - 1,
        Functions.identitySelector(), comparator);
  }

  /**
   * Performs binary search of the upper bound in the given array.
   * It is assumed that the array is sorted.
   * The method is guaranteed to return the maximal index of the element that is
   * less or equal to the given key.
   *
   * @param a array that holds the values
   * @param key element to look for
   * @param comparator comparator that compares keys
   * @param <T> the type of elements in array
   * @return maximal index of the element that is
   *   less or equal to the given key. Returns -1 when all elements are less
   *   than the given key or the array is empty. Returns {@code a.length} when
   *   all elements exceed the given key.
   */
  public static <T> int upperBound(T[] a, T key, Comparator<T> comparator) {
    return upperBound(a, key, 0, a.length - 1,
        Functions.identitySelector(), comparator);
  }

  /**
   * Performs binary search of the lower bound in the given array.
   * The elements in the array are transformed before the comparison.
   * It is assumed that the array is sorted.
   * The method is guaranteed to return the minimal index of the element that is
   * greater or equal to the given key.
   *
   * @param a array that holds the values
   * @param key element to look for
   * @param keySelector function that transforms array contents to the type
   *                    of the key
   * @param comparator comparator that compares keys
   * @param <T> the type of elements in array
   * @param <K> the type of lookup key
   * @return minimal index of the element that is
   *   greater or equal to the given key. Returns -1 when all elements exceed
   *   the given key or the array is empty. Returns {@code a.length} when all
   *   elements are less than the given key.
   */
  public static <T, K> int lowerBound(T[] a, K key, Function1<T, K> keySelector,
      Comparator<K> comparator) {
    return lowerBound(a, key, 0, a.length - 1, keySelector, comparator);
  }

  /**
   * Performs binary search of the upper bound in the given array.
   * The elements in the array are transformed before the comparison.
   * It is assumed that the array is sorted.
   * The method is guaranteed to return the maximal index of the element that is
   * less or equal to the given key.
   *
   * @param a array that holds the values
   * @param key element to look for
   * @param keySelector function that transforms array contents to the type
   *                    of the key
   * @param comparator comparator that compares keys
   * @param <T> the type of elements in array
   * @param <K> the type of lookup key
   * @return maximal index of the element that is
   *   less or equal to the given key. Returns -1 when all elements are less
   *   than the given key or the array is empty. Returns {@code a.length} when
   *   all elements exceed the given key.
   */
  public static <T, K> int upperBound(T[] a, K key, Function1<T, K> keySelector,
      Comparator<K> comparator) {
    return upperBound(a, key, 0, a.length - 1, keySelector, comparator);
  }

  /**
   * Performs binary search of the lower bound in the given section of array.
   * It is assumed that the array is sorted.
   * The method is guaranteed to return the minimal index of the element that is
   * greater or equal to the given key.
   *
   * @param a array that holds the values
   * @param key element to look for
   * @param imin the minimal index (inclusive) to look for
   * @param imax the maximum index (inclusive) to look for
   * @param comparator comparator that compares keys
   * @param <T> the type of elements in array
   * @return minimal index of the element that is
   *   greater or equal to the given key. Returns -1 when all elements exceed
   *   the given key or the array is empty. Returns {@code a.length} when all
   *   elements are less than the given key.
   */
  public static <T> int lowerBound(T[] a, T key, int imin, int imax,
      Comparator<T> comparator) {
    return lowerBound(a, key, imin, imax,
        Functions.identitySelector(), comparator);
  }

  /**
   * Performs binary search of the upper bound in the given array.
   * It is assumed that the array is sorted.
   * The method is guaranteed to return the maximal index of the element that is
   * less or equal to the given key.
   *
   * @param a array that holds the values
   * @param key element to look for
   * @param imin the minimal index (inclusive) to look for
   * @param imax the maximum index (inclusive) to look for
   * @param comparator comparator that compares keys
   * @param <T> the type of elements in array
   * @return maximal index of the element that is
   *   less or equal to the given key. Returns -1 when all elements are less
   *   than the given key or the array is empty. Returns {@code a.length} when
   *   all elements exceed the given key.
   */
  public static <T> int upperBound(T[] a, T key, int imin, int imax,
      Comparator<T> comparator) {
    return upperBound(a, key, imin, imax,
        Functions.identitySelector(), comparator);
  }

  /**
   * Taken from http://en.wikipedia.org/wiki/Binary_search_algorithm
   * #Deferred_detection_of_equality
   */
  public static <T, K> int lowerBound(T[] a, K key, int imin, int imax,
      Function1<T, K> keySelector, Comparator<K> comparator) {
    // continually narrow search until just one element remains
    while (imin < imax) {
      // http://bugs.java.com/bugdatabase/view_bug.do?bug_id=5045582
      int imid = (imin + imax) >>> 1;

      // code must guarantee the interval is reduced at each iteration
      assert imid < imax
          : "search interval should be reduced min=" + imin
          + ", mid=" + imid + ", max=" + imax;
      // note: 0 <= imin < imax implies imid will always be less than imax

      // reduce the search
      if (comparator.compare(keySelector.apply(a[imid]), key) < 0) {
        // change min index to search upper subarray
        imin = imid + 1;
      } else {
        imax = imid;
      }
    }
    // At exit of while:
    //   if a[] is empty, then imax < imin
    //   otherwise imax == imin

    // deferred test for equality
    if (imax != imin) {
      return -1;
    }

    int cmp = comparator.compare(keySelector.apply(a[imin]), key);
    if (cmp == 0) {
      // Detected exact match, just return it
      return imin;
    }
    if (cmp < 0) {
      // We were asked the key that is greater that all the values in array
      return imin + 1;
    }
    // If imin != 0 we return imin since a[imin-1] < key < a[imin]
    // If imin == 0 we return -1 since the resulting window might be empty
    // For instance, range between 100 preceding and 99 preceding
    // Use if-else to ensure code coverage is reported for each return
    if (imin == 0) {
      return -1;
    } else {
      return imin;
    }
  }

  /**
   * Taken from http://en.wikipedia.org/wiki/Binary_search_algorithm
   * #Deferred_detection_of_equality
   * Adapted to find upper bound.
   */
  public static <T, K> int upperBound(T[] a, K key, int imin, int imax,
      Function1<T, K> keySelector, Comparator<K> comparator) {
    int initialMax = imax;
    // continually narrow search until just one element remains
    while (imin < imax) {
      int imid = (imin + imax + 1) >>> 1;

      // code must guarantee the interval is reduced at each iteration
      assert imid > imin
          : "search interval should be reduced min=" + imin
          + ", mid=" + imid + ", max=" + imax;
      // note: 0 <= imin < imax implies imid will always be less than imax

      // reduce the search
      if (comparator.compare(keySelector.apply(a[imid]), key) > 0) {
        // change max index to search lower subarray
        imax = imid - 1;
      } else {
        imin = imid;
      }
    }
    // At exit of while:
    //   if a[] is empty, then imax < imin
    //   otherwise imax == imin

    // deferred test for equality
    if (imax != imin) {
      return -1;
    }

    int cmp = comparator.compare(keySelector.apply(a[imin]), key);
    if (cmp == 0) {
      // Detected exact match, just return it
      return imin;
    }
    if (cmp > 0) {
      // We were asked the key that is less than all the values in array
      return imin - 1;
    }
    // If imin != initialMax we return imin since a[imin-1] < key < a[imin]
    // If imin == initialMax we return initialMax+11 since
    // the resulting window might be empty
    // For instance, range between 99 following and 100 following
    // Use if-else to ensure code coverage is reported for each return
    if (imin == initialMax) {
      return initialMax + 1;
    } else {
      return imin;
    }
  }
}
