From 073144d6b7abc45ab48097fac6c3175c0ab67cc9 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Tue, 21 Jan 2014 16:53:27 +0100 Subject: partial array support in 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/MultibinarySearch.java | 54 +++++++++++++++++++++++-- 1 file changed, 51 insertions(+), 3 deletions(-) (limited to 'src/algorithms/searching') diff --git a/src/algorithms/searching/MultibinarySearch.java b/src/algorithms/searching/MultibinarySearch.java index 841a4eb..868b2d6 100644 --- a/src/algorithms/searching/MultibinarySearch.java +++ b/src/algorithms/searching/MultibinarySearch.java @@ -100,6 +100,55 @@ public class MultibinarySearch * specify anything else. */ public static £(fun "long[][]" indexOf "${T}[] items, ${Tarray} array, SortOrder order, SearchMode mode") + { + return indexOf(items, array, order, mode, 0, array.length - 1£{Targ_name}); + } + + /** + * Find the indices of multiple items in a list, with time + * complexity 𝓞(log n + m) and memory complexity 𝓞(log m) + * + * @param items Sorted list of unique items for which to search, the number + * of elements is named ‘m’ in the complexity analysis + * @param array Sorted list in which to search, the number of elements + * is named ‘n’ in the complexity analysis + * @param order The lists' element order + * @param mode The search mode + * @param start The index of the first position to search in the array + * @return Two arrays of integer arrays, the 0:th being the indices + * of items, the 1:th being their positions. That is, + * two separate arrays, not and array of pairs. The expected + * position is returned inverted if it was not found, the + * position it whould have upon be inserted, otherwise the + * position is returned as an index if the mode does not + * specify anything else. + */ + public static £(fun "long[][]" indexOf "${T}[] items, ${Tarray} array, SortOrder order, SearchMode mode, int start") + { + return indexOf(items, array, order, mode, start, array.length - 1£{Targ_name}); + } + + /** + * Find the indices of multiple items in a list, with time + * complexity 𝓞(log n + m) and memory complexity 𝓞(log m) + * + * @param items Sorted list of unique items for which to search, the number + * of elements is named ‘m’ in the complexity analysis + * @param array Sorted list in which to search, the number of elements + * is named ‘n’ in the complexity analysis + * @param order The lists' 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 Two arrays of integer arrays, the 0:th being the indices + * of items, the 1:th being their positions. That is, + * two separate arrays, not and array of pairs. The expected + * position is returned inverted if it was not found, the + * position it whould have upon be inserted, otherwise the + * position is returned as an index if the mode does not + * specify anything else. + */ + public static £(fun "long[][]" indexOf "${T}[] items, ${Tarray} array, SortOrder order, SearchMode mode, int start, int end") { if (mode != SearchMode.FIND_ANY) throw new Error("Mode not implemented"); /* TODO */ @@ -122,7 +171,6 @@ public class MultibinarySearch if ((m & 0x00000002) != 0) { lb_m += 1; } int[][] minomax = new int[4][lb_m]; - int n = array.length - 1; m = items.length - 1; int rc_i = 0; @@ -131,8 +179,8 @@ public class MultibinarySearch minomax[0][mm_i] = 0; minomax[1][mm_i] = m; - minomax[2][mm_i] = 0; - minomax[3][mm_i++] = n; + minomax[2][mm_i] = start; + minomax[3][mm_i++] = end - 1; while (mm_i-- > 0) { -- cgit v1.2.3-70-g09d2