/**
* 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.*;
/**
* Hybrid 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. Hybrid binary search uses binary search
* and falls back to linear search when the number of elemetns left are small
* enough. Identity search is not possible, only equality search. Null elements
* are not allowed, unless the specified compator allows it.
*/
public class HybridBinarySearch
{
/**
* 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")
{
/* This is identical to as in BinarySearch */
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 index of the first occurance of an item in a list
*
* @param item The item for which to search
* @param array The list in which to search
* @param start Offset for the list or search range
* @param end End of the list or search range
* @return The index of the first occurance of the item within the list, {@code -1} if it was not found
*/
private static £(fun "int" linearFirst "${T} item, ${T}[] array, int start, int end")
{
/* This is nearly identical to LinearSearch.indexOfFirst */
int i = start < 0 ? (array.length - start) : start;
int n = end < 0 ? (array.length - end) : end;
for (;;)
{
if (i == n)
break;
if (array[i] == item)
return i;
i++;
}
return -1;
}
/**
* 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 fallback The number of elements at when to fall back to linear search
* @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 fallback")
{
£{Telement} x;
int min = 0, mid, rc = -1;
int max = array.length - 1;
£>function f
£>{
if (mode == SearchMode.£{1})
for (;;)
{
if (min + fallback >= max)
return linearFirst(item, array, min, max);
if (item == (x = array[mid = (min + max) >>> 1]))
£{2};
/* NB! (x R item), instead of (item R x) */
if (£(${3} x item)) min = mid + 1;
else max = mid - 1;
if (min > max)
return £{4};
}
£>}
£>function p
£>{
for (;;)
{
£>if [ $3 = 0 ]; then
if (min + fallback >= max)
{
first = last = rc = linearFirst(item, array, min, max);
easyMin = first + 1;
easyMax = max;
normal = true;
if (last >= 0)
break;
}
£>else
if (!normal && (min + fallback >= max))
{
first = last = rc = linearFirst(item, array, min, max);
normal = true;
if (last >= 0)
{
easyMin = first + 1;
easyMax = max;
break;
}
}
£>fi
if (item == (x = array[mid = (min + max) >>> 1]))
{
rc = mid;
£>if [ $3 = 0 ]; then
if (easyMin == -1)
{
easyMax = mid - 1;
easyMin = min;
}
£>fi
}
/* NB! (x R item), instead of (item R x) */
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;
boolean normal = false;
£>p "${1}" first 0
min = easyMin;
max = easyMax;
£>p "${1}=" last 1
return (((long)last) << 32) | (long)first;
}
£>}
if (order == SortOrder.ASCENDING)
£>_ 'less'
£>_ 'greater'
}
£>done
}
