gistfile1.txt

class QuadTree:

	def __init__(self,pt):
		self.SE = None
		self.SW = None
		self.NE = None
		self.NW = None
		self.point = pt

	def inorder(self, r=[]):
		hasSE = self.SE is not None
		hasSW = self.SW is not None
		hasNE = self.NE is not None
		hasNW = self.NW is not None
		if self is None :
			return
		else:
			if hasSW:
				self.SW.inorder(r)
			if hasSE:
				self.SE.inorder(r)
			r.append(str(self.point))
			if hasNW:
				self.NW.inorder(r)
			if hasNE:
				self.NE.inorder(r)
		return r

	def __str__(self):
		return str(self.inorder())
		

	def find(self,pt):
		if pt == self.point:
			return True  
		if self.point.x < pt.x:
			#we know we need to be in the south
			if self.point.y < pt.y:
				try:
					return self.SE.find(pt)
				except:
					
					return False
			else:
				try:
					return self.SW.find(pt)
				except:
					return False

		else:
			#we know we need to be in the north
			if self.point.y < pt.y:
				try:
					return self.NW.find(pt)
				except:
					return False
			else:
				try:
					return self.NE.find(pt)
				except:
					return False

	def insert(self,pt):
		#print "="*40
		#print pt
		#print self.point
		#print "="*40
		if pt == self.point:
			raise Exception
		if self.point.x < pt.x:
			#we know we need to be in the south
			if self.point.y < pt.y:
				try:
					self.SE.insert(pt)
				except:		
					self.SE = QuadTree(pt)
			else:
				try:

					self.SW.insert(pt)
				except:					
					self.SW = QuadTree(pt)

		else:
			#we know we need to be in the north
			if self.point.y < pt.y:
				try:
					self.NW.insert(pt)
				except:					
					self.NW = QuadTree(pt)
			else:
				try:
					self.NE.insert(pt)
				except:					
					self.NE = QuadTree(pt)