Simon Forman <sajmik...@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. -- http://mail.python.org/mailman/listinfo/python-list
