nlehuen / ctst Goto Github PK

Currently, only a malloc-based storage has been implemented. This is the
bare minimum and is pretty inefficient (the ratios computed in the test
program show it).

It is possible to implement a compact in-memory storage by using a careful
encoding of node links (some bits in a short header tell which links are
defined in the node, while the remaining bits are for the number of
characters in the node).

Implement a tst_contains method that just checks whether a key has
associated data in the tree. This is useful in the case where loading data
in memory is expensive, so one might want not to use ctst_get for this kind
of test.

As the storage system is abstracted, a disk-based storage could be
implemented for big trees.

Like in pytst, implement a fuzzy matcher, which call a callback method for
all key/value pairs within a given Levenshtein distance of an input key.

Extra credits for implementing the fuzzy match with the Damerau-Levenshtein
distance :

http://en.wikipedia.org/wiki/Damerau-Levenshtein_distance

Like in pytst, implement an Aho-Corasick scanner. This would take an input
string and call callback methods as soon as substrings match some key in
the tree. A file input could also be implemented.

Implement iterators that match the visitors : full, from key, of fuzzy.

Should be implemented with the same techniques as used in the visitor. The iterator
object will keep a ctst_stack instance to maintain its state of iteration. With a
little luck, no other state is required and a stack object IS an iterator. In this
case, write iterator functions that use the stack and refactor _ctst_visit_all to ise
those functions.

Well obviously no other state than the stack is required when iterating on all the
entries of the tree, but if there is a query (a wildcard or fuzzy search) the query
and position in the query must be stored.

Implement wildcard matches like in pytst, that is to say a way to query the tree with
simple wildcards like ? or \* (glob-style, NOT regex style which would be
much more complicated).