/*
 * @author Ranides Atterwim {@literal <ranides@gmail.com>}
 * @copyright Ranides Atterwim
 * @license WTFPL
 * @url http://ranides.net/projects/assira
 */
package net.ranides.assira.collection.arrays;

import lombok.experimental.UtilityClass;

import net.ranides.assira.collection.IntComparator;
import net.ranides.assira.generic.Ref;

import java.util.Comparator;
import java.util.function.Predicate;

/**
 * Utility class for searching inside arrays. Primitive values are supported.
 *
 * Please note, that many times, methods accepts any type A as "array" and any type T as component.
 * It is responsibility of the caller to pass reasonable objects.
 * Generic declarations inferring types helps in writing code without explicit cast, but at the cost of type safety.
 *
 * Boxing and unboxing is supported.
 */
@SuppressWarnings({
    "PMD.AvoidReassigningParameters"
})
@UtilityClass
public class ArraySearch {

    /**
     * Returns true, if array contains value.
     * @param array array
     * @param value value
     * @param <A> array
     * @param <T> value
     * @return bool
     */
    public static <A,T> boolean contains(A array, T value) {
        return NativeArraySearch.contains(NativeArray.wrap(array), value);
    }

    /**
     * Returns true, if array contains value. Searches only inside specified range.
     *
     * @param array array
     * @param value value
     * @param begin begin
     * @param end end
     * @param <A> array
     * @param <T> value
     * @return bool
     */
    public static <A,T> boolean contains(A array, int begin, int end, T value) {
        return NativeArraySearch.contains(NativeArray.wrap(array), begin, end, value);
    }

    /**
     * Returns first element matching predicate.
     *
     * @param array array
     * @param predicate predicate
     * @param <A> array
     * @param <T> value
     * @return optional
     */
    public static <A,T> Ref<T> first(A array, Predicate<? super T> predicate) {
        return NativeArraySearch.first(NativeArray.wrap(array), predicate);
    }

    /**
     * Returns first element matching predicate. Searches only inside specified range.
     * @param array array
     * @param begin begin
     * @param end end
     * @param predicate predicate
     * @param <A> array
     * @param <T> value
     * @return optional
     */
    public static <A,T> Ref<T> first(A array, int begin, int end, Predicate<? super T> predicate) {
        return NativeArraySearch.first(NativeArray.wrap(array), begin, end, predicate);
    }

    /**
     * Returns last element matching predicate.
     *
     * @param array array
     * @param predicate predicate
     * @param <A> array
     * @param <T> value
     * @return optional
     */
    public static <A,T> Ref<T> last(A array, Predicate<? super T> predicate) {
        return NativeArraySearch.last(NativeArray.wrap(array), predicate);
    }

    /**
     * Returns last element matching predicate. Searches only inside specified range.
     *
     * @param array array
     * @param begin begin
     * @param end end
     * @param predicate predicate
     * @param <A> array
     * @param <T> value
     * @return optional
     */
    public static <A,T> Ref<T> last(A array, int begin, int end, Predicate<? super T> predicate) {
        return NativeArraySearch.last(NativeArray.wrap(array), begin, end, predicate);
    }

    /**
     * Finds first element of specified value and returns its position.
     *
     * @param array array
     * @param value value
     * @param <A> array
     * @param <T> value
     * @return negative if not found
     */
    public static <A, T> int indexOf(A array, T value) {
        return NativeArraySearch.indexOf(NativeArray.wrap(array), value);
    }

    /**
     * Finds first element of specified value and returns its position. Searches only inside specified range.
     * @param array array
     * @param begin begin
     * @param end end
     * @param value value
     * @param <A> array
     * @param <T> value
     * @return negative if not found
     */
    public static <A,T> int indexOf(A array, int begin, int end, T value) {
        return NativeArraySearch.indexOf(NativeArray.wrap(array), begin, end, value);
    }

    /**
     * Finds last element of specified value and returns its position.
     *
     * @param array array
     * @param value value
     * @param <A> array
     * @param <T> value
     * @return negative if not found
     */
    public static <A,T> int lastIndexOf(A array, T value) {
        return NativeArraySearch.lastIndexOf(NativeArray.wrap(array), value);
    }

    /**
     * Finds last element of specified value and returns its position. Searches only inside specified range.
     * @param array array
     * @param begin begin
     * @param end end
     * @param value value
     * @param <A> array
     * @param <T> value
     * @return negative if not found
     */
    public static <A,T> int lastIndexOf(A array, int begin, int end, T value) {
        return NativeArraySearch.lastIndexOf(NativeArray.wrap(array), begin, end, value);
    }
    
    /**
     * Searches an array for the specified value using the binary search
     * algorithm. The range must be sorted prior to making this call. If it is
     * not sorted, the results are undefined. If the range contains multiple
     * elements with the specified value, there is no guarantee which one will
     * be found.
     *
     * @param array the array to be searched.
     * @param key the value to be searched for.
     * @param <T> T component
     * @param <A> A array
     * @return index of the search key, if it is contained in the array;
     * otherwise, <code>(-(<i>insertion point</i>) - 1)</code>. The <i>insertion
     * point</i> is defined as the the point at which the value would be
     * inserted into the array: the index of the first element greater than the
     * key, or the length of the array, if all elements in the array are less
     * than the specified key. Note that this guarantees that the return value
     * will be &gt;= 0 if and only if the key is found.
     * @see java.util.Arrays
     */
    public static <A,T> int binarySearch(A array, T key) {
        if($isint(array)) {
            return $binarySearch((int[])array, (Integer)key);
        } else {
            return NativeArraySearch.binarySearch(NativeArray.wrap(array), key);
        }
    }
    
    /**
     * Searches a range of the specified array for the specified value using the
     * binary search algorithm. The range must be sorted prior to making this
     * call. If it is not sorted, the results are undefined. If the range
     * contains multiple elements with the specified value, there is no
     * guarantee which one will be found.
     *
     * @param array the array to be searched.
     * @param begin the index of the first element (inclusive) to be searched.
     * @param end the index of the last element (exclusive) to be searched.
     * @param key the value to be searched for.
     * @param <T> T component
     * @param <A> A array
     * @return index of the search key, if it is contained in the array;
     * otherwise, <code>(-(<i>insertion point</i>) - 1)</code>. The <i>insertion
     * point</i> is defined as the the point at which the value would be
     * inserted into the array: the index of the first element greater than the
     * key, or the length of the array, if all elements in the array are less
     * than the specified key. Note that this guarantees that the return value
     * will be &gt;= 0 if and only if the key is found.
     * @see java.util.Arrays
     */
    public static <A, T> int binarySearch(A array, int begin, int end, T key) {
        if($isint(array)) {
            return $binarySearch((int[])array, begin, end, (Integer)key);
        } else {
            return NativeArraySearch.binarySearch(NativeArray.wrap(array), begin, end, key);
        }
    }
    
    /**
     * Searches an array for the specified value using the binary search
     * algorithm and a specified comparator. The range must be sorted following
     * the comparator prior to making this call. If it is not sorted, the
     * results are undefined. If the range contains multiple elements with the
     * specified value, there is no guarantee which one will be found.
     *
     * @param array the array to be searched.
     * @param key the value to be searched for.
     * @param cmp a comparator.
     * @param <T> T component
     * @param <A> A array
     * @return index of the search key, if it is contained in the array;
     * otherwise, <code>(-(<i>insertion point</i>) - 1)</code>. The <i>insertion
     * point</i> is defined as the the point at which the value would be
     * inserted into the array: the index of the first element greater than the
     * key, or the length of the array, if all elements in the array are less
     * than the specified key. Note that this guarantees that the return value
     * will be &gt;= 0 if and only if the key is found.
     * @see java.util.Arrays
     */
    public static <A,T> int binarySearch(A array, T key, Comparator<? super T> cmp) {
        if($isint(array)) {
            return $binarySearch((int[])array, (Integer)key, IntComparator.$wrap(cmp));
        } else {
            return NativeArraySearch.binarySearch(NativeArray.wrap(array), key, cmp);
        }
    }

    /**
     * Searches a range of the specified array for the specified value using the
     * binary search algorithm and a specified comparator. The range must be
     * sorted following the comparator prior to making this call. If it is not
     * sorted, the results are undefined. If the range contains multiple
     * elements with the specified value, there is no guarantee which one will
     * be found.
     *
     * @param array the array to be searched.
     * @param begin the index of the first element (inclusive) to be searched.
     * @param end the index of the last element (exclusive) to be searched.
     * @param key the value to be searched for.
     * @param comp a comparator.
     * @param <T> T component
     * @param <A> A array
     * @return index of the search key, if it is contained in the array;
     * otherwise, <code>(-(<i>insertion point</i>) - 1)</code>. The <i>insertion
     * point</i> is defined as the the point at which the value would be
     * inserted into the array: the index of the first element greater than the
     * key, or the length of the array, if all elements in the array are less
     * than the specified key. Note that this guarantees that the return value
     * will be &gt;= 0 if and only if the key is found.
     * @see java.util.Arrays
     */
    public static <A,T> int binarySearch(A array, int begin, int end, T key, Comparator<? super T> comp) {
        if($isint(array)) {
            return $binarySearch((int[])array, begin, end, (Integer)key, IntComparator.$wrap(comp));
        } else {
            return NativeArraySearch.binarySearch(NativeArray.wrap(array), begin, end, key, comp);
        }
    }

    private static <A> boolean $isint(A array) {
        return null!=array && int[].class.equals(array.getClass());
    }
    
    private static int $binarySearch(int[] array, int key) {
        return $binarySearch(array, 0, array.length, key);
    }
    
    private static int $binarySearch(int[] array, int begin, int end, int key) {
        int midVal;
        end--;
        while (begin <= end) {
            int mid = (begin + end) >>> 1;
            midVal = array[ mid];
            if (midVal < key) {
                begin = mid + 1;
            } else if (midVal > key) {
                end = mid - 1;
            } else {
                return mid;
            }
        }
        return -(begin + 1);
    }
    
    private static int $binarySearch(int[] array, int key, IntComparator comp) {
        return $binarySearch(array, 0, array.length, key, comp);
    }
    
    private static int $binarySearch(int[] array, int begin, int end, int key, IntComparator comp) {
        int midVal;
        end--;
        while (begin <= end) {
            int mid = (begin + end) >>> 1;
            midVal = array[ mid];
            int cmp = comp.compare(midVal, key);
            if (cmp < 0) {
                begin = mid + 1;
            } else if (cmp > 0) {
                end = mid - 1;
            } else {
                return mid; // key found
            }
        }
        return -(begin + 1);
    }

}
