From 8a3acd2b2ad7f9f2d8bca77c0291a7ba560c675e Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Tue, 21 Jan 2014 16:43:23 +0100 Subject: partial array support in hybrid interpolation search MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- .../searching/HybridInterpolationSearch.java | 51 ++++++++++++++++++---- 1 file changed, 43 insertions(+), 8 deletions(-) diff --git a/src/algorithms/searching/HybridInterpolationSearch.java b/src/algorithms/searching/HybridInterpolationSearch.java index b6669f0..bcea66a 100644 --- a/src/algorithms/searching/HybridInterpolationSearch.java +++ b/src/algorithms/searching/HybridInterpolationSearch.java @@ -39,14 +39,16 @@ public class HybridInterpolationSearch * @param item The item to find * @param array The list in which to search * @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 easiest to find occurance of the item. The bitwise * negation of the position it insert it in is returned if it was not found. */ - public static int indexOf(£{T} item, £{T}[] array, int fallback) + public static int indexOf(£{T} item, £{T}[] array, int fallback, int start, int end) { £{T} low, high, at; - int min = 0, mid; - int max = array.length - 1; + int min = start, mid; + int max = end - 1; for (;;) { @@ -75,14 +77,16 @@ public class HybridInterpolationSearch * @param item The item to find * @param array The list in which to search * @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 easiest to find occurance of the item. The bitwise - * negation of the position it insert it in is returned if it was not found. + * negation of the position it insert it in is returned if it was not found. */ - public static int indexOf(£{T} item, £{T}[] array, int fallback) + public static int indexOf(£{T} item, £{T}[] array, int fallback, int start, int end) { £{T} low, high, at; - int min = 0, mid; - int max = array.length - 1; + int min = start, mid; + int max = end - 1; for (;;) { @@ -105,7 +109,38 @@ public class HybridInterpolationSearch return (array[min] == item) ? min : ~min; } £>done - + +£>for T in char byte short int long float double BigInteger BigDecimal; do + /** + * Find the easiest to find occurance of an item in a list + * + * @param item The item to find + * @param array The list in which to search + * @param fallback The number of elements at when to fall back to linear search + * @return The index of the easiest to find occurance of the item. The bitwise + * negation of the position it insert it in is returned if it was not found. + */ + public static int indexOf(£{T} item, £{T}[] array, int fallback) + { + return indexOf(item, array, fallback, 0, array.length); + } + + /** + * Find the easiest to find occurance of an item in a list + * + * @param item The item to find + * @param array The list in which to search + * @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 easiest to find occurance of the item. The bitwise + * negation of the position it insert it in is returned if it was not found. + */ + public static int indexOf(£{T} item, £{T}[] array, int fallback, int start) + { + return indexOf(item, array, fallback, start, array.length); + } +£>done + £>for T in char byte short int long float double Object; do . src/comparable /** * Finds the index of the first occurance of an item in a list -- cgit v1.2.3-70-g09d2