Commits

Kanwei Li  committed b8fecbd Merge

Merge. Fixes #9

  • Participants
  • Parent commits 79148d2, ca8cc86

Comments (0)

Files changed (6)

File lib/bx/intervals/cluster.c

-/* Generated by Cython 0.10.3 on Thu Feb 19 18:09:06 2009 */
+/* Generated by Pyrex 0.9.8.5 on Tue Aug 18 15:48:59 2009 */
 
 #define PY_SSIZE_T_CLEAN
 #include "Python.h"
 #ifndef PY_LONG_LONG
   #define PY_LONG_LONG LONG_LONG
 #endif
-#ifndef DL_EXPORT
-  #define DL_EXPORT(t) t
-#endif
-#if PY_VERSION_HEX < 0x02040000
-  #define METH_COEXIST 0
-#endif
 #if PY_VERSION_HEX < 0x02050000
   typedef int Py_ssize_t;
   #define PY_SSIZE_T_MAX INT_MAX
   #define PY_SSIZE_T_MIN INT_MIN
   #define PyInt_FromSsize_t(z) PyInt_FromLong(z)
-  #define PyInt_AsSsize_t(o)   PyInt_AsLong(o)
-  #define PyNumber_Index(o)    PyNumber_Int(o)
-  #define PyIndex_Check(o)     PyNumber_Check(o)
-#endif
-#if PY_VERSION_HEX < 0x02060000
-  #define Py_REFCNT(ob) (((PyObject*)(ob))->ob_refcnt)
-  #define Py_TYPE(ob)   (((PyObject*)(ob))->ob_type)
-  #define Py_SIZE(ob)   (((PyVarObject*)(ob))->ob_size)
-  #define PyVarObject_HEAD_INIT(type, size) \
-          PyObject_HEAD_INIT(type) size,
-  #define PyType_Modified(t)
-
-  typedef struct {
-       void *buf;
-       PyObject *obj;
-       Py_ssize_t len;
-       Py_ssize_t itemsize;
-       int readonly;
-       int ndim;
-       char *format;
-       Py_ssize_t *shape;
-       Py_ssize_t *strides;
-       Py_ssize_t *suboffsets;
-       void *internal;
-  } Py_buffer;
-
-  #define PyBUF_SIMPLE 0
-  #define PyBUF_WRITABLE 0x0001
-  #define PyBUF_LOCK 0x0002
-  #define PyBUF_FORMAT 0x0004
-  #define PyBUF_ND 0x0008
-  #define PyBUF_STRIDES (0x0010 | PyBUF_ND)
-  #define PyBUF_C_CONTIGUOUS (0x0020 | PyBUF_STRIDES)
-  #define PyBUF_F_CONTIGUOUS (0x0040 | PyBUF_STRIDES)
-  #define PyBUF_ANY_CONTIGUOUS (0x0080 | PyBUF_STRIDES)
-  #define PyBUF_INDIRECT (0x0100 | PyBUF_STRIDES)
-
-#endif
-#if PY_MAJOR_VERSION < 3
-  #define __Pyx_BUILTIN_MODULE_NAME "__builtin__"
-#else
-  #define __Pyx_BUILTIN_MODULE_NAME "builtins"
-#endif
-#if PY_MAJOR_VERSION >= 3
-  #define Py_TPFLAGS_CHECKTYPES 0
-  #define Py_TPFLAGS_HAVE_INDEX 0
-#endif
-#if (PY_VERSION_HEX < 0x02060000) || (PY_MAJOR_VERSION >= 3)
-  #define Py_TPFLAGS_HAVE_NEWBUFFER 0
-#endif
-#if PY_MAJOR_VERSION >= 3
-  #define PyBaseString_Type            PyUnicode_Type
-  #define PyString_Type                PyBytes_Type
-  #define PyInt_Type                   PyLong_Type
-  #define PyInt_Check(op)              PyLong_Check(op)
-  #define PyInt_CheckExact(op)         PyLong_CheckExact(op)
-  #define PyInt_FromString             PyLong_FromString
-  #define PyInt_FromUnicode            PyLong_FromUnicode
-  #define PyInt_FromLong               PyLong_FromLong
-  #define PyInt_FromSize_t             PyLong_FromSize_t
-  #define PyInt_FromSsize_t            PyLong_FromSsize_t
-  #define PyInt_AsLong                 PyLong_AsLong
-  #define PyInt_AS_LONG                PyLong_AS_LONG
-  #define PyInt_AsSsize_t              PyLong_AsSsize_t
-  #define PyInt_AsUnsignedLongMask     PyLong_AsUnsignedLongMask
-  #define PyInt_AsUnsignedLongLongMask PyLong_AsUnsignedLongLongMask
-  #define __Pyx_PyNumber_Divide(x,y)         PyNumber_TrueDivide(x,y)
-#else
-  #define __Pyx_PyNumber_Divide(x,y)         PyNumber_Divide(x,y)
-  #define PyBytes_Type                 PyString_Type
-#endif
-#if PY_MAJOR_VERSION >= 3
-  #define PyMethod_New(func, self, klass) PyInstanceMethod_New(func)
+  #define PyInt_AsSsize_t(o)	PyInt_AsLong(o)
 #endif
 #if !defined(WIN32) && !defined(MS_WINDOWS)
   #ifndef __stdcall
   #ifndef __cdecl
     #define __cdecl
   #endif
-#else
-  #define _USE_MATH_DEFINES
 #endif
 #ifdef __cplusplus
 #define __PYX_EXTERN_C extern "C"
 #define __PYX_EXTERN_C extern
 #endif
 #include <math.h>
-#define __PYX_HAVE_API__bx__intervals__cluster
-#include "common.h"
 #include "cluster.h"
 
 
-#ifdef __GNUC__
-#define INLINE __inline__
-#elif _WIN32
-#define INLINE __inline
-#else
-#define INLINE 
-#endif
+typedef struct {PyObject **p; int i; char *s; long n;} __Pyx_StringTabEntry; /*proto*/
 
-typedef struct {PyObject **p; char *s; long n; char is_unicode; char intern; char is_identifier;} __Pyx_StringTabEntry; /*proto*/
-
-
-
-static int __pyx_skip_dispatch = 0;
-
-
-/* Type Conversion Predeclarations */
-
-#if PY_MAJOR_VERSION < 3
-#define __Pyx_PyBytes_FromString PyString_FromString
-#define __Pyx_PyBytes_AsString   PyString_AsString
-#else
-#define __Pyx_PyBytes_FromString PyBytes_FromString
-#define __Pyx_PyBytes_AsString   PyBytes_AsString
-#endif
-
-#define __Pyx_PyBool_FromLong(b) ((b) ? (Py_INCREF(Py_True), Py_True) : (Py_INCREF(Py_False), Py_False))
-static INLINE int __Pyx_PyObject_IsTrue(PyObject* x);
-static INLINE PY_LONG_LONG __pyx_PyInt_AsLongLong(PyObject* x);
-static INLINE unsigned PY_LONG_LONG __pyx_PyInt_AsUnsignedLongLong(PyObject* x);
-static INLINE Py_ssize_t __pyx_PyIndex_AsSsize_t(PyObject* b);
-
-#define __pyx_PyInt_AsLong(x) (PyInt_CheckExact(x) ? PyInt_AS_LONG(x) : PyInt_AsLong(x))
-#define __pyx_PyFloat_AsDouble(x) (PyFloat_CheckExact(x) ? PyFloat_AS_DOUBLE(x) : PyFloat_AsDouble(x))
-
-static INLINE unsigned char __pyx_PyInt_unsigned_char(PyObject* x);
-static INLINE unsigned short __pyx_PyInt_unsigned_short(PyObject* x);
-static INLINE char __pyx_PyInt_char(PyObject* x);
-static INLINE short __pyx_PyInt_short(PyObject* x);
-static INLINE int __pyx_PyInt_int(PyObject* x);
-static INLINE long __pyx_PyInt_long(PyObject* x);
-static INLINE signed char __pyx_PyInt_signed_char(PyObject* x);
-static INLINE signed short __pyx_PyInt_signed_short(PyObject* x);
-static INLINE signed int __pyx_PyInt_signed_int(PyObject* x);
-static INLINE signed long __pyx_PyInt_signed_long(PyObject* x);
-static INLINE long double __pyx_PyInt_long_double(PyObject* x);
-#ifdef __GNUC__
-/* Test for GCC > 2.95 */
-#if __GNUC__ > 2 ||               (__GNUC__ == 2 && (__GNUC_MINOR__ > 95)) 
-#define likely(x)   __builtin_expect(!!(x), 1)
-#define unlikely(x) __builtin_expect(!!(x), 0)
-#else /* __GNUC__ > 2 ... */
-#define likely(x)   (x)
-#define unlikely(x) (x)
-#endif /* __GNUC__ > 2 ... */
-#else /* __GNUC__ */
-#define likely(x)   (x)
-#define unlikely(x) (x)
-#endif /* __GNUC__ */
-    
 static PyObject *__pyx_m;
 static PyObject *__pyx_b;
-static PyObject *__pyx_empty_tuple;
 static int __pyx_lineno;
-static int __pyx_clineno = 0;
-static const char * __pyx_cfilenm= __FILE__;
-static const char *__pyx_filename;
-static const char **__pyx_f;
+static char *__pyx_filename;
+static char **__pyx_f;
 
-static char __pyx_mdoc[] = "\nClusterTree data structure that supports efficient queries for \"cluster\" of\nintervals (groups where no interval is more than some distance from at least\none other).\n\nTODO: Documentation of the algorithmic details.\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_RaiseDoubleKeywordsError(
-    const char* func_name, PyObject* kw_name); /*proto*/
+static void __Pyx_Raise(PyObject *type, PyObject *value, PyObject *tb); /*proto*/
 
-static void __Pyx_RaiseArgtupleInvalid(const char* func_name, int exact,
-    Py_ssize_t num_min, Py_ssize_t num_max, Py_ssize_t num_found); /*proto*/
-
-static int __Pyx_ParseOptionalKeywords(PyObject *kwds, PyObject **argnames[],     PyObject *kwds2, PyObject *values[], Py_ssize_t num_pos_args,     const char* function_name); /*proto*/
-
-static INLINE PyObject* __Pyx_PyObject_Append(PyObject* L, PyObject* x) {
-    if (likely(PyList_CheckExact(L))) {
-        if (PyList_Append(L, x) < 0) return NULL;
-        Py_INCREF(Py_None);
-        return Py_None; // this is just to have an accurate signature
-    }
-    else {
-        return PyObject_CallMethod(L, "append", "(O)", x);
-    }
-}
-
-static void __Pyx_AddTraceback(const char *funcname); /*proto*/
+static PyObject *__Pyx_GetName(PyObject *dict, PyObject *name); /*proto*/
 
 static int __Pyx_InitStrings(__Pyx_StringTabEntry *t); /*proto*/
 
-/* Type declarations */
+static void __Pyx_AddTraceback(char *funcname); /*proto*/
 
-/* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":47
- *     int has_next(treeitr **itr)
- * 
- * cdef class ClusterTree:             # <<<<<<<<<<<<<<
- *     cdef ClusterNode * root
- *     cdef int mincols
- */
+/* Declarations from bx.intervals.cluster */
+
+
+/* Declarations from implementation of bx.intervals.cluster */
 
 struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree {
   PyObject_HEAD
-  struct ClusterNode *root;
+  clustertree *tree;
   int mincols;
   int minregions;
 };
-/* Module declarations from bx.intervals.cluster */
+
 
 static PyTypeObject *__pyx_ptype_2bx_9intervals_7cluster_ClusterTree = 0;
 
+static char __pyx_k1[] = "Interval start must be before end";
+static char __pyx_k2[] = "append";
+static char __pyx_k3[] = "sorted";
+static char __pyx_k4[] = "extend";
+
+static PyObject *__pyx_n_append;
+static PyObject *__pyx_n_extend;
+static PyObject *__pyx_n_sorted;
+
+static PyObject *__pyx_k1p;
+
+static __Pyx_StringTabEntry __pyx_string_tab[] = {
+  {&__pyx_n_append, 1, __pyx_k2, sizeof(__pyx_k2)},
+  {&__pyx_n_extend, 1, __pyx_k4, sizeof(__pyx_k4)},
+  {&__pyx_n_sorted, 1, __pyx_k3, sizeof(__pyx_k3)},
+  {&__pyx_k1p, 0, __pyx_k1, sizeof(__pyx_k1)},
+  {0, 0, 0, 0}
+};
+
+
 
 /* Implementation of bx.intervals.cluster */
-static char __pyx_k___cinit__[] = "__cinit__";
-static PyObject *__pyx_kp___cinit__;
-static char __pyx_k___dealloc__[] = "__dealloc__";
-static PyObject *__pyx_kp___dealloc__;
-static char __pyx_k_insert[] = "insert";
-static PyObject *__pyx_kp_insert;
-static char __pyx_k_getregions[] = "getregions";
-static PyObject *__pyx_kp_getregions;
-static char __pyx_k_getlines[] = "getlines";
-static PyObject *__pyx_kp_getlines;
-static char __pyx_k_mincols[] = "mincols";
-static PyObject *__pyx_kp_mincols;
-static char __pyx_k_minregions[] = "minregions";
-static PyObject *__pyx_kp_minregions;
-static char __pyx_k_start[] = "start";
-static PyObject *__pyx_kp_start;
-static char __pyx_k_end[] = "end";
-static PyObject *__pyx_kp_end;
-static char __pyx_k_linenum[] = "linenum";
-static PyObject *__pyx_kp_linenum;
-static char __pyx_k_append[] = "append";
-static PyObject *__pyx_kp_append;
 
-/* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":52
- *     cdef int minregions
- * 
- *     def __new__( self, mincols, minregions ):             # <<<<<<<<<<<<<<
- *         self.root = NULL
- *         self.mincols = mincols
- */
-
-static int __pyx_pf_2bx_9intervals_7cluster_11ClusterTree___new__(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
-static int __pyx_pf_2bx_9intervals_7cluster_11ClusterTree___new__(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
+static int __pyx_f_2bx_9intervals_7cluster_11ClusterTree___cinit__(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
+static int __pyx_f_2bx_9intervals_7cluster_11ClusterTree___cinit__(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
   PyObject *__pyx_v_mincols = 0;
   PyObject *__pyx_v_minregions = 0;
   int __pyx_r;
   int __pyx_1;
-  static PyObject **__pyx_pyargnames[] = {&__pyx_kp_mincols,&__pyx_kp_minregions,0};
-  if (unlikely(__pyx_kwds)) {
-    PyObject* values[2] = {0,0};
-    Py_ssize_t kw_args = PyDict_Size(__pyx_kwds);
-    switch (PyTuple_GET_SIZE(__pyx_args)) {
-      case  2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
-      case  1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
-      case  0: break;
-      default: goto __pyx_L5_argtuple_error;
-    }
-    switch (PyTuple_GET_SIZE(__pyx_args)) {
-      case  0:
-      values[0] = PyDict_GetItem(__pyx_kwds, __pyx_kp_mincols);
-      if (likely(values[0])) kw_args--;
-      else goto __pyx_L5_argtuple_error;
-      case  1:
-      values[1] = PyDict_GetItem(__pyx_kwds, __pyx_kp_minregions);
-      if (likely(values[1])) kw_args--;
-      else {
-        __Pyx_RaiseArgtupleInvalid("__new__", 1, 2, 2, 1); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 52; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
-      }
-    }
-    if (unlikely(kw_args > 0)) {
-      if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, PyTuple_GET_SIZE(__pyx_args), "__new__") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 52; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
-    }
-    __pyx_v_mincols = values[0];
-    __pyx_v_minregions = values[1];
-  } else if (PyTuple_GET_SIZE(__pyx_args) != 2) {
-    goto __pyx_L5_argtuple_error;
-  } else {
-    __pyx_v_mincols = PyTuple_GET_ITEM(__pyx_args, 0);
-    __pyx_v_minregions = PyTuple_GET_ITEM(__pyx_args, 1);
-  }
-  goto __pyx_L4_argument_unpacking_done;
-  __pyx_L5_argtuple_error:;
-  __Pyx_RaiseArgtupleInvalid("__new__", 1, 2, 2, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 52; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
-  __pyx_L3_error:;
-  __Pyx_AddTraceback("bx.intervals.cluster.ClusterTree.__cinit__");
-  return -1;
-  __pyx_L4_argument_unpacking_done:;
+  int __pyx_2;
+  static char *__pyx_argnames[] = {"mincols","minregions",0};
+  if (!PyArg_ParseTupleAndKeywords(__pyx_args, __pyx_kwds, "OO", __pyx_argnames, &__pyx_v_mincols, &__pyx_v_minregions)) return -1;
+  Py_INCREF(__pyx_v_self);
+  Py_INCREF(__pyx_v_mincols);
+  Py_INCREF(__pyx_v_minregions);
 
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":53
- * 
- *     def __new__( self, mincols, minregions ):
- *         self.root = NULL             # <<<<<<<<<<<<<<
- *         self.mincols = mincols
- *         self.minregions = minregions
- */
-  ((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->root = NULL;
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":62 */
+  __pyx_1 = PyInt_AsLong(__pyx_v_mincols); if (PyErr_Occurred()) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; goto __pyx_L1;}
+  __pyx_2 = PyInt_AsLong(__pyx_v_minregions); if (PyErr_Occurred()) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; goto __pyx_L1;}
+  ((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->tree = create_clustertree(__pyx_1,__pyx_2);
 
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":54
- *     def __new__( self, mincols, minregions ):
- *         self.root = NULL
- *         self.mincols = mincols             # <<<<<<<<<<<<<<
- *         self.minregions = minregions
- * 
- */
-  __pyx_1 = __pyx_PyInt_int(__pyx_v_mincols); if (unlikely((__pyx_1 == (int)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 54; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":63 */
+  __pyx_1 = PyInt_AsLong(__pyx_v_mincols); if (PyErr_Occurred()) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 63; goto __pyx_L1;}
   ((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->mincols = __pyx_1;
 
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":55
- *         self.root = NULL
- *         self.mincols = mincols
- *         self.minregions = minregions             # <<<<<<<<<<<<<<
- * 
- *     def __dealloc__( self ):
- */
-  __pyx_1 = __pyx_PyInt_int(__pyx_v_minregions); if (unlikely((__pyx_1 == (int)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 55; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-  ((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->minregions = __pyx_1;
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":64 */
+  __pyx_2 = PyInt_AsLong(__pyx_v_minregions); if (PyErr_Occurred()) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 64; goto __pyx_L1;}
+  ((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->minregions = __pyx_2;
 
   __pyx_r = 0;
   goto __pyx_L0;
-  __pyx_L1_error:;
+  __pyx_L1:;
   __Pyx_AddTraceback("bx.intervals.cluster.ClusterTree.__cinit__");
   __pyx_r = -1;
   __pyx_L0:;
+  Py_DECREF(__pyx_v_self);
+  Py_DECREF(__pyx_v_mincols);
+  Py_DECREF(__pyx_v_minregions);
   return __pyx_r;
 }
 
-/* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":57
- *         self.minregions = minregions
- * 
- *     def __dealloc__( self ):             # <<<<<<<<<<<<<<
- *         freetree( &self.root )
- * 
- */
+static void __pyx_f_2bx_9intervals_7cluster_11ClusterTree___dealloc__(PyObject *__pyx_v_self); /*proto*/
+static void __pyx_f_2bx_9intervals_7cluster_11ClusterTree___dealloc__(PyObject *__pyx_v_self) {
+  Py_INCREF(__pyx_v_self);
+  free_tree(((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->tree);
 
-static void __pyx_pf_2bx_9intervals_7cluster_11ClusterTree___dealloc__(PyObject *__pyx_v_self); /*proto*/
-static void __pyx_pf_2bx_9intervals_7cluster_11ClusterTree___dealloc__(PyObject *__pyx_v_self) {
-
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":58
- * 
- *     def __dealloc__( self ):
- *         freetree( &self.root )             # <<<<<<<<<<<<<<
- * 
- *     def insert( self, int start, int end, int linenum):
- */
-  freetree((&((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->root));
-
+  Py_DECREF(__pyx_v_self);
 }
 
-/* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":60
- *         freetree( &self.root )
- * 
- *     def insert( self, int start, int end, int linenum):             # <<<<<<<<<<<<<<
- *         clusterNodeInsert( &self.root, start, end, linenum, self.mincols )
- *         return self
- */
+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;
+  PyObject *__pyx_v_id = 0;
+  PyObject *__pyx_r;
+  int __pyx_1;
+  PyObject *__pyx_2 = 0;
+  PyObject *__pyx_3 = 0;
+  int __pyx_4;
+  int __pyx_5;
+  static char *__pyx_argnames[] = {"s","e","id",0};
+  if (!PyArg_ParseTupleAndKeywords(__pyx_args, __pyx_kwds, "OOO", __pyx_argnames, &__pyx_v_s, &__pyx_v_e, &__pyx_v_id)) return 0;
+  Py_INCREF(__pyx_v_self);
+  Py_INCREF(__pyx_v_s);
+  Py_INCREF(__pyx_v_e);
+  Py_INCREF(__pyx_v_id);
 
-static PyObject *__pyx_pf_2bx_9intervals_7cluster_11ClusterTree_insert(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
-static PyObject *__pyx_pf_2bx_9intervals_7cluster_11ClusterTree_insert(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
-  int __pyx_v_start;
-  int __pyx_v_end;
-  int __pyx_v_linenum;
-  PyObject *__pyx_r;
-  static PyObject **__pyx_pyargnames[] = {&__pyx_kp_start,&__pyx_kp_end,&__pyx_kp_linenum,0};
-  if (unlikely(__pyx_kwds)) {
-    PyObject* values[3] = {0,0,0};
-    Py_ssize_t kw_args = PyDict_Size(__pyx_kwds);
-    switch (PyTuple_GET_SIZE(__pyx_args)) {
-      case  3: values[2] = PyTuple_GET_ITEM(__pyx_args, 2);
-      case  2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
-      case  1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
-      case  0: break;
-      default: goto __pyx_L5_argtuple_error;
-    }
-    switch (PyTuple_GET_SIZE(__pyx_args)) {
-      case  0:
-      values[0] = PyDict_GetItem(__pyx_kwds, __pyx_kp_start);
-      if (likely(values[0])) kw_args--;
-      else goto __pyx_L5_argtuple_error;
-      case  1:
-      values[1] = PyDict_GetItem(__pyx_kwds, __pyx_kp_end);
-      if (likely(values[1])) kw_args--;
-      else {
-        __Pyx_RaiseArgtupleInvalid("insert", 1, 3, 3, 1); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
-      }
-      case  2:
-      values[2] = PyDict_GetItem(__pyx_kwds, __pyx_kp_linenum);
-      if (likely(values[2])) kw_args--;
-      else {
-        __Pyx_RaiseArgtupleInvalid("insert", 1, 3, 3, 2); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
-      }
-    }
-    if (unlikely(kw_args > 0)) {
-      if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, PyTuple_GET_SIZE(__pyx_args), "insert") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
-    }
-    __pyx_v_start = __pyx_PyInt_int(values[0]); if (unlikely((__pyx_v_start == (int)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
-    __pyx_v_end = __pyx_PyInt_int(values[1]); if (unlikely((__pyx_v_end == (int)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
-    __pyx_v_linenum = __pyx_PyInt_int(values[2]); if (unlikely((__pyx_v_linenum == (int)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
-  } else if (PyTuple_GET_SIZE(__pyx_args) != 3) {
-    goto __pyx_L5_argtuple_error;
-  } else {
-    __pyx_v_start = __pyx_PyInt_int(PyTuple_GET_ITEM(__pyx_args, 0)); if (unlikely((__pyx_v_start == (int)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
-    __pyx_v_end = __pyx_PyInt_int(PyTuple_GET_ITEM(__pyx_args, 1)); if (unlikely((__pyx_v_end == (int)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
-    __pyx_v_linenum = __pyx_PyInt_int(PyTuple_GET_ITEM(__pyx_args, 2)); if (unlikely((__pyx_v_linenum == (int)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
+  /* "/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 = 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 = 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 = 71; goto __pyx_L1;}
+    goto __pyx_L2;
   }
-  goto __pyx_L4_argument_unpacking_done;
-  __pyx_L5_argtuple_error:;
-  __Pyx_RaiseArgtupleInvalid("insert", 1, 3, 3, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
-  __pyx_L3_error:;
-  __Pyx_AddTraceback("bx.intervals.cluster.ClusterTree.insert");
-  return NULL;
-  __pyx_L4_argument_unpacking_done:;
+  __pyx_L2:;
 
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":61
- * 
- *     def insert( self, int start, int end, int linenum):
- *         clusterNodeInsert( &self.root, start, end, linenum, self.mincols )             # <<<<<<<<<<<<<<
- *         return self
- * 
- */
-  clusterNodeInsert((&((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->root), __pyx_v_start, __pyx_v_end, __pyx_v_linenum, ((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->mincols);
-
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":62
- *     def insert( self, int start, int end, int linenum):
- *         clusterNodeInsert( &self.root, start, end, linenum, self.mincols )
- *         return self             # <<<<<<<<<<<<<<
- * 
- *     def getregions( self ):
- */
-  Py_INCREF(__pyx_v_self);
-  __pyx_r = __pyx_v_self;
-  goto __pyx_L0;
+  /* "/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);
+  goto __pyx_L0;
+  __pyx_L1:;
+  Py_XDECREF(__pyx_2);
+  Py_XDECREF(__pyx_3);
+  __Pyx_AddTraceback("bx.intervals.cluster.ClusterTree.insert");
+  __pyx_r = 0;
   __pyx_L0:;
+  Py_DECREF(__pyx_v_self);
+  Py_DECREF(__pyx_v_s);
+  Py_DECREF(__pyx_v_e);
+  Py_DECREF(__pyx_v_id);
   return __pyx_r;
 }
 
-/* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":64
- *         return self
- * 
- *     def getregions( self ):             # <<<<<<<<<<<<<<
- *         cdef treeitr * myitr
- *         cdef ClusterNode * node
- */
-
-static PyObject *__pyx_pf_2bx_9intervals_7cluster_11ClusterTree_getregions(PyObject *__pyx_v_self, PyObject *unused); /*proto*/
-static PyObject *__pyx_pf_2bx_9intervals_7cluster_11ClusterTree_getregions(PyObject *__pyx_v_self, PyObject *unused) {
-  struct treeitr *__pyx_v_myitr;
-  struct ClusterNode *__pyx_v_node;
-  struct linelist *__pyx_v_nums;
-  struct listitem *__pyx_v_num;
+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;
   PyObject *__pyx_v_regions;
-  PyObject *__pyx_v_lines;
+  PyObject *__pyx_v_ids;
   PyObject *__pyx_r;
   PyObject *__pyx_1 = 0;
   int __pyx_2;
-  int __pyx_3;
+  PyObject *__pyx_3 = 0;
   PyObject *__pyx_4 = 0;
   PyObject *__pyx_5 = 0;
+  PyObject *__pyx_6 = 0;
+  PyObject *__pyx_7 = 0;
+  static char *__pyx_argnames[] = {0};
+  if (!PyArg_ParseTupleAndKeywords(__pyx_args, __pyx_kwds, "", __pyx_argnames)) return 0;
+  Py_INCREF(__pyx_v_self);
   __pyx_v_regions = Py_None; Py_INCREF(Py_None);
-  __pyx_v_lines = Py_None; Py_INCREF(Py_None);
+  __pyx_v_ids = Py_None; Py_INCREF(Py_None);
 
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":70
- *         cdef listitem* num
- * 
- *         myitr = NULL             # <<<<<<<<<<<<<<
- *         get_itr_in(self.root, &myitr)
- *         regions = []
- */
-  __pyx_v_myitr = NULL;
-
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":71
- * 
- *         myitr = NULL
- *         get_itr_in(self.root, &myitr)             # <<<<<<<<<<<<<<
- *         regions = []
- *         while (has_next(&myitr)):
- */
-  get_itr_in(((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->root, (&__pyx_v_myitr));
-
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":72
- *         myitr = NULL
- *         get_itr_in(self.root, &myitr)
- *         regions = []             # <<<<<<<<<<<<<<
- *         while (has_next(&myitr)):
- *             node = next(&myitr)
- */
-  __pyx_1 = PyList_New(0); if (unlikely(!__pyx_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 72; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
+  /* "/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 = ((PyObject *)__pyx_1);
+  __pyx_v_regions = __pyx_1;
   __pyx_1 = 0;
 
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":73
- *         get_itr_in(self.root, &myitr)
- *         regions = []
- *         while (has_next(&myitr)):             # <<<<<<<<<<<<<<
- *             node = next(&myitr)
- *             if node.regions >= self.minregions:
- */
+  /* "/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":88 */
   while (1) {
-    __pyx_2 = has_next((&__pyx_v_myitr));
+    __pyx_2 = (__pyx_v_itr != 0);
     if (!__pyx_2) break;
 
-    /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":74
- *         regions = []
- *         while (has_next(&myitr)):
- *             node = next(&myitr)             # <<<<<<<<<<<<<<
- *             if node.regions >= self.minregions:
- *                 lines = []
- */
-    __pyx_v_node = next((&__pyx_v_myitr));
+    /* "/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/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":75
- *         while (has_next(&myitr)):
- *             node = next(&myitr)
- *             if node.regions >= self.minregions:             # <<<<<<<<<<<<<<
- *                 lines = []
- *                 if node.linenums and node.linenums.head:
- */
-    __pyx_3 = (__pyx_v_node->regions >= ((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->minregions);
-    if (__pyx_3) {
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":90 */
+    __pyx_v_ival = __pyx_v_itr->node->interval_head;
 
-      /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":76
- *             node = next(&myitr)
- *             if node.regions >= self.minregions:
- *                 lines = []             # <<<<<<<<<<<<<<
- *                 if node.linenums and node.linenums.head:
- *                     nums = node.linenums
- */
-      __pyx_1 = PyList_New(0); if (unlikely(!__pyx_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 76; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-      Py_DECREF(__pyx_v_lines);
-      __pyx_v_lines = ((PyObject *)__pyx_1);
-      __pyx_1 = 0;
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":91 */
+    while (1) {
+      __pyx_2 = (__pyx_v_ival != 0);
+      if (!__pyx_2) break;
 
-      /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":77
- *             if node.regions >= self.minregions:
- *                 lines = []
- *                 if node.linenums and node.linenums.head:             # <<<<<<<<<<<<<<
- *                     nums = node.linenums
- *                     num = nums.head
- */
-      __pyx_3 = (__pyx_v_node->linenums != 0);
-      if (__pyx_3) {
-        __pyx_3 = (__pyx_v_node->linenums->head != 0);
-      }
-      if (__pyx_3) {
+      /* "/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 = 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/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":78
- *                 lines = []
- *                 if node.linenums and node.linenums.head:
- *                     nums = node.linenums             # <<<<<<<<<<<<<<
- *                     num = nums.head
- *                     while num:
- */
-        __pyx_v_nums = __pyx_v_node->linenums;
+      /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":93 */
+      __pyx_v_ival = __pyx_v_ival->next;
+    }
 
-        /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":79
- *                 if node.linenums and node.linenums.head:
- *                     nums = node.linenums
- *                     num = nums.head             # <<<<<<<<<<<<<<
- *                     while num:
- *                         lines.append( num.value )
- */
-        __pyx_v_num = __pyx_v_nums->head;
+    /* "/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 = 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 = 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 = 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 = 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/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":80
- *                     nums = node.linenums
- *                     num = nums.head
- *                     while num:             # <<<<<<<<<<<<<<
- *                         lines.append( num.value )
- *                         num = num.next
- */
-        while (1) {
-          __pyx_3 = (__pyx_v_num != 0);
-          if (!__pyx_3) break;
-
-          /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":81
- *                     num = nums.head
- *                     while num:
- *                         lines.append( num.value )             # <<<<<<<<<<<<<<
- *                         num = num.next
- *                 regions.append( ( node.start, node.end, lines ) )
- */
-          __pyx_1 = PyInt_FromLong(__pyx_v_num->value); if (unlikely(!__pyx_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 81; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-          __pyx_4 = __Pyx_PyObject_Append(__pyx_v_lines, __pyx_1); if (unlikely(!__pyx_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 81; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-          Py_DECREF(__pyx_1); __pyx_1 = 0;
-          Py_DECREF(__pyx_4); __pyx_4 = 0;
-
-          /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":82
- *                     while num:
- *                         lines.append( num.value )
- *                         num = num.next             # <<<<<<<<<<<<<<
- *                 regions.append( ( node.start, node.end, lines ) )
- * 
- */
-          __pyx_v_num = __pyx_v_num->next;
-        }
-        goto __pyx_L8;
-      }
-      __pyx_L8:;
-
-      /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":83
- *                         lines.append( num.value )
- *                         num = num.next
- *                 regions.append( ( node.start, node.end, lines ) )             # <<<<<<<<<<<<<<
- * 
- *         return regions
- */
-      __pyx_1 = PyInt_FromLong(__pyx_v_node->start); if (unlikely(!__pyx_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 83; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-      __pyx_4 = PyInt_FromLong(__pyx_v_node->end); if (unlikely(!__pyx_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 83; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-      __pyx_5 = PyTuple_New(3); if (unlikely(!__pyx_5)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 83; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-      PyTuple_SET_ITEM(__pyx_5, 0, __pyx_1);
-      PyTuple_SET_ITEM(__pyx_5, 1, __pyx_4);
-      Py_INCREF(__pyx_v_lines);
-      PyTuple_SET_ITEM(__pyx_5, 2, __pyx_v_lines);
-      __pyx_1 = 0;
-      __pyx_4 = 0;
-      __pyx_1 = __Pyx_PyObject_Append(__pyx_v_regions, ((PyObject *)__pyx_5)); if (unlikely(!__pyx_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 83; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-      Py_DECREF(((PyObject *)__pyx_5)); __pyx_5 = 0;
-      Py_DECREF(__pyx_1); __pyx_1 = 0;
-      goto __pyx_L7;
-    }
-    __pyx_L7:;
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":96 */
+    __pyx_v_itr = __pyx_v_itr->next;
   }
 
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":85
- *                 regions.append( ( node.start, node.end, lines ) )
- * 
- *         return regions             # <<<<<<<<<<<<<<
- * 
- *     def getlines( self ):
- */
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":97 */
   Py_INCREF(__pyx_v_regions);
   __pyx_r = __pyx_v_regions;
   goto __pyx_L0;
 
   __pyx_r = Py_None; Py_INCREF(Py_None);
   goto __pyx_L0;
-  __pyx_L1_error:;
+  __pyx_L1:;
   Py_XDECREF(__pyx_1);
+  Py_XDECREF(__pyx_3);
   Py_XDECREF(__pyx_4);
   Py_XDECREF(__pyx_5);
+  Py_XDECREF(__pyx_6);
+  Py_XDECREF(__pyx_7);
   __Pyx_AddTraceback("bx.intervals.cluster.ClusterTree.getregions");
-  __pyx_r = NULL;
+  __pyx_r = 0;
   __pyx_L0:;
   Py_DECREF(__pyx_v_regions);
-  Py_DECREF(__pyx_v_lines);
+  Py_DECREF(__pyx_v_ids);
+  Py_DECREF(__pyx_v_self);
   return __pyx_r;
 }
 
-/* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":87
- *         return regions
- * 
- *     def getlines( self ):             # <<<<<<<<<<<<<<
- *         cdef treeitr * myitr
- *         cdef ClusterNode * node
- */
-
-static PyObject *__pyx_pf_2bx_9intervals_7cluster_11ClusterTree_getlines(PyObject *__pyx_v_self, PyObject *unused); /*proto*/
-static PyObject *__pyx_pf_2bx_9intervals_7cluster_11ClusterTree_getlines(PyObject *__pyx_v_self, PyObject *unused) {
-  struct treeitr *__pyx_v_myitr;
-  struct ClusterNode *__pyx_v_node;
-  struct linelist *__pyx_v_nums;
-  struct listitem *__pyx_v_num;
+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;
   PyObject *__pyx_v_lines;
+  PyObject *__pyx_v_ids;
   PyObject *__pyx_r;
   PyObject *__pyx_1 = 0;
   int __pyx_2;
-  int __pyx_3;
+  PyObject *__pyx_3 = 0;
   PyObject *__pyx_4 = 0;
+  PyObject *__pyx_5 = 0;
+  static char *__pyx_argnames[] = {0};
+  if (!PyArg_ParseTupleAndKeywords(__pyx_args, __pyx_kwds, "", __pyx_argnames)) return 0;
+  Py_INCREF(__pyx_v_self);
   __pyx_v_lines = Py_None; Py_INCREF(Py_None);
+  __pyx_v_ids = Py_None; Py_INCREF(Py_None);
 
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":93
- *         cdef listitem* num
- * 
- *         myitr = NULL             # <<<<<<<<<<<<<<
- *         get_itr_in(self.root, &myitr)
- *         lines = []
- */
-  __pyx_v_myitr = NULL;
-
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":94
- * 
- *         myitr = NULL
- *         get_itr_in(self.root, &myitr)             # <<<<<<<<<<<<<<
- *         lines = []
- *         while (has_next(&myitr)):
- */
-  get_itr_in(((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->root, (&__pyx_v_myitr));
-
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":95
- *         myitr = NULL
- *         get_itr_in(self.root, &myitr)
- *         lines = []             # <<<<<<<<<<<<<<
- *         while (has_next(&myitr)):
- *             node = next(&myitr)
- */
-  __pyx_1 = PyList_New(0); if (unlikely(!__pyx_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 95; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
+  /* "/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 = ((PyObject *)__pyx_1);
+  __pyx_v_lines = __pyx_1;
   __pyx_1 = 0;
 
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":96
- *         get_itr_in(self.root, &myitr)
- *         lines = []
- *         while (has_next(&myitr)):             # <<<<<<<<<<<<<<
- *             node = next(&myitr)
- *             if node.regions >= self.minregions:
- */
+  /* "/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":109 */
   while (1) {
-    __pyx_2 = has_next((&__pyx_v_myitr));
+    __pyx_2 = (__pyx_v_itr != 0);
     if (!__pyx_2) break;
 
-    /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":97
- *         lines = []
- *         while (has_next(&myitr)):
- *             node = next(&myitr)             # <<<<<<<<<<<<<<
- *             if node.regions >= self.minregions:
- *                 if node.linenums and node.linenums.head:
- */
-    __pyx_v_node = next((&__pyx_v_myitr));
+    /* "/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/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":98
- *         while (has_next(&myitr)):
- *             node = next(&myitr)
- *             if node.regions >= self.minregions:             # <<<<<<<<<<<<<<
- *                 if node.linenums and node.linenums.head:
- *                     nums = node.linenums
- */
-    __pyx_3 = (__pyx_v_node->regions >= ((struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree *)__pyx_v_self)->minregions);
-    if (__pyx_3) {
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":111 */
+    __pyx_v_ival = __pyx_v_itr->node->interval_head;
 
-      /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":99
- *             node = next(&myitr)
- *             if node.regions >= self.minregions:
- *                 if node.linenums and node.linenums.head:             # <<<<<<<<<<<<<<
- *                     nums = node.linenums
- *                     num = nums.head
- */
-      __pyx_3 = (__pyx_v_node->linenums != 0);
-      if (__pyx_3) {
-        __pyx_3 = (__pyx_v_node->linenums->head != 0);
-      }
-      if (__pyx_3) {
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":112 */
+    while (1) {
+      __pyx_2 = (__pyx_v_ival != 0);
+      if (!__pyx_2) break;
 
-        /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":100
- *             if node.regions >= self.minregions:
- *                 if node.linenums and node.linenums.head:
- *                     nums = node.linenums             # <<<<<<<<<<<<<<
- *                     num = nums.head
- *                     while num:
- */
-        __pyx_v_nums = __pyx_v_node->linenums;
+      /* "/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 = 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/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":101
- *                 if node.linenums and node.linenums.head:
- *                     nums = node.linenums
- *                     num = nums.head             # <<<<<<<<<<<<<<
- *                     while num:
- *                         lines.append( num.value )
- */
-        __pyx_v_num = __pyx_v_nums->head;
+      /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":114 */
+      __pyx_v_ival = __pyx_v_ival->next;
+    }
 
-        /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":102
- *                     nums = node.linenums
- *                     num = nums.head
- *                     while num:             # <<<<<<<<<<<<<<
- *                         lines.append( num.value )
- *                         num = num.next
- */
-        while (1) {
-          __pyx_3 = (__pyx_v_num != 0);
-          if (!__pyx_3) break;
+    /* "/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 = 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 = 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 = 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/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":103
- *                     num = nums.head
- *                     while num:
- *                         lines.append( num.value )             # <<<<<<<<<<<<<<
- *                         num = num.next
- *         return lines
- */
-          __pyx_1 = PyInt_FromLong(__pyx_v_num->value); if (unlikely(!__pyx_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 103; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-          __pyx_4 = __Pyx_PyObject_Append(__pyx_v_lines, __pyx_1); if (unlikely(!__pyx_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 103; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-          Py_DECREF(__pyx_1); __pyx_1 = 0;
-          Py_DECREF(__pyx_4); __pyx_4 = 0;
-
-          /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":104
- *                     while num:
- *                         lines.append( num.value )
- *                         num = num.next             # <<<<<<<<<<<<<<
- *         return lines
- */
-          __pyx_v_num = __pyx_v_num->next;
-        }
-        goto __pyx_L8;
-      }
-      __pyx_L8:;
-      goto __pyx_L7;
-    }
-    __pyx_L7:;
+    /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":117 */
+    __pyx_v_itr = __pyx_v_itr->next;
   }
 
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":105
- *                         lines.append( num.value )
- *                         num = num.next
- *         return lines             # <<<<<<<<<<<<<<
- */
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":118 */
   Py_INCREF(__pyx_v_lines);
   __pyx_r = __pyx_v_lines;
   goto __pyx_L0;
 
   __pyx_r = Py_None; Py_INCREF(Py_None);
   goto __pyx_L0;
-  __pyx_L1_error:;
+  __pyx_L1:;
   Py_XDECREF(__pyx_1);
+  Py_XDECREF(__pyx_3);
   Py_XDECREF(__pyx_4);
+  Py_XDECREF(__pyx_5);
   __Pyx_AddTraceback("bx.intervals.cluster.ClusterTree.getlines");
-  __pyx_r = NULL;
+  __pyx_r = 0;
   __pyx_L0:;
   Py_DECREF(__pyx_v_lines);
+  Py_DECREF(__pyx_v_ids);
+  Py_DECREF(__pyx_v_self);
   return __pyx_r;
 }
 
 static PyObject *__pyx_tp_new_2bx_9intervals_7cluster_ClusterTree(PyTypeObject *t, PyObject *a, PyObject *k) {
   PyObject *o = (*t->tp_alloc)(t, 0);
   if (!o) return 0;
-  if (__pyx_pf_2bx_9intervals_7cluster_11ClusterTree___new__(o, a, k) < 0) {
+  if (__pyx_f_2bx_9intervals_7cluster_11ClusterTree___cinit__(o, a, k) < 0) {
     Py_DECREF(o); o = 0;
   }
   return o;
   {
     PyObject *etype, *eval, *etb;
     PyErr_Fetch(&etype, &eval, &etb);
-    ++Py_REFCNT(o);
-    __pyx_pf_2bx_9intervals_7cluster_11ClusterTree___dealloc__(o);
+    ++o->ob_refcnt;
+    __pyx_f_2bx_9intervals_7cluster_11ClusterTree___dealloc__(o);
     if (PyErr_Occurred()) PyErr_WriteUnraisable(o);
-    --Py_REFCNT(o);
+    --o->ob_refcnt;
     PyErr_Restore(etype, eval, etb);
   }
-  (*Py_TYPE(o)->tp_free)(o);
+  (*o->ob_type->tp_free)(o);
 }
 
 static struct PyMethodDef __pyx_methods_2bx_9intervals_7cluster_ClusterTree[] = {
-  {"insert", (PyCFunction)__pyx_pf_2bx_9intervals_7cluster_11ClusterTree_insert, METH_VARARGS|METH_KEYWORDS, 0},
-  {"getregions", (PyCFunction)__pyx_pf_2bx_9intervals_7cluster_11ClusterTree_getregions, METH_NOARGS, 0},
-  {"getlines", (PyCFunction)__pyx_pf_2bx_9intervals_7cluster_11ClusterTree_getlines, METH_NOARGS, 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}
 };
 
   0, /*nb_add*/
   0, /*nb_subtract*/
   0, /*nb_multiply*/
-  #if PY_MAJOR_VERSION < 3
   0, /*nb_divide*/
-  #endif
   0, /*nb_remainder*/
   0, /*nb_divmod*/
   0, /*nb_power*/
   0, /*nb_and*/
   0, /*nb_xor*/
   0, /*nb_or*/
-  #if PY_MAJOR_VERSION < 3
   0, /*nb_coerce*/
-  #endif
   0, /*nb_int*/
   0, /*nb_long*/
   0, /*nb_float*/
-  #if PY_MAJOR_VERSION < 3
   0, /*nb_oct*/
-  #endif
-  #if PY_MAJOR_VERSION < 3
   0, /*nb_hex*/
-  #endif
   0, /*nb_inplace_add*/
   0, /*nb_inplace_subtract*/
   0, /*nb_inplace_multiply*/
-  #if PY_MAJOR_VERSION < 3
   0, /*nb_inplace_divide*/
-  #endif
   0, /*nb_inplace_remainder*/
   0, /*nb_inplace_power*/
   0, /*nb_inplace_lshift*/
   0, /*nb_true_divide*/
   0, /*nb_inplace_floor_divide*/
   0, /*nb_inplace_true_divide*/
-  #if (PY_MAJOR_VERSION >= 3) || (Py_TPFLAGS_DEFAULT & Py_TPFLAGS_HAVE_INDEX)
+  #if Py_TPFLAGS_DEFAULT & Py_TPFLAGS_HAVE_INDEX
   0, /*nb_index*/
   #endif
 };
 };
 
 static PyBufferProcs __pyx_tp_as_buffer_ClusterTree = {
-  #if PY_MAJOR_VERSION < 3
   0, /*bf_getreadbuffer*/
-  #endif
-  #if PY_MAJOR_VERSION < 3
   0, /*bf_getwritebuffer*/
-  #endif
-  #if PY_MAJOR_VERSION < 3
   0, /*bf_getsegcount*/
-  #endif
-  #if PY_MAJOR_VERSION < 3
   0, /*bf_getcharbuffer*/
-  #endif
-  #if PY_VERSION_HEX >= 0x02060000
-  0, /*bf_getbuffer*/
-  #endif
-  #if PY_VERSION_HEX >= 0x02060000
-  0, /*bf_releasebuffer*/
-  #endif
 };
 
 PyTypeObject __pyx_type_2bx_9intervals_7cluster_ClusterTree = {
-  PyVarObject_HEAD_INIT(0, 0)
+  PyObject_HEAD_INIT(0)
+  0, /*ob_size*/
   "bx.intervals.cluster.ClusterTree", /*tp_name*/
   sizeof(struct __pyx_obj_2bx_9intervals_7cluster_ClusterTree), /*tp_basicsize*/
   0, /*tp_itemsize*/
   0, /*tp_getattro*/
   0, /*tp_setattro*/
   &__pyx_tp_as_buffer_ClusterTree, /*tp_as_buffer*/
-  Py_TPFLAGS_DEFAULT|Py_TPFLAGS_CHECKTYPES|Py_TPFLAGS_BASETYPE|Py_TPFLAGS_HAVE_NEWBUFFER, /*tp_flags*/
+  Py_TPFLAGS_DEFAULT|Py_TPFLAGS_CHECKTYPES|Py_TPFLAGS_BASETYPE, /*tp_flags*/
   0, /*tp_doc*/
   0, /*tp_traverse*/
   0, /*tp_clear*/
 
 static void __pyx_init_filenames(void); /*proto*/
 
-#if PY_MAJOR_VERSION >= 3
-static struct PyModuleDef __pyx_moduledef = {
-    PyModuleDef_HEAD_INIT,
-    "cluster",
-    __pyx_mdoc, /* m_doc */
-    -1, /* m_size */
-    __pyx_methods /* m_methods */,
-    NULL, /* m_reload */
-    NULL, /* m_traverse */
-    NULL, /* m_clear */
-    NULL /* m_free */
-};
-#endif
+PyMODINIT_FUNC initcluster(void); /*proto*/
+PyMODINIT_FUNC initcluster(void) {
+  __pyx_init_filenames();
+  __pyx_m = Py_InitModule4("cluster", __pyx_methods, __pyx_mdoc, 0, PYTHON_API_VERSION);
+  if (!__pyx_m) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; goto __pyx_L1;};
+  Py_INCREF(__pyx_m);
+  __pyx_b = PyImport_AddModule("__builtin__");
+  if (!__pyx_b) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; goto __pyx_L1;};
+  if (PyObject_SetAttrString(__pyx_m, "__builtins__", __pyx_b) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; goto __pyx_L1;};
+  if (__Pyx_InitStrings(__pyx_string_tab) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; goto __pyx_L1;};
+  if (PyType_Ready(&__pyx_type_2bx_9intervals_7cluster_ClusterTree) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 56; goto __pyx_L1;}
+  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;
 
-static __Pyx_StringTabEntry __pyx_string_tab[] = {
-  {&__pyx_kp___cinit__, __pyx_k___cinit__, sizeof(__pyx_k___cinit__), 1, 1, 1},
-  {&__pyx_kp___dealloc__, __pyx_k___dealloc__, sizeof(__pyx_k___dealloc__), 1, 1, 1},
-  {&__pyx_kp_insert, __pyx_k_insert, sizeof(__pyx_k_insert), 1, 1, 1},
-  {&__pyx_kp_getregions, __pyx_k_getregions, sizeof(__pyx_k_getregions), 1, 1, 1},
-  {&__pyx_kp_getlines, __pyx_k_getlines, sizeof(__pyx_k_getlines), 1, 1, 1},
-  {&__pyx_kp_mincols, __pyx_k_mincols, sizeof(__pyx_k_mincols), 1, 1, 1},
-  {&__pyx_kp_minregions, __pyx_k_minregions, sizeof(__pyx_k_minregions), 1, 1, 1},
-  {&__pyx_kp_start, __pyx_k_start, sizeof(__pyx_k_start), 1, 1, 1},
-  {&__pyx_kp_end, __pyx_k_end, sizeof(__pyx_k_end), 1, 1, 1},
-  {&__pyx_kp_linenum, __pyx_k_linenum, sizeof(__pyx_k_linenum), 1, 1, 1},
-  {&__pyx_kp_append, __pyx_k_append, sizeof(__pyx_k_append), 1, 1, 1},
-  {0, 0, 0, 0, 0, 0}
-};
-static int __Pyx_InitCachedBuiltins(void) {
-  return 0;
-  return -1;
+  /* "/Users/kanwei/bx-python-kl/lib/bx/intervals/cluster.pyx":99 */
+  return;
+  __pyx_L1:;
+  __Pyx_AddTraceback("bx.intervals.cluster");
 }
 
-static int __Pyx_InitGlobals(void) {
-  if (__Pyx_InitStrings(__pyx_string_tab) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
-  return 0;
-  __pyx_L1_error:;
-  return -1;
-}
-
-#if PY_MAJOR_VERSION < 3
-PyMODINIT_FUNC initcluster(void); /*proto*/
-PyMODINIT_FUNC initcluster(void)
-#else
-PyMODINIT_FUNC PyInit_cluster(void); /*proto*/
-PyMODINIT_FUNC PyInit_cluster(void)
-#endif
-{
-  __pyx_empty_tuple = PyTuple_New(0); if (unlikely(!__pyx_empty_tuple)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-  /*--- Library function declarations ---*/
-  __pyx_init_filenames();
-  /*--- Initialize various global constants etc. ---*/
-  if (unlikely(__Pyx_InitGlobals() < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-  /*--- Module creation code ---*/
-  #if PY_MAJOR_VERSION < 3
-  __pyx_m = Py_InitModule4("cluster", __pyx_methods, __pyx_mdoc, 0, PYTHON_API_VERSION);
-  #else
-  __pyx_m = PyModule_Create(&__pyx_moduledef);
-  #endif
-  if (!__pyx_m) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
-  #if PY_MAJOR_VERSION < 3
-  Py_INCREF(__pyx_m);
-  #endif
-  __pyx_b = PyImport_AddModule(__Pyx_BUILTIN_MODULE_NAME);
-  if (!__pyx_b) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
-  if (PyObject_SetAttrString(__pyx_m, "__builtins__", __pyx_b) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
-  /*--- Builtin init code ---*/
-  if (unlikely(__Pyx_InitCachedBuiltins() < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-  __pyx_skip_dispatch = 0;
-  /*--- Global init code ---*/
-  /*--- Function export code ---*/
-  /*--- Type init code ---*/
-  if (PyType_Ready(&__pyx_type_2bx_9intervals_7cluster_ClusterTree) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-  if (PyObject_SetAttrString(__pyx_m, "ClusterTree", (PyObject *)&__pyx_type_2bx_9intervals_7cluster_ClusterTree) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
-  __pyx_ptype_2bx_9intervals_7cluster_ClusterTree = &__pyx_type_2bx_9intervals_7cluster_ClusterTree;
-  /*--- Type import code ---*/
-  /*--- Function import code ---*/
-  /*--- Execution code ---*/
-
-  /* "/Users/james/projects/bx-python/code/bx-python-central/lib/bx/intervals/cluster.pyx":87
- *         return regions
- * 
- *     def getlines( self ):             # <<<<<<<<<<<<<<
- *         cdef treeitr * myitr
- *         cdef ClusterNode * node
- */
-  #if PY_MAJOR_VERSION < 3
-  return;
-  #else
-  return __pyx_m;
-  #endif
-  __pyx_L1_error:;
-  __Pyx_AddTraceback("bx.intervals.cluster");
-  #if PY_MAJOR_VERSION >= 3
-  return NULL;
-  #endif
-}
-
-static const char *__pyx_filenames[] = {
+static char *__pyx_filenames[] = {
   "cluster.pyx",
 };
 
   __pyx_f = __pyx_filenames;
 }
 
-static void __Pyx_RaiseDoubleKeywordsError(
-    const char* func_name,
-    PyObject* kw_name)
-{
-    PyErr_Format(PyExc_TypeError,
-        #if PY_MAJOR_VERSION >= 3
-        "%s() got multiple values for keyword argument '%U'", func_name, kw_name);
+static void __Pyx_Raise(PyObject *type, PyObject *value, PyObject *tb) {
+    Py_XINCREF(type);
+    Py_XINCREF(value);
+    Py_XINCREF(tb);
+    /* First, check the traceback argument, replacing None with NULL. */
+    if (tb == Py_None) {
+        Py_DECREF(tb);
+        tb = 0;
+    }
+    else if (tb != NULL && !PyTraceBack_Check(tb)) {
+        PyErr_SetString(PyExc_TypeError,
+            "raise: arg 3 must be a traceback or None");
+        goto raise_error;
+    }
+    /* Next, replace a missing value with None */
+    if (value == NULL) {
+        value = Py_None;
+        Py_INCREF(value);
+    }
+    #if PY_VERSION_HEX < 0x02050000
+    if (!PyClass_Check(type))
+    #else
+    if (!PyType_Check(type))
+    #endif
+    {
+        /* Raising an instance.  The value should be a dummy. */
+        if (value != Py_None) {
+            PyErr_SetString(PyExc_TypeError,
+                "instance exception may not have a separate value");
+            goto raise_error;
+        }
+        /* Normalize to raise <class>, <instance> */
+        Py_DECREF(value);
+        value = type;
+        #if PY_VERSION_HEX < 0x02050000
+            if (PyInstance_Check(type)) {
+                type = (PyObject*) ((PyInstanceObject*)type)->in_class;
+                Py_INCREF(type);
+            }
+            else {
+                PyErr_SetString(PyExc_TypeError,
+                    "raise: exception must be an old-style class or instance");
+                goto raise_error;
+            }
         #else
-        "%s() got multiple values for keyword argument '%s'", func_name,
-        PyString_AS_STRING(kw_name));
+            type = (PyObject*) type->ob_type;
+            Py_INCREF(type);
+            if (!PyType_IsSubtype((PyTypeObject *)type, (PyTypeObject *)PyExc_BaseException)) {
+                PyErr_SetString(PyExc_TypeError,
+                    "raise: exception class must be a subclass of BaseException");
+                goto raise_error;
+            }
         #endif
+    }
+    PyErr_Restore(type, value, tb);
+    return;
+raise_error:
+    Py_XDECREF(value);
+    Py_XDECREF(type);
+    Py_XDECREF(tb);
+    return;
 }
 
-static void __Pyx_RaiseArgtupleInvalid(
-    const char* func_name,
-    int exact,
-    Py_ssize_t num_min,
-    Py_ssize_t num_max,
-    Py_ssize_t num_found)
-{
-    Py_ssize_t num_expected;
-    const char *number, *more_or_less;
-
-    if (num_found < num_min) {
-        num_expected = num_min;
-        more_or_less = "at least";
-    } else {
-        num_expected = num_max;
-        more_or_less = "at most";
-    }
-    if (exact) {
-        more_or_less = "exactly";
-    }
-    number = (num_expected == 1) ? "" : "s";
-    PyErr_Format(PyExc_TypeError,
-        #if PY_VERSION_HEX < 0x02050000
-            "%s() takes %s %d positional argument%s (%d given)",
-        #else
-            "%s() takes %s %zd positional argument%s (%zd given)",
-        #endif
-        func_name, more_or_less, num_expected, number, num_found);
+static PyObject *__Pyx_GetName(PyObject *dict, PyObject *name) {
+    PyObject *result;
+    result = PyObject_GetAttr(dict, name);
+    if (!result)
+        PyErr_SetObject(PyExc_NameError, name);
+    return result;
 }
 
-static int __Pyx_ParseOptionalKeywords(
-    PyObject *kwds,
-    PyObject **argnames[],
-    PyObject *kwds2,
-    PyObject *values[],
-    Py_ssize_t num_pos_args,
-    const char* function_name)
-{
-    PyObject *key = 0, *value = 0;
-    Py_ssize_t pos = 0;
-    PyObject*** name;
-    PyObject*** first_kw_arg = argnames + num_pos_args;
-
-    while (PyDict_Next(kwds, &pos, &key, &value)) {
-        #if PY_MAJOR_VERSION < 3
-        if (unlikely(!PyString_CheckExact(key)) && unlikely(!PyString_Check(key))) {
-        #else
-        if (unlikely(!PyUnicode_CheckExact(key)) && unlikely(!PyUnicode_Check(key))) {
-        #endif
-            goto invalid_keyword_type;
-        } else {
-            name = argnames;
-            while (*name && (**name != key)) name++;
-            if (*name) {
-                if (name < first_kw_arg) goto arg_passed_twice;
-                values[name-argnames] = value;
-            } else {
-                for (name = first_kw_arg; *name; name++) {
-                    #if PY_MAJOR_VERSION >= 3
-                    if (PyUnicode_GET_SIZE(**name) == PyUnicode_GET_SIZE(key) &&
-                        PyUnicode_Compare(**name, key) == 0) break;
-                    #else
-                    if (PyString_GET_SIZE(**name) == PyString_GET_SIZE(key) &&
-                        strcmp(PyString_AS_STRING(**name),
-                               PyString_AS_STRING(key)) == 0) break;
-                    #endif
-                }
-                if (*name) {
-                    values[name-argnames] = value;
-                } else {
-                    /* unexpected keyword found */
-                    for (name=argnames; name != first_kw_arg; name++) {
-                        if (**name == key) goto arg_passed_twice;
-                        #if PY_MAJOR_VERSION >= 3
-                        if (PyUnicode_GET_SIZE(**name) == PyUnicode_GET_SIZE(key) &&
-                            PyUnicode_Compare(**name, key) == 0) goto arg_passed_twice;
-                        #else
-                        if (PyString_GET_SIZE(**name) == PyString_GET_SIZE(key) &&
-                            strcmp(PyString_AS_STRING(**name),
-                                   PyString_AS_STRING(key)) == 0) goto arg_passed_twice;
-                        #endif
-                    }
-                    if (kwds2) {
-                        if (unlikely(PyDict_SetItem(kwds2, key, value))) goto bad;
-                    } else {
-                        goto invalid_keyword;
-                    }
-                }
-            }
-        }
+static int __Pyx_InitStrings(__Pyx_StringTabEntry *t) {
+    while (t->p) {
+        *t->p = PyString_FromStringAndSize(t->s, t->n - 1);
+        if (!*t->p)
+            return -1;
+        if (t->i)
+            PyString_InternInPlace(t->p);
+        ++t;
     }
     return 0;
-arg_passed_twice:
-    __Pyx_RaiseDoubleKeywordsError(function_name, **name);
-    goto bad;
-invalid_keyword_type:
-    PyErr_Format(PyExc_TypeError,
-        "%s() keywords must be strings", function_name);
-    goto bad;
-invalid_keyword:
-    PyErr_Format(PyExc_TypeError,
-    #if PY_MAJOR_VERSION < 3
-        "%s() got an unexpected keyword argument '%s'",
-        function_name, PyString_AsString(key));
-    #else
-        "%s() got an unexpected keyword argument '%U'",
-        function_name, key);
-    #endif
-bad:
-    return -1;
 }
 
 #include "compile.h"
 #include "frameobject.h"
 #include "traceback.h"
 
-static void __Pyx_AddTraceback(const char *funcname) {
+static void __Pyx_AddTraceback(char *funcname) {
     PyObject *py_srcfile = 0;
     PyObject *py_funcname = 0;
     PyObject *py_globals = 0;
+    PyObject *empty_tuple = 0;
     PyObject *empty_string = 0;
     PyCodeObject *py_code = 0;
     PyFrameObject *py_frame = 0;
-
-    #if PY_MAJOR_VERSION < 3
+    
     py_srcfile = PyString_FromString(__pyx_filename);
-    #else
-    py_srcfile = PyUnicode_FromString(__pyx_filename);
-    #endif
     if (!py_srcfile) goto bad;
-    if (__pyx_clineno) {
-        #if PY_MAJOR_VERSION < 3
-        py_funcname = PyString_FromFormat( "%s (%s:%d)", funcname, __pyx_cfilenm, __pyx_clineno);
-        #else
-        py_funcname = PyUnicode_FromFormat( "%s (%s:%d)", funcname, __pyx_cfilenm, __pyx_clineno);
-        #endif
-    }
-    else {
-        #if PY_MAJOR_VERSION < 3
-        py_funcname = PyString_FromString(funcname);
-        #else
-        py_funcname = PyUnicode_FromString(funcname);
-        #endif
-    }
+    py_funcname = PyString_FromString(funcname);
     if (!py_funcname) goto bad;
     py_globals = PyModule_GetDict(__pyx_m);
     if (!py_globals) goto bad;
-    #if PY_MAJOR_VERSION < 3
-    empty_string = PyString_FromStringAndSize("", 0);
-    #else
-    empty_string = PyBytes_FromStringAndSize("", 0);
-    #endif
+    empty_tuple = PyTuple_New(0);
+    if (!empty_tuple) goto bad;
+    empty_string = PyString_FromString("");
     if (!empty_string) goto bad;
     py_code = PyCode_New(
         0,            /*int argcount,*/
-        #if PY_MAJOR_VERSION >= 3
-        0,            /*int kwonlyargcount,*/
-        #endif
         0,            /*int nlocals,*/
         0,            /*int stacksize,*/
         0,            /*int flags,*/
         empty_string, /*PyObject *code,*/
-        __pyx_empty_tuple,  /*PyObject *consts,*/
-        __pyx_empty_tuple,  /*PyObject *names,*/
-        __pyx_empty_tuple,  /*PyObject *varnames,*/
-        __pyx_empty_tuple,  /*PyObject *freevars,*/
-        __pyx_empty_tuple,  /*PyObject *cellvars,*/
+        empty_tuple,  /*PyObject *consts,*/
+        empty_tuple,  /*PyObject *names,*/
+        empty_tuple,  /*PyObject *varnames,*/
+        empty_tuple,  /*PyObject *freevars,*/
+        empty_tuple,  /*PyObject *cellvars,*/
         py_srcfile,   /*PyObject *filename,*/
         py_funcname,  /*PyObject *name,*/
         __pyx_lineno,   /*int firstlineno,*/
     );
     if (!py_code) goto bad;
     py_frame = PyFrame_New(
-        PyThreadState_GET(), /*PyThreadState *tstate,*/
+        PyThreadState_Get(), /*PyThreadState *tstate,*/
         py_code,             /*PyCodeObject *code,*/
         py_globals,          /*PyObject *globals,*/
         0                    /*PyObject *locals*/
 bad:
     Py_XDECREF(py_srcfile);
     Py_XDECREF(py_funcname);
+    Py_XDECREF(empty_tuple);
     Py_XDECREF(empty_string);
     Py_XDECREF(py_code);
     Py_XDECREF(py_frame);
 }
-
-static int __Pyx_InitStrings(__Pyx_StringTabEntry *t) {
-    while (t->p) {
-        #if PY_MAJOR_VERSION < 3
-        if (t->is_unicode && (!t->is_identifier)) {
-            *t->p = PyUnicode_DecodeUTF8(t->s, t->n - 1, NULL);
-        } else if (t->intern) {
-            *t->p = PyString_InternFromString(t->s);
-        } else {
-            *t->p = PyString_FromStringAndSize(t->s, t->n - 1);
-        }
-        #else  /* Python 3+ has unicode identifiers */
-        if (t->is_identifier || (t->is_unicode && t->intern)) {
-            *t->p = PyUnicode_InternFromString(t->s);
-        } else if (t->is_unicode) {
-            *t->p = PyUnicode_FromStringAndSize(t->s, t->n - 1);
-        } else {
-            *t->p = PyBytes_FromStringAndSize(t->s, t->n - 1);
-        }
-        #endif
-        if (!*t->p)
-            return -1;
-        ++t;
-    }
-    return 0;
-}
-
-/* Type Conversion Functions */
-
-static INLINE Py_ssize_t __pyx_PyIndex_AsSsize_t(PyObject* b) {
-  Py_ssize_t ival;
-  PyObject* x = PyNumber_Index(b);
-  if (!x) return -1;
-  ival = PyInt_AsSsize_t(x);
-  Py_DECREF(x);
-  return ival;
-}
-
-static INLINE int __Pyx_PyObject_IsTrue(PyObject* x) {
-   if (x == Py_True) return 1;
-   else if (x == Py_False) return 0;
-   else return PyObject_IsTrue(x);
-}
-
-static INLINE PY_LONG_LONG __pyx_PyInt_AsLongLong(PyObject* x) {
-    if (PyInt_CheckExact(x)) {
-        return PyInt_AS_LONG(x);
-    }
-    else if (PyLong_CheckExact(x)) {
-        return PyLong_AsLongLong(x);
-    }
-    else {
-        PY_LONG_LONG val;
-        PyObject* tmp = PyNumber_Int(x); if (!tmp) return (PY_LONG_LONG)-1;
-        val = __pyx_PyInt_AsLongLong(tmp);
-        Py_DECREF(tmp);
-        return val;
-    }
-}
-
-static INLINE unsigned PY_LONG_LONG __pyx_PyInt_AsUnsignedLongLong(PyObject* x) {
-    if (PyInt_CheckExact(x)) {
-        long val = PyInt_AS_LONG(x);
-        if (unlikely(val < 0)) {
-            PyErr_SetString(PyExc_TypeError, "Negative assignment to unsigned type.");
-            return (unsigned PY_LONG_LONG)-1;
-        }
-        return val;
-    }
-    else if (PyLong_CheckExact(x)) {
-        return PyLong_AsUnsignedLongLong(x);
-    }
-    else {
-        PY_LONG_LONG val;
-        PyObject* tmp = PyNumber_Int(x); if (!tmp) return (PY_LONG_LONG)-1;
-        val = __pyx_PyInt_AsUnsignedLongLong(tmp);
-        Py_DECREF(tmp);
-        return val;
-    }
-}
-
-
-static INLINE unsigned char __pyx_PyInt_unsigned_char(PyObject* x) {
-    if (sizeof(unsigned char) < sizeof(long)) {
-        long long_val = __pyx_PyInt_AsLong(x);
-        unsigned char val = (unsigned char)long_val;
-        if (unlikely((val != long_val)  || (long_val < 0))) {
-            PyErr_SetString(PyExc_OverflowError, "value too large to convert to unsigned char");
-            return (unsigned char)-1;
-        }
-        return val;
-    }
-    else {
-        return __pyx_PyInt_AsLong(x);
-    }
-}
-
-static INLINE unsigned short __pyx_PyInt_unsigned_short(PyObject* x) {
-    if (sizeof(unsigned short) < sizeof(long)) {
-        long long_val = __pyx_PyInt_AsLong(x);
-        unsigned short val = (unsigned short)long_val;
-        if (unlikely((val != long_val)  || (long_val < 0))) {
-            PyErr_SetString(PyExc_OverflowError, "value too large to convert to unsigned short");
-            return (unsigned short)-1;
-        }
-        return val;
-    }
-    else {
-        return __pyx_PyInt_AsLong(x);
-    }
-}
-
-static INLINE char __pyx_PyInt_char(PyObject* x) {
-    if (sizeof(char) < sizeof(long)) {
-        long long_val = __pyx_PyInt_AsLong(x);
-        char val = (char)long_val;
-        if (unlikely((val != long_val) )) {
-            PyErr_SetString(PyExc_OverflowError, "value too large to convert to char");
-            return (char)-1;
-        }
-        return val;
-    }
-    else {
-        return __pyx_PyInt_AsLong(x);
-    }
-}
-
-static INLINE short __pyx_PyInt_short(PyObject* x) {
-    if (sizeof(short) < sizeof(long)) {
-        long long_val = __pyx_PyInt_AsLong(x);
-        short val = (short)long_val;
-        if (unlikely((val != long_val) )) {
-            PyErr_SetString(PyExc_OverflowError, "value too large to convert to short");
-            return (short)-1;
-        }
-        return val;
-    }
-    else {
-        return __pyx_PyInt_AsLong(x);
-    }
-}
-
-static INLINE int __pyx_PyInt_int(PyObject* x) {
-    if (sizeof(int) < sizeof(long)) {
-        long long_val = __pyx_PyInt_AsLong(x);
-        int val = (int)long_val;
-        if (unlikely((val != long_val) )) {
-            PyErr_SetString(PyExc_OverflowError, "value too large to convert to int");
-            return (int)-1;
-        }
-        return val;
-    }
-    else {
-        return __pyx_PyInt_AsLong(x);
-    }
-}
-
-static INLINE long __pyx_PyInt_long(PyObject* x) {
-    if (sizeof(long) < sizeof(long)) {
-        long long_val = __pyx_PyInt_AsLong(x);
-        long val = (long)long_val;
-        if (unlikely((val != long_val) )) {
-            PyErr_SetString(PyExc_OverflowError, "value too large to convert to long");
-            return (long)-1;
-        }
-        return val;
-    }
-    else {
-        return __pyx_PyInt_AsLong(x);
-    }
-}
-
-static INLINE signed char __pyx_PyInt_signed_char(PyObject* x) {
-    if (sizeof(signed char) < sizeof(long)) {
-        long long_val = __pyx_PyInt_AsLong(x);
-        signed char val = (signed char)long_val;
-        if (unlikely((val != long_val) )) {
-            PyErr_SetString(PyExc_OverflowError, "value too large to convert to signed char");
-            return (signed char)-1;
-        }
-        return val;
-    }
-    else {
-        return __pyx_PyInt_AsLong(x);
-    }
-}
-
-static INLINE signed short __pyx_PyInt_signed_short(PyObject* x) {
-    if (sizeof(signed short) < sizeof(long)) {
-        long long_val = __pyx_PyInt_AsLong(x);
-        signed short val = (signed short)long_val;
-        if (unlikely((val != long_val) )) {
-            PyErr_SetString(PyExc_OverflowError, "value too large to convert to signed short");
-            return (signed short)-1;
-        }
-        return val;
-    }
-    else {
-        return __pyx_PyInt_AsLong(x);
-    }
-}
-
-static INLINE signed int __pyx_PyInt_signed_int(PyObject* x) {
-    if (sizeof(signed int) < sizeof(long)) {
-        long long_val = __pyx_PyInt_AsLong(x);
-        signed int val = (signed int)long_val;
-        if (unlikely((val != long_val) )) {
-            PyErr_SetString(PyExc_OverflowError, "value too large to convert to signed int");
-            return (signed int)-1;
-        }
-        return val;
-    }
-    else {
-        return __pyx_PyInt_AsLong(x);
-    }
-}
-
-static INLINE signed long __pyx_PyInt_signed_long(PyObject* x) {
-    if (sizeof(signed long) < sizeof(long)) {
-        long long_val = __pyx_PyInt_AsLong(x);
-        signed long val = (signed long)long_val;
-        if (unlikely((val != long_val) )) {
-            PyErr_SetString(PyExc_OverflowError, "value too large to convert to signed long");
-            return (signed long)-1;
-        }
-        return val;
-    }
-    else {
-        return __pyx_PyInt_AsLong(x);
-    }
-}
-
-static INLINE long double __pyx_PyInt_long_double(PyObject* x) {
-    if (sizeof(long double) < sizeof(long)) {
-        long long_val = __pyx_PyInt_AsLong(x);
-        long double val = (long double)long_val;
-        if (unlikely((val != long_val) )) {
-            PyErr_SetString(PyExc_OverflowError, "value too large to convert to long double");
-            return (long double)-1;
-        }
-        return val;
-    }
-    else {
-        return __pyx_PyInt_AsLong(x);
-    }
-}
-

File lib/bx/intervals/cluster.pyx

 """
-ClusterTree data structure that supports efficient queries for "cluster" of
-intervals (groups where no interval is more than some distance from at least
-one other).
+Kanwei Li, 2009
+Inspired by previous ClusterTree
 
-TODO: Documentation of the algorithmic details.
+Provides a ClusterTree data structure that supports efficient finding of 
+clusters of intervals that are within a certain distance apart.
+
+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.
+
+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.
+
+C source code is in src/cluster.c
 """
 
-cdef extern from "common.h":
-    pass
-
 cdef extern from "cluster.h":
-    cdef struct listitem:
-        int value
-        listitem * next
-
-    cdef struct linelist:
-        listitem * head
-        listitem * tail
-        
-    cdef struct ClusterNode:
+    
+    cdef struct struct_interval:
         int start
         int end
-        int regions
-        ClusterNode * left
-        ClusterNode * right
-        linelist * linenums
+        int id
+        struct_interval * next
 
-    cdef struct treeitr:
-        ClusterNode * next
-        ClusterNode * value
+    ctypedef struct_interval interval
+    
+    cdef struct struct_clusternode:
+        int start
+        int end
+        struct_interval *interval_head
+        struct_interval *interval_tail
+    
+    ctypedef struct_clusternode clusternode
+    
+    cdef struct struct_clustertree:
+        int max_dist
+        int min_intervals
 
-    # Insert into tree
-    ClusterNode * clusterNodeInsert(ClusterNode ** cn, int start, int end, int linenum, int mincols)
+        struct_clusternode *root
     
-    # Find node holding position
-    ClusterNode * clusterNodeFind(ClusterNode * cn, int position)
-    # Free entire tree
-    void freetree(ClusterNode ** cn)
+    ctypedef struct_clustertree clustertree
+    
+    cdef struct struct_treeitr:
+        struct_treeitr *next
+        struct_clusternode *node
+    
+    ctypedef struct_treeitr treeitr
+    
+    clusternode* clusternode_insert(clustertree *tree, clusternode *node, int start, int end, int id)
+    clustertree* create_clustertree(int max_dist, int min_intervals)
+    treeitr* clusteritr(clustertree *tree)
+    void free_tree(clustertree *tree)
 
-    void get_itr_in(ClusterNode * root, treeitr **itr)
-
-    ClusterNode * next(treeitr **itr)
-
-    int has_next(treeitr **itr)
-    
 cdef class ClusterTree:
-    cdef ClusterNode * root
+    cdef clustertree *tree
     cdef int mincols
     cdef int minregions
     
-    def __new__( self, mincols, minregions ):
-        self.root = NULL
+    def __cinit__(self, mincols, minregions):
+        self.tree = create_clustertree(mincols, minregions)
         self.mincols = mincols
         self.minregions = minregions
+        
+    def __dealloc__(self):
+        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
+        
+        regions = []
+        itr = clusteritr(self.tree)
+        
+        while (itr):
+            ids = []
+            ival = itr.node.interval_head
+            while (ival):
+                ids.append(ival.id)
+                ival = ival.next
 
-    def __dealloc__( self ):
-        freetree( &self.root )
+            regions.append( (itr.node.start, itr.node.end, sorted(ids)) )
+            itr = itr.next
+        return regions
         
-    def insert( self, int start, int end, int linenum):
-        clusterNodeInsert( &self.root, start, end, linenum, self.mincols )
-        return self
-
-    def getregions( self ):
-        cdef treeitr * myitr
-        cdef ClusterNode * node
-        cdef linelist* nums
-        cdef listitem* num
-
-        myitr = NULL
-        get_itr_in(self.root, &myitr)
-        regions = []
-        while (has_next(&myitr)):
-            node = next(&myitr)
-            if node.regions >= self.minregions:
-                lines = []
-                if node.linenums and node.linenums.head:
-                    nums = node.linenums
-                    num = nums.head
-                    while num:
-                        lines.append( num.value )
-                        num = num.next
-                regions.append( ( node.start, node.end, lines ) )
-
-        return regions
-    
-    def getlines( self ):
-        cdef treeitr * myitr
-        cdef ClusterNode * node
-        cdef linelist* nums
-        cdef listitem* num
+    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
         
-        myitr = NULL
-        get_itr_in(self.root, &myitr)
         lines = []
-        while (has_next(&myitr)):