add binary search

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

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)"
     }