Skip to main content
Join the official 2019 Python Developers SurveyStart the survey!

Red/black trees in C++ for Python

Project description

https://travis-ci.org/wroberts/pyredblack.svg?branch=master https://coveralls.io/repos/wroberts/pyredblack/badge.svg?branch=master Latest Version

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for pyredblack, version 0.1.1
Filename, size File type Python version Upload date Hashes
Filename, size pyredblack-0.1.1-cp27-none-macosx_10_11_x86_64.whl (84.0 kB) File type Wheel Python version cp27 Upload date Hashes View hashes
Filename, size pyredblack-0.1.1-cp34-cp34m-macosx_10_11_x86_64.whl (83.8 kB) File type Wheel Python version cp34 Upload date Hashes View hashes
Filename, size pyredblack-0.1.1-cp35-cp35m-macosx_10_11_x86_64.whl (83.6 kB) File type Wheel Python version cp35 Upload date Hashes View hashes
Filename, size pyredblack-0.1.1.tar.gz (88.7 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page