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()