Red/black trees in C++ for Python
Project description
============
pyredblack
============
.. image:: https://travis-ci.org/wroberts/pyredblack.svg?branch=master
:target: https://travis-ci.org/wroberts/pyredblack
Copyright (c) 2015 Will Roberts <wildwilhelm@gmail.com>
Licensed under the MIT License (see ``LICENSE.rst`` for details).
Cython interface to red-black trees implemented in C++.
`Red-black trees`_ are a kind of `self-balancing binary tree`_. They
maintain their entries in sorted order and have O(log n) for
insertion, lookup, and deletion. You can read more about red-black
trees `here
<http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx>`_
and see animations of insertion, lookup, and deletion `here
<https://www.cs.usfca.edu/~galles/visualization/RedBlack.html>`_.
.. _`Red-black trees`: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
.. _`self-balancing binary tree`: http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
This package provides dictionary and set objects based on
red-black-trees; these can be used as drop-in replacements for the
built-in ``dict`` and ``set`` types, except that they maintain their
contents in sorted order.
Dictionary (``rbdict``)::
>>> import pyredblack
>>> d = pyredblack.rbdict(Germany = 'Berlin',
Hungary = 'Budapest',
Ireland = 'Dublin',
Portugal = 'Lisbon',
Cyprus = 'Nicosia',
Greenland = 'Nuuk',
Iceland = 'Reykjavik',
Macedonia = 'Skopje',
Bulgaria = 'Sofia',
Sweden = 'Stockholm')
>>> len(d)
10
>>> d['Ireland']
'Dublin'
>>> d.keys()
['Bulgaria', 'Cyprus', 'Germany', 'Greenland', 'Hungary',
'Iceland', 'Ireland', 'Macedonia', 'Portugal', 'Sweden']
>>> d.values()
['Sofia', 'Nicosia', 'Berlin', 'Nuuk', 'Budapest',
'Reykjavik', 'Dublin', 'Skopje', 'Lisbon', 'Stockholm']
>>> d.popitem()
('Bulgaria', 'Sofia')
>>> d.popitem()
('Cyprus', 'Nicosia')
>>> d.popitem()
('Germany', 'Berlin')
Set (``rbset``)::
>>> fruit = pyredblack.rbset(['apple', 'orange', 'apple', 'pear',
'orange', 'banana'])
>>> 'orange' in fruit
True
>>> 'crabgrass' in fruit
False
>>> a = pyredblack.rbset('abracadabra')
>>> b = pyredblack.rbset('alacazam')
>>> list(a)
['a', 'b', 'c', 'd', 'r']
>>> list(a - b)
['b', 'd', 'r']
>>> list(a | b)
['a', 'b', 'c', 'd', 'l', 'm', 'r', 'z']
>>> list(a & b)
['a', 'c']
>>> list(a ^ b)
['b', 'd', 'l', 'm', 'r', 'z']
>>> a.pop()
'a'
>>> a.pop()
'b'
>>> a.pop()
'c'
Requirements
------------
- Python 2.7, Python 3.2+
- Cython (and a C++ compiler)
Todo
----
- implement slicing on dictionaries
pyredblack
============
.. image:: https://travis-ci.org/wroberts/pyredblack.svg?branch=master
:target: https://travis-ci.org/wroberts/pyredblack
Copyright (c) 2015 Will Roberts <wildwilhelm@gmail.com>
Licensed under the MIT License (see ``LICENSE.rst`` for details).
Cython interface to red-black trees implemented in C++.
`Red-black trees`_ are a kind of `self-balancing binary tree`_. They
maintain their entries in sorted order and have O(log n) for
insertion, lookup, and deletion. You can read more about red-black
trees `here
<http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx>`_
and see animations of insertion, lookup, and deletion `here
<https://www.cs.usfca.edu/~galles/visualization/RedBlack.html>`_.
.. _`Red-black trees`: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
.. _`self-balancing binary tree`: http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
This package provides dictionary and set objects based on
red-black-trees; these can be used as drop-in replacements for the
built-in ``dict`` and ``set`` types, except that they maintain their
contents in sorted order.
Dictionary (``rbdict``)::
>>> import pyredblack
>>> d = pyredblack.rbdict(Germany = 'Berlin',
Hungary = 'Budapest',
Ireland = 'Dublin',
Portugal = 'Lisbon',
Cyprus = 'Nicosia',
Greenland = 'Nuuk',
Iceland = 'Reykjavik',
Macedonia = 'Skopje',
Bulgaria = 'Sofia',
Sweden = 'Stockholm')
>>> len(d)
10
>>> d['Ireland']
'Dublin'
>>> d.keys()
['Bulgaria', 'Cyprus', 'Germany', 'Greenland', 'Hungary',
'Iceland', 'Ireland', 'Macedonia', 'Portugal', 'Sweden']
>>> d.values()
['Sofia', 'Nicosia', 'Berlin', 'Nuuk', 'Budapest',
'Reykjavik', 'Dublin', 'Skopje', 'Lisbon', 'Stockholm']
>>> d.popitem()
('Bulgaria', 'Sofia')
>>> d.popitem()
('Cyprus', 'Nicosia')
>>> d.popitem()
('Germany', 'Berlin')
Set (``rbset``)::
>>> fruit = pyredblack.rbset(['apple', 'orange', 'apple', 'pear',
'orange', 'banana'])
>>> 'orange' in fruit
True
>>> 'crabgrass' in fruit
False
>>> a = pyredblack.rbset('abracadabra')
>>> b = pyredblack.rbset('alacazam')
>>> list(a)
['a', 'b', 'c', 'd', 'r']
>>> list(a - b)
['b', 'd', 'r']
>>> list(a | b)
['a', 'b', 'c', 'd', 'l', 'm', 'r', 'z']
>>> list(a & b)
['a', 'c']
>>> list(a ^ b)
['b', 'd', 'l', 'm', 'r', 'z']
>>> a.pop()
'a'
>>> a.pop()
'b'
>>> a.pop()
'c'
Requirements
------------
- Python 2.7, Python 3.2+
- Cython (and a C++ compiler)
Todo
----
- implement slicing on dictionaries
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
pyredblack-0.1.0.tar.gz
(79.7 kB
view hashes)
Built Distributions
Close
Hashes for pyredblack-0.1.0-cp34-cp34m-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2041e4656fa9386a21da82394be573f9ca80a51d4be86537e84b2268fe0a34d7 |
|
MD5 | e6da824ee2d6ee89311a45a718396716 |
|
BLAKE2b-256 | a0b4f58c2006c06aba1a6cc65d9cc9e54c4d5641b5b06d332f5134b872105c0c |
Close
Hashes for pyredblack-0.1.0-cp27-none-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 05050bd1ade7e8c89cac8ca3e488b3373a90662c7d43c503ae89cced6098eb41 |
|
MD5 | 61fd40707d2ef98d6e998323b2e1141a |
|
BLAKE2b-256 | f165ee3b47f9ffb5e5e1e8deeee23b5669349ee97f6bc5e59614332cb6dccb60 |