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