<!DOCTYPE html>
<html ng-app="plunker">
<head lang="en">
<meta charset="utf-8">
<title>Custom Plunker</title>
<script src="//ajax.googleapis.com/ajax/libs/angularjs/1.0.3/angular.min.js"></script>
<link href="//netdna.bootstrapcdn.com/twitter-bootstrap/2.2.0/css/bootstrap-combined.min.css" rel="stylesheet">
<link href="style.css" rel="stylesheet">
<script>
document.write('<base href="' + document.location + '" />');
</script>
<script src="app.js"></script>
<script src="topologicalSort.js"></script>
</head>
<body ng-controller="MainCtrl" class="container-fluid">
<h3>Topological Sort <a href="testRunner.html"><small>(Run unit tests)</small></a></h3>
<p><b>Instructions:</b> Enter a few elements, select each element, check their dependencies
and click on sort. The result will be one possible order where each element required
is before the elements that require it.</p>
<div class="row-fluid">
<div class="span6 well" ng-show="elements.length">
<h4>Elements</h4>
<div ng-repeat="element in elements">
<input type="radio" name="elementGroup" ng-value="element" ng-model="form.select">
{{element.name}}
</div>
</div>
<div class="span6 well" ng-show="form.select">
<h4>Dependencies</h4>
<div ng-repeat="element in elements">
<input type="checkbox" ng-value="$scope.required = form.select.require[element.name]"
ng-model="$scope.required" ng-change="requiredChanged(element.name)">
{{element.name}}
</div>
</div>
</div>
<div class="well">
<form ng-submit="add()">
<label>Add element:</label>
<input class="span6" type="text" ng-model="form.text" placeholder="enter an element (press enter to add it)" required>
</form>
<button class="btn btn-primary" ng-click="sort()">Sort elements</button>
<h4 ng-show="result">Result: </h4>
<p>{{result.error}}</p>
<ul ng-hide="result.error">
<li ng-repeat="element in result.order">{{element}}</li>
</ul>
</div>
</body>
</html>
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<title>AngularJS test</title>
<link rel="stylesheet" href="testRunnerStyle.css">
<script src="https://raw.github.com/pivotal/jasmine/master/lib/jasmine-core/jasmine.js"></script>
<script src="https://raw.github.com/pivotal/jasmine/master/lib/jasmine-core/jasmine-html.js"></script>
<script src="//ajax.googleapis.com/ajax/libs/angularjs/1.0.3/angular.min.js"></script>
<script src="http://code.angularjs.org/1.0.3/angular-mocks.js"></script>
<script src="app.js"></script>
<script src="topologicalSort.js"></script>
<script src="appSpec.js"></script>
<script src="topologicalSortSpec.js"></script>
</head>
<body>
<script>
// KICK OFF JASMINE
var jasmineEnv = jasmine.getEnv();
var trivialReporter = new jasmine.TrivialReporter();
jasmineEnv.addReporter(trivialReporter);
jasmineEnv.specFilter = function(spec) {
return trivialReporter.specFilter(spec);
};
jasmineEnv.execute();
</script>
</body>
</html>
var app = angular.module('plunker', []);
app.controller('MainCtrl', function($scope, topologicalSort) {
$scope.elements = []; // elements to sort
$scope.form = {
select: null, // selected element
text: "" // name of the element to be added
};
/**
* Add an element to elements and reset the text form
*/
$scope.add = function() {
$scope.elements.push({ name:$scope.form.text, require:{} });
$scope.form.text = "";
};
/**
* Toggle the selected element require value
* @param name of the required (or not) element
*/
$scope.requiredChanged = function(name) {
$scope.form.select.require[name] = !$scope.form.select.require[name];
};
/**
* Sort the elements and attach the result
*/
$scope.sort = function() {
$scope.result = topologicalSort($scope.elements);
};
});
app.factory('topologicalSort', function() {
var vertices, order, error;
/**
* Take an array of elements and their dependencies and sort
* them in an order where each element required is before
* the elements that require it.
* @param elements an array in the form of:
[{name:"A"},
{name:"B", require:{A:true}},
{name:"C", require:{B:true}}]
* @return the order or an error message
*/
function topologicalSort(elements) {
vertices = {}; // hash table of vertices by their name
order = []; // stack of reverse post-order vertices
error = null; // store a cycle error if it detects one
// add one vertex per element in the hash table
angular.forEach(elements, function(element) {
vertices[element.name] = {
adj: [], // will store adjacent vertices names
marked: false, // store the vertex has been visited by dfs
onStack: false // to detect cycle
};
});
// add edges between vertices
// by adding dependent vertices in adjacent list of each vertex
angular.forEach(elements, function(element) {
for (var name in element.require) {
// if required, add the vertex to the adjacent list of the required vertex
element.require[name] && vertices[name].adj.push(element.name);
}
});
// mark all vertices
angular.forEach(elements, function(element) {
// short circuit if cycle found
if (error) { return; }
// if this vertex has not been marked by precedent dfs calls, run dfs from it
vertices[element.name].marked || dfs(element.name);
});
return {error:error, order:order, vertices:vertices};
}
/**
* Depth First Search from the source
* @param source source vertex
* @private
*/
function dfs(source) {
// mark the source vertex
vertices[source].marked = true;
// set its onStack to true (to detect cycle)
vertices[source].onStack = true;
// for each vertices adjacent to it
angular.forEach(vertices[source].adj, function(v) {
// short circuit if cycle error found
if (error) { return; }
// if adjacent vertex is not marked
if (!vertices[v].marked) {
// recursively run dfs on it
dfs(v);
// if it's already onStack
} else if (vertices[v].onStack) {
// cycle found, set error
error = "Error: " + v + " can't require " + source;
}
});
// reset source vertex's onStack to false
vertices[source].onStack = false;
// add it to the order stack
order.unshift(source);
}
return topologicalSort;
});
a > small {
color: green;
}
describe('Testing main controller', function() {
var $scope, ctrl, topologicalSortMock, result;
beforeEach(module('plunker'));
beforeEach(inject(function($rootScope, $controller) {
$scope = $rootScope.$new();
// mock the topologicalSort service with a fake result
result = "fake result";
topologicalSortMock = jasmine.createSpy().andReturn(result);
ctrl = $controller('MainCtrl', {
$scope: $scope,
topologicalSort: topologicalSortMock
});
}));
it('should exist', function () {
expect(!!ctrl).toBe(true);
});
describe("controller scope", function () {
it('should attach elements as an empty array', function () {
expect($scope.elements.length).toBe(0);
});
it('should attach form.select as null', function () {
expect($scope.form.select).toBeNull();
});
it('should attach form.text as an empty string', function () {
expect($scope.form.text).toBe("");
});
});
describe("add", function () {
var elementName;
beforeEach(function () {
$scope.form.text = elementName = "element added";
$scope.add();
});
it('should add an element', function () {
expect($scope.elements.length).toBe(1);
});
it('should add an element with the text as name', function () {
expect($scope.elements[0].name).toBe(elementName);
});
it('should reset form.text as an empty string', function () {
expect($scope.form.text).toBe("");
});
});
describe("requiredChanged", function () {
it('should invert the require value of the selected element to true', function () {
$scope.form.select = {name:"an element", require:{A:false}};
$scope.requiredChanged("A");
expect($scope.form.select.require["A"]).toBeTruthy();
});
it('should invert the require value of the selected element to false', function () {
$scope.form.select = {name:"an element", require:{A:true}};
$scope.requiredChanged("A");
expect($scope.form.select.require["A"]).toBeFalsy();
});
});
describe("sort", function () {
beforeEach(function () {
var a = {name:"A thing", require:{}};
var b = {name:"B", require:{}};
b.require[a.name] = true;
$scope.elements = [a, b];
$scope.sort();
});
it('should call the topologicalSort service with elements as parameter', function () {
expect(topologicalSortMock).toHaveBeenCalledWith($scope.elements);
});
it('should attach the result of the sort', function () {
expect($scope.result).toBe(result);
});
});
});
describe('Testing topologicalSort service', function() {
var topologicalSort;
beforeEach(module('plunker'));
beforeEach(inject(function(_topologicalSort_) {
topologicalSort = _topologicalSort_;
}));
it('should exist', function () {
expect(!!topologicalSort).toBe(true);
});
describe("result of a possible topological sort", function () {
var elements, result;
beforeEach(function () {
var a = {name:"A thing", require:{}};
var b = {name:"B", require:{}};
var c = {name:"C", require:{}};
var d = {name:"D", require:{}};
var e = {name:"E", require:{}};
var f = {name:"F", require:{}};
b.require[a.name] = true;
c.require[b.name] = true;
d.require[b.name] = true;
d.require[f.name] = true;
e.require[d.name] = true;
elements = [a, b, c, d, e, f];
result = topologicalSort(elements);
});
it("should have a vertices hash table with the 6 vertices", function () {
angular.forEach(["A thing", "B", "C", "F", "D", "E"], function(v) {
expect(result.vertices[v]).toBeDefined();
});
});
it("should have the correct adjacent list for each vertice", function () {
expect(result.vertices["A thing"].adj).toContain("B");
expect(result.vertices["B"].adj).toContain("C");
expect(result.vertices["B"].adj).toContain("D");
expect(result.vertices["D"].adj).toContain("E");
expect(result.vertices["F"].adj).toContain("D");
expect(result.vertices["C"].adj.length).toBe(0);
expect(result.vertices["E"].adj.length).toBe(0);
});
it("should contains the 6 elements in order array", function () {
angular.forEach(["A thing", "B", "C", "F", "D", "E"], function(v) {
expect(result.order).toContain(v);
});
});
it("should have a correct order of elements", function () {
expect(result.order.indexOf("A thing")).toBeLessThan(result.order.indexOf("B"));
expect(result.order.indexOf("B")).toBeLessThan(result.order.indexOf("C"));
expect(result.order.indexOf("B")).toBeLessThan(result.order.indexOf("D"));
expect(result.order.indexOf("F")).toBeLessThan(result.order.indexOf("D"));
expect(result.order.indexOf("D")).toBeLessThan(result.order.indexOf("E"));
});
});
describe("result of an impossible topological sort", function () {
var elements, result;
beforeEach(function () {
var a = {name:"A thing", require:{}};
var b = {name:"B", require:{}};
var c = {name:"C", require:{}};
var d = {name:"D", require:{}};
var e = {name:"E", require:{}};
var f = {name:"F", require:{}};
b.require[a.name] = true;
c.require[b.name] = true;
d.require[b.name] = true;
d.require[f.name] = true;
e.require[d.name] = true;
a.require[d.name] = true; // cycle created
elements = [a, b, c, d, e, f];
result = topologicalSort(elements);
});
it("should have an error", function () {
expect(result.error.length).toBeGreaterThan(0);
});
});
});
body { background-color: #eeeeee; padding: 0; margin: 5px; overflow-y: scroll; }
#TrivialReporter { padding: 8px 13px; position: absolute; top: 0; bottom: 0; left: 0; right: 0; overflow-y: scroll; background-color: white; font-family: "Helvetica Neue Light", "Lucida Grande", "Calibri", "Arial", sans-serif; /*.resultMessage {*/ /*white-space: pre;*/ /*}*/ }
#TrivialReporter a:visited, #TrivialReporter a { color: #303; }
#TrivialReporter a:hover, #TrivialReporter a:active { color: blue; }
#TrivialReporter .run_spec { float: right; padding-right: 5px; font-size: .8em; text-decoration: none; }
#TrivialReporter .banner { color: #303; background-color: #fef; padding: 5px; }
#TrivialReporter .logo { float: left; font-size: 1.1em; padding-left: 5px; }
#TrivialReporter .logo .version { font-size: .6em; padding-left: 1em; }
#TrivialReporter .runner.running { background-color: yellow; }
#TrivialReporter .options { text-align: right; font-size: .8em; }
#TrivialReporter .suite { border: 1px outset gray; margin: 5px 0; padding-left: 1em; }
#TrivialReporter .suite .suite { margin: 5px; }
#TrivialReporter .suite.passed { background-color: #dfd; }
#TrivialReporter .suite.failed { background-color: #fdd; }
#TrivialReporter .spec { margin: 5px; padding-left: 1em; clear: both; }
#TrivialReporter .spec.failed, #TrivialReporter .spec.passed, #TrivialReporter .spec.skipped { padding-bottom: 5px; border: 1px solid gray; }
#TrivialReporter .spec.failed { background-color: #fbb; border-color: red; }
#TrivialReporter .spec.passed { background-color: #bfb; border-color: green; }
#TrivialReporter .spec.skipped { background-color: #bbb; }
#TrivialReporter .messages { border-left: 1px dashed gray; padding-left: 1em; padding-right: 1em; }
#TrivialReporter .passed { background-color: #cfc; display: none; }
#TrivialReporter .failed { background-color: #fbb; }
#TrivialReporter .skipped { color: #777; background-color: #eee; display: none; }
#TrivialReporter .resultMessage span.result { display: block; line-height: 2em; color: black; }
#TrivialReporter .resultMessage .mismatch { color: black; }
#TrivialReporter .stackTrace { white-space: pre; font-size: .8em; margin-left: 10px; max-height: 5em; overflow: auto; border: 1px inset red; padding: 1em; background: #eef; }
#TrivialReporter .finished-at { padding-left: 1em; font-size: .6em; }
#TrivialReporter.show-passed .passed, #TrivialReporter.show-skipped .skipped { display: block; }
#TrivialReporter #jasmine_content { position: fixed; right: 100%; }
#TrivialReporter .runner { border: 1px solid gray; display: block; margin: 5px 0; padding: 2px 0 2px 10px; }