app.directive('gitGraph', function() {
	return {
		restrict: 'E',
		transclude: true,
		templateUrl: 'js/directives/git-graph.html',
		link: function(scope, element, attrs) {
			scope.stages = []

			scope.num_columns = 1
			scope.row_height = 54
			scope.column_width = 16
			scope.circle_radius = 8
			scope.bridge_gap = 10
			scope.line_id_counter = 1

			scope.possible_colors = _.shuffle([
				'#FF0000',
				'#FF7F00',
				'#FFFF00',
				'#7FFF00',
				'#00FF00',
				'#00FF7F',
				'#00FFFF',
				'#007FFF',
				'#0000FF',
				'#7F00FF',
				'#FF00FF',
				'#FF007F',
			])

			scope.build_graph_stages = function(commits) {
				// for each commit
				// - inherit open parents from previous iteration
				// - position commit node based on open parents pointing to it (first wins)
				// - calculate new open parent list. remove ones pointing to commit, add parents of commit

				stages = []
				open_parents = []
				scope.num_columns = 1

				for (var i = 0; i < commits.length; i++) {
					commit = commits[i]
					commit.sort_index = i
					stage = {from: [], commit: commit, to: [], bridge: null}
					id_to_this_commit = null
					commit.line_id = null

					commit.cx = function() {
						return (this.column * scope.column_width) + scope.column_width / 2
					}
					commit.cy = function() {
						return (this.sort_index * scope.row_height) + scope.row_height / 2
					}
					
					if (open_parents.length > 0) {
						// place commit in same column as first open parent pointing to it
						for (var j = 0; j < open_parents.length; j++) {
							stage.from[j] = open_parents[j]
							if (open_parents[j].sha == stage.commit.sha) {
								if (stage.commit.column == null) {
									stage.commit.column = j
								}
								if (id_to_this_commit == null) {
									id_to_this_commit = open_parents[j].id
									if (stage.commit.line_id == null) {
										stage.commit.line_id = id_to_this_commit
									}
								}
								open_parents[j] = null
							}
						};
						if (stage.commit.column == null) {
							// add dot to end, tip of branch
							last_filled_column = 0
							for (var j = 0; j < open_parents.length; j++) {
								if (open_parents[j] != null) {
									last_filled_column = j
								}
							};
							stage.commit.column = last_filled_column + 1
						}
					} else {
						stage.commit.column = 0
					}

					stage.to = open_parents.slice(0)

					if (commit.parents != null) {
						for (var j = 0; j < commit.parents.length; j++) {
							parent = commit.parents[j]

							// if we have 2 parents, and the 2nd one is already a "to",
							// we can create a bridge across the stage to it instead of adding a column
							if (j > 0) {
								existing_index = scope.find_sha(stage.to, parent.sha)
								if (existing_index != -1) {
									stage.bridge = {sha: parent.sha, id: stage.to[existing_index].id}
								} else {
									scope.claim_leftmost(stage.to, parent.sha, scope.line_id_counter++)
								}	
							} else {
								used_id = scope.claim_leftmost(stage.to, parent.sha, id_to_this_commit)
								if (stage.commit.line_id == null) {
									stage.commit.line_id = used_id
								}
							}
						}
					}

					// remove gaps before iterating
					stage.to = stage.to.filter(function(e) { return e != null })

					open_parents = stage.to.slice(0)

					if (stage.to.length + 1 > scope.num_columns) {
						scope.num_columns = stage.to.length
					}

					stages.push(stage)
				};

				return stages
			}

			scope.claim_leftmost = function(list, sha, id) {
				if (id == null) {
					id = scope.line_id_counter++
				}
				for (var i = 0; i < list.length; i++) {
					if (list[i] == null) {
						list[i] = {sha: sha, id: id}
						return
					}
				};

				list.push({sha: sha, id: id})

				return id
			}

			scope.find_sha = function(list, sha) {
				for (var i = 0; i < list.length; i++) {
					if (list[i] != null && list[i].sha == sha) {
						return i
					}
				};

				return -1
			}

			scope.apply_lines = function(stages) {
				// calculate line bridged across a stage, from a commit
				function bridge(stage) {
					if (stage.bridge) {
						index = scope.find_sha(stage.to, stage.bridge.sha)

						if (index != -1) {
							stage.lines.push({
								x1: stage.commit.cx(), 
								y1: stage.commit.cy(),
								x2: (index * scope.column_width) + scope.column_width / 2,
								y2: stage.commit.cy() + (scope.row_height / 2) - scope.bridge_gap,
								id: stage.bridge.id
							})
						}
					}
				}

				// calculate lines passing through a stage, returning unassigned "to" targets for use later
				function passthrough(stage) {
					leftover_to = stage.to.slice(0)

					for (var from_index = 0; from_index < stage.from.length; from_index++) {
						from_sha = stage.from[from_index]
						for (var to_index = 0; to_index < leftover_to.length; to_index++) {
							if (leftover_to[to_index] != null) {
								to_sha = leftover_to[to_index]

								// if we find a match that isn't underneath a dot, create a line
								if (from_sha.sha == to_sha.sha && to_index != stage.commit.column) {
									stage.lines.push({
										x1: (from_index * scope.column_width) + scope.column_width / 2,
										y1: stage.commit.cy() - scope.row_height / 2,
										x2: (to_index * scope.column_width) + scope.column_width / 2,
										y2: stage.commit.cy() + scope.row_height / 2,
										id: from_sha.id
									})

									// null out "used" to_sha, so that when calculating from_commit we don't reuse it
									leftover_to[to_index] = null
									break
								}
							}
						};
					};

					return leftover_to
				}

				function to_commit(stage) {
					// draw "from" lines to commit
					stage.from.forEach(function(from_sha, index) {
						if (from_sha.sha == stage.commit.sha) {
							stage.lines.push({
								x1: (index * scope.column_width) + scope.column_width / 2,
								y1: stage.commit.cy() - scope.row_height / 2,
								x2: stage.commit.cx(),
								y2: stage.commit.cy(),
								id: from_sha.id
							})
						}
					})
				}

				function from_commit(stage, leftover_to) {
					// draw "to" lines from commit
					if (stage.commit.parents != null) {
						stage.commit.parents.forEach(function(parent) {
							leftover_to.forEach(function(to_sha, index) {
								if (to_sha != null && parent.sha == to_sha.sha) {
									stage.lines.push({
										x1: stage.commit.cx(), 
										y1: stage.commit.cy(),
										x2: (index * scope.column_width) + scope.column_width / 2,
										y2: stage.commit.cy() + scope.row_height / 2,
										id: to_sha.id
									})
								}
							})
						})
					}
				}

				stages.forEach(function(stage) {
					stage.lines = []

					bridge(stage)
					leftover_to = passthrough(stage)
					to_commit(stage)
					from_commit(stage, leftover_to)
				})

				return stages
			}

			scope.graph_style = function() {
				return {
					float: "left",
					clear: "left",
					height: scope.stages.length * scope.row_height + "px",
					width: scope.num_columns * scope.column_width + "px"
				}
			}

			scope.commit_style = function(commit) {
				return {
					position: "absolute",
					top: (commit.cy() - (scope.row_height / 2)) + "px",
					left: (scope.num_columns * scope.column_width) + 20 + "px",
					"max-height": scope.row_height + "px",
					"height": scope.row_height + "px",
					"width": "100%",
					"border": "1px solid #c5d5dd",
					"padding": "8px 8px 8px 52px"
				}
			}

			scope.line_color = function(line_id) {
				return scope.possible_colors[line_id % scope.possible_colors.length]
			}

			scope.$watch('shown_commits', function() {
				if (scope.shown_commits.length > 0) {
					stages = scope.build_graph_stages(scope.shown_commits)
					scope.stages = scope.apply_lines(stages)	
				}
			})
		}
	}
})