getbuddy.py

class Node(object):
	def __init__(self, parent, depth, nodeID):
		super(Node, self).__init__()
		self.parent = parent
		self.depth = depth
		self.nodeID = nodeID
		self.left = None
		self.right = None
		self.used = False

class Buddy(object):
	def __init__(self):
		super(Buddy, self).__init__()
		self.id = 1
		self.root = Node(None, 1, self.id)
		self.id += 1

	def postOrder(self, root, req):
		if root == None:
			return None
		if root.depth > req:
			return None
		
		leftCandidate = self.postOrder(root.left, req)
		if leftCandidate != None:
			return leftCandidate
		rightCandidate = self.postOrder(root.right, req)
		if rightCandidate != None:
			return rightCandidate

		print root.nodeID

		if root.used == False:
			return root
		return None

	def get(self, req):
		print "Requesting a free node of depth %d" % req
		root = self.postOrder(self.root, req)
		if root == None:
			print "Error, could not found any free node"
			return None
		print "Found free node %d with depth %d" % (root.nodeID, root.depth)

		d = root.depth
		while d < req:
			d += 1
			root.used = True			
			root.left = Node(root, d, self.id)
			print "Added node %d at depth %d as the left node of %d" % (self.id, d, root.nodeID)
			self.id += 1
			root.right = Node(root, d, self.id)
			print "Added node %d at depth %d as the right node of %d" % (self.id, d, root.nodeID)
			self.id += 1
			root = root.left

		root.used = True
		print "Request met, found node %d with depth %d" % (root.nodeID, root.depth)
		return root

	def free(self, root):
		if root.left != None or root.right != None:
			print "Error, cannot free a non-leaf node"
			return
		root.used = False
		print "Node %d freed" % root.nodeID
		while root.parent != None:
			if (root.parent.left == root and root.parent.right.used == False) \
				or (root.parent.right == root and root.parent.left.used == False):
				print "Node %d freed" % root.parent.nodeID
				root.parent.used = False
				root.parent.left = None
				root.parent.right = None
				root = root.parent
			else:
				break
		return

def main():
	buddy = Buddy()
	n1 = buddy.get(3) # 4
	n2 = buddy.get(2) # 3
	n3 = buddy.get(3) # 5
	n4 = buddy.get(1)
	buddy.free(n1)
	buddy.free(n2)
	buddy.free(n3)
	buddy.free(n2)


if __name__ == '__main__':
	main()