module('apps.GraphLayout').requires('lively.Widgets').toRun(function() {

Object.extend(apps.GraphLayout, {
	documentation: 'The GraphLayout module was developed by Arian Treffer as part of his cource work in Software Design 2010/ 2011 at the HPI.'

});


Object.subclass('MyRandom', { 

	initialize: function(s) {
		return this.setSeed(s);
	},

	setSeed: function(s) { 
		if (!s) {
			var d = new Date();
			this.seed = 2345678901 + (d.getSeconds() * 0xFFFFFF) + (d.getMinutes() * 0xFFFF);
		} else {
			this.seed = s;
		}
		this.A = 48271;
		this.M = 2147483647;
		this.Q = this.M / this.A;
		this.R = this.M % this.A;
		this.oneOverM = 1.0 / this.M;
		return this;
	},

	nextValue: function() {
		var hi = this.seed / this.Q;
		var lo = this.seed % this.Q;
		var test = this.A * lo - this.R * hi;
		if(test > 0){
			this.seed = test;
		} else {
	 		this.seed = test + this.M;
		}
		return (this.seed * this.oneOverM);
	},

	next: function(a, b) {
		if (!a) {
			// 0 <= R < 1
			return this.nextValue();
		} else if (!b) {
			// 0 <= R < a
			return this.nextValue() * a;
		} else {
			// a <= R < b
			return a + this.nextValue() * (b-a);
		}
	},

});

Object.subclass('Vertex',
'default category', {

	initialize: function(id, graph) {
		this.id = id;
		this.graph = graph;
		this.searchGuard = false;
		this.neighbors = [];
		this.edges = new Array(graph.size);
		for (var i = 0; i < graph.size; i++)
			this.edges[i] = (i == id ? 0 : 99999);
		var r = 10;
		this.v = Morph.makeCircle(new Point(0, 0), r, 1, Color.black, Color.random());
		this.v.suppressHandles = true;
		this.v.suppressGrabbing = true;
		this.v.v = this;
		this.v.addScript(function onMouseOver  () { 
			this.v.graph.vertices.each(function(v) { 
				v.hideAdjustments();
			});
			this.v.showAdjustments(); 
		});
		this.e = [];
		this.a = [];
		this.visible = false;
		this.location = new Point(0, 0);
		this.center = new Point(r, r);
	},

	connect: function(other) {
		if (this.edges[other.id] < 2) {
			return false;	
		}
		//alert(this.id + " ---> " + other.id);
		this.edges[other.id] = 1;
		other.edges[this.id] = 1;
		this.neighbors.push(other);
		other.neighbors.push(this);
		return true;
	},

	distance: function(other) {
		var d = this.edges[other.id];
		if (d == 99999) {
			d = this.search(other);
			if (d == 99999) {
				this.connect(other);
				return 1;
			} else {
				this.edges[other.id] = d;
			}
		}
		return d;
	},

	actualDistance: function(other) {
		return this.location.dist(other.location);
	},

	search: function(other) {
		var d = this.edges[other.id];
		if (d < 99999) return d;
		if (this.searchGuard) return 99999;

		this.searchGuard = true;
		for (var i = 0; i < this.neighbors.length; i++) {
			var d2 = this.neighbors[i].search(other)+1;
			//alert(this.id + " - " + this.neighbors[i].id + " - " + other.id + ": " + d2);
			if (d2 < d) d = d2;
		}
		this.searchGuard = false;
		return d;
	},

	visNeighborID: function(n) {
		var id = 0;
		for (var i = 0; i < this.neighbors.length; i++) {
			if (this.neighbors[i] == n) return id;
			if (this.neighbors[i].visible) id++;
		}
		return -1;
	},

	applyAdjustments: function() {
		var adjs = this.adjustments || [];
		var w = 0;
		adjs.each(function(a) { w += a.weight });
		w = w / this.temp;
		for (var i = 0; i < adjs.length; i++) {
			var a = adjs[i];
			var delta = new Point(a.dx*a.weight/w, a.dy*a.weight/w);
			this.location = this.location.addPt(delta);
		}
	},

	hideAdjustments: function() {
		this.a.each(function(a){ a.remove() });
		this.a = [];
	},

	showAdjustments: function() {
		var adjs = this.adjustments;
		var w = 1 / adjs.length;
		var loc = this.location;
		for (var i = 0; i < adjs.length; i++) {
			var a = adjs[i];
			var delta = new Point(a.dx*a.weight*w, a.dy*a.weight*w);
			loc = loc.addPt(delta);

			var target = new Point(a.dx, a.dy).scaleBy(a.m || 2).addPt(this.location);
			var c = Morph.makeLine([this.location, target], 5*a.weight, a.other.v.getFill());
			c.ignoreEvents();

			this.a.push(c);
			this.graph.container.addMorph(c);		
		}	
	},

	update: function() {
		this.hideAdjustments();
		this.v.remove();
		this.e.each(function(e){e.remove()});
		this.e = [];
		if (this.visible) {
			var self = this;
			this.neighbors.each(function(n) {
				if (n.visible && n.id > self.id) {
					var l = Morph.makeLine([self.location, n.location], 1, Color.black);
					l.ignoreEvents()
					self.e.push(l);
					self.graph.container.addMorph(l);
				}
			});
			this.v.setPosition(this.location.subPt(this.center));
			this.graph.container.addMorph(this.v);
		}
	},

});

Object.subclass('Graph', {

	initialize: function(container, size) {
		this.size = size;
		this.container = container;
		container.submorphs.clone().each(function(m){m.remove()});
		if (this.container.graph) this.container.graph.clear();
		this.vertices = [];
		for (var i = 0; i < size; i++) {
			this.vertices.push(new Vertex(i, this));
		}
	},

	connect: function(a, b) {
		var r = this.vertices[a].connect(this.vertices[b]);
		return r;
	},

});

Object.subclass('GraphFactory', {

	initialize: function(seed) {
		this.seed = seed;
	},

	emptyGraph: function(size) {
		var c = $morph('GraphContainer');
		var g = new Graph(c, size);
		g.seed = this.seed;
		return g;
	},

	dense: function(size, rate) {
		var rnd = new MyRandom(this.seed);
		var g = this.emptyGraph(size, rnd);
		for (var i = 0; i < size; i++)
			for (var j = 0; j < size; j++)
				if (rnd.next() <= rate/2) g.connect(i, j);
		return this.ensureConnected(g);
	},

	sparse: function(size, con) {
		var rnd = new MyRandom(this.seed);
		var g = this.emptyGraph(size, rnd);
		var rate = con / size;
		if (rate < 0.01) rate = 0.01;
		if (rate > 0.99) rate = 0.99;
		for (var i = 0; i < size; i++)
			for (var j = 0; j < size; j++)
				if (rnd.next() <= rate/2) g.connect(i, j);
		return this.ensureConnected(g);
	},

	ensureConnected: function(graph) {
		for (var i = 0; i < graph.size-1; i++)
			graph.vertices[i].distance(graph.vertices[i+1]);
		return graph;
	},

});
 
Object.subclass('GraphLayout', {

	initialize: function(graph) {
		this.graph = graph;
		this.lastStep = 999999;

		this.statusMorph = $morph('StatusText');

		this.slider = $morph('ProgressSlider');
		disconnectAll(this.slider);
		this.slider.valueScale = this.stepCount();
		connect(this.slider, 'value', this, 'arrange');
		this.slider.setValue(0);
	},

	stepCount: function() {
		return 0;
	},

	arrange: function(step) {
		step = Math.round(step);
		if (step == this.lastStep) return;

		if (step < this.lastStep) {
			if (step > 0 && (this.lastStep - step) < 15) return;
			this.lastStep = 0;
			this.initArrange();
		}
		for (var i = this.lastStep; i < step+1; i++) {
			this.arrangeStep(i);
		}
		this.lastStep = step;
		this.graph.container.submorphs.clone().each(function(s){s.remove()});
		for (var i = 0; i < this.graph.size; i++) {
			this.graph.vertices[i].update();
		}

		this.statusMorph.setTextString(this.getStatus());
	},

	getStatus: function() {
		return "step: " + this.lastStep;
	},

	randomLayout: function() {
		var width = this.graph.container.shape._width;
		var height = this.graph.container.shape._height;
		var rnd = new MyRandom(this.graph.seed);
		for (var i = 0; i < this.graph.size; i++) {
			this.graph.vertices[i].location = new Point(rnd.next(50, width), rnd.next(50, height));
			this.graph.vertices[i].visible = true;
		}
	},

});

GraphLayout.subclass('Eades',
'default category', {

	initialize: function($super, g, k1, k2, k3) {
		this.k1 = k1 || 1;
		this.k2 = k2 || g.vertices[0].v.bounds().width * 2;
		this.k3 = k3 || this.k2 * this.k2 * 3;
		this.vertices = g.vertices;
		$super(g);
	},

	stepCount: function() {
		return 500;
	},

	initArrange: function() {
		this.randomLayout();
	},

	arrangeStep: function(step) {
		for (var i = 0; i < this.vertices.length; i++) {
			this.vertices[i].applyAdjustments();
		}
		for (var i = 0; i < this.vertices.length; i++) {
			this.collectAdjustments(this.vertices[i]);
		}
	},

	collectAdjustments: function(vertex) {
		vertex.adjustments = [];
		for (var i = 0; i < this.vertices.length; i++) {
			var other = this.vertices[i];
			if (other != vertex && other.visible) {
		
				vertex.adjustments.push(this.createAdjustment(vertex, other));
			}
		}
		vertex.temp = vertex.adjustments.length;
	},

	createAdjustment: function(vertex, other) {
		var d = vertex.actualDistance(other);
		if (vertex.distance(other) == 1) {
			var f = this.k1 * Math.log(d/this.k2);
		} else {
			var f = - this.k3 / (d*d);
		}
		var delta = other.location.subPt(vertex.location).normalized().scaleBy(f);
		return { other: other, weight: 1, dx: delta.x, dy: delta.y, m: 50 }
	},

});
GraphLayout.subclass('FruchtermanReingold',

'default category', {

	initialize: function($super, g, k, k2) {
		this.k = k || 2.5;
		this.k2 = k || 30;
		$super(g);
	},

	stepCount: function() {
		return 500;
	},

	collectVertices: function(vertices) {
		var result = [vertices[0]];
		var contains = this.aryContains;
		for (var i = 0; i < result.length; i++) {
			result[i].neighbors.each(function(n) {
				if (! contains(result, n)) result.push(n);
			});
		}
		return result;
	},

	aryContains: function(ary, e) {
		for (var i = 0; i < ary.length; i++)
			if (ary[i] == e) return true;
		return false;
	},

	initArrange: function() {
		this.center = this.graph.container.bounds().center().subPt(this.graph.container.bounds().topLeft());
		this.rnd = new MyRandom(this.graph.seed);
		this.vertices = this.collectVertices(this.graph.vertices);
		this.vertices.each(function(v){
			v.visible = false;
			v.adjustments = [];
			v.location = new Point(0,0);
		});
		this.lastInsert = -1;
	},

	arrangeStep: function(step) {
		this.insertVertex(step);
		for (var i = 0; i < this.vertices.length; i++) {
			this.vertices[i].applyAdjustments();
		}
		for (var i = 0; i < this.vertices.length; i++) {
			this.collectAdjustments(this.vertices[i]);
		}
	},

	insertVertex: function(i) {
		i = Math.floor((i + 4) / 5);
		if (i >= this.vertices.length || i == this.lastInsert) return;
		this.lastInsert = i;
		var l = new Point(0,0);
		var k = 0;
		var rnd = this.rnd;
		this.vertices[i].neighbors.each(function(n) {
			if (n.visible) {
				l = l.addPt(n.location);
				k++;
			}
		});

		if (k < 1) {
			l = this.center;
		} else if (k == 1) {
				var a = rnd.next() * 3.1415 * 2;
				var p = new Point(Math.sin(a), Math.cos(a));
			l = l.addPt(p.scaleBy(50));
		} else {
			 l = l.scaleBy(1/k);
		}

		this.vertices[i].visible = true;
		this.vertices[i].location = l;
	},

	collectAdjustments: function(vertex) {
		vertex.adjustments = [];
		if (! vertex.visible) return;
		for (var i = 0; i < this.vertices.length; i++) {
			var other = this.vertices[i];
			if (other != vertex && other.visible) {
		
				vertex.adjustments.push(this.createAdjustment(vertex, other));
			}
		}
		vertex.temp = vertex.adjustments.length;
	},

	createAdjustment: function(vertex, other) {
		var d = vertex.actualDistance(other) / this.k2;
		if (vertex.distance(other) == 1) {
			var f = (d*d) / this.k
		} else {
			var f = - this.k * this.k / d;
		}
		var delta = other.location.subPt(vertex.location).normalized().scaleBy(f);
		return { other: other, weight: 1, dx: delta.x, dy: delta.y, m: 50 }
	},

});
GraphLayout.subclass('DavidsonHarel',
'default category', {

	initialize: function($super, g, config) {
		if (! config) config = {};
		this.itPerTemp = config.itPerTemp || config.k1 || g.size * 20;
		this.itPerStep = config.itPerStep || this.itPerTemp;
		this.initTemp = config.initTemp || config.k2 || 1;
		this.cooling = config.cooling || config.k3 || 0.85;
		this.fineTuningTemp = config.fineTuningTemp || Math.pow(this.cooling, 10) * this.initTemp;
		
		this.eCrossing = config.crossingEnergy || 20000;
		this.eEdge = config.edgeEnergy || 0.9;
		this.eNode = config.nodeEnergy || 100;
		this.eBorder = config.borderEnergy || 200;
		this.eNodeEdge = config.nodeEdgeEnergy || 10;

		this.vertices = g.vertices;

		this.edges = [];
		for (var i = 0; i < this.vertices.length; i++) {
			for (var j = i+1; j < this.vertices.length; j++) {
				if (this.vertices[i].distance(this.vertices[j]) == 1) {
					this.edges.push([this.vertices[i], this.vertices[j]]);
				}
			}
		}

		var b = g.container.bounds();
		this.center = new Point(b.width, b.height).scaleBy(0.5);
		this.normalSize = this.center.x * this.center.y * 2;
		this.width = g.container.bounds().width;
		this.height = g.container.bounds().height;

		$super(g);
	},

	stepCount: function() {
		return 100;
	},

	initArrange: function() {
		this.randomLayout();
		this.rnd = new MyRandom(this.graph.seed + 11231290);
		this.t = this.initTemp;
		this.tIt = 0;
		this.fineTuning = false;
		this.e = this.calcEnergy();
	},

	getStatus: function($super) {
		return $super() + 
					"; energy: " + (Math.round(this.e)) +
					"; temperature: " + (Math.round(10000*this.t)/10000) + 
						" [" + (this.itPerTemp - this.tIt) + "]" +
					(this.fineTuning ? "; fine-tuning " + this.fineTuningStage :"");
	},

	arrangeStep: function(step) {
		var returnAfter = step*step / 100;
		var retry = 0;
		var succ = 0;
		for (var i = 0; i < this.itPerStep; i++) {
			this.tIt++;
			if (this.tIt > this.itPerTemp) {
				this.t = this.t * this.cooling;
				this.tIt -= this.itPerTemp
				this.fineTuning = this.t < this.fineTuningTemp;
				if (this.fineTuning) {
					if (this.fineTuningStage == 0)
						this.e = this.calcEnergy();
					this.fineTuningStage ++;
				} else {
					this.fineTuningStage = 0;
				}
			}

			if (this.arrangeIteration()) {
				succ++;
				if (succ >= returnAfter) return;
			} else {
				if (retry > 0) { retry--; i--; }
			}
		}
	},

	arrangeIteration: function() {
		this.saveConfiguration();
		this.randomModification();
		var newE = this.calcEnergy();
		if (this.acceptNewConfig(newE)) {
			this.e = newE;
			return true;
		} else {
			this.restoreConfiguration();
			return false;
		}
	},

	calcEnergy: function() {
		var e = 0;
		for (var i = 0; i < this.vertices.length; i++) {
			var v1 = this.vertices[i];
			e += this.borderEnergy(v1);
			for (var j = i+1; j < this.vertices.length; j++) {
				var v2 = this.vertices[j];
				e += this.nodeEnergy(v1, v2);
				e += this.edgeEnergy(v1, v2);
			}
			if (this.fineTuning) {
				for (var j = 0; j < this.edges.length; j++)
					e += this.nodeEdgeEnergy(v1, this.edges[j]);
			}
		}
		if (! this.fineTuning ) {
			for (var i = 0; i < this.edges.length; i++) {
				var e1 = this.edges[i];
				for (var j = i+1; j < this.edges.length; j++) {
					var e2 = this.edges[j];
					e += this.crossingEnergy(e1, e2);
				}
			}
		}
		return e;
	},

	centerEnergy: function(a) {
		var d = this.center.dist(a.location);
		return  0.1 * (d*d);
	},

	borderEnergy: function(a) {
		var l = a.location.x;
		var t = a.location.y;
		var r = this.width - a.location.x;
		var b = this.height - a.location.y;
		return this.eBorder * this.normalSize * (1/(l*l) + 1/(t*t) + 1/(r*r) + 1/(b*b));
	},

	nodeEnergy: function(a, b) {
		var d = a.actualDistance(b);
		return this.eNode * this.normalSize / (d*d);
	},

	edgeEnergy: function(a, b) {
		var expected = a.distance(b);
		if (expected != 1) return 0;
		var actual = a.actualDistance(b);
		return this.eEdge * actual * actual;
	},

	crossingEnergy: function(e1, e2) {
		if (this.edgesCrossing(
						e1[0].location, e1[1].location,
						e2[0].location, e2[1].location)) {
			return this.eCrossing;
		} else {
			return 0;
		}
	},

	edgesCrossing: function(a, b, c, d) {
		return (this.ccw(a, b, c) *
					this.ccw(a, b, d) <= 0)
			&&   (this.ccw(c, d, a) *
					this.ccw(c, d, b) <= 0);
	},

	ccw: function(a, b, p) {
		var bx = b.x - a.x;
		var by = b.y - a.y;
		var px = p.x - a.x;
		var py = p.y - a.y;
		var ccw = px * by - py * bx;
		if (ccw == 0.0) {
		    ccw = px * bx + py * by;
		    if (ccw > 0.0) {
				px -= bx;
				py -= by;
				ccw = px * bx + py * by;
				if (ccw < 0.0) {
					ccw = 0.0;
				}
		    }
		}
		return (ccw < 0.0) ? -1 : ((ccw > 0.0) ? 1 : 0);
	},

	nodeEdgeEnergy: function(v, edge) {
		var e = 0;
		if (edge[0] != v && edge[1] != v) {
			var d = this.vertexEdgeDistance(v.location, [edge[0].location, edge[1].location]);
			d = Math.max(0.001, d);
			e += this.eNodeEdge * this.normalSize / (d*d);
		}
		return e;
	},

	vertexEdgeDistance: function(p, e) {
		var ab = e[1].subPt(e[0]);
		var t = ab.scaleBy(1/ab.r());
		var n = new Point(-t.y, t.x);
		var ap = p.subPt(e[0]);
	    return Math.abs(ap.x*n.x+ap.y*n.y);
	},

	randomModification: function() {
		var retry = 10;
		for (var r = 0; r < retry; r++) {
			var v = Math.floor(this.rnd.next() * this.vertices.length);
			v = this.vertices[v];

			var a = this.rnd.next() * 3.1415 * 2;
			var p = new Point(Math.sin(a), Math.cos(a));
			p = p.scaleBy(this.center.r()).scaleBy(this.t * this.t);
			var l = v.location.addPt(p);
			if (l.x > 0 && l.y > 0 && l.x < this.width && l.y < this.height) {
				v.location = l;
				return;
			} 
		}
	},

	acceptNewConfig: function(newE) {
		if (newE < this.e) return true;
		if (this.fineTuning) return false;
		var r = this.rnd.next();
		var threshold = Math.pow(2.718, (this.e - newE) / (this.t * this.normalSize / 10))
		return r < threshold;
	},

	saveConfiguration: function() {
		this.vertices.each(function(v) {
			v.loc2 = v.location;
		});
	},

	restoreConfiguration: function() {
		this.vertices.each(function(v) {
			v.location = v.loc2;
		});
	},

});


}) // end of module