1/* Generated by Cython 0.17.4 on Sun Feb 24 19:48:34 2013 */ 2 3#define PY_SSIZE_T_CLEAN 4#include "Python.h" 5#ifndef Py_PYTHON_H 6 #error Python headers needed to compile C extensions, please install development version of Python. 7#elif PY_VERSION_HEX < 0x02040000 8 #error Cython requires Python 2.4+. 9#else 10#include <stddef.h> /* For offsetof */ 11#ifndef offsetof 12#define offsetof(type, member) ( (size_t) & ((type*)0) -> member ) 13#endif 14#if !defined(WIN32) && !defined(MS_WINDOWS) 15 #ifndef __stdcall 16 #define __stdcall 17 #endif 18 #ifndef __cdecl 19 #define __cdecl 20 #endif 21 #ifndef __fastcall 22 #define __fastcall 23 #endif 24#endif 25#ifndef DL_IMPORT 26 #define DL_IMPORT(t) t 27#endif 28#ifndef DL_EXPORT 29 #define DL_EXPORT(t) t 30#endif 31#ifndef PY_LONG_LONG 32 #define PY_LONG_LONG LONG_LONG 33#endif 34#ifndef Py_HUGE_VAL 35 #define Py_HUGE_VAL HUGE_VAL 36#endif 37#ifdef PYPY_VERSION 38#define CYTHON_COMPILING_IN_PYPY 1 39#define CYTHON_COMPILING_IN_CPYTHON 0 40#else 41#define CYTHON_COMPILING_IN_PYPY 0 42#define CYTHON_COMPILING_IN_CPYTHON 1 43#endif 44#if PY_VERSION_HEX < 0x02050000 45 typedef int Py_ssize_t; 46 #define PY_SSIZE_T_MAX INT_MAX 47 #define PY_SSIZE_T_MIN INT_MIN 48 #define PY_FORMAT_SIZE_T "" 49 #define CYTHON_FORMAT_SSIZE_T "" 50 #define PyInt_FromSsize_t(z) PyInt_FromLong(z) 51 #define PyInt_AsSsize_t(o) __Pyx_PyInt_AsInt(o) 52 #define PyNumber_Index(o) ((PyNumber_Check(o) && !PyFloat_Check(o)) ? PyNumber_Int(o) : \ 53 (PyErr_Format(PyExc_TypeError, \ 54 "expected index value, got %.200s", Py_TYPE(o)->tp_name), \ 55 (PyObject*)0)) 56 #define __Pyx_PyIndex_Check(o) (PyNumber_Check(o) && !PyFloat_Check(o) && \ 57 !PyComplex_Check(o)) 58 #define PyIndex_Check __Pyx_PyIndex_Check 59 #define PyErr_WarnEx(category, message, stacklevel) PyErr_Warn(category, message) 60 #define __PYX_BUILD_PY_SSIZE_T "i" 61#else 62 #define __PYX_BUILD_PY_SSIZE_T "n" 63 #define CYTHON_FORMAT_SSIZE_T "z" 64 #define __Pyx_PyIndex_Check PyIndex_Check 65#endif 66#if PY_VERSION_HEX < 0x02060000 67 #define Py_REFCNT(ob) (((PyObject*)(ob))->ob_refcnt) 68 #define Py_TYPE(ob) (((PyObject*)(ob))->ob_type) 69 #define Py_SIZE(ob) (((PyVarObject*)(ob))->ob_size) 70 #define PyVarObject_HEAD_INIT(type, size) \ 71 PyObject_HEAD_INIT(type) size, 72 #define PyType_Modified(t) 73 typedef struct { 74 void *buf; 75 PyObject *obj; 76 Py_ssize_t len; 77 Py_ssize_t itemsize; 78 int readonly; 79 int ndim; 80 char *format; 81 Py_ssize_t *shape; 82 Py_ssize_t *strides; 83 Py_ssize_t *suboffsets; 84 void *internal; 85 } Py_buffer; 86 #define PyBUF_SIMPLE 0 87 #define PyBUF_WRITABLE 0x0001 88 #define PyBUF_FORMAT 0x0004 89 #define PyBUF_ND 0x0008 90 #define PyBUF_STRIDES (0x0010 | PyBUF_ND) 91 #define PyBUF_C_CONTIGUOUS (0x0020 | PyBUF_STRIDES) 92 #define PyBUF_F_CONTIGUOUS (0x0040 | PyBUF_STRIDES) 93 #define PyBUF_ANY_CONTIGUOUS (0x0080 | PyBUF_STRIDES) 94 #define PyBUF_INDIRECT (0x0100 | PyBUF_STRIDES) 95 #define PyBUF_RECORDS (PyBUF_STRIDES | PyBUF_FORMAT | PyBUF_WRITABLE) 96 #define PyBUF_FULL (PyBUF_INDIRECT | PyBUF_FORMAT | PyBUF_WRITABLE) 97 typedef int (*getbufferproc)(PyObject *, Py_buffer *, int); 98 typedef void (*releasebufferproc)(PyObject *, Py_buffer *); 99#endif 100#if PY_MAJOR_VERSION < 3 101 #define __Pyx_BUILTIN_MODULE_NAME "__builtin__" 102 #define __Pyx_PyCode_New(a, k, l, s, f, code, c, n, v, fv, cell, fn, name, fline, lnos) \ 103 PyCode_New(a, l, s, f, code, c, n, v, fv, cell, fn, name, fline, lnos) 104#else 105 #define __Pyx_BUILTIN_MODULE_NAME "builtins" 106 #define __Pyx_PyCode_New(a, k, l, s, f, code, c, n, v, fv, cell, fn, name, fline, lnos) \ 107 PyCode_New(a, k, l, s, f, code, c, n, v, fv, cell, fn, name, fline, lnos) 108#endif 109#if PY_MAJOR_VERSION < 3 && PY_MINOR_VERSION < 6 110 #define PyUnicode_FromString(s) PyUnicode_Decode(s, strlen(s), "UTF-8", "strict") 111#endif 112#if PY_MAJOR_VERSION >= 3 113 #define Py_TPFLAGS_CHECKTYPES 0 114 #define Py_TPFLAGS_HAVE_INDEX 0 115#endif 116#if (PY_VERSION_HEX < 0x02060000) || (PY_MAJOR_VERSION >= 3) 117 #define Py_TPFLAGS_HAVE_NEWBUFFER 0 118#endif 119#if PY_VERSION_HEX > 0x03030000 && defined(PyUnicode_KIND) 120 #define CYTHON_PEP393_ENABLED 1 121 #define __Pyx_PyUnicode_READY(op) (likely(PyUnicode_IS_READY(op)) ? \ 122 0 : _PyUnicode_Ready((PyObject *)(op))) 123 #define __Pyx_PyUnicode_GET_LENGTH(u) PyUnicode_GET_LENGTH(u) 124 #define __Pyx_PyUnicode_READ_CHAR(u, i) PyUnicode_READ_CHAR(u, i) 125 #define __Pyx_PyUnicode_READ(k, d, i) PyUnicode_READ(k, d, i) 126#else 127 #define CYTHON_PEP393_ENABLED 0 128 #define __Pyx_PyUnicode_READY(op) (0) 129 #define __Pyx_PyUnicode_GET_LENGTH(u) PyUnicode_GET_SIZE(u) 130 #define __Pyx_PyUnicode_READ_CHAR(u, i) ((Py_UCS4)(PyUnicode_AS_UNICODE(u)[i])) 131 #define __Pyx_PyUnicode_READ(k, d, i) ((k=k), (Py_UCS4)(((Py_UNICODE*)d)[i])) 132#endif 133#if PY_MAJOR_VERSION >= 3 134 #define PyBaseString_Type PyUnicode_Type 135 #define PyStringObject PyUnicodeObject 136 #define PyString_Type PyUnicode_Type 137 #define PyString_Check PyUnicode_Check 138 #define PyString_CheckExact PyUnicode_CheckExact 139#endif 140#if PY_VERSION_HEX < 0x02060000 141 #define PyBytesObject PyStringObject 142 #define PyBytes_Type PyString_Type 143 #define PyBytes_Check PyString_Check 144 #define PyBytes_CheckExact PyString_CheckExact 145 #define PyBytes_FromString PyString_FromString 146 #define PyBytes_FromStringAndSize PyString_FromStringAndSize 147 #define PyBytes_FromFormat PyString_FromFormat 148 #define PyBytes_DecodeEscape PyString_DecodeEscape 149 #define PyBytes_AsString PyString_AsString 150 #define PyBytes_AsStringAndSize PyString_AsStringAndSize 151 #define PyBytes_Size PyString_Size 152 #define PyBytes_AS_STRING PyString_AS_STRING 153 #define PyBytes_GET_SIZE PyString_GET_SIZE 154 #define PyBytes_Repr PyString_Repr 155 #define PyBytes_Concat PyString_Concat 156 #define PyBytes_ConcatAndDel PyString_ConcatAndDel 157#endif 158#if PY_VERSION_HEX < 0x02060000 159 #define PySet_Check(obj) PyObject_TypeCheck(obj, &PySet_Type) 160 #define PyFrozenSet_Check(obj) PyObject_TypeCheck(obj, &PyFrozenSet_Type) 161#endif 162#ifndef PySet_CheckExact 163 #define PySet_CheckExact(obj) (Py_TYPE(obj) == &PySet_Type) 164#endif 165#define __Pyx_TypeCheck(obj, type) PyObject_TypeCheck(obj, (PyTypeObject *)type) 166#if PY_MAJOR_VERSION >= 3 167 #define PyIntObject PyLongObject 168 #define PyInt_Type PyLong_Type 169 #define PyInt_Check(op) PyLong_Check(op) 170 #define PyInt_CheckExact(op) PyLong_CheckExact(op) 171 #define PyInt_FromString PyLong_FromString 172 #define PyInt_FromUnicode PyLong_FromUnicode 173 #define PyInt_FromLong PyLong_FromLong 174 #define PyInt_FromSize_t PyLong_FromSize_t 175 #define PyInt_FromSsize_t PyLong_FromSsize_t 176 #define PyInt_AsLong PyLong_AsLong 177 #define PyInt_AS_LONG PyLong_AS_LONG 178 #define PyInt_AsSsize_t PyLong_AsSsize_t 179 #define PyInt_AsUnsignedLongMask PyLong_AsUnsignedLongMask 180 #define PyInt_AsUnsignedLongLongMask PyLong_AsUnsignedLongLongMask 181#endif 182#if PY_MAJOR_VERSION >= 3 183 #define PyBoolObject PyLongObject 184#endif 185#if PY_VERSION_HEX < 0x03020000 186 typedef long Py_hash_t; 187 #define __Pyx_PyInt_FromHash_t PyInt_FromLong 188 #define __Pyx_PyInt_AsHash_t PyInt_AsLong 189#else 190 #define __Pyx_PyInt_FromHash_t PyInt_FromSsize_t 191 #define __Pyx_PyInt_AsHash_t PyInt_AsSsize_t 192#endif 193#if (PY_MAJOR_VERSION < 3) || (PY_VERSION_HEX >= 0x03010300) 194 #define __Pyx_PySequence_GetSlice(obj, a, b) PySequence_GetSlice(obj, a, b) 195 #define __Pyx_PySequence_SetSlice(obj, a, b, value) PySequence_SetSlice(obj, a, b, value) 196 #define __Pyx_PySequence_DelSlice(obj, a, b) PySequence_DelSlice(obj, a, b) 197#else 198 #define __Pyx_PySequence_GetSlice(obj, a, b) (unlikely(!(obj)) ? \ 199 (PyErr_SetString(PyExc_SystemError, "null argument to internal routine"), (PyObject*)0) : \ 200 (likely((obj)->ob_type->tp_as_mapping) ? (PySequence_GetSlice(obj, a, b)) : \ 201 (PyErr_Format(PyExc_TypeError, "'%.200s' object is unsliceable", (obj)->ob_type->tp_name), (PyObject*)0))) 202 #define __Pyx_PySequence_SetSlice(obj, a, b, value) (unlikely(!(obj)) ? \ 203 (PyErr_SetString(PyExc_SystemError, "null argument to internal routine"), -1) : \ 204 (likely((obj)->ob_type->tp_as_mapping) ? (PySequence_SetSlice(obj, a, b, value)) : \ 205 (PyErr_Format(PyExc_TypeError, "'%.200s' object doesn't support slice assignment", (obj)->ob_type->tp_name), -1))) 206 #define __Pyx_PySequence_DelSlice(obj, a, b) (unlikely(!(obj)) ? \ 207 (PyErr_SetString(PyExc_SystemError, "null argument to internal routine"), -1) : \ 208 (likely((obj)->ob_type->tp_as_mapping) ? (PySequence_DelSlice(obj, a, b)) : \ 209 (PyErr_Format(PyExc_TypeError, "'%.200s' object doesn't support slice deletion", (obj)->ob_type->tp_name), -1))) 210#endif 211#if PY_MAJOR_VERSION >= 3 212 #define PyMethod_New(func, self, klass) ((self) ? PyMethod_New(func, self) : PyInstanceMethod_New(func)) 213#endif 214#if PY_VERSION_HEX < 0x02050000 215 #define __Pyx_GetAttrString(o,n) PyObject_GetAttrString((o),((char *)(n))) 216 #define __Pyx_SetAttrString(o,n,a) PyObject_SetAttrString((o),((char *)(n)),(a)) 217 #define __Pyx_DelAttrString(o,n) PyObject_DelAttrString((o),((char *)(n))) 218#else 219 #define __Pyx_GetAttrString(o,n) PyObject_GetAttrString((o),(n)) 220 #define __Pyx_SetAttrString(o,n,a) PyObject_SetAttrString((o),(n),(a)) 221 #define __Pyx_DelAttrString(o,n) PyObject_DelAttrString((o),(n)) 222#endif 223#if PY_VERSION_HEX < 0x02050000 224 #define __Pyx_NAMESTR(n) ((char *)(n)) 225 #define __Pyx_DOCSTR(n) ((char *)(n)) 226#else 227 #define __Pyx_NAMESTR(n) (n) 228 #define __Pyx_DOCSTR(n) (n) 229#endif 230 231 232#if PY_MAJOR_VERSION >= 3 233 #define __Pyx_PyNumber_Divide(x,y) PyNumber_TrueDivide(x,y) 234 #define __Pyx_PyNumber_InPlaceDivide(x,y) PyNumber_InPlaceTrueDivide(x,y) 235#else 236 #define __Pyx_PyNumber_Divide(x,y) PyNumber_Divide(x,y) 237 #define __Pyx_PyNumber_InPlaceDivide(x,y) PyNumber_InPlaceDivide(x,y) 238#endif 239 240#ifndef __PYX_EXTERN_C 241 #ifdef __cplusplus 242 #define __PYX_EXTERN_C extern "C" 243 #else 244 #define __PYX_EXTERN_C extern 245 #endif 246#endif 247 248#if defined(WIN32) || defined(MS_WINDOWS) 249#define _USE_MATH_DEFINES 250#endif 251#include <math.h> 252#define __PYX_HAVE__bintrees__qavltree 253#define __PYX_HAVE_API__bintrees__qavltree 254#include "ctrees.h" 255#include "stack.h" 256#ifdef _OPENMP 257#include <omp.h> 258#endif /* _OPENMP */ 259 260#ifdef PYREX_WITHOUT_ASSERTIONS 261#define CYTHON_WITHOUT_ASSERTIONS 262#endif 263 264 265/* inline attribute */ 266#ifndef CYTHON_INLINE 267 #if defined(__GNUC__) 268 #define CYTHON_INLINE __inline__ 269 #elif defined(_MSC_VER) 270 #define CYTHON_INLINE __inline 271 #elif defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L 272 #define CYTHON_INLINE inline 273 #else 274 #define CYTHON_INLINE 275 #endif 276#endif 277 278/* unused attribute */ 279#ifndef CYTHON_UNUSED 280# if defined(__GNUC__) 281# if !(defined(__cplusplus)) || (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) 282# define CYTHON_UNUSED __attribute__ ((__unused__)) 283# else 284# define CYTHON_UNUSED 285# endif 286# elif defined(__ICC) || (defined(__INTEL_COMPILER) && !defined(_MSC_VER)) 287# define CYTHON_UNUSED __attribute__ ((__unused__)) 288# else 289# define CYTHON_UNUSED 290# endif 291#endif 292 293typedef struct {PyObject **p; char *s; const long n; const char* encoding; const char is_unicode; const char is_str; const char intern; } __Pyx_StringTabEntry; /*proto*/ 294 295 296/* Type Conversion Predeclarations */ 297 298#define __Pyx_PyBytes_FromUString(s) PyBytes_FromString((char*)s) 299#define __Pyx_PyBytes_AsUString(s) ((unsigned char*) PyBytes_AsString(s)) 300 301#define __Pyx_Owned_Py_None(b) (Py_INCREF(Py_None), Py_None) 302#define __Pyx_PyBool_FromLong(b) ((b) ? (Py_INCREF(Py_True), Py_True) : (Py_INCREF(Py_False), Py_False)) 303static CYTHON_INLINE int __Pyx_PyObject_IsTrue(PyObject*); 304static CYTHON_INLINE PyObject* __Pyx_PyNumber_Int(PyObject* x); 305 306static CYTHON_INLINE Py_ssize_t __Pyx_PyIndex_AsSsize_t(PyObject*); 307static CYTHON_INLINE PyObject * __Pyx_PyInt_FromSize_t(size_t); 308static CYTHON_INLINE size_t __Pyx_PyInt_AsSize_t(PyObject*); 309 310#if CYTHON_COMPILING_IN_CPYTHON 311#define __pyx_PyFloat_AsDouble(x) (PyFloat_CheckExact(x) ? PyFloat_AS_DOUBLE(x) : PyFloat_AsDouble(x)) 312#else 313#define __pyx_PyFloat_AsDouble(x) PyFloat_AsDouble(x) 314#endif 315#define __pyx_PyFloat_AsFloat(x) ((float) __pyx_PyFloat_AsDouble(x)) 316 317#ifdef __GNUC__ 318 /* Test for GCC > 2.95 */ 319 #if __GNUC__ > 2 || (__GNUC__ == 2 && (__GNUC_MINOR__ > 95)) 320 #define likely(x) __builtin_expect(!!(x), 1) 321 #define unlikely(x) __builtin_expect(!!(x), 0) 322 #else /* __GNUC__ > 2 ... */ 323 #define likely(x) (x) 324 #define unlikely(x) (x) 325 #endif /* __GNUC__ > 2 ... */ 326#else /* __GNUC__ */ 327 #define likely(x) (x) 328 #define unlikely(x) (x) 329#endif /* __GNUC__ */ 330 331static PyObject *__pyx_m; 332static PyObject *__pyx_b; 333static PyObject *__pyx_empty_tuple; 334static PyObject *__pyx_empty_bytes; 335static int __pyx_lineno; 336static int __pyx_clineno = 0; 337static const char * __pyx_cfilenm= __FILE__; 338static const char *__pyx_filename; 339 340 341static const char *__pyx_f[] = { 342 "qavltree.pyx", 343 "cwalker.pxd", 344}; 345 346/*--- Type declarations ---*/ 347struct __pyx_obj_8bintrees_7cwalker_cWalker; 348struct __pyx_obj_8bintrees_8qavltree_cAVLTree; 349 350/* "cwalker.pxd":11 351 * from stack cimport node_stack_t 352 * 353 * cdef class cWalker: # <<<<<<<<<<<<<< 354 * cdef node_t *node 355 * cdef node_t *root 356 */ 357struct __pyx_obj_8bintrees_7cwalker_cWalker { 358 PyObject_HEAD 359 struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker *__pyx_vtab; 360 node_t *node; 361 node_t *root; 362 node_stack_t *stack; 363}; 364 365 366/* "bintrees\qavltree.pyx":16 367 * from ctrees cimport * 368 * 369 * cdef class cAVLTree: # <<<<<<<<<<<<<< 370 * cdef node_t *_root 371 * cdef int _count 372 */ 373struct __pyx_obj_8bintrees_8qavltree_cAVLTree { 374 PyObject_HEAD 375 node_t *_root; 376 int _count; 377}; 378 379 380 381/* "cwalker.pxd":11 382 * from stack cimport node_stack_t 383 * 384 * cdef class cWalker: # <<<<<<<<<<<<<< 385 * cdef node_t *node 386 * cdef node_t *root 387 */ 388 389struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker { 390 void (*set_tree)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, node_t *); 391 PyObject *(*reset)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, int __pyx_skip_dispatch); 392 PyObject *(*push)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, int __pyx_skip_dispatch); 393 PyObject *(*pop)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, int __pyx_skip_dispatch); 394}; 395static struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker *__pyx_vtabptr_8bintrees_7cwalker_cWalker; 396#ifndef CYTHON_REFNANNY 397 #define CYTHON_REFNANNY 0 398#endif 399#if CYTHON_REFNANNY 400 typedef struct { 401 void (*INCREF)(void*, PyObject*, int); 402 void (*DECREF)(void*, PyObject*, int); 403 void (*GOTREF)(void*, PyObject*, int); 404 void (*GIVEREF)(void*, PyObject*, int); 405 void* (*SetupContext)(const char*, int, const char*); 406 void (*FinishContext)(void**); 407 } __Pyx_RefNannyAPIStruct; 408 static __Pyx_RefNannyAPIStruct *__Pyx_RefNanny = NULL; 409 static __Pyx_RefNannyAPIStruct *__Pyx_RefNannyImportAPI(const char *modname); /*proto*/ 410 #define __Pyx_RefNannyDeclarations void *__pyx_refnanny = NULL; 411#ifdef WITH_THREAD 412 #define __Pyx_RefNannySetupContext(name, acquire_gil) \ 413 if (acquire_gil) { \ 414 PyGILState_STATE __pyx_gilstate_save = PyGILState_Ensure(); \ 415 __pyx_refnanny = __Pyx_RefNanny->SetupContext((name), __LINE__, __FILE__); \ 416 PyGILState_Release(__pyx_gilstate_save); \ 417 } else { \ 418 __pyx_refnanny = __Pyx_RefNanny->SetupContext((name), __LINE__, __FILE__); \ 419 } 420#else 421 #define __Pyx_RefNannySetupContext(name, acquire_gil) \ 422 __pyx_refnanny = __Pyx_RefNanny->SetupContext((name), __LINE__, __FILE__) 423#endif 424 #define __Pyx_RefNannyFinishContext() \ 425 __Pyx_RefNanny->FinishContext(&__pyx_refnanny) 426 #define __Pyx_INCREF(r) __Pyx_RefNanny->INCREF(__pyx_refnanny, (PyObject *)(r), __LINE__) 427 #define __Pyx_DECREF(r) __Pyx_RefNanny->DECREF(__pyx_refnanny, (PyObject *)(r), __LINE__) 428 #define __Pyx_GOTREF(r) __Pyx_RefNanny->GOTREF(__pyx_refnanny, (PyObject *)(r), __LINE__) 429 #define __Pyx_GIVEREF(r) __Pyx_RefNanny->GIVEREF(__pyx_refnanny, (PyObject *)(r), __LINE__) 430 #define __Pyx_XINCREF(r) do { if((r) != NULL) {__Pyx_INCREF(r); }} while(0) 431 #define __Pyx_XDECREF(r) do { if((r) != NULL) {__Pyx_DECREF(r); }} while(0) 432 #define __Pyx_XGOTREF(r) do { if((r) != NULL) {__Pyx_GOTREF(r); }} while(0) 433 #define __Pyx_XGIVEREF(r) do { if((r) != NULL) {__Pyx_GIVEREF(r);}} while(0) 434#else 435 #define __Pyx_RefNannyDeclarations 436 #define __Pyx_RefNannySetupContext(name, acquire_gil) 437 #define __Pyx_RefNannyFinishContext() 438 #define __Pyx_INCREF(r) Py_INCREF(r) 439 #define __Pyx_DECREF(r) Py_DECREF(r) 440 #define __Pyx_GOTREF(r) 441 #define __Pyx_GIVEREF(r) 442 #define __Pyx_XINCREF(r) Py_XINCREF(r) 443 #define __Pyx_XDECREF(r) Py_XDECREF(r) 444 #define __Pyx_XGOTREF(r) 445 #define __Pyx_XGIVEREF(r) 446#endif /* CYTHON_REFNANNY */ 447#define __Pyx_CLEAR(r) do { PyObject* tmp = ((PyObject*)(r)); r = NULL; __Pyx_DECREF(tmp);} while(0) 448#define __Pyx_XCLEAR(r) do { if((r) != NULL) {PyObject* tmp = ((PyObject*)(r)); r = NULL; __Pyx_DECREF(tmp);}} while(0) 449 450static PyObject *__Pyx_GetName(PyObject *dict, PyObject *name); /*proto*/ 451 452static void __Pyx_RaiseDoubleKeywordsError(const char* func_name, PyObject* kw_name); /*proto*/ 453 454static int __Pyx_ParseOptionalKeywords(PyObject *kwds, PyObject **argnames[], \ 455 PyObject *kwds2, PyObject *values[], Py_ssize_t num_pos_args, \ 456 const char* function_name); /*proto*/ 457 458static void __Pyx_RaiseArgtupleInvalid(const char* func_name, int exact, 459 Py_ssize_t num_min, Py_ssize_t num_max, Py_ssize_t num_found); /*proto*/ 460 461static CYTHON_INLINE void __Pyx_ErrRestore(PyObject *type, PyObject *value, PyObject *tb); /*proto*/ 462static CYTHON_INLINE void __Pyx_ErrFetch(PyObject **type, PyObject **value, PyObject **tb); /*proto*/ 463 464static void __Pyx_Raise(PyObject *type, PyObject *value, PyObject *tb, PyObject *cause); /*proto*/ 465 466static CYTHON_INLINE PyObject *__Pyx_GetItemInt_Generic(PyObject *o, PyObject* j) { 467 PyObject *r; 468 if (!j) return NULL; 469 r = PyObject_GetItem(o, j); 470 Py_DECREF(j); 471 return r; 472} 473#define __Pyx_GetItemInt_List(o, i, size, to_py_func) (((size) <= sizeof(Py_ssize_t)) ? \ 474 __Pyx_GetItemInt_List_Fast(o, i) : \ 475 __Pyx_GetItemInt_Generic(o, to_py_func(i))) 476static CYTHON_INLINE PyObject *__Pyx_GetItemInt_List_Fast(PyObject *o, Py_ssize_t i) { 477#if CYTHON_COMPILING_IN_CPYTHON 478 if (likely((0 <= i) & (i < PyList_GET_SIZE(o)))) { 479 PyObject *r = PyList_GET_ITEM(o, i); 480 Py_INCREF(r); 481 return r; 482 } 483 else if ((-PyList_GET_SIZE(o) <= i) & (i < 0)) { 484 PyObject *r = PyList_GET_ITEM(o, PyList_GET_SIZE(o) + i); 485 Py_INCREF(r); 486 return r; 487 } 488 return __Pyx_GetItemInt_Generic(o, PyInt_FromSsize_t(i)); 489#else 490 return PySequence_GetItem(o, i); 491#endif 492} 493#define __Pyx_GetItemInt_Tuple(o, i, size, to_py_func) (((size) <= sizeof(Py_ssize_t)) ? \ 494 __Pyx_GetItemInt_Tuple_Fast(o, i) : \ 495 __Pyx_GetItemInt_Generic(o, to_py_func(i))) 496static CYTHON_INLINE PyObject *__Pyx_GetItemInt_Tuple_Fast(PyObject *o, Py_ssize_t i) { 497#if CYTHON_COMPILING_IN_CPYTHON 498 if (likely((0 <= i) & (i < PyTuple_GET_SIZE(o)))) { 499 PyObject *r = PyTuple_GET_ITEM(o, i); 500 Py_INCREF(r); 501 return r; 502 } 503 else if ((-PyTuple_GET_SIZE(o) <= i) & (i < 0)) { 504 PyObject *r = PyTuple_GET_ITEM(o, PyTuple_GET_SIZE(o) + i); 505 Py_INCREF(r); 506 return r; 507 } 508 return __Pyx_GetItemInt_Generic(o, PyInt_FromSsize_t(i)); 509#else 510 return PySequence_GetItem(o, i); 511#endif 512} 513#define __Pyx_GetItemInt(o, i, size, to_py_func) (((size) <= sizeof(Py_ssize_t)) ? \ 514 __Pyx_GetItemInt_Fast(o, i) : \ 515 __Pyx_GetItemInt_Generic(o, to_py_func(i))) 516static CYTHON_INLINE PyObject *__Pyx_GetItemInt_Fast(PyObject *o, Py_ssize_t i) { 517#if CYTHON_COMPILING_IN_CPYTHON 518 if (PyList_CheckExact(o)) { 519 Py_ssize_t n = (likely(i >= 0)) ? i : i + PyList_GET_SIZE(o); 520 if (likely((n >= 0) & (n < PyList_GET_SIZE(o)))) { 521 PyObject *r = PyList_GET_ITEM(o, n); 522 Py_INCREF(r); 523 return r; 524 } 525 } 526 else if (PyTuple_CheckExact(o)) { 527 Py_ssize_t n = (likely(i >= 0)) ? i : i + PyTuple_GET_SIZE(o); 528 if (likely((n >= 0) & (n < PyTuple_GET_SIZE(o)))) { 529 PyObject *r = PyTuple_GET_ITEM(o, n); 530 Py_INCREF(r); 531 return r; 532 } 533 } else { /* inlined PySequence_GetItem() */ 534 PySequenceMethods *m = Py_TYPE(o)->tp_as_sequence; 535 if (likely(m && m->sq_item)) { 536 if (unlikely(i < 0) && likely(m->sq_length)) { 537 Py_ssize_t l = m->sq_length(o); 538 if (unlikely(l < 0)) return NULL; 539 i += l; 540 } 541 return m->sq_item(o, i); 542 } 543 } 544#else 545 if (PySequence_Check(o)) { 546 return PySequence_GetItem(o, i); 547 } 548#endif 549 return __Pyx_GetItemInt_Generic(o, PyInt_FromSsize_t(i)); 550} 551 552static PyObject *__Pyx_Import(PyObject *name, PyObject *from_list, long level); /*proto*/ 553 554static CYTHON_INLINE unsigned char __Pyx_PyInt_AsUnsignedChar(PyObject *); 555 556static CYTHON_INLINE unsigned short __Pyx_PyInt_AsUnsignedShort(PyObject *); 557 558static CYTHON_INLINE unsigned int __Pyx_PyInt_AsUnsignedInt(PyObject *); 559 560static CYTHON_INLINE char __Pyx_PyInt_AsChar(PyObject *); 561 562static CYTHON_INLINE short __Pyx_PyInt_AsShort(PyObject *); 563 564static CYTHON_INLINE int __Pyx_PyInt_AsInt(PyObject *); 565 566static CYTHON_INLINE signed char __Pyx_PyInt_AsSignedChar(PyObject *); 567 568static CYTHON_INLINE signed short __Pyx_PyInt_AsSignedShort(PyObject *); 569 570static CYTHON_INLINE signed int __Pyx_PyInt_AsSignedInt(PyObject *); 571 572static CYTHON_INLINE int __Pyx_PyInt_AsLongDouble(PyObject *); 573 574static CYTHON_INLINE unsigned long __Pyx_PyInt_AsUnsignedLong(PyObject *); 575 576static CYTHON_INLINE unsigned PY_LONG_LONG __Pyx_PyInt_AsUnsignedLongLong(PyObject *); 577 578static CYTHON_INLINE long __Pyx_PyInt_AsLong(PyObject *); 579 580static CYTHON_INLINE PY_LONG_LONG __Pyx_PyInt_AsLongLong(PyObject *); 581 582static CYTHON_INLINE signed long __Pyx_PyInt_AsSignedLong(PyObject *); 583 584static CYTHON_INLINE signed PY_LONG_LONG __Pyx_PyInt_AsSignedLongLong(PyObject *); 585 586static int __Pyx_check_binary_version(void); 587 588#if !defined(__Pyx_PyIdentifier_FromString) 589#if PY_MAJOR_VERSION < 3 590 #define __Pyx_PyIdentifier_FromString(s) PyString_FromString(s) 591#else 592 #define __Pyx_PyIdentifier_FromString(s) PyUnicode_FromString(s) 593#endif 594#endif 595 596static PyObject *__Pyx_ImportModule(const char *name); /*proto*/ 597 598static PyTypeObject *__Pyx_ImportType(const char *module_name, const char *class_name, size_t size, int strict); /*proto*/ 599 600static void* __Pyx_GetVtable(PyObject *dict); /*proto*/ 601 602typedef struct { 603 int code_line; 604 PyCodeObject* code_object; 605} __Pyx_CodeObjectCacheEntry; 606struct __Pyx_CodeObjectCache { 607 int count; 608 int max_count; 609 __Pyx_CodeObjectCacheEntry* entries; 610}; 611static struct __Pyx_CodeObjectCache __pyx_code_cache = {0,0,NULL}; 612static int __pyx_bisect_code_objects(__Pyx_CodeObjectCacheEntry* entries, int count, int code_line); 613static PyCodeObject *__pyx_find_code_object(int code_line); 614static void __pyx_insert_code_object(int code_line, PyCodeObject* code_object); 615 616static void __Pyx_AddTraceback(const char *funcname, int c_line, 617 int py_line, const char *filename); /*proto*/ 618 619static int __Pyx_InitStrings(__Pyx_StringTabEntry *t); /*proto*/ 620 621 622/* Module declarations from 'bintrees.ctrees' */ 623 624/* Module declarations from 'bintrees.stack' */ 625 626/* Module declarations from 'bintrees.cwalker' */ 627static PyTypeObject *__pyx_ptype_8bintrees_7cwalker_cWalker = 0; 628 629/* Module declarations from 'bintrees.qavltree' */ 630static PyTypeObject *__pyx_ptype_8bintrees_8qavltree_cAVLTree = 0; 631#define __Pyx_MODULE_NAME "bintrees.qavltree" 632int __pyx_module_is_main_bintrees__qavltree = 0; 633 634/* Implementation of 'bintrees.qavltree' */ 635static PyObject *__pyx_builtin_property; 636static PyObject *__pyx_builtin_KeyError; 637static PyObject *__pyx_builtin_MemoryError; 638static PyObject *__pyx_builtin_ValueError; 639static int __pyx_pf_8bintrees_8qavltree_8cAVLTree___cinit__(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self, PyObject *__pyx_v_items); /* proto */ 640static void __pyx_pf_8bintrees_8qavltree_8cAVLTree_2__dealloc__(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self); /* proto */ 641static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_4count(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self); /* proto */ 642static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_6__getstate__(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self); /* proto */ 643static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_8__setstate__(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self, PyObject *__pyx_v_state); /* proto */ 644static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_10clear(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self); /* proto */ 645static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_12get_value(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self, PyObject *__pyx_v_key); /* proto */ 646static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_14get_walker(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self); /* proto */ 647static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_16insert(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self, PyObject *__pyx_v_key, PyObject *__pyx_v_value); /* proto */ 648static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_18remove(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self, PyObject *__pyx_v_key); /* proto */ 649static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_20max_item(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self); /* proto */ 650static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_22min_item(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self); /* proto */ 651static char __pyx_k_1[] = "Can not allocate memory for node structure."; 652static char __pyx_k_3[] = "Tree is empty"; 653static char __pyx_k__key[] = "key"; 654static char __pyx_k__count[] = "count"; 655static char __pyx_k__items[] = "items"; 656static char __pyx_k__value[] = "value"; 657static char __pyx_k__update[] = "update"; 658static char __pyx_k____all__[] = "__all__"; 659static char __pyx_k__cWalker[] = "cWalker"; 660static char __pyx_k__cwalker[] = "cwalker"; 661static char __pyx_k__KeyError[] = "KeyError"; 662static char __pyx_k____main__[] = "__main__"; 663static char __pyx_k____test__[] = "__test__"; 664static char __pyx_k__cAVLTree[] = "cAVLTree"; 665static char __pyx_k__property[] = "property"; 666static char __pyx_k__ValueError[] = "ValueError"; 667static char __pyx_k__MemoryError[] = "MemoryError"; 668static PyObject *__pyx_kp_s_1; 669static PyObject *__pyx_kp_s_3; 670static PyObject *__pyx_n_s__KeyError; 671static PyObject *__pyx_n_s__MemoryError; 672static PyObject *__pyx_n_s__ValueError; 673static PyObject *__pyx_n_s____all__; 674static PyObject *__pyx_n_s____main__; 675static PyObject *__pyx_n_s____test__; 676static PyObject *__pyx_n_s__cAVLTree; 677static PyObject *__pyx_n_s__cWalker; 678static PyObject *__pyx_n_s__count; 679static PyObject *__pyx_n_s__cwalker; 680static PyObject *__pyx_n_s__items; 681static PyObject *__pyx_n_s__key; 682static PyObject *__pyx_n_s__property; 683static PyObject *__pyx_n_s__update; 684static PyObject *__pyx_n_s__value; 685static PyObject *__pyx_int_0; 686static PyObject *__pyx_k_tuple_2; 687static PyObject *__pyx_k_tuple_4; 688static PyObject *__pyx_k_tuple_5; 689 690/* Python wrapper */ 691static int __pyx_pw_8bintrees_8qavltree_8cAVLTree_1__cinit__(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/ 692static int __pyx_pw_8bintrees_8qavltree_8cAVLTree_1__cinit__(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds) { 693 PyObject *__pyx_v_items = 0; 694 int __pyx_r; 695 __Pyx_RefNannyDeclarations 696 __Pyx_RefNannySetupContext("__cinit__ (wrapper)", 0); 697 { 698 static PyObject **__pyx_pyargnames[] = {&__pyx_n_s__items,0}; 699 PyObject* values[1] = {0}; 700 701 /* "bintrees\qavltree.pyx":20 702 * cdef int _count 703 * 704 * def __cinit__(self, items=None): # <<<<<<<<<<<<<< 705 * self._root = NULL 706 * self._count = 0 707 */ 708 values[0] = ((PyObject *)Py_None); 709 if (unlikely(__pyx_kwds)) { 710 Py_ssize_t kw_args; 711 const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args); 712 switch (pos_args) { 713 case 1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0); 714 case 0: break; 715 default: goto __pyx_L5_argtuple_error; 716 } 717 kw_args = PyDict_Size(__pyx_kwds); 718 switch (pos_args) { 719 case 0: 720 if (kw_args > 0) { 721 PyObject* value = PyDict_GetItem(__pyx_kwds, __pyx_n_s__items); 722 if (value) { values[0] = value; kw_args--; } 723 } 724 } 725 if (unlikely(kw_args > 0)) { 726 if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "__cinit__") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 20; __pyx_clineno = __LINE__; goto __pyx_L3_error;} 727 } 728 } else { 729 switch (PyTuple_GET_SIZE(__pyx_args)) { 730 case 1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0); 731 case 0: break; 732 default: goto __pyx_L5_argtuple_error; 733 } 734 } 735 __pyx_v_items = values[0]; 736 } 737 goto __pyx_L4_argument_unpacking_done; 738 __pyx_L5_argtuple_error:; 739 __Pyx_RaiseArgtupleInvalid("__cinit__", 0, 0, 1, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 20; __pyx_clineno = __LINE__; goto __pyx_L3_error;} 740 __pyx_L3_error:; 741 __Pyx_AddTraceback("bintrees.qavltree.cAVLTree.__cinit__", __pyx_clineno, __pyx_lineno, __pyx_filename); 742 __Pyx_RefNannyFinishContext(); 743 return -1; 744 __pyx_L4_argument_unpacking_done:; 745 __pyx_r = __pyx_pf_8bintrees_8qavltree_8cAVLTree___cinit__(((struct __pyx_obj_8bintrees_8qavltree_cAVLTree *)__pyx_v_self), __pyx_v_items); 746 __Pyx_RefNannyFinishContext(); 747 return __pyx_r; 748} 749 750static int __pyx_pf_8bintrees_8qavltree_8cAVLTree___cinit__(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self, PyObject *__pyx_v_items) { 751 int __pyx_r; 752 __Pyx_RefNannyDeclarations 753 int __pyx_t_1; 754 PyObject *__pyx_t_2 = NULL; 755 PyObject *__pyx_t_3 = NULL; 756 PyObject *__pyx_t_4 = NULL; 757 int __pyx_lineno = 0; 758 const char *__pyx_filename = NULL; 759 int __pyx_clineno = 0; 760 __Pyx_RefNannySetupContext("__cinit__", 0); 761 762 /* "bintrees\qavltree.pyx":21 763 * 764 * def __cinit__(self, items=None): 765 * self._root = NULL # <<<<<<<<<<<<<< 766 * self._count = 0 767 * if items: 768 */ 769 __pyx_v_self->_root = NULL; 770 771 /* "bintrees\qavltree.pyx":22 772 * def __cinit__(self, items=None): 773 * self._root = NULL 774 * self._count = 0 # <<<<<<<<<<<<<< 775 * if items: 776 * self.update(items) 777 */ 778 __pyx_v_self->_count = 0; 779 780 /* "bintrees\qavltree.pyx":23 781 * self._root = NULL 782 * self._count = 0 783 * if items: # <<<<<<<<<<<<<< 784 * self.update(items) 785 * 786 */ 787 __pyx_t_1 = __Pyx_PyObject_IsTrue(__pyx_v_items); if (unlikely(__pyx_t_1 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 788 if (__pyx_t_1) { 789 790 /* "bintrees\qavltree.pyx":24 791 * self._count = 0 792 * if items: 793 * self.update(items) # <<<<<<<<<<<<<< 794 * 795 * def __dealloc__(self): 796 */ 797 __pyx_t_2 = PyObject_GetAttr(((PyObject *)__pyx_v_self), __pyx_n_s__update); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 24; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 798 __Pyx_GOTREF(__pyx_t_2); 799 __pyx_t_3 = PyTuple_New(1); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 24; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 800 __Pyx_GOTREF(__pyx_t_3); 801 __Pyx_INCREF(__pyx_v_items); 802 PyTuple_SET_ITEM(__pyx_t_3, 0, __pyx_v_items); 803 __Pyx_GIVEREF(__pyx_v_items); 804 __pyx_t_4 = PyObject_Call(__pyx_t_2, ((PyObject *)__pyx_t_3), NULL); if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 24; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 805 __Pyx_GOTREF(__pyx_t_4); 806 __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; 807 __Pyx_DECREF(((PyObject *)__pyx_t_3)); __pyx_t_3 = 0; 808 __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0; 809 goto __pyx_L3; 810 } 811 __pyx_L3:; 812 813 __pyx_r = 0; 814 goto __pyx_L0; 815 __pyx_L1_error:; 816 __Pyx_XDECREF(__pyx_t_2); 817 __Pyx_XDECREF(__pyx_t_3); 818 __Pyx_XDECREF(__pyx_t_4); 819 __Pyx_AddTraceback("bintrees.qavltree.cAVLTree.__cinit__", __pyx_clineno, __pyx_lineno, __pyx_filename); 820 __pyx_r = -1; 821 __pyx_L0:; 822 __Pyx_RefNannyFinishContext(); 823 return __pyx_r; 824} 825 826/* Python wrapper */ 827static void __pyx_pw_8bintrees_8qavltree_8cAVLTree_3__dealloc__(PyObject *__pyx_v_self); /*proto*/ 828static void __pyx_pw_8bintrees_8qavltree_8cAVLTree_3__dealloc__(PyObject *__pyx_v_self) { 829 __Pyx_RefNannyDeclarations 830 __Pyx_RefNannySetupContext("__dealloc__ (wrapper)", 0); 831 __pyx_pf_8bintrees_8qavltree_8cAVLTree_2__dealloc__(((struct __pyx_obj_8bintrees_8qavltree_cAVLTree *)__pyx_v_self)); 832 __Pyx_RefNannyFinishContext(); 833} 834 835/* "bintrees\qavltree.pyx":26 836 * self.update(items) 837 * 838 * def __dealloc__(self): # <<<<<<<<<<<<<< 839 * ct_delete_tree(self._root) 840 * 841 */ 842 843static void __pyx_pf_8bintrees_8qavltree_8cAVLTree_2__dealloc__(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self) { 844 __Pyx_RefNannyDeclarations 845 __Pyx_RefNannySetupContext("__dealloc__", 0); 846 847 /* "bintrees\qavltree.pyx":27 848 * 849 * def __dealloc__(self): 850 * ct_delete_tree(self._root) # <<<<<<<<<<<<<< 851 * 852 * @property 853 */ 854 ct_delete_tree(__pyx_v_self->_root); 855 856 __Pyx_RefNannyFinishContext(); 857} 858 859/* Python wrapper */ 860static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_5count(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 861static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_5count(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 862 PyObject *__pyx_r = 0; 863 __Pyx_RefNannyDeclarations 864 __Pyx_RefNannySetupContext("count (wrapper)", 0); 865 __pyx_r = __pyx_pf_8bintrees_8qavltree_8cAVLTree_4count(((struct __pyx_obj_8bintrees_8qavltree_cAVLTree *)__pyx_v_self)); 866 __Pyx_RefNannyFinishContext(); 867 return __pyx_r; 868} 869 870/* "bintrees\qavltree.pyx":30 871 * 872 * @property 873 * def count(self): # <<<<<<<<<<<<<< 874 * return self._count 875 * 876 */ 877 878static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_4count(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self) { 879 PyObject *__pyx_r = NULL; 880 __Pyx_RefNannyDeclarations 881 PyObject *__pyx_t_1 = NULL; 882 int __pyx_lineno = 0; 883 const char *__pyx_filename = NULL; 884 int __pyx_clineno = 0; 885 __Pyx_RefNannySetupContext("count", 0); 886 887 /* "bintrees\qavltree.pyx":31 888 * @property 889 * def count(self): 890 * return self._count # <<<<<<<<<<<<<< 891 * 892 * def __getstate__(self): 893 */ 894 __Pyx_XDECREF(__pyx_r); 895 __pyx_t_1 = PyInt_FromLong(__pyx_v_self->_count); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 31; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 896 __Pyx_GOTREF(__pyx_t_1); 897 __pyx_r = __pyx_t_1; 898 __pyx_t_1 = 0; 899 goto __pyx_L0; 900 901 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 902 goto __pyx_L0; 903 __pyx_L1_error:; 904 __Pyx_XDECREF(__pyx_t_1); 905 __Pyx_AddTraceback("bintrees.qavltree.cAVLTree.count", __pyx_clineno, __pyx_lineno, __pyx_filename); 906 __pyx_r = NULL; 907 __pyx_L0:; 908 __Pyx_XGIVEREF(__pyx_r); 909 __Pyx_RefNannyFinishContext(); 910 return __pyx_r; 911} 912 913/* Python wrapper */ 914static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_7__getstate__(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 915static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_7__getstate__(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 916 PyObject *__pyx_r = 0; 917 __Pyx_RefNannyDeclarations 918 __Pyx_RefNannySetupContext("__getstate__ (wrapper)", 0); 919 __pyx_r = __pyx_pf_8bintrees_8qavltree_8cAVLTree_6__getstate__(((struct __pyx_obj_8bintrees_8qavltree_cAVLTree *)__pyx_v_self)); 920 __Pyx_RefNannyFinishContext(); 921 return __pyx_r; 922} 923 924/* "bintrees\qavltree.pyx":33 925 * return self._count 926 * 927 * def __getstate__(self): # <<<<<<<<<<<<<< 928 * return dict(self.items()) 929 * 930 */ 931 932static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_6__getstate__(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self) { 933 PyObject *__pyx_r = NULL; 934 __Pyx_RefNannyDeclarations 935 PyObject *__pyx_t_1 = NULL; 936 PyObject *__pyx_t_2 = NULL; 937 int __pyx_lineno = 0; 938 const char *__pyx_filename = NULL; 939 int __pyx_clineno = 0; 940 __Pyx_RefNannySetupContext("__getstate__", 0); 941 942 /* "bintrees\qavltree.pyx":34 943 * 944 * def __getstate__(self): 945 * return dict(self.items()) # <<<<<<<<<<<<<< 946 * 947 * def __setstate__(self, state): 948 */ 949 __Pyx_XDECREF(__pyx_r); 950 __pyx_t_1 = PyObject_GetAttr(((PyObject *)__pyx_v_self), __pyx_n_s__items); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 34; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 951 __Pyx_GOTREF(__pyx_t_1); 952 __pyx_t_2 = PyObject_Call(__pyx_t_1, ((PyObject *)__pyx_empty_tuple), NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 34; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 953 __Pyx_GOTREF(__pyx_t_2); 954 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 955 __pyx_t_1 = PyTuple_New(1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 34; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 956 __Pyx_GOTREF(__pyx_t_1); 957 PyTuple_SET_ITEM(__pyx_t_1, 0, __pyx_t_2); 958 __Pyx_GIVEREF(__pyx_t_2); 959 __pyx_t_2 = 0; 960 __pyx_t_2 = PyObject_Call(((PyObject *)((PyObject*)(&PyDict_Type))), ((PyObject *)__pyx_t_1), NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 34; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 961 __Pyx_GOTREF(__pyx_t_2); 962 __Pyx_DECREF(((PyObject *)__pyx_t_1)); __pyx_t_1 = 0; 963 __pyx_r = __pyx_t_2; 964 __pyx_t_2 = 0; 965 goto __pyx_L0; 966 967 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 968 goto __pyx_L0; 969 __pyx_L1_error:; 970 __Pyx_XDECREF(__pyx_t_1); 971 __Pyx_XDECREF(__pyx_t_2); 972 __Pyx_AddTraceback("bintrees.qavltree.cAVLTree.__getstate__", __pyx_clineno, __pyx_lineno, __pyx_filename); 973 __pyx_r = NULL; 974 __pyx_L0:; 975 __Pyx_XGIVEREF(__pyx_r); 976 __Pyx_RefNannyFinishContext(); 977 return __pyx_r; 978} 979 980/* Python wrapper */ 981static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_9__setstate__(PyObject *__pyx_v_self, PyObject *__pyx_v_state); /*proto*/ 982static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_9__setstate__(PyObject *__pyx_v_self, PyObject *__pyx_v_state) { 983 PyObject *__pyx_r = 0; 984 __Pyx_RefNannyDeclarations 985 __Pyx_RefNannySetupContext("__setstate__ (wrapper)", 0); 986 __pyx_r = __pyx_pf_8bintrees_8qavltree_8cAVLTree_8__setstate__(((struct __pyx_obj_8bintrees_8qavltree_cAVLTree *)__pyx_v_self), ((PyObject *)__pyx_v_state)); 987 __Pyx_RefNannyFinishContext(); 988 return __pyx_r; 989} 990 991/* "bintrees\qavltree.pyx":36 992 * return dict(self.items()) 993 * 994 * def __setstate__(self, state): # <<<<<<<<<<<<<< 995 * self.update(state) 996 * 997 */ 998 999static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_8__setstate__(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self, PyObject *__pyx_v_state) { 1000 PyObject *__pyx_r = NULL; 1001 __Pyx_RefNannyDeclarations 1002 PyObject *__pyx_t_1 = NULL; 1003 PyObject *__pyx_t_2 = NULL; 1004 PyObject *__pyx_t_3 = NULL; 1005 int __pyx_lineno = 0; 1006 const char *__pyx_filename = NULL; 1007 int __pyx_clineno = 0; 1008 __Pyx_RefNannySetupContext("__setstate__", 0); 1009 1010 /* "bintrees\qavltree.pyx":37 1011 * 1012 * def __setstate__(self, state): 1013 * self.update(state) # <<<<<<<<<<<<<< 1014 * 1015 * def clear(self): 1016 */ 1017 __pyx_t_1 = PyObject_GetAttr(((PyObject *)__pyx_v_self), __pyx_n_s__update); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 37; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1018 __Pyx_GOTREF(__pyx_t_1); 1019 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 37; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1020 __Pyx_GOTREF(__pyx_t_2); 1021 __Pyx_INCREF(__pyx_v_state); 1022 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_v_state); 1023 __Pyx_GIVEREF(__pyx_v_state); 1024 __pyx_t_3 = PyObject_Call(__pyx_t_1, ((PyObject *)__pyx_t_2), NULL); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 37; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1025 __Pyx_GOTREF(__pyx_t_3); 1026 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 1027 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 1028 __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; 1029 1030 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1031 goto __pyx_L0; 1032 __pyx_L1_error:; 1033 __Pyx_XDECREF(__pyx_t_1); 1034 __Pyx_XDECREF(__pyx_t_2); 1035 __Pyx_XDECREF(__pyx_t_3); 1036 __Pyx_AddTraceback("bintrees.qavltree.cAVLTree.__setstate__", __pyx_clineno, __pyx_lineno, __pyx_filename); 1037 __pyx_r = NULL; 1038 __pyx_L0:; 1039 __Pyx_XGIVEREF(__pyx_r); 1040 __Pyx_RefNannyFinishContext(); 1041 return __pyx_r; 1042} 1043 1044/* Python wrapper */ 1045static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_11clear(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1046static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_11clear(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1047 PyObject *__pyx_r = 0; 1048 __Pyx_RefNannyDeclarations 1049 __Pyx_RefNannySetupContext("clear (wrapper)", 0); 1050 __pyx_r = __pyx_pf_8bintrees_8qavltree_8cAVLTree_10clear(((struct __pyx_obj_8bintrees_8qavltree_cAVLTree *)__pyx_v_self)); 1051 __Pyx_RefNannyFinishContext(); 1052 return __pyx_r; 1053} 1054 1055/* "bintrees\qavltree.pyx":39 1056 * self.update(state) 1057 * 1058 * def clear(self): # <<<<<<<<<<<<<< 1059 * ct_delete_tree(self._root) 1060 * self._count = 0 1061 */ 1062 1063static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_10clear(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self) { 1064 PyObject *__pyx_r = NULL; 1065 __Pyx_RefNannyDeclarations 1066 __Pyx_RefNannySetupContext("clear", 0); 1067 1068 /* "bintrees\qavltree.pyx":40 1069 * 1070 * def clear(self): 1071 * ct_delete_tree(self._root) # <<<<<<<<<<<<<< 1072 * self._count = 0 1073 * self._root = NULL 1074 */ 1075 ct_delete_tree(__pyx_v_self->_root); 1076 1077 /* "bintrees\qavltree.pyx":41 1078 * def clear(self): 1079 * ct_delete_tree(self._root) 1080 * self._count = 0 # <<<<<<<<<<<<<< 1081 * self._root = NULL 1082 * 1083 */ 1084 __pyx_v_self->_count = 0; 1085 1086 /* "bintrees\qavltree.pyx":42 1087 * ct_delete_tree(self._root) 1088 * self._count = 0 1089 * self._root = NULL # <<<<<<<<<<<<<< 1090 * 1091 * def get_value(self, key): 1092 */ 1093 __pyx_v_self->_root = NULL; 1094 1095 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1096 __Pyx_XGIVEREF(__pyx_r); 1097 __Pyx_RefNannyFinishContext(); 1098 return __pyx_r; 1099} 1100 1101/* Python wrapper */ 1102static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_13get_value(PyObject *__pyx_v_self, PyObject *__pyx_v_key); /*proto*/ 1103static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_13get_value(PyObject *__pyx_v_self, PyObject *__pyx_v_key) { 1104 PyObject *__pyx_r = 0; 1105 __Pyx_RefNannyDeclarations 1106 __Pyx_RefNannySetupContext("get_value (wrapper)", 0); 1107 __pyx_r = __pyx_pf_8bintrees_8qavltree_8cAVLTree_12get_value(((struct __pyx_obj_8bintrees_8qavltree_cAVLTree *)__pyx_v_self), ((PyObject *)__pyx_v_key)); 1108 __Pyx_RefNannyFinishContext(); 1109 return __pyx_r; 1110} 1111 1112/* "bintrees\qavltree.pyx":44 1113 * self._root = NULL 1114 * 1115 * def get_value(self, key): # <<<<<<<<<<<<<< 1116 * result = <object> ct_get_item(self._root, key) 1117 * if result is None: 1118 */ 1119 1120static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_12get_value(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self, PyObject *__pyx_v_key) { 1121 PyObject *__pyx_v_result = NULL; 1122 PyObject *__pyx_r = NULL; 1123 __Pyx_RefNannyDeclarations 1124 PyObject *__pyx_t_1; 1125 int __pyx_t_2; 1126 PyObject *__pyx_t_3 = NULL; 1127 PyObject *__pyx_t_4 = NULL; 1128 int __pyx_lineno = 0; 1129 const char *__pyx_filename = NULL; 1130 int __pyx_clineno = 0; 1131 __Pyx_RefNannySetupContext("get_value", 0); 1132 1133 /* "bintrees\qavltree.pyx":45 1134 * 1135 * def get_value(self, key): 1136 * result = <object> ct_get_item(self._root, key) # <<<<<<<<<<<<<< 1137 * if result is None: 1138 * raise KeyError(key) 1139 */ 1140 __pyx_t_1 = ct_get_item(__pyx_v_self->_root, __pyx_v_key); 1141 __Pyx_INCREF(((PyObject *)__pyx_t_1)); 1142 __pyx_v_result = ((PyObject *)__pyx_t_1); 1143 1144 /* "bintrees\qavltree.pyx":46 1145 * def get_value(self, key): 1146 * result = <object> ct_get_item(self._root, key) 1147 * if result is None: # <<<<<<<<<<<<<< 1148 * raise KeyError(key) 1149 * else: 1150 */ 1151 __pyx_t_2 = (__pyx_v_result == Py_None); 1152 if (__pyx_t_2) { 1153 1154 /* "bintrees\qavltree.pyx":47 1155 * result = <object> ct_get_item(self._root, key) 1156 * if result is None: 1157 * raise KeyError(key) # <<<<<<<<<<<<<< 1158 * else: 1159 * return result[1] 1160 */ 1161 __pyx_t_3 = PyTuple_New(1); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1162 __Pyx_GOTREF(__pyx_t_3); 1163 __Pyx_INCREF(__pyx_v_key); 1164 PyTuple_SET_ITEM(__pyx_t_3, 0, __pyx_v_key); 1165 __Pyx_GIVEREF(__pyx_v_key); 1166 __pyx_t_4 = PyObject_Call(__pyx_builtin_KeyError, ((PyObject *)__pyx_t_3), NULL); if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1167 __Pyx_GOTREF(__pyx_t_4); 1168 __Pyx_DECREF(((PyObject *)__pyx_t_3)); __pyx_t_3 = 0; 1169 __Pyx_Raise(__pyx_t_4, 0, 0, 0); 1170 __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0; 1171 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1172 goto __pyx_L3; 1173 } 1174 /*else*/ { 1175 1176 /* "bintrees\qavltree.pyx":49 1177 * raise KeyError(key) 1178 * else: 1179 * return result[1] # <<<<<<<<<<<<<< 1180 * 1181 * def get_walker(self): 1182 */ 1183 __Pyx_XDECREF(__pyx_r); 1184 __pyx_t_4 = __Pyx_GetItemInt(__pyx_v_result, 1, sizeof(long), PyInt_FromLong); if (!__pyx_t_4) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 49; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1185 __Pyx_GOTREF(__pyx_t_4); 1186 __pyx_r = __pyx_t_4; 1187 __pyx_t_4 = 0; 1188 goto __pyx_L0; 1189 } 1190 __pyx_L3:; 1191 1192 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1193 goto __pyx_L0; 1194 __pyx_L1_error:; 1195 __Pyx_XDECREF(__pyx_t_3); 1196 __Pyx_XDECREF(__pyx_t_4); 1197 __Pyx_AddTraceback("bintrees.qavltree.cAVLTree.get_value", __pyx_clineno, __pyx_lineno, __pyx_filename); 1198 __pyx_r = NULL; 1199 __pyx_L0:; 1200 __Pyx_XDECREF(__pyx_v_result); 1201 __Pyx_XGIVEREF(__pyx_r); 1202 __Pyx_RefNannyFinishContext(); 1203 return __pyx_r; 1204} 1205 1206/* Python wrapper */ 1207static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_15get_walker(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1208static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_15get_walker(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1209 PyObject *__pyx_r = 0; 1210 __Pyx_RefNannyDeclarations 1211 __Pyx_RefNannySetupContext("get_walker (wrapper)", 0); 1212 __pyx_r = __pyx_pf_8bintrees_8qavltree_8cAVLTree_14get_walker(((struct __pyx_obj_8bintrees_8qavltree_cAVLTree *)__pyx_v_self)); 1213 __Pyx_RefNannyFinishContext(); 1214 return __pyx_r; 1215} 1216 1217/* "bintrees\qavltree.pyx":51 1218 * return result[1] 1219 * 1220 * def get_walker(self): # <<<<<<<<<<<<<< 1221 * cdef cWalker walker 1222 * walker = cWalker() 1223 */ 1224 1225static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_14get_walker(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self) { 1226 struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_walker = 0; 1227 PyObject *__pyx_r = NULL; 1228 __Pyx_RefNannyDeclarations 1229 PyObject *__pyx_t_1 = NULL; 1230 int __pyx_lineno = 0; 1231 const char *__pyx_filename = NULL; 1232 int __pyx_clineno = 0; 1233 __Pyx_RefNannySetupContext("get_walker", 0); 1234 1235 /* "bintrees\qavltree.pyx":53 1236 * def get_walker(self): 1237 * cdef cWalker walker 1238 * walker = cWalker() # <<<<<<<<<<<<<< 1239 * walker.set_tree(self._root) 1240 * return walker 1241 */ 1242 __pyx_t_1 = PyObject_Call(((PyObject *)((PyObject*)__pyx_ptype_8bintrees_7cwalker_cWalker)), ((PyObject *)__pyx_empty_tuple), NULL); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 53; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1243 __Pyx_GOTREF(__pyx_t_1); 1244 __pyx_v_walker = ((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_t_1); 1245 __pyx_t_1 = 0; 1246 1247 /* "bintrees\qavltree.pyx":54 1248 * cdef cWalker walker 1249 * walker = cWalker() 1250 * walker.set_tree(self._root) # <<<<<<<<<<<<<< 1251 * return walker 1252 * 1253 */ 1254 ((struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker *)__pyx_v_walker->__pyx_vtab)->set_tree(__pyx_v_walker, __pyx_v_self->_root); 1255 1256 /* "bintrees\qavltree.pyx":55 1257 * walker = cWalker() 1258 * walker.set_tree(self._root) 1259 * return walker # <<<<<<<<<<<<<< 1260 * 1261 * def insert(self, key, value): 1262 */ 1263 __Pyx_XDECREF(__pyx_r); 1264 __Pyx_INCREF(((PyObject *)__pyx_v_walker)); 1265 __pyx_r = ((PyObject *)__pyx_v_walker); 1266 goto __pyx_L0; 1267 1268 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1269 goto __pyx_L0; 1270 __pyx_L1_error:; 1271 __Pyx_XDECREF(__pyx_t_1); 1272 __Pyx_AddTraceback("bintrees.qavltree.cAVLTree.get_walker", __pyx_clineno, __pyx_lineno, __pyx_filename); 1273 __pyx_r = NULL; 1274 __pyx_L0:; 1275 __Pyx_XDECREF((PyObject *)__pyx_v_walker); 1276 __Pyx_XGIVEREF(__pyx_r); 1277 __Pyx_RefNannyFinishContext(); 1278 return __pyx_r; 1279} 1280 1281/* Python wrapper */ 1282static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_17insert(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/ 1283static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_17insert(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds) { 1284 PyObject *__pyx_v_key = 0; 1285 PyObject *__pyx_v_value = 0; 1286 PyObject *__pyx_r = 0; 1287 __Pyx_RefNannyDeclarations 1288 __Pyx_RefNannySetupContext("insert (wrapper)", 0); 1289 { 1290 static PyObject **__pyx_pyargnames[] = {&__pyx_n_s__key,&__pyx_n_s__value,0}; 1291 PyObject* values[2] = {0,0}; 1292 if (unlikely(__pyx_kwds)) { 1293 Py_ssize_t kw_args; 1294 const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args); 1295 switch (pos_args) { 1296 case 2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1); 1297 case 1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0); 1298 case 0: break; 1299 default: goto __pyx_L5_argtuple_error; 1300 } 1301 kw_args = PyDict_Size(__pyx_kwds); 1302 switch (pos_args) { 1303 case 0: 1304 if (likely((values[0] = PyDict_GetItem(__pyx_kwds, __pyx_n_s__key)) != 0)) kw_args--; 1305 else goto __pyx_L5_argtuple_error; 1306 case 1: 1307 if (likely((values[1] = PyDict_GetItem(__pyx_kwds, __pyx_n_s__value)) != 0)) kw_args--; 1308 else { 1309 __Pyx_RaiseArgtupleInvalid("insert", 1, 2, 2, 1); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 57; __pyx_clineno = __LINE__; goto __pyx_L3_error;} 1310 } 1311 } 1312 if (unlikely(kw_args > 0)) { 1313 if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "insert") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 57; __pyx_clineno = __LINE__; goto __pyx_L3_error;} 1314 } 1315 } else if (PyTuple_GET_SIZE(__pyx_args) != 2) { 1316 goto __pyx_L5_argtuple_error; 1317 } else { 1318 values[0] = PyTuple_GET_ITEM(__pyx_args, 0); 1319 values[1] = PyTuple_GET_ITEM(__pyx_args, 1); 1320 } 1321 __pyx_v_key = values[0]; 1322 __pyx_v_value = values[1]; 1323 } 1324 goto __pyx_L4_argument_unpacking_done; 1325 __pyx_L5_argtuple_error:; 1326 __Pyx_RaiseArgtupleInvalid("insert", 1, 2, 2, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 57; __pyx_clineno = __LINE__; goto __pyx_L3_error;} 1327 __pyx_L3_error:; 1328 __Pyx_AddTraceback("bintrees.qavltree.cAVLTree.insert", __pyx_clineno, __pyx_lineno, __pyx_filename); 1329 __Pyx_RefNannyFinishContext(); 1330 return NULL; 1331 __pyx_L4_argument_unpacking_done:; 1332 __pyx_r = __pyx_pf_8bintrees_8qavltree_8cAVLTree_16insert(((struct __pyx_obj_8bintrees_8qavltree_cAVLTree *)__pyx_v_self), __pyx_v_key, __pyx_v_value); 1333 __Pyx_RefNannyFinishContext(); 1334 return __pyx_r; 1335} 1336 1337/* "bintrees\qavltree.pyx":57 1338 * return walker 1339 * 1340 * def insert(self, key, value): # <<<<<<<<<<<<<< 1341 * res = avl_insert(&self._root, key, value) 1342 * if res < 0: 1343 */ 1344 1345static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_16insert(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self, PyObject *__pyx_v_key, PyObject *__pyx_v_value) { 1346 PyObject *__pyx_v_res = NULL; 1347 PyObject *__pyx_r = NULL; 1348 __Pyx_RefNannyDeclarations 1349 PyObject *__pyx_t_1 = NULL; 1350 int __pyx_t_2; 1351 PyObject *__pyx_t_3 = NULL; 1352 int __pyx_t_4; 1353 int __pyx_lineno = 0; 1354 const char *__pyx_filename = NULL; 1355 int __pyx_clineno = 0; 1356 __Pyx_RefNannySetupContext("insert", 0); 1357 1358 /* "bintrees\qavltree.pyx":58 1359 * 1360 * def insert(self, key, value): 1361 * res = avl_insert(&self._root, key, value) # <<<<<<<<<<<<<< 1362 * if res < 0: 1363 * raise MemoryError('Can not allocate memory for node structure.') 1364 */ 1365 __pyx_t_1 = PyInt_FromLong(avl_insert((&__pyx_v_self->_root), __pyx_v_key, __pyx_v_value)); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 58; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1366 __Pyx_GOTREF(__pyx_t_1); 1367 __pyx_v_res = __pyx_t_1; 1368 __pyx_t_1 = 0; 1369 1370 /* "bintrees\qavltree.pyx":59 1371 * def insert(self, key, value): 1372 * res = avl_insert(&self._root, key, value) 1373 * if res < 0: # <<<<<<<<<<<<<< 1374 * raise MemoryError('Can not allocate memory for node structure.') 1375 * else: 1376 */ 1377 __pyx_t_1 = PyObject_RichCompare(__pyx_v_res, __pyx_int_0, Py_LT); __Pyx_XGOTREF(__pyx_t_1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 59; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1378 __pyx_t_2 = __Pyx_PyObject_IsTrue(__pyx_t_1); if (unlikely(__pyx_t_2 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 59; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1379 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 1380 if (__pyx_t_2) { 1381 1382 /* "bintrees\qavltree.pyx":60 1383 * res = avl_insert(&self._root, key, value) 1384 * if res < 0: 1385 * raise MemoryError('Can not allocate memory for node structure.') # <<<<<<<<<<<<<< 1386 * else: 1387 * self._count += res 1388 */ 1389 __pyx_t_1 = PyObject_Call(__pyx_builtin_MemoryError, ((PyObject *)__pyx_k_tuple_2), NULL); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1390 __Pyx_GOTREF(__pyx_t_1); 1391 __Pyx_Raise(__pyx_t_1, 0, 0, 0); 1392 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 1393 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1394 goto __pyx_L3; 1395 } 1396 /*else*/ { 1397 1398 /* "bintrees\qavltree.pyx":62 1399 * raise MemoryError('Can not allocate memory for node structure.') 1400 * else: 1401 * self._count += res # <<<<<<<<<<<<<< 1402 * 1403 * def remove(self, key): 1404 */ 1405 __pyx_t_1 = PyInt_FromLong(__pyx_v_self->_count); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1406 __Pyx_GOTREF(__pyx_t_1); 1407 __pyx_t_3 = PyNumber_InPlaceAdd(__pyx_t_1, __pyx_v_res); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1408 __Pyx_GOTREF(__pyx_t_3); 1409 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 1410 __pyx_t_4 = __Pyx_PyInt_AsInt(__pyx_t_3); if (unlikely((__pyx_t_4 == (int)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1411 __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; 1412 __pyx_v_self->_count = __pyx_t_4; 1413 } 1414 __pyx_L3:; 1415 1416 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1417 goto __pyx_L0; 1418 __pyx_L1_error:; 1419 __Pyx_XDECREF(__pyx_t_1); 1420 __Pyx_XDECREF(__pyx_t_3); 1421 __Pyx_AddTraceback("bintrees.qavltree.cAVLTree.insert", __pyx_clineno, __pyx_lineno, __pyx_filename); 1422 __pyx_r = NULL; 1423 __pyx_L0:; 1424 __Pyx_XDECREF(__pyx_v_res); 1425 __Pyx_XGIVEREF(__pyx_r); 1426 __Pyx_RefNannyFinishContext(); 1427 return __pyx_r; 1428} 1429 1430/* Python wrapper */ 1431static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_19remove(PyObject *__pyx_v_self, PyObject *__pyx_v_key); /*proto*/ 1432static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_19remove(PyObject *__pyx_v_self, PyObject *__pyx_v_key) { 1433 PyObject *__pyx_r = 0; 1434 __Pyx_RefNannyDeclarations 1435 __Pyx_RefNannySetupContext("remove (wrapper)", 0); 1436 __pyx_r = __pyx_pf_8bintrees_8qavltree_8cAVLTree_18remove(((struct __pyx_obj_8bintrees_8qavltree_cAVLTree *)__pyx_v_self), ((PyObject *)__pyx_v_key)); 1437 __Pyx_RefNannyFinishContext(); 1438 return __pyx_r; 1439} 1440 1441/* "bintrees\qavltree.pyx":64 1442 * self._count += res 1443 * 1444 * def remove(self, key): # <<<<<<<<<<<<<< 1445 * cdef int result 1446 * result = avl_remove(&self._root, key) 1447 */ 1448 1449static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_18remove(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self, PyObject *__pyx_v_key) { 1450 int __pyx_v_result; 1451 PyObject *__pyx_r = NULL; 1452 __Pyx_RefNannyDeclarations 1453 int __pyx_t_1; 1454 PyObject *__pyx_t_2 = NULL; 1455 PyObject *__pyx_t_3 = NULL; 1456 int __pyx_lineno = 0; 1457 const char *__pyx_filename = NULL; 1458 int __pyx_clineno = 0; 1459 __Pyx_RefNannySetupContext("remove", 0); 1460 1461 /* "bintrees\qavltree.pyx":66 1462 * def remove(self, key): 1463 * cdef int result 1464 * result = avl_remove(&self._root, key) # <<<<<<<<<<<<<< 1465 * if result == 0: 1466 * raise KeyError(str(key)) 1467 */ 1468 __pyx_v_result = avl_remove((&__pyx_v_self->_root), __pyx_v_key); 1469 1470 /* "bintrees\qavltree.pyx":67 1471 * cdef int result 1472 * result = avl_remove(&self._root, key) 1473 * if result == 0: # <<<<<<<<<<<<<< 1474 * raise KeyError(str(key)) 1475 * else: 1476 */ 1477 __pyx_t_1 = (__pyx_v_result == 0); 1478 if (__pyx_t_1) { 1479 1480 /* "bintrees\qavltree.pyx":68 1481 * result = avl_remove(&self._root, key) 1482 * if result == 0: 1483 * raise KeyError(str(key)) # <<<<<<<<<<<<<< 1484 * else: 1485 * self._count -= 1 1486 */ 1487 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 68; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1488 __Pyx_GOTREF(__pyx_t_2); 1489 __Pyx_INCREF(__pyx_v_key); 1490 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_v_key); 1491 __Pyx_GIVEREF(__pyx_v_key); 1492 __pyx_t_3 = PyObject_Call(((PyObject *)((PyObject*)(&PyString_Type))), ((PyObject *)__pyx_t_2), NULL); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 68; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1493 __Pyx_GOTREF(__pyx_t_3); 1494 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 1495 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 68; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1496 __Pyx_GOTREF(__pyx_t_2); 1497 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_t_3); 1498 __Pyx_GIVEREF(__pyx_t_3); 1499 __pyx_t_3 = 0; 1500 __pyx_t_3 = PyObject_Call(__pyx_builtin_KeyError, ((PyObject *)__pyx_t_2), NULL); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 68; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1501 __Pyx_GOTREF(__pyx_t_3); 1502 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 1503 __Pyx_Raise(__pyx_t_3, 0, 0, 0); 1504 __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; 1505 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 68; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1506 goto __pyx_L3; 1507 } 1508 /*else*/ { 1509 1510 /* "bintrees\qavltree.pyx":70 1511 * raise KeyError(str(key)) 1512 * else: 1513 * self._count -= 1 # <<<<<<<<<<<<<< 1514 * 1515 * def max_item(self): 1516 */ 1517 __pyx_v_self->_count = (__pyx_v_self->_count - 1); 1518 } 1519 __pyx_L3:; 1520 1521 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1522 goto __pyx_L0; 1523 __pyx_L1_error:; 1524 __Pyx_XDECREF(__pyx_t_2); 1525 __Pyx_XDECREF(__pyx_t_3); 1526 __Pyx_AddTraceback("bintrees.qavltree.cAVLTree.remove", __pyx_clineno, __pyx_lineno, __pyx_filename); 1527 __pyx_r = NULL; 1528 __pyx_L0:; 1529 __Pyx_XGIVEREF(__pyx_r); 1530 __Pyx_RefNannyFinishContext(); 1531 return __pyx_r; 1532} 1533 1534/* Python wrapper */ 1535static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_21max_item(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1536static char __pyx_doc_8bintrees_8qavltree_8cAVLTree_20max_item[] = " Get item with max key of tree, raises ValueError if tree is empty. "; 1537static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_21max_item(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1538 PyObject *__pyx_r = 0; 1539 __Pyx_RefNannyDeclarations 1540 __Pyx_RefNannySetupContext("max_item (wrapper)", 0); 1541 __pyx_r = __pyx_pf_8bintrees_8qavltree_8cAVLTree_20max_item(((struct __pyx_obj_8bintrees_8qavltree_cAVLTree *)__pyx_v_self)); 1542 __Pyx_RefNannyFinishContext(); 1543 return __pyx_r; 1544} 1545 1546/* "bintrees\qavltree.pyx":72 1547 * self._count -= 1 1548 * 1549 * def max_item(self): # <<<<<<<<<<<<<< 1550 * """ Get item with max key of tree, raises ValueError if tree is empty. """ 1551 * cdef node_t *node 1552 */ 1553 1554static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_20max_item(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self) { 1555 node_t *__pyx_v_node; 1556 PyObject *__pyx_r = NULL; 1557 __Pyx_RefNannyDeclarations 1558 int __pyx_t_1; 1559 PyObject *__pyx_t_2 = NULL; 1560 int __pyx_lineno = 0; 1561 const char *__pyx_filename = NULL; 1562 int __pyx_clineno = 0; 1563 __Pyx_RefNannySetupContext("max_item", 0); 1564 1565 /* "bintrees\qavltree.pyx":75 1566 * """ Get item with max key of tree, raises ValueError if tree is empty. """ 1567 * cdef node_t *node 1568 * node = ct_max_node(self._root) # <<<<<<<<<<<<<< 1569 * if node == NULL: # root is None 1570 * raise ValueError("Tree is empty") 1571 */ 1572 __pyx_v_node = ct_max_node(__pyx_v_self->_root); 1573 1574 /* "bintrees\qavltree.pyx":76 1575 * cdef node_t *node 1576 * node = ct_max_node(self._root) 1577 * if node == NULL: # root is None # <<<<<<<<<<<<<< 1578 * raise ValueError("Tree is empty") 1579 * return (<object>node.key, <object>node.value) 1580 */ 1581 __pyx_t_1 = (__pyx_v_node == NULL); 1582 if (__pyx_t_1) { 1583 1584 /* "bintrees\qavltree.pyx":77 1585 * node = ct_max_node(self._root) 1586 * if node == NULL: # root is None 1587 * raise ValueError("Tree is empty") # <<<<<<<<<<<<<< 1588 * return (<object>node.key, <object>node.value) 1589 * 1590 */ 1591 __pyx_t_2 = PyObject_Call(__pyx_builtin_ValueError, ((PyObject *)__pyx_k_tuple_4), NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 77; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1592 __Pyx_GOTREF(__pyx_t_2); 1593 __Pyx_Raise(__pyx_t_2, 0, 0, 0); 1594 __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; 1595 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 77; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1596 goto __pyx_L3; 1597 } 1598 __pyx_L3:; 1599 1600 /* "bintrees\qavltree.pyx":78 1601 * if node == NULL: # root is None 1602 * raise ValueError("Tree is empty") 1603 * return (<object>node.key, <object>node.value) # <<<<<<<<<<<<<< 1604 * 1605 * def min_item(self): 1606 */ 1607 __Pyx_XDECREF(__pyx_r); 1608 __pyx_t_2 = PyTuple_New(2); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 78; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1609 __Pyx_GOTREF(__pyx_t_2); 1610 __Pyx_INCREF(((PyObject *)__pyx_v_node->key)); 1611 PyTuple_SET_ITEM(__pyx_t_2, 0, ((PyObject *)__pyx_v_node->key)); 1612 __Pyx_GIVEREF(((PyObject *)__pyx_v_node->key)); 1613 __Pyx_INCREF(((PyObject *)__pyx_v_node->value)); 1614 PyTuple_SET_ITEM(__pyx_t_2, 1, ((PyObject *)__pyx_v_node->value)); 1615 __Pyx_GIVEREF(((PyObject *)__pyx_v_node->value)); 1616 __pyx_r = ((PyObject *)__pyx_t_2); 1617 __pyx_t_2 = 0; 1618 goto __pyx_L0; 1619 1620 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1621 goto __pyx_L0; 1622 __pyx_L1_error:; 1623 __Pyx_XDECREF(__pyx_t_2); 1624 __Pyx_AddTraceback("bintrees.qavltree.cAVLTree.max_item", __pyx_clineno, __pyx_lineno, __pyx_filename); 1625 __pyx_r = NULL; 1626 __pyx_L0:; 1627 __Pyx_XGIVEREF(__pyx_r); 1628 __Pyx_RefNannyFinishContext(); 1629 return __pyx_r; 1630} 1631 1632/* Python wrapper */ 1633static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_23min_item(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1634static char __pyx_doc_8bintrees_8qavltree_8cAVLTree_22min_item[] = " Get item with min key of tree, raises ValueError if tree is empty. "; 1635static PyObject *__pyx_pw_8bintrees_8qavltree_8cAVLTree_23min_item(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1636 PyObject *__pyx_r = 0; 1637 __Pyx_RefNannyDeclarations 1638 __Pyx_RefNannySetupContext("min_item (wrapper)", 0); 1639 __pyx_r = __pyx_pf_8bintrees_8qavltree_8cAVLTree_22min_item(((struct __pyx_obj_8bintrees_8qavltree_cAVLTree *)__pyx_v_self)); 1640 __Pyx_RefNannyFinishContext(); 1641 return __pyx_r; 1642} 1643 1644/* "bintrees\qavltree.pyx":80 1645 * return (<object>node.key, <object>node.value) 1646 * 1647 * def min_item(self): # <<<<<<<<<<<<<< 1648 * """ Get item with min key of tree, raises ValueError if tree is empty. """ 1649 * cdef node_t *node 1650 */ 1651 1652static PyObject *__pyx_pf_8bintrees_8qavltree_8cAVLTree_22min_item(struct __pyx_obj_8bintrees_8qavltree_cAVLTree *__pyx_v_self) { 1653 node_t *__pyx_v_node; 1654 PyObject *__pyx_r = NULL; 1655 __Pyx_RefNannyDeclarations 1656 int __pyx_t_1; 1657 PyObject *__pyx_t_2 = NULL; 1658 int __pyx_lineno = 0; 1659 const char *__pyx_filename = NULL; 1660 int __pyx_clineno = 0; 1661 __Pyx_RefNannySetupContext("min_item", 0); 1662 1663 /* "bintrees\qavltree.pyx":83 1664 * """ Get item with min key of tree, raises ValueError if tree is empty. """ 1665 * cdef node_t *node 1666 * node = ct_min_node(self._root) # <<<<<<<<<<<<<< 1667 * if node == NULL: # root is None 1668 * raise ValueError("Tree is empty") 1669 */ 1670 __pyx_v_node = ct_min_node(__pyx_v_self->_root); 1671 1672 /* "bintrees\qavltree.pyx":84 1673 * cdef node_t *node 1674 * node = ct_min_node(self._root) 1675 * if node == NULL: # root is None # <<<<<<<<<<<<<< 1676 * raise ValueError("Tree is empty") 1677 * return (<object>node.key, <object>node.value) 1678 */ 1679 __pyx_t_1 = (__pyx_v_node == NULL); 1680 if (__pyx_t_1) { 1681 1682 /* "bintrees\qavltree.pyx":85 1683 * node = ct_min_node(self._root) 1684 * if node == NULL: # root is None 1685 * raise ValueError("Tree is empty") # <<<<<<<<<<<<<< 1686 * return (<object>node.key, <object>node.value) 1687 * 1688 */ 1689 __pyx_t_2 = PyObject_Call(__pyx_builtin_ValueError, ((PyObject *)__pyx_k_tuple_5), NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 85; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1690 __Pyx_GOTREF(__pyx_t_2); 1691 __Pyx_Raise(__pyx_t_2, 0, 0, 0); 1692 __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; 1693 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 85; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1694 goto __pyx_L3; 1695 } 1696 __pyx_L3:; 1697 1698 /* "bintrees\qavltree.pyx":86 1699 * if node == NULL: # root is None 1700 * raise ValueError("Tree is empty") 1701 * return (<object>node.key, <object>node.value) # <<<<<<<<<<<<<< 1702 * 1703 */ 1704 __Pyx_XDECREF(__pyx_r); 1705 __pyx_t_2 = PyTuple_New(2); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 86; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1706 __Pyx_GOTREF(__pyx_t_2); 1707 __Pyx_INCREF(((PyObject *)__pyx_v_node->key)); 1708 PyTuple_SET_ITEM(__pyx_t_2, 0, ((PyObject *)__pyx_v_node->key)); 1709 __Pyx_GIVEREF(((PyObject *)__pyx_v_node->key)); 1710 __Pyx_INCREF(((PyObject *)__pyx_v_node->value)); 1711 PyTuple_SET_ITEM(__pyx_t_2, 1, ((PyObject *)__pyx_v_node->value)); 1712 __Pyx_GIVEREF(((PyObject *)__pyx_v_node->value)); 1713 __pyx_r = ((PyObject *)__pyx_t_2); 1714 __pyx_t_2 = 0; 1715 goto __pyx_L0; 1716 1717 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1718 goto __pyx_L0; 1719 __pyx_L1_error:; 1720 __Pyx_XDECREF(__pyx_t_2); 1721 __Pyx_AddTraceback("bintrees.qavltree.cAVLTree.min_item", __pyx_clineno, __pyx_lineno, __pyx_filename); 1722 __pyx_r = NULL; 1723 __pyx_L0:; 1724 __Pyx_XGIVEREF(__pyx_r); 1725 __Pyx_RefNannyFinishContext(); 1726 return __pyx_r; 1727} 1728 1729static PyObject *__pyx_tp_new_8bintrees_8qavltree_cAVLTree(PyTypeObject *t, PyObject *a, PyObject *k) { 1730 PyObject *o = (*t->tp_alloc)(t, 0); 1731 if (!o) return 0; 1732 if (__pyx_pw_8bintrees_8qavltree_8cAVLTree_1__cinit__(o, a, k) < 0) { 1733 Py_DECREF(o); o = 0; 1734 } 1735 return o; 1736} 1737 1738static void __pyx_tp_dealloc_8bintrees_8qavltree_cAVLTree(PyObject *o) { 1739 { 1740 PyObject *etype, *eval, *etb; 1741 PyErr_Fetch(&etype, &eval, &etb); 1742 ++Py_REFCNT(o); 1743 __pyx_pw_8bintrees_8qavltree_8cAVLTree_3__dealloc__(o); 1744 if (PyErr_Occurred()) PyErr_WriteUnraisable(o); 1745 --Py_REFCNT(o); 1746 PyErr_Restore(etype, eval, etb); 1747 } 1748 (*Py_TYPE(o)->tp_free)(o); 1749} 1750 1751static PyMethodDef __pyx_methods_8bintrees_8qavltree_cAVLTree[] = { 1752 {__Pyx_NAMESTR("count"), (PyCFunction)__pyx_pw_8bintrees_8qavltree_8cAVLTree_5count, METH_NOARGS, __Pyx_DOCSTR(0)}, 1753 {__Pyx_NAMESTR("__getstate__"), (PyCFunction)__pyx_pw_8bintrees_8qavltree_8cAVLTree_7__getstate__, METH_NOARGS, __Pyx_DOCSTR(0)}, 1754 {__Pyx_NAMESTR("__setstate__"), (PyCFunction)__pyx_pw_8bintrees_8qavltree_8cAVLTree_9__setstate__, METH_O, __Pyx_DOCSTR(0)}, 1755 {__Pyx_NAMESTR("clear"), (PyCFunction)__pyx_pw_8bintrees_8qavltree_8cAVLTree_11clear, METH_NOARGS, __Pyx_DOCSTR(0)}, 1756 {__Pyx_NAMESTR("get_value"), (PyCFunction)__pyx_pw_8bintrees_8qavltree_8cAVLTree_13get_value, METH_O, __Pyx_DOCSTR(0)}, 1757 {__Pyx_NAMESTR("get_walker"), (PyCFunction)__pyx_pw_8bintrees_8qavltree_8cAVLTree_15get_walker, METH_NOARGS, __Pyx_DOCSTR(0)}, 1758 {__Pyx_NAMESTR("insert"), (PyCFunction)__pyx_pw_8bintrees_8qavltree_8cAVLTree_17insert, METH_VARARGS|METH_KEYWORDS, __Pyx_DOCSTR(0)}, 1759 {__Pyx_NAMESTR("remove"), (PyCFunction)__pyx_pw_8bintrees_8qavltree_8cAVLTree_19remove, METH_O, __Pyx_DOCSTR(0)}, 1760 {__Pyx_NAMESTR("max_item"), (PyCFunction)__pyx_pw_8bintrees_8qavltree_8cAVLTree_21max_item, METH_NOARGS, __Pyx_DOCSTR(__pyx_doc_8bintrees_8qavltree_8cAVLTree_20max_item)}, 1761 {__Pyx_NAMESTR("min_item"), (PyCFunction)__pyx_pw_8bintrees_8qavltree_8cAVLTree_23min_item, METH_NOARGS, __Pyx_DOCSTR(__pyx_doc_8bintrees_8qavltree_8cAVLTree_22min_item)}, 1762 {0, 0, 0, 0} 1763}; 1764 1765static PyNumberMethods __pyx_tp_as_number_cAVLTree = { 1766 0, /*nb_add*/ 1767 0, /*nb_subtract*/ 1768 0, /*nb_multiply*/ 1769 #if PY_MAJOR_VERSION < 3 1770 0, /*nb_divide*/ 1771 #endif 1772 0, /*nb_remainder*/ 1773 0, /*nb_divmod*/ 1774 0, /*nb_power*/ 1775 0, /*nb_negative*/ 1776 0, /*nb_positive*/ 1777 0, /*nb_absolute*/ 1778 0, /*nb_nonzero*/ 1779 0, /*nb_invert*/ 1780 0, /*nb_lshift*/ 1781 0, /*nb_rshift*/ 1782 0, /*nb_and*/ 1783 0, /*nb_xor*/ 1784 0, /*nb_or*/ 1785 #if PY_MAJOR_VERSION < 3 1786 0, /*nb_coerce*/ 1787 #endif 1788 0, /*nb_int*/ 1789 #if PY_MAJOR_VERSION < 3 1790 0, /*nb_long*/ 1791 #else 1792 0, /*reserved*/ 1793 #endif 1794 0, /*nb_float*/ 1795 #if PY_MAJOR_VERSION < 3 1796 0, /*nb_oct*/ 1797 #endif 1798 #if PY_MAJOR_VERSION < 3 1799 0, /*nb_hex*/ 1800 #endif 1801 0, /*nb_inplace_add*/ 1802 0, /*nb_inplace_subtract*/ 1803 0, /*nb_inplace_multiply*/ 1804 #if PY_MAJOR_VERSION < 3 1805 0, /*nb_inplace_divide*/ 1806 #endif 1807 0, /*nb_inplace_remainder*/ 1808 0, /*nb_inplace_power*/ 1809 0, /*nb_inplace_lshift*/ 1810 0, /*nb_inplace_rshift*/ 1811 0, /*nb_inplace_and*/ 1812 0, /*nb_inplace_xor*/ 1813 0, /*nb_inplace_or*/ 1814 0, /*nb_floor_divide*/ 1815 0, /*nb_true_divide*/ 1816 0, /*nb_inplace_floor_divide*/ 1817 0, /*nb_inplace_true_divide*/ 1818 #if PY_VERSION_HEX >= 0x02050000 1819 0, /*nb_index*/ 1820 #endif 1821}; 1822 1823static PySequenceMethods __pyx_tp_as_sequence_cAVLTree = { 1824 0, /*sq_length*/ 1825 0, /*sq_concat*/ 1826 0, /*sq_repeat*/ 1827 0, /*sq_item*/ 1828 0, /*sq_slice*/ 1829 0, /*sq_ass_item*/ 1830 0, /*sq_ass_slice*/ 1831 0, /*sq_contains*/ 1832 0, /*sq_inplace_concat*/ 1833 0, /*sq_inplace_repeat*/ 1834}; 1835 1836static PyMappingMethods __pyx_tp_as_mapping_cAVLTree = { 1837 0, /*mp_length*/ 1838 0, /*mp_subscript*/ 1839 0, /*mp_ass_subscript*/ 1840}; 1841 1842static PyBufferProcs __pyx_tp_as_buffer_cAVLTree = { 1843 #if PY_MAJOR_VERSION < 3 1844 0, /*bf_getreadbuffer*/ 1845 #endif 1846 #if PY_MAJOR_VERSION < 3 1847 0, /*bf_getwritebuffer*/ 1848 #endif 1849 #if PY_MAJOR_VERSION < 3 1850 0, /*bf_getsegcount*/ 1851 #endif 1852 #if PY_MAJOR_VERSION < 3 1853 0, /*bf_getcharbuffer*/ 1854 #endif 1855 #if PY_VERSION_HEX >= 0x02060000 1856 0, /*bf_getbuffer*/ 1857 #endif 1858 #if PY_VERSION_HEX >= 0x02060000 1859 0, /*bf_releasebuffer*/ 1860 #endif 1861}; 1862 1863static PyTypeObject __pyx_type_8bintrees_8qavltree_cAVLTree = { 1864 PyVarObject_HEAD_INIT(0, 0) 1865 __Pyx_NAMESTR("bintrees.qavltree.cAVLTree"), /*tp_name*/ 1866 sizeof(struct __pyx_obj_8bintrees_8qavltree_cAVLTree), /*tp_basicsize*/ 1867 0, /*tp_itemsize*/ 1868 __pyx_tp_dealloc_8bintrees_8qavltree_cAVLTree, /*tp_dealloc*/ 1869 0, /*tp_print*/ 1870 0, /*tp_getattr*/ 1871 0, /*tp_setattr*/ 1872 #if PY_MAJOR_VERSION < 3 1873 0, /*tp_compare*/ 1874 #else 1875 0, /*reserved*/ 1876 #endif 1877 0, /*tp_repr*/ 1878 &__pyx_tp_as_number_cAVLTree, /*tp_as_number*/ 1879 &__pyx_tp_as_sequence_cAVLTree, /*tp_as_sequence*/ 1880 &__pyx_tp_as_mapping_cAVLTree, /*tp_as_mapping*/ 1881 0, /*tp_hash*/ 1882 0, /*tp_call*/ 1883 0, /*tp_str*/ 1884 0, /*tp_getattro*/ 1885 0, /*tp_setattro*/ 1886 &__pyx_tp_as_buffer_cAVLTree, /*tp_as_buffer*/ 1887 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_CHECKTYPES|Py_TPFLAGS_HAVE_NEWBUFFER|Py_TPFLAGS_BASETYPE, /*tp_flags*/ 1888 0, /*tp_doc*/ 1889 0, /*tp_traverse*/ 1890 0, /*tp_clear*/ 1891 0, /*tp_richcompare*/ 1892 0, /*tp_weaklistoffset*/ 1893 0, /*tp_iter*/ 1894 0, /*tp_iternext*/ 1895 __pyx_methods_8bintrees_8qavltree_cAVLTree, /*tp_methods*/ 1896 0, /*tp_members*/ 1897 0, /*tp_getset*/ 1898 0, /*tp_base*/ 1899 0, /*tp_dict*/ 1900 0, /*tp_descr_get*/ 1901 0, /*tp_descr_set*/ 1902 0, /*tp_dictoffset*/ 1903 0, /*tp_init*/ 1904 0, /*tp_alloc*/ 1905 __pyx_tp_new_8bintrees_8qavltree_cAVLTree, /*tp_new*/ 1906 0, /*tp_free*/ 1907 0, /*tp_is_gc*/ 1908 0, /*tp_bases*/ 1909 0, /*tp_mro*/ 1910 0, /*tp_cache*/ 1911 0, /*tp_subclasses*/ 1912 0, /*tp_weaklist*/ 1913 0, /*tp_del*/ 1914 #if PY_VERSION_HEX >= 0x02060000 1915 0, /*tp_version_tag*/ 1916 #endif 1917}; 1918 1919static PyMethodDef __pyx_methods[] = { 1920 {0, 0, 0, 0} 1921}; 1922 1923#if PY_MAJOR_VERSION >= 3 1924static struct PyModuleDef __pyx_moduledef = { 1925 PyModuleDef_HEAD_INIT, 1926 __Pyx_NAMESTR("qavltree"), 1927 0, /* m_doc */ 1928 -1, /* m_size */ 1929 __pyx_methods /* m_methods */, 1930 NULL, /* m_reload */ 1931 NULL, /* m_traverse */ 1932 NULL, /* m_clear */ 1933 NULL /* m_free */ 1934}; 1935#endif 1936 1937static __Pyx_StringTabEntry __pyx_string_tab[] = { 1938 {&__pyx_kp_s_1, __pyx_k_1, sizeof(__pyx_k_1), 0, 0, 1, 0}, 1939 {&__pyx_kp_s_3, __pyx_k_3, sizeof(__pyx_k_3), 0, 0, 1, 0}, 1940 {&__pyx_n_s__KeyError, __pyx_k__KeyError, sizeof(__pyx_k__KeyError), 0, 0, 1, 1}, 1941 {&__pyx_n_s__MemoryError, __pyx_k__MemoryError, sizeof(__pyx_k__MemoryError), 0, 0, 1, 1}, 1942 {&__pyx_n_s__ValueError, __pyx_k__ValueError, sizeof(__pyx_k__ValueError), 0, 0, 1, 1}, 1943 {&__pyx_n_s____all__, __pyx_k____all__, sizeof(__pyx_k____all__), 0, 0, 1, 1}, 1944 {&__pyx_n_s____main__, __pyx_k____main__, sizeof(__pyx_k____main__), 0, 0, 1, 1}, 1945 {&__pyx_n_s____test__, __pyx_k____test__, sizeof(__pyx_k____test__), 0, 0, 1, 1}, 1946 {&__pyx_n_s__cAVLTree, __pyx_k__cAVLTree, sizeof(__pyx_k__cAVLTree), 0, 0, 1, 1}, 1947 {&__pyx_n_s__cWalker, __pyx_k__cWalker, sizeof(__pyx_k__cWalker), 0, 0, 1, 1}, 1948 {&__pyx_n_s__count, __pyx_k__count, sizeof(__pyx_k__count), 0, 0, 1, 1}, 1949 {&__pyx_n_s__cwalker, __pyx_k__cwalker, sizeof(__pyx_k__cwalker), 0, 0, 1, 1}, 1950 {&__pyx_n_s__items, __pyx_k__items, sizeof(__pyx_k__items), 0, 0, 1, 1}, 1951 {&__pyx_n_s__key, __pyx_k__key, sizeof(__pyx_k__key), 0, 0, 1, 1}, 1952 {&__pyx_n_s__property, __pyx_k__property, sizeof(__pyx_k__property), 0, 0, 1, 1}, 1953 {&__pyx_n_s__update, __pyx_k__update, sizeof(__pyx_k__update), 0, 0, 1, 1}, 1954 {&__pyx_n_s__value, __pyx_k__value, sizeof(__pyx_k__value), 0, 0, 1, 1}, 1955 {0, 0, 0, 0, 0, 0, 0} 1956}; 1957static int __Pyx_InitCachedBuiltins(void) { 1958 __pyx_builtin_property = __Pyx_GetName(__pyx_b, __pyx_n_s__property); if (!__pyx_builtin_property) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 29; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1959 __pyx_builtin_KeyError = __Pyx_GetName(__pyx_b, __pyx_n_s__KeyError); if (!__pyx_builtin_KeyError) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1960 __pyx_builtin_MemoryError = __Pyx_GetName(__pyx_b, __pyx_n_s__MemoryError); if (!__pyx_builtin_MemoryError) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1961 __pyx_builtin_ValueError = __Pyx_GetName(__pyx_b, __pyx_n_s__ValueError); if (!__pyx_builtin_ValueError) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 77; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1962 return 0; 1963 __pyx_L1_error:; 1964 return -1; 1965} 1966 1967static int __Pyx_InitCachedConstants(void) { 1968 __Pyx_RefNannyDeclarations 1969 __Pyx_RefNannySetupContext("__Pyx_InitCachedConstants", 0); 1970 1971 /* "bintrees\qavltree.pyx":60 1972 * res = avl_insert(&self._root, key, value) 1973 * if res < 0: 1974 * raise MemoryError('Can not allocate memory for node structure.') # <<<<<<<<<<<<<< 1975 * else: 1976 * self._count += res 1977 */ 1978 __pyx_k_tuple_2 = PyTuple_New(1); if (unlikely(!__pyx_k_tuple_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1979 __Pyx_GOTREF(__pyx_k_tuple_2); 1980 __Pyx_INCREF(((PyObject *)__pyx_kp_s_1)); 1981 PyTuple_SET_ITEM(__pyx_k_tuple_2, 0, ((PyObject *)__pyx_kp_s_1)); 1982 __Pyx_GIVEREF(((PyObject *)__pyx_kp_s_1)); 1983 __Pyx_GIVEREF(((PyObject *)__pyx_k_tuple_2)); 1984 1985 /* "bintrees\qavltree.pyx":77 1986 * node = ct_max_node(self._root) 1987 * if node == NULL: # root is None 1988 * raise ValueError("Tree is empty") # <<<<<<<<<<<<<< 1989 * return (<object>node.key, <object>node.value) 1990 * 1991 */ 1992 __pyx_k_tuple_4 = PyTuple_New(1); if (unlikely(!__pyx_k_tuple_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 77; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1993 __Pyx_GOTREF(__pyx_k_tuple_4); 1994 __Pyx_INCREF(((PyObject *)__pyx_kp_s_3)); 1995 PyTuple_SET_ITEM(__pyx_k_tuple_4, 0, ((PyObject *)__pyx_kp_s_3)); 1996 __Pyx_GIVEREF(((PyObject *)__pyx_kp_s_3)); 1997 __Pyx_GIVEREF(((PyObject *)__pyx_k_tuple_4)); 1998 1999 /* "bintrees\qavltree.pyx":85 2000 * node = ct_min_node(self._root) 2001 * if node == NULL: # root is None 2002 * raise ValueError("Tree is empty") # <<<<<<<<<<<<<< 2003 * return (<object>node.key, <object>node.value) 2004 * 2005 */ 2006 __pyx_k_tuple_5 = PyTuple_New(1); if (unlikely(!__pyx_k_tuple_5)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 85; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2007 __Pyx_GOTREF(__pyx_k_tuple_5); 2008 __Pyx_INCREF(((PyObject *)__pyx_kp_s_3)); 2009 PyTuple_SET_ITEM(__pyx_k_tuple_5, 0, ((PyObject *)__pyx_kp_s_3)); 2010 __Pyx_GIVEREF(((PyObject *)__pyx_kp_s_3)); 2011 __Pyx_GIVEREF(((PyObject *)__pyx_k_tuple_5)); 2012 __Pyx_RefNannyFinishContext(); 2013 return 0; 2014 __pyx_L1_error:; 2015 __Pyx_RefNannyFinishContext(); 2016 return -1; 2017} 2018 2019static int __Pyx_InitGlobals(void) { 2020 if (__Pyx_InitStrings(__pyx_string_tab) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}; 2021 __pyx_int_0 = PyInt_FromLong(0); if (unlikely(!__pyx_int_0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}; 2022 return 0; 2023 __pyx_L1_error:; 2024 return -1; 2025} 2026 2027#if PY_MAJOR_VERSION < 3 2028PyMODINIT_FUNC initqavltree(void); /*proto*/ 2029PyMODINIT_FUNC initqavltree(void) 2030#else 2031PyMODINIT_FUNC PyInit_qavltree(void); /*proto*/ 2032PyMODINIT_FUNC PyInit_qavltree(void) 2033#endif 2034{ 2035 PyObject *__pyx_t_1 = NULL; 2036 PyObject *__pyx_t_2 = NULL; 2037 __Pyx_RefNannyDeclarations 2038 #if CYTHON_REFNANNY 2039 __Pyx_RefNanny = __Pyx_RefNannyImportAPI("refnanny"); 2040 if (!__Pyx_RefNanny) { 2041 PyErr_Clear(); 2042 __Pyx_RefNanny = __Pyx_RefNannyImportAPI("Cython.Runtime.refnanny"); 2043 if (!__Pyx_RefNanny) 2044 Py_FatalError("failed to import 'refnanny' module"); 2045 } 2046 #endif 2047 __Pyx_RefNannySetupContext("PyMODINIT_FUNC PyInit_qavltree(void)", 0); 2048 if ( __Pyx_check_binary_version() < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2049 __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;} 2050 __pyx_empty_bytes = PyBytes_FromStringAndSize("", 0); if (unlikely(!__pyx_empty_bytes)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2051 #ifdef __Pyx_CyFunction_USED 2052 if (__Pyx_CyFunction_init() < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2053 #endif 2054 #ifdef __Pyx_FusedFunction_USED 2055 if (__pyx_FusedFunction_init() < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2056 #endif 2057 #ifdef __Pyx_Generator_USED 2058 if (__pyx_Generator_init() < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2059 #endif 2060 /*--- Library function declarations ---*/ 2061 /*--- Threads initialization code ---*/ 2062 #if defined(__PYX_FORCE_INIT_THREADS) && __PYX_FORCE_INIT_THREADS 2063 #ifdef WITH_THREAD /* Python build with threading support? */ 2064 PyEval_InitThreads(); 2065 #endif 2066 #endif 2067 /*--- Module creation code ---*/ 2068 #if PY_MAJOR_VERSION < 3 2069 __pyx_m = Py_InitModule4(__Pyx_NAMESTR("qavltree"), __pyx_methods, 0, 0, PYTHON_API_VERSION); Py_XINCREF(__pyx_m); 2070 #else 2071 __pyx_m = PyModule_Create(&__pyx_moduledef); 2072 #endif 2073 if (unlikely(!__pyx_m)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2074 #if PY_MAJOR_VERSION >= 3 2075 { 2076 PyObject *modules = PyImport_GetModuleDict(); if (unlikely(!modules)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2077 if (!PyDict_GetItemString(modules, "bintrees.qavltree")) { 2078 if (unlikely(PyDict_SetItemString(modules, "bintrees.qavltree", __pyx_m) < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2079 } 2080 } 2081 #endif 2082 __pyx_b = PyImport_AddModule(__Pyx_NAMESTR(__Pyx_BUILTIN_MODULE_NAME)); if (unlikely(!__pyx_b)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2083 #if CYTHON_COMPILING_IN_PYPY 2084 Py_INCREF(__pyx_b); 2085 #endif 2086 if (__Pyx_SetAttrString(__pyx_m, "__builtins__", __pyx_b) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}; 2087 /*--- Initialize various global constants etc. ---*/ 2088 if (unlikely(__Pyx_InitGlobals() < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2089 if (__pyx_module_is_main_bintrees__qavltree) { 2090 if (__Pyx_SetAttrString(__pyx_m, "__name__", __pyx_n_s____main__) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}; 2091 } 2092 /*--- Builtin init code ---*/ 2093 if (unlikely(__Pyx_InitCachedBuiltins() < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2094 /*--- Constants init code ---*/ 2095 if (unlikely(__Pyx_InitCachedConstants() < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2096 /*--- Global init code ---*/ 2097 /*--- Variable export code ---*/ 2098 /*--- Function export code ---*/ 2099 /*--- Type init code ---*/ 2100 if (PyType_Ready(&__pyx_type_8bintrees_8qavltree_cAVLTree) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 16; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2101 if (__Pyx_SetAttrString(__pyx_m, "cAVLTree", (PyObject *)&__pyx_type_8bintrees_8qavltree_cAVLTree) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 16; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2102 __pyx_ptype_8bintrees_8qavltree_cAVLTree = &__pyx_type_8bintrees_8qavltree_cAVLTree; 2103 /*--- Type import code ---*/ 2104 __pyx_ptype_8bintrees_7cwalker_cWalker = __Pyx_ImportType("bintrees.cwalker", "cWalker", sizeof(struct __pyx_obj_8bintrees_7cwalker_cWalker), 1); if (unlikely(!__pyx_ptype_8bintrees_7cwalker_cWalker)) {__pyx_filename = __pyx_f[1]; __pyx_lineno = 11; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2105 __pyx_vtabptr_8bintrees_7cwalker_cWalker = (struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker*)__Pyx_GetVtable(__pyx_ptype_8bintrees_7cwalker_cWalker->tp_dict); if (unlikely(!__pyx_vtabptr_8bintrees_7cwalker_cWalker)) {__pyx_filename = __pyx_f[1]; __pyx_lineno = 11; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2106 /*--- Variable import code ---*/ 2107 /*--- Function import code ---*/ 2108 /*--- Execution code ---*/ 2109 2110 /* "bintrees\qavltree.pyx":9 2111 * # License: MIT License 2112 * 2113 * __all__ = ['cAVLTree'] # <<<<<<<<<<<<<< 2114 * 2115 * from cwalker import cWalker 2116 */ 2117 __pyx_t_1 = PyList_New(1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 9; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2118 __Pyx_GOTREF(__pyx_t_1); 2119 __Pyx_INCREF(((PyObject *)__pyx_n_s__cAVLTree)); 2120 PyList_SET_ITEM(__pyx_t_1, 0, ((PyObject *)__pyx_n_s__cAVLTree)); 2121 __Pyx_GIVEREF(((PyObject *)__pyx_n_s__cAVLTree)); 2122 if (PyObject_SetAttr(__pyx_m, __pyx_n_s____all__, ((PyObject *)__pyx_t_1)) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 9; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2123 __Pyx_DECREF(((PyObject *)__pyx_t_1)); __pyx_t_1 = 0; 2124 2125 /* "bintrees\qavltree.pyx":11 2126 * __all__ = ['cAVLTree'] 2127 * 2128 * from cwalker import cWalker # <<<<<<<<<<<<<< 2129 * 2130 * from cwalker cimport * 2131 */ 2132 __pyx_t_1 = PyList_New(1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 11; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2133 __Pyx_GOTREF(__pyx_t_1); 2134 __Pyx_INCREF(((PyObject *)__pyx_n_s__cWalker)); 2135 PyList_SET_ITEM(__pyx_t_1, 0, ((PyObject *)__pyx_n_s__cWalker)); 2136 __Pyx_GIVEREF(((PyObject *)__pyx_n_s__cWalker)); 2137 __pyx_t_2 = __Pyx_Import(((PyObject *)__pyx_n_s__cwalker), ((PyObject *)__pyx_t_1), -1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 11; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2138 __Pyx_GOTREF(__pyx_t_2); 2139 __Pyx_DECREF(((PyObject *)__pyx_t_1)); __pyx_t_1 = 0; 2140 __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; 2141 2142 /* "bintrees\qavltree.pyx":30 2143 * 2144 * @property 2145 * def count(self): # <<<<<<<<<<<<<< 2146 * return self._count 2147 * 2148 */ 2149 __pyx_t_2 = __Pyx_GetName((PyObject *)__pyx_ptype_8bintrees_8qavltree_cAVLTree, __pyx_n_s__count); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 30; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2150 __Pyx_GOTREF(__pyx_t_2); 2151 __pyx_t_1 = PyTuple_New(1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 29; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2152 __Pyx_GOTREF(__pyx_t_1); 2153 PyTuple_SET_ITEM(__pyx_t_1, 0, __pyx_t_2); 2154 __Pyx_GIVEREF(__pyx_t_2); 2155 __pyx_t_2 = 0; 2156 __pyx_t_2 = PyObject_Call(__pyx_builtin_property, ((PyObject *)__pyx_t_1), NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 29; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2157 __Pyx_GOTREF(__pyx_t_2); 2158 __Pyx_DECREF(((PyObject *)__pyx_t_1)); __pyx_t_1 = 0; 2159 if (PyDict_SetItem((PyObject *)__pyx_ptype_8bintrees_8qavltree_cAVLTree->tp_dict, __pyx_n_s__count, __pyx_t_2) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 30; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2160 __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; 2161 PyType_Modified(__pyx_ptype_8bintrees_8qavltree_cAVLTree); 2162 2163 /* "bintrees\qavltree.pyx":1 2164 * #!/usr/bin/env python # <<<<<<<<<<<<<< 2165 * #coding:utf-8 2166 * # Author: mozman 2167 */ 2168 __pyx_t_2 = PyDict_New(); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2169 __Pyx_GOTREF(((PyObject *)__pyx_t_2)); 2170 if (PyObject_SetAttr(__pyx_m, __pyx_n_s____test__, ((PyObject *)__pyx_t_2)) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2171 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 2172 goto __pyx_L0; 2173 __pyx_L1_error:; 2174 __Pyx_XDECREF(__pyx_t_1); 2175 __Pyx_XDECREF(__pyx_t_2); 2176 if (__pyx_m) { 2177 __Pyx_AddTraceback("init bintrees.qavltree", __pyx_clineno, __pyx_lineno, __pyx_filename); 2178 Py_DECREF(__pyx_m); __pyx_m = 0; 2179 } else if (!PyErr_Occurred()) { 2180 PyErr_SetString(PyExc_ImportError, "init bintrees.qavltree"); 2181 } 2182 __pyx_L0:; 2183 __Pyx_RefNannyFinishContext(); 2184 #if PY_MAJOR_VERSION < 3 2185 return; 2186 #else 2187 return __pyx_m; 2188 #endif 2189} 2190 2191/* Runtime support code */ 2192#if CYTHON_REFNANNY 2193static __Pyx_RefNannyAPIStruct *__Pyx_RefNannyImportAPI(const char *modname) { 2194 PyObject *m = NULL, *p = NULL; 2195 void *r = NULL; 2196 m = PyImport_ImportModule((char *)modname); 2197 if (!m) goto end; 2198 p = PyObject_GetAttrString(m, (char *)"RefNannyAPI"); 2199 if (!p) goto end; 2200 r = PyLong_AsVoidPtr(p); 2201end: 2202 Py_XDECREF(p); 2203 Py_XDECREF(m); 2204 return (__Pyx_RefNannyAPIStruct *)r; 2205} 2206#endif /* CYTHON_REFNANNY */ 2207 2208static PyObject *__Pyx_GetName(PyObject *dict, PyObject *name) { 2209 PyObject *result; 2210 result = PyObject_GetAttr(dict, name); 2211 if (!result) { 2212 if (dict != __pyx_b) { 2213 PyErr_Clear(); 2214 result = PyObject_GetAttr(__pyx_b, name); 2215 } 2216 if (!result) { 2217 PyErr_SetObject(PyExc_NameError, name); 2218 } 2219 } 2220 return result; 2221} 2222 2223static void __Pyx_RaiseDoubleKeywordsError( 2224 const char* func_name, 2225 PyObject* kw_name) 2226{ 2227 PyErr_Format(PyExc_TypeError, 2228 #if PY_MAJOR_VERSION >= 3 2229 "%s() got multiple values for keyword argument '%U'", func_name, kw_name); 2230 #else 2231 "%s() got multiple values for keyword argument '%s'", func_name, 2232 PyString_AsString(kw_name)); 2233 #endif 2234} 2235 2236static int __Pyx_ParseOptionalKeywords( 2237 PyObject *kwds, 2238 PyObject **argnames[], 2239 PyObject *kwds2, 2240 PyObject *values[], 2241 Py_ssize_t num_pos_args, 2242 const char* function_name) 2243{ 2244 PyObject *key = 0, *value = 0; 2245 Py_ssize_t pos = 0; 2246 PyObject*** name; 2247 PyObject*** first_kw_arg = argnames + num_pos_args; 2248 while (PyDict_Next(kwds, &pos, &key, &value)) { 2249 name = first_kw_arg; 2250 while (*name && (**name != key)) name++; 2251 if (*name) { 2252 values[name-argnames] = value; 2253 continue; 2254 } 2255 name = first_kw_arg; 2256 #if PY_MAJOR_VERSION < 3 2257 if (likely(PyString_CheckExact(key)) || likely(PyString_Check(key))) { 2258 while (*name) { 2259 if ((CYTHON_COMPILING_IN_PYPY || PyString_GET_SIZE(**name) == PyString_GET_SIZE(key)) 2260 && _PyString_Eq(**name, key)) { 2261 values[name-argnames] = value; 2262 break; 2263 } 2264 name++; 2265 } 2266 if (*name) continue; 2267 else { 2268 PyObject*** argname = argnames; 2269 while (argname != first_kw_arg) { 2270 if ((**argname == key) || ( 2271 (CYTHON_COMPILING_IN_PYPY || PyString_GET_SIZE(**argname) == PyString_GET_SIZE(key)) 2272 && _PyString_Eq(**argname, key))) { 2273 goto arg_passed_twice; 2274 } 2275 argname++; 2276 } 2277 } 2278 } else 2279 #endif 2280 if (likely(PyUnicode_Check(key))) { 2281 while (*name) { 2282 int cmp = (**name == key) ? 0 : 2283 #if !CYTHON_COMPILING_IN_PYPY && PY_MAJOR_VERSION >= 3 2284 (PyUnicode_GET_SIZE(**name) != PyUnicode_GET_SIZE(key)) ? 1 : 2285 #endif 2286 PyUnicode_Compare(**name, key); 2287 if (cmp < 0 && unlikely(PyErr_Occurred())) goto bad; 2288 if (cmp == 0) { 2289 values[name-argnames] = value; 2290 break; 2291 } 2292 name++; 2293 } 2294 if (*name) continue; 2295 else { 2296 PyObject*** argname = argnames; 2297 while (argname != first_kw_arg) { 2298 int cmp = (**argname == key) ? 0 : 2299 #if !CYTHON_COMPILING_IN_PYPY && PY_MAJOR_VERSION >= 3 2300 (PyUnicode_GET_SIZE(**argname) != PyUnicode_GET_SIZE(key)) ? 1 : 2301 #endif 2302 PyUnicode_Compare(**argname, key); 2303 if (cmp < 0 && unlikely(PyErr_Occurred())) goto bad; 2304 if (cmp == 0) goto arg_passed_twice; 2305 argname++; 2306 } 2307 } 2308 } else 2309 goto invalid_keyword_type; 2310 if (kwds2) { 2311 if (unlikely(PyDict_SetItem(kwds2, key, value))) goto bad; 2312 } else { 2313 goto invalid_keyword; 2314 } 2315 } 2316 return 0; 2317arg_passed_twice: 2318 __Pyx_RaiseDoubleKeywordsError(function_name, key); 2319 goto bad; 2320invalid_keyword_type: 2321 PyErr_Format(PyExc_TypeError, 2322 "%s() keywords must be strings", function_name); 2323 goto bad; 2324invalid_keyword: 2325 PyErr_Format(PyExc_TypeError, 2326 #if PY_MAJOR_VERSION < 3 2327 "%s() got an unexpected keyword argument '%s'", 2328 function_name, PyString_AsString(key)); 2329 #else 2330 "%s() got an unexpected keyword argument '%U'", 2331 function_name, key); 2332 #endif 2333bad: 2334 return -1; 2335} 2336 2337static void __Pyx_RaiseArgtupleInvalid( 2338 const char* func_name, 2339 int exact, 2340 Py_ssize_t num_min, 2341 Py_ssize_t num_max, 2342 Py_ssize_t num_found) 2343{ 2344 Py_ssize_t num_expected; 2345 const char *more_or_less; 2346 if (num_found < num_min) { 2347 num_expected = num_min; 2348 more_or_less = "at least"; 2349 } else { 2350 num_expected = num_max; 2351 more_or_less = "at most"; 2352 } 2353 if (exact) { 2354 more_or_less = "exactly"; 2355 } 2356 PyErr_Format(PyExc_TypeError, 2357 "%s() takes %s %" CYTHON_FORMAT_SSIZE_T "d positional argument%s (%" CYTHON_FORMAT_SSIZE_T "d given)", 2358 func_name, more_or_less, num_expected, 2359 (num_expected == 1) ? "" : "s", num_found); 2360} 2361 2362static CYTHON_INLINE void __Pyx_ErrRestore(PyObject *type, PyObject *value, PyObject *tb) { 2363#if CYTHON_COMPILING_IN_CPYTHON 2364 PyObject *tmp_type, *tmp_value, *tmp_tb; 2365 PyThreadState *tstate = PyThreadState_GET(); 2366 tmp_type = tstate->curexc_type; 2367 tmp_value = tstate->curexc_value; 2368 tmp_tb = tstate->curexc_traceback; 2369 tstate->curexc_type = type; 2370 tstate->curexc_value = value; 2371 tstate->curexc_traceback = tb; 2372 Py_XDECREF(tmp_type); 2373 Py_XDECREF(tmp_value); 2374 Py_XDECREF(tmp_tb); 2375#else 2376 PyErr_Restore(type, value, tb); 2377#endif 2378} 2379static CYTHON_INLINE void __Pyx_ErrFetch(PyObject **type, PyObject **value, PyObject **tb) { 2380#if CYTHON_COMPILING_IN_CPYTHON 2381 PyThreadState *tstate = PyThreadState_GET(); 2382 *type = tstate->curexc_type; 2383 *value = tstate->curexc_value; 2384 *tb = tstate->curexc_traceback; 2385 tstate->curexc_type = 0; 2386 tstate->curexc_value = 0; 2387 tstate->curexc_traceback = 0; 2388#else 2389 PyErr_Fetch(type, value, tb); 2390#endif 2391} 2392 2393#if PY_MAJOR_VERSION < 3 2394static void __Pyx_Raise(PyObject *type, PyObject *value, PyObject *tb, 2395 CYTHON_UNUSED PyObject *cause) { 2396 Py_XINCREF(type); 2397 if (!value || value == Py_None) 2398 value = NULL; 2399 else 2400 Py_INCREF(value); 2401 if (!tb || tb == Py_None) 2402 tb = NULL; 2403 else { 2404 Py_INCREF(tb); 2405 if (!PyTraceBack_Check(tb)) { 2406 PyErr_SetString(PyExc_TypeError, 2407 "raise: arg 3 must be a traceback or None"); 2408 goto raise_error; 2409 } 2410 } 2411 #if PY_VERSION_HEX < 0x02050000 2412 if (PyClass_Check(type)) { 2413 #else 2414 if (PyType_Check(type)) { 2415 #endif 2416#if CYTHON_COMPILING_IN_PYPY 2417 if (!value) { 2418 Py_INCREF(Py_None); 2419 value = Py_None; 2420 } 2421#endif 2422 PyErr_NormalizeException(&type, &value, &tb); 2423 } else { 2424 if (value) { 2425 PyErr_SetString(PyExc_TypeError, 2426 "instance exception may not have a separate value"); 2427 goto raise_error; 2428 } 2429 value = type; 2430 #if PY_VERSION_HEX < 0x02050000 2431 if (PyInstance_Check(type)) { 2432 type = (PyObject*) ((PyInstanceObject*)type)->in_class; 2433 Py_INCREF(type); 2434 } 2435 else { 2436 type = 0; 2437 PyErr_SetString(PyExc_TypeError, 2438 "raise: exception must be an old-style class or instance"); 2439 goto raise_error; 2440 } 2441 #else 2442 type = (PyObject*) Py_TYPE(type); 2443 Py_INCREF(type); 2444 if (!PyType_IsSubtype((PyTypeObject *)type, (PyTypeObject *)PyExc_BaseException)) { 2445 PyErr_SetString(PyExc_TypeError, 2446 "raise: exception class must be a subclass of BaseException"); 2447 goto raise_error; 2448 } 2449 #endif 2450 } 2451 __Pyx_ErrRestore(type, value, tb); 2452 return; 2453raise_error: 2454 Py_XDECREF(value); 2455 Py_XDECREF(type); 2456 Py_XDECREF(tb); 2457 return; 2458} 2459#else /* Python 3+ */ 2460static void __Pyx_Raise(PyObject *type, PyObject *value, PyObject *tb, PyObject *cause) { 2461 PyObject* owned_instance = NULL; 2462 if (tb == Py_None) { 2463 tb = 0; 2464 } else if (tb && !PyTraceBack_Check(tb)) { 2465 PyErr_SetString(PyExc_TypeError, 2466 "raise: arg 3 must be a traceback or None"); 2467 goto bad; 2468 } 2469 if (value == Py_None) 2470 value = 0; 2471 if (PyExceptionInstance_Check(type)) { 2472 if (value) { 2473 PyErr_SetString(PyExc_TypeError, 2474 "instance exception may not have a separate value"); 2475 goto bad; 2476 } 2477 value = type; 2478 type = (PyObject*) Py_TYPE(value); 2479 } else if (PyExceptionClass_Check(type)) { 2480 PyObject *args; 2481 if (!value) 2482 args = PyTuple_New(0); 2483 else if (PyTuple_Check(value)) { 2484 Py_INCREF(value); 2485 args = value; 2486 } 2487 else 2488 args = PyTuple_Pack(1, value); 2489 if (!args) 2490 goto bad; 2491 owned_instance = PyEval_CallObject(type, args); 2492 Py_DECREF(args); 2493 if (!owned_instance) 2494 goto bad; 2495 value = owned_instance; 2496 if (!PyExceptionInstance_Check(value)) { 2497 PyErr_Format(PyExc_TypeError, 2498 "calling %R should have returned an instance of " 2499 "BaseException, not %R", 2500 type, Py_TYPE(value)); 2501 goto bad; 2502 } 2503 } else { 2504 PyErr_SetString(PyExc_TypeError, 2505 "raise: exception class must be a subclass of BaseException"); 2506 goto bad; 2507 } 2508 if (cause && cause != Py_None) { 2509 PyObject *fixed_cause; 2510 if (PyExceptionClass_Check(cause)) { 2511 fixed_cause = PyObject_CallObject(cause, NULL); 2512 if (fixed_cause == NULL) 2513 goto bad; 2514 } 2515 else if (PyExceptionInstance_Check(cause)) { 2516 fixed_cause = cause; 2517 Py_INCREF(fixed_cause); 2518 } 2519 else { 2520 PyErr_SetString(PyExc_TypeError, 2521 "exception causes must derive from " 2522 "BaseException"); 2523 goto bad; 2524 } 2525 PyException_SetCause(value, fixed_cause); 2526 } 2527 PyErr_SetObject(type, value); 2528 if (tb) { 2529 PyThreadState *tstate = PyThreadState_GET(); 2530 PyObject* tmp_tb = tstate->curexc_traceback; 2531 if (tb != tmp_tb) { 2532 Py_INCREF(tb); 2533 tstate->curexc_traceback = tb; 2534 Py_XDECREF(tmp_tb); 2535 } 2536 } 2537bad: 2538 Py_XDECREF(owned_instance); 2539 return; 2540} 2541#endif 2542 2543static PyObject *__Pyx_Import(PyObject *name, PyObject *from_list, long level) { 2544 PyObject *py_import = 0; 2545 PyObject *empty_list = 0; 2546 PyObject *module = 0; 2547 PyObject *global_dict = 0; 2548 PyObject *empty_dict = 0; 2549 PyObject *list; 2550 py_import = __Pyx_GetAttrString(__pyx_b, "__import__"); 2551 if (!py_import) 2552 goto bad; 2553 if (from_list) 2554 list = from_list; 2555 else { 2556 empty_list = PyList_New(0); 2557 if (!empty_list) 2558 goto bad; 2559 list = empty_list; 2560 } 2561 global_dict = PyModule_GetDict(__pyx_m); 2562 if (!global_dict) 2563 goto bad; 2564 empty_dict = PyDict_New(); 2565 if (!empty_dict) 2566 goto bad; 2567 #if PY_VERSION_HEX >= 0x02050000 2568 { 2569 #if PY_MAJOR_VERSION >= 3 2570 if (level == -1) { 2571 if (strchr(__Pyx_MODULE_NAME, '.')) { 2572 /* try package relative import first */ 2573 PyObject *py_level = PyInt_FromLong(1); 2574 if (!py_level) 2575 goto bad; 2576 module = PyObject_CallFunctionObjArgs(py_import, 2577 name, global_dict, empty_dict, list, py_level, NULL); 2578 Py_DECREF(py_level); 2579 if (!module) { 2580 if (!PyErr_ExceptionMatches(PyExc_ImportError)) 2581 goto bad; 2582 PyErr_Clear(); 2583 } 2584 } 2585 level = 0; /* try absolute import on failure */ 2586 } 2587 #endif 2588 if (!module) { 2589 PyObject *py_level = PyInt_FromLong(level); 2590 if (!py_level) 2591 goto bad; 2592 module = PyObject_CallFunctionObjArgs(py_import, 2593 name, global_dict, empty_dict, list, py_level, NULL); 2594 Py_DECREF(py_level); 2595 } 2596 } 2597 #else 2598 if (level>0) { 2599 PyErr_SetString(PyExc_RuntimeError, "Relative import is not supported for Python <=2.4."); 2600 goto bad; 2601 } 2602 module = PyObject_CallFunctionObjArgs(py_import, 2603 name, global_dict, empty_dict, list, NULL); 2604 #endif 2605bad: 2606 Py_XDECREF(empty_list); 2607 Py_XDECREF(py_import); 2608 Py_XDECREF(empty_dict); 2609 return module; 2610} 2611 2612static CYTHON_INLINE unsigned char __Pyx_PyInt_AsUnsignedChar(PyObject* x) { 2613 const unsigned char neg_one = (unsigned char)-1, const_zero = 0; 2614 const int is_unsigned = neg_one > const_zero; 2615 if (sizeof(unsigned char) < sizeof(long)) { 2616 long val = __Pyx_PyInt_AsLong(x); 2617 if (unlikely(val != (long)(unsigned char)val)) { 2618 if (!unlikely(val == -1 && PyErr_Occurred())) { 2619 PyErr_SetString(PyExc_OverflowError, 2620 (is_unsigned && unlikely(val < 0)) ? 2621 "can't convert negative value to unsigned char" : 2622 "value too large to convert to unsigned char"); 2623 } 2624 return (unsigned char)-1; 2625 } 2626 return (unsigned char)val; 2627 } 2628 return (unsigned char)__Pyx_PyInt_AsUnsignedLong(x); 2629} 2630 2631static CYTHON_INLINE unsigned short __Pyx_PyInt_AsUnsignedShort(PyObject* x) { 2632 const unsigned short neg_one = (unsigned short)-1, const_zero = 0; 2633 const int is_unsigned = neg_one > const_zero; 2634 if (sizeof(unsigned short) < sizeof(long)) { 2635 long val = __Pyx_PyInt_AsLong(x); 2636 if (unlikely(val != (long)(unsigned short)val)) { 2637 if (!unlikely(val == -1 && PyErr_Occurred())) { 2638 PyErr_SetString(PyExc_OverflowError, 2639 (is_unsigned && unlikely(val < 0)) ? 2640 "can't convert negative value to unsigned short" : 2641 "value too large to convert to unsigned short"); 2642 } 2643 return (unsigned short)-1; 2644 } 2645 return (unsigned short)val; 2646 } 2647 return (unsigned short)__Pyx_PyInt_AsUnsignedLong(x); 2648} 2649 2650static CYTHON_INLINE unsigned int __Pyx_PyInt_AsUnsignedInt(PyObject* x) { 2651 const unsigned int neg_one = (unsigned int)-1, const_zero = 0; 2652 const int is_unsigned = neg_one > const_zero; 2653 if (sizeof(unsigned int) < sizeof(long)) { 2654 long val = __Pyx_PyInt_AsLong(x); 2655 if (unlikely(val != (long)(unsigned int)val)) { 2656 if (!unlikely(val == -1 && PyErr_Occurred())) { 2657 PyErr_SetString(PyExc_OverflowError, 2658 (is_unsigned && unlikely(val < 0)) ? 2659 "can't convert negative value to unsigned int" : 2660 "value too large to convert to unsigned int"); 2661 } 2662 return (unsigned int)-1; 2663 } 2664 return (unsigned int)val; 2665 } 2666 return (unsigned int)__Pyx_PyInt_AsUnsignedLong(x); 2667} 2668 2669static CYTHON_INLINE char __Pyx_PyInt_AsChar(PyObject* x) { 2670 const char neg_one = (char)-1, const_zero = 0; 2671 const int is_unsigned = neg_one > const_zero; 2672 if (sizeof(char) < sizeof(long)) { 2673 long val = __Pyx_PyInt_AsLong(x); 2674 if (unlikely(val != (long)(char)val)) { 2675 if (!unlikely(val == -1 && PyErr_Occurred())) { 2676 PyErr_SetString(PyExc_OverflowError, 2677 (is_unsigned && unlikely(val < 0)) ? 2678 "can't convert negative value to char" : 2679 "value too large to convert to char"); 2680 } 2681 return (char)-1; 2682 } 2683 return (char)val; 2684 } 2685 return (char)__Pyx_PyInt_AsLong(x); 2686} 2687 2688static CYTHON_INLINE short __Pyx_PyInt_AsShort(PyObject* x) { 2689 const short neg_one = (short)-1, const_zero = 0; 2690 const int is_unsigned = neg_one > const_zero; 2691 if (sizeof(short) < sizeof(long)) { 2692 long val = __Pyx_PyInt_AsLong(x); 2693 if (unlikely(val != (long)(short)val)) { 2694 if (!unlikely(val == -1 && PyErr_Occurred())) { 2695 PyErr_SetString(PyExc_OverflowError, 2696 (is_unsigned && unlikely(val < 0)) ? 2697 "can't convert negative value to short" : 2698 "value too large to convert to short"); 2699 } 2700 return (short)-1; 2701 } 2702 return (short)val; 2703 } 2704 return (short)__Pyx_PyInt_AsLong(x); 2705} 2706 2707static CYTHON_INLINE int __Pyx_PyInt_AsInt(PyObject* x) { 2708 const int neg_one = (int)-1, const_zero = 0; 2709 const int is_unsigned = neg_one > const_zero; 2710 if (sizeof(int) < sizeof(long)) { 2711 long val = __Pyx_PyInt_AsLong(x); 2712 if (unlikely(val != (long)(int)val)) { 2713 if (!unlikely(val == -1 && PyErr_Occurred())) { 2714 PyErr_SetString(PyExc_OverflowError, 2715 (is_unsigned && unlikely(val < 0)) ? 2716 "can't convert negative value to int" : 2717 "value too large to convert to int"); 2718 } 2719 return (int)-1; 2720 } 2721 return (int)val; 2722 } 2723 return (int)__Pyx_PyInt_AsLong(x); 2724} 2725 2726static CYTHON_INLINE signed char __Pyx_PyInt_AsSignedChar(PyObject* x) { 2727 const signed char neg_one = (signed char)-1, const_zero = 0; 2728 const int is_unsigned = neg_one > const_zero; 2729 if (sizeof(signed char) < sizeof(long)) { 2730 long val = __Pyx_PyInt_AsLong(x); 2731 if (unlikely(val != (long)(signed char)val)) { 2732 if (!unlikely(val == -1 && PyErr_Occurred())) { 2733 PyErr_SetString(PyExc_OverflowError, 2734 (is_unsigned && unlikely(val < 0)) ? 2735 "can't convert negative value to signed char" : 2736 "value too large to convert to signed char"); 2737 } 2738 return (signed char)-1; 2739 } 2740 return (signed char)val; 2741 } 2742 return (signed char)__Pyx_PyInt_AsSignedLong(x); 2743} 2744 2745static CYTHON_INLINE signed short __Pyx_PyInt_AsSignedShort(PyObject* x) { 2746 const signed short neg_one = (signed short)-1, const_zero = 0; 2747 const int is_unsigned = neg_one > const_zero; 2748 if (sizeof(signed short) < sizeof(long)) { 2749 long val = __Pyx_PyInt_AsLong(x); 2750 if (unlikely(val != (long)(signed short)val)) { 2751 if (!unlikely(val == -1 && PyErr_Occurred())) { 2752 PyErr_SetString(PyExc_OverflowError, 2753 (is_unsigned && unlikely(val < 0)) ? 2754 "can't convert negative value to signed short" : 2755 "value too large to convert to signed short"); 2756 } 2757 return (signed short)-1; 2758 } 2759 return (signed short)val; 2760 } 2761 return (signed short)__Pyx_PyInt_AsSignedLong(x); 2762} 2763 2764static CYTHON_INLINE signed int __Pyx_PyInt_AsSignedInt(PyObject* x) { 2765 const signed int neg_one = (signed int)-1, const_zero = 0; 2766 const int is_unsigned = neg_one > const_zero; 2767 if (sizeof(signed int) < sizeof(long)) { 2768 long val = __Pyx_PyInt_AsLong(x); 2769 if (unlikely(val != (long)(signed int)val)) { 2770 if (!unlikely(val == -1 && PyErr_Occurred())) { 2771 PyErr_SetString(PyExc_OverflowError, 2772 (is_unsigned && unlikely(val < 0)) ? 2773 "can't convert negative value to signed int" : 2774 "value too large to convert to signed int"); 2775 } 2776 return (signed int)-1; 2777 } 2778 return (signed int)val; 2779 } 2780 return (signed int)__Pyx_PyInt_AsSignedLong(x); 2781} 2782 2783static CYTHON_INLINE int __Pyx_PyInt_AsLongDouble(PyObject* x) { 2784 const int neg_one = (int)-1, const_zero = 0; 2785 const int is_unsigned = neg_one > const_zero; 2786 if (sizeof(int) < sizeof(long)) { 2787 long val = __Pyx_PyInt_AsLong(x); 2788 if (unlikely(val != (long)(int)val)) { 2789 if (!unlikely(val == -1 && PyErr_Occurred())) { 2790 PyErr_SetString(PyExc_OverflowError, 2791 (is_unsigned && unlikely(val < 0)) ? 2792 "can't convert negative value to int" : 2793 "value too large to convert to int"); 2794 } 2795 return (int)-1; 2796 } 2797 return (int)val; 2798 } 2799 return (int)__Pyx_PyInt_AsLong(x); 2800} 2801 2802static CYTHON_INLINE unsigned long __Pyx_PyInt_AsUnsignedLong(PyObject* x) { 2803 const unsigned long neg_one = (unsigned long)-1, const_zero = 0; 2804 const int is_unsigned = neg_one > const_zero; 2805#if PY_VERSION_HEX < 0x03000000 2806 if (likely(PyInt_Check(x))) { 2807 long val = PyInt_AS_LONG(x); 2808 if (is_unsigned && unlikely(val < 0)) { 2809 PyErr_SetString(PyExc_OverflowError, 2810 "can't convert negative value to unsigned long"); 2811 return (unsigned long)-1; 2812 } 2813 return (unsigned long)val; 2814 } else 2815#endif 2816 if (likely(PyLong_Check(x))) { 2817 if (is_unsigned) { 2818 if (unlikely(Py_SIZE(x) < 0)) { 2819 PyErr_SetString(PyExc_OverflowError, 2820 "can't convert negative value to unsigned long"); 2821 return (unsigned long)-1; 2822 } 2823 return (unsigned long)PyLong_AsUnsignedLong(x); 2824 } else { 2825 return (unsigned long)PyLong_AsLong(x); 2826 } 2827 } else { 2828 unsigned long val; 2829 PyObject *tmp = __Pyx_PyNumber_Int(x); 2830 if (!tmp) return (unsigned long)-1; 2831 val = __Pyx_PyInt_AsUnsignedLong(tmp); 2832 Py_DECREF(tmp); 2833 return val; 2834 } 2835} 2836 2837static CYTHON_INLINE unsigned PY_LONG_LONG __Pyx_PyInt_AsUnsignedLongLong(PyObject* x) { 2838 const unsigned PY_LONG_LONG neg_one = (unsigned PY_LONG_LONG)-1, const_zero = 0; 2839 const int is_unsigned = neg_one > const_zero; 2840#if PY_VERSION_HEX < 0x03000000 2841 if (likely(PyInt_Check(x))) { 2842 long val = PyInt_AS_LONG(x); 2843 if (is_unsigned && unlikely(val < 0)) { 2844 PyErr_SetString(PyExc_OverflowError, 2845 "can't convert negative value to unsigned PY_LONG_LONG"); 2846 return (unsigned PY_LONG_LONG)-1; 2847 } 2848 return (unsigned PY_LONG_LONG)val; 2849 } else 2850#endif 2851 if (likely(PyLong_Check(x))) { 2852 if (is_unsigned) { 2853 if (unlikely(Py_SIZE(x) < 0)) { 2854 PyErr_SetString(PyExc_OverflowError, 2855 "can't convert negative value to unsigned PY_LONG_LONG"); 2856 return (unsigned PY_LONG_LONG)-1; 2857 } 2858 return (unsigned PY_LONG_LONG)PyLong_AsUnsignedLongLong(x); 2859 } else { 2860 return (unsigned PY_LONG_LONG)PyLong_AsLongLong(x); 2861 } 2862 } else { 2863 unsigned PY_LONG_LONG val; 2864 PyObject *tmp = __Pyx_PyNumber_Int(x); 2865 if (!tmp) return (unsigned PY_LONG_LONG)-1; 2866 val = __Pyx_PyInt_AsUnsignedLongLong(tmp); 2867 Py_DECREF(tmp); 2868 return val; 2869 } 2870} 2871 2872static CYTHON_INLINE long __Pyx_PyInt_AsLong(PyObject* x) { 2873 const long neg_one = (long)-1, const_zero = 0; 2874 const int is_unsigned = neg_one > const_zero; 2875#if PY_VERSION_HEX < 0x03000000 2876 if (likely(PyInt_Check(x))) { 2877 long val = PyInt_AS_LONG(x); 2878 if (is_unsigned && unlikely(val < 0)) { 2879 PyErr_SetString(PyExc_OverflowError, 2880 "can't convert negative value to long"); 2881 return (long)-1; 2882 } 2883 return (long)val; 2884 } else 2885#endif 2886 if (likely(PyLong_Check(x))) { 2887 if (is_unsigned) { 2888 if (unlikely(Py_SIZE(x) < 0)) { 2889 PyErr_SetString(PyExc_OverflowError, 2890 "can't convert negative value to long"); 2891 return (long)-1; 2892 } 2893 return (long)PyLong_AsUnsignedLong(x); 2894 } else { 2895 return (long)PyLong_AsLong(x); 2896 } 2897 } else { 2898 long val; 2899 PyObject *tmp = __Pyx_PyNumber_Int(x); 2900 if (!tmp) return (long)-1; 2901 val = __Pyx_PyInt_AsLong(tmp); 2902 Py_DECREF(tmp); 2903 return val; 2904 } 2905} 2906 2907static CYTHON_INLINE PY_LONG_LONG __Pyx_PyInt_AsLongLong(PyObject* x) { 2908 const PY_LONG_LONG neg_one = (PY_LONG_LONG)-1, const_zero = 0; 2909 const int is_unsigned = neg_one > const_zero; 2910#if PY_VERSION_HEX < 0x03000000 2911 if (likely(PyInt_Check(x))) { 2912 long val = PyInt_AS_LONG(x); 2913 if (is_unsigned && unlikely(val < 0)) { 2914 PyErr_SetString(PyExc_OverflowError, 2915 "can't convert negative value to PY_LONG_LONG"); 2916 return (PY_LONG_LONG)-1; 2917 } 2918 return (PY_LONG_LONG)val; 2919 } else 2920#endif 2921 if (likely(PyLong_Check(x))) { 2922 if (is_unsigned) { 2923 if (unlikely(Py_SIZE(x) < 0)) { 2924 PyErr_SetString(PyExc_OverflowError, 2925 "can't convert negative value to PY_LONG_LONG"); 2926 return (PY_LONG_LONG)-1; 2927 } 2928 return (PY_LONG_LONG)PyLong_AsUnsignedLongLong(x); 2929 } else { 2930 return (PY_LONG_LONG)PyLong_AsLongLong(x); 2931 } 2932 } else { 2933 PY_LONG_LONG val; 2934 PyObject *tmp = __Pyx_PyNumber_Int(x); 2935 if (!tmp) return (PY_LONG_LONG)-1; 2936 val = __Pyx_PyInt_AsLongLong(tmp); 2937 Py_DECREF(tmp); 2938 return val; 2939 } 2940} 2941 2942static CYTHON_INLINE signed long __Pyx_PyInt_AsSignedLong(PyObject* x) { 2943 const signed long neg_one = (signed long)-1, const_zero = 0; 2944 const int is_unsigned = neg_one > const_zero; 2945#if PY_VERSION_HEX < 0x03000000 2946 if (likely(PyInt_Check(x))) { 2947 long val = PyInt_AS_LONG(x); 2948 if (is_unsigned && unlikely(val < 0)) { 2949 PyErr_SetString(PyExc_OverflowError, 2950 "can't convert negative value to signed long"); 2951 return (signed long)-1; 2952 } 2953 return (signed long)val; 2954 } else 2955#endif 2956 if (likely(PyLong_Check(x))) { 2957 if (is_unsigned) { 2958 if (unlikely(Py_SIZE(x) < 0)) { 2959 PyErr_SetString(PyExc_OverflowError, 2960 "can't convert negative value to signed long"); 2961 return (signed long)-1; 2962 } 2963 return (signed long)PyLong_AsUnsignedLong(x); 2964 } else { 2965 return (signed long)PyLong_AsLong(x); 2966 } 2967 } else { 2968 signed long val; 2969 PyObject *tmp = __Pyx_PyNumber_Int(x); 2970 if (!tmp) return (signed long)-1; 2971 val = __Pyx_PyInt_AsSignedLong(tmp); 2972 Py_DECREF(tmp); 2973 return val; 2974 } 2975} 2976 2977static CYTHON_INLINE signed PY_LONG_LONG __Pyx_PyInt_AsSignedLongLong(PyObject* x) { 2978 const signed PY_LONG_LONG neg_one = (signed PY_LONG_LONG)-1, const_zero = 0; 2979 const int is_unsigned = neg_one > const_zero; 2980#if PY_VERSION_HEX < 0x03000000 2981 if (likely(PyInt_Check(x))) { 2982 long val = PyInt_AS_LONG(x); 2983 if (is_unsigned && unlikely(val < 0)) { 2984 PyErr_SetString(PyExc_OverflowError, 2985 "can't convert negative value to signed PY_LONG_LONG"); 2986 return (signed PY_LONG_LONG)-1; 2987 } 2988 return (signed PY_LONG_LONG)val; 2989 } else 2990#endif 2991 if (likely(PyLong_Check(x))) { 2992 if (is_unsigned) { 2993 if (unlikely(Py_SIZE(x) < 0)) { 2994 PyErr_SetString(PyExc_OverflowError, 2995 "can't convert negative value to signed PY_LONG_LONG"); 2996 return (signed PY_LONG_LONG)-1; 2997 } 2998 return (signed PY_LONG_LONG)PyLong_AsUnsignedLongLong(x); 2999 } else { 3000 return (signed PY_LONG_LONG)PyLong_AsLongLong(x); 3001 } 3002 } else { 3003 signed PY_LONG_LONG val; 3004 PyObject *tmp = __Pyx_PyNumber_Int(x); 3005 if (!tmp) return (signed PY_LONG_LONG)-1; 3006 val = __Pyx_PyInt_AsSignedLongLong(tmp); 3007 Py_DECREF(tmp); 3008 return val; 3009 } 3010} 3011 3012static int __Pyx_check_binary_version(void) { 3013 char ctversion[4], rtversion[4]; 3014 PyOS_snprintf(ctversion, 4, "%d.%d", PY_MAJOR_VERSION, PY_MINOR_VERSION); 3015 PyOS_snprintf(rtversion, 4, "%s", Py_GetVersion()); 3016 if (ctversion[0] != rtversion[0] || ctversion[2] != rtversion[2]) { 3017 char message[200]; 3018 PyOS_snprintf(message, sizeof(message), 3019 "compiletime version %s of module '%.100s' " 3020 "does not match runtime version %s", 3021 ctversion, __Pyx_MODULE_NAME, rtversion); 3022 #if PY_VERSION_HEX < 0x02050000 3023 return PyErr_Warn(NULL, message); 3024 #else 3025 return PyErr_WarnEx(NULL, message, 1); 3026 #endif 3027 } 3028 return 0; 3029} 3030 3031#ifndef __PYX_HAVE_RT_ImportModule 3032#define __PYX_HAVE_RT_ImportModule 3033static PyObject *__Pyx_ImportModule(const char *name) { 3034 PyObject *py_name = 0; 3035 PyObject *py_module = 0; 3036 py_name = __Pyx_PyIdentifier_FromString(name); 3037 if (!py_name) 3038 goto bad; 3039 py_module = PyImport_Import(py_name); 3040 Py_DECREF(py_name); 3041 return py_module; 3042bad: 3043 Py_XDECREF(py_name); 3044 return 0; 3045} 3046#endif 3047 3048#ifndef __PYX_HAVE_RT_ImportType 3049#define __PYX_HAVE_RT_ImportType 3050static PyTypeObject *__Pyx_ImportType(const char *module_name, const char *class_name, 3051 size_t size, int strict) 3052{ 3053 PyObject *py_module = 0; 3054 PyObject *result = 0; 3055 PyObject *py_name = 0; 3056 char warning[200]; 3057 py_module = __Pyx_ImportModule(module_name); 3058 if (!py_module) 3059 goto bad; 3060 py_name = __Pyx_PyIdentifier_FromString(class_name); 3061 if (!py_name) 3062 goto bad; 3063 result = PyObject_GetAttr(py_module, py_name); 3064 Py_DECREF(py_name); 3065 py_name = 0; 3066 Py_DECREF(py_module); 3067 py_module = 0; 3068 if (!result) 3069 goto bad; 3070 if (!PyType_Check(result)) { 3071 PyErr_Format(PyExc_TypeError, 3072 "%s.%s is not a type object", 3073 module_name, class_name); 3074 goto bad; 3075 } 3076 if (!strict && (size_t)((PyTypeObject *)result)->tp_basicsize > size) { 3077 PyOS_snprintf(warning, sizeof(warning), 3078 "%s.%s size changed, may indicate binary incompatibility", 3079 module_name, class_name); 3080 #if PY_VERSION_HEX < 0x02050000 3081 if (PyErr_Warn(NULL, warning) < 0) goto bad; 3082 #else 3083 if (PyErr_WarnEx(NULL, warning, 0) < 0) goto bad; 3084 #endif 3085 } 3086 else if ((size_t)((PyTypeObject *)result)->tp_basicsize != size) { 3087 PyErr_Format(PyExc_ValueError, 3088 "%s.%s has the wrong size, try recompiling", 3089 module_name, class_name); 3090 goto bad; 3091 } 3092 return (PyTypeObject *)result; 3093bad: 3094 Py_XDECREF(py_module); 3095 Py_XDECREF(result); 3096 return NULL; 3097} 3098#endif 3099 3100static void* __Pyx_GetVtable(PyObject *dict) { 3101 void* ptr; 3102 PyObject *ob = PyMapping_GetItemString(dict, (char *)"__pyx_vtable__"); 3103 if (!ob) 3104 goto bad; 3105#if PY_VERSION_HEX >= 0x02070000 && !(PY_MAJOR_VERSION==3&&PY_MINOR_VERSION==0) 3106 ptr = PyCapsule_GetPointer(ob, 0); 3107#else 3108 ptr = PyCObject_AsVoidPtr(ob); 3109#endif 3110 if (!ptr && !PyErr_Occurred()) 3111 PyErr_SetString(PyExc_RuntimeError, "invalid vtable found for imported type"); 3112 Py_DECREF(ob); 3113 return ptr; 3114bad: 3115 Py_XDECREF(ob); 3116 return NULL; 3117} 3118 3119static int __pyx_bisect_code_objects(__Pyx_CodeObjectCacheEntry* entries, int count, int code_line) { 3120 int start = 0, mid = 0, end = count - 1; 3121 if (end >= 0 && code_line > entries[end].code_line) { 3122 return count; 3123 } 3124 while (start < end) { 3125 mid = (start + end) / 2; 3126 if (code_line < entries[mid].code_line) { 3127 end = mid; 3128 } else if (code_line > entries[mid].code_line) { 3129 start = mid + 1; 3130 } else { 3131 return mid; 3132 } 3133 } 3134 if (code_line <= entries[mid].code_line) { 3135 return mid; 3136 } else { 3137 return mid + 1; 3138 } 3139} 3140static PyCodeObject *__pyx_find_code_object(int code_line) { 3141 PyCodeObject* code_object; 3142 int pos; 3143 if (unlikely(!code_line) || unlikely(!__pyx_code_cache.entries)) { 3144 return NULL; 3145 } 3146 pos = __pyx_bisect_code_objects(__pyx_code_cache.entries, __pyx_code_cache.count, code_line); 3147 if (unlikely(pos >= __pyx_code_cache.count) || unlikely(__pyx_code_cache.entries[pos].code_line != code_line)) { 3148 return NULL; 3149 } 3150 code_object = __pyx_code_cache.entries[pos].code_object; 3151 Py_INCREF(code_object); 3152 return code_object; 3153} 3154static void __pyx_insert_code_object(int code_line, PyCodeObject* code_object) { 3155 int pos, i; 3156 __Pyx_CodeObjectCacheEntry* entries = __pyx_code_cache.entries; 3157 if (unlikely(!code_line)) { 3158 return; 3159 } 3160 if (unlikely(!entries)) { 3161 entries = (__Pyx_CodeObjectCacheEntry*)PyMem_Malloc(64*sizeof(__Pyx_CodeObjectCacheEntry)); 3162 if (likely(entries)) { 3163 __pyx_code_cache.entries = entries; 3164 __pyx_code_cache.max_count = 64; 3165 __pyx_code_cache.count = 1; 3166 entries[0].code_line = code_line; 3167 entries[0].code_object = code_object; 3168 Py_INCREF(code_object); 3169 } 3170 return; 3171 } 3172 pos = __pyx_bisect_code_objects(__pyx_code_cache.entries, __pyx_code_cache.count, code_line); 3173 if ((pos < __pyx_code_cache.count) && unlikely(__pyx_code_cache.entries[pos].code_line == code_line)) { 3174 PyCodeObject* tmp = entries[pos].code_object; 3175 entries[pos].code_object = code_object; 3176 Py_DECREF(tmp); 3177 return; 3178 } 3179 if (__pyx_code_cache.count == __pyx_code_cache.max_count) { 3180 int new_max = __pyx_code_cache.max_count + 64; 3181 entries = (__Pyx_CodeObjectCacheEntry*)PyMem_Realloc( 3182 __pyx_code_cache.entries, new_max*sizeof(__Pyx_CodeObjectCacheEntry)); 3183 if (unlikely(!entries)) { 3184 return; 3185 } 3186 __pyx_code_cache.entries = entries; 3187 __pyx_code_cache.max_count = new_max; 3188 } 3189 for (i=__pyx_code_cache.count; i>pos; i--) { 3190 entries[i] = entries[i-1]; 3191 } 3192 entries[pos].code_line = code_line; 3193 entries[pos].code_object = code_object; 3194 __pyx_code_cache.count++; 3195 Py_INCREF(code_object); 3196} 3197 3198#include "compile.h" 3199#include "frameobject.h" 3200#include "traceback.h" 3201static PyCodeObject* __Pyx_CreateCodeObjectForTraceback( 3202 const char *funcname, int c_line, 3203 int py_line, const char *filename) { 3204 PyCodeObject *py_code = 0; 3205 PyObject *py_srcfile = 0; 3206 PyObject *py_funcname = 0; 3207 #if PY_MAJOR_VERSION < 3 3208 py_srcfile = PyString_FromString(filename); 3209 #else 3210 py_srcfile = PyUnicode_FromString(filename); 3211 #endif 3212 if (!py_srcfile) goto bad; 3213 if (c_line) { 3214 #if PY_MAJOR_VERSION < 3 3215 py_funcname = PyString_FromFormat( "%s (%s:%d)", funcname, __pyx_cfilenm, c_line); 3216 #else 3217 py_funcname = PyUnicode_FromFormat( "%s (%s:%d)", funcname, __pyx_cfilenm, c_line); 3218 #endif 3219 } 3220 else { 3221 #if PY_MAJOR_VERSION < 3 3222 py_funcname = PyString_FromString(funcname); 3223 #else 3224 py_funcname = PyUnicode_FromString(funcname); 3225 #endif 3226 } 3227 if (!py_funcname) goto bad; 3228 py_code = __Pyx_PyCode_New( 3229 0, /*int argcount,*/ 3230 0, /*int kwonlyargcount,*/ 3231 0, /*int nlocals,*/ 3232 0, /*int stacksize,*/ 3233 0, /*int flags,*/ 3234 __pyx_empty_bytes, /*PyObject *code,*/ 3235 __pyx_empty_tuple, /*PyObject *consts,*/ 3236 __pyx_empty_tuple, /*PyObject *names,*/ 3237 __pyx_empty_tuple, /*PyObject *varnames,*/ 3238 __pyx_empty_tuple, /*PyObject *freevars,*/ 3239 __pyx_empty_tuple, /*PyObject *cellvars,*/ 3240 py_srcfile, /*PyObject *filename,*/ 3241 py_funcname, /*PyObject *name,*/ 3242 py_line, /*int firstlineno,*/ 3243 __pyx_empty_bytes /*PyObject *lnotab*/ 3244 ); 3245 Py_DECREF(py_srcfile); 3246 Py_DECREF(py_funcname); 3247 return py_code; 3248bad: 3249 Py_XDECREF(py_srcfile); 3250 Py_XDECREF(py_funcname); 3251 return NULL; 3252} 3253static void __Pyx_AddTraceback(const char *funcname, int c_line, 3254 int py_line, const char *filename) { 3255 PyCodeObject *py_code = 0; 3256 PyObject *py_globals = 0; 3257 PyFrameObject *py_frame = 0; 3258 py_code = __pyx_find_code_object(c_line ? c_line : py_line); 3259 if (!py_code) { 3260 py_code = __Pyx_CreateCodeObjectForTraceback( 3261 funcname, c_line, py_line, filename); 3262 if (!py_code) goto bad; 3263 __pyx_insert_code_object(c_line ? c_line : py_line, py_code); 3264 } 3265 py_globals = PyModule_GetDict(__pyx_m); 3266 if (!py_globals) goto bad; 3267 py_frame = PyFrame_New( 3268 PyThreadState_GET(), /*PyThreadState *tstate,*/ 3269 py_code, /*PyCodeObject *code,*/ 3270 py_globals, /*PyObject *globals,*/ 3271 0 /*PyObject *locals*/ 3272 ); 3273 if (!py_frame) goto bad; 3274 py_frame->f_lineno = py_line; 3275 PyTraceBack_Here(py_frame); 3276bad: 3277 Py_XDECREF(py_code); 3278 Py_XDECREF(py_frame); 3279} 3280 3281static int __Pyx_InitStrings(__Pyx_StringTabEntry *t) { 3282 while (t->p) { 3283 #if PY_MAJOR_VERSION < 3 3284 if (t->is_unicode) { 3285 *t->p = PyUnicode_DecodeUTF8(t->s, t->n - 1, NULL); 3286 } else if (t->intern) { 3287 *t->p = PyString_InternFromString(t->s); 3288 } else { 3289 *t->p = PyString_FromStringAndSize(t->s, t->n - 1); 3290 } 3291 #else /* Python 3+ has unicode identifiers */ 3292 if (t->is_unicode | t->is_str) { 3293 if (t->intern) { 3294 *t->p = PyUnicode_InternFromString(t->s); 3295 } else if (t->encoding) { 3296 *t->p = PyUnicode_Decode(t->s, t->n - 1, t->encoding, NULL); 3297 } else { 3298 *t->p = PyUnicode_FromStringAndSize(t->s, t->n - 1); 3299 } 3300 } else { 3301 *t->p = PyBytes_FromStringAndSize(t->s, t->n - 1); 3302 } 3303 #endif 3304 if (!*t->p) 3305 return -1; 3306 ++t; 3307 } 3308 return 0; 3309} 3310 3311 3312/* Type Conversion Functions */ 3313 3314static CYTHON_INLINE int __Pyx_PyObject_IsTrue(PyObject* x) { 3315 int is_true = x == Py_True; 3316 if (is_true | (x == Py_False) | (x == Py_None)) return is_true; 3317 else return PyObject_IsTrue(x); 3318} 3319 3320static CYTHON_INLINE PyObject* __Pyx_PyNumber_Int(PyObject* x) { 3321 PyNumberMethods *m; 3322 const char *name = NULL; 3323 PyObject *res = NULL; 3324#if PY_VERSION_HEX < 0x03000000 3325 if (PyInt_Check(x) || PyLong_Check(x)) 3326#else 3327 if (PyLong_Check(x)) 3328#endif 3329 return Py_INCREF(x), x; 3330 m = Py_TYPE(x)->tp_as_number; 3331#if PY_VERSION_HEX < 0x03000000 3332 if (m && m->nb_int) { 3333 name = "int"; 3334 res = PyNumber_Int(x); 3335 } 3336 else if (m && m->nb_long) { 3337 name = "long"; 3338 res = PyNumber_Long(x); 3339 } 3340#else 3341 if (m && m->nb_int) { 3342 name = "int"; 3343 res = PyNumber_Long(x); 3344 } 3345#endif 3346 if (res) { 3347#if PY_VERSION_HEX < 0x03000000 3348 if (!PyInt_Check(res) && !PyLong_Check(res)) { 3349#else 3350 if (!PyLong_Check(res)) { 3351#endif 3352 PyErr_Format(PyExc_TypeError, 3353 "__%s__ returned non-%s (type %.200s)", 3354 name, name, Py_TYPE(res)->tp_name); 3355 Py_DECREF(res); 3356 return NULL; 3357 } 3358 } 3359 else if (!PyErr_Occurred()) { 3360 PyErr_SetString(PyExc_TypeError, 3361 "an integer is required"); 3362 } 3363 return res; 3364} 3365 3366static CYTHON_INLINE Py_ssize_t __Pyx_PyIndex_AsSsize_t(PyObject* b) { 3367 Py_ssize_t ival; 3368 PyObject* x = PyNumber_Index(b); 3369 if (!x) return -1; 3370 ival = PyInt_AsSsize_t(x); 3371 Py_DECREF(x); 3372 return ival; 3373} 3374 3375static CYTHON_INLINE PyObject * __Pyx_PyInt_FromSize_t(size_t ival) { 3376#if PY_VERSION_HEX < 0x02050000 3377 if (ival <= LONG_MAX) 3378 return PyInt_FromLong((long)ival); 3379 else { 3380 unsigned char *bytes = (unsigned char *) &ival; 3381 int one = 1; int little = (int)*(unsigned char*)&one; 3382 return _PyLong_FromByteArray(bytes, sizeof(size_t), little, 0); 3383 } 3384#else 3385 return PyInt_FromSize_t(ival); 3386#endif 3387} 3388 3389static CYTHON_INLINE size_t __Pyx_PyInt_AsSize_t(PyObject* x) { 3390 unsigned PY_LONG_LONG val = __Pyx_PyInt_AsUnsignedLongLong(x); 3391 if (unlikely(val == (unsigned PY_LONG_LONG)-1 && PyErr_Occurred())) { 3392 return (size_t)-1; 3393 } else if (unlikely(val != (unsigned PY_LONG_LONG)(size_t)val)) { 3394 PyErr_SetString(PyExc_OverflowError, 3395 "value too large to convert to size_t"); 3396 return (size_t)-1; 3397 } 3398 return (size_t)val; 3399} 3400 3401 3402#endif /* Py_PYTHON_H */ 3403