Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Simple example of ranged binary tree in Python, able to perform slice retrieval
# coding: utf-8
class EmptyClass(object):
def __repr__(self):
return ""
Empty = EmptyClass()
class Node(object):
def __init__(self, value, key=None):
self.left = Empty
self.right = Empty
self.value = value
if key is None:
self.key = lambda x:x
else:
self.key = key
def insert(self, new_value):
if self.key(new_value) < self.key(self.value):
self._inner_insert(new_value, self.left, "left")
else:
self._inner_insert(new_value, self.right, "right")
def _inner_insert(self, new_value, branch_value, branch_name):
if branch_value is Empty:
setattr(self, branch_name, new_value)
elif isinstance(branch_value, Node):
branch_value.insert(new_value)
else:
new_branch = Node(branch_value, self.key)
new_branch.insert(new_value)
setattr(self, branch_name, new_branch)
def __lshift__(self, value):
self.insert(value)
def __repr__(self):
return " ".join((repr(self.left), repr(self.value), repr(self.right)))
def __getitem__(self, value):
if isinstance(value, slice):
return self._getslice(value)
return self._getitem_and_next(value)[0]
def _getitem_and_next(self, value):
keyed = self.key(value)
if keyed == self.key(self.value):
return value, self.closer_right()
if keyed < self.key(self.value):
if isinstance(self.left, Node):
if keyed > self.left.key(self.left.value):
return self.value, self.closer_right()
result = self.left._getitem_and_next(value)
if result[1] is Empty:
return result[0], self.value
return result
if self.left is Empty:
return self.value, self.closer_right()
if keyed <= self.key(self.left):
return self.left, self.value
return self.value, self.closer_right()
else:
if isinstance(self.right, Node):
return self.right._getitem_and_next(value)
if self.right is Empty:
raise ValueError("No value less or equal %s" % value)
return self.right
def closer_right(self):
if isinstance(self.right, Node):
return self.right.leftmost()
return self.right
def leftmost(self):
if isinstance(self.left, Node):
return self.left.leftmost()
if self.left is Empty:
return self.value
return self.left
def _getslice(self, value):
return list(self.iterslice(value.start, value.stop))
def iterslice(self, start, stop):
result, next_ = self._getitem_and_next(start)
keyed_stop = self.key(stop)
while result is not Empty and self.key(result) < keyed_stop:
yield result
result, next_ = self._getitem_and_next(next_)
raise StopIteration
@jsbueno

This comment has been minimized.

Copy link
Owner Author

@jsbueno jsbueno commented Jan 8, 2015

>>> b  = simpletree.Node("fnord")
>>> b << "dalmata"; b << "castelo"; b << "elefante"; b << "amarelo"; b << "pizza"; b << "gelo"; b<<"zebra"
>>> b
'amarelo' 'castelo'  'dalmata' 'elefante' 'fnord' 'gelo' 'pizza' 'zebra'
>>> b["a"]
'amarelo'
>>> b["a":"g"]
['amarelo', 'castelo', 'dalmata', 'fnord']
@jsbueno

This comment has been minimized.

Copy link
Owner Author

@jsbueno jsbueno commented Jan 9, 2015

This version is really b0rk for some cases - I fixed it, but added more features and it is no longer that "simple" for a gist. Write me if you need the better version. Although this i s not a complete binary-tree project: there is no node removal or any kind of tree balancing.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment