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