From 1d9332538db3c759b591f2bd0db43261dac03634 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Tue, 21 Jan 2014 16:35:39 +0100 Subject: partial array support in binary search + add multibinary 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 | 78 +++++++++++++++++++++++++++--- 1 file changed, 71 insertions(+), 7 deletions(-) (limited to 'src/algorithms/searching/BinarySearch.java') diff --git a/src/algorithms/searching/BinarySearch.java b/src/algorithms/searching/BinarySearch.java index a72f75f..c4e35a7 100644 --- a/src/algorithms/searching/BinarySearch.java +++ b/src/algorithms/searching/BinarySearch.java @@ -113,7 +113,38 @@ public class BinarySearch */ public static £(fun "int" contains "${T} item, ${Tarray} array, SortOrder order") { - int low = £(cmp "array[0]" "item"); + 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") + { + int low = £(cmp "array[start]" "item"); if (order == SortOrder.ASCENDING) { @@ -123,20 +154,20 @@ public class BinarySearch int high = £(cmp "array[1]" "item"); if (low == 0) - return high == 0 ? EVERY_ELEMENT : 0; + return high == 0 ? EVERY_ELEMENT : start; - 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 n = end - 1; int high = £(cmp "array[n]" "item"); if (low == 0) - return high == 0 ? EVERY_ELEMENT : 0; + return high == 0 ? EVERY_ELEMENT : start; return high == 0 ? n : high > 0 ? TOO_LARGE : MAYBE; } @@ -154,11 +185,44 @@ public class BinarySearch * 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") + { + return indexOf(item, array, order, mode, 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 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 start") + { + return indexOf(item, array, order, mode, 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 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 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