[Patches] [ python-Patches-1324770 ] Adding redblack tree to collections module

[SourceForge.net]

Patches item #1324770, was opened at 2005-10-12 20:58
Message generated for change (Tracker Item Submitted) made by Item Submitter
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1324770&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Modules
Group: Python 2.5
Status: Open
Resolution: None
Priority: 5
Submitted By: Hye-Shik Chang (perky)
Assigned to: Nobody/Anonymous (nobody)
Summary: Adding redblack tree to collections module

Initial Comment:
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]


----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1324770&group_id=5470