I am trying to implement a generic sorting algorithm in cython. So, I created the following module which implements the Heapsort algorithm inside the class sorter_t:
# file general_sort_c.pyx
from libc.stdint cimport int32_t
cdef bint bint_true = 1
cdef bint bint_false = 0
cdef class sorter_t:
cdef object sortable_object
def __init__(self,sortable_object):
self.sortable_object = sortable_object
cpdef sort_c(self):
"""
https://en.wikipedia.org/wiki/Heapsort
"""
cdef int32_t end
cdef int32_t count = self.sortable_object.num_elements_int32
self.heapify_c(count)
end = count-1
while end > 0:
self.sortable_object.swap_c(0,end)
end = end - 1
self.siftDown_c(0,end)
cdef heapify_c(self,int32_t count):
cdef int32_t start = (count - 2)/2
while start >= 0:
self.siftDown_c(start, count-1)
start -= 1
cdef siftDown_c(self,int32_t start, int32_t end):
cdef int32_t root = start
cdef int32_t swap
cdef int32_t child
while root * 2 + 1 <= end:
child = root * 2 + 1
swap = root
# if "swap" < "child" then ...
if self.sortable_object.lt_c(swap,child) == 1:
swap = child
if child+1 <= end and self.sortable_object.lt_c(swap,child+1) == 1:
swap = child + 1
if swap != root:
self.sortable_object.swap_c(root,swap)
root = swap
else:
return
When you define an object of type sorter_t you must provide a sortable_object which has its own particular implementations of the cdef functions lt_c (for comparing if one element is smaller than the other) and swap_c (for swapping elements).
For instance, the following code will define and create a sortable_object from a list, and will test the implementation of "sorter_t" using that sortable_object.
import numpy
cimport numpy
from libc.stdint cimport int32_t
import general_sort_c
cdef class sortable_t:
cdef public int32_t num_elements_int32
cdef int32_t [:] mv_lista
def __init__(self,int32_t [:] mv_lista):
self.num_elements_int32 = mv_lista.shape[0]
self.mv_lista = mv_lista
cdef public bint lt_c(self, int32_t left, int32_t right):
if self.mv_lista[left] < self.mv_lista[right]:
return 1 # True
else:
return 0 # False
cdef public bint gt_c(self, int32_t left, int32_t right):
if self.mv_lista[left] > self.mv_lista[right]:
return 1 # True
else:
return 0 # False
cdef public swap_c(self, int32_t left, int32_t right):
cdef int32_t tmp
tmp = self.mv_lista[right]
self.mv_lista[right] = self.mv_lista[left]
self.mv_lista[left] = tmp
def probar():
lista = numpy.array([3,4,1,7],dtype=numpy.int32)
cdef int32_t [:] mv_lista = lista
cdef sortable = sortable_t(mv_lista)
cdef sorter = general_sort_c.sorter_t(sortable)
sorter.sort_increasing_c()
print list(lista)
After compiling both .pyx files and running following commands in an IPython console, the following error emerges:
In [1]: import test_general_sort_c as tgs
In [2]: tgs.probar()
...
general_sort_c.sorter_t.siftDown_increasing_c (general_sort_c.c:1452)()
132
133 #if mv_tnet_time[swap] < mv_tnet_time[child]:
--> 134 if self.sortable_object.lt_c(swap,child) == bint_true:
135 swap = child
136
AttributeError: 'test_general_sort_c.sortable_t' object has no attribute 'lt_c'
So, the problem is that the implementation of the function lt_c is not visible from the code in module general_sort_c.pyx. If I define the function lt_c using cpdef instead of cdef it will work, but then you have a lot of Python overhead. How to call this function in a cdef ("pure C") way?
