(function(){

	var Rooms, Tree, sort
	if ('window' in this) {
		Rooms = window.Rooms
		Tree = window.Tree
		sort = window.sort
	}
	else {
		Rooms = require('./_rooms')
		Tree = require('../../models/tree')
		sort = require('../../util/sort')
		FRONT = 0x1, BACK = 0x2, LEFT = 0x4, RIGHT = 0x8, FLOOR = 0x10, CEILING = 0x20
		TOP = CEILING, BOTTOM = FLOOR
		function sidesToString(sides){
			var s = ""
			if (sides & FRONT) s += "front "
			if (sides & BACK)  s += "back "
			if (sides & LEFT)  s += "left "
			if (sides & RIGHT) s += "right "
			if (sides & TOP)  s += "top "
			if (sides & BOTTOM) s += "bottom "
			return s
		}
	}

	Rooms.clipper = new function(){
		var base = this

		base.init = function(){
			base.bind()
			base.update()
		}
	
		base.bind = function(){
			map.ui && map.ui.mouse.tube.on("up", function(){ base.update() })
		}

		base.update = function(){
			base.solve_rects()
		}
	
		var regions
	
		// Given a set of overlapping rooms, clip any intersections, then cull any duplicate polygons
		base.solve_rects = function(){
			if (Rooms.count() == 0) {
				Rooms.regions = regions = []
				return
			}
		  
			base.reset_rects()
			base.clip_rects()
			var culled = base.cull_rects_iterative()

			Rooms.regions = sort.rects_by_position(culled)
		}
	
		// Reset the clipping/culling states of each of the rooms
		base.reset_rects = function(){
			regions = []
			Rooms.forEach(function(room){
				room.reset()
			})
		}

		// Compare each room to the rooms it overlaps, and subdivide
		base.clip_rects = function(){
			var rooms = Rooms.sorted_by_position()

			var left, right
			for (var i = 0; i < rooms.length; i++) {
				left = rooms[i]
				for (var j = i+1; j < rooms.length; j++) {
					right = rooms[j]
					if (left.rect.intersects(right.rect)) {
						left.clipTo(right.rect)
						right.clipTo(left.rect)
						left.intersects.push(right)
						right.intersects.push(left)
					}
					if (left.rect.x.b < right.rect.x.a) {
						break
					}
				}
			}
			for (var i = 0; i < rooms.length; i++) {
				rooms[i].regions = rooms[i].regions.filter(function(r){ return !!r })
				regions = regions.concat(rooms[i].regions)
			}
			
			return regions
		}
	
		// Find overlapping regions (of the same size) and dedupe
		base.cull_rects = function(){
			regions = sort.rects_by_area( regions )

			var ty = new Tree (regions[0].y.a, [regions[0]])
			var tx = new Tree (regions[0].x.a, ty)
			var ttx, tty
	
			for (var i = 1; i < regions.length; i++) {
				ttx = tx.add (regions[i].x.a, null)
				if (ttx.data) {
					tty = ttx.data.add (regions[i].y.a, null)
					// duplicate polygon?
					if (tty.data) {
						tty.data.forEach(function(yy, ii){
							if (yy.intersects(regions[i])) {
								if (yy.area() > regions[i].area()) {
									regions[i].dupe = true
								}
								else {
									yy.dupe = true
									tty.data[ii] = regions[i]
								}
							}
						})
					}
					else {
						tty.data = [regions[i]]
					}
				}
				else {
					ttx.data = new Tree (regions[i].y.a, [regions[i]])
				}
			}
			
			return regions
		}

		// Find overlapping regions and dedupe the smaller ones
		base.cull_rects_iterative = function(){
			regions = sort.rects_by_area( regions )
			
			var region_i, region_j, i, j, _len
			
			for (i = 0, _len = regions.length; i < _len-1; i++) {
				region_i = regions[i]
				for (j = i+1; j < _len; j++) {
					region_j = regions[j]
					if (region_j.dupe) continue;
					if (region_i.overlaps(region_j)) {
						region_i.dupe = true
					}
				}
			}

			return regions.filter(function(r){ return ! r.dupe })
		}

		return base
	}

})()