Searches.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.commons.statistics.inference;

import java.util.function.IntToDoubleFunction;

/**
 * Search utility methods.
 *
 * @since 1.1
 */
final class Searches {
    /** Range threshold to use a binary search.
     * The binary search takes O(log(n)) so is used when n is large and a sequential
     * search is slower. */
    private static final int BINARY_SEARCH = 8;

    /** No instances. */
    private Searches() {}

    /**
     * Conduct a search between {@code a} inclusive and {@code b} inclusive
     * to find the lowest index where {@code value <= x}. The values must be
     * in <em>descending</em> order. The method is functionally equivalent to:
     * <pre>
     * {@code
     * i = b + 1
     * while (i > a AND value(i - 1) <= x)
     *    i = i - 1
     * return i
     * }</pre>
     *
     * <p>The function is only evaluated between the closed interval {@code [a, b]}.
     * Special cases:
     * <ul>
     * <li>If {@code value(a) <= x} the returned index is {@code a}.
     * <li>If {@code value(b) > x} the returned index is {@code b + 1}.
     * </ul>
     *
     * @param a Lower limit (inclusive).
     * @param b Upper limit (inclusive).
     * @param x Target value.
     * @param value Function to evaluate the value at an index.
     * @return the minimum index where {@code value(i) <= x}.
     */
    static int searchDescending(int a, int b, double x, IntToDoubleFunction value) {
        // Re-use the search for ascending order.
        // Invert the index to find the lowest for the descending order.
        final int offset = a + b;
        return offset - searchAscending(a, b, x, i -> value.applyAsDouble(offset - i));
    }

    /**
     * Conduct a search between {@code a} inclusive and {@code b} inclusive
     * to find the highest index where {@code value <= x}. The values must be
     * in <em>ascending</em> order. The method is functionally equivalent to:
     * <pre>
     * {@code
     * i = a - 1
     * while (i < b AND value(i + 1) <= x)
     *    i = i + 1
     * return i
     * }</pre>
     *
     * <p>The function is only evaluated between the closed interval {@code [a, b]}.
     * Special cases:
     * <ul>
     * <li>If {@code value(a) > x} the returned index is {@code a - 1}.
     * <li>If {@code value(b) <= x} the returned index is {@code b}.
     * </ul>
     *
     * @param a Lower limit (inclusive).
     * @param b Upper limit (inclusive).
     * @param x Target value.
     * @param value Function to evaluate the value at an index.
     * @return the maximum index where {@code value(i) <= x}.
     */
    static int searchAscending(int a, int b, double x, IntToDoubleFunction value) {
        // Use a binary search for a large range.
        if (b - a > BINARY_SEARCH) {
            // Edge case as the search never evaluates the end points.
            if (value.applyAsDouble(a) > x) {
                return a - 1;
            }
            if (value.applyAsDouble(b) <= x) {
                return b;
            }

            // value(lo) is always <= x
            // value(hi) is always > x
            int lo = a;
            int hi = b;
            while (lo + 1 < hi) {
                final int mid = (lo + hi) >>> 1;
                if (value.applyAsDouble(mid) <= x) {
                    lo = mid;
                } else {
                    hi = mid;
                }
            }
            return lo;
        }

        // Sequential search
        int i = a - 1;
        // Evaluate between [a, b]
        while (i < b && value.applyAsDouble(i + 1) <= x) {
            i++;
        }
        return i;
    }
}