diff options
Diffstat (limited to 'src/algorithms/searching')
| -rw-r--r-- | src/algorithms/searching/BinarySearch.java | 78 | ||||
| -rw-r--r-- | src/algorithms/searching/MultibinarySearch.java | 169 |
2 files changed, 240 insertions, 7 deletions
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; } @@ -155,10 +186,43 @@ public class BinarySearch */ 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 £>{ diff --git a/src/algorithms/searching/MultibinarySearch.java b/src/algorithms/searching/MultibinarySearch.java new file mode 100644 index 0000000..841a4eb --- /dev/null +++ b/src/algorithms/searching/MultibinarySearch.java @@ -0,0 +1,169 @@ +/** + * Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +package algorithms.searching; + +import java.util.*; + + +/** + * Multibinary search class. Multibinary search runs with time complexity + * 𝓞(log n + m) and memory complexity 𝓞(log m), where n is the number of + * elements in the array to be searched, and m is the number of items for + * which to search. Multibinary search locates multiple items in an array + * effectively, the items to locate must however be unique and stored in + * a sorted list. The algorithm only works with sorted arrays. Identity + * search is not possible, only equality search. Null elements are not + * allowed, unless the specified compator allows it. + * + * This algorithm was devised by Mattias Andrée in February of 2013. + */ +public class MultibinarySearch +{ + /** + * List sort order + */ + public static enum SortOrder + { + /** + * Bigger index, bigger value + */ + ASCENDING, + + /** + * Bigger index, smaller value + */ + DESCENDING, + + } + + /** + * List sort order + */ + public static enum SearchMode + { + /** + * Look for the index of the easiest to find occurence + */ + FIND_ANY, + + /** + * Look for the index of the first occurence + */ + FIND_FIRST, + + /** + * Look for the index of the last occurence + */ + FIND_LAST, + + /** + * 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, + + } + + + +£>for T in boolean char byte short int long float double T T++; do . src/comparable + /** + * 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 + * @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") + { + if (mode != SearchMode.FIND_ANY) + throw new Error("Mode not implemented"); /* TODO */ + if (order != SortOrder.ASCENDING) + throw new Error("Order not implemented"); /* TODO */ + + BinarySearch.SearchMode mode_ = BinarySearch.SearchMode.FIND_ANY; + BinarySearch.SortOrder order_ = BinarySearch.SortOrder.ASCENDING; + + int m = items.length, lb_m = 1; + long[][] rc = new long[2][m]; + + if (m == 0) + return rc; + + if ((m & 0xFFFF0000) != 0) { lb_m |= 16; m >>= 16; } + if ((m & 0x0000FF00) != 0) { lb_m |= 8; m >>= 8; } + if ((m & 0x000000F0) != 0) { lb_m |= 4; m >>= 4; } + if ((m & 0x0000000C) != 0) { lb_m |= 2; m >>= 2; } + 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; + int mm_i = 0; + int min, max, amin = 0, amax = 0, lastmax, lastamax; + + minomax[0][mm_i] = 0; + minomax[1][mm_i] = m; + minomax[2][mm_i] = 0; + minomax[3][mm_i++] = n; + + while (mm_i-- > 0) + { + min = minomax[0][mm_i]; + max = minomax[1][mm_i]; + amin = minomax[2][mm_i]; + amax = minomax[3][mm_i]; + + while (max != min) + { + lastmax = max; + 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})); + if (amax < 0) + amax = ~amax; + + minomax[0][mm_i] = max + 1; + minomax[1][mm_i] = lastmax; + 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; + rc[1][rc_i++] = amax; + + return rc; + } +£>done +} + |