partial array support in binary search + add multibinary search

Signed-off-by: Mattias Andrée <maandree@operamail.com>

4 files changed, 245 insertions, 9 deletions

diff --git a/Makefile b/Makefile
index 914d9a4..772906b 100644
--- a/Makefile
+++ b/Makefile
@@ -18,6 +18,9 @@ obj/%.java: src/%.java $(foreach F, $(PP), src/$(F))
 	$(GPP) -s £ < "$<" > "$@"
 
 
+obj/algorithms/searching/MultibinarySearch.class: obj/algorithms/searching/BinarySearch.class
+
+
 .PHONY: clean
 clean:
 	-rm -r -- bin obj
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
+}
+
diff --git a/src/comparable b/src/comparable
index 26feb1f..70cfb7b 100644
--- a/src/comparable
+++ b/src/comparable
@@ -4,6 +4,7 @@ Telement="${T}"
 Tarray="${Telement}[]"
 Tparam=""
 Targ=""
+Targ_name=""
 function T-array
 {
     elems=""
@@ -42,6 +43,7 @@ elif [[ "${T}" = @(T|T+|T++) ]]; then
     if [ "${T}" = T ]; then
 	Tparam="<T> "
 	Targ=", Comparator<T> comparator"
+	Targ_name=", comparator"
 	function cmp
 	{   echo "comparator.compare($1, $2)"
 	}
@@ -66,12 +68,10 @@ elif [[ "${T}" = @(T|T+|T++) ]]; then
     else
 	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)"