Back to index

python-biopython  1.60
Classes | Defines | Functions | Variables
KDTreemodule.c File Reference
#include <Python.h>
#include <numpy/arrayobject.h>
#include "KDTree.h"

Go to the source code of this file.

Classes

struct  PyNeighbor
struct  PyTree

Defines

#define Py_TYPE(o)   ((o)->ob_type)
#define PyVarObject_HEAD_INIT(type, size)   PyObject_HEAD_INIT(type) size,

Functions

static int PyNeighbor_init (PyNeighbor *self, PyObject *args, PyObject *kwds)
static PyObject * PyNeighbor_repr (PyNeighbor *self)
static PyObject * PyNeighbor_getindex1 (PyNeighbor *self, void *closure)
static int PyNeighbor_setindex1 (PyNeighbor *self, PyObject *value, void *closure)
static PyObject * PyNeighbor_getindex2 (PyNeighbor *self, void *closure)
static int PyNeighbor_setindex2 (PyNeighbor *self, PyObject *value, void *closure)
static PyObject * PyNeighbor_getradius (PyNeighbor *self, void *closure)
static int PyNeighbor_setradius (PyNeighbor *self, PyObject *value, void *closure)
static void PyTree_dealloc (PyTree *self)
static int PyTree_init (PyTree *self, PyObject *args, PyObject *kwds)
static PyObject * PyTree_get_count (PyTree *self)
static PyObject * PyTree_neighbor_get_count (PyTree *self)
static PyObject * PyTree_set_data (PyTree *self, PyObject *args)
static PyObject * PyTree_search_center_radius (PyTree *self, PyObject *args)
static PyObject * PyTree_neighbor_search (PyTree *self, PyObject *args)
static PyObject * PyTree_neighbor_simple_search (PyTree *self, PyObject *args)
static PyObject * PyTree_get_indices (PyTree *self)
static PyObject * PyTree_get_radii (PyTree *self)
void init_CKDTree (void)

Variables

static char PyNeighbor_index1__doc__ [] = "index of the first neighbor"
static char PyNeighbor_index2__doc__ [] = "index of the second neighbor"
static char PyNeighbor_radius__doc__ [] = "the radius\n"
static PyGetSetDef PyNeighbor_getset []
static char PyNeighbor_doc [] = "A neighbor pair; members are index1, index2, and radius.\n"
static PyTypeObject PyNeighborType
static char PyTree_get_indices__doc__ [] = "returns indices of coordinates within radius as a Numpy array\n"
static char PyTree_get_radii__doc__ [] = "returns distances of coordinates within radius as a Numpy array.\n"
static PyMethodDef PyTree_methods []
static char PyTree_doc [] = "C KDTree.\n"
static PyTypeObject PyTreeType

Class Documentation

struct PyNeighbor

Definition at line 18 of file KDTreemodule.c.

Collaboration diagram for PyNeighbor:
Class Members
PyObject_HEAD struct Neighbor
struct PyTree

Definition at line 1105 of file clustermodule.c.

Collaboration diagram for PyTree:
Class Members
int n
PyObject_HEAD Node * nodes
PyObject_HEAD struct KDTree * tree

Define Documentation

#define Py_TYPE (   o)    ((o)->ob_type)

Definition at line 8 of file KDTreemodule.c.

#define PyVarObject_HEAD_INIT (   type,
  size 
)    PyObject_HEAD_INIT(type) size,

Definition at line 13 of file KDTreemodule.c.


Function Documentation

void init_CKDTree ( void  )

Definition at line 676 of file KDTreemodule.c.

{
  PyObject *module;

  import_array();

  PyTreeType.tp_new = PyType_GenericNew;
  PyNeighborType.tp_new = PyType_GenericNew;
  if (PyType_Ready(&PyTreeType) < 0)
#if PY_MAJOR_VERSION >= 3
      return NULL;
#else
      return;
#endif
  if (PyType_Ready(&PyNeighborType) < 0)
#if PY_MAJOR_VERSION >= 3
      return NULL;
#else
      return;
#endif

#if PY_MAJOR_VERSION >= 3
  module = PyModule_Create(&moduledef);
  if (module==NULL) return NULL;
#else
  module = Py_InitModule("_CKDTree", NULL);
  if (module==NULL) return;
#endif

  Py_INCREF(&PyTreeType);
  Py_INCREF(&PyNeighborType);
  PyModule_AddObject(module, "KDTree", (PyObject*) &PyTreeType);
  PyModule_AddObject(module, "Neighbor", (PyObject*) &PyNeighborType);

  if (PyErr_Occurred()) Py_FatalError("can't initialize module _CKDTree");
#if PY_MAJOR_VERSION >= 3
  return module;
#endif
}
static PyObject* PyNeighbor_getindex1 ( PyNeighbor self,
void *  closure 
) [static]

Definition at line 58 of file KDTreemodule.c.

{
#if PY_MAJOR_VERSION >= 3
    return PyLong_FromLong(self->neighbor.index1);
#else
    return PyInt_FromLong(self->neighbor.index1);
#endif
}
static PyObject* PyNeighbor_getindex2 ( PyNeighbor self,
void *  closure 
) [static]

Definition at line 84 of file KDTreemodule.c.

{
#if PY_MAJOR_VERSION >= 3
    return PyLong_FromLong(self->neighbor.index2);
#else
    return PyInt_FromLong(self->neighbor.index2);
#endif
}
static PyObject* PyNeighbor_getradius ( PyNeighbor self,
void *  closure 
) [static]

Definition at line 107 of file KDTreemodule.c.

{
    float value = self->neighbor.radius;
    return PyFloat_FromDouble((double)value);
}
static int PyNeighbor_init ( PyNeighbor self,
PyObject *  args,
PyObject *  kwds 
) [static]

Definition at line 24 of file KDTreemodule.c.

{
    long int index1, index2;
    float radius = 0.0;
    static char *kwlist[] = {"index1", "index2", "radius", NULL};

    if (! PyArg_ParseTupleAndKeywords(args, kwds, "ii|d", kwlist, 
                                      &index1, &index2, &radius))
        return -1;
    self->neighbor.index1 = index1;
    self->neighbor.index2 = index2;
    self->neighbor.radius = radius;

    return 0;
}
static PyObject* PyNeighbor_repr ( PyNeighbor self) [static]

Definition at line 41 of file KDTreemodule.c.

{
    char string[64];
    sprintf(string, "(%ld, %ld): %g",
            self->neighbor.index1, self->neighbor.index2, self->neighbor.radius);
#if PY_MAJOR_VERSION >= 3
    return PyUnicode_FromString(string);
#else
    return PyString_FromString(string);
#endif

}
static int PyNeighbor_setindex1 ( PyNeighbor self,
PyObject *  value,
void *  closure 
) [static]

Definition at line 68 of file KDTreemodule.c.

{
#if PY_MAJOR_VERSION >= 3
    long index1 = PyLong_AsLong(value);
#else
    long index1 = PyInt_AsLong(value);
#endif
    if (PyErr_Occurred()) return -1;
    self->neighbor.index1 = index1;
    return 0;
}
static int PyNeighbor_setindex2 ( PyNeighbor self,
PyObject *  value,
void *  closure 
) [static]

Definition at line 94 of file KDTreemodule.c.

{
#if PY_MAJOR_VERSION >= 3
    long index2 = PyLong_AsLong(value);
#else
    long index2 = PyInt_AsLong(value);
#endif
    if (PyErr_Occurred()) return -1;
    self->neighbor.index2 = index2;
    return 0;
}
static int PyNeighbor_setradius ( PyNeighbor self,
PyObject *  value,
void *  closure 
) [static]

Definition at line 114 of file KDTreemodule.c.

{ const double radius = PyFloat_AsDouble(value);
  if (PyErr_Occurred()) return -1;
  self->neighbor.radius = (float)radius;
  return 0;
}
static void PyTree_dealloc ( PyTree self) [static]

Definition at line 179 of file KDTreemodule.c.

{
    KDTree_destroy(self->tree);
    Py_TYPE(self)->tp_free((PyObject*)self);
}

Here is the call graph for this function:

static PyObject* PyTree_get_count ( PyTree self) [static]

Definition at line 212 of file KDTreemodule.c.

{
    long count;
    struct KDTree* tree = self->tree;
    PyObject* result;
    count = KDTree_get_count(tree);
#if PY_MAJOR_VERSION >= 3
    result = PyLong_FromLong(count);
#else
    result = PyInt_FromLong(count);
#endif
    if (!result)
    {
        PyErr_SetString (PyExc_MemoryError, "Failed to allocate memory for object.");
        return NULL;
    }
    return result;
}

Here is the call graph for this function:

static PyObject* PyTree_get_indices ( PyTree self) [static]

Definition at line 542 of file KDTreemodule.c.

{
       npy_intp length;
       PyArrayObject *array;
       struct KDTree* tree = self->tree;
 
       length=KDTree_get_count(tree);
       
       if (length==0)
       {
              Py_INCREF(Py_None);
              return Py_None;
       }

       array=(PyArrayObject *) PyArray_SimpleNew(1, &length, PyArray_LONG);
       if (!array)
       {
              PyErr_SetString(PyExc_MemoryError,
                            "Insufficient memory for array");
              return NULL;
       }

       /* copy the data into the Numpy data pointer */
       KDTree_copy_indices(tree, (long int *) PyArray_BYTES(array));
       return PyArray_Return(array);
}

Here is the call graph for this function:

static PyObject* PyTree_get_radii ( PyTree self) [static]

Definition at line 572 of file KDTreemodule.c.

{
       npy_intp length;
       PyArrayObject *array;
       struct KDTree* tree = self->tree;
        
       length=KDTree_get_count(tree);

       if (length==0)
       {
              Py_INCREF(Py_None);
              return Py_None;
       }
              
       array=(PyArrayObject *) PyArray_SimpleNew(1, &length, PyArray_FLOAT);
       if (!array)
       {
              PyErr_SetString(PyExc_MemoryError,
                            "Insufficient memory for array");
              return NULL;
       }

       /* copy the data into the Numpy data pointer */
       KDTree_copy_radii(tree, (float *) PyArray_BYTES(array));
       return PyArray_Return(array);
}                                   

Here is the call graph for this function:

static int PyTree_init ( PyTree self,
PyObject *  args,
PyObject *  kwds 
) [static]

Definition at line 186 of file KDTreemodule.c.

{
    int dim;
    int bucket_size;
    struct KDTree* tree;
   
    if(!PyArg_ParseTuple(args, "ii:KDTree_init" ,&dim, &bucket_size)) return -1;

    if (dim <= 0 || bucket_size <= 0)
    {
        PyErr_SetString(PyExc_ValueError, "Both arguments should be positive");
        return -1;
    }

    tree = KDTree_init(dim, bucket_size);
    if (tree==NULL)
    {
        PyErr_SetString(PyExc_MemoryError, "Insufficient memory for tree");
       return -1;
    }

    self->tree = tree;
    return 0;
}

Here is the call graph for this function:

static PyObject* PyTree_neighbor_get_count ( PyTree self) [static]

Definition at line 232 of file KDTreemodule.c.

{
    long count;
    struct KDTree* tree = self->tree;
    PyObject* result;
    count = KDTree_neighbor_get_count(tree);
#if PY_MAJOR_VERSION >= 3
    result = PyLong_FromLong(count);
#else
    result = PyInt_FromLong(count);
#endif
    if (!result)
    {
        PyErr_SetString (PyExc_MemoryError, "Failed to allocate memory for object.");
        return NULL;
    }
    return result;
}

Here is the call graph for this function:

static PyObject* PyTree_neighbor_search ( PyTree self,
PyObject *  args 
) [static]

Definition at line 416 of file KDTreemodule.c.

{
    int ok;
    double radius;
    struct KDTree* tree = self->tree;
    struct Neighbor* neighbors;
    struct Neighbor* pp, *qq;
    PyObject* list;
    Py_ssize_t i, n;

    if(!PyArg_ParseTuple(args, "d:KDTree_neighbor_search", &radius))
        return NULL;

    if(radius <= 0)
    {
        PyErr_SetString(PyExc_ValueError, "Radius must be positive.");
        return NULL;
    }

    ok = KDTree_neighbor_search(tree, radius, &neighbors);
    if (!ok)
    {
        PyErr_SetString(PyExc_MemoryError,
            "calculation failed due to lack of memory");
        return NULL;
    }

    pp = neighbors;
    n = 0;
    while (pp)
    {
        n+=1;
        pp = pp->next;
    }

    list = PyList_New(n);
    if (list)
    {
        PyNeighbor* p;
        pp = neighbors;
        for (i = 0; i < n; i++)
        {
            p = (PyNeighbor*) PyNeighborType.tp_alloc(&PyNeighborType, 0);
            if(!p)
            {
                PyErr_SetString(PyExc_MemoryError,
                    "could not create node for return value");
                Py_DECREF(list);
                return NULL;
            }
            p->neighbor = *pp;
            PyList_SET_ITEM(list, i, (PyObject*)p);
            qq = pp->next;
            free(pp);
            pp = qq;
        }
    }

    return list;
}

Here is the call graph for this function:

static PyObject* PyTree_neighbor_simple_search ( PyTree self,
PyObject *  args 
) [static]

Definition at line 478 of file KDTreemodule.c.

{
    int ok;
    double radius;
    struct KDTree* tree = self->tree;
    struct Neighbor* neighbors;
    struct Neighbor* pp, *qq;
    PyObject* list;
    Py_ssize_t i, n;

    if(!PyArg_ParseTuple(args, "d:KDTree_neighbor_simple_search", &radius))
        return NULL;

    if(radius <= 0)
    {
        PyErr_SetString(PyExc_ValueError, "Radius must be positive.");
        return NULL;
    }

    ok = KDTree_neighbor_simple_search(tree, radius, &neighbors);
    if (!ok)
    {
        PyErr_SetString(PyExc_MemoryError,
            "calculation failed due to lack of memory");
        return NULL;
    }

    pp = neighbors;
    n = 0;
    while (pp)
    {
        n+=1;
        pp = pp->next;
    }

    list = PyList_New(n);
    if (list)
    {
        PyNeighbor* p;
        pp = neighbors;
        for (i = 0; i < n; i++)
        {
            p = (PyNeighbor*) PyNeighborType.tp_alloc(&PyNeighborType, 0);
            if(!p)
            {
                PyErr_SetString(PyExc_MemoryError,
                    "could not create node for return value");
                Py_DECREF(list);
                return NULL;
            }
            p->neighbor = *pp;
            PyList_SET_ITEM(list, i, (PyObject*)p);
            qq = pp->next;
            free(pp);
            pp = qq;
        }
    }

    return list;
}

Here is the call graph for this function:

static PyObject* PyTree_search_center_radius ( PyTree self,
PyObject *  args 
) [static]

Definition at line 333 of file KDTreemodule.c.

{
    PyObject *obj;
    double radius;
    PyArrayObject *array;
    long int n, i;
    float *coords;
    struct KDTree* tree = self->tree;
    int ok;
    npy_intp stride;
    const char* p;

    if(!PyArg_ParseTuple(args, "Od:KDTree_search_center_radius", &obj ,&radius))
        return NULL;

    if(radius <= 0)
    {
        PyErr_SetString(PyExc_ValueError, "Radius must be positive.");
        return NULL;
    }

    /* Check if it is an array */
    if (!PyArray_Check(obj))
    {
        PyErr_SetString(PyExc_TypeError, "First argument must be an array.");
        return NULL;
    }
    array=(PyArrayObject *) obj;

    if(PyArray_NDIM(array)!=1)
    {
        PyErr_SetString(PyExc_ValueError, "Array must be one dimensional.");
        return NULL;
    }
    if (PyArray_TYPE(array) == NPY_DOUBLE)
    {
        Py_INCREF(obj);
    }
    else
    {
        /* Cast to type double */
        obj = PyArray_Cast(array, NPY_DOUBLE);
        if (!obj)
        {
            PyErr_SetString(PyExc_ValueError,
                            "coordinates cannot be cast to needed type.");
            return NULL;
        }
        array = (PyArrayObject*) obj;
    }

    n = (long int) PyArray_DIM(array, 0);

    /* coord_data is deleted by the KDTree object */
    coords= malloc(n*sizeof(float));
    if (!coords)
    {
        Py_DECREF(obj);
        PyErr_SetString (PyExc_MemoryError, "Failed to allocate memory for coordinates.");
        return NULL;
    }

    stride =  PyArray_STRIDE(array, 0);
    p = PyArray_BYTES(array);
    for (i=0; i<n; i++)
    {
        coords[i]=*(double *) (p+i*stride);
    }
    Py_DECREF(obj);

    ok = KDTree_search_center_radius(tree, coords, radius);

    if (!ok)
    {
        PyErr_SetString (PyExc_MemoryError, "Insufficient memory for calculation.");
        return NULL;
    }

    Py_INCREF(Py_None);
    return Py_None;
}

Here is the call graph for this function:

static PyObject* PyTree_set_data ( PyTree self,
PyObject *  args 
) [static]

Definition at line 252 of file KDTreemodule.c.

{
    float* coords;
    long int n, m, i;
    PyObject *obj;
    PyArrayObject *array;
    struct KDTree* tree = self->tree;
    int ok;
    npy_intp rowstride, colstride;
    const char* p;

    if(!PyArg_ParseTuple(args, "O:KDTree_set_data",&obj)) return NULL;

    /* Check if it is an array */
    if (!PyArray_Check(obj))
    {
        PyErr_SetString(PyExc_TypeError, "First argument must be an array.");
        return NULL;
    }
    array=(PyArrayObject *) obj;
    if(PyArray_NDIM(array)!=2)
    {
        PyErr_SetString(PyExc_ValueError, "Array must be two dimensional.");
        return NULL;
    }
    if (PyArray_TYPE(array) == NPY_DOUBLE)
    {
        Py_INCREF(obj);
    }
    else
    {
        /* Cast to type double */
        obj = PyArray_Cast(array, NPY_DOUBLE);
        if (!obj)
        {
            PyErr_SetString(PyExc_ValueError,
                            "coordinates cannot be cast to needed type.");
            return NULL;
        }
        array = (PyArrayObject*) obj;
    }

    n = (long int) PyArray_DIM(array, 0);
    m = (long int) PyArray_DIM(array, 1);

    /* coord_data is deleted by the KDTree object */
    coords= malloc(m*n*sizeof(float));
    if (!coords)
    {
        Py_DECREF(obj);
        PyErr_SetString (PyExc_MemoryError, "Failed to allocate memory for coordinates.");
        return NULL;
    }

    rowstride =  PyArray_STRIDE(array, 0);
    colstride =  PyArray_STRIDE(array, 1);
    p = PyArray_BYTES(array);

    for (i=0; i<n; i++)
    {
        int j;

        for (j=0; j<m; j++)
        {
            coords[i*m+j]=*(double *) (p+i*rowstride+j*colstride);
        }
    }  
    Py_DECREF(obj);

    ok = KDTree_set_data(tree, coords, n);
    if (!ok)
    {
        PyErr_SetString (PyExc_MemoryError, "Failed to allocate memory for nodes.");
        return NULL;
    }

    Py_INCREF(Py_None);
    return Py_None;
}

Here is the call graph for this function:


Variable Documentation

char PyNeighbor_doc[] = "A neighbor pair; members are index1, index2, and radius.\n" [static]

Definition at line 131 of file KDTreemodule.c.

PyGetSetDef PyNeighbor_getset[] [static]
Initial value:
 {
    {"index1", (getter)PyNeighbor_getindex1, (setter)PyNeighbor_setindex1, PyNeighbor_index1__doc__, NULL},
    {"index2", (getter)PyNeighbor_getindex2, (setter)PyNeighbor_setindex2, PyNeighbor_index2__doc__, NULL},
    {"radius", (getter)PyNeighbor_getradius, (setter)PyNeighbor_setradius, PyNeighbor_radius__doc__, NULL},
    {NULL}  
}

Definition at line 124 of file KDTreemodule.c.

char PyNeighbor_index1__doc__[] = "index of the first neighbor" [static]

Definition at line 54 of file KDTreemodule.c.

char PyNeighbor_index2__doc__[] = "index of the second neighbor" [static]

Definition at line 80 of file KDTreemodule.c.

char PyNeighbor_radius__doc__[] = "the radius\n" [static]

Definition at line 121 of file KDTreemodule.c.

PyTypeObject PyNeighborType [static]

Definition at line 134 of file KDTreemodule.c.

char PyTree_doc[] = "C KDTree.\n" [static]

Definition at line 611 of file KDTreemodule.c.

char PyTree_get_indices__doc__[] = "returns indices of coordinates within radius as a Numpy array\n" [static]

Definition at line 539 of file KDTreemodule.c.

char PyTree_get_radii__doc__[] = "returns distances of coordinates within radius as a Numpy array.\n" [static]

Definition at line 569 of file KDTreemodule.c.

Initial value:
 {
    {"get_count", (PyCFunction)PyTree_get_count, METH_NOARGS, NULL},
    {"set_data", (PyCFunction)PyTree_set_data, METH_VARARGS, NULL},
    {"search_center_radius", (PyCFunction)PyTree_search_center_radius, METH_VARARGS, NULL},
    {"neighbor_get_count", (PyCFunction)PyTree_neighbor_get_count, METH_NOARGS, NULL},
    {"neighbor_search", (PyCFunction)PyTree_neighbor_search, METH_VARARGS, NULL},
    {"neighbor_simple_search", (PyCFunction)PyTree_neighbor_simple_search, METH_VARARGS, NULL},
    {"get_indices", (PyCFunction)PyTree_get_indices, METH_NOARGS, PyTree_get_indices__doc__},
    {"get_radii", (PyCFunction)PyTree_get_radii, METH_NOARGS, PyTree_get_radii__doc__},
    {NULL}  
}

Definition at line 599 of file KDTreemodule.c.

PyTypeObject PyTreeType [static]

Definition at line 613 of file KDTreemodule.c.