12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#!/usr/bin/env python 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#coding:utf-8 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)# Author: mozman 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)# Purpose: cython unbalanced binary tree module 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)# Created: 28.04.2010 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)# Copyright (c) 2010-2013 by Manfred Moitzi 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)# License: MIT License 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)__all__ = ['cRBTree'] 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)from cwalker import cWalker 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)from cwalker cimport * 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)from ctrees cimport * 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)cdef class cRBTree: 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cdef node_t *_root 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cdef int _count 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def __cinit__(self, items=None): 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self._root = NULL 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self._count = 0 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if items: 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self.update(items) 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def __dealloc__(self): 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ct_delete_tree(self._root) 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) @property 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def count(self): 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return self._count 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def __getstate__(self): 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return dict(self.items()) 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def __setstate__(self, state): 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self.update(state) 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def clear(self): 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ct_delete_tree(self._root) 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self._count = 0 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self._root = NULL 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def get_value(self, key): 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) result = <object> ct_get_item(self._root, key) 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if result is None: 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) raise KeyError(key) 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else: 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return result[1] 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def get_walker(self): 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cdef cWalker walker 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) walker = cWalker() 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) walker.set_tree(self._root) 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return walker 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def insert(self, key, value): 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) res = rb_insert(&self._root, key, value) 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if res < 0: 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) raise MemoryError('Can not allocate memory for node structure.') 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else: 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self._count += res 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def remove(self, key): 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cdef int result 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) result = rb_remove(&self._root, key) 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if result == 0: 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) raise KeyError(str(key)) 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else: 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self._count -= 1 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def max_item(self): 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) """ Get item with max key of tree, raises ValueError if tree is empty. """ 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cdef node_t *node 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = ct_max_node(self._root) 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if node == NULL: # root is None 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) raise ValueError("Tree is empty") 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return (<object>node.key, <object>node.value) 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def min_item(self): 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) """ Get item with min key of tree, raises ValueError if tree is empty. """ 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cdef node_t *node 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node = ct_min_node(self._root) 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if node == NULL: # root is None 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) raise ValueError("Tree is empty") 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return (<object>node.key, <object>node.value) 87