//
// This work is licensed under the Creative Commons Attribution 2.5 License. To 
// view a copy of this license, visit
// http://creativecommons.org/licenses/by/2.5/
// or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San
// Francisco, California, 94105, USA.
//
// All copies and derivatives of this source must contain the license statement 
// above and the following attribution:
//
// Author: Kyle Scholz      http://kylescholz.com/
// Copyright: 2006
//

/**
 * FDNode:
 * 
 * Represents a node in a Force Directed Graph.
 */
var FDNode = function( id, mass, isStatic, x, y ) {

	// A unique identifier
	this['id'] = id;
	
	// The node's mass is used to dictate it's repulsive forces
	this['mass'] = mass;

	// indicates whether this node can move
	this['isStatic'] = isStatic;

	// indicates that this nodes is selected
	this['selected'] = false;

	// current Position
	this['position'] = new Object();
	this['position']['x'] = x;
	this['position']['y'] = y;

	// forces on this node
	this['force'] = new Object();
	this['force']['x'] = 0;
	this['force']['y'] = 0;

	// edges
	// TODO: Remove one of these ... "edges" was added for compatibility
	this['edgeNodes'] = {};
	this['edges'] = new Array();

	/*
	 * Adds an edge between this node and another. 
	 */	
	this['addEdge'] = function( node, weight ) {
		this['edgeNodes'][node.id]=weight;
		this['edges'].push(node);
	}
};

/**
 * Distance:
 * 
 * Calculates distance in for vectors and 2D space.
 */
var Distance = function( pointA, pointB ) {;
	// X Distance
	this['dx'] = pointA['x'] - pointB['x'];
	// Y Distance
	this['dy'] = pointA['y'] - pointB['y'];
	this['d2'] = (this['dx']*this['dx']+this['dy']*this['dy']);
	// Distance
	this['d'] = Math.sqrt(this['d2']);
}

/**
 * FDGraphModel:
 * 
 * Performs positioning on nodes.
 * 
 * @extends GraphModel
 */
var FDGraphModel = function( frameWidth, frameHeight ) {
	this.initialize( frameWidth, frameHeight );	
}
FDGraphModel.prototype = {

	// A collection of GraphModelListeners that want to receive updates from this graph
	subscribers: new Array(),
	
	// A collection  of root nodes
	updateQueue: new Array(),
	
	//
	nextUID: 0,
	
	/*
	 * Initialize this instance.
	 * 
	 * @overrides GraphModel.initialize
	 */
	initialize: function( frameWidth, frameHeight ) {
		this['frameWidth']=frameWidth;
		this['frameHeight']=frameHeight;

	    // A "speed" multiple applied to all of the forces in each iteration
	    // (a higher number makes the graph move faster but also makes it more volatile)
	    this['speed'] = 8;

	    // Actually an _inverse_ gravity constant, used in calculating repulsive force
	    this['gravity']=96;

	    // The maximum repulsive distance over which a repulsive force can effect
	    this['maxRepulsiveForceDistance']=300;

		//
	    this['maxDistancePerIteration']=40;

		this['entropy_deviation']=.01;

		// A factor that skews the forces on the graph relative to the dimenions
		// of the enclosing frame.
		this['skew'] = frameWidth/frameHeight;
	},

	/*
	 * Graph is a TimerControl Listener. This is the function the TimerControl event
	 * handler calls
	 */
	update: function() {
		var entropy = this.applyForce();

		for( var i=0; i<this['updateQueue'].length; i++ ) {
			// Tell subscribers to draw nodes.
			for( var j=0; j<this['subscribers'].length; j++ ) {
				this['subscribers'][j].drawNode( this['updateQueue'][i] );
			}
		}

		if ( entropy < this['entropy_deviation'] && entropy > (-1)*this['entropy_deviation'] ) {
			return 0;
		} else {
			return 2;
		}
	},

	/*
	 * Apply an attractive force between two nodes
	 */
	attractiveForce: function( nodeI, nodeJ, distance ) {
		//   F = (currentLength - desiredLength)
		weight = nodeI['edgeNodes'][nodeJ.id];
		
		// cheesy multiplier to make edge lengths longer as you add neighbors
		weight += nodeI['edges'].length;

		if ( weight ) {
			var attractive_force = (distance['d'] - weight)/weight;

			if ( !nodeI['selected'] ) {
				nodeI['force']['x'] -= attractive_force * distance['dx'] / distance['d'];
				nodeI['force']['y'] -= attractive_force * distance['dy'] / distance['d'];
			}

			// since edges are one way in our data structure, we need to explicitly add
			// an equal attractive force to our neighbor
			if ( !nodeJ['selected'] ) {
				nodeJ['force']['x'] += attractive_force * distance['dx'] / distance['d'];
				nodeJ['force']['y'] += attractive_force * distance['dy'] / distance['d'];
			}
		}
	},

	/*
	 * Apply a repulsive force between two nodes
	 */
	repulsiveForce: function( nodeI, nodeJ, distance ) {
		//   force = gravity*(mass1*mass2)/distance^2.
		var repulsive_force=this['gravity']*nodeI['mass']*nodeJ['mass']/distance['d2'];

		nodeI['force']['x'] += (repulsive_force * distance['dx'] / distance['d'])*this['skew'];
		nodeI['force']['y'] += repulsive_force * distance['dy'] / distance['d'];
	},

	lastVariance: 100,
	
	/*
	 * Iterate through all of the nodes, calculating applicable forces, then apply
	 * to the node's position
	 */
	applyForce: function() {

		// Values used to calculate variance.
		var sumForce = 0;
		var sumForce2 = 0;

		// Reposition nodes
		for( var i=0; i<this['updateQueue'].length; i++ ) {
			var nodeI = this['updateQueue'][i];

			for( var j=0; j<this['updateQueue'].length; j++ ) {
				var nodeJ = this['updateQueue'][j];
				if ( i != j ) {

					// Get the distance between nodes
					var distance = new Distance( nodeI.position, nodeJ.position );
					if( distance['d']==0 ) {
						if ( Math.random()<0.5 ) { distance['dx']=-1; } else { distance['dx']=1; }
						if ( Math.random()<0.5 ) { distance['dy']=-1; } else { distance['dy']=1; }
						distance['d']=1;
						distance['d2']=1;
					}
					
					// Attractive force applied across an edge
					if ( nodeJ.id in nodeI['edgeNodes'] ) {
						this.attractiveForce(nodeI, nodeJ, distance);
					}

					// Repulsive force between any two nodes
					if ( !nodeI.isStatic && !nodeI['selected'] && 
						distance['d'] <= this.maxRepulsiveForceDistance ) {
						this.repulsiveForce(nodeI, nodeJ, distance);
					}
				}
			}

			if ( !nodeI.isStatic ) {

				// Speed multiple
				nodeI['force']['x']*=this['speed'];
				nodeI['force']['y']*=this['speed'];

				// Control the maximum distance travelled in an iteration
				var force2=nodeI['force']['x']*nodeI['force']['x']+nodeI['force']['y']*nodeI['force']['y'];
				var force = Math.sqrt(force2);
				sumForce+=force;
				sumForce2+=force2;
				if ( force > this['maxDistancePerIteration'] ||
    				force < this['maxDistancePerIteration']*(-1) ) {
					nodeI['force']['x'] = this['maxDistancePerIteration'] * nodeI['force']['x'] / force;
					nodeI['force']['y'] = this['maxDistancePerIteration'] * nodeI['force']['y'] / force;	
				}
				
				// Add forces to node position
				nodeI['position']['x'] += nodeI['force']['x'];
				nodeI['position']['y'] += nodeI['force']['y'];

				// Wipe forces for iteration
				nodeI['force']['x']=0;
				nodeI['force']['y']=0;

				// Keep the node in our frame
				this.bounds(nodeI);
			}

		} // for
		var variance = (sumForce2-(sumForce*sumForce)/this['updateQueue']['length'])/this['updateQueue']['length'];
		var diff = this['lastVariance'] - variance;

		this['lastVariance'] = variance;
		return diff;
	},

	/*
	 * Force a node to stay in bounds
	 * 
	 * TODO: Get a value for r for a node ... This currently only keeps only
	 *   middle in bounds.
	 */
	bounds: function( node ) {
		var r = 0;
		var cxl = node['position']['x'];
		var cxm = node['position']['x'] + r;
		var cyl = node['position']['y'];
		var cym = node['position']['y'] + r;

		if ( cxl < 0 ) { node['position']['x']  = 0; }
		if ( cyl < 0 ) { node['position']['y']  = 0; }

		if ( cxm > this['frameWidth'] ) { node['position']['x']  = this['frameWidth'] - r; }
		if ( cym > this['frameHeight'] ) { node['position']['y']  = this['frameHeight'] - r; }
	},

	/*
	 * Add an edge to the graph
	 */
	addEdge: function( node1, node2, weight ) {
		node1.addEdge(node2, weight);
	},

	/*
	 * Add a node to the graph
	 */
	addNode: function( mass, isStatic, startX, startY ) {

		// Create the Node and add it to the collection
		var node = new FDNode( this['nextUID']++, mass, isStatic, startX, startY );
		this['updateQueue'].push(node);

		return node;
	}
}
FDGraphModel.extend(GraphModel);