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
11from cwalker import cWalker
12
13from cwalker cimport *
14from ctrees cimport *
15
16cdef 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