Red/black trees in C++ for Python
Project description
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 and see animations of insertion, lookup, and deletion.
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
Built Distributions
Hashes for pyredblack-0.1.1-cp35-cp35m-macosx_10_11_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d1935966d13b91c1fc9ebdb434bc2d4c66f6ac3b4e4d74d4eb80e20c7b17118a |
|
MD5 | 0e57ae90fa99a54eb0686acea9dfcc0e |
|
BLAKE2b-256 | 85ea4b43a2869cf41ed529e96e524828a26d13f1b85a11690e1c73c259779723 |
Hashes for pyredblack-0.1.1-cp34-cp34m-macosx_10_11_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8a4ff3b951b0872d01ce2d05943a60a311e063e38d81d0699a6475eadf2a316b |
|
MD5 | 3e8326054d2c85c2547d235a261cfb31 |
|
BLAKE2b-256 | d8c7e2ad5b3bd972455720b499fbea534e3fbb779d7ab9560801fda91cadbda0 |
Hashes for pyredblack-0.1.1-cp27-none-macosx_10_11_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 141040cbb8d06f0737b9fa9766064099688adb8e09bb7bb3fd8af2865eb2e613 |
|
MD5 | fabfe66b7ba44991788886157669ccf8 |
|
BLAKE2b-256 | 379481032a0f9efce24ab7c30a40255ce0fec055f22c454b640d7c60d469db1f |