[Python-ideas] Trie ABC?

[Nick Coghlan]

On Mon, May 6, 2013 at 3:03 PM, Stephen J. Turnbull <stephen at xemacs.org> wrote:
> Geoffrey Sneddon writes:
>
>  > Currently there are a large number of trie implementations for Python,
>  > all with slightly different APIs. It would be nice to introduce a ABC
>  > for Tries to attempt to unify these.
>
> I don't understand why you want an ABC.  Mapping is the ABC, Trie is a
> concrete implementation, and an actual trie is an instance of Trie.
> Wouldn't canonizing one of the existing implementations into the
> stdlib be the straight way forward?

I believe it is the extra trie specific method names that Geoffrey is
interested in standardising:

longest_prefix(item)
keys_with_prefix(prefix)
has_key_with_prefix(prefix)

Note that using "prefix" as the parameter for the first operation is
incorrect (as it is not a prefix, it is the candidate item to be
matched against), and that using "has_keys_with_prefix" as the name
for the last operation is wrong if the condition is "at least one key"
- including the plural in the name suggests the condition is "at least
two keys".

This seems reasonable, although I think it may make more sense in
conjunction with a reference implementation in the standard library.

Cheers,
Nick.

--
Nick Coghlan   |   ncoghlan at gmail.com   |   Brisbane, Australia