Kanwei Li avatar Kanwei Li committed ca8cc86

More docs, tabs -> spaces

Comments (0)

Files changed (4)

lib/bx/intervals/cluster.c

-/* Generated by Pyrex 0.9.8.5 on Tue Aug 18 13:11:29 2009 */
+/* Generated by Pyrex 0.9.8.5 on Tue Aug 18 15:48:59 2009 */
 
 #define PY_SSIZE_T_CLEAN
 #include "Python.h"
 static char *__pyx_filename;
 static char **__pyx_f;
 
-static char __pyx_mdoc[] = "\nKanwei Li, 2009\nInspired by previous ClusterTree\n\nProvides a ClusterTree data structure that supports efficient finding of \nclusters of intervals that are within a certain distance apart.\n\nThis clustering algorithm uses a binary tree structure. Nodes correspond to \nnon-overlapping intervals, where overlapping means that the distance between\ntwo	intervals is less or equal to the max separation.\n\nThe tree self-balances using rotations based on the binomial sequence. Merges\namong nodes are performed whenever a node is changed/added that will cause other\nnodes to form a new cluster.\n\nC source code is in src/cluster.c\n";
+static char __pyx_mdoc[] = "\nKanwei Li, 2009\nInspired by previous ClusterTree\n\nProvides a ClusterTree data structure that supports efficient finding of \nclusters of intervals that are within a certain distance apart.\n\nThis clustering algorithm uses a binary tree structure. Nodes correspond to \nnon-overlapping intervals, where overlapping means that the distance between\ntwo intervals is less or equal to the max separation.\n\nThe tree self-balances using rotations based on the binomial sequence. Merges\namong nodes are performed whenever a node is changed/added that will cause other\nnodes to form a new cluster.\n\nC source code is in src/cluster.c\n";
 
 static void __Pyx_Raise(PyObject *type, PyObject *value, PyObject *tb); /*proto*/
 
 }
 
 static PyObject *__pyx_f_2bx_9intervals_7cluster_11ClusterTree_insert(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
+static char __pyx_doc_2bx_9intervals_7cluster_11ClusterTree_insert[] = " Insert an interval with start, end, id as parameters";
 static PyObject *__pyx_f_2bx_9intervals_7cluster_11ClusterTree_insert(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
   PyObject *__pyx_v_s = 0;
   PyObject *__pyx_v_e = 0;
   Py_INCREF(__pyx_v_e);
   Py_INCREF(__pyx_v_id);
 
-  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":70 */
-  if (PyObject_Cmp(__pyx_v_s, __pyx_v_e, &__pyx_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 70; goto __pyx_L1;}
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":71 */
+  if (PyObject_Cmp(__pyx_v_s, __pyx_v_e, &__pyx_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; goto __pyx_L1;}
   __pyx_1 = __pyx_1 > 0;
   if (__pyx_1) {
-    __pyx_2 = PyTuple_New(1); if (!__pyx_2) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 70; goto __pyx_L1;}
+    __pyx_2 = PyTuple_New(1); if (!__pyx_2) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; goto __pyx_L1;}
     Py_INCREF(__pyx_k1p);
     PyTuple_SET_ITEM(__pyx_2, 0, __pyx_k1p);
-    __pyx_3 = PyObject_CallObject(PyExc_ValueError, __pyx_2); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 70; goto __pyx_L1;}
+    __pyx_3 = PyObject_CallObject(PyExc_ValueError, __pyx_2); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; goto __pyx_L1;}
     Py_DECREF(__pyx_2); __pyx_2 = 0;
     __Pyx_Raise(__pyx_3, 0, 0);
     Py_DECREF(__pyx_3); __pyx_3 = 0;
-    {__pyx_filename = __pyx_f[0]; __pyx_lineno = 70; goto __pyx_L1;}
+    {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; goto __pyx_L1;}
     goto __pyx_L2;
   }
   __pyx_L2:;
 
-  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":71 */
-  __pyx_1 = PyInt_AsLong(__pyx_v_s); if (PyErr_Occurred()) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; goto __pyx_L1;}
-  __pyx_4 = PyInt_AsLong(__pyx_v_e); if (PyErr_Occurred()) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; goto __pyx_L1;}
-  __pyx_5 = PyInt_AsLong(__pyx_v_id); if (PyErr_Occurred()) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; goto __pyx_L1;}
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":72 */
+  __pyx_1 = PyInt_AsLong(__pyx_v_s); if (PyErr_Occurred()) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 72; goto __pyx_L1;}
+  __pyx_4 = PyInt_AsLong(__pyx_v_e); if (PyErr_Occurred()) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 72; goto __pyx_L1;}
+  __pyx_5 = PyInt_AsLong(__pyx_v_id); if (PyErr_Occurred()) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 72; goto __pyx_L1;}
   ((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->tree->root = clusternode_insert(((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->tree,((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->tree->root,__pyx_1,__pyx_4,__pyx_5);
 
   __pyx_r = Py_None; Py_INCREF(Py_None);
 }
 
 static PyObject *__pyx_f_2bx_9intervals_7cluster_11ClusterTree_getregions(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
+static char __pyx_doc_2bx_9intervals_7cluster_11ClusterTree_getregions[] = " Returns a list clusters in ascending order of starting position.\n            Each cluster is a tuple of (start, end, [sorted ids of intervals in cluster])\n        \n        tree = ClusterTree(0, 0)\n        Insert (6, 7, 1), (1, 2, 3), (9, 10, 2), (3, 4, 0), (3, 8, 4)\n        tree.getregions() returns [(1, 2, [3]), (3, 8, [0, 1, 4]), (9, 10, [2])]\n        ";
 static PyObject *__pyx_f_2bx_9intervals_7cluster_11ClusterTree_getregions(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
   treeitr *__pyx_v_itr;
   interval *__pyx_v_ival;
   __pyx_v_regions = Py_None; Py_INCREF(Py_None);
   __pyx_v_ids = Py_None; Py_INCREF(Py_None);
 
-  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":77 */
-  __pyx_1 = PyList_New(0); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 77; goto __pyx_L1;}
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":85 */
+  __pyx_1 = PyList_New(0); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 85; goto __pyx_L1;}
   Py_DECREF(__pyx_v_regions);
   __pyx_v_regions = __pyx_1;
   __pyx_1 = 0;
 
-  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":78 */
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":86 */
   __pyx_v_itr = clusteritr(((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->tree);
 
-  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":80 */
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":88 */
   while (1) {
     __pyx_2 = (__pyx_v_itr != 0);
     if (!__pyx_2) break;
 
-    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":81 */
-    __pyx_1 = PyList_New(0); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 81; goto __pyx_L1;}
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":89 */
+    __pyx_1 = PyList_New(0); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 89; goto __pyx_L1;}
     Py_DECREF(__pyx_v_ids);
     __pyx_v_ids = __pyx_1;
     __pyx_1 = 0;
 
-    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":82 */
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":90 */
     __pyx_v_ival = __pyx_v_itr->node->interval_head;
 
-    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":83 */
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":91 */
     while (1) {
       __pyx_2 = (__pyx_v_ival != 0);
       if (!__pyx_2) break;
 
-      /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":84 */
-      __pyx_1 = PyObject_GetAttr(__pyx_v_ids, __pyx_n_append); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 84; goto __pyx_L1;}
-      __pyx_3 = PyInt_FromLong(__pyx_v_ival->id); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 84; goto __pyx_L1;}
-      __pyx_4 = PyTuple_New(1); if (!__pyx_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 84; goto __pyx_L1;}
+      /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":92 */
+      __pyx_1 = PyObject_GetAttr(__pyx_v_ids, __pyx_n_append); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 92; goto __pyx_L1;}
+      __pyx_3 = PyInt_FromLong(__pyx_v_ival->id); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 92; goto __pyx_L1;}
+      __pyx_4 = PyTuple_New(1); if (!__pyx_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 92; goto __pyx_L1;}
       PyTuple_SET_ITEM(__pyx_4, 0, __pyx_3);
       __pyx_3 = 0;
-      __pyx_3 = PyObject_CallObject(__pyx_1, __pyx_4); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 84; goto __pyx_L1;}
+      __pyx_3 = PyObject_CallObject(__pyx_1, __pyx_4); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 92; goto __pyx_L1;}
       Py_DECREF(__pyx_1); __pyx_1 = 0;
       Py_DECREF(__pyx_4); __pyx_4 = 0;
       Py_DECREF(__pyx_3); __pyx_3 = 0;
 
-      /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":85 */
+      /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":93 */
       __pyx_v_ival = __pyx_v_ival->next;
     }
 
-    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":87 */
-    __pyx_1 = PyObject_GetAttr(__pyx_v_regions, __pyx_n_append); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 87; goto __pyx_L1;}
-    __pyx_4 = PyInt_FromLong(__pyx_v_itr->node->start); if (!__pyx_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 87; goto __pyx_L1;}
-    __pyx_3 = PyInt_FromLong(__pyx_v_itr->node->end); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 87; goto __pyx_L1;}
-    __pyx_5 = __Pyx_GetName(__pyx_b, __pyx_n_sorted); if (!__pyx_5) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 87; goto __pyx_L1;}
-    __pyx_6 = PyTuple_New(1); if (!__pyx_6) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 87; goto __pyx_L1;}
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":95 */
+    __pyx_1 = PyObject_GetAttr(__pyx_v_regions, __pyx_n_append); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 95; goto __pyx_L1;}
+    __pyx_4 = PyInt_FromLong(__pyx_v_itr->node->start); if (!__pyx_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 95; goto __pyx_L1;}
+    __pyx_3 = PyInt_FromLong(__pyx_v_itr->node->end); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 95; goto __pyx_L1;}
+    __pyx_5 = __Pyx_GetName(__pyx_b, __pyx_n_sorted); if (!__pyx_5) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 95; goto __pyx_L1;}
+    __pyx_6 = PyTuple_New(1); if (!__pyx_6) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 95; goto __pyx_L1;}
     Py_INCREF(__pyx_v_ids);
     PyTuple_SET_ITEM(__pyx_6, 0, __pyx_v_ids);
-    __pyx_7 = PyObject_CallObject(__pyx_5, __pyx_6); if (!__pyx_7) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 87; goto __pyx_L1;}
+    __pyx_7 = PyObject_CallObject(__pyx_5, __pyx_6); if (!__pyx_7) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 95; goto __pyx_L1;}
     Py_DECREF(__pyx_5); __pyx_5 = 0;
     Py_DECREF(__pyx_6); __pyx_6 = 0;
-    __pyx_5 = PyTuple_New(3); if (!__pyx_5) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 87; goto __pyx_L1;}
+    __pyx_5 = PyTuple_New(3); if (!__pyx_5) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 95; goto __pyx_L1;}
     PyTuple_SET_ITEM(__pyx_5, 0, __pyx_4);
     PyTuple_SET_ITEM(__pyx_5, 1, __pyx_3);
     PyTuple_SET_ITEM(__pyx_5, 2, __pyx_7);
     __pyx_4 = 0;
     __pyx_3 = 0;
     __pyx_7 = 0;
-    __pyx_6 = PyTuple_New(1); if (!__pyx_6) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 87; goto __pyx_L1;}
+    __pyx_6 = PyTuple_New(1); if (!__pyx_6) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 95; goto __pyx_L1;}
     PyTuple_SET_ITEM(__pyx_6, 0, __pyx_5);
     __pyx_5 = 0;
-    __pyx_4 = PyObject_CallObject(__pyx_1, __pyx_6); if (!__pyx_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 87; goto __pyx_L1;}
+    __pyx_4 = PyObject_CallObject(__pyx_1, __pyx_6); if (!__pyx_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 95; goto __pyx_L1;}
     Py_DECREF(__pyx_1); __pyx_1 = 0;
     Py_DECREF(__pyx_6); __pyx_6 = 0;
     Py_DECREF(__pyx_4); __pyx_4 = 0;
 
-    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":88 */
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":96 */
     __pyx_v_itr = __pyx_v_itr->next;
   }
 
-  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":89 */
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":97 */
   Py_INCREF(__pyx_v_regions);
   __pyx_r = __pyx_v_regions;
   goto __pyx_L0;
 }
 
 static PyObject *__pyx_f_2bx_9intervals_7cluster_11ClusterTree_getlines(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
+static char __pyx_doc_2bx_9intervals_7cluster_11ClusterTree_getlines[] = " Similar to getregions except it just returns a list of ids of intervals\n            The above example would return [3, 0, 1, 4, 2]\n         ";
 static PyObject *__pyx_f_2bx_9intervals_7cluster_11ClusterTree_getlines(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
   treeitr *__pyx_v_itr;
   interval *__pyx_v_ival;
   __pyx_v_lines = Py_None; Py_INCREF(Py_None);
   __pyx_v_ids = Py_None; Py_INCREF(Py_None);
 
-  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":95 */
-  __pyx_1 = PyList_New(0); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 95; goto __pyx_L1;}
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":106 */
+  __pyx_1 = PyList_New(0); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 106; goto __pyx_L1;}
   Py_DECREF(__pyx_v_lines);
   __pyx_v_lines = __pyx_1;
   __pyx_1 = 0;
 
-  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":96 */
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":107 */
   __pyx_v_itr = clusteritr(((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->tree);
 
-  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":98 */
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":109 */
   while (1) {
     __pyx_2 = (__pyx_v_itr != 0);
     if (!__pyx_2) break;
 
-    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":99 */
-    __pyx_1 = PyList_New(0); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 99; goto __pyx_L1;}
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":110 */
+    __pyx_1 = PyList_New(0); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 110; goto __pyx_L1;}
     Py_DECREF(__pyx_v_ids);
     __pyx_v_ids = __pyx_1;
     __pyx_1 = 0;
 
-    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":100 */
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":111 */
     __pyx_v_ival = __pyx_v_itr->node->interval_head;
 
-    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":101 */
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":112 */
     while (1) {
       __pyx_2 = (__pyx_v_ival != 0);
       if (!__pyx_2) break;
 
-      /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":102 */
-      __pyx_1 = PyObject_GetAttr(__pyx_v_ids, __pyx_n_append); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 102; goto __pyx_L1;}
-      __pyx_3 = PyInt_FromLong(__pyx_v_ival->id); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 102; goto __pyx_L1;}
-      __pyx_4 = PyTuple_New(1); if (!__pyx_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 102; goto __pyx_L1;}
+      /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":113 */
+      __pyx_1 = PyObject_GetAttr(__pyx_v_ids, __pyx_n_append); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 113; goto __pyx_L1;}
+      __pyx_3 = PyInt_FromLong(__pyx_v_ival->id); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 113; goto __pyx_L1;}
+      __pyx_4 = PyTuple_New(1); if (!__pyx_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 113; goto __pyx_L1;}
       PyTuple_SET_ITEM(__pyx_4, 0, __pyx_3);
       __pyx_3 = 0;
-      __pyx_3 = PyObject_CallObject(__pyx_1, __pyx_4); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 102; goto __pyx_L1;}
+      __pyx_3 = PyObject_CallObject(__pyx_1, __pyx_4); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 113; goto __pyx_L1;}
       Py_DECREF(__pyx_1); __pyx_1 = 0;
       Py_DECREF(__pyx_4); __pyx_4 = 0;
       Py_DECREF(__pyx_3); __pyx_3 = 0;
 
-      /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":103 */
+      /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":114 */
       __pyx_v_ival = __pyx_v_ival->next;
     }
 
-    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":105 */
-    __pyx_1 = PyObject_GetAttr(__pyx_v_lines, __pyx_n_extend); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 105; goto __pyx_L1;}
-    __pyx_4 = __Pyx_GetName(__pyx_b, __pyx_n_sorted); if (!__pyx_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 105; goto __pyx_L1;}
-    __pyx_3 = PyTuple_New(1); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 105; goto __pyx_L1;}
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":116 */
+    __pyx_1 = PyObject_GetAttr(__pyx_v_lines, __pyx_n_extend); if (!__pyx_1) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 116; goto __pyx_L1;}
+    __pyx_4 = __Pyx_GetName(__pyx_b, __pyx_n_sorted); if (!__pyx_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 116; goto __pyx_L1;}
+    __pyx_3 = PyTuple_New(1); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 116; goto __pyx_L1;}
     Py_INCREF(__pyx_v_ids);
     PyTuple_SET_ITEM(__pyx_3, 0, __pyx_v_ids);
-    __pyx_5 = PyObject_CallObject(__pyx_4, __pyx_3); if (!__pyx_5) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 105; goto __pyx_L1;}
+    __pyx_5 = PyObject_CallObject(__pyx_4, __pyx_3); if (!__pyx_5) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 116; goto __pyx_L1;}
     Py_DECREF(__pyx_4); __pyx_4 = 0;
     Py_DECREF(__pyx_3); __pyx_3 = 0;
-    __pyx_4 = PyTuple_New(1); if (!__pyx_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 105; goto __pyx_L1;}
+    __pyx_4 = PyTuple_New(1); if (!__pyx_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 116; goto __pyx_L1;}
     PyTuple_SET_ITEM(__pyx_4, 0, __pyx_5);
     __pyx_5 = 0;
-    __pyx_3 = PyObject_CallObject(__pyx_1, __pyx_4); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 105; goto __pyx_L1;}
+    __pyx_3 = PyObject_CallObject(__pyx_1, __pyx_4); if (!__pyx_3) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 116; goto __pyx_L1;}
     Py_DECREF(__pyx_1); __pyx_1 = 0;
     Py_DECREF(__pyx_4); __pyx_4 = 0;
     Py_DECREF(__pyx_3); __pyx_3 = 0;
 
-    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":106 */
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":117 */
     __pyx_v_itr = __pyx_v_itr->next;
   }
 
-  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":107 */
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":118 */
   Py_INCREF(__pyx_v_lines);
   __pyx_r = __pyx_v_lines;
   goto __pyx_L0;
 }
 
 static struct PyMethodDef __pyx_methods_2bx_9intervals_7cluster_ClusterTree[] = {
-  {"insert", (PyCFunction)__pyx_f_2bx_9intervals_7cluster_11ClusterTree_insert, METH_VARARGS|METH_KEYWORDS, 0},
-  {"getregions", (PyCFunction)__pyx_f_2bx_9intervals_7cluster_11ClusterTree_getregions, METH_VARARGS|METH_KEYWORDS, 0},
-  {"getlines", (PyCFunction)__pyx_f_2bx_9intervals_7cluster_11ClusterTree_getlines, METH_VARARGS|METH_KEYWORDS, 0},
+  {"insert", (PyCFunction)__pyx_f_2bx_9intervals_7cluster_11ClusterTree_insert, METH_VARARGS|METH_KEYWORDS, __pyx_doc_2bx_9intervals_7cluster_11ClusterTree_insert},
+  {"getregions", (PyCFunction)__pyx_f_2bx_9intervals_7cluster_11ClusterTree_getregions, METH_VARARGS|METH_KEYWORDS, __pyx_doc_2bx_9intervals_7cluster_11ClusterTree_getregions},
+  {"getlines", (PyCFunction)__pyx_f_2bx_9intervals_7cluster_11ClusterTree_getlines, METH_VARARGS|METH_KEYWORDS, __pyx_doc_2bx_9intervals_7cluster_11ClusterTree_getlines},
   {0, 0, 0, 0}
 };
 
   if (PyObject_SetAttrString(__pyx_m, "ClusterTree", (PyObject *)&__pyx_type_2bx_9intervals_7cluster_ClusterTree) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 56; goto __pyx_L1;}
   __pyx_ptype_2bx_9intervals_7cluster_ClusterTree = &__pyx_type_2bx_9intervals_7cluster_ClusterTree;
 
-  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":91 */
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":99 */
   return;
   __pyx_L1:;
   __Pyx_AddTraceback("bx.intervals.cluster");

lib/bx/intervals/cluster.pyx

 
 This clustering algorithm uses a binary tree structure. Nodes correspond to 
 non-overlapping intervals, where overlapping means that the distance between
-two	intervals is less or equal to the max separation.
+two intervals is less or equal to the max separation.
 
 The tree self-balances using rotations based on the binomial sequence. Merges
 among nodes are performed whenever a node is changed/added that will cause other
         free_tree(self.tree)
     
     def insert(self, s, e, id):
+        ''' Insert an interval with start, end, id as parameters'''
         if s > e: raise ValueError("Interval start must be before end")
         self.tree.root = clusternode_insert(self.tree, self.tree.root, s, e, id)
                 
     def getregions(self):
+        ''' Returns a list clusters in ascending order of starting position.
+            Each cluster is a tuple of (start, end, [sorted ids of intervals in cluster])
+        
+        tree = ClusterTree(0, 0)
+        Insert (6, 7, 1), (1, 2, 3), (9, 10, 2), (3, 4, 0), (3, 8, 4)
+        tree.getregions() returns [(1, 2, [3]), (3, 8, [0, 1, 4]), (9, 10, [2])]
+        '''
         cdef treeitr *itr
         cdef interval *ival
         
         return regions
         
     def getlines(self):
+        ''' Similar to getregions except it just returns a list of ids of intervals
+            The above example would return [3, 0, 1, 4, 2]
+         '''
         cdef treeitr *itr
         cdef interval *ival
         
 /*
-	Kanwei Li, 2009
-	Inspired by previous ClusterTree
-	
-	This clustering algorithm uses a binary tree structure. Nodes correspond to 
-	non-overlapping intervals, where overlapping means that the distance between
-	two	intervals is less or equal to max_dist, which is the max separation.
-	
-	The tree self-balances using rotations based on the binomial sequence. Merges
-	among nodes are performed whenever a node is changed/added that will cause other
-	nodes to form a new cluster.
+    Kanwei Li, 2009
+    Inspired by previous ClusterTree
+    
+    This clustering algorithm uses a binary tree structure. Nodes correspond to 
+    non-overlapping intervals, where overlapping means that the distance between
+    two intervals is less or equal to max_dist, which is the max separation.
+    
+    The tree self-balances using rotations based on the binomial sequence. Merges
+    among nodes are performed whenever a node is changed/added that will cause other
+    nodes to form a new cluster.
 */
 #include <stdlib.h>
 #include <stdio.h>
 #define ALLOC(pt) (malloc(sizeof(pt)))
 
 static int min(int a, int b) {
-	if( a < b )
-		return a;
-	else
-		return b;
+    if( a < b )
+        return a;
+    else
+        return b;
 }
 
 static int max(int a, int b) {
-	if( a > b )
-		return a;
-	else
-		return b;
+    if( a > b )
+        return a;
+    else
+        return b;
 }
 
 /* Create new tree with given max_dist (max distance between intervals to be
-	considered a cluster), and min_intervals, the minimum number of intervals
-	needed for a cluster to be considered significant */
+    considered a cluster), and min_intervals, the minimum number of intervals
+    needed for a cluster to be considered significant */
 clustertree* create_clustertree(int max_dist, int min_intervals) {
-	clustertree *tree = ALLOC(clustertree);
-	tree->max_dist = max_dist;
-	tree->min_intervals = min_intervals;
-	tree->root = NULL;
-	return tree;
+    clustertree *tree = ALLOC(clustertree);
+    tree->max_dist = max_dist;
+    tree->min_intervals = min_intervals;
+    tree->root = NULL;
+    return tree;
 }
 
 static interval* create_interval(int start, int end, int id) {
-	interval *ival = ALLOC(interval);
-	
-	ival->start = start;
-	ival->end = end;
-	ival->id = id;
-	ival->next = NULL;
-	return ival;
+    interval *ival = ALLOC(interval);
+    
+    ival->start = start;
+    ival->end = end;
+    ival->id = id;
+    ival->next = NULL;
+    return ival;
 }
 
 static clusternode* create_node(int start, int end, int id) {
-	clusternode *new_node = ALLOC(clusternode);
-	
-	new_node->start		= start;
-	new_node->end		= end;
-	new_node->interval_head = create_interval(start, end, id);
-	new_node->interval_tail = new_node->interval_head;
-	new_node->num_ivals = 1;
-	new_node->left		= NULL;
-	new_node->right		= NULL;
-	
-	double uniform = ((double)rand()) / (RAND_MAX);
-	if (uniform == 1.0)
-		uniform = 0;
-	new_node->priority = (int)ceil( (-1.0 / log(.5)) * log( -1.0 / (uniform - 1)));
-	
-	return new_node;
+    clusternode *new_node = ALLOC(clusternode);
+    
+    new_node->start     = start;
+    new_node->end       = end;
+    new_node->interval_head = create_interval(start, end, id);
+    new_node->interval_tail = new_node->interval_head;
+    new_node->num_ivals = 1;
+    new_node->left      = NULL;
+    new_node->right     = NULL;
+    
+    double uniform = ((double)rand()) / (RAND_MAX);
+    if (uniform == 1.0)
+        uniform = 0;
+    new_node->priority = (int)ceil( (-1.0 / log(.5)) * log( -1.0 / (uniform - 1)));
+    
+    return new_node;
 }
 
 static void recursively_free_intervals(interval *ival) {
-	interval *next;
-	if(ival) {
-		next = ival->next;
-		free(ival);
-		recursively_free_intervals(next);
-	}
+    interval *next;
+    if(ival) {
+        next = ival->next;
+        free(ival);
+        recursively_free_intervals(next);
+    }
 }
 
 static void recursively_free_nodes(clusternode *node) {
-	if(node) {
-		recursively_free_nodes(node->left);
-		recursively_free_nodes(node->right);
-		recursively_free_intervals(node->interval_head);
-		free(node);
-	}
+    if(node) {
+        recursively_free_nodes(node->left);
+        recursively_free_nodes(node->right);
+        recursively_free_intervals(node->interval_head);
+        free(node);
+    }
 }
 
 void free_tree(clustertree *tree) {
-	recursively_free_nodes(tree->root);
-	free(tree);
+    recursively_free_nodes(tree->root);
+    free(tree);
 }
 
 void cluster_rotateright(clusternode **node) {
-	clusternode* root = (*node)->left;
-	(*node)->left = (*node)->left->right;
-	root->right = (*node);
-	*node = root;
+    clusternode* root = (*node)->left;
+    (*node)->left = (*node)->left->right;
+    root->right = (*node);
+    *node = root;
 }
 
 void cluster_rotateleft(clusternode **node) {
-	clusternode* root = (*node)->right;
-	(*node)->right = (*node)->right->left;
-	root->left = (*node);
-	*node = root;
+    clusternode* root = (*node)->right;
+    (*node)->right = (*node)->right->left;
+    root->left = (*node);
+    *node = root;
 }
 
 /* Go down the tree and merge nodes if necessary */
 void cluster_fixup(clustertree *tree, clusternode **ln, clusternode **rn) {
-	clusternode* local = *ln;
-	clusternode* root = *rn;
-	int maxstart = max(root->start, local->start);
-	int maxend = max(local->end, root->end);
-	int minstart = min(root->start, local->start);
-	int minend = min(root->end, local->end);
+    clusternode* local = *ln;
+    clusternode* root = *rn;
+    int maxstart = max(root->start, local->start);
+    int maxend = max(local->end, root->end);
+    int minstart = min(root->start, local->start);
+    int minend = min(root->end, local->end);
 
-	if( maxstart - minend <= tree->max_dist ) {
-		/* Have to merge this node and children */
-		root->start = minstart;
-		root->end = maxend;
-		root->interval_tail->next = local->interval_head;
-		root->interval_tail = local->interval_tail;
-		root->num_ivals += local->num_ivals;
-		if( local->right) cluster_fixup(tree, &(local->right), rn);
-		if( local->left) cluster_fixup(tree, &(local->left), rn);
-		if((local->right == NULL) && (local->left == NULL)) {
-			free(local);
-			*ln = NULL;
-		} else if(local->right) {
-			*ln = local->right;
-			free(local);
-		} else if (local->left) {
-			*ln = local->left;
-			free(local);
-		}
-		return;
-	}
-	// Even if we miss, we still have to check children
-	if(local->left) {
-		cluster_fixup(tree, &(local->left), rn);
-	}
-	if(local->right) {
-		cluster_fixup(tree, &(local->right), rn);
-	}
+    if( maxstart - minend <= tree->max_dist ) {
+        /* Have to merge this node and children */
+        root->start = minstart;
+        root->end = maxend;
+        root->interval_tail->next = local->interval_head;
+        root->interval_tail = local->interval_tail;
+        root->num_ivals += local->num_ivals;
+        if( local->right) cluster_fixup(tree, &(local->right), rn);
+        if( local->left) cluster_fixup(tree, &(local->left), rn);
+        if((local->right == NULL) && (local->left == NULL)) {
+            free(local);
+            *ln = NULL;
+        } else if(local->right) {
+            *ln = local->right;
+            free(local);
+        } else if (local->left) {
+            *ln = local->left;
+            free(local);
+        }
+        return;
+    }
+    // Even if we miss, we still have to check children
+    if(local->left) {
+        cluster_fixup(tree, &(local->left), rn);
+    }
+    if(local->right) {
+        cluster_fixup(tree, &(local->right), rn);
+    }
 }
 
 /* Pyrex "getregions" implements this. Only used for C debugging */
 void clustereach(clustertree *tree, clusternode *node) {
-	interval* ival;
-	if (node == NULL) {
-		exit(1); /* Shouldn't happen */
-	}
-	if (node->left != NULL) {
-		clustereach(tree, node->left);
-	}
-	printf("Node: %d\t%d\n", node->start, node->end);
-	ival = node->interval_head;
-	while(ival) {
-		printf("\tInterval %d: %d\t%d\n", ival->id, ival->start, ival->end);
-		ival = ival->next;
-	}
-	
-	if (node->right != NULL) {
-		clustereach(tree, node->right);
-	}
+    interval* ival;
+    if (node == NULL) {
+        exit(1); /* Shouldn't happen */
+    }
+    if (node->left != NULL) {
+        clustereach(tree, node->left);
+    }
+    printf("Node: %d\t%d\n", node->start, node->end);
+    ival = node->interval_head;
+    while(ival) {
+        printf("\tInterval %d: %d\t%d\n", ival->id, ival->start, ival->end);
+        ival = ival->next;
+    }
+    
+    if (node->right != NULL) {
+        clustereach(tree, node->right);
+    }
 }
 
 void clusteritr_recursive(clustertree *tree, clusternode *node, treeitr* *itr) {
-	treeitr *newitr;
+    treeitr *newitr;
 
-	if (node == NULL) {
-		return;
-	}
-	if (node->right != NULL) {
-		clusteritr_recursive(tree, node->right, itr);
-	}
-	if (node->num_ivals >= tree->min_intervals) {
-		newitr = ALLOC(treeitr);
-		newitr->next = *itr;
-		newitr->node = node;
-		*itr = newitr;
-	}
-	if (node->left != NULL) {
-		clusteritr_recursive(tree, node->left, itr);
-	}
+    if (node == NULL) {
+        return;
+    }
+    if (node->right != NULL) {
+        clusteritr_recursive(tree, node->right, itr);
+    }
+    if (node->num_ivals >= tree->min_intervals) {
+        newitr = ALLOC(treeitr);
+        newitr->next = *itr;
+        newitr->node = node;
+        *itr = newitr;
+    }
+    if (node->left != NULL) {
+        clusteritr_recursive(tree, node->left, itr);
+    }
 }
 
 /* Create an infix iterator */
 treeitr* clusteritr(clustertree *tree) {
-	treeitr *itr = NULL;
-	
-	clusteritr_recursive(tree, tree->root, &itr);
-	if (itr != NULL) {
-		return itr;
-	}
-	return NULL;
+    treeitr *itr = NULL;
+    
+    clusteritr_recursive(tree, tree->root, &itr);
+    if (itr != NULL) {
+        return itr;
+    }
+    return NULL;
 }
 
 /* Insert based on the start position of intervals */
 clusternode* clusternode_insert(clustertree *tree, clusternode *node, int start, int end, int id) {
-	int oldstart;
-	int oldend;
-	interval* ival;
-	
-	// printf("Inserting %d %d %d\n", start, end, id);
-	if (node == NULL) {
-		node = create_node(start, end, id);
-		
-	} else if ( (start - tree->max_dist) > node->end ) { /* We're to the right of this cluster */
-		node->right = clusternode_insert(tree, node->right, start, end, id);
-		if (node->priority < node->right->priority) cluster_rotateleft(&node);
-	
-	} else if ( (end + tree->max_dist) < node->start) { /* We're to the left of this cluster */
-		node->left = clusternode_insert(tree, node->left, start, end, id);
-		if (node->priority < node->left->priority) cluster_rotateright(&node);
-						
-	} else { /* We're in the range of this cluster */
-		/* Update the start and end to match to new values */
-		oldstart	= node->start;
-		oldend		= node->end;
-		node->start = min(start, node->start);
-		node->end	= max(end, node->end);
-		ival = create_interval(start, end, id);
-		ival->next = node->interval_head; /* Add this interval as the head of the interval list */
-		node->interval_head = ival;
-		node->num_ivals += 1;
-				
-		if ( oldstart > node->start && node->left != NULL ) { /* New interval added to the start, and there's a left child */
-			cluster_fixup(tree, &(node->left), &node);
-		}
-		if ( oldend < node->end && node->right != NULL ) { /* New interval added to the end, and there's a right child */
-			cluster_fixup(tree, &(node->right), &node);
-		}
-	}
-	return node;
+    int oldstart;
+    int oldend;
+    interval* ival;
+    
+    // printf("Inserting %d %d %d\n", start, end, id);
+    if (node == NULL) {
+        node = create_node(start, end, id);
+        
+    } else if ( (start - tree->max_dist) > node->end ) { /* We're to the right of this cluster */
+        node->right = clusternode_insert(tree, node->right, start, end, id);
+        if (node->priority < node->right->priority) cluster_rotateleft(&node);
+    
+    } else if ( (end + tree->max_dist) < node->start) { /* We're to the left of this cluster */
+        node->left = clusternode_insert(tree, node->left, start, end, id);
+        if (node->priority < node->left->priority) cluster_rotateright(&node);
+                        
+    } else { /* We're in the range of this cluster */
+        /* Update the start and end to match to new values */
+        oldstart    = node->start;
+        oldend      = node->end;
+        node->start = min(start, node->start);
+        node->end   = max(end, node->end);
+        ival = create_interval(start, end, id);
+        ival->next = node->interval_head; /* Add this interval as the head of the interval list */
+        node->interval_head = ival;
+        node->num_ivals += 1;
+                
+        if ( oldstart > node->start && node->left != NULL ) { /* New interval added to the start, and there's a left child */
+            cluster_fixup(tree, &(node->left), &node);
+        }
+        if ( oldend < node->end && node->right != NULL ) { /* New interval added to the end, and there's a right child */
+            cluster_fixup(tree, &(node->right), &node);
+        }
+    }
+    return node;
 }
 
 int main() {
-	
-	// Simple test
-	clustertree* tree = create_clustertree(0, 1);
-	
-	tree->root = clusternode_insert(tree, tree->root, 3, 4, 0);
-	tree->root = clusternode_insert(tree, tree->root, 6, 7, 1);
-	tree->root = clusternode_insert(tree, tree->root, 9, 10, 2);
-	tree->root = clusternode_insert(tree, tree->root, 1, 2, 3);
-	tree->root = clusternode_insert(tree, tree->root, 3, 8, 4);
-	
-	clustereach(tree, tree->root);
-	return 0;
-	
+    
+    // Simple test
+    clustertree* tree = create_clustertree(0, 1);
+    
+    tree->root = clusternode_insert(tree, tree->root, 3, 4, 0);
+    tree->root = clusternode_insert(tree, tree->root, 6, 7, 1);
+    tree->root = clusternode_insert(tree, tree->root, 9, 10, 2);
+    tree->root = clusternode_insert(tree, tree->root, 1, 2, 3);
+    tree->root = clusternode_insert(tree, tree->root, 3, 8, 4);
+    
+    clustereach(tree, tree->root);
+    return 0;
+    
 }
 typedef struct struct_clusternode {
     int start;
     int end;
-	int priority;
+    int priority;
     
     struct struct_interval *interval_head;
     struct struct_interval *interval_tail;
-	int num_ivals;
-	
-	struct struct_clusternode *left;
-	struct struct_clusternode *right;
+    int num_ivals;
+    
+    struct struct_clusternode *left;
+    struct struct_clusternode *right;
 } clusternode;
 
 typedef struct {
-	int max_dist;
+    int max_dist;
     int min_intervals;
-	
-	clusternode *root;
+    
+    clusternode *root;
 } clustertree;
 
 typedef struct struct_treeitr {
-	struct struct_treeitr *next;
-	struct struct_clusternode *node;
+    struct struct_treeitr *next;
+    struct struct_clusternode *node;
 } treeitr;
 
 
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.