diff options
author | Mattias Andrée <maandree@operamail.com> | 2014-01-21 17:04:16 +0100 |
---|---|---|
committer | Mattias Andrée <maandree@operamail.com> | 2014-01-21 17:04:16 +0100 |
commit | c2ca752513ff30de34ebe4704dbc573dcba9d685 (patch) | |
tree | b4e08274cf282d8985619047f2b1b1d022daa488 /src/algorithms/searching | |
parent | typo (diff) | |
download | algorithms-and-data-structures-c2ca752513ff30de34ebe4704dbc573dcba9d685.tar.gz algorithms-and-data-structures-c2ca752513ff30de34ebe4704dbc573dcba9d685.tar.bz2 algorithms-and-data-structures-c2ca752513ff30de34ebe4704dbc573dcba9d685.tar.xz |
m
Signed-off-by: Mattias Andrée <maandree@operamail.com>
Diffstat (limited to 'src/algorithms/searching')
-rw-r--r-- | src/algorithms/searching/MultibinarySearch.java | 38 |
1 files changed, 23 insertions, 15 deletions
diff --git a/src/algorithms/searching/MultibinarySearch.java b/src/algorithms/searching/MultibinarySearch.java index 868b2d6..cf105b0 100644 --- a/src/algorithms/searching/MultibinarySearch.java +++ b/src/algorithms/searching/MultibinarySearch.java @@ -74,7 +74,7 @@ public class MultibinarySearch * 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, + FIND_FIRST_AND_LAST, } @@ -155,8 +155,14 @@ public class MultibinarySearch if (order != SortOrder.ASCENDING) throw new Error("Order not implemented"); /* TODO */ - BinarySearch.SearchMode mode_ = BinarySearch.SearchMode.FIND_ANY; - BinarySearch.SortOrder order_ = BinarySearch.SortOrder.ASCENDING; + BinarySearch.SearchMode mode_ = + mode == SearchMode.FIND_ANY ? BinarySearch.SearchMode.FIND_ANY + : mode == SearchMode.FIND_FIRST ? BinarySearch.SearchMode.FIND_FIRST + : mode == SearchMode.FIND_LAST ? BinarySearch.SearchMode.FIND_LAST + : BinarySearch.SearchMode.FIND_FIRST_AND_LAST; + BinarySearch.SortOrder order_ = order == SortOrder.ASCENDING + ? BinarySearch.SortOrder.ASCENDING + : BinarySearch.SortOrder.DESCENDING; int m = items.length, lb_m = 1; long[][] rc = new long[2][m]; @@ -175,39 +181,41 @@ public class MultibinarySearch int rc_i = 0; int mm_i = 0; - int min, max, amin = 0, amax = 0, lastmax, lastamax; + int imin, imax, amin = 0, amax = 0, lastimax, lastamax; minomax[0][mm_i] = 0; minomax[1][mm_i] = m; minomax[2][mm_i] = start; minomax[3][mm_i++] = end - 1; +£>bin_search="BinarySearch.indexOf(items[imax], array, order_, mode_, amin, amax${Targ_name})" + while (mm_i-- > 0) { - min = minomax[0][mm_i]; - max = minomax[1][mm_i]; + imin = minomax[0][mm_i]; + imax = minomax[1][mm_i]; amin = minomax[2][mm_i]; amax = minomax[3][mm_i]; - while (max != min) + while (imax != imin) { - lastmax = max; + lastimax = imax; lastamax = amax; - rc[0][rc_i] = max = min + ((max - min) >>> 1); - rc[1][rc_i++] = amax = (int)(BinarySearch.indexOf(items[max], array, order_, mode_, amin, amax£{Targ_name})); + rc[0][rc_i] = imax = imin + ((imax - imin) >>> 1); + rc[1][rc_i++] = amax = (int)(£{bin_search}); if (amax < 0) amax = ~amax; - minomax[0][mm_i] = max + 1; - minomax[1][mm_i] = lastmax; + minomax[0][mm_i] = imax + 1; + minomax[1][mm_i] = lastimax; minomax[2][mm_i] = amax + 1; minomax[3][mm_i++] = lastamax; } } - max = m; - amax = (int)(BinarySearch.indexOf(items[max], array, order_, mode_, amin, amax£{Targ_name})); - rc[0][rc_i] = max; + imax = m; + amax = (int)(£{bin_search}); + rc[0][rc_i] = imax; rc[1][rc_i++] = amax; return rc; |