[Numpy-svn] r3104 - in trunk/numpy: . core core/include/numpy core/src

numpy-svn at scipy.org numpy-svn at scipy.org
Sat Sep 2 21:26:29 CDT 2006


Author: charris
Date: 2006-09-02 21:26:26 -0500 (Sat, 02 Sep 2006)
New Revision: 3104

Modified:
   trunk/numpy/add_newdocs.py
   trunk/numpy/core/fromnumeric.py
   trunk/numpy/core/include/numpy/ndarrayobject.h
   trunk/numpy/core/src/arraymethods.c
   trunk/numpy/core/src/arrayobject.c
   trunk/numpy/core/src/multiarraymodule.c
Log:
Add new keyword <side> to the searchsorted method and function.
Add documentation thereto.
Cleanup whitespace.


Modified: trunk/numpy/add_newdocs.py
===================================================================
--- trunk/numpy/add_newdocs.py	2006-09-02 22:33:40 UTC (rev 3103)
+++ trunk/numpy/add_newdocs.py	2006-09-03 02:26:26 UTC (rev 3104)
@@ -819,14 +819,41 @@
 
 
 add_newdoc('numpy.core.multiarray', 'ndarray', ('searchsorted',
-"""a.searchsorted(v)
+"""a.searchsorted(values=v, side='left') -> array of indices.
 
- Assuming that a is a 1-D array, in ascending order and represents bin
- boundaries, then a.searchsorted(values) gives an array of bin numbers,
- giving the bin into which each value would be placed.  This method is
- helpful for histograming.  Note: No warning is given if the boundaries, in
- a, are not in ascending order.
+    Required Arguments:
+        v -- keys to be searched for in a.
 
+    Keyword arguments
+        side -- {'left', 'right'}, default('left').
+
+    If a is a 1-D array in ascending order, then
+
+        a.searchsorted(v, side='left')
+
+    returns an array of indices i such that for each element of values the
+    following holds:
+
+           a[j] < key <= a[i] for all j < i,
+
+    If such an index does not exist, a.size() is used. The result is such that
+    if the key were to be inserted in the slot before the index i, then the
+    order of a would be preserved and i would be the smallest index with that
+    property.
+
+    If a is a 1-D array in ascending order, then
+
+        a.searchsorted(v, side='right')
+
+    returns an array of indices i such that for each element of values the
+    following holds:
+
+           a[j] <= key < a[i] for all j < i,
+
+    If such an index does not exist, a.size() is used. The result is that if the
+    key were to be inserted in the slot before the index i, then the order of a
+    would be preserved and i would be the largest index with that property.
+
 """))
 
 

Modified: trunk/numpy/core/fromnumeric.py
===================================================================
--- trunk/numpy/core/fromnumeric.py	2006-09-02 22:33:40 UTC (rev 3103)
+++ trunk/numpy/core/fromnumeric.py	2006-09-03 02:26:26 UTC (rev 3104)
@@ -220,14 +220,49 @@
         return _wrapit(a, 'argmin', axis)
     return argmin(axis)
 
-def searchsorted(a, v):
-    """searchsorted(a, v)
+def searchsorted(a, v, side ='left'):
+    """-> array ind. Inserting v[i] before a[ind[i]] will leave a in order.
+
+    Required Arguments:
+        a -- sorted 1-D array to be searched.
+        v -- keys to be searched for in a.
+
+    Keyword arguments
+        side -- {'left', 'right'}, default('left').
+
+    If a is a 1-D array in ascending order, then
+
+        searchsorted(a, v, side='left')
+
+    returns an array of indices i such that for each element of values the
+    following holds:
+
+           a[j] < key <= a[i] for all j < i,
+
+    If such an index does not exist, a.size() is used. The result is such that
+    if the key were to be inserted in the slot before the index i, then the
+    order of a would be preserved and i would be the smallest index with that
+    property.
+
+    If a is a 1-D array in ascending order, then
+
+        searchsorted(a, v, side='right')
+
+    returns an array of indices i such that for each element of values the
+    following holds:
+
+           a[j] <= key < a[i] for all j < i,
+
+    If such an index does not exist, a.size() is used. The result is that if the
+    key were to be inserted in the slot before the index i, then the order of a
+    would be preserved and i would be the largest index with that property.
+
     """
     try:
         searchsorted = a.searchsorted
     except AttributeError:
-        return _wrapit(a, 'searchsorted', v)
-    return searchsorted(v)
+        return _wrapit(a, 'searchsorted', v, side)
+    return searchsorted(v, side)
 
 def resize(a, new_shape):
     """resize(a,new_shape) returns a new array with the specified shape.

Modified: trunk/numpy/core/include/numpy/ndarrayobject.h
===================================================================
--- trunk/numpy/core/include/numpy/ndarrayobject.h	2006-09-02 22:33:40 UTC (rev 3103)
+++ trunk/numpy/core/include/numpy/ndarrayobject.h	2006-09-03 02:26:26 UTC (rev 3104)
@@ -183,6 +183,13 @@
 
 
 typedef enum {
+        NPY_SEARCHLEFT=0,
+        NPY_SEARCHRIGHT=1,
+} NPY_SEARCHKIND;
+#define NPY_NSEARCHKINDS NPY_SEARCHRIGHT + 1
+
+
+typedef enum {
         NPY_NOSCALAR=-1,
         NPY_BOOL_SCALAR,
         NPY_INTPOS_SCALAR,

Modified: trunk/numpy/core/src/arraymethods.c
===================================================================
--- trunk/numpy/core/src/arraymethods.c	2006-09-02 22:33:40 UTC (rev 3103)
+++ trunk/numpy/core/src/arraymethods.c	2006-09-03 02:26:26 UTC (rev 3104)
@@ -693,13 +693,32 @@
 }
 
 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 @@
 
 	/* 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 @@
         {"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 @@
         {"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 @@
         {"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 */

Modified: trunk/numpy/core/src/arrayobject.c
===================================================================
--- trunk/numpy/core/src/arrayobject.c	2006-09-02 22:33:40 UTC (rev 3103)
+++ trunk/numpy/core/src/arrayobject.c	2006-09-03 02:26:26 UTC (rev 3104)
@@ -2399,9 +2399,9 @@
                 }
         }
 
-        /* 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 @@
                         if (temp) *axis = PyArray_NDIM(temp)-1;
                         else *axis = 0;
                 }
-                else { 
+                else {
                         temp = (PyObject *)arr;
                         Py_INCREF(temp);
                         *axis = 0;
@@ -6288,7 +6288,7 @@
 }
 
 /* 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 @@
         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 @@
 {
         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 @@
         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 @@
 
         it = (PyArrayIterObject *)_pya_malloc(sizeof(PyArrayIterObject));
         PyObject_Init((PyObject *)it, &PyArrayIter_Type);
-        
+
         if (it == NULL)
                 return NULL;
 

Modified: trunk/numpy/core/src/multiarraymodule.c
===================================================================
--- trunk/numpy/core/src/multiarraymodule.c	2006-09-02 22:33:40 UTC (rev 3103)
+++ trunk/numpy/core/src/multiarraymodule.c	2006-09-03 02:26:26 UTC (rev 3104)
@@ -2526,37 +2526,27 @@
 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;
+	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 (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;
-			}
+	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 @@
 		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 @@
  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 @@
 
 #else
 
-static void 
-_PyArray_SigintHandler(int signum) 
+static void
+_PyArray_SigintHandler(int signum)
 {
         return;
 }
@@ -6554,14 +6558,14 @@
         else {
 
                 NPY_SIGINT_ON
-                        
+
                 while(a>=0) {
                         a += 1;
                 }
-                
-                NPY_SIGINT_OFF                        
+
+                NPY_SIGINT_OFF
         }
-            
+
         return PyInt_FromLong(a);
 }
 



More information about the Numpy-svn mailing list