Skip to main content

Python dictionary and set implemented using prefix trees

Project description

This package provides PrefixDict, a dictionary like object, and PrefixSet, set like object, that are implemented using using prefix trees, or tries. Using tries provides the following unique features when compared to the builtin dict and set objects.

  • Keys are returned in sorted order.

  • Slice operations for getting, setting and deleting values.

Trie based collections are useful when ordered access to key and values is a requirement.

Usage

PrefixDict and PrefixSet behave like the builtin dict and set objects. They are implementations of the MutableMapping and MutableSet abstract base classes. They also support the same constructors as the builtins.

>>> from prefixtree import PrefixDict
>>> pd = PrefixDict(a=0, b=1)
>>> pd['c'] = 2
>>> 'a' in pd
True
>>> 'd' in pd
False

The only incompatible API difference between prefixtree collections and the builtins is that PrefixDict and PrefixSet only support strings as keys. Unicode strings will be encoded to byte strings before and after use.

Unlike the bultins, it’s possible to use slices when getting, setting and deleting values from prefixtree collecionts.

>>> list(pd['a':'c'])
[0, 1, 2]
>>> pd[:'b'] = [4, 3]
>>> list(pd['a':'c':-1])
[2, 3, 4]

PrefixDict also has additional methods not present on builtin dicts.

  • commonprefix(key), to find the longest comment prefix with current keys.

  • startswith(prefix), iterates over current keys with matching prefix.

Refer to the full prefixtree documentation on Read The Docs for details.

Compatability

prefixtree is implemented to be compatible with Python 2.x and Python 3.x. It has been tested against the following Python implementations:

  • CPython 2.6

  • CPython 2.7

  • CPython 3.2

  • PyPy 1.9.0

Continuous integration testing is provided by Travis CI.

Issues

Source code for prefixtree is hosted on GitHub. Any bug reports or feature requests can be made using GitHub’s issues system.

build_status

Further Reading

Full documentation for prefixtree is hosted by Read The Docs.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

prefixtree-0.2.tar.gz (580.0 kB view details)

Uploaded Source

File details

Details for the file prefixtree-0.2.tar.gz.

File metadata

  • Download URL: prefixtree-0.2.tar.gz
  • Upload date:
  • Size: 580.0 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No

File hashes

Hashes for prefixtree-0.2.tar.gz
Algorithm Hash digest
SHA256 3c012520d21dd39685cc13f11461d42a32b67d18ba80fccaac8252cc2d22e283
MD5 fdeae4935baeef81e47ee21059521993
BLAKE2b-256 28c090789ffd3fef08972f28ab385ee16a59c30bb08e212bb2c5c16a04d33ff6

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page