Implementing a recursive struct (e.g. trie node)

[Aaron Voelker]

I am trying to implement a prefix tree (a "trie") in Cython, because
my current Python implementation eats up far too much memory from the
overhead of every edge/node.

A part of that requires that I make a struct, which, as an attribute,
has an array of pointers to itself.

DEF SIZE 62
cdef struct TrieNode # forward declaration
cdef struct TrieNode:
cdef TrieNode children[SIZE]
cdef object value

This gives a syntax error. When I tried to use a cdef class instead, I
got "Array element cannot be a Python object".

What is the correct way to achieve the desired result? Thanks in
advance!

Aaron

[Robert Bradshaw]

There are two options. To create a cdef class instead of a struct, i.e.

cdef class TrieNode
cdef list children
cdef object value

(Unfortunately we don't have a way to type the members of the list...)
This should still be rather efficient. Alternatively, you can do

from cpython cimport PyObject
DEF SIZE = 62
cdef struct TrieNode:
TrieNode *children[SIZE] # or just *children
PyObject* value

and manually incref/decref the value node (and, of course, allocate
memory for the children, you can't have a struct that contains itself
or an array of itself--what would the memory layout look like?).
Personally, I think the cdef class option is much cleaner.

- Robert