Metadata-Version: 2.1
Name: pygtrie
Version: 2.2
Summary: Trie data structure implementation.
Home-page: https://github.com/google/pygtrie
Download-URL: https://github.com/google/pygtrie/tarball/v2.2
Author: Michal Nazarewicz
Author-email: mina86@mina86.com
License: Apache-2.0
Keywords: trie,prefix tree,data structure
Platform: Platform Independent
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: Apache Software License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python
Classifier: Programming Language :: Python :: 2
Classifier: Programming Language :: Python :: 2.6
Classifier: Programming Language :: Python :: 2.7
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Software Development :: Libraries :: Python Modules
License-File: LICENSE

pygtrie
=======

.. image:: https://readthedocs.org/projects/pygtrie/badge/?version=latest
   :target: http://pygtrie.readthedocs.io/en/latest/
   :alt: Documentation Status (latest)

.. image:: https://readthedocs.org/projects/pygtrie/badge/?version=stable
   :target: http://pygtrie.readthedocs.io/en/stable/
   :alt: Documentation Status (stable)

pygtrie is a Python library implementing a trie data structure.

`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, run::

    pip install pygtrie

Or download the sources and save ``pygtrie.py`` file with your
project.

Upgrading from 0.9.x
--------------------

The 1.0 release introduced backwards incompatibility in naming.  The
module has been renamed from ``trie`` to ``pygtrie``.  Fortunately,
updating scripts using pygtrie should boil down to replacing::

    from pytrie import trie

with::

    import pygtrie as trie

Version History
---------------

2.2: 2017/06/03

- Fixes to setup.py breaking on Windows which prevents installation
  among other things.

2.1: 2017/03/23

- The library is now Python 3 compatible.

- Value returend by ``shortest_prefix`` and ``longest_prefix`` evaluates
  to false if no prefix was found.  This is in addition to it being
  a pair of Nones of course.

2.0: 2016/07/06

- Sorting of child nodes is disabled by default for better performance.
  ``enable_sorting`` method can be used to bring back old behaviour.

- Tries of arbitrary depth can be pickled without reaching Python’s
  recursion limits.  (N.B. The pickle format is incompatible with one
  from 1.2 release).  ``_Node``’s ``__getstate__`` and ``__setstate__``
  method can be used to implement other serialisation methods such as
  JSON.

1.2: 2016/06/21  [pulled back from PyPi]

- Tries can now be pickled.

- Iterating no longer uses recursion so tries of arbitrary depth can be
  iterated over.  The ``traverse`` method, however, still uses recursion
  thus cannot be used on big structures.

1.1: 2016/01/18

- Fixed PyPi installation issues; all should work now.

1.0: 2015/12/16

- The module has been renamed from ``trie`` to ``pygtrie``.  This
  could break current users but see documentation for how to quickly
  upgrade your scripts.

- Added ``traverse`` method which goes through the nodes of the trie
  preserving structure of the tree.  This is a depth-first traversal
  which can be used to search for elements or translate a trie into
  a different tree structure.

- Minor documentation fixes.

0.9.3: 2015/05/28

- Minor documentation fixes.

0.9.2: 2015/05/28

- Added Sphinx configuration and updated docstrings to work better
  with Sphinx.

0.9.1: 2014/02/03

- New name.

0.9: 2014/02/03

- Initial release.
