diff options
| -rw-r--r-- | src/algorithms/searching/HybridBinarySearch.java | 297 |
1 files changed, 297 insertions, 0 deletions
diff --git a/src/algorithms/searching/HybridBinarySearch.java b/src/algorithms/searching/HybridBinarySearch.java new file mode 100644 index 0000000..bb0739c --- /dev/null +++ b/src/algorithms/searching/HybridBinarySearch.java @@ -0,0 +1,297 @@ +/** + * Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +package algorithms.searching; + +import java.util.*; + + +/** + * Hybrid binary search class. Binary search runs in logarithmic time, constant + * memory, and requires the list to be sorted. Binary search often out preforms + * linear search, interpolation sort however often out preforms binary search + * for lists with smooth distribution. Hybrid binary search uses binary search + * and falls back to linear search when the number of elemetns left are small + * enough. Identity search is not possible, only equality search. Null elements + * are not allowed, unless the specified compator allows it. + */ +public class HybridBinarySearch +{ + /** + * All elements in the array is the searched for item + */ + public static final int EVERY_ELEMENT = -1; + + /** + * Item was not on the edges, but may be inside + * Values lower than this value indicate that the value does + * not exist. + */ + public static final int MAYBE = -2; + + /** + * The item's value is smaller than the smallest in the array. + * This value and lower values indicate that the value does + * not exist. + */ + public static final int TOO_SMALL = -3; + + /** + * The item's value is larger than the largest in the array + */ + public static final int TOO_LARGE = -4; + + + + /** + * List sort order + */ + public static enum SortOrder + { + /** + * Bigger index, bigger value + */ + ASCENDING, + + /** + * Bigger index, smaller value + */ + DESCENDING, + + } + + /** + * List sort order + */ + public static enum SearchMode + { + /** + * Look for the index of the easiest to find occurence + */ + FIND_ANY, + + /** + * Look for the index of the first occurence + */ + FIND_FIRST, + + /** + * Look for the index of the last occurence + */ + FIND_LAST, + + /** + * Look for both the index of the fist occurence and of the last occurence.<br> + * The returned value will be {@code (LAST << 32) | FIRST}. + */ + FIND_FIST_AND_LAST, + + } + + + +£>for T in boolean char byte short int long float double T T++; do . src/comparable + + /** + * Gets whether an item may be contained by a list + * + * @param item The item for which to search + * @param array The list in which to search + * @param order The list's element order + * @return {@link #MAYBE}, {@link #TOO_SMALL}, {@link #TOO_LARGE}, {@link #EVERY_ELEMENT} + * or the index of a(!) found item [first or last position] + */ + public static £(fun "int" contains "${T} item, ${Tarray} array, SortOrder order") + { + /* This is identical to as in BinarySearch */ + + int low = £(cmp "array[0]" "item"); + + if (order == SortOrder.ASCENDING) + { + if (low > 0) + return TOO_SMALL; + + int high = £(cmp "array[1]" "item"); + + if (low == 0) + return high == 0 ? EVERY_ELEMENT : 0; + + return high == 0 ? array.length - 1 : high < 0 ? TOO_LARGE : MAYBE; + } + + { + if (low < 0) + return TOO_SMALL; + + int n = array.length - 1; + int high = £(cmp "array[n]" "item"); + + if (low == 0) + return high == 0 ? EVERY_ELEMENT : 0; + + return high == 0 ? n : high > 0 ? TOO_LARGE : MAYBE; + } + } + + + /** + * Finds the index of the first occurance of an item in a list + * + * @param item The item for which to search + * @param array The list in which to search + * @param start Offset for the list or search range + * @param end End of the list or search range + * @return The index of the first occurance of the item within the list, {@code -1} if it was not found + */ + private static £(fun "int" linearFirst "${T} item, ${T}[] array, int start, int end") + { + /* This is nearly identical to LinearSearch.indexOfFirst */ + + int i = start < 0 ? (array.length - start) : start; + int n = end < 0 ? (array.length - end) : end; + + for (;;) + { + if (i == n) + break; + + if (array[i] == item) + return i; + + i++; + } + + return -1; + } + + /** + * Finds the first, last or any occurance of an item in a list + * + * @param item The item for which to search + * @param array The list in which to search + * @param order The list's element order + * @param mode The search mode + * @param fallback The number of elements at when to fall back to linear search + * @return The index of the found item, if not mode does not say otherwise, or, if not + * found, the bitwise negation of the position to which it should be inserted + */ + public static £(fun "long" indexOf "${T} item, ${Tarray} array, SortOrder order, SearchMode mode, int fallback") + { + £{Telement} x; + + int min = 0, mid, rc = -1; + int max = array.length - 1; + +£>function f +£>{ + if (mode == SearchMode.£{1}) + for (;;) + { + if (min + fallback >= max) + return linearFirst(item, array, min, max); + + if (item == (x = array[mid = (min + max) >>> 1])) + £{2}; + + /* NB! (x R item), instead of (item R x) */ + if (£(${3} x item)) min = mid + 1; + else max = mid - 1; + + if (min > max) + return £{4}; + } +£>} + +£>function p +£>{ + for (;;) + { +£>if [ $3 = 0 ]; then + if (min + fallback >= max) + { + first = last = rc = linearFirst(item, array, min, max); + easyMin = first + 1; + easyMax = max; + normal = true; + if (last >= 0) + break; + } +£>else + if (!normal && (min + fallback >= max)) + { + first = last = rc = linearFirst(item, array, min, max); + normal = true; + if (last >= 0) + { + easyMin = first + 1; + easyMax = max; + break; + } + } +£>fi + + if (item == (x = array[mid = (min + max) >>> 1])) + { + rc = mid; +£>if [ $3 = 0 ]; then + if (easyMin == -1) + { + easyMax = mid - 1; + easyMin = min; + } +£>fi + } + + /* NB! (x R item), instead of (item R x) */ + if (£(${1} x item)) min = mid + 1; + else max = mid - 1; + + if (min > max) + { + if (rc < 0) + return ~((long)min); + £{2} = rc; + break; + } + } + +£>} + +£>function _ +£>{ + { +£>f FIND_ANY 'return (long)mid' "${1}" '~((long)min)' +£>f FIND_FIRST 'rc = mid' "${1}" 'rc < 0 ? ~((long)min) : (long)rc' +£>f FIND_LAST 'rc = mid' "${1}=" 'rc < 0 ? ~((long)min) : (long)rc' + + int easyMin = -1, easyMax = -1, first, last; + boolean normal = false; +£>p "${1}" first 0 + min = easyMin; + max = easyMax; +£>p "${1}=" last 1 + return (((long)last) << 32) | (long)first; + } +£>} + + if (order == SortOrder.ASCENDING) +£>_ 'less' +£>_ 'greater' + } +£>done +} + |