/**
* 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
}
