classification
Title: Adding redblack tree to collections module
Type: enhancement Stage: test needed
Components: Extension Modules Versions: Python 3.1, Python 2.7
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: georg.brandl, hyeshik.chang, loewis, rhettinger, stutzbach
Priority: normal Keywords: patch

Created on 2005-10-12 11:58 by hyeshik.chang, last changed 2009-04-05 13:52 by georg.brandl. This issue is now closed.

Files
File name Uploaded Description Edit
collections-rbtree-r5.diff.txt hyeshik.chang, 2006-04-24 13:40 rev.5
Messages (8)
msg48858 - (view) Author: Hyeshik Chang (hyeshik.chang) * (Python committer) Date: 2005-10-12 11:58
This patch drafts a new type "rbtree" implementing
Redblack Tree for collections module. It's just a
preliminary material for the future discussion and
includes a least working code.

Usage:

[basic list-like tree operations]

>>> from collections import rbtree
>>> r = rbtree()
>>> map(r.insert, [9, 3, 4, 100, 'dalki', 'subak', -51])
[None, None, None, None, None, None, None]
>>> r.values()
[-51, 3, 4, 9, 100, 'dalki', 'subak']
>>> r.remove(100)
>>> r.values()
[-51, 3, 4, 9, 'dalki', 'subak']
>>> r.insert('snisni')
>>> r.values()
[-51, 3, 4, 9, 'dalki', 'snisni', 'subak']
>>> 9 in r
True
>>> 8 in r
False

[labeled nodes operations]

>>> r = rbtree()
>>> r['dalki'] = 5; r['subak'] = 1; r['spam'] = 7
>>> r.values()
[1, 5, 7]
>>> r.keys()
['subak', 'dalki', 'spam']
>>> r['egg'] = 1
>>> r.items()
[('egg', 1), ('dalki', 5), ('spam', 7)]
>>> del r['spam']
>>> r.items()
[('egg', 1), ('dalki', 5)]

[mixed altogether]

>>> r.insert(7)
>>> r.insert(0)
>>> r.items()
[(None, 0), ('egg', 1), ('dalki', 5), (None, 7)]
>>> r['dalki'] = 7
>>> r.items()
[(None, 0), ('egg', 1), ('dalki', 7)]

[heapq-like stuff]

>>> r = rbtree()
>>> map(r.insert, range(20))
[None, None, None, None, None, None, None, None, None,
None, None, None, None, None, None, None, None, None,
None, None]
>>> r.nfirst(3)
[0, 1, 2]
>>> r.nfirst(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> r.nlast(5)
[19, 18, 17, 16, 15]
>>> r.popleft(5)
[0, 1, 2, 3, 4]
>>> r.values()
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> r.popright(15)
[19, 18, 17, 16]
>>> r.values()
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> r['ham'] = 14
>>> r.poprightitems(14, True)
[(None, 15), ('ham', 14)]

[cmp, key and reverse are also supported]

>>> r = rbtree(key=lambda x: x%10)
>>> map(r.insert, range(30))
[None, None, None, None, None, None, None, None, None,
None, None, None, None, None, None, None, None, None,
None, None, None, None, None, None, None, None, None,
None, None, None]
>>> r.values()
[20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
>>> r['yay'] = 78
>>> r.values()
[20, 21, 22, 23, 24, 25, 26, 27, 78, 29]
>>> r.items()
[(None, 20), (None, 21), (None, 22), (None, 23), (None,
24), (None, 25), (None, 26), (None, 27), ('yay', 78),
(None, 29)]
>>> r.clear()
>>> r.values()
[]
>>> r = rbtree(reverse=True)
>>> map(r.insert, range(10))
[None, None, None, None, None, None, None, None, None,
None]
>>> r.values()
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
msg48859 - (view) Author: Hyeshik Chang (hyeshik.chang) * (Python committer) Date: 2005-10-14 15:55
Logged In: YES 
user_id=55188

Added a unittest and fixed a bug on initcollection() calling
PyType_Ready(&rbtree_type).
msg48860 - (view) Author: Hyeshik Chang (hyeshik.chang) * (Python committer) Date: 2005-10-16 07:42
Logged In: YES 
user_id=55188

Added iterator and reverse iterator implementations and
__copy__ method.
msg48861 - (view) Author: Hyeshik Chang (hyeshik.chang) * (Python committer) Date: 2006-03-19 03:08
Logged In: YES 
user_id=55188

Updated the patch for the current svn.
msg48862 - (view) Author: Martin v. Löwis (loewis) * (Python committer) Date: 2006-04-25 06:21
Logged In: YES 
user_id=21627

This implementation gives me many questions:
- what is the rationale for keeping a separate keys
dictionary? If applications wanted that, couldn't they
maintain a key dictionary themselves? It just seems strange
to rely on hashing inside a rbtree implementation.
- Currently, you need two RichCompare invocations for
insertion/contains. Couldn't that be reduced to just one
comparison if __cmp__ is used?
- for key functions, wouldn't it usually be better to cache
the key?
- shouldn't tp_clear also be implemented?
- this entire code needs many more comments. For example,
why does the forward iterator first follow the right-most
links? I would have expected that it needs to start with the
leftmost node first (and somehow, it does - but why?)
msg83895 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-03-21 00:14
I'm curious what the use case is for this.  It is not the purpose of the
collections module to implement all possible storage techniques
(b-trees, pairing heaps and whatnot).  What problem is being solved?

AFAICT, this offers a ordered dictionary style API without the
restriction of hashability, instead using the typically much more
expensive compare operation.  Also, the big-oh times degrade from O(1)
so that now we have O(log n) searches, insertions, and deletions.
msg84638 - (view) Author: Daniel Stutzbach (stutzbach) (Python committer) Date: 2009-03-30 20:25
I agree with Raymond.

In general, the collections module should define containers that are
named after their function rather than their implementation.  That way
the implementation can be changed at a later date (or in other Python
implementations) without causing confusion, and it makes it more obvious
what use-case the new collection is solving.  That's my opinion, anyway.

As much as I'd love to see more container types in the collections
module (my kingdom for a heap with .decrease_key()!), I don't see what
use-case this implementation of red-black trees fills.
msg85496 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2009-04-05 13:52
Let's reject it then.
History
Date User Action Args
2009-04-05 13:52:25georg.brandlsetstatus: open -> closed

nosy: + georg.brandl
messages: + msg85496

resolution: rejected
2009-03-30 20:25:14stutzbachsetnosy: + stutzbach
messages: + msg84638
2009-03-21 00:14:33rhettingersetnosy: + rhettinger
messages: + msg83895
2009-03-20 23:00:03ajaksu2setstage: test needed
type: enhancement
versions: + Python 3.1, Python 2.7, - Python 2.5
2005-10-12 11:58:27hyeshik.changcreate