from Graph import *

class Node:
	def __str__(self):
		return "\"" + str(self.location) + "\""
	

def kdtree(pointList, depth=0):
	if not pointList:
		return

	# Select axis based on depth so that axis cycles through all valid values
 	k = len(pointList[0]) # Assumes all points have the same dimension
	axis = depth % k

	# Sort point list to select median
	pointList.sort(cmp=lambda x, y: cmp(x[axis], y[axis]))
	median = len(pointList)//2 # Choose median

	# Create node and construct subtrees
	node = Node()
	node.location = pointList[median]
	node.leftChild = kdtree(pointList[:median], depth+1)
	node.rightChild = kdtree(pointList[median+1:], depth+1)
    
	return node

# A list of 3d points
pointList = [   (1,2,3), \
		(1,3,4), \
		(-3,2,8), \
		(6,8,9), \
		(-5,2,8), \
		(3,2,9), \
		(6,4,7), \
		(8,2,1) ]

k = kdtree( pointList )

g = Graph( "kdtree" )

def genGraph( node, g, parent=None ):
	if parent is not None:
		g.add( str( parent ), ( str( node ), ) )
	if node.leftChild is not None:
		genGraph( node.leftChild, g, node )
	if node.rightChild is not None:
		genGraph( node.rightChild, g, node )

genGraph( k, g )
print g