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__cwalker 253 #define __PYX_HAVE_API__bintrees__cwalker 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 293 typedef 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)) 303 static CYTHON_INLINE int __Pyx_PyObject_IsTrue(PyObject*); 304 static CYTHON_INLINE PyObject* __Pyx_PyNumber_Int(PyObject* x); 305 306 static CYTHON_INLINE Py_ssize_t __Pyx_PyIndex_AsSsize_t(PyObject*); 307 static CYTHON_INLINE PyObject * __Pyx_PyInt_FromSize_t(size_t); 308 static 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 331 static PyObject *__pyx_m; 332 static PyObject *__pyx_b; 333 static PyObject *__pyx_empty_tuple; 334 static PyObject *__pyx_empty_bytes; 335 static int __pyx_lineno; 336 static int __pyx_clineno = 0; 337 static const char * __pyx_cfilenm= __FILE__; 338 static const char *__pyx_filename; 339 340 341 static const char *__pyx_f[] = { 342 "cwalker.pyx", 343 }; 344 345 /*--- Type declarations ---*/ 346 struct __pyx_obj_8bintrees_7cwalker_cWalker; 347 348 /* "bintrees\cwalker.pxd":11 349 * from stack cimport node_stack_t 350 * 351 * cdef class cWalker: # <<<<<<<<<<<<<< 352 * cdef node_t *node 353 * cdef node_t *root 354 */ 355 struct __pyx_obj_8bintrees_7cwalker_cWalker { 356 PyObject_HEAD 357 struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker *__pyx_vtab; 358 node_t *node; 359 node_t *root; 360 node_stack_t *stack; 361 }; 362 363 364 365 /* "bintrees\cwalker.pyx":14 366 * from ctrees cimport * 367 * 368 * cdef class cWalker: # <<<<<<<<<<<<<< 369 * def __cinit__(self): 370 * self.root = NULL 371 */ 372 373 struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker { 374 void (*set_tree)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, node_t *); 375 PyObject *(*reset)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, int __pyx_skip_dispatch); 376 PyObject *(*push)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, int __pyx_skip_dispatch); 377 PyObject *(*pop)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, int __pyx_skip_dispatch); 378 }; 379 static struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker *__pyx_vtabptr_8bintrees_7cwalker_cWalker; 380 #ifndef CYTHON_REFNANNY 381 #define CYTHON_REFNANNY 0 382 #endif 383 #if CYTHON_REFNANNY 384 typedef struct { 385 void (*INCREF)(void*, PyObject*, int); 386 void (*DECREF)(void*, PyObject*, int); 387 void (*GOTREF)(void*, PyObject*, int); 388 void (*GIVEREF)(void*, PyObject*, int); 389 void* (*SetupContext)(const char*, int, const char*); 390 void (*FinishContext)(void**); 391 } __Pyx_RefNannyAPIStruct; 392 static __Pyx_RefNannyAPIStruct *__Pyx_RefNanny = NULL; 393 static __Pyx_RefNannyAPIStruct *__Pyx_RefNannyImportAPI(const char *modname); /*proto*/ 394 #define __Pyx_RefNannyDeclarations void *__pyx_refnanny = NULL; 395 #ifdef WITH_THREAD 396 #define __Pyx_RefNannySetupContext(name, acquire_gil) \ 397 if (acquire_gil) { \ 398 PyGILState_STATE __pyx_gilstate_save = PyGILState_Ensure(); \ 399 __pyx_refnanny = __Pyx_RefNanny->SetupContext((name), __LINE__, __FILE__); \ 400 PyGILState_Release(__pyx_gilstate_save); \ 401 } else { \ 402 __pyx_refnanny = __Pyx_RefNanny->SetupContext((name), __LINE__, __FILE__); \ 403 } 404 #else 405 #define __Pyx_RefNannySetupContext(name, acquire_gil) \ 406 __pyx_refnanny = __Pyx_RefNanny->SetupContext((name), __LINE__, __FILE__) 407 #endif 408 #define __Pyx_RefNannyFinishContext() \ 409 __Pyx_RefNanny->FinishContext(&__pyx_refnanny) 410 #define __Pyx_INCREF(r) __Pyx_RefNanny->INCREF(__pyx_refnanny, (PyObject *)(r), __LINE__) 411 #define __Pyx_DECREF(r) __Pyx_RefNanny->DECREF(__pyx_refnanny, (PyObject *)(r), __LINE__) 412 #define __Pyx_GOTREF(r) __Pyx_RefNanny->GOTREF(__pyx_refnanny, (PyObject *)(r), __LINE__) 413 #define __Pyx_GIVEREF(r) __Pyx_RefNanny->GIVEREF(__pyx_refnanny, (PyObject *)(r), __LINE__) 414 #define __Pyx_XINCREF(r) do { if((r) != NULL) {__Pyx_INCREF(r); }} while(0) 415 #define __Pyx_XDECREF(r) do { if((r) != NULL) {__Pyx_DECREF(r); }} while(0) 416 #define __Pyx_XGOTREF(r) do { if((r) != NULL) {__Pyx_GOTREF(r); }} while(0) 417 #define __Pyx_XGIVEREF(r) do { if((r) != NULL) {__Pyx_GIVEREF(r);}} while(0) 418 #else 419 #define __Pyx_RefNannyDeclarations 420 #define __Pyx_RefNannySetupContext(name, acquire_gil) 421 #define __Pyx_RefNannyFinishContext() 422 #define __Pyx_INCREF(r) Py_INCREF(r) 423 #define __Pyx_DECREF(r) Py_DECREF(r) 424 #define __Pyx_GOTREF(r) 425 #define __Pyx_GIVEREF(r) 426 #define __Pyx_XINCREF(r) Py_XINCREF(r) 427 #define __Pyx_XDECREF(r) Py_XDECREF(r) 428 #define __Pyx_XGOTREF(r) 429 #define __Pyx_XGIVEREF(r) 430 #endif /* CYTHON_REFNANNY */ 431 #define __Pyx_CLEAR(r) do { PyObject* tmp = ((PyObject*)(r)); r = NULL; __Pyx_DECREF(tmp);} while(0) 432 #define __Pyx_XCLEAR(r) do { if((r) != NULL) {PyObject* tmp = ((PyObject*)(r)); r = NULL; __Pyx_DECREF(tmp);}} while(0) 433 434 static PyObject *__Pyx_GetName(PyObject *dict, PyObject *name); /*proto*/ 435 436 static void __Pyx_RaiseArgtupleInvalid(const char* func_name, int exact, 437 Py_ssize_t num_min, Py_ssize_t num_max, Py_ssize_t num_found); /*proto*/ 438 439 static CYTHON_INLINE int __Pyx_CheckKeywordStrings(PyObject *kwdict, const char* function_name, int kw_allowed); /*proto*/ 440 441 static CYTHON_INLINE void __Pyx_ErrRestore(PyObject *type, PyObject *value, PyObject *tb); /*proto*/ 442 static CYTHON_INLINE void __Pyx_ErrFetch(PyObject **type, PyObject **value, PyObject **tb); /*proto*/ 443 444 static void __Pyx_Raise(PyObject *type, PyObject *value, PyObject *tb, PyObject *cause); /*proto*/ 445 446 static CYTHON_INLINE unsigned char __Pyx_PyInt_AsUnsignedChar(PyObject *); 447 448 static CYTHON_INLINE unsigned short __Pyx_PyInt_AsUnsignedShort(PyObject *); 449 450 static CYTHON_INLINE unsigned int __Pyx_PyInt_AsUnsignedInt(PyObject *); 451 452 static CYTHON_INLINE char __Pyx_PyInt_AsChar(PyObject *); 453 454 static CYTHON_INLINE short __Pyx_PyInt_AsShort(PyObject *); 455 456 static CYTHON_INLINE int __Pyx_PyInt_AsInt(PyObject *); 457 458 static CYTHON_INLINE signed char __Pyx_PyInt_AsSignedChar(PyObject *); 459 460 static CYTHON_INLINE signed short __Pyx_PyInt_AsSignedShort(PyObject *); 461 462 static CYTHON_INLINE signed int __Pyx_PyInt_AsSignedInt(PyObject *); 463 464 static CYTHON_INLINE int __Pyx_PyInt_AsLongDouble(PyObject *); 465 466 static CYTHON_INLINE unsigned long __Pyx_PyInt_AsUnsignedLong(PyObject *); 467 468 static CYTHON_INLINE unsigned PY_LONG_LONG __Pyx_PyInt_AsUnsignedLongLong(PyObject *); 469 470 static CYTHON_INLINE long __Pyx_PyInt_AsLong(PyObject *); 471 472 static CYTHON_INLINE PY_LONG_LONG __Pyx_PyInt_AsLongLong(PyObject *); 473 474 static CYTHON_INLINE signed long __Pyx_PyInt_AsSignedLong(PyObject *); 475 476 static CYTHON_INLINE signed PY_LONG_LONG __Pyx_PyInt_AsSignedLongLong(PyObject *); 477 478 static void __Pyx_WriteUnraisable(const char *name, int clineno, 479 int lineno, const char *filename); /*proto*/ 480 481 static int __Pyx_check_binary_version(void); 482 483 static int __Pyx_SetVtable(PyObject *dict, void *vtable); /*proto*/ 484 485 typedef struct { 486 int code_line; 487 PyCodeObject* code_object; 488 } __Pyx_CodeObjectCacheEntry; 489 struct __Pyx_CodeObjectCache { 490 int count; 491 int max_count; 492 __Pyx_CodeObjectCacheEntry* entries; 493 }; 494 static struct __Pyx_CodeObjectCache __pyx_code_cache = {0,0,NULL}; 495 static int __pyx_bisect_code_objects(__Pyx_CodeObjectCacheEntry* entries, int count, int code_line); 496 static PyCodeObject *__pyx_find_code_object(int code_line); 497 static void __pyx_insert_code_object(int code_line, PyCodeObject* code_object); 498 499 static void __Pyx_AddTraceback(const char *funcname, int c_line, 500 int py_line, const char *filename); /*proto*/ 501 502 static int __Pyx_InitStrings(__Pyx_StringTabEntry *t); /*proto*/ 503 504 505 /* Module declarations from 'bintrees.ctrees' */ 506 507 /* Module declarations from 'bintrees.stack' */ 508 509 /* Module declarations from 'bintrees.cwalker' */ 510 static PyTypeObject *__pyx_ptype_8bintrees_7cwalker_cWalker = 0; 511 #define __Pyx_MODULE_NAME "bintrees.cwalker" 512 int __pyx_module_is_main_bintrees__cwalker = 0; 513 514 /* Implementation of 'bintrees.cwalker' */ 515 static PyObject *__pyx_builtin_property; 516 static PyObject *__pyx_builtin_IndexError; 517 static PyObject *__pyx_builtin_KeyError; 518 static int __pyx_pf_8bintrees_7cwalker_7cWalker___cinit__(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 519 static void __pyx_pf_8bintrees_7cwalker_7cWalker_2__dealloc__(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 520 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_4reset(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 521 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_6key(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 522 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_8value(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 523 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_10item(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 524 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_12is_valid(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 525 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_14goto(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, PyObject *__pyx_v_key); /* proto */ 526 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_16push(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 527 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_18pop(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 528 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_20stack_is_empty(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 529 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_22goto_leaf(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 530 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_24has_child(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, int __pyx_v_direction); /* proto */ 531 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_26down(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, int __pyx_v_direction); /* proto */ 532 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_28go_left(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 533 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_30go_right(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 534 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_32has_left(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 535 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_34has_right(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self); /* proto */ 536 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_36succ_item(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, PyObject *__pyx_v_key); /* proto */ 537 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_38prev_item(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, PyObject *__pyx_v_key); /* proto */ 538 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_40floor_item(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, PyObject *__pyx_v_key); /* proto */ 539 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_42ceiling_item(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, PyObject *__pyx_v_key); /* proto */ 540 static char __pyx_k_1[] = "pop(): stack is empty"; 541 static char __pyx_k__key[] = "key"; 542 static char __pyx_k__pop[] = "pop"; 543 static char __pyx_k__item[] = "item"; 544 static char __pyx_k__push[] = "push"; 545 static char __pyx_k__reset[] = "reset"; 546 static char __pyx_k__value[] = "value"; 547 static char __pyx_k__KeyError[] = "KeyError"; 548 static char __pyx_k____main__[] = "__main__"; 549 static char __pyx_k____test__[] = "__test__"; 550 static char __pyx_k__is_valid[] = "is_valid"; 551 static char __pyx_k__property[] = "property"; 552 static char __pyx_k__IndexError[] = "IndexError"; 553 static PyObject *__pyx_kp_s_1; 554 static PyObject *__pyx_n_s__IndexError; 555 static PyObject *__pyx_n_s__KeyError; 556 static PyObject *__pyx_n_s____main__; 557 static PyObject *__pyx_n_s____test__; 558 static PyObject *__pyx_n_s__is_valid; 559 static PyObject *__pyx_n_s__item; 560 static PyObject *__pyx_n_s__key; 561 static PyObject *__pyx_n_s__pop; 562 static PyObject *__pyx_n_s__property; 563 static PyObject *__pyx_n_s__push; 564 static PyObject *__pyx_n_s__reset; 565 static PyObject *__pyx_n_s__value; 566 static PyObject *__pyx_k_tuple_2; 567 568 /* Python wrapper */ 569 static int __pyx_pw_8bintrees_7cwalker_7cWalker_1__cinit__(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/ 570 static int __pyx_pw_8bintrees_7cwalker_7cWalker_1__cinit__(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds) { 571 int __pyx_r; 572 __Pyx_RefNannyDeclarations 573 __Pyx_RefNannySetupContext("__cinit__ (wrapper)", 0); 574 if (unlikely(PyTuple_GET_SIZE(__pyx_args) > 0)) { 575 __Pyx_RaiseArgtupleInvalid("__cinit__", 1, 0, 0, PyTuple_GET_SIZE(__pyx_args)); return -1;} 576 if (unlikely(__pyx_kwds) && unlikely(PyDict_Size(__pyx_kwds) > 0) && unlikely(!__Pyx_CheckKeywordStrings(__pyx_kwds, "__cinit__", 0))) return -1; 577 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker___cinit__(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 578 __Pyx_RefNannyFinishContext(); 579 return __pyx_r; 580 } 581 582 /* "bintrees\cwalker.pyx":15 583 * 584 * cdef class cWalker: 585 * def __cinit__(self): # <<<<<<<<<<<<<< 586 * self.root = NULL 587 * self.node = NULL 588 */ 589 590 static int __pyx_pf_8bintrees_7cwalker_7cWalker___cinit__(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 591 int __pyx_r; 592 __Pyx_RefNannyDeclarations 593 __Pyx_RefNannySetupContext("__cinit__", 0); 594 595 /* "bintrees\cwalker.pyx":16 596 * cdef class cWalker: 597 * def __cinit__(self): 598 * self.root = NULL # <<<<<<<<<<<<<< 599 * self.node = NULL 600 * self.stack = stack_init(MAXSTACK) 601 */ 602 __pyx_v_self->root = NULL; 603 604 /* "bintrees\cwalker.pyx":17 605 * def __cinit__(self): 606 * self.root = NULL 607 * self.node = NULL # <<<<<<<<<<<<<< 608 * self.stack = stack_init(MAXSTACK) 609 * 610 */ 611 __pyx_v_self->node = NULL; 612 613 /* "bintrees\cwalker.pyx":18 614 * self.root = NULL 615 * self.node = NULL 616 * self.stack = stack_init(MAXSTACK) # <<<<<<<<<<<<<< 617 * 618 * def __dealloc__(self): 619 */ 620 __pyx_v_self->stack = stack_init(32); 621 622 __pyx_r = 0; 623 __Pyx_RefNannyFinishContext(); 624 return __pyx_r; 625 } 626 627 /* Python wrapper */ 628 static void __pyx_pw_8bintrees_7cwalker_7cWalker_3__dealloc__(PyObject *__pyx_v_self); /*proto*/ 629 static void __pyx_pw_8bintrees_7cwalker_7cWalker_3__dealloc__(PyObject *__pyx_v_self) { 630 __Pyx_RefNannyDeclarations 631 __Pyx_RefNannySetupContext("__dealloc__ (wrapper)", 0); 632 __pyx_pf_8bintrees_7cwalker_7cWalker_2__dealloc__(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 633 __Pyx_RefNannyFinishContext(); 634 } 635 636 /* "bintrees\cwalker.pyx":20 637 * self.stack = stack_init(MAXSTACK) 638 * 639 * def __dealloc__(self): # <<<<<<<<<<<<<< 640 * stack_delete(self.stack) 641 * 642 */ 643 644 static void __pyx_pf_8bintrees_7cwalker_7cWalker_2__dealloc__(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 645 __Pyx_RefNannyDeclarations 646 __Pyx_RefNannySetupContext("__dealloc__", 0); 647 648 /* "bintrees\cwalker.pyx":21 649 * 650 * def __dealloc__(self): 651 * stack_delete(self.stack) # <<<<<<<<<<<<<< 652 * 653 * cdef void set_tree(self, node_t *root): 654 */ 655 stack_delete(__pyx_v_self->stack); 656 657 __Pyx_RefNannyFinishContext(); 658 } 659 660 /* "bintrees\cwalker.pyx":23 661 * stack_delete(self.stack) 662 * 663 * cdef void set_tree(self, node_t *root): # <<<<<<<<<<<<<< 664 * self.root = root 665 * self.reset() 666 */ 667 668 static void __pyx_f_8bintrees_7cwalker_7cWalker_set_tree(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, node_t *__pyx_v_root) { 669 __Pyx_RefNannyDeclarations 670 PyObject *__pyx_t_1 = NULL; 671 int __pyx_lineno = 0; 672 const char *__pyx_filename = NULL; 673 int __pyx_clineno = 0; 674 __Pyx_RefNannySetupContext("set_tree", 0); 675 676 /* "bintrees\cwalker.pyx":24 677 * 678 * cdef void set_tree(self, node_t *root): 679 * self.root = root # <<<<<<<<<<<<<< 680 * self.reset() 681 * 682 */ 683 __pyx_v_self->root = __pyx_v_root; 684 685 /* "bintrees\cwalker.pyx":25 686 * cdef void set_tree(self, node_t *root): 687 * self.root = root 688 * self.reset() # <<<<<<<<<<<<<< 689 * 690 * cpdef reset(self): 691 */ 692 __pyx_t_1 = ((struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker *)__pyx_v_self->__pyx_vtab)->reset(__pyx_v_self, 0); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 25; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 693 __Pyx_GOTREF(__pyx_t_1); 694 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 695 696 goto __pyx_L0; 697 __pyx_L1_error:; 698 __Pyx_XDECREF(__pyx_t_1); 699 __Pyx_WriteUnraisable("bintrees.cwalker.cWalker.set_tree", __pyx_clineno, __pyx_lineno, __pyx_filename); 700 __pyx_L0:; 701 __Pyx_RefNannyFinishContext(); 702 } 703 704 /* "bintrees\cwalker.pyx":27 705 * self.reset() 706 * 707 * cpdef reset(self): # <<<<<<<<<<<<<< 708 * stack_reset(self.stack) 709 * self.node = self.root 710 */ 711 712 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_5reset(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 713 static PyObject *__pyx_f_8bintrees_7cwalker_7cWalker_reset(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, int __pyx_skip_dispatch) { 714 PyObject *__pyx_r = NULL; 715 __Pyx_RefNannyDeclarations 716 PyObject *__pyx_t_1 = NULL; 717 PyObject *__pyx_t_2 = NULL; 718 node_t *__pyx_t_3; 719 int __pyx_lineno = 0; 720 const char *__pyx_filename = NULL; 721 int __pyx_clineno = 0; 722 __Pyx_RefNannySetupContext("reset", 0); 723 /* Check if called by wrapper */ 724 if (unlikely(__pyx_skip_dispatch)) ; 725 /* Check if overriden in Python */ 726 else if (unlikely(Py_TYPE(((PyObject *)__pyx_v_self))->tp_dictoffset != 0)) { 727 __pyx_t_1 = PyObject_GetAttr(((PyObject *)__pyx_v_self), __pyx_n_s__reset); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 27; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 728 __Pyx_GOTREF(__pyx_t_1); 729 if (!PyCFunction_Check(__pyx_t_1) || (PyCFunction_GET_FUNCTION(__pyx_t_1) != (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_5reset)) { 730 __Pyx_XDECREF(__pyx_r); 731 __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 = 27; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 732 __Pyx_GOTREF(__pyx_t_2); 733 __pyx_r = __pyx_t_2; 734 __pyx_t_2 = 0; 735 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 736 goto __pyx_L0; 737 } 738 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 739 } 740 741 /* "bintrees\cwalker.pyx":28 742 * 743 * cpdef reset(self): 744 * stack_reset(self.stack) # <<<<<<<<<<<<<< 745 * self.node = self.root 746 * 747 */ 748 stack_reset(__pyx_v_self->stack); 749 750 /* "bintrees\cwalker.pyx":29 751 * cpdef reset(self): 752 * stack_reset(self.stack) 753 * self.node = self.root # <<<<<<<<<<<<<< 754 * 755 * @property 756 */ 757 __pyx_t_3 = __pyx_v_self->root; 758 __pyx_v_self->node = __pyx_t_3; 759 760 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 761 goto __pyx_L0; 762 __pyx_L1_error:; 763 __Pyx_XDECREF(__pyx_t_1); 764 __Pyx_XDECREF(__pyx_t_2); 765 __Pyx_AddTraceback("bintrees.cwalker.cWalker.reset", __pyx_clineno, __pyx_lineno, __pyx_filename); 766 __pyx_r = 0; 767 __pyx_L0:; 768 __Pyx_XGIVEREF(__pyx_r); 769 __Pyx_RefNannyFinishContext(); 770 return __pyx_r; 771 } 772 773 /* Python wrapper */ 774 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_5reset(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 775 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_5reset(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 776 PyObject *__pyx_r = 0; 777 __Pyx_RefNannyDeclarations 778 __Pyx_RefNannySetupContext("reset (wrapper)", 0); 779 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_4reset(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 780 __Pyx_RefNannyFinishContext(); 781 return __pyx_r; 782 } 783 784 /* "bintrees\cwalker.pyx":27 785 * self.reset() 786 * 787 * cpdef reset(self): # <<<<<<<<<<<<<< 788 * stack_reset(self.stack) 789 * self.node = self.root 790 */ 791 792 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_4reset(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 793 PyObject *__pyx_r = NULL; 794 __Pyx_RefNannyDeclarations 795 PyObject *__pyx_t_1 = NULL; 796 int __pyx_lineno = 0; 797 const char *__pyx_filename = NULL; 798 int __pyx_clineno = 0; 799 __Pyx_RefNannySetupContext("reset", 0); 800 __Pyx_XDECREF(__pyx_r); 801 __pyx_t_1 = ((struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker *)__pyx_v_self->__pyx_vtab)->reset(__pyx_v_self, 1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 27; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 802 __Pyx_GOTREF(__pyx_t_1); 803 __pyx_r = __pyx_t_1; 804 __pyx_t_1 = 0; 805 goto __pyx_L0; 806 807 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 808 goto __pyx_L0; 809 __pyx_L1_error:; 810 __Pyx_XDECREF(__pyx_t_1); 811 __Pyx_AddTraceback("bintrees.cwalker.cWalker.reset", __pyx_clineno, __pyx_lineno, __pyx_filename); 812 __pyx_r = NULL; 813 __pyx_L0:; 814 __Pyx_XGIVEREF(__pyx_r); 815 __Pyx_RefNannyFinishContext(); 816 return __pyx_r; 817 } 818 819 /* Python wrapper */ 820 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_7key(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 821 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_7key(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 822 PyObject *__pyx_r = 0; 823 __Pyx_RefNannyDeclarations 824 __Pyx_RefNannySetupContext("key (wrapper)", 0); 825 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_6key(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 826 __Pyx_RefNannyFinishContext(); 827 return __pyx_r; 828 } 829 830 /* "bintrees\cwalker.pyx":32 831 * 832 * @property 833 * def key(self): # <<<<<<<<<<<<<< 834 * return <object> self.node.key 835 * 836 */ 837 838 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_6key(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 839 PyObject *__pyx_r = NULL; 840 __Pyx_RefNannyDeclarations 841 __Pyx_RefNannySetupContext("key", 0); 842 843 /* "bintrees\cwalker.pyx":33 844 * @property 845 * def key(self): 846 * return <object> self.node.key # <<<<<<<<<<<<<< 847 * 848 * @property 849 */ 850 __Pyx_XDECREF(__pyx_r); 851 __Pyx_INCREF(((PyObject *)__pyx_v_self->node->key)); 852 __pyx_r = ((PyObject *)__pyx_v_self->node->key); 853 goto __pyx_L0; 854 855 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 856 __pyx_L0:; 857 __Pyx_XGIVEREF(__pyx_r); 858 __Pyx_RefNannyFinishContext(); 859 return __pyx_r; 860 } 861 862 /* Python wrapper */ 863 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_9value(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 864 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_9value(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 865 PyObject *__pyx_r = 0; 866 __Pyx_RefNannyDeclarations 867 __Pyx_RefNannySetupContext("value (wrapper)", 0); 868 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_8value(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 869 __Pyx_RefNannyFinishContext(); 870 return __pyx_r; 871 } 872 873 /* "bintrees\cwalker.pyx":36 874 * 875 * @property 876 * def value(self): # <<<<<<<<<<<<<< 877 * return <object> self.node.value 878 * 879 */ 880 881 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_8value(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 882 PyObject *__pyx_r = NULL; 883 __Pyx_RefNannyDeclarations 884 __Pyx_RefNannySetupContext("value", 0); 885 886 /* "bintrees\cwalker.pyx":37 887 * @property 888 * def value(self): 889 * return <object> self.node.value # <<<<<<<<<<<<<< 890 * 891 * @property 892 */ 893 __Pyx_XDECREF(__pyx_r); 894 __Pyx_INCREF(((PyObject *)__pyx_v_self->node->value)); 895 __pyx_r = ((PyObject *)__pyx_v_self->node->value); 896 goto __pyx_L0; 897 898 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 899 __pyx_L0:; 900 __Pyx_XGIVEREF(__pyx_r); 901 __Pyx_RefNannyFinishContext(); 902 return __pyx_r; 903 } 904 905 /* Python wrapper */ 906 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_11item(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 907 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_11item(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 908 PyObject *__pyx_r = 0; 909 __Pyx_RefNannyDeclarations 910 __Pyx_RefNannySetupContext("item (wrapper)", 0); 911 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_10item(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 912 __Pyx_RefNannyFinishContext(); 913 return __pyx_r; 914 } 915 916 /* "bintrees\cwalker.pyx":40 917 * 918 * @property 919 * def item(self): # <<<<<<<<<<<<<< 920 * return (<object>self.node.key, <object>self.node.value) 921 * 922 */ 923 924 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_10item(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 925 PyObject *__pyx_r = NULL; 926 __Pyx_RefNannyDeclarations 927 PyObject *__pyx_t_1 = NULL; 928 int __pyx_lineno = 0; 929 const char *__pyx_filename = NULL; 930 int __pyx_clineno = 0; 931 __Pyx_RefNannySetupContext("item", 0); 932 933 /* "bintrees\cwalker.pyx":41 934 * @property 935 * def item(self): 936 * return (<object>self.node.key, <object>self.node.value) # <<<<<<<<<<<<<< 937 * 938 * @property 939 */ 940 __Pyx_XDECREF(__pyx_r); 941 __pyx_t_1 = PyTuple_New(2); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 41; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 942 __Pyx_GOTREF(__pyx_t_1); 943 __Pyx_INCREF(((PyObject *)__pyx_v_self->node->key)); 944 PyTuple_SET_ITEM(__pyx_t_1, 0, ((PyObject *)__pyx_v_self->node->key)); 945 __Pyx_GIVEREF(((PyObject *)__pyx_v_self->node->key)); 946 __Pyx_INCREF(((PyObject *)__pyx_v_self->node->value)); 947 PyTuple_SET_ITEM(__pyx_t_1, 1, ((PyObject *)__pyx_v_self->node->value)); 948 __Pyx_GIVEREF(((PyObject *)__pyx_v_self->node->value)); 949 __pyx_r = ((PyObject *)__pyx_t_1); 950 __pyx_t_1 = 0; 951 goto __pyx_L0; 952 953 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 954 goto __pyx_L0; 955 __pyx_L1_error:; 956 __Pyx_XDECREF(__pyx_t_1); 957 __Pyx_AddTraceback("bintrees.cwalker.cWalker.item", __pyx_clineno, __pyx_lineno, __pyx_filename); 958 __pyx_r = NULL; 959 __pyx_L0:; 960 __Pyx_XGIVEREF(__pyx_r); 961 __Pyx_RefNannyFinishContext(); 962 return __pyx_r; 963 } 964 965 /* Python wrapper */ 966 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_13is_valid(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 967 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_13is_valid(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 968 PyObject *__pyx_r = 0; 969 __Pyx_RefNannyDeclarations 970 __Pyx_RefNannySetupContext("is_valid (wrapper)", 0); 971 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_12is_valid(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 972 __Pyx_RefNannyFinishContext(); 973 return __pyx_r; 974 } 975 976 /* "bintrees\cwalker.pyx":44 977 * 978 * @property 979 * def is_valid(self): # <<<<<<<<<<<<<< 980 * return self.node != NULL 981 * 982 */ 983 984 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_12is_valid(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 985 PyObject *__pyx_r = NULL; 986 __Pyx_RefNannyDeclarations 987 PyObject *__pyx_t_1 = NULL; 988 int __pyx_lineno = 0; 989 const char *__pyx_filename = NULL; 990 int __pyx_clineno = 0; 991 __Pyx_RefNannySetupContext("is_valid", 0); 992 993 /* "bintrees\cwalker.pyx":45 994 * @property 995 * def is_valid(self): 996 * return self.node != NULL # <<<<<<<<<<<<<< 997 * 998 * def goto(self, key): 999 */ 1000 __Pyx_XDECREF(__pyx_r); 1001 __pyx_t_1 = __Pyx_PyBool_FromLong((__pyx_v_self->node != NULL)); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 45; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1002 __Pyx_GOTREF(__pyx_t_1); 1003 __pyx_r = __pyx_t_1; 1004 __pyx_t_1 = 0; 1005 goto __pyx_L0; 1006 1007 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1008 goto __pyx_L0; 1009 __pyx_L1_error:; 1010 __Pyx_XDECREF(__pyx_t_1); 1011 __Pyx_AddTraceback("bintrees.cwalker.cWalker.is_valid", __pyx_clineno, __pyx_lineno, __pyx_filename); 1012 __pyx_r = NULL; 1013 __pyx_L0:; 1014 __Pyx_XGIVEREF(__pyx_r); 1015 __Pyx_RefNannyFinishContext(); 1016 return __pyx_r; 1017 } 1018 1019 /* Python wrapper */ 1020 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_15goto(PyObject *__pyx_v_self, PyObject *__pyx_v_key); /*proto*/ 1021 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_15goto(PyObject *__pyx_v_self, PyObject *__pyx_v_key) { 1022 PyObject *__pyx_r = 0; 1023 __Pyx_RefNannyDeclarations 1024 __Pyx_RefNannySetupContext("goto (wrapper)", 0); 1025 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_14goto(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self), ((PyObject *)__pyx_v_key)); 1026 __Pyx_RefNannyFinishContext(); 1027 return __pyx_r; 1028 } 1029 1030 /* "bintrees\cwalker.pyx":47 1031 * return self.node != NULL 1032 * 1033 * def goto(self, key): # <<<<<<<<<<<<<< 1034 * cdef int cval 1035 * self.node = self.root 1036 */ 1037 1038 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_14goto(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, PyObject *__pyx_v_key) { 1039 int __pyx_v_cval; 1040 PyObject *__pyx_r = NULL; 1041 __Pyx_RefNannyDeclarations 1042 node_t *__pyx_t_1; 1043 int __pyx_t_2; 1044 PyObject *__pyx_t_3 = NULL; 1045 int __pyx_lineno = 0; 1046 const char *__pyx_filename = NULL; 1047 int __pyx_clineno = 0; 1048 __Pyx_RefNannySetupContext("goto", 0); 1049 1050 /* "bintrees\cwalker.pyx":49 1051 * def goto(self, key): 1052 * cdef int cval 1053 * self.node = self.root # <<<<<<<<<<<<<< 1054 * while self.node != NULL: 1055 * cval = ct_compare(key, <object> self.node.key) 1056 */ 1057 __pyx_t_1 = __pyx_v_self->root; 1058 __pyx_v_self->node = __pyx_t_1; 1059 1060 /* "bintrees\cwalker.pyx":50 1061 * cdef int cval 1062 * self.node = self.root 1063 * while self.node != NULL: # <<<<<<<<<<<<<< 1064 * cval = ct_compare(key, <object> self.node.key) 1065 * if cval == 0: 1066 */ 1067 while (1) { 1068 __pyx_t_2 = (__pyx_v_self->node != NULL); 1069 if (!__pyx_t_2) break; 1070 1071 /* "bintrees\cwalker.pyx":51 1072 * self.node = self.root 1073 * while self.node != NULL: 1074 * cval = ct_compare(key, <object> self.node.key) # <<<<<<<<<<<<<< 1075 * if cval == 0: 1076 * return True 1077 */ 1078 __pyx_t_3 = ((PyObject *)__pyx_v_self->node->key); 1079 __Pyx_INCREF(__pyx_t_3); 1080 __pyx_v_cval = ct_compare(__pyx_v_key, __pyx_t_3); 1081 __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; 1082 1083 /* "bintrees\cwalker.pyx":52 1084 * while self.node != NULL: 1085 * cval = ct_compare(key, <object> self.node.key) 1086 * if cval == 0: # <<<<<<<<<<<<<< 1087 * return True 1088 * elif cval < 0: 1089 */ 1090 __pyx_t_2 = (__pyx_v_cval == 0); 1091 if (__pyx_t_2) { 1092 1093 /* "bintrees\cwalker.pyx":53 1094 * cval = ct_compare(key, <object> self.node.key) 1095 * if cval == 0: 1096 * return True # <<<<<<<<<<<<<< 1097 * elif cval < 0: 1098 * self.node = self.node.link[0] 1099 */ 1100 __Pyx_XDECREF(__pyx_r); 1101 __pyx_t_3 = __Pyx_PyBool_FromLong(1); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 53; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1102 __Pyx_GOTREF(__pyx_t_3); 1103 __pyx_r = __pyx_t_3; 1104 __pyx_t_3 = 0; 1105 goto __pyx_L0; 1106 goto __pyx_L5; 1107 } 1108 1109 /* "bintrees\cwalker.pyx":54 1110 * if cval == 0: 1111 * return True 1112 * elif cval < 0: # <<<<<<<<<<<<<< 1113 * self.node = self.node.link[0] 1114 * else: 1115 */ 1116 __pyx_t_2 = (__pyx_v_cval < 0); 1117 if (__pyx_t_2) { 1118 1119 /* "bintrees\cwalker.pyx":55 1120 * return True 1121 * elif cval < 0: 1122 * self.node = self.node.link[0] # <<<<<<<<<<<<<< 1123 * else: 1124 * self.node = self.node.link[1] 1125 */ 1126 __pyx_v_self->node = (__pyx_v_self->node->link[0]); 1127 goto __pyx_L5; 1128 } 1129 /*else*/ { 1130 1131 /* "bintrees\cwalker.pyx":57 1132 * self.node = self.node.link[0] 1133 * else: 1134 * self.node = self.node.link[1] # <<<<<<<<<<<<<< 1135 * return False 1136 * 1137 */ 1138 __pyx_v_self->node = (__pyx_v_self->node->link[1]); 1139 } 1140 __pyx_L5:; 1141 } 1142 1143 /* "bintrees\cwalker.pyx":58 1144 * else: 1145 * self.node = self.node.link[1] 1146 * return False # <<<<<<<<<<<<<< 1147 * 1148 * cpdef push(self): 1149 */ 1150 __Pyx_XDECREF(__pyx_r); 1151 __pyx_t_3 = __Pyx_PyBool_FromLong(0); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 58; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1152 __Pyx_GOTREF(__pyx_t_3); 1153 __pyx_r = __pyx_t_3; 1154 __pyx_t_3 = 0; 1155 goto __pyx_L0; 1156 1157 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1158 goto __pyx_L0; 1159 __pyx_L1_error:; 1160 __Pyx_XDECREF(__pyx_t_3); 1161 __Pyx_AddTraceback("bintrees.cwalker.cWalker.goto", __pyx_clineno, __pyx_lineno, __pyx_filename); 1162 __pyx_r = NULL; 1163 __pyx_L0:; 1164 __Pyx_XGIVEREF(__pyx_r); 1165 __Pyx_RefNannyFinishContext(); 1166 return __pyx_r; 1167 } 1168 1169 /* "bintrees\cwalker.pyx":60 1170 * return False 1171 * 1172 * cpdef push(self): # <<<<<<<<<<<<<< 1173 * stack_push(self.stack, self.node) 1174 * 1175 */ 1176 1177 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_17push(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1178 static PyObject *__pyx_f_8bintrees_7cwalker_7cWalker_push(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, int __pyx_skip_dispatch) { 1179 PyObject *__pyx_r = NULL; 1180 __Pyx_RefNannyDeclarations 1181 PyObject *__pyx_t_1 = NULL; 1182 PyObject *__pyx_t_2 = NULL; 1183 int __pyx_lineno = 0; 1184 const char *__pyx_filename = NULL; 1185 int __pyx_clineno = 0; 1186 __Pyx_RefNannySetupContext("push", 0); 1187 /* Check if called by wrapper */ 1188 if (unlikely(__pyx_skip_dispatch)) ; 1189 /* Check if overriden in Python */ 1190 else if (unlikely(Py_TYPE(((PyObject *)__pyx_v_self))->tp_dictoffset != 0)) { 1191 __pyx_t_1 = PyObject_GetAttr(((PyObject *)__pyx_v_self), __pyx_n_s__push); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1192 __Pyx_GOTREF(__pyx_t_1); 1193 if (!PyCFunction_Check(__pyx_t_1) || (PyCFunction_GET_FUNCTION(__pyx_t_1) != (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_17push)) { 1194 __Pyx_XDECREF(__pyx_r); 1195 __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 = 60; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1196 __Pyx_GOTREF(__pyx_t_2); 1197 __pyx_r = __pyx_t_2; 1198 __pyx_t_2 = 0; 1199 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 1200 goto __pyx_L0; 1201 } 1202 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 1203 } 1204 1205 /* "bintrees\cwalker.pyx":61 1206 * 1207 * cpdef push(self): 1208 * stack_push(self.stack, self.node) # <<<<<<<<<<<<<< 1209 * 1210 * cpdef pop(self): 1211 */ 1212 stack_push(__pyx_v_self->stack, __pyx_v_self->node); 1213 1214 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1215 goto __pyx_L0; 1216 __pyx_L1_error:; 1217 __Pyx_XDECREF(__pyx_t_1); 1218 __Pyx_XDECREF(__pyx_t_2); 1219 __Pyx_AddTraceback("bintrees.cwalker.cWalker.push", __pyx_clineno, __pyx_lineno, __pyx_filename); 1220 __pyx_r = 0; 1221 __pyx_L0:; 1222 __Pyx_XGIVEREF(__pyx_r); 1223 __Pyx_RefNannyFinishContext(); 1224 return __pyx_r; 1225 } 1226 1227 /* Python wrapper */ 1228 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_17push(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1229 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_17push(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1230 PyObject *__pyx_r = 0; 1231 __Pyx_RefNannyDeclarations 1232 __Pyx_RefNannySetupContext("push (wrapper)", 0); 1233 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_16push(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 1234 __Pyx_RefNannyFinishContext(); 1235 return __pyx_r; 1236 } 1237 1238 /* "bintrees\cwalker.pyx":60 1239 * return False 1240 * 1241 * cpdef push(self): # <<<<<<<<<<<<<< 1242 * stack_push(self.stack, self.node) 1243 * 1244 */ 1245 1246 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_16push(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 1247 PyObject *__pyx_r = NULL; 1248 __Pyx_RefNannyDeclarations 1249 PyObject *__pyx_t_1 = NULL; 1250 int __pyx_lineno = 0; 1251 const char *__pyx_filename = NULL; 1252 int __pyx_clineno = 0; 1253 __Pyx_RefNannySetupContext("push", 0); 1254 __Pyx_XDECREF(__pyx_r); 1255 __pyx_t_1 = ((struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker *)__pyx_v_self->__pyx_vtab)->push(__pyx_v_self, 1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 60; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1256 __Pyx_GOTREF(__pyx_t_1); 1257 __pyx_r = __pyx_t_1; 1258 __pyx_t_1 = 0; 1259 goto __pyx_L0; 1260 1261 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1262 goto __pyx_L0; 1263 __pyx_L1_error:; 1264 __Pyx_XDECREF(__pyx_t_1); 1265 __Pyx_AddTraceback("bintrees.cwalker.cWalker.push", __pyx_clineno, __pyx_lineno, __pyx_filename); 1266 __pyx_r = NULL; 1267 __pyx_L0:; 1268 __Pyx_XGIVEREF(__pyx_r); 1269 __Pyx_RefNannyFinishContext(); 1270 return __pyx_r; 1271 } 1272 1273 /* "bintrees\cwalker.pyx":63 1274 * stack_push(self.stack, self.node) 1275 * 1276 * cpdef pop(self): # <<<<<<<<<<<<<< 1277 * if stack_is_empty(self.stack) != 0: 1278 * raise IndexError('pop(): stack is empty') 1279 */ 1280 1281 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_19pop(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1282 static PyObject *__pyx_f_8bintrees_7cwalker_7cWalker_pop(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, int __pyx_skip_dispatch) { 1283 PyObject *__pyx_r = NULL; 1284 __Pyx_RefNannyDeclarations 1285 PyObject *__pyx_t_1 = NULL; 1286 PyObject *__pyx_t_2 = NULL; 1287 int __pyx_t_3; 1288 int __pyx_lineno = 0; 1289 const char *__pyx_filename = NULL; 1290 int __pyx_clineno = 0; 1291 __Pyx_RefNannySetupContext("pop", 0); 1292 /* Check if called by wrapper */ 1293 if (unlikely(__pyx_skip_dispatch)) ; 1294 /* Check if overriden in Python */ 1295 else if (unlikely(Py_TYPE(((PyObject *)__pyx_v_self))->tp_dictoffset != 0)) { 1296 __pyx_t_1 = PyObject_GetAttr(((PyObject *)__pyx_v_self), __pyx_n_s__pop); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 63; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1297 __Pyx_GOTREF(__pyx_t_1); 1298 if (!PyCFunction_Check(__pyx_t_1) || (PyCFunction_GET_FUNCTION(__pyx_t_1) != (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_19pop)) { 1299 __Pyx_XDECREF(__pyx_r); 1300 __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 = 63; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1301 __Pyx_GOTREF(__pyx_t_2); 1302 __pyx_r = __pyx_t_2; 1303 __pyx_t_2 = 0; 1304 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 1305 goto __pyx_L0; 1306 } 1307 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 1308 } 1309 1310 /* "bintrees\cwalker.pyx":64 1311 * 1312 * cpdef pop(self): 1313 * if stack_is_empty(self.stack) != 0: # <<<<<<<<<<<<<< 1314 * raise IndexError('pop(): stack is empty') 1315 * self.node = stack_pop(self.stack) 1316 */ 1317 __pyx_t_3 = (stack_is_empty(__pyx_v_self->stack) != 0); 1318 if (__pyx_t_3) { 1319 1320 /* "bintrees\cwalker.pyx":65 1321 * cpdef pop(self): 1322 * if stack_is_empty(self.stack) != 0: 1323 * raise IndexError('pop(): stack is empty') # <<<<<<<<<<<<<< 1324 * self.node = stack_pop(self.stack) 1325 * 1326 */ 1327 __pyx_t_1 = PyObject_Call(__pyx_builtin_IndexError, ((PyObject *)__pyx_k_tuple_2), NULL); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 65; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1328 __Pyx_GOTREF(__pyx_t_1); 1329 __Pyx_Raise(__pyx_t_1, 0, 0, 0); 1330 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 1331 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 65; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1332 goto __pyx_L3; 1333 } 1334 __pyx_L3:; 1335 1336 /* "bintrees\cwalker.pyx":66 1337 * if stack_is_empty(self.stack) != 0: 1338 * raise IndexError('pop(): stack is empty') 1339 * self.node = stack_pop(self.stack) # <<<<<<<<<<<<<< 1340 * 1341 * def stack_is_empty(self): 1342 */ 1343 __pyx_v_self->node = stack_pop(__pyx_v_self->stack); 1344 1345 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1346 goto __pyx_L0; 1347 __pyx_L1_error:; 1348 __Pyx_XDECREF(__pyx_t_1); 1349 __Pyx_XDECREF(__pyx_t_2); 1350 __Pyx_AddTraceback("bintrees.cwalker.cWalker.pop", __pyx_clineno, __pyx_lineno, __pyx_filename); 1351 __pyx_r = 0; 1352 __pyx_L0:; 1353 __Pyx_XGIVEREF(__pyx_r); 1354 __Pyx_RefNannyFinishContext(); 1355 return __pyx_r; 1356 } 1357 1358 /* Python wrapper */ 1359 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_19pop(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1360 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_19pop(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1361 PyObject *__pyx_r = 0; 1362 __Pyx_RefNannyDeclarations 1363 __Pyx_RefNannySetupContext("pop (wrapper)", 0); 1364 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_18pop(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 1365 __Pyx_RefNannyFinishContext(); 1366 return __pyx_r; 1367 } 1368 1369 /* "bintrees\cwalker.pyx":63 1370 * stack_push(self.stack, self.node) 1371 * 1372 * cpdef pop(self): # <<<<<<<<<<<<<< 1373 * if stack_is_empty(self.stack) != 0: 1374 * raise IndexError('pop(): stack is empty') 1375 */ 1376 1377 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_18pop(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 1378 PyObject *__pyx_r = NULL; 1379 __Pyx_RefNannyDeclarations 1380 PyObject *__pyx_t_1 = NULL; 1381 int __pyx_lineno = 0; 1382 const char *__pyx_filename = NULL; 1383 int __pyx_clineno = 0; 1384 __Pyx_RefNannySetupContext("pop", 0); 1385 __Pyx_XDECREF(__pyx_r); 1386 __pyx_t_1 = ((struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker *)__pyx_v_self->__pyx_vtab)->pop(__pyx_v_self, 1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 63; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1387 __Pyx_GOTREF(__pyx_t_1); 1388 __pyx_r = __pyx_t_1; 1389 __pyx_t_1 = 0; 1390 goto __pyx_L0; 1391 1392 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1393 goto __pyx_L0; 1394 __pyx_L1_error:; 1395 __Pyx_XDECREF(__pyx_t_1); 1396 __Pyx_AddTraceback("bintrees.cwalker.cWalker.pop", __pyx_clineno, __pyx_lineno, __pyx_filename); 1397 __pyx_r = NULL; 1398 __pyx_L0:; 1399 __Pyx_XGIVEREF(__pyx_r); 1400 __Pyx_RefNannyFinishContext(); 1401 return __pyx_r; 1402 } 1403 1404 /* Python wrapper */ 1405 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_21stack_is_empty(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1406 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_21stack_is_empty(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1407 PyObject *__pyx_r = 0; 1408 __Pyx_RefNannyDeclarations 1409 __Pyx_RefNannySetupContext("stack_is_empty (wrapper)", 0); 1410 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_20stack_is_empty(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 1411 __Pyx_RefNannyFinishContext(); 1412 return __pyx_r; 1413 } 1414 1415 /* "bintrees\cwalker.pyx":68 1416 * self.node = stack_pop(self.stack) 1417 * 1418 * def stack_is_empty(self): # <<<<<<<<<<<<<< 1419 * return <bint> stack_is_empty(self.stack) 1420 * 1421 */ 1422 1423 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_20stack_is_empty(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 1424 PyObject *__pyx_r = NULL; 1425 __Pyx_RefNannyDeclarations 1426 PyObject *__pyx_t_1 = NULL; 1427 int __pyx_lineno = 0; 1428 const char *__pyx_filename = NULL; 1429 int __pyx_clineno = 0; 1430 __Pyx_RefNannySetupContext("stack_is_empty", 0); 1431 1432 /* "bintrees\cwalker.pyx":69 1433 * 1434 * def stack_is_empty(self): 1435 * return <bint> stack_is_empty(self.stack) # <<<<<<<<<<<<<< 1436 * 1437 * def goto_leaf(self): 1438 */ 1439 __Pyx_XDECREF(__pyx_r); 1440 __pyx_t_1 = __Pyx_PyBool_FromLong(((int)stack_is_empty(__pyx_v_self->stack))); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 69; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1441 __Pyx_GOTREF(__pyx_t_1); 1442 __pyx_r = __pyx_t_1; 1443 __pyx_t_1 = 0; 1444 goto __pyx_L0; 1445 1446 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1447 goto __pyx_L0; 1448 __pyx_L1_error:; 1449 __Pyx_XDECREF(__pyx_t_1); 1450 __Pyx_AddTraceback("bintrees.cwalker.cWalker.stack_is_empty", __pyx_clineno, __pyx_lineno, __pyx_filename); 1451 __pyx_r = NULL; 1452 __pyx_L0:; 1453 __Pyx_XGIVEREF(__pyx_r); 1454 __Pyx_RefNannyFinishContext(); 1455 return __pyx_r; 1456 } 1457 1458 /* Python wrapper */ 1459 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_23goto_leaf(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1460 static char __pyx_doc_8bintrees_7cwalker_7cWalker_22goto_leaf[] = " get a leaf node "; 1461 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_23goto_leaf(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1462 PyObject *__pyx_r = 0; 1463 __Pyx_RefNannyDeclarations 1464 __Pyx_RefNannySetupContext("goto_leaf (wrapper)", 0); 1465 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_22goto_leaf(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 1466 __Pyx_RefNannyFinishContext(); 1467 return __pyx_r; 1468 } 1469 1470 /* "bintrees\cwalker.pyx":71 1471 * return <bint> stack_is_empty(self.stack) 1472 * 1473 * def goto_leaf(self): # <<<<<<<<<<<<<< 1474 * """ get a leaf node """ 1475 * while self.node != NULL: 1476 */ 1477 1478 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_22goto_leaf(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 1479 PyObject *__pyx_r = NULL; 1480 __Pyx_RefNannyDeclarations 1481 int __pyx_t_1; 1482 __Pyx_RefNannySetupContext("goto_leaf", 0); 1483 1484 /* "bintrees\cwalker.pyx":73 1485 * def goto_leaf(self): 1486 * """ get a leaf node """ 1487 * while self.node != NULL: # <<<<<<<<<<<<<< 1488 * if self.node.link[0] != NULL: 1489 * self.node = self.node.link[0] 1490 */ 1491 while (1) { 1492 __pyx_t_1 = (__pyx_v_self->node != NULL); 1493 if (!__pyx_t_1) break; 1494 1495 /* "bintrees\cwalker.pyx":74 1496 * """ get a leaf node """ 1497 * while self.node != NULL: 1498 * if self.node.link[0] != NULL: # <<<<<<<<<<<<<< 1499 * self.node = self.node.link[0] 1500 * elif self.node.link[1] != NULL: 1501 */ 1502 __pyx_t_1 = ((__pyx_v_self->node->link[0]) != NULL); 1503 if (__pyx_t_1) { 1504 1505 /* "bintrees\cwalker.pyx":75 1506 * while self.node != NULL: 1507 * if self.node.link[0] != NULL: 1508 * self.node = self.node.link[0] # <<<<<<<<<<<<<< 1509 * elif self.node.link[1] != NULL: 1510 * self.node = self.node.link[1] 1511 */ 1512 __pyx_v_self->node = (__pyx_v_self->node->link[0]); 1513 goto __pyx_L5; 1514 } 1515 1516 /* "bintrees\cwalker.pyx":76 1517 * if self.node.link[0] != NULL: 1518 * self.node = self.node.link[0] 1519 * elif self.node.link[1] != NULL: # <<<<<<<<<<<<<< 1520 * self.node = self.node.link[1] 1521 * else: 1522 */ 1523 __pyx_t_1 = ((__pyx_v_self->node->link[1]) != NULL); 1524 if (__pyx_t_1) { 1525 1526 /* "bintrees\cwalker.pyx":77 1527 * self.node = self.node.link[0] 1528 * elif self.node.link[1] != NULL: 1529 * self.node = self.node.link[1] # <<<<<<<<<<<<<< 1530 * else: 1531 * return 1532 */ 1533 __pyx_v_self->node = (__pyx_v_self->node->link[1]); 1534 goto __pyx_L5; 1535 } 1536 /*else*/ { 1537 1538 /* "bintrees\cwalker.pyx":79 1539 * self.node = self.node.link[1] 1540 * else: 1541 * return # <<<<<<<<<<<<<< 1542 * 1543 * def has_child(self, int direction): 1544 */ 1545 __Pyx_XDECREF(__pyx_r); 1546 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1547 goto __pyx_L0; 1548 } 1549 __pyx_L5:; 1550 } 1551 1552 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1553 __pyx_L0:; 1554 __Pyx_XGIVEREF(__pyx_r); 1555 __Pyx_RefNannyFinishContext(); 1556 return __pyx_r; 1557 } 1558 1559 /* Python wrapper */ 1560 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_25has_child(PyObject *__pyx_v_self, PyObject *__pyx_arg_direction); /*proto*/ 1561 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_25has_child(PyObject *__pyx_v_self, PyObject *__pyx_arg_direction) { 1562 int __pyx_v_direction; 1563 PyObject *__pyx_r = 0; 1564 __Pyx_RefNannyDeclarations 1565 __Pyx_RefNannySetupContext("has_child (wrapper)", 0); 1566 assert(__pyx_arg_direction); { 1567 __pyx_v_direction = __Pyx_PyInt_AsInt(__pyx_arg_direction); if (unlikely((__pyx_v_direction == (int)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 81; __pyx_clineno = __LINE__; goto __pyx_L3_error;} 1568 } 1569 goto __pyx_L4_argument_unpacking_done; 1570 __pyx_L3_error:; 1571 __Pyx_AddTraceback("bintrees.cwalker.cWalker.has_child", __pyx_clineno, __pyx_lineno, __pyx_filename); 1572 __Pyx_RefNannyFinishContext(); 1573 return NULL; 1574 __pyx_L4_argument_unpacking_done:; 1575 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_24has_child(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self), ((int)__pyx_v_direction)); 1576 __Pyx_RefNannyFinishContext(); 1577 return __pyx_r; 1578 } 1579 1580 /* "bintrees\cwalker.pyx":81 1581 * return 1582 * 1583 * def has_child(self, int direction): # <<<<<<<<<<<<<< 1584 * return self.node.link[direction] != NULL 1585 * 1586 */ 1587 1588 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_24has_child(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, int __pyx_v_direction) { 1589 PyObject *__pyx_r = NULL; 1590 __Pyx_RefNannyDeclarations 1591 PyObject *__pyx_t_1 = NULL; 1592 int __pyx_lineno = 0; 1593 const char *__pyx_filename = NULL; 1594 int __pyx_clineno = 0; 1595 __Pyx_RefNannySetupContext("has_child", 0); 1596 1597 /* "bintrees\cwalker.pyx":82 1598 * 1599 * def has_child(self, int direction): 1600 * return self.node.link[direction] != NULL # <<<<<<<<<<<<<< 1601 * 1602 * def down(self, int direction): 1603 */ 1604 __Pyx_XDECREF(__pyx_r); 1605 __pyx_t_1 = __Pyx_PyBool_FromLong(((__pyx_v_self->node->link[__pyx_v_direction]) != NULL)); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 82; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1606 __Pyx_GOTREF(__pyx_t_1); 1607 __pyx_r = __pyx_t_1; 1608 __pyx_t_1 = 0; 1609 goto __pyx_L0; 1610 1611 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1612 goto __pyx_L0; 1613 __pyx_L1_error:; 1614 __Pyx_XDECREF(__pyx_t_1); 1615 __Pyx_AddTraceback("bintrees.cwalker.cWalker.has_child", __pyx_clineno, __pyx_lineno, __pyx_filename); 1616 __pyx_r = NULL; 1617 __pyx_L0:; 1618 __Pyx_XGIVEREF(__pyx_r); 1619 __Pyx_RefNannyFinishContext(); 1620 return __pyx_r; 1621 } 1622 1623 /* Python wrapper */ 1624 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_27down(PyObject *__pyx_v_self, PyObject *__pyx_arg_direction); /*proto*/ 1625 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_27down(PyObject *__pyx_v_self, PyObject *__pyx_arg_direction) { 1626 int __pyx_v_direction; 1627 PyObject *__pyx_r = 0; 1628 __Pyx_RefNannyDeclarations 1629 __Pyx_RefNannySetupContext("down (wrapper)", 0); 1630 assert(__pyx_arg_direction); { 1631 __pyx_v_direction = __Pyx_PyInt_AsInt(__pyx_arg_direction); if (unlikely((__pyx_v_direction == (int)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 84; __pyx_clineno = __LINE__; goto __pyx_L3_error;} 1632 } 1633 goto __pyx_L4_argument_unpacking_done; 1634 __pyx_L3_error:; 1635 __Pyx_AddTraceback("bintrees.cwalker.cWalker.down", __pyx_clineno, __pyx_lineno, __pyx_filename); 1636 __Pyx_RefNannyFinishContext(); 1637 return NULL; 1638 __pyx_L4_argument_unpacking_done:; 1639 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_26down(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self), ((int)__pyx_v_direction)); 1640 __Pyx_RefNannyFinishContext(); 1641 return __pyx_r; 1642 } 1643 1644 /* "bintrees\cwalker.pyx":84 1645 * return self.node.link[direction] != NULL 1646 * 1647 * def down(self, int direction): # <<<<<<<<<<<<<< 1648 * self.node = self.node.link[direction] 1649 * 1650 */ 1651 1652 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_26down(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, int __pyx_v_direction) { 1653 PyObject *__pyx_r = NULL; 1654 __Pyx_RefNannyDeclarations 1655 __Pyx_RefNannySetupContext("down", 0); 1656 1657 /* "bintrees\cwalker.pyx":85 1658 * 1659 * def down(self, int direction): 1660 * self.node = self.node.link[direction] # <<<<<<<<<<<<<< 1661 * 1662 * def go_left(self): 1663 */ 1664 __pyx_v_self->node = (__pyx_v_self->node->link[__pyx_v_direction]); 1665 1666 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1667 __Pyx_XGIVEREF(__pyx_r); 1668 __Pyx_RefNannyFinishContext(); 1669 return __pyx_r; 1670 } 1671 1672 /* Python wrapper */ 1673 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_29go_left(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1674 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_29go_left(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1675 PyObject *__pyx_r = 0; 1676 __Pyx_RefNannyDeclarations 1677 __Pyx_RefNannySetupContext("go_left (wrapper)", 0); 1678 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_28go_left(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 1679 __Pyx_RefNannyFinishContext(); 1680 return __pyx_r; 1681 } 1682 1683 /* "bintrees\cwalker.pyx":87 1684 * self.node = self.node.link[direction] 1685 * 1686 * def go_left(self): # <<<<<<<<<<<<<< 1687 * self.node = self.node.link[0] 1688 * 1689 */ 1690 1691 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_28go_left(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 1692 PyObject *__pyx_r = NULL; 1693 __Pyx_RefNannyDeclarations 1694 __Pyx_RefNannySetupContext("go_left", 0); 1695 1696 /* "bintrees\cwalker.pyx":88 1697 * 1698 * def go_left(self): 1699 * self.node = self.node.link[0] # <<<<<<<<<<<<<< 1700 * 1701 * def go_right(self): 1702 */ 1703 __pyx_v_self->node = (__pyx_v_self->node->link[0]); 1704 1705 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1706 __Pyx_XGIVEREF(__pyx_r); 1707 __Pyx_RefNannyFinishContext(); 1708 return __pyx_r; 1709 } 1710 1711 /* Python wrapper */ 1712 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_31go_right(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1713 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_31go_right(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1714 PyObject *__pyx_r = 0; 1715 __Pyx_RefNannyDeclarations 1716 __Pyx_RefNannySetupContext("go_right (wrapper)", 0); 1717 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_30go_right(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 1718 __Pyx_RefNannyFinishContext(); 1719 return __pyx_r; 1720 } 1721 1722 /* "bintrees\cwalker.pyx":90 1723 * self.node = self.node.link[0] 1724 * 1725 * def go_right(self): # <<<<<<<<<<<<<< 1726 * self.node = self.node.link[1] 1727 * 1728 */ 1729 1730 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_30go_right(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 1731 PyObject *__pyx_r = NULL; 1732 __Pyx_RefNannyDeclarations 1733 __Pyx_RefNannySetupContext("go_right", 0); 1734 1735 /* "bintrees\cwalker.pyx":91 1736 * 1737 * def go_right(self): 1738 * self.node = self.node.link[1] # <<<<<<<<<<<<<< 1739 * 1740 * def has_left(self): 1741 */ 1742 __pyx_v_self->node = (__pyx_v_self->node->link[1]); 1743 1744 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1745 __Pyx_XGIVEREF(__pyx_r); 1746 __Pyx_RefNannyFinishContext(); 1747 return __pyx_r; 1748 } 1749 1750 /* Python wrapper */ 1751 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_33has_left(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1752 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_33has_left(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1753 PyObject *__pyx_r = 0; 1754 __Pyx_RefNannyDeclarations 1755 __Pyx_RefNannySetupContext("has_left (wrapper)", 0); 1756 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_32has_left(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 1757 __Pyx_RefNannyFinishContext(); 1758 return __pyx_r; 1759 } 1760 1761 /* "bintrees\cwalker.pyx":93 1762 * self.node = self.node.link[1] 1763 * 1764 * def has_left(self): # <<<<<<<<<<<<<< 1765 * return self.node.link[0] != NULL 1766 * 1767 */ 1768 1769 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_32has_left(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 1770 PyObject *__pyx_r = NULL; 1771 __Pyx_RefNannyDeclarations 1772 PyObject *__pyx_t_1 = NULL; 1773 int __pyx_lineno = 0; 1774 const char *__pyx_filename = NULL; 1775 int __pyx_clineno = 0; 1776 __Pyx_RefNannySetupContext("has_left", 0); 1777 1778 /* "bintrees\cwalker.pyx":94 1779 * 1780 * def has_left(self): 1781 * return self.node.link[0] != NULL # <<<<<<<<<<<<<< 1782 * 1783 * def has_right(self): 1784 */ 1785 __Pyx_XDECREF(__pyx_r); 1786 __pyx_t_1 = __Pyx_PyBool_FromLong(((__pyx_v_self->node->link[0]) != NULL)); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 94; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1787 __Pyx_GOTREF(__pyx_t_1); 1788 __pyx_r = __pyx_t_1; 1789 __pyx_t_1 = 0; 1790 goto __pyx_L0; 1791 1792 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1793 goto __pyx_L0; 1794 __pyx_L1_error:; 1795 __Pyx_XDECREF(__pyx_t_1); 1796 __Pyx_AddTraceback("bintrees.cwalker.cWalker.has_left", __pyx_clineno, __pyx_lineno, __pyx_filename); 1797 __pyx_r = NULL; 1798 __pyx_L0:; 1799 __Pyx_XGIVEREF(__pyx_r); 1800 __Pyx_RefNannyFinishContext(); 1801 return __pyx_r; 1802 } 1803 1804 /* Python wrapper */ 1805 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_35has_right(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused); /*proto*/ 1806 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_35has_right(PyObject *__pyx_v_self, CYTHON_UNUSED PyObject *unused) { 1807 PyObject *__pyx_r = 0; 1808 __Pyx_RefNannyDeclarations 1809 __Pyx_RefNannySetupContext("has_right (wrapper)", 0); 1810 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_34has_right(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self)); 1811 __Pyx_RefNannyFinishContext(); 1812 return __pyx_r; 1813 } 1814 1815 /* "bintrees\cwalker.pyx":96 1816 * return self.node.link[0] != NULL 1817 * 1818 * def has_right(self): # <<<<<<<<<<<<<< 1819 * return self.node.link[1] != NULL 1820 * 1821 */ 1822 1823 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_34has_right(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self) { 1824 PyObject *__pyx_r = NULL; 1825 __Pyx_RefNannyDeclarations 1826 PyObject *__pyx_t_1 = NULL; 1827 int __pyx_lineno = 0; 1828 const char *__pyx_filename = NULL; 1829 int __pyx_clineno = 0; 1830 __Pyx_RefNannySetupContext("has_right", 0); 1831 1832 /* "bintrees\cwalker.pyx":97 1833 * 1834 * def has_right(self): 1835 * return self.node.link[1] != NULL # <<<<<<<<<<<<<< 1836 * 1837 * def succ_item(self, key): 1838 */ 1839 __Pyx_XDECREF(__pyx_r); 1840 __pyx_t_1 = __Pyx_PyBool_FromLong(((__pyx_v_self->node->link[1]) != NULL)); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 97; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1841 __Pyx_GOTREF(__pyx_t_1); 1842 __pyx_r = __pyx_t_1; 1843 __pyx_t_1 = 0; 1844 goto __pyx_L0; 1845 1846 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1847 goto __pyx_L0; 1848 __pyx_L1_error:; 1849 __Pyx_XDECREF(__pyx_t_1); 1850 __Pyx_AddTraceback("bintrees.cwalker.cWalker.has_right", __pyx_clineno, __pyx_lineno, __pyx_filename); 1851 __pyx_r = NULL; 1852 __pyx_L0:; 1853 __Pyx_XGIVEREF(__pyx_r); 1854 __Pyx_RefNannyFinishContext(); 1855 return __pyx_r; 1856 } 1857 1858 /* Python wrapper */ 1859 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_37succ_item(PyObject *__pyx_v_self, PyObject *__pyx_v_key); /*proto*/ 1860 static char __pyx_doc_8bintrees_7cwalker_7cWalker_36succ_item[] = " Get successor (k,v) pair of key, raises KeyError if key is max key\n or key does not exist.\n "; 1861 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_37succ_item(PyObject *__pyx_v_self, PyObject *__pyx_v_key) { 1862 PyObject *__pyx_r = 0; 1863 __Pyx_RefNannyDeclarations 1864 __Pyx_RefNannySetupContext("succ_item (wrapper)", 0); 1865 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_36succ_item(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self), ((PyObject *)__pyx_v_key)); 1866 __Pyx_RefNannyFinishContext(); 1867 return __pyx_r; 1868 } 1869 1870 /* "bintrees\cwalker.pyx":99 1871 * return self.node.link[1] != NULL 1872 * 1873 * def succ_item(self, key): # <<<<<<<<<<<<<< 1874 * """ Get successor (k,v) pair of key, raises KeyError if key is max key 1875 * or key does not exist. 1876 */ 1877 1878 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_36succ_item(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, PyObject *__pyx_v_key) { 1879 PyObject *__pyx_r = NULL; 1880 __Pyx_RefNannyDeclarations 1881 int __pyx_t_1; 1882 PyObject *__pyx_t_2 = NULL; 1883 PyObject *__pyx_t_3 = NULL; 1884 int __pyx_lineno = 0; 1885 const char *__pyx_filename = NULL; 1886 int __pyx_clineno = 0; 1887 __Pyx_RefNannySetupContext("succ_item", 0); 1888 1889 /* "bintrees\cwalker.pyx":103 1890 * or key does not exist. 1891 * """ 1892 * self.node = ct_succ_node(self.root, key) # <<<<<<<<<<<<<< 1893 * if self.node == NULL: # given key is biggest in tree 1894 * raise KeyError(str(key)) 1895 */ 1896 __pyx_v_self->node = ct_succ_node(__pyx_v_self->root, __pyx_v_key); 1897 1898 /* "bintrees\cwalker.pyx":104 1899 * """ 1900 * self.node = ct_succ_node(self.root, key) 1901 * if self.node == NULL: # given key is biggest in tree # <<<<<<<<<<<<<< 1902 * raise KeyError(str(key)) 1903 * return (<object> self.node.key, <object> self.node.value) 1904 */ 1905 __pyx_t_1 = (__pyx_v_self->node == NULL); 1906 if (__pyx_t_1) { 1907 1908 /* "bintrees\cwalker.pyx":105 1909 * self.node = ct_succ_node(self.root, key) 1910 * if self.node == NULL: # given key is biggest in tree 1911 * raise KeyError(str(key)) # <<<<<<<<<<<<<< 1912 * return (<object> self.node.key, <object> self.node.value) 1913 * 1914 */ 1915 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 105; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1916 __Pyx_GOTREF(__pyx_t_2); 1917 __Pyx_INCREF(__pyx_v_key); 1918 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_v_key); 1919 __Pyx_GIVEREF(__pyx_v_key); 1920 __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 = 105; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1921 __Pyx_GOTREF(__pyx_t_3); 1922 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 1923 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 105; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1924 __Pyx_GOTREF(__pyx_t_2); 1925 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_t_3); 1926 __Pyx_GIVEREF(__pyx_t_3); 1927 __pyx_t_3 = 0; 1928 __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 = 105; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1929 __Pyx_GOTREF(__pyx_t_3); 1930 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 1931 __Pyx_Raise(__pyx_t_3, 0, 0, 0); 1932 __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; 1933 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 105; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1934 goto __pyx_L3; 1935 } 1936 __pyx_L3:; 1937 1938 /* "bintrees\cwalker.pyx":106 1939 * if self.node == NULL: # given key is biggest in tree 1940 * raise KeyError(str(key)) 1941 * return (<object> self.node.key, <object> self.node.value) # <<<<<<<<<<<<<< 1942 * 1943 * def prev_item(self, key): 1944 */ 1945 __Pyx_XDECREF(__pyx_r); 1946 __pyx_t_3 = PyTuple_New(2); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 106; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 1947 __Pyx_GOTREF(__pyx_t_3); 1948 __Pyx_INCREF(((PyObject *)__pyx_v_self->node->key)); 1949 PyTuple_SET_ITEM(__pyx_t_3, 0, ((PyObject *)__pyx_v_self->node->key)); 1950 __Pyx_GIVEREF(((PyObject *)__pyx_v_self->node->key)); 1951 __Pyx_INCREF(((PyObject *)__pyx_v_self->node->value)); 1952 PyTuple_SET_ITEM(__pyx_t_3, 1, ((PyObject *)__pyx_v_self->node->value)); 1953 __Pyx_GIVEREF(((PyObject *)__pyx_v_self->node->value)); 1954 __pyx_r = ((PyObject *)__pyx_t_3); 1955 __pyx_t_3 = 0; 1956 goto __pyx_L0; 1957 1958 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 1959 goto __pyx_L0; 1960 __pyx_L1_error:; 1961 __Pyx_XDECREF(__pyx_t_2); 1962 __Pyx_XDECREF(__pyx_t_3); 1963 __Pyx_AddTraceback("bintrees.cwalker.cWalker.succ_item", __pyx_clineno, __pyx_lineno, __pyx_filename); 1964 __pyx_r = NULL; 1965 __pyx_L0:; 1966 __Pyx_XGIVEREF(__pyx_r); 1967 __Pyx_RefNannyFinishContext(); 1968 return __pyx_r; 1969 } 1970 1971 /* Python wrapper */ 1972 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_39prev_item(PyObject *__pyx_v_self, PyObject *__pyx_v_key); /*proto*/ 1973 static char __pyx_doc_8bintrees_7cwalker_7cWalker_38prev_item[] = " Get predecessor (k,v) pair of key, raises KeyError if key is min key\n or key does not exist.\n "; 1974 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_39prev_item(PyObject *__pyx_v_self, PyObject *__pyx_v_key) { 1975 PyObject *__pyx_r = 0; 1976 __Pyx_RefNannyDeclarations 1977 __Pyx_RefNannySetupContext("prev_item (wrapper)", 0); 1978 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_38prev_item(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self), ((PyObject *)__pyx_v_key)); 1979 __Pyx_RefNannyFinishContext(); 1980 return __pyx_r; 1981 } 1982 1983 /* "bintrees\cwalker.pyx":108 1984 * return (<object> self.node.key, <object> self.node.value) 1985 * 1986 * def prev_item(self, key): # <<<<<<<<<<<<<< 1987 * """ Get predecessor (k,v) pair of key, raises KeyError if key is min key 1988 * or key does not exist. 1989 */ 1990 1991 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_38prev_item(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, PyObject *__pyx_v_key) { 1992 PyObject *__pyx_r = NULL; 1993 __Pyx_RefNannyDeclarations 1994 int __pyx_t_1; 1995 PyObject *__pyx_t_2 = NULL; 1996 PyObject *__pyx_t_3 = NULL; 1997 int __pyx_lineno = 0; 1998 const char *__pyx_filename = NULL; 1999 int __pyx_clineno = 0; 2000 __Pyx_RefNannySetupContext("prev_item", 0); 2001 2002 /* "bintrees\cwalker.pyx":112 2003 * or key does not exist. 2004 * """ 2005 * self.node = ct_prev_node(self.root, key) # <<<<<<<<<<<<<< 2006 * if self.node == NULL: # given key is smallest in tree 2007 * raise KeyError(str(key)) 2008 */ 2009 __pyx_v_self->node = ct_prev_node(__pyx_v_self->root, __pyx_v_key); 2010 2011 /* "bintrees\cwalker.pyx":113 2012 * """ 2013 * self.node = ct_prev_node(self.root, key) 2014 * if self.node == NULL: # given key is smallest in tree # <<<<<<<<<<<<<< 2015 * raise KeyError(str(key)) 2016 * return (<object> self.node.key, <object> self.node.value) 2017 */ 2018 __pyx_t_1 = (__pyx_v_self->node == NULL); 2019 if (__pyx_t_1) { 2020 2021 /* "bintrees\cwalker.pyx":114 2022 * self.node = ct_prev_node(self.root, key) 2023 * if self.node == NULL: # given key is smallest in tree 2024 * raise KeyError(str(key)) # <<<<<<<<<<<<<< 2025 * return (<object> self.node.key, <object> self.node.value) 2026 * 2027 */ 2028 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 114; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2029 __Pyx_GOTREF(__pyx_t_2); 2030 __Pyx_INCREF(__pyx_v_key); 2031 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_v_key); 2032 __Pyx_GIVEREF(__pyx_v_key); 2033 __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 = 114; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2034 __Pyx_GOTREF(__pyx_t_3); 2035 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 2036 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 114; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2037 __Pyx_GOTREF(__pyx_t_2); 2038 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_t_3); 2039 __Pyx_GIVEREF(__pyx_t_3); 2040 __pyx_t_3 = 0; 2041 __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 = 114; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2042 __Pyx_GOTREF(__pyx_t_3); 2043 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 2044 __Pyx_Raise(__pyx_t_3, 0, 0, 0); 2045 __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; 2046 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 114; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2047 goto __pyx_L3; 2048 } 2049 __pyx_L3:; 2050 2051 /* "bintrees\cwalker.pyx":115 2052 * if self.node == NULL: # given key is smallest in tree 2053 * raise KeyError(str(key)) 2054 * return (<object> self.node.key, <object> self.node.value) # <<<<<<<<<<<<<< 2055 * 2056 * def floor_item(self, key): 2057 */ 2058 __Pyx_XDECREF(__pyx_r); 2059 __pyx_t_3 = PyTuple_New(2); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 115; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2060 __Pyx_GOTREF(__pyx_t_3); 2061 __Pyx_INCREF(((PyObject *)__pyx_v_self->node->key)); 2062 PyTuple_SET_ITEM(__pyx_t_3, 0, ((PyObject *)__pyx_v_self->node->key)); 2063 __Pyx_GIVEREF(((PyObject *)__pyx_v_self->node->key)); 2064 __Pyx_INCREF(((PyObject *)__pyx_v_self->node->value)); 2065 PyTuple_SET_ITEM(__pyx_t_3, 1, ((PyObject *)__pyx_v_self->node->value)); 2066 __Pyx_GIVEREF(((PyObject *)__pyx_v_self->node->value)); 2067 __pyx_r = ((PyObject *)__pyx_t_3); 2068 __pyx_t_3 = 0; 2069 goto __pyx_L0; 2070 2071 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 2072 goto __pyx_L0; 2073 __pyx_L1_error:; 2074 __Pyx_XDECREF(__pyx_t_2); 2075 __Pyx_XDECREF(__pyx_t_3); 2076 __Pyx_AddTraceback("bintrees.cwalker.cWalker.prev_item", __pyx_clineno, __pyx_lineno, __pyx_filename); 2077 __pyx_r = NULL; 2078 __pyx_L0:; 2079 __Pyx_XGIVEREF(__pyx_r); 2080 __Pyx_RefNannyFinishContext(); 2081 return __pyx_r; 2082 } 2083 2084 /* Python wrapper */ 2085 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_41floor_item(PyObject *__pyx_v_self, PyObject *__pyx_v_key); /*proto*/ 2086 static char __pyx_doc_8bintrees_7cwalker_7cWalker_40floor_item[] = " Get the element (k,v) pair associated with the greatest key less\n than or equal to the given key, raises KeyError if there is no such key.\n "; 2087 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_41floor_item(PyObject *__pyx_v_self, PyObject *__pyx_v_key) { 2088 PyObject *__pyx_r = 0; 2089 __Pyx_RefNannyDeclarations 2090 __Pyx_RefNannySetupContext("floor_item (wrapper)", 0); 2091 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_40floor_item(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self), ((PyObject *)__pyx_v_key)); 2092 __Pyx_RefNannyFinishContext(); 2093 return __pyx_r; 2094 } 2095 2096 /* "bintrees\cwalker.pyx":117 2097 * return (<object> self.node.key, <object> self.node.value) 2098 * 2099 * def floor_item(self, key): # <<<<<<<<<<<<<< 2100 * """ Get the element (k,v) pair associated with the greatest key less 2101 * than or equal to the given key, raises KeyError if there is no such key. 2102 */ 2103 2104 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_40floor_item(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, PyObject *__pyx_v_key) { 2105 PyObject *__pyx_r = NULL; 2106 __Pyx_RefNannyDeclarations 2107 int __pyx_t_1; 2108 PyObject *__pyx_t_2 = NULL; 2109 PyObject *__pyx_t_3 = NULL; 2110 int __pyx_lineno = 0; 2111 const char *__pyx_filename = NULL; 2112 int __pyx_clineno = 0; 2113 __Pyx_RefNannySetupContext("floor_item", 0); 2114 2115 /* "bintrees\cwalker.pyx":121 2116 * than or equal to the given key, raises KeyError if there is no such key. 2117 * """ 2118 * self.node = ct_floor_node(self.root, key) # <<<<<<<<<<<<<< 2119 * if self.node == NULL: # given key is smaller than min-key in tree 2120 * raise KeyError(str(key)) 2121 */ 2122 __pyx_v_self->node = ct_floor_node(__pyx_v_self->root, __pyx_v_key); 2123 2124 /* "bintrees\cwalker.pyx":122 2125 * """ 2126 * self.node = ct_floor_node(self.root, key) 2127 * if self.node == NULL: # given key is smaller than min-key in tree # <<<<<<<<<<<<<< 2128 * raise KeyError(str(key)) 2129 * return (<object> self.node.key, <object> self.node.value) 2130 */ 2131 __pyx_t_1 = (__pyx_v_self->node == NULL); 2132 if (__pyx_t_1) { 2133 2134 /* "bintrees\cwalker.pyx":123 2135 * self.node = ct_floor_node(self.root, key) 2136 * if self.node == NULL: # given key is smaller than min-key in tree 2137 * raise KeyError(str(key)) # <<<<<<<<<<<<<< 2138 * return (<object> self.node.key, <object> self.node.value) 2139 * 2140 */ 2141 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 123; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2142 __Pyx_GOTREF(__pyx_t_2); 2143 __Pyx_INCREF(__pyx_v_key); 2144 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_v_key); 2145 __Pyx_GIVEREF(__pyx_v_key); 2146 __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 = 123; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2147 __Pyx_GOTREF(__pyx_t_3); 2148 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 2149 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 123; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2150 __Pyx_GOTREF(__pyx_t_2); 2151 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_t_3); 2152 __Pyx_GIVEREF(__pyx_t_3); 2153 __pyx_t_3 = 0; 2154 __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 = 123; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2155 __Pyx_GOTREF(__pyx_t_3); 2156 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 2157 __Pyx_Raise(__pyx_t_3, 0, 0, 0); 2158 __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; 2159 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 123; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2160 goto __pyx_L3; 2161 } 2162 __pyx_L3:; 2163 2164 /* "bintrees\cwalker.pyx":124 2165 * if self.node == NULL: # given key is smaller than min-key in tree 2166 * raise KeyError(str(key)) 2167 * return (<object> self.node.key, <object> self.node.value) # <<<<<<<<<<<<<< 2168 * 2169 * def ceiling_item(self, key): 2170 */ 2171 __Pyx_XDECREF(__pyx_r); 2172 __pyx_t_3 = PyTuple_New(2); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 124; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2173 __Pyx_GOTREF(__pyx_t_3); 2174 __Pyx_INCREF(((PyObject *)__pyx_v_self->node->key)); 2175 PyTuple_SET_ITEM(__pyx_t_3, 0, ((PyObject *)__pyx_v_self->node->key)); 2176 __Pyx_GIVEREF(((PyObject *)__pyx_v_self->node->key)); 2177 __Pyx_INCREF(((PyObject *)__pyx_v_self->node->value)); 2178 PyTuple_SET_ITEM(__pyx_t_3, 1, ((PyObject *)__pyx_v_self->node->value)); 2179 __Pyx_GIVEREF(((PyObject *)__pyx_v_self->node->value)); 2180 __pyx_r = ((PyObject *)__pyx_t_3); 2181 __pyx_t_3 = 0; 2182 goto __pyx_L0; 2183 2184 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 2185 goto __pyx_L0; 2186 __pyx_L1_error:; 2187 __Pyx_XDECREF(__pyx_t_2); 2188 __Pyx_XDECREF(__pyx_t_3); 2189 __Pyx_AddTraceback("bintrees.cwalker.cWalker.floor_item", __pyx_clineno, __pyx_lineno, __pyx_filename); 2190 __pyx_r = NULL; 2191 __pyx_L0:; 2192 __Pyx_XGIVEREF(__pyx_r); 2193 __Pyx_RefNannyFinishContext(); 2194 return __pyx_r; 2195 } 2196 2197 /* Python wrapper */ 2198 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_43ceiling_item(PyObject *__pyx_v_self, PyObject *__pyx_v_key); /*proto*/ 2199 static char __pyx_doc_8bintrees_7cwalker_7cWalker_42ceiling_item[] = " Get the element (k,v) pair associated with the smallest key greater\n than or equal to the given key, raises KeyError if there is no such key.\n "; 2200 static PyObject *__pyx_pw_8bintrees_7cwalker_7cWalker_43ceiling_item(PyObject *__pyx_v_self, PyObject *__pyx_v_key) { 2201 PyObject *__pyx_r = 0; 2202 __Pyx_RefNannyDeclarations 2203 __Pyx_RefNannySetupContext("ceiling_item (wrapper)", 0); 2204 __pyx_r = __pyx_pf_8bintrees_7cwalker_7cWalker_42ceiling_item(((struct __pyx_obj_8bintrees_7cwalker_cWalker *)__pyx_v_self), ((PyObject *)__pyx_v_key)); 2205 __Pyx_RefNannyFinishContext(); 2206 return __pyx_r; 2207 } 2208 2209 /* "bintrees\cwalker.pyx":126 2210 * return (<object> self.node.key, <object> self.node.value) 2211 * 2212 * def ceiling_item(self, key): # <<<<<<<<<<<<<< 2213 * """ Get the element (k,v) pair associated with the smallest key greater 2214 * than or equal to the given key, raises KeyError if there is no such key. 2215 */ 2216 2217 static PyObject *__pyx_pf_8bintrees_7cwalker_7cWalker_42ceiling_item(struct __pyx_obj_8bintrees_7cwalker_cWalker *__pyx_v_self, PyObject *__pyx_v_key) { 2218 PyObject *__pyx_r = NULL; 2219 __Pyx_RefNannyDeclarations 2220 int __pyx_t_1; 2221 PyObject *__pyx_t_2 = NULL; 2222 PyObject *__pyx_t_3 = NULL; 2223 int __pyx_lineno = 0; 2224 const char *__pyx_filename = NULL; 2225 int __pyx_clineno = 0; 2226 __Pyx_RefNannySetupContext("ceiling_item", 0); 2227 2228 /* "bintrees\cwalker.pyx":130 2229 * than or equal to the given key, raises KeyError if there is no such key. 2230 * """ 2231 * self.node = ct_ceiling_node(self.root, key) # <<<<<<<<<<<<<< 2232 * if self.node == NULL: # given key is greater than max-key in tree 2233 * raise KeyError(str(key)) 2234 */ 2235 __pyx_v_self->node = ct_ceiling_node(__pyx_v_self->root, __pyx_v_key); 2236 2237 /* "bintrees\cwalker.pyx":131 2238 * """ 2239 * self.node = ct_ceiling_node(self.root, key) 2240 * if self.node == NULL: # given key is greater than max-key in tree # <<<<<<<<<<<<<< 2241 * raise KeyError(str(key)) 2242 * return (<object> self.node.key, <object> self.node.value) 2243 */ 2244 __pyx_t_1 = (__pyx_v_self->node == NULL); 2245 if (__pyx_t_1) { 2246 2247 /* "bintrees\cwalker.pyx":132 2248 * self.node = ct_ceiling_node(self.root, key) 2249 * if self.node == NULL: # given key is greater than max-key in tree 2250 * raise KeyError(str(key)) # <<<<<<<<<<<<<< 2251 * return (<object> self.node.key, <object> self.node.value) 2252 */ 2253 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 132; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2254 __Pyx_GOTREF(__pyx_t_2); 2255 __Pyx_INCREF(__pyx_v_key); 2256 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_v_key); 2257 __Pyx_GIVEREF(__pyx_v_key); 2258 __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 = 132; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2259 __Pyx_GOTREF(__pyx_t_3); 2260 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 2261 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 132; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2262 __Pyx_GOTREF(__pyx_t_2); 2263 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_t_3); 2264 __Pyx_GIVEREF(__pyx_t_3); 2265 __pyx_t_3 = 0; 2266 __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 = 132; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2267 __Pyx_GOTREF(__pyx_t_3); 2268 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 2269 __Pyx_Raise(__pyx_t_3, 0, 0, 0); 2270 __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; 2271 {__pyx_filename = __pyx_f[0]; __pyx_lineno = 132; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2272 goto __pyx_L3; 2273 } 2274 __pyx_L3:; 2275 2276 /* "bintrees\cwalker.pyx":133 2277 * if self.node == NULL: # given key is greater than max-key in tree 2278 * raise KeyError(str(key)) 2279 * return (<object> self.node.key, <object> self.node.value) # <<<<<<<<<<<<<< 2280 */ 2281 __Pyx_XDECREF(__pyx_r); 2282 __pyx_t_3 = PyTuple_New(2); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 133; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2283 __Pyx_GOTREF(__pyx_t_3); 2284 __Pyx_INCREF(((PyObject *)__pyx_v_self->node->key)); 2285 PyTuple_SET_ITEM(__pyx_t_3, 0, ((PyObject *)__pyx_v_self->node->key)); 2286 __Pyx_GIVEREF(((PyObject *)__pyx_v_self->node->key)); 2287 __Pyx_INCREF(((PyObject *)__pyx_v_self->node->value)); 2288 PyTuple_SET_ITEM(__pyx_t_3, 1, ((PyObject *)__pyx_v_self->node->value)); 2289 __Pyx_GIVEREF(((PyObject *)__pyx_v_self->node->value)); 2290 __pyx_r = ((PyObject *)__pyx_t_3); 2291 __pyx_t_3 = 0; 2292 goto __pyx_L0; 2293 2294 __pyx_r = Py_None; __Pyx_INCREF(Py_None); 2295 goto __pyx_L0; 2296 __pyx_L1_error:; 2297 __Pyx_XDECREF(__pyx_t_2); 2298 __Pyx_XDECREF(__pyx_t_3); 2299 __Pyx_AddTraceback("bintrees.cwalker.cWalker.ceiling_item", __pyx_clineno, __pyx_lineno, __pyx_filename); 2300 __pyx_r = NULL; 2301 __pyx_L0:; 2302 __Pyx_XGIVEREF(__pyx_r); 2303 __Pyx_RefNannyFinishContext(); 2304 return __pyx_r; 2305 } 2306 static struct __pyx_vtabstruct_8bintrees_7cwalker_cWalker __pyx_vtable_8bintrees_7cwalker_cWalker; 2307 2308 static PyObject *__pyx_tp_new_8bintrees_7cwalker_cWalker(PyTypeObject *t, CYTHON_UNUSED PyObject *a, CYTHON_UNUSED PyObject *k) { 2309 struct __pyx_obj_8bintrees_7cwalker_cWalker *p; 2310 PyObject *o = (*t->tp_alloc)(t, 0); 2311 if (!o) return 0; 2312 p = ((struct __pyx_obj_8bintrees_7cwalker_cWalker *)o); 2313 p->__pyx_vtab = __pyx_vtabptr_8bintrees_7cwalker_cWalker; 2314 if (__pyx_pw_8bintrees_7cwalker_7cWalker_1__cinit__(o, __pyx_empty_tuple, NULL) < 0) { 2315 Py_DECREF(o); o = 0; 2316 } 2317 return o; 2318 } 2319 2320 static void __pyx_tp_dealloc_8bintrees_7cwalker_cWalker(PyObject *o) { 2321 { 2322 PyObject *etype, *eval, *etb; 2323 PyErr_Fetch(&etype, &eval, &etb); 2324 ++Py_REFCNT(o); 2325 __pyx_pw_8bintrees_7cwalker_7cWalker_3__dealloc__(o); 2326 if (PyErr_Occurred()) PyErr_WriteUnraisable(o); 2327 --Py_REFCNT(o); 2328 PyErr_Restore(etype, eval, etb); 2329 } 2330 (*Py_TYPE(o)->tp_free)(o); 2331 } 2332 2333 static PyMethodDef __pyx_methods_8bintrees_7cwalker_cWalker[] = { 2334 {__Pyx_NAMESTR("reset"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_5reset, METH_NOARGS, __Pyx_DOCSTR(0)}, 2335 {__Pyx_NAMESTR("key"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_7key, METH_NOARGS, __Pyx_DOCSTR(0)}, 2336 {__Pyx_NAMESTR("value"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_9value, METH_NOARGS, __Pyx_DOCSTR(0)}, 2337 {__Pyx_NAMESTR("item"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_11item, METH_NOARGS, __Pyx_DOCSTR(0)}, 2338 {__Pyx_NAMESTR("is_valid"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_13is_valid, METH_NOARGS, __Pyx_DOCSTR(0)}, 2339 {__Pyx_NAMESTR("goto"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_15goto, METH_O, __Pyx_DOCSTR(0)}, 2340 {__Pyx_NAMESTR("push"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_17push, METH_NOARGS, __Pyx_DOCSTR(0)}, 2341 {__Pyx_NAMESTR("pop"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_19pop, METH_NOARGS, __Pyx_DOCSTR(0)}, 2342 {__Pyx_NAMESTR("stack_is_empty"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_21stack_is_empty, METH_NOARGS, __Pyx_DOCSTR(0)}, 2343 {__Pyx_NAMESTR("goto_leaf"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_23goto_leaf, METH_NOARGS, __Pyx_DOCSTR(__pyx_doc_8bintrees_7cwalker_7cWalker_22goto_leaf)}, 2344 {__Pyx_NAMESTR("has_child"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_25has_child, METH_O, __Pyx_DOCSTR(0)}, 2345 {__Pyx_NAMESTR("down"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_27down, METH_O, __Pyx_DOCSTR(0)}, 2346 {__Pyx_NAMESTR("go_left"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_29go_left, METH_NOARGS, __Pyx_DOCSTR(0)}, 2347 {__Pyx_NAMESTR("go_right"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_31go_right, METH_NOARGS, __Pyx_DOCSTR(0)}, 2348 {__Pyx_NAMESTR("has_left"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_33has_left, METH_NOARGS, __Pyx_DOCSTR(0)}, 2349 {__Pyx_NAMESTR("has_right"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_35has_right, METH_NOARGS, __Pyx_DOCSTR(0)}, 2350 {__Pyx_NAMESTR("succ_item"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_37succ_item, METH_O, __Pyx_DOCSTR(__pyx_doc_8bintrees_7cwalker_7cWalker_36succ_item)}, 2351 {__Pyx_NAMESTR("prev_item"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_39prev_item, METH_O, __Pyx_DOCSTR(__pyx_doc_8bintrees_7cwalker_7cWalker_38prev_item)}, 2352 {__Pyx_NAMESTR("floor_item"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_41floor_item, METH_O, __Pyx_DOCSTR(__pyx_doc_8bintrees_7cwalker_7cWalker_40floor_item)}, 2353 {__Pyx_NAMESTR("ceiling_item"), (PyCFunction)__pyx_pw_8bintrees_7cwalker_7cWalker_43ceiling_item, METH_O, __Pyx_DOCSTR(__pyx_doc_8bintrees_7cwalker_7cWalker_42ceiling_item)}, 2354 {0, 0, 0, 0} 2355 }; 2356 2357 static PyNumberMethods __pyx_tp_as_number_cWalker = { 2358 0, /*nb_add*/ 2359 0, /*nb_subtract*/ 2360 0, /*nb_multiply*/ 2361 #if PY_MAJOR_VERSION < 3 2362 0, /*nb_divide*/ 2363 #endif 2364 0, /*nb_remainder*/ 2365 0, /*nb_divmod*/ 2366 0, /*nb_power*/ 2367 0, /*nb_negative*/ 2368 0, /*nb_positive*/ 2369 0, /*nb_absolute*/ 2370 0, /*nb_nonzero*/ 2371 0, /*nb_invert*/ 2372 0, /*nb_lshift*/ 2373 0, /*nb_rshift*/ 2374 0, /*nb_and*/ 2375 0, /*nb_xor*/ 2376 0, /*nb_or*/ 2377 #if PY_MAJOR_VERSION < 3 2378 0, /*nb_coerce*/ 2379 #endif 2380 0, /*nb_int*/ 2381 #if PY_MAJOR_VERSION < 3 2382 0, /*nb_long*/ 2383 #else 2384 0, /*reserved*/ 2385 #endif 2386 0, /*nb_float*/ 2387 #if PY_MAJOR_VERSION < 3 2388 0, /*nb_oct*/ 2389 #endif 2390 #if PY_MAJOR_VERSION < 3 2391 0, /*nb_hex*/ 2392 #endif 2393 0, /*nb_inplace_add*/ 2394 0, /*nb_inplace_subtract*/ 2395 0, /*nb_inplace_multiply*/ 2396 #if PY_MAJOR_VERSION < 3 2397 0, /*nb_inplace_divide*/ 2398 #endif 2399 0, /*nb_inplace_remainder*/ 2400 0, /*nb_inplace_power*/ 2401 0, /*nb_inplace_lshift*/ 2402 0, /*nb_inplace_rshift*/ 2403 0, /*nb_inplace_and*/ 2404 0, /*nb_inplace_xor*/ 2405 0, /*nb_inplace_or*/ 2406 0, /*nb_floor_divide*/ 2407 0, /*nb_true_divide*/ 2408 0, /*nb_inplace_floor_divide*/ 2409 0, /*nb_inplace_true_divide*/ 2410 #if PY_VERSION_HEX >= 0x02050000 2411 0, /*nb_index*/ 2412 #endif 2413 }; 2414 2415 static PySequenceMethods __pyx_tp_as_sequence_cWalker = { 2416 0, /*sq_length*/ 2417 0, /*sq_concat*/ 2418 0, /*sq_repeat*/ 2419 0, /*sq_item*/ 2420 0, /*sq_slice*/ 2421 0, /*sq_ass_item*/ 2422 0, /*sq_ass_slice*/ 2423 0, /*sq_contains*/ 2424 0, /*sq_inplace_concat*/ 2425 0, /*sq_inplace_repeat*/ 2426 }; 2427 2428 static PyMappingMethods __pyx_tp_as_mapping_cWalker = { 2429 0, /*mp_length*/ 2430 0, /*mp_subscript*/ 2431 0, /*mp_ass_subscript*/ 2432 }; 2433 2434 static PyBufferProcs __pyx_tp_as_buffer_cWalker = { 2435 #if PY_MAJOR_VERSION < 3 2436 0, /*bf_getreadbuffer*/ 2437 #endif 2438 #if PY_MAJOR_VERSION < 3 2439 0, /*bf_getwritebuffer*/ 2440 #endif 2441 #if PY_MAJOR_VERSION < 3 2442 0, /*bf_getsegcount*/ 2443 #endif 2444 #if PY_MAJOR_VERSION < 3 2445 0, /*bf_getcharbuffer*/ 2446 #endif 2447 #if PY_VERSION_HEX >= 0x02060000 2448 0, /*bf_getbuffer*/ 2449 #endif 2450 #if PY_VERSION_HEX >= 0x02060000 2451 0, /*bf_releasebuffer*/ 2452 #endif 2453 }; 2454 2455 static PyTypeObject __pyx_type_8bintrees_7cwalker_cWalker = { 2456 PyVarObject_HEAD_INIT(0, 0) 2457 __Pyx_NAMESTR("bintrees.cwalker.cWalker"), /*tp_name*/ 2458 sizeof(struct __pyx_obj_8bintrees_7cwalker_cWalker), /*tp_basicsize*/ 2459 0, /*tp_itemsize*/ 2460 __pyx_tp_dealloc_8bintrees_7cwalker_cWalker, /*tp_dealloc*/ 2461 0, /*tp_print*/ 2462 0, /*tp_getattr*/ 2463 0, /*tp_setattr*/ 2464 #if PY_MAJOR_VERSION < 3 2465 0, /*tp_compare*/ 2466 #else 2467 0, /*reserved*/ 2468 #endif 2469 0, /*tp_repr*/ 2470 &__pyx_tp_as_number_cWalker, /*tp_as_number*/ 2471 &__pyx_tp_as_sequence_cWalker, /*tp_as_sequence*/ 2472 &__pyx_tp_as_mapping_cWalker, /*tp_as_mapping*/ 2473 0, /*tp_hash*/ 2474 0, /*tp_call*/ 2475 0, /*tp_str*/ 2476 0, /*tp_getattro*/ 2477 0, /*tp_setattro*/ 2478 &__pyx_tp_as_buffer_cWalker, /*tp_as_buffer*/ 2479 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_CHECKTYPES|Py_TPFLAGS_HAVE_NEWBUFFER|Py_TPFLAGS_BASETYPE, /*tp_flags*/ 2480 0, /*tp_doc*/ 2481 0, /*tp_traverse*/ 2482 0, /*tp_clear*/ 2483 0, /*tp_richcompare*/ 2484 0, /*tp_weaklistoffset*/ 2485 0, /*tp_iter*/ 2486 0, /*tp_iternext*/ 2487 __pyx_methods_8bintrees_7cwalker_cWalker, /*tp_methods*/ 2488 0, /*tp_members*/ 2489 0, /*tp_getset*/ 2490 0, /*tp_base*/ 2491 0, /*tp_dict*/ 2492 0, /*tp_descr_get*/ 2493 0, /*tp_descr_set*/ 2494 0, /*tp_dictoffset*/ 2495 0, /*tp_init*/ 2496 0, /*tp_alloc*/ 2497 __pyx_tp_new_8bintrees_7cwalker_cWalker, /*tp_new*/ 2498 0, /*tp_free*/ 2499 0, /*tp_is_gc*/ 2500 0, /*tp_bases*/ 2501 0, /*tp_mro*/ 2502 0, /*tp_cache*/ 2503 0, /*tp_subclasses*/ 2504 0, /*tp_weaklist*/ 2505 0, /*tp_del*/ 2506 #if PY_VERSION_HEX >= 0x02060000 2507 0, /*tp_version_tag*/ 2508 #endif 2509 }; 2510 2511 static PyMethodDef __pyx_methods[] = { 2512 {0, 0, 0, 0} 2513 }; 2514 2515 #if PY_MAJOR_VERSION >= 3 2516 static struct PyModuleDef __pyx_moduledef = { 2517 PyModuleDef_HEAD_INIT, 2518 __Pyx_NAMESTR("cwalker"), 2519 0, /* m_doc */ 2520 -1, /* m_size */ 2521 __pyx_methods /* m_methods */, 2522 NULL, /* m_reload */ 2523 NULL, /* m_traverse */ 2524 NULL, /* m_clear */ 2525 NULL /* m_free */ 2526 }; 2527 #endif 2528 2529 static __Pyx_StringTabEntry __pyx_string_tab[] = { 2530 {&__pyx_kp_s_1, __pyx_k_1, sizeof(__pyx_k_1), 0, 0, 1, 0}, 2531 {&__pyx_n_s__IndexError, __pyx_k__IndexError, sizeof(__pyx_k__IndexError), 0, 0, 1, 1}, 2532 {&__pyx_n_s__KeyError, __pyx_k__KeyError, sizeof(__pyx_k__KeyError), 0, 0, 1, 1}, 2533 {&__pyx_n_s____main__, __pyx_k____main__, sizeof(__pyx_k____main__), 0, 0, 1, 1}, 2534 {&__pyx_n_s____test__, __pyx_k____test__, sizeof(__pyx_k____test__), 0, 0, 1, 1}, 2535 {&__pyx_n_s__is_valid, __pyx_k__is_valid, sizeof(__pyx_k__is_valid), 0, 0, 1, 1}, 2536 {&__pyx_n_s__item, __pyx_k__item, sizeof(__pyx_k__item), 0, 0, 1, 1}, 2537 {&__pyx_n_s__key, __pyx_k__key, sizeof(__pyx_k__key), 0, 0, 1, 1}, 2538 {&__pyx_n_s__pop, __pyx_k__pop, sizeof(__pyx_k__pop), 0, 0, 1, 1}, 2539 {&__pyx_n_s__property, __pyx_k__property, sizeof(__pyx_k__property), 0, 0, 1, 1}, 2540 {&__pyx_n_s__push, __pyx_k__push, sizeof(__pyx_k__push), 0, 0, 1, 1}, 2541 {&__pyx_n_s__reset, __pyx_k__reset, sizeof(__pyx_k__reset), 0, 0, 1, 1}, 2542 {&__pyx_n_s__value, __pyx_k__value, sizeof(__pyx_k__value), 0, 0, 1, 1}, 2543 {0, 0, 0, 0, 0, 0, 0} 2544 }; 2545 static int __Pyx_InitCachedBuiltins(void) { 2546 __pyx_builtin_property = __Pyx_GetName(__pyx_b, __pyx_n_s__property); if (!__pyx_builtin_property) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 31; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2547 __pyx_builtin_IndexError = __Pyx_GetName(__pyx_b, __pyx_n_s__IndexError); if (!__pyx_builtin_IndexError) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 65; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2548 __pyx_builtin_KeyError = __Pyx_GetName(__pyx_b, __pyx_n_s__KeyError); if (!__pyx_builtin_KeyError) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 105; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2549 return 0; 2550 __pyx_L1_error:; 2551 return -1; 2552 } 2553 2554 static int __Pyx_InitCachedConstants(void) { 2555 __Pyx_RefNannyDeclarations 2556 __Pyx_RefNannySetupContext("__Pyx_InitCachedConstants", 0); 2557 2558 /* "bintrees\cwalker.pyx":65 2559 * cpdef pop(self): 2560 * if stack_is_empty(self.stack) != 0: 2561 * raise IndexError('pop(): stack is empty') # <<<<<<<<<<<<<< 2562 * self.node = stack_pop(self.stack) 2563 * 2564 */ 2565 __pyx_k_tuple_2 = PyTuple_New(1); if (unlikely(!__pyx_k_tuple_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 65; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2566 __Pyx_GOTREF(__pyx_k_tuple_2); 2567 __Pyx_INCREF(((PyObject *)__pyx_kp_s_1)); 2568 PyTuple_SET_ITEM(__pyx_k_tuple_2, 0, ((PyObject *)__pyx_kp_s_1)); 2569 __Pyx_GIVEREF(((PyObject *)__pyx_kp_s_1)); 2570 __Pyx_GIVEREF(((PyObject *)__pyx_k_tuple_2)); 2571 __Pyx_RefNannyFinishContext(); 2572 return 0; 2573 __pyx_L1_error:; 2574 __Pyx_RefNannyFinishContext(); 2575 return -1; 2576 } 2577 2578 static int __Pyx_InitGlobals(void) { 2579 if (__Pyx_InitStrings(__pyx_string_tab) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}; 2580 return 0; 2581 __pyx_L1_error:; 2582 return -1; 2583 } 2584 2585 #if PY_MAJOR_VERSION < 3 2586 PyMODINIT_FUNC initcwalker(void); /*proto*/ 2587 PyMODINIT_FUNC initcwalker(void) 2588 #else 2589 PyMODINIT_FUNC PyInit_cwalker(void); /*proto*/ 2590 PyMODINIT_FUNC PyInit_cwalker(void) 2591 #endif 2592 { 2593 PyObject *__pyx_t_1 = NULL; 2594 PyObject *__pyx_t_2 = NULL; 2595 __Pyx_RefNannyDeclarations 2596 #if CYTHON_REFNANNY 2597 __Pyx_RefNanny = __Pyx_RefNannyImportAPI("refnanny"); 2598 if (!__Pyx_RefNanny) { 2599 PyErr_Clear(); 2600 __Pyx_RefNanny = __Pyx_RefNannyImportAPI("Cython.Runtime.refnanny"); 2601 if (!__Pyx_RefNanny) 2602 Py_FatalError("failed to import 'refnanny' module"); 2603 } 2604 #endif 2605 __Pyx_RefNannySetupContext("PyMODINIT_FUNC PyInit_cwalker(void)", 0); 2606 if ( __Pyx_check_binary_version() < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2607 __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;} 2608 __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;} 2609 #ifdef __Pyx_CyFunction_USED 2610 if (__Pyx_CyFunction_init() < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2611 #endif 2612 #ifdef __Pyx_FusedFunction_USED 2613 if (__pyx_FusedFunction_init() < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2614 #endif 2615 #ifdef __Pyx_Generator_USED 2616 if (__pyx_Generator_init() < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2617 #endif 2618 /*--- Library function declarations ---*/ 2619 /*--- Threads initialization code ---*/ 2620 #if defined(__PYX_FORCE_INIT_THREADS) && __PYX_FORCE_INIT_THREADS 2621 #ifdef WITH_THREAD /* Python build with threading support? */ 2622 PyEval_InitThreads(); 2623 #endif 2624 #endif 2625 /*--- Module creation code ---*/ 2626 #if PY_MAJOR_VERSION < 3 2627 __pyx_m = Py_InitModule4(__Pyx_NAMESTR("cwalker"), __pyx_methods, 0, 0, PYTHON_API_VERSION); Py_XINCREF(__pyx_m); 2628 #else 2629 __pyx_m = PyModule_Create(&__pyx_moduledef); 2630 #endif 2631 if (unlikely(!__pyx_m)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2632 #if PY_MAJOR_VERSION >= 3 2633 { 2634 PyObject *modules = PyImport_GetModuleDict(); if (unlikely(!modules)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2635 if (!PyDict_GetItemString(modules, "bintrees.cwalker")) { 2636 if (unlikely(PyDict_SetItemString(modules, "bintrees.cwalker", __pyx_m) < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2637 } 2638 } 2639 #endif 2640 __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;} 2641 #if CYTHON_COMPILING_IN_PYPY 2642 Py_INCREF(__pyx_b); 2643 #endif 2644 if (__Pyx_SetAttrString(__pyx_m, "__builtins__", __pyx_b) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}; 2645 /*--- Initialize various global constants etc. ---*/ 2646 if (unlikely(__Pyx_InitGlobals() < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2647 if (__pyx_module_is_main_bintrees__cwalker) { 2648 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;}; 2649 } 2650 /*--- Builtin init code ---*/ 2651 if (unlikely(__Pyx_InitCachedBuiltins() < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2652 /*--- Constants init code ---*/ 2653 if (unlikely(__Pyx_InitCachedConstants() < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2654 /*--- Global init code ---*/ 2655 /*--- Variable export code ---*/ 2656 /*--- Function export code ---*/ 2657 /*--- Type init code ---*/ 2658 __pyx_vtabptr_8bintrees_7cwalker_cWalker = &__pyx_vtable_8bintrees_7cwalker_cWalker; 2659 __pyx_vtable_8bintrees_7cwalker_cWalker.set_tree = (void (*)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, node_t *))__pyx_f_8bintrees_7cwalker_7cWalker_set_tree; 2660 __pyx_vtable_8bintrees_7cwalker_cWalker.reset = (PyObject *(*)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, int __pyx_skip_dispatch))__pyx_f_8bintrees_7cwalker_7cWalker_reset; 2661 __pyx_vtable_8bintrees_7cwalker_cWalker.push = (PyObject *(*)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, int __pyx_skip_dispatch))__pyx_f_8bintrees_7cwalker_7cWalker_push; 2662 __pyx_vtable_8bintrees_7cwalker_cWalker.pop = (PyObject *(*)(struct __pyx_obj_8bintrees_7cwalker_cWalker *, int __pyx_skip_dispatch))__pyx_f_8bintrees_7cwalker_7cWalker_pop; 2663 if (PyType_Ready(&__pyx_type_8bintrees_7cwalker_cWalker) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 14; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2664 if (__Pyx_SetVtable(__pyx_type_8bintrees_7cwalker_cWalker.tp_dict, __pyx_vtabptr_8bintrees_7cwalker_cWalker) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 14; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2665 if (__Pyx_SetAttrString(__pyx_m, "cWalker", (PyObject *)&__pyx_type_8bintrees_7cwalker_cWalker) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 14; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2666 __pyx_ptype_8bintrees_7cwalker_cWalker = &__pyx_type_8bintrees_7cwalker_cWalker; 2667 /*--- Type import code ---*/ 2668 /*--- Variable import code ---*/ 2669 /*--- Function import code ---*/ 2670 /*--- Execution code ---*/ 2671 2672 /* "bintrees\cwalker.pyx":32 2673 * 2674 * @property 2675 * def key(self): # <<<<<<<<<<<<<< 2676 * return <object> self.node.key 2677 * 2678 */ 2679 __pyx_t_1 = __Pyx_GetName((PyObject *)__pyx_ptype_8bintrees_7cwalker_cWalker, __pyx_n_s__key); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 32; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2680 __Pyx_GOTREF(__pyx_t_1); 2681 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 31; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2682 __Pyx_GOTREF(__pyx_t_2); 2683 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_t_1); 2684 __Pyx_GIVEREF(__pyx_t_1); 2685 __pyx_t_1 = 0; 2686 __pyx_t_1 = PyObject_Call(__pyx_builtin_property, ((PyObject *)__pyx_t_2), NULL); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 31; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2687 __Pyx_GOTREF(__pyx_t_1); 2688 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 2689 if (PyDict_SetItem((PyObject *)__pyx_ptype_8bintrees_7cwalker_cWalker->tp_dict, __pyx_n_s__key, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 32; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2690 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 2691 PyType_Modified(__pyx_ptype_8bintrees_7cwalker_cWalker); 2692 2693 /* "bintrees\cwalker.pyx":36 2694 * 2695 * @property 2696 * def value(self): # <<<<<<<<<<<<<< 2697 * return <object> self.node.value 2698 * 2699 */ 2700 __pyx_t_1 = __Pyx_GetName((PyObject *)__pyx_ptype_8bintrees_7cwalker_cWalker, __pyx_n_s__value); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 36; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2701 __Pyx_GOTREF(__pyx_t_1); 2702 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 35; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2703 __Pyx_GOTREF(__pyx_t_2); 2704 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_t_1); 2705 __Pyx_GIVEREF(__pyx_t_1); 2706 __pyx_t_1 = 0; 2707 __pyx_t_1 = PyObject_Call(__pyx_builtin_property, ((PyObject *)__pyx_t_2), NULL); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 35; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2708 __Pyx_GOTREF(__pyx_t_1); 2709 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 2710 if (PyDict_SetItem((PyObject *)__pyx_ptype_8bintrees_7cwalker_cWalker->tp_dict, __pyx_n_s__value, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 36; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2711 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 2712 PyType_Modified(__pyx_ptype_8bintrees_7cwalker_cWalker); 2713 2714 /* "bintrees\cwalker.pyx":40 2715 * 2716 * @property 2717 * def item(self): # <<<<<<<<<<<<<< 2718 * return (<object>self.node.key, <object>self.node.value) 2719 * 2720 */ 2721 __pyx_t_1 = __Pyx_GetName((PyObject *)__pyx_ptype_8bintrees_7cwalker_cWalker, __pyx_n_s__item); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 40; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2722 __Pyx_GOTREF(__pyx_t_1); 2723 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 39; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2724 __Pyx_GOTREF(__pyx_t_2); 2725 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_t_1); 2726 __Pyx_GIVEREF(__pyx_t_1); 2727 __pyx_t_1 = 0; 2728 __pyx_t_1 = PyObject_Call(__pyx_builtin_property, ((PyObject *)__pyx_t_2), NULL); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 39; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2729 __Pyx_GOTREF(__pyx_t_1); 2730 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 2731 if (PyDict_SetItem((PyObject *)__pyx_ptype_8bintrees_7cwalker_cWalker->tp_dict, __pyx_n_s__item, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 40; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2732 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 2733 PyType_Modified(__pyx_ptype_8bintrees_7cwalker_cWalker); 2734 2735 /* "bintrees\cwalker.pyx":44 2736 * 2737 * @property 2738 * def is_valid(self): # <<<<<<<<<<<<<< 2739 * return self.node != NULL 2740 * 2741 */ 2742 __pyx_t_1 = __Pyx_GetName((PyObject *)__pyx_ptype_8bintrees_7cwalker_cWalker, __pyx_n_s__is_valid); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 44; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2743 __Pyx_GOTREF(__pyx_t_1); 2744 __pyx_t_2 = PyTuple_New(1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 43; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2745 __Pyx_GOTREF(__pyx_t_2); 2746 PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_t_1); 2747 __Pyx_GIVEREF(__pyx_t_1); 2748 __pyx_t_1 = 0; 2749 __pyx_t_1 = PyObject_Call(__pyx_builtin_property, ((PyObject *)__pyx_t_2), NULL); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 43; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2750 __Pyx_GOTREF(__pyx_t_1); 2751 __Pyx_DECREF(((PyObject *)__pyx_t_2)); __pyx_t_2 = 0; 2752 if (PyDict_SetItem((PyObject *)__pyx_ptype_8bintrees_7cwalker_cWalker->tp_dict, __pyx_n_s__is_valid, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 44; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2753 __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; 2754 PyType_Modified(__pyx_ptype_8bintrees_7cwalker_cWalker); 2755 2756 /* "bintrees\cwalker.pyx":1 2757 * #!/usr/bin/env python # <<<<<<<<<<<<<< 2758 * #coding:utf-8 2759 * # Author: mozman 2760 */ 2761 __pyx_t_1 = PyDict_New(); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2762 __Pyx_GOTREF(((PyObject *)__pyx_t_1)); 2763 if (PyObject_SetAttr(__pyx_m, __pyx_n_s____test__, ((PyObject *)__pyx_t_1)) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;} 2764 __Pyx_DECREF(((PyObject *)__pyx_t_1)); __pyx_t_1 = 0; 2765 goto __pyx_L0; 2766 __pyx_L1_error:; 2767 __Pyx_XDECREF(__pyx_t_1); 2768 __Pyx_XDECREF(__pyx_t_2); 2769 if (__pyx_m) { 2770 __Pyx_AddTraceback("init bintrees.cwalker", __pyx_clineno, __pyx_lineno, __pyx_filename); 2771 Py_DECREF(__pyx_m); __pyx_m = 0; 2772 } else if (!PyErr_Occurred()) { 2773 PyErr_SetString(PyExc_ImportError, "init bintrees.cwalker"); 2774 } 2775 __pyx_L0:; 2776 __Pyx_RefNannyFinishContext(); 2777 #if PY_MAJOR_VERSION < 3 2778 return; 2779 #else 2780 return __pyx_m; 2781 #endif 2782 } 2783 2784 /* Runtime support code */ 2785 #if CYTHON_REFNANNY 2786 static __Pyx_RefNannyAPIStruct *__Pyx_RefNannyImportAPI(const char *modname) { 2787 PyObject *m = NULL, *p = NULL; 2788 void *r = NULL; 2789 m = PyImport_ImportModule((char *)modname); 2790 if (!m) goto end; 2791 p = PyObject_GetAttrString(m, (char *)"RefNannyAPI"); 2792 if (!p) goto end; 2793 r = PyLong_AsVoidPtr(p); 2794 end: 2795 Py_XDECREF(p); 2796 Py_XDECREF(m); 2797 return (__Pyx_RefNannyAPIStruct *)r; 2798 } 2799 #endif /* CYTHON_REFNANNY */ 2800 2801 static PyObject *__Pyx_GetName(PyObject *dict, PyObject *name) { 2802 PyObject *result; 2803 result = PyObject_GetAttr(dict, name); 2804 if (!result) { 2805 if (dict != __pyx_b) { 2806 PyErr_Clear(); 2807 result = PyObject_GetAttr(__pyx_b, name); 2808 } 2809 if (!result) { 2810 PyErr_SetObject(PyExc_NameError, name); 2811 } 2812 } 2813 return result; 2814 } 2815 2816 static void __Pyx_RaiseArgtupleInvalid( 2817 const char* func_name, 2818 int exact, 2819 Py_ssize_t num_min, 2820 Py_ssize_t num_max, 2821 Py_ssize_t num_found) 2822 { 2823 Py_ssize_t num_expected; 2824 const char *more_or_less; 2825 if (num_found < num_min) { 2826 num_expected = num_min; 2827 more_or_less = "at least"; 2828 } else { 2829 num_expected = num_max; 2830 more_or_less = "at most"; 2831 } 2832 if (exact) { 2833 more_or_less = "exactly"; 2834 } 2835 PyErr_Format(PyExc_TypeError, 2836 "%s() takes %s %" CYTHON_FORMAT_SSIZE_T "d positional argument%s (%" CYTHON_FORMAT_SSIZE_T "d given)", 2837 func_name, more_or_less, num_expected, 2838 (num_expected == 1) ? "" : "s", num_found); 2839 } 2840 2841 static CYTHON_INLINE int __Pyx_CheckKeywordStrings( 2842 PyObject *kwdict, 2843 const char* function_name, 2844 int kw_allowed) 2845 { 2846 PyObject* key = 0; 2847 Py_ssize_t pos = 0; 2848 #if CPYTHON_COMPILING_IN_PYPY 2849 if (!kw_allowed && PyDict_Next(kwdict, &pos, &key, 0)) 2850 goto invalid_keyword; 2851 return 1; 2852 #else 2853 while (PyDict_Next(kwdict, &pos, &key, 0)) { 2854 #if PY_MAJOR_VERSION < 3 2855 if (unlikely(!PyString_CheckExact(key)) && unlikely(!PyString_Check(key))) 2856 #endif 2857 if (unlikely(!PyUnicode_Check(key))) 2858 goto invalid_keyword_type; 2859 } 2860 if ((!kw_allowed) && unlikely(key)) 2861 goto invalid_keyword; 2862 return 1; 2863 invalid_keyword_type: 2864 PyErr_Format(PyExc_TypeError, 2865 "%s() keywords must be strings", function_name); 2866 return 0; 2867 #endif 2868 invalid_keyword: 2869 PyErr_Format(PyExc_TypeError, 2870 #if PY_MAJOR_VERSION < 3 2871 "%s() got an unexpected keyword argument '%s'", 2872 function_name, PyString_AsString(key)); 2873 #else 2874 "%s() got an unexpected keyword argument '%U'", 2875 function_name, key); 2876 #endif 2877 return 0; 2878 } 2879 2880 static CYTHON_INLINE void __Pyx_ErrRestore(PyObject *type, PyObject *value, PyObject *tb) { 2881 #if CYTHON_COMPILING_IN_CPYTHON 2882 PyObject *tmp_type, *tmp_value, *tmp_tb; 2883 PyThreadState *tstate = PyThreadState_GET(); 2884 tmp_type = tstate->curexc_type; 2885 tmp_value = tstate->curexc_value; 2886 tmp_tb = tstate->curexc_traceback; 2887 tstate->curexc_type = type; 2888 tstate->curexc_value = value; 2889 tstate->curexc_traceback = tb; 2890 Py_XDECREF(tmp_type); 2891 Py_XDECREF(tmp_value); 2892 Py_XDECREF(tmp_tb); 2893 #else 2894 PyErr_Restore(type, value, tb); 2895 #endif 2896 } 2897 static CYTHON_INLINE void __Pyx_ErrFetch(PyObject **type, PyObject **value, PyObject **tb) { 2898 #if CYTHON_COMPILING_IN_CPYTHON 2899 PyThreadState *tstate = PyThreadState_GET(); 2900 *type = tstate->curexc_type; 2901 *value = tstate->curexc_value; 2902 *tb = tstate->curexc_traceback; 2903 tstate->curexc_type = 0; 2904 tstate->curexc_value = 0; 2905 tstate->curexc_traceback = 0; 2906 #else 2907 PyErr_Fetch(type, value, tb); 2908 #endif 2909 } 2910 2911 #if PY_MAJOR_VERSION < 3 2912 static void __Pyx_Raise(PyObject *type, PyObject *value, PyObject *tb, 2913 CYTHON_UNUSED PyObject *cause) { 2914 Py_XINCREF(type); 2915 if (!value || value == Py_None) 2916 value = NULL; 2917 else 2918 Py_INCREF(value); 2919 if (!tb || tb == Py_None) 2920 tb = NULL; 2921 else { 2922 Py_INCREF(tb); 2923 if (!PyTraceBack_Check(tb)) { 2924 PyErr_SetString(PyExc_TypeError, 2925 "raise: arg 3 must be a traceback or None"); 2926 goto raise_error; 2927 } 2928 } 2929 #if PY_VERSION_HEX < 0x02050000 2930 if (PyClass_Check(type)) { 2931 #else 2932 if (PyType_Check(type)) { 2933 #endif 2934 #if CYTHON_COMPILING_IN_PYPY 2935 if (!value) { 2936 Py_INCREF(Py_None); 2937 value = Py_None; 2938 } 2939 #endif 2940 PyErr_NormalizeException(&type, &value, &tb); 2941 } else { 2942 if (value) { 2943 PyErr_SetString(PyExc_TypeError, 2944 "instance exception may not have a separate value"); 2945 goto raise_error; 2946 } 2947 value = type; 2948 #if PY_VERSION_HEX < 0x02050000 2949 if (PyInstance_Check(type)) { 2950 type = (PyObject*) ((PyInstanceObject*)type)->in_class; 2951 Py_INCREF(type); 2952 } 2953 else { 2954 type = 0; 2955 PyErr_SetString(PyExc_TypeError, 2956 "raise: exception must be an old-style class or instance"); 2957 goto raise_error; 2958 } 2959 #else 2960 type = (PyObject*) Py_TYPE(type); 2961 Py_INCREF(type); 2962 if (!PyType_IsSubtype((PyTypeObject *)type, (PyTypeObject *)PyExc_BaseException)) { 2963 PyErr_SetString(PyExc_TypeError, 2964 "raise: exception class must be a subclass of BaseException"); 2965 goto raise_error; 2966 } 2967 #endif 2968 } 2969 __Pyx_ErrRestore(type, value, tb); 2970 return; 2971 raise_error: 2972 Py_XDECREF(value); 2973 Py_XDECREF(type); 2974 Py_XDECREF(tb); 2975 return; 2976 } 2977 #else /* Python 3+ */ 2978 static void __Pyx_Raise(PyObject *type, PyObject *value, PyObject *tb, PyObject *cause) { 2979 PyObject* owned_instance = NULL; 2980 if (tb == Py_None) { 2981 tb = 0; 2982 } else if (tb && !PyTraceBack_Check(tb)) { 2983 PyErr_SetString(PyExc_TypeError, 2984 "raise: arg 3 must be a traceback or None"); 2985 goto bad; 2986 } 2987 if (value == Py_None) 2988 value = 0; 2989 if (PyExceptionInstance_Check(type)) { 2990 if (value) { 2991 PyErr_SetString(PyExc_TypeError, 2992 "instance exception may not have a separate value"); 2993 goto bad; 2994 } 2995 value = type; 2996 type = (PyObject*) Py_TYPE(value); 2997 } else if (PyExceptionClass_Check(type)) { 2998 PyObject *args; 2999 if (!value) 3000 args = PyTuple_New(0); 3001 else if (PyTuple_Check(value)) { 3002 Py_INCREF(value); 3003 args = value; 3004 } 3005 else 3006 args = PyTuple_Pack(1, value); 3007 if (!args) 3008 goto bad; 3009 owned_instance = PyEval_CallObject(type, args); 3010 Py_DECREF(args); 3011 if (!owned_instance) 3012 goto bad; 3013 value = owned_instance; 3014 if (!PyExceptionInstance_Check(value)) { 3015 PyErr_Format(PyExc_TypeError, 3016 "calling %R should have returned an instance of " 3017 "BaseException, not %R", 3018 type, Py_TYPE(value)); 3019 goto bad; 3020 } 3021 } else { 3022 PyErr_SetString(PyExc_TypeError, 3023 "raise: exception class must be a subclass of BaseException"); 3024 goto bad; 3025 } 3026 if (cause && cause != Py_None) { 3027 PyObject *fixed_cause; 3028 if (PyExceptionClass_Check(cause)) { 3029 fixed_cause = PyObject_CallObject(cause, NULL); 3030 if (fixed_cause == NULL) 3031 goto bad; 3032 } 3033 else if (PyExceptionInstance_Check(cause)) { 3034 fixed_cause = cause; 3035 Py_INCREF(fixed_cause); 3036 } 3037 else { 3038 PyErr_SetString(PyExc_TypeError, 3039 "exception causes must derive from " 3040 "BaseException"); 3041 goto bad; 3042 } 3043 PyException_SetCause(value, fixed_cause); 3044 } 3045 PyErr_SetObject(type, value); 3046 if (tb) { 3047 PyThreadState *tstate = PyThreadState_GET(); 3048 PyObject* tmp_tb = tstate->curexc_traceback; 3049 if (tb != tmp_tb) { 3050 Py_INCREF(tb); 3051 tstate->curexc_traceback = tb; 3052 Py_XDECREF(tmp_tb); 3053 } 3054 } 3055 bad: 3056 Py_XDECREF(owned_instance); 3057 return; 3058 } 3059 #endif 3060 3061 static CYTHON_INLINE unsigned char __Pyx_PyInt_AsUnsignedChar(PyObject* x) { 3062 const unsigned char neg_one = (unsigned char)-1, const_zero = 0; 3063 const int is_unsigned = neg_one > const_zero; 3064 if (sizeof(unsigned char) < sizeof(long)) { 3065 long val = __Pyx_PyInt_AsLong(x); 3066 if (unlikely(val != (long)(unsigned char)val)) { 3067 if (!unlikely(val == -1 && PyErr_Occurred())) { 3068 PyErr_SetString(PyExc_OverflowError, 3069 (is_unsigned && unlikely(val < 0)) ? 3070 "can't convert negative value to unsigned char" : 3071 "value too large to convert to unsigned char"); 3072 } 3073 return (unsigned char)-1; 3074 } 3075 return (unsigned char)val; 3076 } 3077 return (unsigned char)__Pyx_PyInt_AsUnsignedLong(x); 3078 } 3079 3080 static CYTHON_INLINE unsigned short __Pyx_PyInt_AsUnsignedShort(PyObject* x) { 3081 const unsigned short neg_one = (unsigned short)-1, const_zero = 0; 3082 const int is_unsigned = neg_one > const_zero; 3083 if (sizeof(unsigned short) < sizeof(long)) { 3084 long val = __Pyx_PyInt_AsLong(x); 3085 if (unlikely(val != (long)(unsigned short)val)) { 3086 if (!unlikely(val == -1 && PyErr_Occurred())) { 3087 PyErr_SetString(PyExc_OverflowError, 3088 (is_unsigned && unlikely(val < 0)) ? 3089 "can't convert negative value to unsigned short" : 3090 "value too large to convert to unsigned short"); 3091 } 3092 return (unsigned short)-1; 3093 } 3094 return (unsigned short)val; 3095 } 3096 return (unsigned short)__Pyx_PyInt_AsUnsignedLong(x); 3097 } 3098 3099 static CYTHON_INLINE unsigned int __Pyx_PyInt_AsUnsignedInt(PyObject* x) { 3100 const unsigned int neg_one = (unsigned int)-1, const_zero = 0; 3101 const int is_unsigned = neg_one > const_zero; 3102 if (sizeof(unsigned int) < sizeof(long)) { 3103 long val = __Pyx_PyInt_AsLong(x); 3104 if (unlikely(val != (long)(unsigned int)val)) { 3105 if (!unlikely(val == -1 && PyErr_Occurred())) { 3106 PyErr_SetString(PyExc_OverflowError, 3107 (is_unsigned && unlikely(val < 0)) ? 3108 "can't convert negative value to unsigned int" : 3109 "value too large to convert to unsigned int"); 3110 } 3111 return (unsigned int)-1; 3112 } 3113 return (unsigned int)val; 3114 } 3115 return (unsigned int)__Pyx_PyInt_AsUnsignedLong(x); 3116 } 3117 3118 static CYTHON_INLINE char __Pyx_PyInt_AsChar(PyObject* x) { 3119 const char neg_one = (char)-1, const_zero = 0; 3120 const int is_unsigned = neg_one > const_zero; 3121 if (sizeof(char) < sizeof(long)) { 3122 long val = __Pyx_PyInt_AsLong(x); 3123 if (unlikely(val != (long)(char)val)) { 3124 if (!unlikely(val == -1 && PyErr_Occurred())) { 3125 PyErr_SetString(PyExc_OverflowError, 3126 (is_unsigned && unlikely(val < 0)) ? 3127 "can't convert negative value to char" : 3128 "value too large to convert to char"); 3129 } 3130 return (char)-1; 3131 } 3132 return (char)val; 3133 } 3134 return (char)__Pyx_PyInt_AsLong(x); 3135 } 3136 3137 static CYTHON_INLINE short __Pyx_PyInt_AsShort(PyObject* x) { 3138 const short neg_one = (short)-1, const_zero = 0; 3139 const int is_unsigned = neg_one > const_zero; 3140 if (sizeof(short) < sizeof(long)) { 3141 long val = __Pyx_PyInt_AsLong(x); 3142 if (unlikely(val != (long)(short)val)) { 3143 if (!unlikely(val == -1 && PyErr_Occurred())) { 3144 PyErr_SetString(PyExc_OverflowError, 3145 (is_unsigned && unlikely(val < 0)) ? 3146 "can't convert negative value to short" : 3147 "value too large to convert to short"); 3148 } 3149 return (short)-1; 3150 } 3151 return (short)val; 3152 } 3153 return (short)__Pyx_PyInt_AsLong(x); 3154 } 3155 3156 static CYTHON_INLINE int __Pyx_PyInt_AsInt(PyObject* x) { 3157 const int neg_one = (int)-1, const_zero = 0; 3158 const int is_unsigned = neg_one > const_zero; 3159 if (sizeof(int) < sizeof(long)) { 3160 long val = __Pyx_PyInt_AsLong(x); 3161 if (unlikely(val != (long)(int)val)) { 3162 if (!unlikely(val == -1 && PyErr_Occurred())) { 3163 PyErr_SetString(PyExc_OverflowError, 3164 (is_unsigned && unlikely(val < 0)) ? 3165 "can't convert negative value to int" : 3166 "value too large to convert to int"); 3167 } 3168 return (int)-1; 3169 } 3170 return (int)val; 3171 } 3172 return (int)__Pyx_PyInt_AsLong(x); 3173 } 3174 3175 static CYTHON_INLINE signed char __Pyx_PyInt_AsSignedChar(PyObject* x) { 3176 const signed char neg_one = (signed char)-1, const_zero = 0; 3177 const int is_unsigned = neg_one > const_zero; 3178 if (sizeof(signed char) < sizeof(long)) { 3179 long val = __Pyx_PyInt_AsLong(x); 3180 if (unlikely(val != (long)(signed char)val)) { 3181 if (!unlikely(val == -1 && PyErr_Occurred())) { 3182 PyErr_SetString(PyExc_OverflowError, 3183 (is_unsigned && unlikely(val < 0)) ? 3184 "can't convert negative value to signed char" : 3185 "value too large to convert to signed char"); 3186 } 3187 return (signed char)-1; 3188 } 3189 return (signed char)val; 3190 } 3191 return (signed char)__Pyx_PyInt_AsSignedLong(x); 3192 } 3193 3194 static CYTHON_INLINE signed short __Pyx_PyInt_AsSignedShort(PyObject* x) { 3195 const signed short neg_one = (signed short)-1, const_zero = 0; 3196 const int is_unsigned = neg_one > const_zero; 3197 if (sizeof(signed short) < sizeof(long)) { 3198 long val = __Pyx_PyInt_AsLong(x); 3199 if (unlikely(val != (long)(signed short)val)) { 3200 if (!unlikely(val == -1 && PyErr_Occurred())) { 3201 PyErr_SetString(PyExc_OverflowError, 3202 (is_unsigned && unlikely(val < 0)) ? 3203 "can't convert negative value to signed short" : 3204 "value too large to convert to signed short"); 3205 } 3206 return (signed short)-1; 3207 } 3208 return (signed short)val; 3209 } 3210 return (signed short)__Pyx_PyInt_AsSignedLong(x); 3211 } 3212 3213 static CYTHON_INLINE signed int __Pyx_PyInt_AsSignedInt(PyObject* x) { 3214 const signed int neg_one = (signed int)-1, const_zero = 0; 3215 const int is_unsigned = neg_one > const_zero; 3216 if (sizeof(signed int) < sizeof(long)) { 3217 long val = __Pyx_PyInt_AsLong(x); 3218 if (unlikely(val != (long)(signed int)val)) { 3219 if (!unlikely(val == -1 && PyErr_Occurred())) { 3220 PyErr_SetString(PyExc_OverflowError, 3221 (is_unsigned && unlikely(val < 0)) ? 3222 "can't convert negative value to signed int" : 3223 "value too large to convert to signed int"); 3224 } 3225 return (signed int)-1; 3226 } 3227 return (signed int)val; 3228 } 3229 return (signed int)__Pyx_PyInt_AsSignedLong(x); 3230 } 3231 3232 static CYTHON_INLINE int __Pyx_PyInt_AsLongDouble(PyObject* x) { 3233 const int neg_one = (int)-1, const_zero = 0; 3234 const int is_unsigned = neg_one > const_zero; 3235 if (sizeof(int) < sizeof(long)) { 3236 long val = __Pyx_PyInt_AsLong(x); 3237 if (unlikely(val != (long)(int)val)) { 3238 if (!unlikely(val == -1 && PyErr_Occurred())) { 3239 PyErr_SetString(PyExc_OverflowError, 3240 (is_unsigned && unlikely(val < 0)) ? 3241 "can't convert negative value to int" : 3242 "value too large to convert to int"); 3243 } 3244 return (int)-1; 3245 } 3246 return (int)val; 3247 } 3248 return (int)__Pyx_PyInt_AsLong(x); 3249 } 3250 3251 static CYTHON_INLINE unsigned long __Pyx_PyInt_AsUnsignedLong(PyObject* x) { 3252 const unsigned long neg_one = (unsigned long)-1, const_zero = 0; 3253 const int is_unsigned = neg_one > const_zero; 3254 #if PY_VERSION_HEX < 0x03000000 3255 if (likely(PyInt_Check(x))) { 3256 long val = PyInt_AS_LONG(x); 3257 if (is_unsigned && unlikely(val < 0)) { 3258 PyErr_SetString(PyExc_OverflowError, 3259 "can't convert negative value to unsigned long"); 3260 return (unsigned long)-1; 3261 } 3262 return (unsigned long)val; 3263 } else 3264 #endif 3265 if (likely(PyLong_Check(x))) { 3266 if (is_unsigned) { 3267 if (unlikely(Py_SIZE(x) < 0)) { 3268 PyErr_SetString(PyExc_OverflowError, 3269 "can't convert negative value to unsigned long"); 3270 return (unsigned long)-1; 3271 } 3272 return (unsigned long)PyLong_AsUnsignedLong(x); 3273 } else { 3274 return (unsigned long)PyLong_AsLong(x); 3275 } 3276 } else { 3277 unsigned long val; 3278 PyObject *tmp = __Pyx_PyNumber_Int(x); 3279 if (!tmp) return (unsigned long)-1; 3280 val = __Pyx_PyInt_AsUnsignedLong(tmp); 3281 Py_DECREF(tmp); 3282 return val; 3283 } 3284 } 3285 3286 static CYTHON_INLINE unsigned PY_LONG_LONG __Pyx_PyInt_AsUnsignedLongLong(PyObject* x) { 3287 const unsigned PY_LONG_LONG neg_one = (unsigned PY_LONG_LONG)-1, const_zero = 0; 3288 const int is_unsigned = neg_one > const_zero; 3289 #if PY_VERSION_HEX < 0x03000000 3290 if (likely(PyInt_Check(x))) { 3291 long val = PyInt_AS_LONG(x); 3292 if (is_unsigned && unlikely(val < 0)) { 3293 PyErr_SetString(PyExc_OverflowError, 3294 "can't convert negative value to unsigned PY_LONG_LONG"); 3295 return (unsigned PY_LONG_LONG)-1; 3296 } 3297 return (unsigned PY_LONG_LONG)val; 3298 } else 3299 #endif 3300 if (likely(PyLong_Check(x))) { 3301 if (is_unsigned) { 3302 if (unlikely(Py_SIZE(x) < 0)) { 3303 PyErr_SetString(PyExc_OverflowError, 3304 "can't convert negative value to unsigned PY_LONG_LONG"); 3305 return (unsigned PY_LONG_LONG)-1; 3306 } 3307 return (unsigned PY_LONG_LONG)PyLong_AsUnsignedLongLong(x); 3308 } else { 3309 return (unsigned PY_LONG_LONG)PyLong_AsLongLong(x); 3310 } 3311 } else { 3312 unsigned PY_LONG_LONG val; 3313 PyObject *tmp = __Pyx_PyNumber_Int(x); 3314 if (!tmp) return (unsigned PY_LONG_LONG)-1; 3315 val = __Pyx_PyInt_AsUnsignedLongLong(tmp); 3316 Py_DECREF(tmp); 3317 return val; 3318 } 3319 } 3320 3321 static CYTHON_INLINE long __Pyx_PyInt_AsLong(PyObject* x) { 3322 const long neg_one = (long)-1, const_zero = 0; 3323 const int is_unsigned = neg_one > const_zero; 3324 #if PY_VERSION_HEX < 0x03000000 3325 if (likely(PyInt_Check(x))) { 3326 long val = PyInt_AS_LONG(x); 3327 if (is_unsigned && unlikely(val < 0)) { 3328 PyErr_SetString(PyExc_OverflowError, 3329 "can't convert negative value to long"); 3330 return (long)-1; 3331 } 3332 return (long)val; 3333 } else 3334 #endif 3335 if (likely(PyLong_Check(x))) { 3336 if (is_unsigned) { 3337 if (unlikely(Py_SIZE(x) < 0)) { 3338 PyErr_SetString(PyExc_OverflowError, 3339 "can't convert negative value to long"); 3340 return (long)-1; 3341 } 3342 return (long)PyLong_AsUnsignedLong(x); 3343 } else { 3344 return (long)PyLong_AsLong(x); 3345 } 3346 } else { 3347 long val; 3348 PyObject *tmp = __Pyx_PyNumber_Int(x); 3349 if (!tmp) return (long)-1; 3350 val = __Pyx_PyInt_AsLong(tmp); 3351 Py_DECREF(tmp); 3352 return val; 3353 } 3354 } 3355 3356 static CYTHON_INLINE PY_LONG_LONG __Pyx_PyInt_AsLongLong(PyObject* x) { 3357 const PY_LONG_LONG neg_one = (PY_LONG_LONG)-1, const_zero = 0; 3358 const int is_unsigned = neg_one > const_zero; 3359 #if PY_VERSION_HEX < 0x03000000 3360 if (likely(PyInt_Check(x))) { 3361 long val = PyInt_AS_LONG(x); 3362 if (is_unsigned && unlikely(val < 0)) { 3363 PyErr_SetString(PyExc_OverflowError, 3364 "can't convert negative value to PY_LONG_LONG"); 3365 return (PY_LONG_LONG)-1; 3366 } 3367 return (PY_LONG_LONG)val; 3368 } else 3369 #endif 3370 if (likely(PyLong_Check(x))) { 3371 if (is_unsigned) { 3372 if (unlikely(Py_SIZE(x) < 0)) { 3373 PyErr_SetString(PyExc_OverflowError, 3374 "can't convert negative value to PY_LONG_LONG"); 3375 return (PY_LONG_LONG)-1; 3376 } 3377 return (PY_LONG_LONG)PyLong_AsUnsignedLongLong(x); 3378 } else { 3379 return (PY_LONG_LONG)PyLong_AsLongLong(x); 3380 } 3381 } else { 3382 PY_LONG_LONG val; 3383 PyObject *tmp = __Pyx_PyNumber_Int(x); 3384 if (!tmp) return (PY_LONG_LONG)-1; 3385 val = __Pyx_PyInt_AsLongLong(tmp); 3386 Py_DECREF(tmp); 3387 return val; 3388 } 3389 } 3390 3391 static CYTHON_INLINE signed long __Pyx_PyInt_AsSignedLong(PyObject* x) { 3392 const signed long neg_one = (signed long)-1, const_zero = 0; 3393 const int is_unsigned = neg_one > const_zero; 3394 #if PY_VERSION_HEX < 0x03000000 3395 if (likely(PyInt_Check(x))) { 3396 long val = PyInt_AS_LONG(x); 3397 if (is_unsigned && unlikely(val < 0)) { 3398 PyErr_SetString(PyExc_OverflowError, 3399 "can't convert negative value to signed long"); 3400 return (signed long)-1; 3401 } 3402 return (signed long)val; 3403 } else 3404 #endif 3405 if (likely(PyLong_Check(x))) { 3406 if (is_unsigned) { 3407 if (unlikely(Py_SIZE(x) < 0)) { 3408 PyErr_SetString(PyExc_OverflowError, 3409 "can't convert negative value to signed long"); 3410 return (signed long)-1; 3411 } 3412 return (signed long)PyLong_AsUnsignedLong(x); 3413 } else { 3414 return (signed long)PyLong_AsLong(x); 3415 } 3416 } else { 3417 signed long val; 3418 PyObject *tmp = __Pyx_PyNumber_Int(x); 3419 if (!tmp) return (signed long)-1; 3420 val = __Pyx_PyInt_AsSignedLong(tmp); 3421 Py_DECREF(tmp); 3422 return val; 3423 } 3424 } 3425 3426 static CYTHON_INLINE signed PY_LONG_LONG __Pyx_PyInt_AsSignedLongLong(PyObject* x) { 3427 const signed PY_LONG_LONG neg_one = (signed PY_LONG_LONG)-1, const_zero = 0; 3428 const int is_unsigned = neg_one > const_zero; 3429 #if PY_VERSION_HEX < 0x03000000 3430 if (likely(PyInt_Check(x))) { 3431 long val = PyInt_AS_LONG(x); 3432 if (is_unsigned && unlikely(val < 0)) { 3433 PyErr_SetString(PyExc_OverflowError, 3434 "can't convert negative value to signed PY_LONG_LONG"); 3435 return (signed PY_LONG_LONG)-1; 3436 } 3437 return (signed PY_LONG_LONG)val; 3438 } else 3439 #endif 3440 if (likely(PyLong_Check(x))) { 3441 if (is_unsigned) { 3442 if (unlikely(Py_SIZE(x) < 0)) { 3443 PyErr_SetString(PyExc_OverflowError, 3444 "can't convert negative value to signed PY_LONG_LONG"); 3445 return (signed PY_LONG_LONG)-1; 3446 } 3447 return (signed PY_LONG_LONG)PyLong_AsUnsignedLongLong(x); 3448 } else { 3449 return (signed PY_LONG_LONG)PyLong_AsLongLong(x); 3450 } 3451 } else { 3452 signed PY_LONG_LONG val; 3453 PyObject *tmp = __Pyx_PyNumber_Int(x); 3454 if (!tmp) return (signed PY_LONG_LONG)-1; 3455 val = __Pyx_PyInt_AsSignedLongLong(tmp); 3456 Py_DECREF(tmp); 3457 return val; 3458 } 3459 } 3460 3461 static void __Pyx_WriteUnraisable(const char *name, CYTHON_UNUSED int clineno, 3462 CYTHON_UNUSED int lineno, CYTHON_UNUSED const char *filename) { 3463 PyObject *old_exc, *old_val, *old_tb; 3464 PyObject *ctx; 3465 __Pyx_ErrFetch(&old_exc, &old_val, &old_tb); 3466 #if PY_MAJOR_VERSION < 3 3467 ctx = PyString_FromString(name); 3468 #else 3469 ctx = PyUnicode_FromString(name); 3470 #endif 3471 __Pyx_ErrRestore(old_exc, old_val, old_tb); 3472 if (!ctx) { 3473 PyErr_WriteUnraisable(Py_None); 3474 } else { 3475 PyErr_WriteUnraisable(ctx); 3476 Py_DECREF(ctx); 3477 } 3478 } 3479 3480 static int __Pyx_check_binary_version(void) { 3481 char ctversion[4], rtversion[4]; 3482 PyOS_snprintf(ctversion, 4, "%d.%d", PY_MAJOR_VERSION, PY_MINOR_VERSION); 3483 PyOS_snprintf(rtversion, 4, "%s", Py_GetVersion()); 3484 if (ctversion[0] != rtversion[0] || ctversion[2] != rtversion[2]) { 3485 char message[200]; 3486 PyOS_snprintf(message, sizeof(message), 3487 "compiletime version %s of module '%.100s' " 3488 "does not match runtime version %s", 3489 ctversion, __Pyx_MODULE_NAME, rtversion); 3490 #if PY_VERSION_HEX < 0x02050000 3491 return PyErr_Warn(NULL, message); 3492 #else 3493 return PyErr_WarnEx(NULL, message, 1); 3494 #endif 3495 } 3496 return 0; 3497 } 3498 3499 static int __Pyx_SetVtable(PyObject *dict, void *vtable) { 3500 #if PY_VERSION_HEX >= 0x02070000 && !(PY_MAJOR_VERSION==3&&PY_MINOR_VERSION==0) 3501 PyObject *ob = PyCapsule_New(vtable, 0, 0); 3502 #else 3503 PyObject *ob = PyCObject_FromVoidPtr(vtable, 0); 3504 #endif 3505 if (!ob) 3506 goto bad; 3507 if (PyDict_SetItemString(dict, "__pyx_vtable__", ob) < 0) 3508 goto bad; 3509 Py_DECREF(ob); 3510 return 0; 3511 bad: 3512 Py_XDECREF(ob); 3513 return -1; 3514 } 3515 3516 static int __pyx_bisect_code_objects(__Pyx_CodeObjectCacheEntry* entries, int count, int code_line) { 3517 int start = 0, mid = 0, end = count - 1; 3518 if (end >= 0 && code_line > entries[end].code_line) { 3519 return count; 3520 } 3521 while (start < end) { 3522 mid = (start + end) / 2; 3523 if (code_line < entries[mid].code_line) { 3524 end = mid; 3525 } else if (code_line > entries[mid].code_line) { 3526 start = mid + 1; 3527 } else { 3528 return mid; 3529 } 3530 } 3531 if (code_line <= entries[mid].code_line) { 3532 return mid; 3533 } else { 3534 return mid + 1; 3535 } 3536 } 3537 static PyCodeObject *__pyx_find_code_object(int code_line) { 3538 PyCodeObject* code_object; 3539 int pos; 3540 if (unlikely(!code_line) || unlikely(!__pyx_code_cache.entries)) { 3541 return NULL; 3542 } 3543 pos = __pyx_bisect_code_objects(__pyx_code_cache.entries, __pyx_code_cache.count, code_line); 3544 if (unlikely(pos >= __pyx_code_cache.count) || unlikely(__pyx_code_cache.entries[pos].code_line != code_line)) { 3545 return NULL; 3546 } 3547 code_object = __pyx_code_cache.entries[pos].code_object; 3548 Py_INCREF(code_object); 3549 return code_object; 3550 } 3551 static void __pyx_insert_code_object(int code_line, PyCodeObject* code_object) { 3552 int pos, i; 3553 __Pyx_CodeObjectCacheEntry* entries = __pyx_code_cache.entries; 3554 if (unlikely(!code_line)) { 3555 return; 3556 } 3557 if (unlikely(!entries)) { 3558 entries = (__Pyx_CodeObjectCacheEntry*)PyMem_Malloc(64*sizeof(__Pyx_CodeObjectCacheEntry)); 3559 if (likely(entries)) { 3560 __pyx_code_cache.entries = entries; 3561 __pyx_code_cache.max_count = 64; 3562 __pyx_code_cache.count = 1; 3563 entries[0].code_line = code_line; 3564 entries[0].code_object = code_object; 3565 Py_INCREF(code_object); 3566 } 3567 return; 3568 } 3569 pos = __pyx_bisect_code_objects(__pyx_code_cache.entries, __pyx_code_cache.count, code_line); 3570 if ((pos < __pyx_code_cache.count) && unlikely(__pyx_code_cache.entries[pos].code_line == code_line)) { 3571 PyCodeObject* tmp = entries[pos].code_object; 3572 entries[pos].code_object = code_object; 3573 Py_DECREF(tmp); 3574 return; 3575 } 3576 if (__pyx_code_cache.count == __pyx_code_cache.max_count) { 3577 int new_max = __pyx_code_cache.max_count + 64; 3578 entries = (__Pyx_CodeObjectCacheEntry*)PyMem_Realloc( 3579 __pyx_code_cache.entries, new_max*sizeof(__Pyx_CodeObjectCacheEntry)); 3580 if (unlikely(!entries)) { 3581 return; 3582 } 3583 __pyx_code_cache.entries = entries; 3584 __pyx_code_cache.max_count = new_max; 3585 } 3586 for (i=__pyx_code_cache.count; i>pos; i--) { 3587 entries[i] = entries[i-1]; 3588 } 3589 entries[pos].code_line = code_line; 3590 entries[pos].code_object = code_object; 3591 __pyx_code_cache.count++; 3592 Py_INCREF(code_object); 3593 } 3594 3595 #include "compile.h" 3596 #include "frameobject.h" 3597 #include "traceback.h" 3598 static PyCodeObject* __Pyx_CreateCodeObjectForTraceback( 3599 const char *funcname, int c_line, 3600 int py_line, const char *filename) { 3601 PyCodeObject *py_code = 0; 3602 PyObject *py_srcfile = 0; 3603 PyObject *py_funcname = 0; 3604 #if PY_MAJOR_VERSION < 3 3605 py_srcfile = PyString_FromString(filename); 3606 #else 3607 py_srcfile = PyUnicode_FromString(filename); 3608 #endif 3609 if (!py_srcfile) goto bad; 3610 if (c_line) { 3611 #if PY_MAJOR_VERSION < 3 3612 py_funcname = PyString_FromFormat( "%s (%s:%d)", funcname, __pyx_cfilenm, c_line); 3613 #else 3614 py_funcname = PyUnicode_FromFormat( "%s (%s:%d)", funcname, __pyx_cfilenm, c_line); 3615 #endif 3616 } 3617 else { 3618 #if PY_MAJOR_VERSION < 3 3619 py_funcname = PyString_FromString(funcname); 3620 #else 3621 py_funcname = PyUnicode_FromString(funcname); 3622 #endif 3623 } 3624 if (!py_funcname) goto bad; 3625 py_code = __Pyx_PyCode_New( 3626 0, /*int argcount,*/ 3627 0, /*int kwonlyargcount,*/ 3628 0, /*int nlocals,*/ 3629 0, /*int stacksize,*/ 3630 0, /*int flags,*/ 3631 __pyx_empty_bytes, /*PyObject *code,*/ 3632 __pyx_empty_tuple, /*PyObject *consts,*/ 3633 __pyx_empty_tuple, /*PyObject *names,*/ 3634 __pyx_empty_tuple, /*PyObject *varnames,*/ 3635 __pyx_empty_tuple, /*PyObject *freevars,*/ 3636 __pyx_empty_tuple, /*PyObject *cellvars,*/ 3637 py_srcfile, /*PyObject *filename,*/ 3638 py_funcname, /*PyObject *name,*/ 3639 py_line, /*int firstlineno,*/ 3640 __pyx_empty_bytes /*PyObject *lnotab*/ 3641 ); 3642 Py_DECREF(py_srcfile); 3643 Py_DECREF(py_funcname); 3644 return py_code; 3645 bad: 3646 Py_XDECREF(py_srcfile); 3647 Py_XDECREF(py_funcname); 3648 return NULL; 3649 } 3650 static void __Pyx_AddTraceback(const char *funcname, int c_line, 3651 int py_line, const char *filename) { 3652 PyCodeObject *py_code = 0; 3653 PyObject *py_globals = 0; 3654 PyFrameObject *py_frame = 0; 3655 py_code = __pyx_find_code_object(c_line ? c_line : py_line); 3656 if (!py_code) { 3657 py_code = __Pyx_CreateCodeObjectForTraceback( 3658 funcname, c_line, py_line, filename); 3659 if (!py_code) goto bad; 3660 __pyx_insert_code_object(c_line ? c_line : py_line, py_code); 3661 } 3662 py_globals = PyModule_GetDict(__pyx_m); 3663 if (!py_globals) goto bad; 3664 py_frame = PyFrame_New( 3665 PyThreadState_GET(), /*PyThreadState *tstate,*/ 3666 py_code, /*PyCodeObject *code,*/ 3667 py_globals, /*PyObject *globals,*/ 3668 0 /*PyObject *locals*/ 3669 ); 3670 if (!py_frame) goto bad; 3671 py_frame->f_lineno = py_line; 3672 PyTraceBack_Here(py_frame); 3673 bad: 3674 Py_XDECREF(py_code); 3675 Py_XDECREF(py_frame); 3676 } 3677 3678 static int __Pyx_InitStrings(__Pyx_StringTabEntry *t) { 3679 while (t->p) { 3680 #if PY_MAJOR_VERSION < 3 3681 if (t->is_unicode) { 3682 *t->p = PyUnicode_DecodeUTF8(t->s, t->n - 1, NULL); 3683 } else if (t->intern) { 3684 *t->p = PyString_InternFromString(t->s); 3685 } else { 3686 *t->p = PyString_FromStringAndSize(t->s, t->n - 1); 3687 } 3688 #else /* Python 3+ has unicode identifiers */ 3689 if (t->is_unicode | t->is_str) { 3690 if (t->intern) { 3691 *t->p = PyUnicode_InternFromString(t->s); 3692 } else if (t->encoding) { 3693 *t->p = PyUnicode_Decode(t->s, t->n - 1, t->encoding, NULL); 3694 } else { 3695 *t->p = PyUnicode_FromStringAndSize(t->s, t->n - 1); 3696 } 3697 } else { 3698 *t->p = PyBytes_FromStringAndSize(t->s, t->n - 1); 3699 } 3700 #endif 3701 if (!*t->p) 3702 return -1; 3703 ++t; 3704 } 3705 return 0; 3706 } 3707 3708 3709 /* Type Conversion Functions */ 3710 3711 static CYTHON_INLINE int __Pyx_PyObject_IsTrue(PyObject* x) { 3712 int is_true = x == Py_True; 3713 if (is_true | (x == Py_False) | (x == Py_None)) return is_true; 3714 else return PyObject_IsTrue(x); 3715 } 3716 3717 static CYTHON_INLINE PyObject* __Pyx_PyNumber_Int(PyObject* x) { 3718 PyNumberMethods *m; 3719 const char *name = NULL; 3720 PyObject *res = NULL; 3721 #if PY_VERSION_HEX < 0x03000000 3722 if (PyInt_Check(x) || PyLong_Check(x)) 3723 #else 3724 if (PyLong_Check(x)) 3725 #endif 3726 return Py_INCREF(x), x; 3727 m = Py_TYPE(x)->tp_as_number; 3728 #if PY_VERSION_HEX < 0x03000000 3729 if (m && m->nb_int) { 3730 name = "int"; 3731 res = PyNumber_Int(x); 3732 } 3733 else if (m && m->nb_long) { 3734 name = "long"; 3735 res = PyNumber_Long(x); 3736 } 3737 #else 3738 if (m && m->nb_int) { 3739 name = "int"; 3740 res = PyNumber_Long(x); 3741 } 3742 #endif 3743 if (res) { 3744 #if PY_VERSION_HEX < 0x03000000 3745 if (!PyInt_Check(res) && !PyLong_Check(res)) { 3746 #else 3747 if (!PyLong_Check(res)) { 3748 #endif 3749 PyErr_Format(PyExc_TypeError, 3750 "__%s__ returned non-%s (type %.200s)", 3751 name, name, Py_TYPE(res)->tp_name); 3752 Py_DECREF(res); 3753 return NULL; 3754 } 3755 } 3756 else if (!PyErr_Occurred()) { 3757 PyErr_SetString(PyExc_TypeError, 3758 "an integer is required"); 3759 } 3760 return res; 3761 } 3762 3763 static CYTHON_INLINE Py_ssize_t __Pyx_PyIndex_AsSsize_t(PyObject* b) { 3764 Py_ssize_t ival; 3765 PyObject* x = PyNumber_Index(b); 3766 if (!x) return -1; 3767 ival = PyInt_AsSsize_t(x); 3768 Py_DECREF(x); 3769 return ival; 3770 } 3771 3772 static CYTHON_INLINE PyObject * __Pyx_PyInt_FromSize_t(size_t ival) { 3773 #if PY_VERSION_HEX < 0x02050000 3774 if (ival <= LONG_MAX) 3775 return PyInt_FromLong((long)ival); 3776 else { 3777 unsigned char *bytes = (unsigned char *) &ival; 3778 int one = 1; int little = (int)*(unsigned char*)&one; 3779 return _PyLong_FromByteArray(bytes, sizeof(size_t), little, 0); 3780 } 3781 #else 3782 return PyInt_FromSize_t(ival); 3783 #endif 3784 } 3785 3786 static CYTHON_INLINE size_t __Pyx_PyInt_AsSize_t(PyObject* x) { 3787 unsigned PY_LONG_LONG val = __Pyx_PyInt_AsUnsignedLongLong(x); 3788 if (unlikely(val == (unsigned PY_LONG_LONG)-1 && PyErr_Occurred())) { 3789 return (size_t)-1; 3790 } else if (unlikely(val != (unsigned PY_LONG_LONG)(size_t)val)) { 3791 PyErr_SetString(PyExc_OverflowError, 3792 "value too large to convert to size_t"); 3793 return (size_t)-1; 3794 } 3795 return (size_t)val; 3796 } 3797 3798 3799 #endif /* Py_PYTHON_H */ 3800
