From 1ddfab95b71d41de868b5b2ad16c44efcc694373 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Tue, 21 Jan 2014 16:49:45 +0100 Subject: m + partial array support in hybrid binary search MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- src/algorithms/searching/BinarySearch.java | 7 +- src/algorithms/searching/HybridBinarySearch.java | 82 +++++++++++++++++++++--- 2 files changed, 76 insertions(+), 13 deletions(-) diff --git a/src/algorithms/searching/BinarySearch.java b/src/algorithms/searching/BinarySearch.java index c4e35a7..c4caaea 100644 --- a/src/algorithms/searching/BinarySearch.java +++ b/src/algorithms/searching/BinarySearch.java @@ -151,7 +151,7 @@ public class BinarySearch if (low > 0) return TOO_SMALL; - int high = £(cmp "array[1]" "item"); + int high = £(cmp "array[end - 1]" "item"); if (low == 0) return high == 0 ? EVERY_ELEMENT : start; @@ -163,13 +163,12 @@ public class BinarySearch if (low < 0) return TOO_SMALL; - int n = end - 1; - int high = £(cmp "array[n]" "item"); + int high = £(cmp "array[end - 1]" "item"); if (low == 0) return high == 0 ? EVERY_ELEMENT : start; - return high == 0 ? n : high > 0 ? TOO_LARGE : MAYBE; + return high == 0 ? end - 1 : high > 0 ? TOO_LARGE : MAYBE; } } diff --git a/src/algorithms/searching/HybridBinarySearch.java b/src/algorithms/searching/HybridBinarySearch.java index 2063ca9..a5b5754 100644 --- a/src/algorithms/searching/HybridBinarySearch.java +++ b/src/algorithms/searching/HybridBinarySearch.java @@ -104,7 +104,6 @@ public class HybridBinarySearch £>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 * @@ -115,35 +114,65 @@ public class HybridBinarySearch * or the index of a(!) found item [first or last position] */ public static £(fun "int" contains "${T} item, ${Tarray} array, SortOrder order") + { + return contains(item, array, order, 0, array.length£{Targ_name}); + } + + /** + * 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 + * @param start The index of the first position to search in the array + * @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, int start") + { + return contains(item, array, order, start, array.length£{Targ_name}); + } + + /** + * 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 + * @param start The index of the first position to search in the array + * @param end The index after the last position to search in the array + * @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, int start, int end") { /* This is identical to as in BinarySearch */ - int low = £(cmp "array[0]" "item"); + int low = £(cmp "array[start]" "item"); if (order == SortOrder.ASCENDING) { if (low > 0) return TOO_SMALL; - int high = £(cmp "array[1]" "item"); + int high = £(cmp "array[end - 1]" "item"); if (low == 0) return high == 0 ? EVERY_ELEMENT : 0; - return high == 0 ? array.length - 1 : high < 0 ? TOO_LARGE : MAYBE; + return high == 0 ? end - 1 : high < 0 ? TOO_LARGE : MAYBE; } { if (low < 0) return TOO_SMALL; - int n = array.length - 1; - int high = £(cmp "array[n]" "item"); + int high = £(cmp "array[end - 1]" "item"); if (low == 0) return high == 0 ? EVERY_ELEMENT : 0; - return high == 0 ? n : high > 0 ? TOO_LARGE : MAYBE; + return high == 0 ? end - 1 : high > 0 ? TOO_LARGE : MAYBE; } } @@ -190,11 +219,46 @@ public class HybridBinarySearch * 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") + { + return indexOf(item, array, order, mode, fallback, 0, array.length£{Targ_name}); + } + + /** + * 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 + * @param start The index of the first position to search in the array + * @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, int start") + { + return indexOf(item, array, order, mode, fallback, start, array.length£{Targ_name}); + } + + /** + * 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 + * @param start The index of the first position to search in the array + * @param end The index after the last position to search in the array + * @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, int start, int end") { £{Telement} x; - int min = 0, mid, rc = -1; - int max = array.length - 1; + int min = start, mid, rc = -1; + int max = end - 1; £>function f £>{ -- cgit v1.2.3-70-g09d2