question of style

[Paul Rubin]

Simon Forman <sajmikins at gmail.com> writes:
> > Yes, but the concept of null pointers is considered kludgy these days.
> Seriously? "kludgy"?  (I really AM getting old.)

  http://math.andrej.com/2009/04/11/on-programming-language-design/

discusses the issue (scroll down to "Undefined values" section).

> Well I wouldn't know, I've been fortunate enough to program mostly in
> python for over half a decade now and None and 0 are as close as I've
> gotten to NULL in a long time.

Right, and how many times have you had to debug

   AttributeError: 'NoneType' object has no attribute 'foo'

or the equivalent null pointer exceptions in Java, C, or whatever?
They are very common.  And the basic idea is that if you avoid using
null pointers in the first place, you'll get fewer accidental null
pointer exceptions.

> That sounds very interesting, but I'm only writing a BTree to then use
> it to play with "persistent data structures" 

But you have implemented a mutable tree.  If you want to write a
persistent one, then write a persistent one!  You also use a wishful
heuristic in the hope of keeping the tree balanced--if you want a
balanced tree, why not use one that's guaranteed to stay in balance?
AVL trees are pretty easy to implement; maybe you could try writing a
persistent one:

  http://en.wikipedia.org/wiki/AVL_tree

> In this particular case it's somewhat more elegant (IMO) to check "is
> None".

Well, I can't understand why that might be, but it's surely
subjective, so ok.

> > I'm sorry but I find that class rather ugly.  The code would be a lot
> > smaller and have fewer corner cases with a different data representation.
> 
> Um, thanks?  Seriously though, care to put your money where your mouth
> is? I'd be interested to see a BTree implemented as you indicated above.

Er, I'm not trying to argue with you.  You asked for people's advice
and impressions, so I gave you some.  I don't feel like rewriting that
whole class, but I'll do a method or two, using [] to represent an
empty node.  (Hmm, actually changing the empty node representation did
less to shorten the code than just getting rid of a bunch of
duplication.  Really, I'd tend to look for a slightly different tree
structure which tried to avoid these issues).

Untested:

class BinaryTree:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.higher = self.lower = []

    def get(self, key):
        if key == self.key:
            return self.value
        branch = self.lower if key < self.key else self.higher
        return branch.get(key) if branch else []

    def insert(self, key, value):
        def xinsert(xtree):  # xtree is either a tree or []
           if not xtree: xtree = BinaryTree(key, value)
           else: xtree.insert(key, value)
           return xtree

        if key == self.key:
            self.value = value
        elif key < self.key:
            self.lower = xinsert(self.lower)
        else:
            self.higher = xinsert(self.higher)

and so forth.