from __future__ import print_function
 import bisect
 import collections
 from util import CoordPair
 
 class RoomTree(object):
 	def __init__(self):
 		self.rooms = []
 	def add_room(self, room):
 		def dist(pos):
 			return (pos[0]**2 + pos[1]**2)**0.5
 		bisect.insort(self.rooms, (dist(room.pos),room))
 
 class RoomGrid(object):
 	def __init__(self, size):
 		self.grid = [[None for __ in range(size[1])] for ___ in range(size[0])]
 		self.size = size
 	
 UP,DOWN,LEFT,RIGHT = range(4)
 opposite = {UP:DOWN,LEFT:RIGHT,DOWN:UP,RIGHT:LEFT}
 strings = {UP:'up',DOWN:'down',LEFT:'left',RIGHT:'right'}
 # 4y    g  h  i
 # 3y    a  b  c
 # 2y    d  e  f
 # 1y
 # 0y
 #    0x 1x 2x 3x 4x
 # (x,y)
 
 class Room(object):
 	@property
 	def sw(self):
 		return self.pos
 	@property
 	def se(self):
 		return self.pos[0]+self.size[0]-1, self.pos[1]
 	@property
 	def ne(self):
 		return self.pos[0]+self.size[0]-1, self.pos[1]+self.size[1]-1
 	@property
 	def nw(self):
 		return self.pos[0], self.pos[1]+self.size[1]-1
 	@property
 	def corners(self):
 		'SW, SE, NE, NW'
 		return self.sw, self.se, self.ne, self.nw
 
 	@property
 	def rect(self):
 		return self.pos, self.size
 
 	def __init__(self, pos, size):
 		self.pos = pos
 		self.size = size
 		self.neighbours = [None,None,None,None] # u,d,l,r
 
 	def add_neighbour(self, other):
 		sx,sy = self.pos
 		ox,oy = other.pos
 		
 		direction = None
 		cont = False
 		if sx > other.se[0]+1:
 			direction = LEFT
 			cont = True
 		elif sx < ox - 1:
 			direction = RIGHT
 			cont = True
 
 		if cont == False:
 			if sy > other.nw[1]+1:
 				direction = DOWN
 				cont = True
 			elif sy < oy-1:
 				direction = UP
 				cont = True
 			else:
 				raise ValueError('overlapping rooms')
 
 		neighbour = self.neighbours[direction]
 		if neighbour is None:
 			other.neighbours[opposite[direction]] = self	
 			self.neighbours[direction] = other
 		else:
 			neighbour.add_neighbour(other)
 
 	def __repr__(self):
 		return '%s(%r,%r)' % (self.__class__.__name__, self.pos, self.size)
 
 	def print(self, ind=0, prefix='', visited=None):
 		if visited is None: visited = set()
 		visited.add(self)
 		print('\t'*ind, prefix, ': ', self,sep='')
 		for idx,x in enumerate(self.neighbours):
 			if x is not None and x not in visited:
 				x.print(ind=ind+1, prefix=strings[idx], visited=visited)
 
 
 if __name__ == '__main__':
 	x = Room((0,0), (3,3))
 	y = Room((4,0), (3,3))
 	x.add_neighbour(y)
 	y = Room((-4,0), (3,3))
 	x.add_neighbour(y)
 	y = Room((0,4), (3,3))
 	x.add_neighbour(y)
 	y = Room((0,-4), (3,3))
 	x.add_neighbour(y)
 	y = Room((-4,4), (3,3))
 	x.add_neighbour(y)
 	y = Room((-4,-4), (3,3))
 	x.add_neighbour(y)
 	y = Room((4,4), (3,3))
 	x.add_neighbour(y)
 	y = Room((4,-4), (3,3))
 	x.add_neighbour(y)
 	x.print()
 	print()
 	y.print()