diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/algorithms/searching/BinarySearch.java | 231 | ||||
| -rw-r--r-- | src/comparable | 43 |
2 files changed, 268 insertions, 6 deletions
diff --git a/src/algorithms/searching/BinarySearch.java b/src/algorithms/searching/BinarySearch.java new file mode 100644 index 0000000..150cca9 --- /dev/null +++ b/src/algorithms/searching/BinarySearch.java @@ -0,0 +1,231 @@ +/** + * 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.*; + + +/** + * Binary search class. Binary search runs in logarithmic time, constant memory, + * and requires the list to be sorted. Binary search often out preforms linear + * search, interpolation sort however often out preforms binary search for lists + * with smooth distribution. Identity search is not possible, only equality + * search. Null elements are not allowed, unless the specified compator allows it. + */ +public class BinarySearch +{ + /** + * All elements in the array is the searched for item + */ + public static final int EVERY_ELEMENT = -1; + + /** + * Item was not on the edges, but may be inside + * Values lower than this value indicate that the value does + * not exist. + */ + public static final int MAYBE = -2; + + /** + * The item's value is smaller than the smallest in the array. + * This value and lower values indicate that the value does + * not exist. + */ + public static final int TOO_SMALL = -3; + + /** + * The item's value is larger than the largest in the array + */ + public static final int TOO_LARGE = -4; + + + + /** + * 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 + /** + * 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 + * @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 low = £(cmp "array[0]" "item"); + + if (order == SortOrder.ASCENDING) + { + if (low > 0) + return TOO_SMALL; + + int high = £(cmp "array[1]" "item"); + + if (low == 0) + return high == 0 ? EVERY_ELEMENT : 0; + + return high == 0 ? array.length - 1 : high < 0 ? TOO_LARGE : MAYBE; + } + + { + if (low < 0) + return TOO_SMALL; + + int n = array.length - 1; + int high = £(cmp "array[n]" "item"); + + if (low == 0) + return high == 0 ? EVERY_ELEMENT : 0; + + return high == 0 ? n : high > 0 ? TOO_LARGE : MAYBE; + } + } + + + /** + * 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 + * @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") + { + £{Telement} x; + + int min = 0, mid, rc = -1; + int max = array.length - 1; + +£>function f +£>{ + if (mode == SearchMode.£{1}) + for (;;) + { + if (item == (x = array[mid = (min + max) >>> 1])) + £{2}; + + if (£(${3} x item)) min = mid + 1; + else max = mid - 1; + + if (min > max) + return £{4}; + } +£>} + +£>function p +£>{ + for (;;) + { + if (item == (x = array[mid = (min + max) >>> 1])) + { + rc = mid; +£>if [ $3 = 0 ]; then + if (easyMin == -1) + { + easyMax = mid - 1; + easyMin = min; + } +£>fi + } + + if (£(${1} x item)) min = mid + 1; + else max = mid - 1; + + if (min > max) + { + if (rc < 0) + return ~((long)min); + £{2} = rc; + break; + } + } + +£>} + +£>function _ +£>{ + { +£>f FIND_ANY 'return (long)mid' "${1}" '~((long)min)' +£>f FIND_FIRST 'rc = mid' "${1}" 'rc < 0 ? ~((long)min) : (long)rc' +£>f FIND_LAST 'rc = mid' "${1}=" 'rc < 0 ? ~((long)min) : (long)rc' + + int easyMin = -1, easyMax = -1, first, last; +£>p "${1}" first 0 + min = easyMin; + max = easyMax; +£>p "${1}=" last 1 + return (((long)last) << 32) | (long)first; + } +£>} + + if (order == SortOrder.ASCENDING) +£>_ 'greater' +£>_ 'less' + } +£>done +} + diff --git a/src/comparable b/src/comparable index 51762d3..0d3c21e 100644 --- a/src/comparable +++ b/src/comparable @@ -1,5 +1,7 @@ # -*- shell-script -*- +Telement="${T}" +Tarray="${Telement}[]" Tparam="" Targ="" function T-array @@ -8,13 +10,16 @@ function T-array for elem in "$@"; do elems="${elems:+${elems}, }${elem}" done - if [ $T = T ]; then + if [ "${T}" = T ]; then echo "((${T}[])(new Object[] { ${elems} }))" else echo "(new ${T}[] { ${elems} })" fi } -if [ $T = boolean ]; then +if [ "${T}" = boolean ]; then + function cmp + { echo "(($1) == ($2) ? 0 : ($1) ? 1 : -1)" + } function greater { echo "($1) & !($2)" } @@ -33,10 +38,13 @@ if [ $T = boolean ]; then function less { echo "!($1) & ($2)" } -elif [ $T = T ] || [ $T = T+ ]; then - if [ $T = T ]; then +elif [[ "${T}" = @(T|T+|T++) ]]; then + if [ "${T}" = T ]; then Tparam="<T> " Targ=", Comparator<T> comparator" + function cmp + { echo "comparator.compare($1, $2)" + } function greater { echo "comparator.compare($1, $2) > 0" } @@ -56,8 +64,18 @@ elif [ $T = T ] || [ $T = T+ ]; then { echo "comparator.compare($1, $2) < 0" } else - Tparam="<T extends Comparable<? super T>> " - Targ="" + if [ "${T}" = T++ ]; then + Tparam="<T> " + Targ="" + Telement="Comparable<T>" + Tarray="${Telement}[]" + else + Tparam="<T extends Comparable<? super T>> " + Targ="" + fi + function cmp + { echo "($1).compareTo($2)" + } function greater { echo "($1).compareTo($2) > 0" } @@ -79,6 +97,19 @@ elif [ $T = T ] || [ $T = T+ ]; then T=T fi else + if [ "${T}" = long ]; then + function cmp + { echo "(int)(($1) - ($2) | ($1) - ($2) >> 32L)" + } + elif [[ "${T}" = @(float|double) ]]; then + function cmp + { echo "(($1) < ($2) ? -1 : ($1) > ($2) ? 1 : 0)" + } + else + function cmp + { echo "(($1) - ($2))" + } + fi function greater { echo "($1) > ($2)" } |