/*
 * @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 java.util.Comparator;
import java.util.function.IntPredicate;
import java.util.function.Predicate;

import lombok.experimental.UtilityClass;
import net.ranides.assira.collection.arrays.NativeArray.NativeComparator;
import net.ranides.assira.generic.Ref;

/**
 * Utility class for searching inside NativeArray. Primitive values are supported.
 *
 * Please note, that many times, methods accepts NativeArray and any type T as component.
 * It is responsibility of the caller to pass reasonable objects.
 *
 * Boxing and unboxing is supported.
 *
 * It is quite the same as {@link ArraySearch}, but it takes NativeArray wrapper instead of "just array".
 */
@SuppressWarnings({
    "PMD.AvoidReassigningParameters"
})
@UtilityClass
public class NativeArraySearch {

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

    /**
     * Returns first element matching predicate. Searches only inside specified range.
     *
     * @param array array
     * @param begin begin
     * @param end end
     * @param predicate predicate
     * @param <T> T
     * @return optional
     */
    @SuppressWarnings("unchecked")
    public static <T> Ref<T> first(NativeArray array, int begin, int end, Predicate<? super T> predicate) {
        for (int i=begin; i<end; i++) {
            T v = (T)array.get(i);
            if( predicate.test(v)) {
                return Ref.of(v);
            }
        }
        return Ref.empty();
    }

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

    /**
     * Returns last element matching predicate. Searches only inside specified range.
     *
     * @param array array
     * @param begin begin
     * @param end end
     * @param predicate predicate
     * @param <T> T
     * @return optional
     */
    @SuppressWarnings("unchecked")
    public static <T> Ref<T> last(NativeArray array, int begin, int end, Predicate<? super T> predicate) {
        for (int i=end-1; i>=begin; i--) {
            T v = (T)array.get(i);
            if( predicate.test(v)) {
                return Ref.of(v);
            }
        }
        return Ref.empty();
    }

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

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

    /**
     * Finds first element of specified value and returns its position.
     *
     * @param array array
     * @param value value
     * @param <T> T
     * @return negative if not found
     */
    public static <T> int indexOf(NativeArray array, T value) {
        return indexOf(array, 0, array.size(), 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 <T> T
     * @return negative if not found
     */
    public static <T> int indexOf(NativeArray array, int begin, int end, T value) {
        IntPredicate ip = array.cmp(value);
        for (int i=begin; i<end; i++) {
            if( ip.test(i)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * Finds last element of specified value and returns its position.
     *
     * @param array array
     * @param value value
     * @param <T> T
     * @return negative if not found
     */
    public static <T> int lastIndexOf(NativeArray array, T value) {
        return lastIndexOf(array, 0, array.size(), 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 <T> T
     * @return negative if not found
     */
    public static <T> int lastIndexOf(NativeArray array, int begin, int end, T value) {
        IntPredicate ip = array.cmp(value);
        for (int i=end-1; i>=begin; i--) {
            if( ip.test(i)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 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
     * @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 <T> int binarySearch(NativeArray array, T key) {
        return binarySearch(array.rcmp(key), 0, array.size());
    }

    /**
     * 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
     * @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 <T> int binarySearch(NativeArray array, int begin, int end, T key) {
        return binarySearch(array.rcmp(key), begin, end);
    }

    /**
     * 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 comp a comparator.
     * @param <T> T component
     * @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 <T> int binarySearch(NativeArray array, T key, Comparator<? super T> comp) {
        return binarySearch(array.rcmp(key, comp), 0, array.size());
    }

    /**
     * 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
     * @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 <T> int binarySearch(NativeArray array, int begin, int end, T key, Comparator<? super T> comp) {
        return binarySearch(array.rcmp(key, comp), begin, end);
    }

    /**
     * Searches specified range 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.
     *
     * This method does not take any array or value as arguments.
     * This method takes {@link NativeComparator} which tells you, what is the result of comparison at "index".
     *
     * Essentially, this method can be used as a framework to implement search through any data structure as long
     * as you can provide NativeComparator which encapsulates information about both structure and searched value.
     *
     * @param comp a comparator.
     * @param begin the index of the first element (inclusive) to be searched.
     * @param end the index of the last element (exclusive) to be searched.
     * @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 int binarySearch(NativeComparator comp, int begin, int end) {
        end--;
        while (begin <= end) {
            int mid = (begin + end) >>> 1;
            int cmp = comp.compare(mid);
            if (cmp < 0) {
                begin = mid + 1;
            } else if (cmp > 0) {
                end = mid - 1;
            } else {
                return mid; // key found
            }
        }
        return -(begin + 1);
    }
    
}
