Skip list based sorted collections (currently only SkipListDict)
Project description
skiplistcollections is a Python module containing skip list based sorted collections. skiplistcollections is written in Python and works with:
CPython 2.6+, 3.2+
PyPy 1.9+
Project page on GitHub: https://github.com/jstasiak/skiplistcollections
Project page on PyPI: https://pypi.python.org/pypi/skiplistcollections
SkipListDict
SkipListDict is container providing dict-like interface and implemented using skip list. It’s permanently sorted by key.
Iterating the container (starting with any key, supports reverse ordering) is O(n)
Getting, setting and deleting arbitrary key is O(log n) on average, O(n) in worst case (degenerated skip list)
See http://pythonsweetness.tumblr.com/post/45227295342/fast-pypy-compatible-ordered-map-in-89-lines-of-python for details.
>>> from skiplistcollections import SkipListDict
>>> things = SkipListDict(capacity=16)
>>> len(things)
0
>>> things['x'] = 1
>>> things.setdefault('x', 'DEFAULT')
1
>>> 'x' in things
True
>>> len(things)
1
>>> things['g'] = 2
>>> things['z'] = 3
>>> tuple(things.keys())
('g', 'x', 'z')
>>> tuple(things.values())
(2, 1, 3)
>>> tuple(things.items())
(('g', 2), ('x', 1), ('z', 3))
>>> tuple(things.items(start_key='x'))
(('x', 1), ('z', 3))
>>> tuple(things.items(start_key='x', reverse=True))
(('x', 1), ('g', 2))
>>> del things['z']
>>> things.update({'a': 'A', 'b': 'B'})
>>> len(things)
4
As you can see, SkipListDict follows Python dict interface quite closely. In fact it inherits MutableMapping Abstract Base Class.
There are differences of course:
You need to set the maximum dict size when you create it
Initializing using another mapping is not supported yet
You can’t use None as a key
items, keys, and values are views and accept start_key and reverse parameters
Copyright
Original version - Copyright (C) 2013 David Wilson
Copyright (C) 2013 Jakub Stasiak
This source code is licensed under MIT license, see LICENSE file for details.
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
Built Distribution
Hashes for skiplistcollections-0.0.4.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | 40531a27e9bdd035f85532d80eea4c5775f97ef53f9b3645c4d473c2f14e55f4 |
|
MD5 | a5c453fe064a7d375e9d3860708d8d54 |
|
BLAKE2b-256 | 269ed34506789c76fef7adc283990912fe5d32dada2226c2c15de934a651ac7e |
Hashes for skiplistcollections-0.0.4-py27-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 604f4ae6ab5a3c0716ea0dcf178f8a9ed8ceb60e4c0d46f9e9dce24944ece9c6 |
|
MD5 | 9c29e3feebb20c61ba30a86265daf6aa |
|
BLAKE2b-256 | 50824bf2b0d4d749bf2c98742adc9d7f920033dcce35c3d309c768b872ca84c2 |