package graph;

typedef Pos = {
	var l : Int;
	var c : Int;
}

//IDEA: place node given the position of all of its (already placed) neighboors
//FIXME: doesn't handle placing subclasses below parent
class Positioner<T> {
	var graph : Array<GraphNode<T>>;
	var grid : Array<Array<GraphNode<T>>>;

	static final ARROUND : Array<Pos> = [{l:0, c:1}, {l:1, c:0}, {l:-1, c:0}, {l:0, c:-1}, {l:1, c:1}, {l:-1, c:1}, {l:1, c:-1}, {l:-1, c:-1}];

	public function new(graph : Array<GraphNode<T>>) {
		this.graph = graph;
		Lambda.iter(graph, n -> { n.visited = false; n.l = -1; });
	}

	public function arrange() : Array<Array<T>> { //graph is modified
		orderNodes();
		placeNodes();
		var canvas : Array<Array<T>> = new Array();
		for (l in 1...grid.length - 1) { //first and last lines are empty
			var line : Array<T> = new Array();
			for (c in 1...grid[l].length - 1) { //first and last columns are empty
				if (grid[l][c] == null) {
					line.push(null);
				} else {
					//~ grid[l][c].l--; //unneeded
					//~ grid[l][c].c--;
					line.push(grid[l][c].node);
				}
			}
			canvas.push(line);
		}
		//~ debugGraph();
		return canvas;
	}

	function orderNodes() { //descending
		graph.sort((n1, n2) -> n1.links.length == n2.links.length ? 0 : n1.links.length > n2.links.length ? -1 : 1);
		for (n in graph) {
			n.links.sort((n1, n2) -> n1.links.length == n2.links.length ? 0 : n1.links.length > n2.links.length ? -1 : 1);
		}
	}

	function placeNodes() {
		grid = new Array(); //initialise an empty 1x1 grid
		grid.push(new Array());
		grid[0].push(null);
		var queue : List<GraphNode<T>> = new List();
		Lambda.iter(graph, sn -> if (!sn.visited) {
			queue.push(sn);
			placeNode(sn, getUnlinkedNodePos());
			while (queue.length != 0) {
				var n : GraphNode<T> = queue.pop();
				if (!n.visited) {
					n.visited = true;
					for (l in n.links) {
						queue.push(l);
					}
					placeNodeNeighbours(n);
				}
			}
		});
	}

	function placeNodeNeighbours(n : GraphNode<T>) {
		for (l in n.links) {
			var i : Int = 0;
			var placed : Bool = l.l != -1;
			while (!placed && i < ARROUND.length) {
				var p : Pos = { l : n.l + ARROUND[i].l, c : n.c + ARROUND[i].c };
				if (grid[p.l][p.c] == null) {
					placed = true;
					placeNode(l, p);
					placeCommonNeighBours(n, l);
				}
				i++;
			}
			if (!placed) { //no place arround
				placeNode(l, getUnlinkedNodePos());
			}
		}
	}

	function placeCommonNeighBours(n : GraphNode<T>, l : GraphNode<T>) {
		var surroundingPos : Array<Pos> = null;
		if (n.l == l.l) {
			surroundingPos = [{l:n.l + 1, c:l.c}, {l:n.l - 1, c:l.c}, {l:n.l + 1, c:n.c}, {l:n.l - 1, c:n.c}];
		} else if (n.c == l.c) {
			surroundingPos = [{l:l.l, c:n.c + 1}, {l:l.l, c:n.c - 1}, {l:n.l, c:n.c + 1}, {l:n.l, c:n.c - 1}];
		} else {
			surroundingPos = [{l:n.l, c:l.c}, {l:l.l, c:n.c}];
		}
		for (nl in Lambda.filter(n.links, nl -> l.links.indexOf(nl) != -1)) { //for each node in common
			var placed : Bool = nl.l != -1;
			var i : Int = 0;
			while (!placed && i < surroundingPos.length) {
				var p : Pos = surroundingPos[i];
				if (grid[p.l][p.c] == null) {
					placed = true;
					placeNode(nl, p);
				}
				i++;
			}
		}
	}

	function placeNode(n : GraphNode<T>, p : Pos) { //graph nodes are always surrounded by an empty line and column
		grid[p.l][p.c] = n;
		n.l = p.l;
		n.c = p.c;
		if (p.l == grid.length - 1) {
			addBottomLine();
		}
		if (p.l == 0) {
			addAboveLine();
		}
		if (p.c == grid[0].length - 1) {
			addRightColumn();
		}
		if (p.c == 0) {
			addLeftColumn();
		}
	}

	function addLeftColumn(left : Bool = false) {
		for (line in grid) {
			line.insert(0, null);
			Lambda.iter(line, gn -> if (gn != null) gn.c++ );
		}
	}

	function addRightColumn() {
		for (line in grid) {
			line.push(null);
		}
	}

	function addAboveLine() {
		var line : Array<GraphNode<T>> = new Array();
		for (i in 0...grid[0].length) {
			line.push(null);
		}
		for (line in grid) {
			Lambda.iter(line, gn -> if (gn != null) gn.l++ );
		}
		grid.insert(0, line);
	}

	function addBottomLine() {
		var line : Array<GraphNode<T>> = new Array();
		for (i in 0...grid[0].length) {
			line.push(null);
		}
		grid.push(line);
	}

	function getUnlinkedNodePos() : Pos {
		var l : Int = grid.length - 1;
		var c : Int = grid[0].length - 1;
		if (grid[l][c] != null) {
			addRightColumn();
			c++;
		}
		return { l : l, c : c };
	}

	//~ function debugGraph() {
		//~ for (n in graph) {
			//~ Sys.print("- " + n.name + (n.l == -1 ? "" : "(" + Std.string(n.l) + "," + Std.string(n.c) + ")") + " : ");
			//~ for (i in 0...n.links.length) {
				//~ if (i != 0) {
					//~ Sys.print(", ");
				//~ }
				//~ Sys.print(n.links[i].name);
			//~ }
			//~ Sys.println("");
		//~ }
	//~ }
}
