pygtrie
=======
pygtrie is a pure Python implementation of a trie data structure
compatible with Python 2.x and Python 3.x.
`Trie data structure <http://en.wikipedia.org/wiki/Trie>`_, also known
as radix or prefix tree, is a tree associating keys to values where
all the descendants of a node have a common prefix (associated with
that node).
The trie module contains ``Trie``, ``CharTrie`` and ``StringTrie``
classes each implementing a mutable mapping interface, i.e. ``dict``
interface. As such, in most circumstances, ``Trie`` could be used as
a drop-in replacement for a ``dict``, but the prefix nature of the
data structure is trie’s real strength.
The module also contains ``PrefixSet`` class which uses a trie to
store a set of prefixes such that a key is contained in the set if it
or its prefix is stored in the set.
Features
--------
- A full mutable mapping implementation.
- Supports iterating over as well as deleting a subtrie.
- Supports prefix checking as well as shortest and longest prefix
look-up.
- Extensible for any kind of user-defined keys.
- A PrefixSet supports “all keys starting with given prefix” logic.
- Can store any value including None.
Installation
------------
To install pygtrie, simply run::
pip install pygtrie
or by adding line such as::
pygtrie == 2.*
to project’s `requirements file
<https://pip.pypa.io/en/latest/user_guide/#requirements-files>`_.
Alternatively, if installation from source is desired, it can be
achieved by executing::
python setup.py install
Version History
---------------
2.5: TBD
- Add ``pygtrie.Trie.merge`` method which merges structures of two
tries.
- Add ``pygtrie.Trie.strictly_equals`` method which compares two
tries with stricter rules than regular equality operator. It’s not
sufficient that keys and values are the same but the structure of
the tries must be the same as well. For example:
>>> t0 = StringTrie({'foo/bar.baz': 42}, separator='/')
>>> t1 = StringTrie({'foo/bar.baz': 42}, separator='.')
>>> t0 == t1
True
>>> t0.strictly_equals(t1)
False
- Fix ``pygtrie.Trie.__eq__`` implementation such that key values
are taken into consideration rather than just looking at trie
structure. To see what this means it’s best to look at a few
examples. Firstly:
>>> t0 = StringTrie({'foo/bar': 42}, separator='/')
>>> t1 = StringTrie({'foo.bar': 42}, separator='.')
>>> t0 == t1
False
This used to be true since the two tries have the same node
structure. However, as far as Mapping interface is concerned, they
use different keys, i.e. ```set(t0) != set(t1)``. Secondly:
>>> t0 = StringTrie({'foo/bar.baz': 42}, separator='/')
>>> t1 = StringTrie({'foo/bar.baz': 42}, separator='.')
>>> t0 == t1
True
This used to be false since the two tries have different node
structures (the first one splits key into ``('foo', 'bar.baz')``
while the second into ``('foo/bar', 'baz')``). However, their keys
are the same, i.e. ```set(t0) == set(t1)``. And lastly:
>>> t0 = Trie({'foo': 42})
>>> t1 = CharTrie({'foo': 42})
>>> t0 == t1
False
This used to be true since the two tries have the same node
structure. However, the two classes return key as different values.
``pygtrie.Trie`` returns keys as tuples while
``pygtrie.CharTrie`` returns them as strings.
2.4.2: 2021/01/03
- Remove use of ‘super’ in ``setup.py`` to fix compatibility with
Python 2.7. This changes build code only; no changes to the library
itself.
2.4.1: 2020/11/20
- Remove dependency on ``packaging`` module from ``setup.py`` to fix
installation on systems without that package. This changes build
code only; no changes to the library itself. [Thanks to Eric
McLachlan for reporting]
2.4.0: 2020/11/19 [pulled back from PyPi]
- Change ``children`` argument of the ``node_factory`` passed to
``pygtrie.Trie.traverse`` from a generator to an iterator with
a custom bool conversion. This allows checking whether node has
children without having to iterate over them (``bool(children)``)
To test whether this feature is available, one can check whether
`Trie.traverse.uses_bool_convertible_children` property is true,
e.g.: ``getattr(pygtrie.Trie.traverse,
'uses_bool_convertible_children', False)``.
[Thanks to Pallab Pain for suggesting the feature]
2.3.3: 2020/04/04
- Fix to ‘``AttributeError``: ``_NoChildren`` object has no
attribute ``sorted_items``’ failure when iterating over a trie with
sorting enabled. [Thanks to Pallab Pain for reporting]
- Add ``value`` property setter to step objects returned by
``pygtrie.Trie.walk_towards`` et al. This deprecates the
``set`` method.
- The module now exports `pygtrie.__version__` making it possible to
determine version of the library at run-time.
2.3.2: 2019/07/18
- Trivial metadata fix
2.3.1: 2019/07/18 [pulled back from PyPi]
- Fix to ``pygtrie.PrefixSet`` initialisation incorrectly storing
elements even if their prefixes are also added to the set.
For example, ``PrefixSet(('foo', 'foobar'))`` incorrectly resulted
in a two-element set even though the interface dictates that only
``foo`` is kept (recall that if ``foo`` is member of the set,
``foobar`` is as well). [Thanks to Tal Maimon for reporting]
- Fix to ``pygtrie.Trie.copy`` method not preserving
enable-sorting flag and, in case of ``pygtrie.StringTrie``,
``separator`` property.
- Add support for the ``copy`` module so ``copy.copy`` can now be
used with trie objects.
- Leafs and nodes with just one child use more memory-optimised
representation which reduces overall memory usage of a trie
structure.
- Minor performance improvement for adding new elements to
a ``pygtrie.PrefixSet``.
- Improvements to string representation of objects which now includes
type and, for ``pygtrie.StringTrie`` object, value of separator
property.
2.3: 2018/08/10
- New ``pygtrie.Trie.walk_towards`` method allows walking a path
towards a node with given key accessing each step of the path.
Compared to `pygtrie.Trie.walk_prefixes` method, steps for nodes
without assigned values are returned.
- Fix to ``pygtrie.PrefixSet.copy`` not preserving type of backing
trie.
- ``pygtrie.StringTrie`` now checks and explicitly rejects empty
separators. Previously empty separator would be accepted but lead
to confusing errors later on. [Thanks to Waren Long]
- Various documentation improvements, Python 2/3 compatibility and
test coverage (python-coverage reports 100%).
Raw data
{
"_id": null,
"home_page": "https://github.com/mina86/pygtrie",
"name": "pygtrie",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "trie,prefix tree,data structure",
"author": "Michal Nazarewicz",
"author_email": "mina86@mina86.com",
"download_url": "https://files.pythonhosted.org/packages/b9/13/55deec25bf09383216fa7f1dfcdbfca40a04aa00b6d15a5cbf25af8fce5f/pygtrie-2.5.0.tar.gz",
"platform": "Platform Independent",
"description": "pygtrie\n=======\n\npygtrie is a pure Python implementation of a trie data structure\ncompatible with Python 2.x and Python 3.x.\n\n`Trie data structure <http://en.wikipedia.org/wiki/Trie>`_, also known\nas radix or prefix tree, is a tree associating keys to values where\nall the descendants of a node have a common prefix (associated with\nthat node).\n\nThe trie module contains ``Trie``, ``CharTrie`` and ``StringTrie``\nclasses each implementing a mutable mapping interface, i.e. ``dict``\ninterface. As such, in most circumstances, ``Trie`` could be used as\na drop-in replacement for a ``dict``, but the prefix nature of the\ndata structure is trie\u2019s real strength.\n\nThe module also contains ``PrefixSet`` class which uses a trie to\nstore a set of prefixes such that a key is contained in the set if it\nor its prefix is stored in the set.\n\nFeatures\n--------\n\n- A full mutable mapping implementation.\n\n- Supports iterating over as well as deleting a subtrie.\n\n- Supports prefix checking as well as shortest and longest prefix\n look-up.\n\n- Extensible for any kind of user-defined keys.\n\n- A PrefixSet supports \u201call keys starting with given prefix\u201d logic.\n\n- Can store any value including None.\n\nInstallation\n------------\n\nTo install pygtrie, simply run::\n\n pip install pygtrie\n\nor by adding line such as::\n\n pygtrie == 2.*\n\nto project\u2019s `requirements file\n<https://pip.pypa.io/en/latest/user_guide/#requirements-files>`_.\nAlternatively, if installation from source is desired, it can be\nachieved by executing::\n\n python setup.py install\n\nVersion History\n---------------\n\n2.5: TBD\n\n- Add ``pygtrie.Trie.merge`` method which merges structures of two\n tries.\n\n- Add ``pygtrie.Trie.strictly_equals`` method which compares two\n tries with stricter rules than regular equality operator. It\u2019s not\n sufficient that keys and values are the same but the structure of\n the tries must be the same as well. For example:\n\n >>> t0 = StringTrie({'foo/bar.baz': 42}, separator='/')\n >>> t1 = StringTrie({'foo/bar.baz': 42}, separator='.')\n >>> t0 == t1\n True\n >>> t0.strictly_equals(t1)\n False\n\n- Fix ``pygtrie.Trie.__eq__`` implementation such that key values\n are taken into consideration rather than just looking at trie\n structure. To see what this means it\u2019s best to look at a few\n examples. Firstly:\n\n >>> t0 = StringTrie({'foo/bar': 42}, separator='/')\n >>> t1 = StringTrie({'foo.bar': 42}, separator='.')\n >>> t0 == t1\n False\n\n This used to be true since the two tries have the same node\n structure. However, as far as Mapping interface is concerned, they\n use different keys, i.e. ```set(t0) != set(t1)``. Secondly:\n\n >>> t0 = StringTrie({'foo/bar.baz': 42}, separator='/')\n >>> t1 = StringTrie({'foo/bar.baz': 42}, separator='.')\n >>> t0 == t1\n True\n\n This used to be false since the two tries have different node\n structures (the first one splits key into ``('foo', 'bar.baz')``\n while the second into ``('foo/bar', 'baz')``). However, their keys\n are the same, i.e. ```set(t0) == set(t1)``. And lastly:\n\n >>> t0 = Trie({'foo': 42})\n >>> t1 = CharTrie({'foo': 42})\n >>> t0 == t1\n False\n\n This used to be true since the two tries have the same node\n structure. However, the two classes return key as different values.\n ``pygtrie.Trie`` returns keys as tuples while\n ``pygtrie.CharTrie`` returns them as strings.\n\n2.4.2: 2021/01/03\n\n- Remove use of \u2018super\u2019 in ``setup.py`` to fix compatibility with\n Python 2.7. This changes build code only; no changes to the library\n itself.\n\n2.4.1: 2020/11/20\n\n- Remove dependency on ``packaging`` module from ``setup.py`` to fix\n installation on systems without that package. This changes build\n code only; no changes to the library itself. [Thanks to Eric\n McLachlan for reporting]\n\n2.4.0: 2020/11/19 [pulled back from PyPi]\n\n- Change ``children`` argument of the ``node_factory`` passed to\n ``pygtrie.Trie.traverse`` from a generator to an iterator with\n a custom bool conversion. This allows checking whether node has\n children without having to iterate over them (``bool(children)``)\n\n To test whether this feature is available, one can check whether\n `Trie.traverse.uses_bool_convertible_children` property is true,\n e.g.: ``getattr(pygtrie.Trie.traverse,\n 'uses_bool_convertible_children', False)``.\n\n [Thanks to Pallab Pain for suggesting the feature]\n\n2.3.3: 2020/04/04\n\n- Fix to \u2018``AttributeError``: ``_NoChildren`` object has no\n attribute ``sorted_items``\u2019 failure when iterating over a trie with\n sorting enabled. [Thanks to Pallab Pain for reporting]\n\n- Add ``value`` property setter to step objects returned by\n ``pygtrie.Trie.walk_towards`` et al. This deprecates the\n ``set`` method.\n\n- The module now exports `pygtrie.__version__` making it possible to\n determine version of the library at run-time.\n\n2.3.2: 2019/07/18\n\n- Trivial metadata fix\n\n2.3.1: 2019/07/18 [pulled back from PyPi]\n\n- Fix to ``pygtrie.PrefixSet`` initialisation incorrectly storing\n elements even if their prefixes are also added to the set.\n\n For example, ``PrefixSet(('foo', 'foobar'))`` incorrectly resulted\n in a two-element set even though the interface dictates that only\n ``foo`` is kept (recall that if ``foo`` is member of the set,\n ``foobar`` is as well). [Thanks to Tal Maimon for reporting]\n\n- Fix to ``pygtrie.Trie.copy`` method not preserving\n enable-sorting flag and, in case of ``pygtrie.StringTrie``,\n ``separator`` property.\n\n- Add support for the ``copy`` module so ``copy.copy`` can now be\n used with trie objects.\n\n- Leafs and nodes with just one child use more memory-optimised\n representation which reduces overall memory usage of a trie\n structure.\n\n- Minor performance improvement for adding new elements to\n a ``pygtrie.PrefixSet``.\n\n- Improvements to string representation of objects which now includes\n type and, for ``pygtrie.StringTrie`` object, value of separator\n property.\n\n2.3: 2018/08/10\n\n- New ``pygtrie.Trie.walk_towards`` method allows walking a path\n towards a node with given key accessing each step of the path.\n Compared to `pygtrie.Trie.walk_prefixes` method, steps for nodes\n without assigned values are returned.\n\n- Fix to ``pygtrie.PrefixSet.copy`` not preserving type of backing\n trie.\n\n- ``pygtrie.StringTrie`` now checks and explicitly rejects empty\n separators. Previously empty separator would be accepted but lead\n to confusing errors later on. [Thanks to Waren Long]\n\n- Various documentation improvements, Python 2/3 compatibility and\n test coverage (python-coverage reports 100%).",
"bugtrack_url": null,
"license": "Apache-2.0",
"summary": "A pure Python trie data structure implementation.",
"version": "2.5.0",
"split_keywords": [
"trie",
"prefix tree",
"data structure"
],
"urls": [
{
"comment_text": "",
"digests": {
"md5": "603dea6eaf252d45b4b9fbe7fd2a15f7",
"sha256": "8795cda8105493d5ae159a5bef313ff13156c5d4d72feddefacaad59f8c8ce16"
},
"downloads": -1,
"filename": "pygtrie-2.5.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "603dea6eaf252d45b4b9fbe7fd2a15f7",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 25099,
"upload_time": "2022-09-23T20:30:05",
"upload_time_iso_8601": "2022-09-23T20:30:05.120188Z",
"url": "https://files.pythonhosted.org/packages/ec/cd/bd196b2cf014afb1009de8b0f05ecd54011d881944e62763f3c1b1e8ef37/pygtrie-2.5.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "4cd66ab6cf0f625cd0fb367712a0cccf",
"sha256": "203514ad826eb403dab1d2e2ddd034e0d1534bbe4dbe0213bb0593f66beba4e2"
},
"downloads": -1,
"filename": "pygtrie-2.5.0.tar.gz",
"has_sig": false,
"md5_digest": "4cd66ab6cf0f625cd0fb367712a0cccf",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 39266,
"upload_time": "2022-07-16T14:29:47",
"upload_time_iso_8601": "2022-07-16T14:29:47.459173Z",
"url": "https://files.pythonhosted.org/packages/b9/13/55deec25bf09383216fa7f1dfcdbfca40a04aa00b6d15a5cbf25af8fce5f/pygtrie-2.5.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2022-07-16 14:29:47",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "mina86",
"github_project": "pygtrie",
"travis_ci": true,
"coveralls": true,
"github_actions": false,
"lcname": "pygtrie"
}
JSON
