Metadata-Version: 2.4
Name: py-fast-trie
Version: 2.2.0
Summary: Python library for tries with different grades of fastness.
Author-email: Jeremy Brown <mischif@noreply.codeberg.org>
License-Expression: LicenseRef-Prosperity-3.0.0
Project-URL: source, https://codeberg.org/mischif/py-fast-trie
Project-URL: releasenotes, https://codeberg.org/mischif/py-fast-trie/releases/latest
Project-URL: changelog, https://codeberg.org/mischif/py-fast-trie/src/CHANGELOG.md
Project-URL: issues, https://codeberg.org/mischif/py-fast-trie/issues
Keywords: x-fast,y-fast,trie,data structures
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Developers
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Requires-Python: ~=3.10
Description-Content-Type: text/markdown
License-File: LICENSE.md
Requires-Dist: py-hopscotch-dict
Requires-Dist: sortedcontainers
Dynamic: license-file

py-fast-trie
============

[![Python Versions](https://img.shields.io/pypi/pyversions/py-fast-trie?style=for-the-badge)](https://pypi.org/project/py-fast-trie/)
[![Package Version](https://img.shields.io/pypi/v/py-fast-trie?style=for-the-badge)](https://pypi.org/project/py-fast-trie/)

py-fast-trie is a package that contains pure-Python implementations of an [X-fast Trie](https://en.wikipedia.org/wiki/X-fast_trie) and a [Y-fast trie](https://en.wikipedia.org/wiki/Y-fast_trie), as described in the [foundational paper](https://web.archive.org/web/20230818235641/https://users.cs.utah.edu/~pandey/courses/cs6968/spring23/papers/yfast.pdf).

The most notable benefit of X-fast and Y-fast tries compared to more common data structures such as binary search trees is that searches are log-logarithmic in the cardinality of the universe as opposed to being logarithmic in the number of elements in the structure itself; For reference if you needed to store 2^20 items with a potential maximum value of 2^32 - 1, finding a particular item would take 20 operations in a red/black or AVL tree, but only 5 with an X-fast or Y-fast trie.

Usage
-----

The interfaces of the X-fast and Y-fast tries are identical, the Y-fast trie is used here as an example.

	>>> from py_fast_trie import YFastTrie
	>>> t = YFastTrie(max_length=32)		# The library defaults to the machine's word size
	>>> for i in range(10, 13):
	...     t += i					# Value insertion/removal operations have intuitive
	>>> t.min					# shorthands
	10
	>>> t += b'\x0d'				# The library can handle byte strings less than the
	>>> t.max					# max length by treating them as integers
	13
	>>> for val in t:
	...     print val
	10
	11
	12
	13
	>>> t < 12					# Predecessor/successor queries have intuitive
	11						# shorthands
	>>> t > 0
	10
	t -= 13
	>>> t > 12
	>>>

License
-------

py-hopscotch-dict is released under version 3.0.0 of the [Prosperity Public License](./LICENSE.txt)
