src/third_party/bintrees/bintrees/cwalker.pyx

   1 #!/usr/bin/env python
   2 #coding:utf-8
   3 # Author:  mozman
   4 # Purpose: tree walker for cython trees
   5 # Created: 07.05.2010
   6 # Copyright (c) 2010-2013 by Manfred Moitzi
   7 # License: MIT License
   8
   9 DEF MAXSTACK=32
  10
  11 from stack cimport *
  12 from ctrees cimport *
  13
  14 cdef class cWalker:
  15     def __cinit__(self):
  16         self.root = NULL
  17         self.node = NULL
  18         self.stack = stack_init(MAXSTACK)
  19
  20     def __dealloc__(self):
  21         stack_delete(self.stack)
  22
  23     cdef void set_tree(self, node_t *root):
  24         self.root = root
  25         self.reset()
  26
  27     cpdef reset(self):
  28         stack_reset(self.stack)
  29         self.node = self.root
  30
  31     @property
  32     def key(self):
  33         return <object> self.node.key
  34
  35     @property
  36     def value(self):
  37         return <object> self.node.value
  38
  39     @property
  40     def item(self):
  41         return (<object>self.node.key, <object>self.node.value)
  42
  43     @property
  44     def is_valid(self):
  45         return self.node != NULL
  46
  47     def goto(self, key):
  48         cdef int cval
  49         self.node = self.root
  50         while self.node != NULL:
  51             cval = ct_compare(key, <object> self.node.key)
  52             if cval == 0:
  53                 return True
  54             elif cval < 0:
  55                 self.node = self.node.link[0]
  56             else:
  57                 self.node = self.node.link[1]
  58         return False
  59
  60     cpdef push(self):
  61         stack_push(self.stack, self.node)
  62
  63     cpdef pop(self):
  64         if stack_is_empty(self.stack) != 0:
  65             raise IndexError('pop(): stack is empty')
  66         self.node = stack_pop(self.stack)
  67
  68     def stack_is_empty(self):
  69         return <bint> stack_is_empty(self.stack)
  70
  71     def goto_leaf(self):
  72         """ get a leaf node """
  73         while self.node != NULL:
  74             if self.node.link[0] != NULL:
  75                 self.node = self.node.link[0]
  76             elif self.node.link[1] != NULL:
  77                 self.node = self.node.link[1]
  78             else:
  79                 return
  80
  81     def has_child(self, int direction):
  82         return self.node.link[direction] != NULL
  83
  84     def down(self, int direction):
  85         self.node = self.node.link[direction]
  86
  87     def go_left(self):
  88         self.node = self.node.link[0]
  89
  90     def go_right(self):
  91         self.node = self.node.link[1]
  92
  93     def has_left(self):
  94         return self.node.link[0] != NULL
  95
  96     def has_right(self):
  97         return self.node.link[1] != NULL
  98
  99     def succ_item(self, key):
 100         """ Get successor (k,v) pair of key, raises KeyError if key is max key
 101         or key does not exist.
 102         """
 103         self.node = ct_succ_node(self.root, key)
 104         if self.node == NULL: # given key is biggest in tree
 105             raise KeyError(str(key))
 106         return (<object> self.node.key, <object> self.node.value)
 107
 108     def prev_item(self, key):
 109         """ Get predecessor (k,v) pair of key, raises KeyError if key is min key
 110         or key does not exist.
 111         """
 112         self.node = ct_prev_node(self.root, key)
 113         if self.node == NULL: # given key is smallest in tree
 114             raise KeyError(str(key))
 115         return (<object> self.node.key, <object> self.node.value)
 116
 117     def floor_item(self, key):
 118         """ Get the element (k,v) pair associated with the greatest key less
 119         than or equal to the given key, raises KeyError if there is no such key.
 120         """
 121         self.node = ct_floor_node(self.root, key)
 122         if self.node == NULL:  # given key is smaller than min-key in tree
 123             raise KeyError(str(key))
 124         return (<object> self.node.key, <object> self.node.value)
 125
 126     def ceiling_item(self, key):
 127         """ Get the element (k,v) pair associated with the smallest key greater
 128         than or equal to the given key, raises KeyError if there is no such key.
 129         """
 130         self.node = ct_ceiling_node(self.root, key)
 131         if self.node == NULL:  # given key is greater than max-key in tree
 132             raise KeyError(str(key))
 133         return (<object> self.node.key, <object> self.node.value)