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

	def addPoint(self,thePoint,theParent=None):
		"""Include another point in the kD-tree."""
		if self.split is None:
			self.parent = theParent
			self.split = thePoint
			self.left = kdtree(self.dimension, (self.index + 1) % self.dimension, parent=self)
			self.right = kdtree(self.dimension, (self.index + 1) % self.dimension, parent=self)
			return "wtf"
		elif self.split[self.index] < thePoint[self.index]:
			return self.left.addPoint(thePoint, self)
		else:
			return self.right.addPoint(thePoint, self)
	
	def __repr__(self):
		if self.split:
			x, y = self.split
			s = '<%s.%s: (%i,%i)>' % (__name__,
									  self.__class__.__name__,
									  x,y)
		else:
			s = '<%s.%s: (TAIL)>' % (__name__,
									 self.__class__.__name__)
		return s

	def getOrientation( self ):
		if self.parent:
			return int(not self.parent.getOrientation())
		else:
			return 0
	
	def getDepth( self ):
		if self.parent:
			return self.parent.getDepth() + 1
		else:
			return 0

	def getRoot( self ):
		if self.parent:
			return self.parent.getRoot()
		else:
			return self

	def getChildrenAtDepth( self, depth ):
		root = self.getRoot()
		kids = root.getChildren()
		return [kid for kid in kids if kid.getDepth() == depth]

	def getParentOfPoint( self, p ):
		kdtrees = self.getChildren()
		k = [k for k in kdtrees if k.split == p]
		assert len(k) == 1
		k = k[0]
		assert k.parent
		return k.parent
	
	def getChildren( self ):
		points = []
		points.append(self)
		if 'left' in self.__dict__.keys():
			points += self.left.getChildren()
		if 'right' in self.__dict__.keys():
			points += self.right.getChildren()
		return [i for i in points if i]
	
	def getPoints( self ):
		points = []
		points.append(self.split)
		if 'left' in self.__dict__.keys():
			points += self.left.getPoints()
		if 'right' in self.__dict__.keys():
			points += self.right.getPoints()
		return [i for i in points if i]
	
	def width( self ):
		points = self.getPoints()
		points = dict(points)
		x = points.keys()
		return max(x) - min(x)
	
	def height( self ):
		points = self.getPoints()
		points = dict(points)
		y = points.values()
		return max(y) - min(y)
	
	minx = lambda self: self.corners()[0][0]
	miny = lambda self: self.corners()[0][1]
	maxx = lambda self: self.corners()[1][0]
	maxy = lambda self: self.corners()[1][1]
	
	def corners( self ):
		points = self.getPoints()
		points = dict(points)
		x = points.keys()
		y = points.values()
		if x and y:
			return (map(min, (x,y))), (map(max, (x,y)))
		else:
			return (0,0), (0,0)
	

def draw( kdroottree ):
	from turtle import Pen
	p = Pen()
	H = 600
	OH = -300
	W = 600
	OW = -300
	bl,ur = kdroottree.corners()
	w = kdroottree.width()
	h = kdroottree.height()
	xscale = W / float(w)
	yscale = H / float(h)
	xoffset = kdroottree.minx()
	yoffset = kdroottree.miny()
	pen.delay(5)
	pen.tracer(False)
	tp = lambda p: ((p[0]-xoffset) * xscale + OW, (p[1]-yoffset) * yscale + OH)
	ul = (bl[0], ur[1])
	br = (ur[0], bl[1])
	ur, ul, br, bl = map( tp, (ur, ul, br, bl) )
	print ul, ur, bl, br
	#draw box
	pen.up()
	pen.goto(ur)
	pen.down()
	pen.goto(ul)
	pen.goto(bl)
	pen.goto(br)
	pen.goto(ur)
	pen.up()
	points = kdroottree.getChildren()
	points = dict( [ (kdtree, kdtree.getDepth()) for kdtree in points ] )
	depths = points.values()
	depths = list(set(depths))
	depths.sort()
	for depth in depths:
		points = kdroottree.getChildrenAtDepth(depth)
		if points:
			for point in points:
				if depth == 0 and point.split:
					assert len(points_in_depth) == 1
					x1, x2 = kdroottree.minx(), kdroottree.maxx()
					y = point.split[1]
					start = tp((x1,y))
					end = tp((x2,y))
					print start, end
					pen.goto(start)
					pen.down()
					pen.goto(end)
					pen.up()
				elif point.split:
					print point
					o = point.getOrientation()
					if o:
						walls = 
	

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)