/* Filename: graph.js
 * This file is part of the gRaDF Semantic Web browsing tool.
 * Copyright (C) 2006  Marcus Cobden
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 * (or see the file gpl.txt)
 * 
 * 	Description:
 * This file contains a library of classes implementing an abstract force directed graph layout engine.
 * 
 *	Classes:
 * GraphNode
 * GraphEdge
 * GPlotter
 * GOptions
 * FADETree
 * FADELevel
 * 
 * 	Version information:
 * $HeadURL: svn+ssh://mc1204@svn.ugforge.ecs.soton.ac.uk/projects/grdf/code/branches/serverside/js/graph.js $
 * $Date: 2007-06-21 16:38:10 +0100 (Thu, 21 Jun 2007) $
 * $Author: mc1204 $
 * $Rev: 134 $
 */

	/* Debug placeholders */
window.gLOG = function(message, section)	{};
window.gWARN = function(message, section)	{};
window.gERROR = function(message, section)	{};
	/* End Debug placeholders */

/**
 * 	GraphNode 
 *
 * Represents a node on a force directed graph
 * ( Required )
 * @param id	Unique ID for this node
 * ( Optional )
 * @param nodeType Node type to link to. Used to xlink to a element inside the defs section.
 * @param events Associative array for events to be registered on this node. Key is the event id; eg. 'mouseover'
 * @param fixed	Boolean. Whether the node is fixed in place or free to move.
 */
function GraphNode(id, events, nodeType, fixed) {
	this.id = id;
	this.mass = 1;
	this.events = events;
		
	if (nodeType == null)
		this.nodeType = 'node';
	else
		this.nodeType = nodeType;
			
	if (fixed == null)
		this.fixed = false;
	else
		this.fixed = fixed;
		
	return this;
}

GraphNode.prototype.type = 'GraphNode';

/**
 * 	GraphEdge
 *
 * Represents an edge (node-node link) on a force directed graph
 * ( Required )
 * @param id	Unique ID for this edge
 * @param start	GraphNode at the beginning of the link
 * @param end	GraphNode at the end of the link
 * ( Optional )
 * @param edgetype	Type of the edge. Unimplemented
 * @param events DOM Events to register on this edge 
 */
function GraphEdge(id, start, end, edgetype, events)
{
	this.id = id;
	this.start = start;
	this.end = end;
	this.edgetype = edgetype;
	this.events = events;
	
	return this;
}

GraphEdge.prototype.type = 'GraphEdge';

/* Begin GPlotter */

function GPlotter(elementID, gOptions){
	this.type = "Graph Plotter";
	this.elemID = elementID;
	this.elem = document.getElementById(elementID);
	this.opt = gOptions;
	
	// Set up callback
	this.elem.callback = this;
	
	// Namespaces
	this.ns = [];
	this.ns['svg'] = 'http://www.w3.org/2000/svg';
	this.ns['xlink'] = 'http://www.w3.org/1999/xlink';
	
	// GraphNode collection
	this.nodes = [];
	// SVG node collection
	this.svgNodes = [];
	// GraphEdge collection
	this.edges = [];
	// SVG edge collection
	this.svgEdges = [];
	
	// Mouse event information container
	this.mouse = [];
	
	// Disable context menus!
	this.elem.addEventListener('contextmenu',function(event){
		event.preventDefault();	
		event.returnValue = false; // Not nessecary?
		event.stopPropagation();
		return false;
	}, false);
	
	return this;
}

/**
 * addNode - Adds a node into the force directed graph
 *
 * @param node	GraphNode to be added.
 */
GPlotter.prototype.addNode = function(node, referenceNode) {
	var svgElem = this.elem;
	var svgNode = document.createElementNS(this.ns.svg, 'use');

	//getNodeAddRadius
	// svgNode.setAttribute('id', this.elemID + ':node:' + node.id);
	svgNode.setAttributeNS(this.ns.xlink, 'href', '#' + node.nodeType);
	
	var rand = function (n) { return (Math.floor (Math.random() * n + 1)); };
	
	var temp = [];
	// Initial position
	temp['x'] = 0;
	temp['y'] = 0;
	
	var rad;
	if (referenceNode != null &&
		this.svgNodes[referenceNode.id] != null &&
		(rad = this.opt.getNodeAddRadius()) != null) {
		// If we are told to add it near to an existing node, do so at a random point in a circle around the reference node
		
		var r = Math.floor((rad.max - rad.min) * Math.random()) + rad.min;
		var angle = 2 * Math.PI * Math.random();
		var ref = this.svgNodes[referenceNode.id].temp;
	
		temp.x = r * Math.cos(angle) + ref.x;
		temp.y = r * Math.sin(angle) + ref.y;
	} else {
		// else just be randomly placed
		temp.x = rand(svgElem.width.baseVal.value);
		temp.y = rand(svgElem.height.baseVal.value);
	}
	
	// Initial speed
	temp['dx'] = 0;		temp['dy'] = 0;
	// Initial Acceleration
	temp['dvdx'] = 0;	temp['dvdy'] = 0;
	// The mass of the node
	temp['mass'] = node.mass;
	// The GraphNode associated with this node
	temp['node'] = node;
	// The node-node links which start/end at this node respectively
	temp['lineStart'] = [];
	temp['edgeStart'] = [];
	temp['lineEnd'] = [];
	temp['edgeEnd'] = [];
	
	this.nodes[node.id] = node;
	this.svgNodes[node.id] = svgNode;
	
	svgNode.setAttribute('fixed', node.fixed);
	//svgNode.setAttribute('transform', 'translate(' + svgNode.temp.x -10 + ',' + svgNode.temp.y -10+ ')');
	svgNode.setAttribute('x', temp.x -10);
	svgNode.setAttribute('y', temp.y -10);
	svgNode.setAttribute('width', 20);
	svgNode.setAttribute('height', 20);
	svgNode.addEventListener('mousedown',this.mouseDownCallback,false);
	
	svgNode['temp'] = temp;
	
	for(var id in node.events){
		svgNode.addEventListener(id,node.events[id],false);
	}
	
	svgElem.appendChild(svgNode);
};

// TODO
GPlotter.prototype.updateNode = function(node) {
	var svgNode = this.svgNodes[node.id];
	svgNode.temp.mass = node.mass;
	svgNode.setAttribute('fixed', node.fixed);
	svgNode.setAttributeNS(this.ns.xlink, "href", '#' + node.nodeType);
};

/**
 * 	removeNode
 * Removes a Node from the graph
 * 
 * @return returns any edges also removed due to the action.
 */
GPlotter.prototype.removeNode = function(node) {
	var svgElem = this.elem;
	
	var edges = [];
	
	edges = edges.concat(this.svgNodes[node.id].temp.edgeStart);
	edges = edges.concat(this.svgNodes[node.id].temp.edgeEnd);
	
	svgElem.removeChild(this.svgNodes[node.id]);
	delete this.nodes[node.id];
	delete this.svgNodes[node.id];
	
	this.removeEdges(edges);
	
	return edges;
};

/**
 * 	addEdges
 * Adds a collection of edges to the graph
 * 
 * @param edges Array of edges to add
 */
GPlotter.prototype.addEdges = function(edges) {
	var svgElem = this.elem;
	
	for (id in edges){
		edge = edges[id];
		if(this.edges[edge.id] != null){
			gERROR('Attempted to add the same node twice.', this.type);
			continue;
		}	
		this.edges[edge.id] = edge;
		line = document.createElementNS(this.ns.svg, 'line');
		
		this.svgEdges[edge.id] = line;

		line.setAttribute('x1', this.svgNodes[edge.start.id].x.baseVal.value +10);
		line.setAttribute('y1', this.svgNodes[edge.start.id].y.baseVal.value +10);
		line.setAttribute('x2', this.svgNodes[edge.end.id].x.baseVal.value +10);
		line.setAttribute('y2', this.svgNodes[edge.end.id].y.baseVal.value +10);
		line.setAttribute('class', 'link');
		
		this.svgNodes[edge.start.id].temp.lineStart[edge.id] = line;
		this.svgNodes[edge.start.id].temp.edgeStart[edge.id] = edge;
		this.svgNodes[edge.end.id].temp.lineEnd[edge.id] = line;
		this.svgNodes[edge.end.id].temp.edgeEnd[edge.id] = edge;
		
		for(var index in edge.events){
			line.addEventListener(index,edge.events[index],false);
		}
		
		svgElem.appendChild(line);
	}
	
	// Re-order the svg so the nodes are infront of the lines
	for (id in this.svgNodes){
		svgElem.appendChild(this.svgNodes[id]);
	}
};

/**
 * 	removeEdges
 * Removes a collection of edges from the graph
 * 
 * @param edges Array of edges to remove
 */
GPlotter.prototype.removeEdges = function(edges) {
	var svgElem = this.elem;
	
	for (i in edges){
		var edge = edges[i];
		if (this.edges[edge.id] == null){
			gERROR('Attempted to remove an edge which wasn\'t there.', this.type);
			continue;
		}
		
		var startNode = this.svgNodes[edge.start.id];
		if (startNode != null){
			delete startNode.temp.lineStart[edge.id];
			delete startNode.temp.edgeStart[edge.id];
		}
		var endNode = this.svgNodes[edge.end.id];
		if (endNode != null){
			delete endNode.temp.lineEnd[edge.id];
			delete endNode.temp.edgeEnd[edge.id];
		}
		
		svgElem.removeChild(this.svgEdges[edge.id]);
		
		delete this.svgEdges[edge.id];
		delete this.edges[edge.id];
	}
};

/**
 * 	removeAllEdges
 * Removes all the edges from the graph
 */
GPlotter.prototype.removeAllEdges = function() {
	var svgElem = this.elem;

	// Remove the lines from the DOM
	for (id in this.svgEdges){
		if (this.svgEdges[id].parentNode != null)
			svgElem.removeChild(this.svgEdges[id]);
	}
	// Remove them from the svg nodes
	for (id in this.svgNodes){
		this.svgNodes[id].temp.lineStart = [];
		this.svgNodes[id].temp.lineEnd = [];
	}
	
	// Delete the collections;
	delete this.svgEdges;
	this.svgEdges = [];
	delete this.edges;
	this.edges = [];
};

/**
 * 	timeStep
 * performs a timestep of the force-directed graph
 * 
 * @param interval Unimlemented.
 * (Could be used to perform svg animation of the nodes 
 * between each timestep, however there is no browser
 * support for this yet, so it is not implemented)
 */
GPlotter.prototype.timeStep = function(interval) {
	// Interval unused, is there for when future versions of firefox support svg animation.
	var svgElem = this.elem;
	var canvas = [];
	canvas['width'] = svgElem.width.baseVal.value;
	canvas['height'] = svgElem.height.baseVal.value;
	
	for (id in this.svgNodes){
		this.svgNodes[id].temp.dvdx = 0;
		this.svgNodes[id].temp.dvdy = 0;
	}
	
	this.edgeForces();
	this.nonedgeForces();

	// Friction coefficient
	var mu = this.opt.getFriction();
	// Maximum force!
	var maxForce = this.opt.getMaxForce();
	var maxForceSq = maxForce*maxForce;
	// Maximum speed
	var maxSpeed = this.opt.getMaxSpeed();
	var maxSpeedSq = maxSpeed*maxSpeed;
			
	for (id in this.svgNodes){
		var node = this.svgNodes[id];
		var nodetemp = node.temp;
		
		// Friction
		var speed = nodetemp.dx*nodetemp.dx + nodetemp.dy*nodetemp.dy;
		var force = nodetemp.dvdx*nodetemp.dvdx + nodetemp.dvdy*nodetemp.dvdy;
		if (speed == 0){
			if (force != 0) {
				// If the node is stopped but has some force acting on it
				// Don't let the friction be more than the force, because that'd be silly
				// (things would start moving away from the force untill the force was greater than friction)
				var xScale = Math.abs(nodetemp.dvdx) + Math.abs(nodetemp.dvdy);
				var yScale = nodetemp.dvdy / xScale;
				xScale = nodetemp.dvdx / xScale;
				
				var friction =  Math.min(nodetemp.mass * mu, Math.sqrt(force));
				nodetemp.dvdx -= xScale * friction;
				nodetemp.dvdy -= yScale * friction;
				
				force = nodetemp.dvdx*nodetemp.dvdx + nodetemp.dvdy*nodetemp.dvdy;
			}
		} else {
			// If the node is in motion apply the full force
			// but don't actually apply the full force, because we calculate it in jumps so it might make it go backwards too.
			var xScale = Math.abs(nodetemp.dx) + Math.abs(nodetemp.dy);
			var yScale = nodetemp.dy / xScale;
			xScale = nodetemp.dx / xScale;
			
			var friction = Math.min(nodetemp.mass * mu, Math.sqrt(speed));
			nodetemp.dvdx -= xScale * friction;
			nodetemp.dvdy -= yScale * friction;
		}

		// Maximum force (Square root optimisation here)
		if (force > maxForceSq) {
			var scale = maxForce / Math.sqrt(force);
			nodetemp.dvdx *= scale;
			nodetemp.dvdy *= scale;
		}
		
		// Apply the force to the motion
		nodetemp.dx += nodetemp.dvdx / nodetemp.mass;
		nodetemp.dy += nodetemp.dvdy / nodetemp.mass;
		
		// Maximum Speed (Square root optimisation here)
		var speed = nodetemp.dx*nodetemp.dx + nodetemp.dy*nodetemp.dy;
		if (speed > maxSpeedSq) {
			var scale = maxSpeed / Math.sqrt(speed);
			nodetemp.dx *= scale;
			nodetemp.dy *= scale;
		}		
		
		// Check the window bounds
		if(nodetemp.x + nodetemp.dx  <= 0) {
			nodetemp.dx = - nodetemp.x;
		} else if(nodetemp.x + nodetemp.dx  >= canvas.width) {
			nodetemp.dx = canvas.width - nodetemp.x;
		}
		if(nodetemp.y + nodetemp.dy  <= 0) {
			nodetemp.dy = - nodetemp.y;
		} else if(nodetemp.y + nodetemp.dy  >= canvas.height) {
			nodetemp.dy = canvas.height - nodetemp.y;
		}
		
		// Move the node
		if(nodetemp.node.fixed == false) {
			// Update the position from the speed
			nodetemp.x += nodetemp.dx;
			nodetemp.y += nodetemp.dy;
			// Stop it eating CPU
			if(Math.abs(nodetemp.x - node.x.baseVal.value) > 3 || Math.abs(nodetemp.y - node.y.baseVal.value) > 3){
				// Move the node in the DOM
				node.setAttribute('x', Math.round(nodetemp.x -10));
				node.setAttribute('y', Math.round(nodetemp.y -10));
			
				// Move any attatched edges
				var line = null;
				// Lines starting here
				for (index in nodetemp.lineStart){
					line = nodetemp.lineStart[index];
					line.setAttribute('x1', nodetemp.x);
					line.setAttribute('y1', nodetemp.y);
				}
				// Lines ending here
				for (index in nodetemp.lineEnd){
					line = nodetemp.lineEnd[index];
					line.setAttribute('x2', nodetemp.x);
					line.setAttribute('y2', nodetemp.y);
				}
			}
		} else {
			// Node is fixed, so has no speed
			nodetemp.dx = 0;
			nodetemp.dy = 0;
		}
	}
	/*
	var line = null;
	for (var id in this.svgEdges){
		line = this.svgEdges[id];
		line.setAttribute('x1', this.svgNodes[this.edges[id].start.id].getCTM().e +10);
		line.setAttribute('y1', this.svgNodes[this.edges[id].start.id].getCTM().f +10);
		line.setAttribute('x2', this.svgNodes[this.edges[id].end.id].getCTM().e +10);
		line.setAttribute('y2', this.svgNodes[this.edges[id].end.id].getCTM().f +10);
	}*/
};

/**
 * 	nonedgeForces
 * performs one calculation of the non-edge forces in the graph
 */
GPlotter.prototype.nonedgeForces = function() {
	var svgElem = this.elem;
	
	var tree = new FADETree(this, this.opt);
	tree.insertNodes(this.svgNodes);
	tree.apply();
	
	// Tree decomposition display
	if(this.treeRects != null){
		for(id in this.treeRects){
			svgElem.removeChild(this.treeRects[id]);
		}
		this.treeRects = null;
	}
	
	if(this.opt.nonedge.showTree == true)
		this.treeRects = tree.showRects();
};

/**
 * 	edgeForces
 * performs one calculation of the edge forces in the graph
 */
GPlotter.prototype.edgeForces = function() {
	var svgElem = this.elem;
	var canvas = [];
	canvas.width = svgElem.width.baseVal.value;
	canvas.height = svgElem.height.baseVal.value;

	for (id in this.edges){
		// Don't do circular links!
		if(this.edges[id].start == this.edges[id].end){
			continue;
		}
			
		var startNode = this.svgNodes[this.edges[id].start.id];
		var endNode = this.svgNodes[this.edges[id].end.id];
		
		// get Hooke's law (constants)
		var temp = this.opt.getEdgeProperties(this.edges[id].edgetype);
		var k = temp.k;	// Scale
		var l = temp.l; // Natural Length
		
		var Ax = endNode.temp.x - startNode.temp.x;
		var Ay = endNode.temp.y - startNode.temp.y;
		
		var d = Math.sqrt(Math.pow(Ax,2) + Math.pow(Ay,2));
		
		var Sx = Ax;
		var Sy = Ay;
		
		if (d != 0) {
			var Axy = Math.abs(Ax) + Math.abs(Ay);
			Sx /= Axy; Sy /= Axy;
		} else {
			// For safety, assume they can't really be on exactly the same point
			d = 0.0001;
			Sx = (Math.random() *2) -1;
			Sy = (Math.random() *2) -1;
		}
		
		// Hooke's law (equasion)
		var force = k * (d - l);
		
		// Fixed position doubles the force? Probably not.
		/*if ((startNode.temp.node.fixed == null || startNode.temp.node.fixed == false)
				&& (endNode.temp.fixed == null || endNode.temp.fixed == false)) {*/
			startNode.temp.dvdx += force * Sx;
			startNode.temp.dvdy += force * Sy;
			endNode.temp.dvdx -= force * Sx;
			endNode.temp.dvdy -= force * Sy;
		/*} else if ((startNode.temp.node.fixed == null || startNode.temp.node.fixed == false)
				&& (endNode.temp.node.fixed != null && endNode.temp.node.fixed == true)){
			startNode.temp.dvdx += 2 * force * Sx;
			startNode.temp.dvdy += 2 * force * Sy;
		} else if ((startNode.temp.node.fixed != null && startNode.temp.node.fixed == true)
				&& (endNode.temp.node.fixed == null || endNode.temp.node.fixed == false)){
			endNode.temp.dvdx -= 2 * force * Sx;
			endNode.temp.dvdy -= 2 * force * Sy;
		}*/
	}
};

/**
 * 	startDrag
 * Performs housekeeping for the beginning of a dragging event
 * @param event Mouse event
 */
GPlotter.prototype.startDrag = function(event) {
	var svgRoot = event.currentTarget.parentNode;
	svgRoot.addEventListener('mousemove',this.mouseMoveCallback,false);
	svgRoot.addEventListener('mouseup',this.mouseUpCallback,false);
	
	event.currentTarget.temp['prevState'] = event.currentTarget.temp.node.fixed;
	event.currentTarget.temp.node.fixed = true;
		
	this.mouse.target = event.currentTarget;
	this.mouse.startX = event.layerX;
	this.mouse.startY = event.layerY;
	
	this.mouse.offsetX = event.currentTarget.x.baseVal.value - this.mouse.startX;
	this.mouse.offsetY = event.currentTarget.y.baseVal.value - this.mouse.startY;
};

/**
 * 	startDrag
 * Tidies up after a drag event.
 * Also detects when a drag was actually just a click.
 *
 * @param event Mouse event
 */
GPlotter.prototype.endDrag = function(event) {
	var svgRoot = event.currentTarget;
	svgRoot.removeEventListener('mousemove',this.mouseMoveCallback,false);
	svgRoot.removeEventListener('mouseup',this.mouseUpCallback,false);

	var d = Math.sqrt(Math.pow(event.layerX - this.mouse.startX,2) + Math.pow(event.layerY - this.mouse.startY,2));
	
	// Click for stickyness. Number allows for a bit of accidental mouse movement
	var target = this.mouse.target.temp;
	if (d < 3) {
		target.node.fixed = ! target.prevState;
	} else {
		target.node.fixed = target.prevState;
	}
	this.updateNode(target.node);
};

/**
 * 	mouseDownCallback
 * Callback function for 'mousedown' events on graph nodes
 *
 * @param event Mouse event
 */
GPlotter.prototype.mouseDownCallback = function(event) {
	if(event.button == 0)
		event.currentTarget.parentNode.callback.startDrag(event);
};

/**
 * 	mouseDownCallback
 * Callback function for 'mousemove' events on the svg canvas
 *
 * @param event Mouse event
 */
GPlotter.prototype.mouseMoveCallback = function(event) {
	var mouse = event.currentTarget.callback.mouse;
	var x = mouse.offsetX + event.layerX;
	var y = mouse.offsetY + event.layerY;
	// maintain the node's position variable
	mouse.target.temp.x = x +10;
	mouse.target.temp.y = y +10;
	mouse.target.setAttribute('x', x);
	mouse.target.setAttribute('y', y);
	//mouse.target.setAttribute('transform', 'translate(' + x + ',' + y + ')');
	
	// Move any attatched edges
	var line = null;
	// Lines starting here
	for (index in mouse.target.temp.lineStart){
		line = mouse.target.temp.lineStart[index];
		line.setAttribute('x1', mouse.target.temp.x);
		line.setAttribute('y1', mouse.target.temp.y);
	}
	// Lines ending here
	for (index in mouse.target.temp.lineEnd){
		line = mouse.target.temp.lineEnd[index];
		line.setAttribute('x2', mouse.target.temp.x);
		line.setAttribute('y2', mouse.target.temp.y);
	}
};

/**
 * 	mouseDownCallback
 * Callback function for 'mouseup' events on the svg canvas
 *
 * @param event Mouse event
 */
GPlotter.prototype.mouseUpCallback = function(event) {
	event.currentTarget.callback.endDrag(event);
};

/* End GPlotter */

/* Begin FADETrees */

/**
 * 	FADETree
 * An optimisation method for non-edge forces, reducing the complexity of the comparison operation
 * 
 * @param owner 
 * @param gOptions
 * @param width Width of the entire tree
 * @param height Height of the entire tree
 */
function FADETree(owner, gOptions)
{
	this.type = 'FADETree';
	this.owner = owner;
	this.opt = gOptions;
	var elem = owner.elem;
	var width = elem.width.baseVal.value;
	var height = elem.height.baseVal.value;
	
	this.levels = [];		
	this.topLevel = new FADELevel(this, 0, 0, 0, width, height);
	
	this.delta = this.opt.getNonedgeDelta();
	this.scale = this.opt.getNonedgeProperties();
	// Maximum distance to apply forces up to
	this.maxDist = this.opt.getNonedgeMaxDist();
	
	// The square of the minimum distance
	this.minSqDist = this.scale / this.opt.getMaxForce();
	// TODO remove
	return this;
}

FADETree.prototype.insertNodes = function(nodes) {
	for (id in nodes){
		var node = nodes[id];
		var level = 0;
		var nodeRecord = this.levels[0][0].insertNode(node);

		while (nodeRecord != null){
			level++;

			if (nodeRecord.length == 1){
				nodeRecord = this.levels[level][nodeRecord[0].id].insertNode(nodeRecord[0].node);
			} else if (nodeRecord.length == 2) {
				this.levels[level][nodeRecord[0].id].insertNode(nodeRecord[0].node);
				nodeRecord = this.levels[level][nodeRecord[1].id].insertNode(nodeRecord[1].node);

			} else {
				gERROR('Unhandled Special Case', this.type);
			}
		}
	}
};

FADETree.prototype.apply = function() {
	this.calcMass();
	this.applyMass();
}

FADETree.prototype.calcMass = function() {
	for(var i = this.levels.length -1; i >= 0; i--){
		for(var id in this.levels[i]){
			this.levels[i][id].calcMass();
		}
	}
};

FADETree.prototype.applyMass = function() {
	var dist = this.delta;
	var leaves = this.getLeafNodes();
	
	for(id in leaves){
		
		for(nodeID in leaves[id].nodes){
			var node = leaves[id].nodes[nodeID];
			// If this node can't move, don't bother with it.
			if (node.fixed == true)
				continue;
				
			var levels = [];
			levels.push(this.topLevel);
			
			while(levels.length != 0){
				var newLevels = [];
				
				for(key in levels){
					var above, below, left, right;
					above = (levels[key].top > node.temp.y);
					below = (levels[key].top + levels[key].height < node.temp.y);
					left = (levels[key].left > node.temp.x);
					right = (levels[key].left + levels[key].width < node.temp.x);
					
					var s, d;
					/* = Math.sqrt(Math.pow(levels[key].width,2) + Math.pow(levels[key].height,2));
					var d = Math.sqrt(
						Math.pow(levels[key].mass.x - node.temp.x,2) +
						Math.pow(levels[key].mass.y - node.temp.y,2));*/
					if (above ^ below ^ left ^ right) {
						// Node is Along one side - Not diagonal
						if (above ^ below){
							// Top or bottom
							s = levels[key].height;
							d = (above ? levels[key].top - node.temp.y : node.temp.y - levels[key].top - levels[key].height);
						} else {
							// Left or right
							s = levels[key].width;
							d = (left ? levels[key].left - node.temp.x : node.temp.x - levels[key].left - levels[key].width);
						}
					} else {
						s = Math.sqrt(Math.pow(levels[key].width,2) + Math.pow(levels[key].height,2));
						if ((above || below || left || right) == false){
							// Inside
							d = 0.0000001; // Very small number, should be 0 but would give infinity
						} else {
							// Some kind of diagonal
							var x = levels[key].left + (left ? 0 : levels[key].width) - node.temp.x;
							var y = levels[key].top + (above ? 0 : levels[key].height) - node.temp.y;
							d = Math.sqrt(x*x + y*y);
						}
					}
					
					if(s/d > dist){
						// Close
						if(levels[key].childCount != 0){
							for(index in levels[key].children){
								newLevels.push(levels[key].children[index]);
							}
						} else {
							for(index in levels[key].nodes){
								if (leaves[id].nodes[nodeID] != levels[key].nodes[index])
									this.applyForce(node.temp, levels[key].nodes[index].temp);
							}
						}
					} else {
						// Far
						// Average node forces
						this.applyForce(node.temp, levels[key].mass);
					}
				}
				levels = newLevels;
			}
		}
	}
};

FADETree.prototype.applyForce = function(subject, reference) {
	// Coulomb's law constant
	var k = this.scale;
	// Maximum Distance
	var maxDist = this.maxDist;
	
	var Ax = subject.x - reference.x;
	var Ay = subject.y - reference.y;

	var d = Ax * Ax + Ay * Ay;

	// TODO Check
	if (maxDist != -1){
		if (d > maxDist * maxDist)
			return;
	}

	var Sx = Ax;
	var Sy = Ay;

	
	if (d >= this.minSqDist) { // If nodes are far enough apart
		var Axy = Math.abs(Ax) + Math.abs(Ay);
		Sx /= Axy; Sy /= Axy;
	}
	else if (d > 1){ // If nodes are close
		var Axy = Math.abs(Ax) + Math.abs(Ay);
		d = this.minSqDist;
		Sx /= Axy; Sy /= Axy;
	}
	else { // If nodes are practically atop each other
		// For divideByZero safety, assume they can't really be on exactly the same point
		d = this.minSqDist;
		Sx = Math.random();
		Sy = 1 - Sx;
		Sx *= 1- Math.floor(Math.random() *2) *2;
		Sy *= 1- Math.floor(Math.random() *2) *2;
	}
	
	// Coulomb's law
	var force = (k * subject.mass * reference.mass) / d;

	subject.dvdx += force * Sx;
	subject.dvdy += force * Sy;
};

FADETree.prototype.getLeafNodes = function() {
	var leaves = [];
	for(var i = this.levels.length -1; i >= 0; i--){
		for(var id in this.levels[i]){
			if (this.levels[i][id].childCount == 0 && this.levels[i][id].nodes.length != 0)
				leaves.push(this.levels[i][id]);
		}
	}
	return leaves;
};

FADETree.prototype.showRects = function() {
	var rects = [];
	for(var i = 0; i < this.levels.length; i++){
		for(var id in this.levels[i]){
			rects.push(this.levels[i][id].showRect());
		}
	}
	return rects;
};

function FADELevel(collection, level, left, top, width, height)
{
	this.type = 'FADELevel';
	this.collection = collection;
	this.level = level;
	this.children = [];
	this.childCount = 0;
	
	if(collection.levels[level] == null){
		collection.levels[level] = [];
	}
	this.id = collection.levels[level].length;
	collection.levels[level][this.id] = this;
	
	this.left = left;
	this.top = top;
	this.width = width;
	this.height = height;
	
	this.nodes = [];
	this.mass = null;
	
	return this;
}

FADELevel.prototype.insertNode = function(newNode) {
	if (// No Node and no child branches
			(this.nodes.length == 0 && this.childCount == 0) ||
			// Don't subdivide forever
			(this.width <= 1 || this.height <= 1)){
		this.nodes.push(newNode);
		return null;
	} else {
		var out = [];
		var temp = [];
		
		// Pass back the existing node
		if (this.nodes.length == 1) {
			
			temp['id'] = this.children[this.checkQuad(this.nodes[0])].id;
			temp['node'] = this.nodes[0];
			out.push(temp);
			this.nodes = [];
		} else if (this.nodes.length > 1){
			gERROR('Unimplemented Special Case!', this.type);
		}
		
		temp = [];
		temp['id'] = this.children[this.checkQuad(newNode)].id;
		temp['node'] = newNode;
		out.push(temp);

		return out;
	}
};

FADELevel.prototype.calcMass = function() {
	var result = [];
	if(this.children.length == 0) {
		result['mass'] = 0;
		result['x'] = 0;
		result['y'] = 0;
		
		for(var id in this.nodes){
			result['mass'] += this.nodes[id].temp.mass;
			result.x += this.nodes[id].temp.x;
			result.y += this.nodes[id].temp.y;
		}
		if(result.mass != 0){
			result.x /= result.mass;
			result.y /= result.mass;
		}
	} else {
		result['mass'] =0;
		result['x'] = 0;
		result['y'] = 0;
		for (id in this.children){
			var temp = this.children[id].mass;
			result.mass += temp.mass;
			result.x += temp.mass * temp.x;
			result.y += temp.mass * temp.y;
		}
		result.x /= result.mass;
		result.y /= result.mass;
	}
	this.mass = result;
};

FADELevel.prototype.checkQuad = function(node) {
	var right = (node.temp.x > this.left + (this.width /2));
	var bottom = (node.temp.y > this.top + (this.height /2));
	var pos = (right ? 1 : 0) + (bottom ? 2 : 0);
	
	if(this.children[pos] == null){
		this.childCount++;
		this.children[pos] = new FADELevel(this.collection, this.level +1,
			this.left + (right ? 1 : 0) * (this.width /2),
		 	this.top + (bottom ? 1 : 0) * (this.height /2),
			this.width /2, this.height/2);
	}
	return pos;
};

FADELevel.prototype.showRect = function() {
	var svgElem = this.collection.owner.elem;
	
	var rect = document.createElementNS('http://www.w3.org/2000/svg','rect');
	rect.setAttribute('x', this.left);
	rect.setAttribute('y', this.top);
	rect.setAttribute('width', this.width);
	rect.setAttribute('height', this.height);
	
	svgElem.appendChild(rect);
	
	return rect;
};

/* End FADETrees */
/* Begin GOptions */

function GOptions () {

	// Friction co-efficient
	this.friction = 4;
	
	// Maximum force (acceleration) per timestep, any higher and it gets rounded down to this
	this.maxForce = 80;
	// Maximum speed for nodes, any higher and it gets rounded down to this
	this.maxSpeed = 60;
	/**
	 * Distance away from the reference node new nodes should be added
	 * format: {min: value1, max: value2}. null to disable.
	 */
	this.nodeAddRadius = {min: 80, max: 100};

	// ** Edge Forces **
	this.edge = [];
	// Default edge force (Hooke's law). k: scale, l: natural length of spring
	this.edge.def = {k: 0.15, l: 50};
	// Store for customised edges
	this.edge.list = [];
		
	// ** Non-Edge Forces **
	this.nonedge = [];
	// Tree distance comparison ratio
	this.nonedge.delta = 3;
	// non-edge force scale
	this.nonedge.def = 2000;
	// Maximum distance of the non-edge force calculation (-1 == disabled)
	this.nonedge.maxDist = 250;
	// Show the decomposition tree rectangles
	this.nonedge.showTree = false;
	
	this.getEdgeProperties = function(type) {
		var k = this.edge.def.k;
		var l = this.edge.def.l;
		if (this.edge.list[type] != null) {
			if(this.edge.list[type].k != null)
				k = this.edge.list[type].k;
			if(this.edge.list[type].l != null)
				l = this.edge.list[type].l;
		}
		
		return {k: k, l: l};
	};
	
	this.getNonedgeProperties = function() {
		return this.nonedge.def;
	};
	
	this.getNonedgeDelta = function() {
		return this.nonedge.delta;
	};
	
	this.getNonedgeMaxDist = function() {
		return this.nonedge.maxDist;
	};
	
	this.getFriction = function() {
		return this.friction;
	};
		
	this.getMaxForce = function() {
		return this.maxForce;
	};
	
	this.getMaxSpeed = function() {
		return this.maxSpeed;
	};
	
	this.getNodeAddRadius = function() {
		return this.nodeAddRadius;
	};
	
	return this;
}
/* End GOptions */