numpy  2.0.0
src/multiarray/item_selection.c File Reference
#include <Python.h>
#include "structmember.h"
#include "numpy/arrayobject.h"
#include "numpy/arrayscalars.h"
#include "numpy/npy_math.h"
#include "npy_config.h"
#include "npy_pycompat.h"
#include "common.h"
#include "arrayobject.h"
#include "ctors.h"
#include "lowlevel_strided_loops.h"
#include "item_selection.h"
#include "npy_sort.h"

Defines

#define PY_SSIZE_T_CLEAN
#define NPY_NO_DEPRECATED_API   NPY_API_VERSION
#define _MULTIARRAYMODULE
#define SWAPAXES(op, ap)
#define SWAPBACK(op, ap)
#define SWAPINTP(a, b)   {npy_intp c; c=(a); (a) = (b); (b) = c;}
#define SWAPAXES2(ap)
#define SWAPBACK2(ap)

Functions

NPY_NO_EXPORT PyObject * PyArray_TakeFrom (PyArrayObject *self0, PyObject *indices0, int axis, PyArrayObject *out, NPY_CLIPMODE clipmode)
NPY_NO_EXPORT PyObject * PyArray_PutTo (PyArrayObject *self, PyObject *values0, PyObject *indices0, NPY_CLIPMODE clipmode)
NPY_NO_EXPORT PyObject * PyArray_PutMask (PyArrayObject *self, PyObject *values0, PyObject *mask0)
NPY_NO_EXPORT PyObject * PyArray_Repeat (PyArrayObject *aop, PyObject *op, int axis)
NPY_NO_EXPORT PyObject * PyArray_Choose (PyArrayObject *ip, PyObject *op, PyArrayObject *out, NPY_CLIPMODE clipmode)
static int _new_sort (PyArrayObject *op, int axis, NPY_SORTKIND which)
static PyObject * _new_argsort (PyArrayObject *op, int axis, NPY_SORTKIND which)
static int sortCompare (const void *a, const void *b)
NPY_NO_EXPORT int PyArray_Sort (PyArrayObject *op, int axis, NPY_SORTKIND which)
static int argsort_static_compare (const void *ip1, const void *ip2)
NPY_NO_EXPORT PyObject * PyArray_ArgSort (PyArrayObject *op, int axis, NPY_SORTKIND which)
NPY_NO_EXPORT PyObject * PyArray_LexSort (PyObject *sort_keys, int axis)
static void local_search_left (PyArrayObject *arr, PyArrayObject *key, PyArrayObject *ret)
static void local_search_right (PyArrayObject *arr, PyArrayObject *key, PyArrayObject *ret)
static int local_argsearch_left (PyArrayObject *arr, PyArrayObject *key, PyArrayObject *sorter, PyArrayObject *ret)
static int local_argsearch_right (PyArrayObject *arr, PyArrayObject *key, PyArrayObject *sorter, PyArrayObject *ret)
NPY_NO_EXPORT PyObject * PyArray_SearchSorted (PyArrayObject *op1, PyObject *op2, NPY_SEARCHSIDE side, PyObject *perm)
NPY_NO_EXPORT PyObject * PyArray_Diagonal (PyArrayObject *self, int offset, int axis1, int axis2)
NPY_NO_EXPORT PyObject * PyArray_Compress (PyArrayObject *self, PyObject *condition, int axis, PyArrayObject *out)
NPY_NO_EXPORT npy_intp count_boolean_trues (int ndim, char *data, npy_intp *ashape, npy_intp *astrides)
NPY_NO_EXPORT npy_intp PyArray_CountNonzero (PyArrayObject *self)
NPY_NO_EXPORT PyObject * PyArray_Nonzero (PyArrayObject *self)
NPY_NO_EXPORT PyObject * PyArray_MultiIndexGetItem (PyArrayObject *self, npy_intp *multi_index)
NPY_NO_EXPORT int PyArray_MultiIndexSetItem (PyArrayObject *self, npy_intp *multi_index, PyObject *obj)

Variables

static PyArrayObjectglobal_obj
static char * global_data

Define Documentation

#define NPY_NO_DEPRECATED_API   NPY_API_VERSION
#define SWAPAXES (   op,
  ap 
)
Value:
{ \
        orign = PyArray_NDIM(ap)-1; \
        if (axis != orign) { \
            (op) = (PyArrayObject *)PyArray_SwapAxes((ap), axis, orign); \
            Py_DECREF((ap)); \
            if ((op) == NULL) return NULL; \
        } \
        else (op) = (ap); \
    }
Consumes reference to ap (op gets it) op contains a version of the array with axes swapped if local variable axis is not the last dimension. Origin must be defined locally.
#define SWAPAXES2 (   ap)
Value:
{ \
        orign = PyArray_NDIM(ap)-1; \
        if (axis != orign) { \
            SWAPINTP(PyArray_DIMS(ap)[axis], PyArray_DIMS(ap)[orign]); \
            SWAPINTP(PyArray_STRIDES(ap)[axis], PyArray_STRIDES(ap)[orign]); \
            PyArray_UpdateFlags(ap, NPY_ARRAY_C_CONTIGUOUS | \
                                    NPY_ARRAY_F_CONTIGUOUS); \
        } \
    }
#define SWAPBACK (   op,
  ap 
)
Value:
{                                      \
        if (axis != orign) {                                    \
            (op) = (PyArrayObject *)PyArray_SwapAxes((ap), axis, orign); \
            Py_DECREF((ap));                                    \
            if ((op) == NULL) return NULL;                      \
        }                                                       \
        else (op) = (ap);                                       \
    }
Consumes reference to ap (op gets it) origin must be previously defined locally. SWAPAXES must have been called previously. op contains the swapped version of the array.
#define SWAPBACK2 (   ap)
Value:
{ \
        if (axis != orign) { \
            SWAPINTP(PyArray_DIMS(ap)[axis], PyArray_DIMS(ap)[orign]); \
            SWAPINTP(PyArray_STRIDES(ap)[axis], PyArray_STRIDES(ap)[orign]); \
            PyArray_UpdateFlags(ap, NPY_ARRAY_C_CONTIGUOUS | \
                                    NPY_ARRAY_F_CONTIGUOUS); \
        } \
    }
#define SWAPINTP (   a,
 
)    {npy_intp c; c=(a); (a) = (b); (b) = c;}
These swap axes in-place if necessary

Function Documentation

static PyObject* _new_argsort ( PyArrayObject op,
int  axis,
NPY_SORTKIND  which 
) [static]

Referenced by argsort_static_compare().

static int _new_sort ( PyArrayObject op,
int  axis,
NPY_SORTKIND  which 
) [static]
These algorithms use special sorting. They are not called unless the underlying sort function for the type is available. Note that axis is already valid. The sort functions require 1-d contiguous and well-behaved data. Therefore, a copy will be made of the data if needed before handing it to the sorting routine. An iterator is constructed and adjusted to walk over all but the desired sorting axis.

References _strided_byte_swap(), _unaligned_strided_byte_copy(), PyArrayIterObject_tag::dataptr, PyArray_ITER_NEXT, PyDataMem_FREE(), and PyDataMem_NEW().

static int argsort_static_compare ( const void *  ip1,
const void *  ip2 
) [static]

References _new_argsort().

NPY_NO_EXPORT npy_intp count_boolean_trues ( int  ndim,
char *  data,
npy_intp ashape,
npy_intp astrides 
)
Counts the number of True values in a raw boolean array. This is a low-overhead function which does no heap allocations.
Returns -1 on error.
Use raw iteration with no heap memory allocation
Handle zero-sized array
Special case for contiguous inner loop
Process the innermost dimension
General inner loop
Process the innermost dimension
static int local_argsearch_left ( PyArrayObject arr,
PyArrayObject key,
PyArrayObject sorter,
PyArrayObject ret 
) [static]
&#64;brief Use bisection of sorted array to find first entries >= keys.
For each key use bisection to find the first index i s.t. key <= arr[i]. When there is no such index i, set i = len(arr). Return the results in ret. All arrays are assumed contiguous on entry and both arr and key must be of the same comparable type.
&#64;param arr contiguous sorted array to be searched. &#64;param key contiguous array of keys. &#64;param ret contiguous array of intp for returned indices. &#64;return int
static int local_argsearch_right ( PyArrayObject arr,
PyArrayObject key,
PyArrayObject sorter,
PyArrayObject ret 
) [static]
&#64;brief Use bisection of sorted array to find first entries > keys.
For each key use bisection to find the first index i s.t. key < arr[i]. When there is no such index i, set i = len(arr). Return the results in ret. All arrays are assumed contiguous on entry and both arr and key must be of the same comparable type.
&#64;param arr contiguous sorted array to be searched. &#64;param key contiguous array of keys. &#64;param ret contiguous array of intp for returned indices. &#64;return int

References NPY_ARRAY_DEFAULT, NPY_ARRAY_NOTSWAPPED, NPY_BEGIN_THREADS_DEF, NPY_INTP, Py_TYPE, PyArray_CheckFromAny(), PyArray_DESCR, PyArray_DescrFromObject(), PyArray_DescrFromType(), PyArray_DIMS, PyArray_FromArray(), PyArray_ISINTEGER, PyArray_NDIM, PyArray_New(), and PyArray_SIZE.

static void local_search_left ( PyArrayObject arr,
PyArrayObject key,
PyArrayObject ret 
) [static]
&#64;brief Use bisection of sorted array to find first entries >= keys.
For each key use bisection to find the first index i s.t. key <= arr[i]. When there is no such index i, set i = len(arr). Return the results in ret. All arrays are assumed contiguous on entry and both arr and key must be of the same comparable type.
&#64;param arr contiguous sorted array to be searched. &#64;param key contiguous array of keys. &#64;param ret contiguous array of intp for returned indices. &#64;return void

Referenced by PyArray_SearchSorted().

static void local_search_right ( PyArrayObject arr,
PyArrayObject key,
PyArrayObject ret 
) [static]
&#64;brief Use bisection of sorted array to find first entries > keys.
For each key use bisection to find the first index i s.t. key < arr[i]. When there is no such index i, set i = len(arr). Return the results in ret. All arrays are assumed contiguous on entry and both arr and key must be of the same comparable type.
&#64;param arr contiguous sorted array to be searched. &#64;param key contiguous array of keys. &#64;param ret contiguous array of intp for returned indices. &#64;return void

Referenced by PyArray_SearchSorted().

NPY_NO_EXPORT PyObject* PyArray_ArgSort ( PyArrayObject op,
int  axis,
NPY_SORTKIND  which 
)
ArgSort an array
Creates new reference op2
Determine if we should use new algorithm or not
ap will contain the reference to op2

References NPY_HEAPSORT, npy_heapsort(), NPY_MERGESORT, npy_mergesort(), NPY_QUICKSORT, and npy_quicksort().

NPY_NO_EXPORT PyObject* PyArray_Choose ( PyArrayObject ip,
PyObject *  op,
PyArrayObject out,
NPY_CLIPMODE  clipmode 
)
Convert all inputs to arrays of a common type Also makes them C-contiguous
Broadcast all arrays to each other, index array at the end.
Set-up return array
we need to make sure and get a copy so the input array is not changed before the error is called
NPY_NO_EXPORT PyObject* PyArray_Compress ( PyArrayObject self,
PyObject *  condition,
int  axis,
PyArrayObject out 
)
Compress
Counts the number of non-zero elements in the array. <blockquote> Returns -1 on error.</blockquote>
Special low-overhead version specific to the boolean type
If it's a trivial one-dimensional loop, don't use an iterator
If the array has size zero, return zero (the iterator rejects size zero arrays)
Otherwise create and use an iterator to count the nonzeros.
Get the pointers for inner loop iteration
Iterate over all the elements to count the nonzeros
NPY_NO_EXPORT PyObject* PyArray_Diagonal ( PyArrayObject self,
int  offset,
int  axis1,
int  axis2 
)
Diagonal <blockquote> In NumPy versions prior to 1.7, this function always returned a copy of the diagonal array. In 1.7, the code has been updated to compute a view onto 'self', but it still copies this array before returning, as well as setting the internal WARN_ON_WRITE flag. In a future version, it will simply return a view onto self.</blockquote>
Handle negative axes with standard Python indexing rules
Error check the two axes
Get the shape and strides of the two axes
Compute the data pointers and diag_size for the view
Build the new shape and strides for the main data
Create the diagonal view
For backwards compatibility, during the deprecation period:
NPY_NO_EXPORT PyObject* PyArray_LexSort ( PyObject *  sort_keys,
int  axis 
)
LexSort an array providing indices that will sort a collection of arrays lexicographically. The first key is sorted on first, followed by the second key -- requires that arg"merge"sort is available for each sort_key
Returns an index array that shows the indexes for the lexicographic sort along the given axis.
Now we can check the axis
single element case
Now do the sorting
NPY_NO_EXPORT PyObject* PyArray_MultiIndexGetItem ( PyArrayObject self,
npy_intp multi_index 
)
Gets a single item from the array, based on a single multi-index array of values, which must be of length PyArray_NDIM(self).
Get the data pointer
NPY_NO_EXPORT int PyArray_MultiIndexSetItem ( PyArrayObject self,
npy_intp multi_index,
PyObject *  obj 
)
Sets a single item in the array, based on a single multi-index array of values, which must be of length PyArray_NDIM(self).
Returns 0 on success, -1 on failure.
Get the data pointer
Nonzero <blockquote> TODO: In NumPy 2.0, should make the iteration order a parameter.</blockquote>
First count the number of non-zeros in 'self'.
Allocate the result as a 2D array
If it's a one-dimensional result, don't use an iterator
Build an iterator tracking a multi-index, in C order.
Get the pointers for inner loop iteration
Get the multi-index for each non-zero element
Treat zero-dimensional as shape (1,)
Create views into ret, one for each dimension
Directly switch to one dimensions (dimension 1 is 1 anyway)
NPY_NO_EXPORT PyObject* PyArray_PutMask ( PyArrayObject self,
PyObject *  values0,
PyObject *  mask0 
)
Put values into an array according to a mask.

<

zero if null array
NPY_NO_EXPORT PyObject* PyArray_PutTo ( PyArrayObject self,
PyObject *  values0,
PyObject *  indices0,
NPY_CLIPMODE  clipmode 
)
Put values into an array
NPY_NO_EXPORT PyObject* PyArray_Repeat ( PyArrayObject aop,
PyObject *  op,
int  axis 
)
Repeat the array.
nd == 0
Construct new array
NPY_NO_EXPORT PyObject* PyArray_SearchSorted ( PyArrayObject op1,
PyObject *  op2,
NPY_SEARCHSIDE  side,
PyObject *  perm 
)
Search the sorted array op1 for the location of the items in op2. The

result is an array of indexes, one for each element in op2, such that if the item were to be inserted in op1 just before that index the array would still be in sorted order.

System Message: SEVERE/4 (<string>, line 7)
Unexpected section title.

Parameters
----------
op1 : PyArrayObject *
Array to be searched, must be 1-D.
op2 : PyObject *
Array of items whose insertion indexes in op1 are wanted
side : {NPY_SEARCHLEFT, NPY_SEARCHRIGHT}
If NPY_SEARCHLEFT, return first valid insertion indexes If NPY_SEARCHRIGHT, return last valid insertion indexes
perm : PyObject *
Permutation array that sorts op1 (optional)
System Message: SEVERE/4 (<string>, line 19)
Unexpected section title.

Returns
-------
ret : PyObject *
New reference to npy_intp array containing indexes where items in op2 could be validly inserted into op1. NULL on error.
System Message: SEVERE/4 (<string>, line 25)
Unexpected section title.

Notes
-----

Binary search is used to find the indexes.

Find common type
need ap1 as contiguous array and of right type
need ap2 as contiguous array and of right type
check that comparison function exists
need ap3 as contiguous array and of right type
convert to known integer size
ret is a contiguous array of intp type to hold returned indices

References local_search_left(), local_search_right(), NPY_BEGIN_THREADS_DESCR, NPY_END_THREADS_DESCR, NPY_SEARCHLEFT, NPY_SEARCHRIGHT, and PyArray_DESCR.

NPY_NO_EXPORT int PyArray_Sort ( PyArrayObject op,
int  axis,
NPY_SORTKIND  which 
)
Sort an array in-place
Determine if we should use type-specific algorithm or not
Store global -- allows re-entry -- restore before leaving

<

Should update op if needed
static int sortCompare ( const void *  a,
const void *  b 
) [static]

Variable Documentation

char* global_data [static]
Be sure to save this global_compare when necessary