Created
October 9, 2014 18:57
-
-
Save timeartist/288d916d5d26cef4569c to your computer and use it in GitHub Desktop.
Pythonic Linked List
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Tree(object): | |
def __init__(self, root=None): | |
self.root = root | |
@classmethod | |
def from_string(cls, tree_string): | |
raise NotImplementedError | |
def __contains__(self, item): | |
if isinstance(item, Node): | |
return self._node_exists(item) | |
elif isinstance(item, Tree): | |
##This either will get really messy or work perfectly | |
return self._node_exists(item.root) | |
else: | |
return self.lookup(item) | |
def _node_exists(self, item): | |
if self.root == item: | |
return True | |
elif item.value <= self.root.value and self.root.left is not None: | |
return Tree(self.root.left)._node_exists(item) | |
elif item.value > self.root.value and self.root.right is not None: | |
return Tree(self.root.right)._node_exists(item) | |
else: | |
return False | |
def lookup(self, item): | |
raise NotImplementedError | |
def insert(self, value): | |
if self.root is None: | |
print 'Root is None - Creating Root' | |
self.root = Node(value) | |
elif value <= self.root.value and self.root.left is None: | |
print 'Left Node Acquired' | |
self.root.left = Node(value) | |
elif value <= self.root.value: | |
print 'Going to the Left Node' | |
Tree(self.root.left).insert(value) | |
elif self.root.right is None: | |
print 'Right Node Acquired' | |
self.root.right = Node(value) | |
else: | |
print 'Going to the Right Node' | |
Tree(self.root.right).insert(value) | |
class Node(object): | |
def __init__(self, value, left=None, right=None): | |
assert isinstance(left, Node) or left is None | |
assert isinstance(right, Node) or right is None | |
self.value = value | |
self.left = left | |
self.right = right | |
def __eq__(self, other): | |
if other: | |
return all((self.value == other.value, | |
self.left == other.left, | |
self.right == other.right)) | |
else: | |
return False | |
if __name__ == '__main__': | |
n1 = Node(1, None, None) | |
n2 = Node(2, n1, None) | |
n3 = Node(2, n1, None) | |
#import pdb | |
#pdb.set_trace() | |
print n2 == n3 | |
print n2 == n1 | |
tree = Tree() | |
tree.insert(5) | |
tree.insert(7) | |
tree.insert(3) | |
tree.insert(27) | |
tree.insert(5) | |
t2 = Tree() | |
t2.insert(7) | |
t2.insert(27) | |
t2.insert(5) | |
import pdb; pdb.set_trace() | |
print t2 in tree | |
n4 = Node(27) | |
n5 = Node(5) | |
n6 = Node(7, n5, n4) | |
print n6 in t2 | |
print n6 in tree | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I would break this code apart onto 3 files :)