/*
 * Copyright 2013 Alex Kasko (alexkasko.com)
 *
 * Licensed 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 com.alexkasko.unsafe.offheapstruct;

import java.io.Serializable;

/**
 * Binary search implementation borrowed from {@code https://android.googlesource.com/platform/libcore/+/android-4.2.2_r1/luni/src/main/java/java/util/Arrays.java}
 * and adapted to {@link com.alexkasko.unsafe.offheapstruct.OffHeapStructCollection}
 *
 * @author alexkasko
 * Date: 7/4/13
 * @see com.alexkasko.unsafe.offheaplong.OffHeapLongSorter
 * @see com.alexkasko.unsafe.offheapstruct.OffHeapStructSorter
 */
public class OffHeapStructBinarySearch {


    // long key part

    /**
     * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using long struct key.
     * Searching in an unsorted collection has an undefined result. It's also undefined which element
     * is found if there are multiple occurrences of the same element.
     *
     * @param collection the sorted array to search.
     * @param value the element to find.
     * @param keyOffset long key field offset within stuct bounds
     * @return the non-negative index of the element, or a negative index which
     *         is {@code -index - 1} where the element would be inserted.
     */
    public static long binarySearchByLongKey(OffHeapStructCollection collection, long value, int keyOffset) {
        return binarySearchByLongKey(collection, 0, collection.size(), value, keyOffset);
    }

    /**
     * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using long struct key.
     * in the range specified by fromIndex (inclusive) and toIndex (exclusive).
     * Searching in an unsorted collection has an undefined result. It's also undefined which element
     * is found if there are multiple occurrences of the same element.
     *
     * @param collection      the sorted collection to search.
     * @param startIndex the inclusive start index.
     * @param endIndex   the exclusive end index.
     * @param value      the element to find.
     * @param keyOffset  long key field offset within stuct bounds
     * @return the non-negative index of the element, or a negative index which
     *         is {@code -index - 1} where the element would be inserted.
     * @throws IllegalArgumentException {@code if (startIndex < 0 || startIndex > endIndex || endIndex > collection.size()}
     */
    public static long binarySearchByLongKey(OffHeapStructCollection collection, long startIndex, long endIndex, long value, int keyOffset) {
        if (startIndex < 0 || startIndex > endIndex || endIndex > collection.size()) {
            throw new IllegalArgumentException("Illegal input, collection size: [" + collection.size() + "], " +
                    "startIndex: [" + startIndex + "], endIndex: [" + endIndex + "]");
        }
        long lo = startIndex;
        long hi = endIndex - 1;
        while (lo <= hi) {
            long mid = (lo + hi) >>> 1;
            long midVal = collection.getLong(mid, keyOffset);

            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }

    /**
     * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using long struct key.
     * Returns range of indices having given value or empty range.
     * Searching in an unsorted collection has an undefined result. It's also undefined which element
     * is found if there are multiple occurrences of the same element.
     *
     * @param collection the sorted array to search.
     * @param value the element to find.
     * @param keyOffset  long key field offset within stuct bounds
     * @param out range instance, will be set with start/end indices having given value or with empty value
     */
    public static void binarySearchRangeByLongKey(OffHeapStructCollection collection, long value, int keyOffset, IndexRange out) {
        binarySearchRangeByLongKey(collection, 0, collection.size(), value, keyOffset, out);
    }

    /**
     * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using long struct key.
     * Returns range of indices having given value or empty range.
     * Searching in an unsorted collection has an undefined result. It's also undefined which element
     * is found if there are multiple occurrences of the same element.
     *
     * @param collection the sorted array to search.
     * @param startIndex the inclusive start index.
     * @param endIndex   the exclusive end index.
     * @param value the element to find.
     * @param keyOffset  long key field offset within stuct bounds
     * @param out range instance, will be set with start/end indices having given value or with empty value
     */
    public static void binarySearchRangeByLongKey(OffHeapStructCollection collection, long startIndex, long endIndex,
                                               long value, int keyOffset, IndexRange out) {
        long ind = binarySearchByLongKey(collection, startIndex, endIndex, value, keyOffset);
        if(ind < 0) {
            out.setEmpty(ind);
            return;
        }
        long from = ind;
        while (from >= startIndex && value == collection.getLong(from, keyOffset)) {
            from -= 1;
        }
        from += 1;
        long to = ind;
        while (to < endIndex && value == collection.getLong(to, keyOffset)) {
            to += 1;
        }
        to -= 1;
        out.set(from, to);
    }


    // int key part

    /**
     * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using int struct key.
     * Searching in an unsorted collection has an undefined result. It's also undefined which element
     * is found if there are multiple occurrences of the same element.
     *
     * @param collection the sorted array to search.
     * @param value the element to find.
     * @param keyOffset int key field offset within stuct bounds
     * @return the non-negative index of the element, or a negative index which
     *         is {@code -index - 1} where the element would be inserted.
     */
    public static long binarySearchByIntKey(OffHeapStructCollection collection, long value, int keyOffset) {
        return binarySearchByIntKey(collection, 0, collection.size(), value, keyOffset);
    }

    /**
     * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using int struct key.
     * in the range specified by fromIndex (inclusive) and toIndex (exclusive).
     * Searching in an unsorted collection has an undefined result. It's also undefined which element
     * is found if there are multiple occurrences of the same element.
     *
     * @param collection      the sorted collection to search.
     * @param startIndex the inclusive start index.
     * @param endIndex   the exclusive end index.
     * @param value      the element to find.
     * @param keyOffset  int key field offset within stuct bounds
     * @return the non-negative index of the element, or a negative index which
     *         is {@code -index - 1} where the element would be inserted.
     * @throws IllegalArgumentException {@code if (startIndex < 0 || startIndex > endIndex || endIndex > collection.size()}
     */
    public static long binarySearchByIntKey(OffHeapStructCollection collection, long startIndex, long endIndex, long value, int keyOffset) {
        if (startIndex < 0 || startIndex > endIndex || endIndex > collection.size()) {
            throw new IllegalArgumentException("Illegal input, collection size: [" + collection.size() + "], " +
                    "startIndex: [" + startIndex + "], endIndex: [" + endIndex + "]");
        }
        long lo = startIndex;
        long hi = endIndex - 1;
        while (lo <= hi) {
            long mid = (lo + hi) >>> 1;
            long midVal = collection.getInt(mid, keyOffset);

            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }

    /**
     * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using int struct key.
     * Returns range of indices having given value or empty range.
     * Searching in an unsorted collection has an undefined result. It's also undefined which element
     * is found if there are multiple occurrences of the same element.
     *
     * @param collection the sorted array to search.
     * @param value the element to find.
     * @param keyOffset int key field offset within stuct bounds
     * @param out range instance, will be set with start/end indices having given value or with empty value
     */
    public static void binarySearchRangeByIntKey(OffHeapStructCollection collection, long value, int keyOffset, IndexRange out) {
        binarySearchRangeByIntKey(collection, 0, collection.size(), value, keyOffset, out);
    }

    /**
     * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using int struct key.
     * Returns range of indices having given value or empty range.
     * Searching in an unsorted collection has an undefined result. It's also undefined which element
     * is found if there are multiple occurrences of the same element.
     *
     * @param collection the sorted array to search.
     * @param startIndex the inclusive start index.
     * @param endIndex   the exclusive end index.
     * @param value the element to find.
     * @param keyOffset  int key field offset within stuct bounds
     * @param out range instance, will be set with start/end indices having given value or with empty value
     */
    public static void binarySearchRangeByIntKey(OffHeapStructCollection collection, long startIndex, long endIndex,
                                               long value, int keyOffset, IndexRange out) {
        long ind = binarySearchByIntKey(collection, startIndex, endIndex, value, keyOffset);
        if(ind < 0) {
            out.setEmpty(ind);
            return;
        }
        long from = ind;
        while (from >= startIndex && value == collection.getInt(from, keyOffset)) {
            from -= 1;
        }
        from += 1;
        long to = ind;
        while (to < endIndex && value == collection.getInt(to, keyOffset)) {
            to += 1;
        }
        to -= 1;
        out.set(from, to);
    }

    /**
     * {@link OffHeapStructCollection} index range representation.
     * Was made mutable to prevent new object instantiation for each search.
     * {@link #isEmpty()} method should be checked before accessing indices.
     * Empty range will contain negative equal indices which values are
     * {@code -index - 1} where the element would be inserted.
     * Range with size {@code 1} will contain equal indices.
     */
    public static class IndexRange implements Serializable {
        private static final long serialVersionUID = 879348143026038919L;
        private boolean empty;
        private long fromIndex;
        private long toIndex;

        public IndexRange() {
            this.empty = false;
            this.fromIndex = -1;
            this.toIndex = -1;
        }

        /**
         * Sets value for empty range
         *
         * @param value negative value for empty range returned by search
         */
        void setEmpty(long value) {
            this.empty = true;
            this.fromIndex = value;
            this.toIndex = value;
        }

        /**
         * Sets boundaries for non-empty range
         *
         * @param from start index
         * @param to end index
         */
        void set(long from, long to) {
            this.empty = false;
            this.fromIndex = from;
            this.toIndex = to;
        }

        /**
         * Whether this range is empty
         *
         * @return whether this range is empty
         */
        public boolean isEmpty() {
            return empty;
        }

        /**
         * Whether this range is not empty
         *
         * @return whether this range is not empty
         */
        public boolean isNotEmpty() {
            return !empty;
        }

        /**
         * Start index or {@code -index - 1}
         *      where the element would be inserted for empty range
         *
         * @return start index value or {@code -index - 1}
         *      where the element would be inserted for empty range
         */
        public long getFromIndex() {
            return fromIndex;
        }

        /**
         * End index or {@code -index - 1}
         *      where the element would be inserted for empty range
         *
         * @return end index value, {@code -index - 1}
         *      where the element would be inserted for empty range
         */
        public long getToIndex() {
            return toIndex;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            IndexRange that = (IndexRange) o;
            if (empty != that.empty) return false;
            if (fromIndex != that.fromIndex) return false;
            if (toIndex != that.toIndex) return false;
            return true;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public int hashCode() {
            int result = (empty ? 1 : 0);
            result = 31 * result + (int) (fromIndex ^ (fromIndex >>> 32));
            result = 31 * result + (int) (toIndex ^ (toIndex >>> 32));
            return result;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder();
            sb.append("IndexRange");
            sb.append("{empty=").append(empty);
            sb.append(", fromIndex=").append(fromIndex);
            sb.append(", toIndex=").append(toIndex);
            sb.append('}');
            return sb.toString();
        }
    }
}