← Back to branch summary

~ubuntu-branches/ubuntu/karmic/pypy/karmic

« back to all changes in this revision

Viewing changes to pypy/rlib/cslib/btree.py

  • Committer: Bazaar Package Importer
  • Author(s): Alexandre Fayolle
  • Date: 2007-04-13 09:33:09 UTC
  • Revision ID: james.westby@ubuntu.com-20070413093309-yoojh4jcoocu2krz
Tags: upstream-1.0.0
Import upstream version 1.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
pypy/rlib/cslib/btree.py
 
1
"""
 
2
A minimalist binary tree implementation
 
3
whose values are (descendants of) BTreeNodes.
 
4
This alleviates some typing difficulties when
 
5
using TimSort on lists of the form [(key, Thing), ...]
 
6
"""
 
7
 
 
8
class BTreeNode:
 
9
 
 
10
    def __init__(self, key):
 
11
        self.key = key
 
12
        self.left = None
 
13
        self.right = None
 
14
 
 
15
    def add(self, val):
 
16
        key = val.key
 
17
        assert isinstance(key, int)
 
18
        assert isinstance(val, BTreeNode)
 
19
        
 
20
        if key > self.key:
 
21
            if self.right:
 
22
                self.right.add(val)
 
23
            else:
 
24
                self.right = val
 
25
        else:
 
26
            if self.left:
 
27
                self.left.add(val)
 
28
            else:
 
29
                self.left = val
 
30
 
 
31
 
 
32
    def _values(self, dest):
 
33
        if self.left:
 
34
            self.left._values(dest)
 
35
        dest.append(self)
 
36
        if self.right:
 
37
            self.right._values(dest)
 
38
 
 
39
    def get_values(self):
 
40
        dest = []
 
41
        self._values( dest )
 
42
        return dest
 
43