add hybrid binary search

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

1 files changed, 297 insertions, 0 deletions

diff --git a/src/algorithms/searching/HybridBinarySearch.java b/src/algorithms/searching/HybridBinarySearch.java
new file mode 100644
index 0000000..bb0739c
--- /dev/null
+++ b/src/algorithms/searching/HybridBinarySearch.java
@@ -0,0 +1,297 @@
+/**
+ * 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
+}
+