class kdtree:
	def __init__(self, dimension =2,index=0):
		self.dimension = dimension
		self.index = index
		self.split = None

	def addPoint(self,thePoint,theParent=None):
		"""Include another point in the kD-tree."""
		if self.split is None:
			#you are now a end
			self.split = thePoint
			print "at a edge %s. Node%s" % (self.split, self)
			self.parent=theParent
			self.left = kdtree(self.dimension, (self.index + 1) % self.dimension)
			self.right = kdtree(self.dimension, (self.index + 1) % self.dimension)
			print self.parent
			return self.parent
		elif self.split[self.index] < thePoint[self.index]:
			#go left
			print "%s, go left%s" % (self.split,"")
			self.left.addPoint(thePoint, self)
		else:
			#go right
			print "%s, go right%s" % (self.split,"")
			self.right.addPoint(thePoint, self)
		if self.split is None: print "test"	

if __name__ == "__main__":
        pointList=[(5,6), (9,7), (8,3), (7,4), (6,7), (10,6), (4,8), (3,1), (2,0), (1,9)]
	k = kdtree()
        for i in range(len(pointList)):
		thePoint=pointList[i]
		print k.addPoint(thePoint)