Add new keyword <side> to the searchsorted method and function.

Add documentation thereto.
Cleanup whitespace.

3 files changed, 117 insertions, 94 deletions

diff --git a/numpy/core/src/arraymethods.c b/numpy/core/src/arraymethods.c
index 18077745d..c7da26b79 100644
--- a/numpy/core/src/arraymethods.c
+++ b/numpy/core/src/arraymethods.c
@@ -693,13 +693,32 @@ array_argsort(PyArrayObject *self, PyObject *args, PyObject *kwds)
 }
 
 static PyObject *
-array_searchsorted(PyArrayObject *self, PyObject *args)
+array_searchsorted(PyArrayObject *self, PyObject *args, PyObject *kwds)
 {
 	PyObject *values;
+        char *side = "left";
+        static char *kwlist[] = {"values","side", NULL};
+        NPY_SEARCHKIND which;
 
-	if (!PyArg_ParseTuple(args, "O", &values)) return NULL;
+	if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|s", kwlist, &values, &side))
+            return NULL;
+	if (strlen(side) < 1) {
+		PyErr_SetString(PyExc_ValueError,
+                        "Searchsorted side string must be at least length 1");
+		return PY_FAIL;
+	}
 
-	return _ARET(PyArray_SearchSorted(self, values));
+        if (side[0] == 'l' || side[0] == 'L')
+                which = NPY_SEARCHLEFT;
+        else if (side[0] == 'r' || side[0] == 'R')
+                which = NPY_SEARCHRIGHT;
+        else {
+		PyErr_Format(PyExc_ValueError,
+                        "%s is an unrecognized side", side);
+		return PY_FAIL;
+	}
+
+	return _ARET(PyArray_SearchSorted(self, values, which));
 }
 
 static void
@@ -1549,25 +1568,25 @@ static PyMethodDef array_methods[] = {
 
 	/* Original and Extended methods added 2005 */
         {"all", (PyCFunction)array_all,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"any", (PyCFunction)array_any,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"argmax", (PyCFunction)array_argmax,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"argmin", (PyCFunction)array_argmin,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"argsort", (PyCFunction)array_argsort,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
         {"astype", (PyCFunction)array_cast,
             METH_VARARGS, NULL},
         {"byteswap", (PyCFunction)array_byteswap,
             METH_VARARGS, NULL},
 	{"choose", (PyCFunction)array_choose,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"clip", (PyCFunction)array_clip,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"compress", (PyCFunction)array_compress,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"conj", (PyCFunction)array_conjugate,
 	    METH_VARARGS, NULL},
 	{"conjugate", (PyCFunction)array_conjugate,
@@ -1575,11 +1594,11 @@ static PyMethodDef array_methods[] = {
         {"copy", (PyCFunction)array_copy,
             METH_VARARGS, NULL},
 	{"cumprod", (PyCFunction)array_cumprod,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"cumsum", (PyCFunction)array_cumsum,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"diagonal", (PyCFunction)array_diagonal,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"fill", (PyCFunction)array_fill,
 	    METH_VARARGS, NULL},
 	{"flatten", (PyCFunction)array_flatten,
@@ -1589,51 +1608,51 @@ static PyMethodDef array_methods[] = {
         {"item", (PyCFunction)array_toscalar,
             METH_VARARGS, NULL},
 	{"max", (PyCFunction)array_max,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"mean", (PyCFunction)array_mean,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"min", (PyCFunction)array_min,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"newbyteorder", (PyCFunction)array_newbyteorder,
 	    METH_VARARGS, NULL},
 	{"nonzero", (PyCFunction)array_nonzero,
 	    METH_VARARGS, NULL},
 	{"prod", (PyCFunction)array_prod,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"ptp", (PyCFunction)array_ptp,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"put",	(PyCFunction)array_put,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"putmask", (PyCFunction)array_putmask,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"ravel", (PyCFunction)array_ravel,
 	    METH_VARARGS, NULL},
 	{"repeat", (PyCFunction)array_repeat,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"reshape", (PyCFunction)array_reshape,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
         {"resize", (PyCFunction)array_resize,
             METH_VARARGS | METH_KEYWORDS, NULL},
 	{"round", (PyCFunction)array_round,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"searchsorted", (PyCFunction)array_searchsorted,
-	    METH_VARARGS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"setfield", (PyCFunction)array_setfield,
             METH_VARARGS | METH_KEYWORDS, NULL},
 	{"setflags", (PyCFunction)array_setflags,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"sort", (PyCFunction)array_sort,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"squeeze", (PyCFunction)array_squeeze,
 	    METH_VARARGS, NULL},
 	{"std", (PyCFunction)array_stddev,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"sum", (PyCFunction)array_sum,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"swapaxes", (PyCFunction)array_swapaxes,
 	    METH_VARARGS, NULL},
 	{"take", (PyCFunction)array_take,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"tofile", (PyCFunction)array_tofile,
             METH_VARARGS | METH_KEYWORDS, NULL},
         {"tolist", (PyCFunction)array_tolist,
@@ -1641,11 +1660,11 @@ static PyMethodDef array_methods[] = {
         {"tostring", (PyCFunction)array_tostring,
             METH_VARARGS | METH_KEYWORDS, NULL},
 	{"trace", (PyCFunction)array_trace,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"transpose", (PyCFunction)array_transpose,
 	    METH_VARARGS, NULL},
 	{"var", (PyCFunction)array_variance,
-	    METH_VARARGS|METH_KEYWORDS, NULL},
+	    METH_VARARGS | METH_KEYWORDS, NULL},
 	{"view", (PyCFunction)array_view,
 	    METH_VARARGS, NULL},
         {NULL,		NULL}		/* sentinel */
diff --git a/numpy/core/src/arrayobject.c b/numpy/core/src/arrayobject.c
index c8a750a38..0bfb5a06d 100644
--- a/numpy/core/src/arrayobject.c
+++ b/numpy/core/src/arrayobject.c
@@ -2399,9 +2399,9 @@ PyArray_SetMap(PyArrayMapIterObject *mit, PyObject *op)
                 }
         }
 
-        /* Be sure values array is "broadcastable" 
+        /* Be sure values array is "broadcastable"
            to shape of mit->dimensions, mit->nd */
-        
+
         if ((it = (PyArrayIterObject *)\
              PyArray_BroadcastToShape(arr, mit->dimensions, mit->nd))==NULL) {
                 Py_DECREF(arr);
@@ -4698,7 +4698,7 @@ _check_axis(PyArrayObject *arr, int *axis, int flags)
                         if (temp) *axis = PyArray_NDIM(temp)-1;
                         else *axis = 0;
                 }
-                else { 
+                else {
                         temp = (PyObject *)arr;
                         Py_INCREF(temp);
                         *axis = 0;
@@ -6288,7 +6288,7 @@ array_base_get(PyArrayObject *self)
 }
 
 /* Create a view of a complex array with an equivalent data-type
-   except it is real instead of complex. 
+   except it is real instead of complex.
 */
 
 static PyArrayObject *
@@ -6301,7 +6301,7 @@ _get_part(PyArrayObject *self, int imag)
         type = PyArray_DescrFromType(self->descr->type_num -
                                      PyArray_NUM_FLOATTYPE);
         offset = (imag ? type->elsize : 0);
-        
+
         if (!PyArray_ISNBO(self->descr->byteorder)) {
                 PyArray_Descr *new;
                 new = PyArray_DescrNew(type);
@@ -6759,14 +6759,14 @@ _array_small_type(PyArray_Descr *chktype, PyArray_Descr* mintype)
 {
         PyArray_Descr *outtype;
         int outtype_num, save_num;
-        
-        if (chktype->type_num > mintype->type_num) 
+
+        if (chktype->type_num > mintype->type_num)
                 outtype_num = chktype->type_num;
-        else 
+        else
                 outtype_num = mintype->type_num;
-        
+
         save_num = outtype_num;
-        while(outtype_num < PyArray_NTYPES && 
+        while(outtype_num < PyArray_NTYPES &&
               !(PyArray_CanCastSafely(chktype->type_num, outtype_num)
                 && PyArray_CanCastSafely(mintype->type_num, outtype_num)))
                 outtype_num++;
@@ -8627,7 +8627,7 @@ PyArray_BroadcastToShape(PyObject *obj, intp *dims, int nd)
         PyArrayIterObject *it;
         int i, diff, j, compat, k;
         PyArrayObject *ao = (PyArrayObject *)obj;
- 
+
         if (ao->nd > nd) goto err;
         compat = 1;
         diff = j = nd - ao->nd;
@@ -8642,7 +8642,7 @@ PyArray_BroadcastToShape(PyObject *obj, intp *dims, int nd)
 
         it = (PyArrayIterObject *)_pya_malloc(sizeof(PyArrayIterObject));
         PyObject_Init((PyObject *)it, &PyArrayIter_Type);
-        
+
         if (it == NULL)
                 return NULL;
 
diff --git a/numpy/core/src/multiarraymodule.c b/numpy/core/src/multiarraymodule.c
index fd78f73a6..12771ac4d 100644
--- a/numpy/core/src/multiarraymodule.c
+++ b/numpy/core/src/multiarraymodule.c
@@ -2526,37 +2526,27 @@ static void
 local_search_left(PyArrayObject *ap1, PyArrayObject *ap2, PyArrayObject *ret)
 {
 	PyArray_CompareFunc *compare = ap2->descr->f->compare;
-	intp  min_i, max_i, i, j;
-	int location, elsize = ap1->descr->elsize;
-	intp elements = ap1->dimensions[ap1->nd-1];
-	intp n = PyArray_SIZE(ap2);
-	intp *rp = (intp *)ret->data;
-	char *ip = ap2->data;
-	char *vp = ap1->data;
-
-	for (j=0; j<n; j++, ip+=elsize, rp++) {
-		min_i = 0;
-		max_i = elements;
-		while (min_i != max_i) {
-			i = (max_i-min_i)/2 + min_i;
-			location = compare(ip, vp+elsize*i, ap2);
-			if (location == 0) {
-				while (i > 0) {
-					if (compare(ip, vp+elsize*(--i), ap2) \
-					    != 0) {
-						i = i+1; break;
-					}
-				}
-				min_i = i;
-				break;
-			}
-			else if (location < 0) {
-				max_i = i;
-			} else {
-				min_i = i+1;
-			}
+	intp nelts = ap1->dimensions[ap1->nd - 1];
+	intp nkeys = PyArray_SIZE(ap2);
+	char *p1 = ap1->data;
+	char *p2 = ap2->data;
+	intp *pr = (intp *)ret->data;
+	int elsize = ap1->descr->elsize;
+	intp i;
+
+	for(i = 0; i < nkeys; ++i) {
+		intp imin = 0;
+		intp imax = nelts;
+		while (imin < imax) {
+			intp imid = imin + ((imax - imin) >> 2);
+			if (compare(p1 + elsize*imid, p2, ap2) < 0)
+                                imin = imid + 1;
+			else
+				imax = imid;
 		}
-		*rp = min_i;
+                *pr = imin;
+                pr += 1;
+                p2 += elsize;
 	}
 }
 
@@ -2595,11 +2585,10 @@ local_search_right(PyArrayObject *ap1, PyArrayObject *ap2, PyArrayObject *ret)
 		intp imax = nelts;
 		while (imin < imax) {
 			intp imid = imin + ((imax - imin) >> 2);
-			if (compare(p1 + elsize*imid, p2, ap2) < 0)  {
+			if (compare(p1 + elsize*imid, p2, ap2) <= 0)
                                 imin = imid + 1;
-			} else {
+			else
 				imax = imid;
-			}
 		}
                 *pr = imin;
                 pr += 1;
@@ -2611,39 +2600,54 @@ local_search_right(PyArrayObject *ap1, PyArrayObject *ap2, PyArrayObject *ret)
  Numeric.searchsorted(a,v)
 */
 static PyObject *
-PyArray_SearchSorted(PyArrayObject *op1, PyObject *op2)
+PyArray_SearchSorted(PyArrayObject *op1, PyObject *op2, NPY_SEARCHKIND which)
 {
-	PyArrayObject *ap1=NULL, *ap2=NULL, *ret=NULL;
+	PyArrayObject *ap1=NULL;
+        PyArrayObject *ap2=NULL;
+        PyArrayObject *ret=NULL;
 	int typenum = 0;
 
 	NPY_BEGIN_THREADS_DEF
 
 	typenum = PyArray_ObjectType((PyObject *)op1, 0);
 	typenum = PyArray_ObjectType(op2, typenum);
-	ret = NULL;
+
+        /* need ap1 as contiguous array and of right type */
 	ap1 = (PyArrayObject *)PyArray_ContiguousFromAny((PyObject *)op1,
 							    typenum,
 							    1, 1);
-	if (ap1 == NULL) return NULL;
-	ap2 = (PyArrayObject *)PyArray_ContiguousFromAny(op2, typenum,
+	if (ap1 == NULL)
+            return NULL;
+
+        /* need ap2 as contiguous array and of right type */
+        ap2 = (PyArrayObject *)PyArray_ContiguousFromAny(op2, typenum,
 							    0, 0);
-	if (ap2 == NULL) goto fail;
+	if (ap2 == NULL)
+            goto fail;
 
+        /* ret is a contiguous array of intp type to hold returned indices */
 	ret = (PyArrayObject *)PyArray_New(ap2->ob_type, ap2->nd,
 					   ap2->dimensions, PyArray_INTP,
 					   NULL, NULL, 0, 0, (PyObject *)ap2);
-	if (ret == NULL) goto fail;
+	if (ret == NULL)
+            goto fail;
 
+        /* check that comparison function exists */
 	if (ap2->descr->f->compare == NULL) {
 		PyErr_SetString(PyExc_TypeError,
 				"compare not supported for type");
 		goto fail;
 	}
 
-	NPY_BEGIN_THREADS_DESCR(ap2->descr)
-	local_search_left(ap1, ap2, ret);
-	NPY_END_THREADS_DESCR(ap2->descr)
-
+        if (which == NPY_SEARCHLEFT) {
+                NPY_BEGIN_THREADS_DESCR(ap2->descr)
+                local_search_left(ap1, ap2, ret);
+                NPY_END_THREADS_DESCR(ap2->descr)
+        } else if (which == NPY_SEARCHRIGHT) {
+                NPY_BEGIN_THREADS_DESCR(ap2->descr)
+                local_search_right(ap1, ap2, ret);
+                NPY_END_THREADS_DESCR(ap2->descr)
+        }
 	Py_DECREF(ap1);
 	Py_DECREF(ap2);
 	return (PyObject *)ret;
@@ -6519,8 +6523,8 @@ _PyArray_GetSigintBuf(void)
 
 #else
 
-static void 
-_PyArray_SigintHandler(int signum) 
+static void
+_PyArray_SigintHandler(int signum)
 {
         return;
 }
@@ -6554,14 +6558,14 @@ test_interrupt(PyObject *self, PyObject *args)
         else {
 
                 NPY_SIGINT_ON
-                        
+
                 while(a>=0) {
                         a += 1;
                 }
-                
-                NPY_SIGINT_OFF                        
+
+                NPY_SIGINT_OFF
         }
-            
+
         return PyInt_FromLong(a);
 }