1 #!/usr/bin/env python 2 #coding:utf-8 3 # Author: mozman 4 # Purpose: cython unbalanced binary tree module 5 # Created: 28.04.2010 6 # Copyright (c) 2010-2013 by Manfred Moitzi 7 # License: MIT License 8 9 __all__ = ['cBinaryTree'] 10 11 from cwalker import cWalker 12 13 from cwalker cimport * 14 from ctrees cimport * 15 16 cdef class cBinaryTree: 17 cdef node_t *_root 18 cdef int _count 19 20 def __cinit__(self, items=None): 21 self._root = NULL 22 self._count = 0 23 if items: 24 self.update(items) 25 26 def __dealloc__(self): 27 ct_delete_tree(self._root) 28 29 @property 30 def count(self): 31 return self._count 32 33 def __getstate__(self): 34 return dict(self.items()) 35 36 def __setstate__(self, state): 37 self.update(state) 38 39 def clear(self): 40 ct_delete_tree(self._root) 41 self._count = 0 42 self._root = NULL 43 44 def get_value(self, key): 45 result = <object> ct_get_item(self._root, key) 46 if result is None: 47 raise KeyError(key) 48 else: 49 return result[1] 50 51 def get_walker(self): 52 cdef cWalker walker 53 walker = cWalker() 54 walker.set_tree(self._root) 55 return walker 56 57 def insert(self, key, value): 58 res = ct_bintree_insert(&self._root, key, value) 59 if res < 0: 60 raise MemoryError('Can not allocate memory for node structure.') 61 self._count += res 62 63 def remove(self, key): 64 cdef int result 65 result = ct_bintree_remove(&self._root, key) 66 if result == 0: 67 raise KeyError(str(key)) 68 else: 69 self._count -= 1 70 71 def max_item(self): 72 """ Get item with max key of tree, raises ValueError if tree is empty. """ 73 cdef node_t *node 74 node = ct_max_node(self._root) 75 if node == NULL: # root is None 76 raise ValueError("Tree is empty") 77 return (<object>node.key, <object>node.value) 78 79 def min_item(self): 80 """ Get item with min key of tree, raises ValueError if tree is empty. """ 81 cdef node_t *node 82 node = ct_min_node(self._root) 83 if node == NULL: # root is None 84 raise ValueError("Tree is empty") 85 return (<object>node.key, <object>node.value) 86
