Skip to main content

Skip list based sorted collections

Project description

Build status

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-hypernode.com/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
>>> things
SkipListDict({'a': 'A', 'b': 'B', 'g': 2, 'x': 1}, capacity=16)

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

SkipListSet

SkipListSet is set implementation using skip list. It’s permanently sorted by key.

  • Iterating the container is O(n)

  • Adding, removing and checking if a key exist in the containe is O(log n) on average, O(n) in worst case (degenerated skip list)

>>> from skiplistcollections import SkipListSet
>>> things = SkipListSet(capacity=16)
>>> len(things)
0
>>> things.add(3)
>>> len(things)
1
>>> things.add(1)
>>> things.add(4)
>>> things
SkipListSet((1, 3, 4), capacity=16)
>>> tuple(things)
(1, 3, 4)
>>> things.remove(2)
Traceback (most recent call last):
KeyError: 2

Changes

0.0.6

  • Fixed bug with SkipListDict yielding too many items if start_key was not found (GitHub issue #1)

0.0.5

  • Fixed SkipListDict repr

  • Created SkipListSet

0.0.4

  • Included start_key and reverse values in views reprs

  • Improved README

0.0.3

  • items(), values(), keys() return views now

0.0.2

  • Improved README

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

skiplistcollections-0.0.6.tar.gz (4.8 kB view details)

Uploaded Source

Built Distribution

skiplistcollections-0.0.6-py2.py3-none-any.whl (6.9 kB view details)

Uploaded Python 2 Python 3

File details

Details for the file skiplistcollections-0.0.6.tar.gz.

File metadata

File hashes

Hashes for skiplistcollections-0.0.6.tar.gz
Algorithm Hash digest
SHA256 f7099783b6b521369f44fe6a5320bb951fd567bed61bf914c7f09de61b446387
MD5 0f0909016e62264860a88cce892c6dbd
BLAKE2b-256 c95095269ccd2fef8580aa96f32e0a9af558361b1259535ab1c926686ef36d7c

See more details on using hashes here.

File details

Details for the file skiplistcollections-0.0.6-py2.py3-none-any.whl.

File metadata

File hashes

Hashes for skiplistcollections-0.0.6-py2.py3-none-any.whl
Algorithm Hash digest
SHA256 e4fc2077d2e9fede118efbb27a2a0bd23b789f998b5c62577879793c532594e2
MD5 0e4aa4977d9782decfe6cb801cbfbebc
BLAKE2b-256 0649e701126c3af55599d65fd04053676957398a9249d054c9c009cca3eda267

See more details on using hashes here.

Supported by

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