This is an automated email from the git hooks/post-receive script. New commit to branch develop in repository coselmar. See http://git.codelutin.com/coselmar.git commit 24a8cdaf9041ab81b16963ea2d3ef19030f2fdb4 Author: Yannick Martel <martel@©odelutin.com> Date: Mon Jan 11 18:53:34 2016 +0100 refs-80 #7894 prepare add first draw of hierarchy graph --- coselmar-ui/pom.xml | 6 + .../src/main/webapp/css/d3-collapsible-tree.css | 109 + coselmar-ui/src/main/webapp/index.html | 3 + .../src/main/webapp/js/coselmar-controllers.js | 15 + .../src/main/webapp/js/d3-2waytree-graph.js | 420 ++++ coselmar-ui/src/main/webapp/js/d3.layout.js | 2123 ++++++++++++++++++++ .../webapp/views/questions/modalHierarchy.html | 24 +- pom.xml | 8 + 8 files changed, 2692 insertions(+), 16 deletions(-) diff --git a/coselmar-ui/pom.xml b/coselmar-ui/pom.xml index 59d45c4..0c2069f 100644 --- a/coselmar-ui/pom.xml +++ b/coselmar-ui/pom.xml @@ -105,6 +105,12 @@ <scope>runtime</scope> </dependency> + <dependency> + <groupId>org.webjars</groupId> + <artifactId>d3js</artifactId> + <scope>runtime</scope> + </dependency> + </dependencies> <build> diff --git a/coselmar-ui/src/main/webapp/css/d3-collapsible-tree.css b/coselmar-ui/src/main/webapp/css/d3-collapsible-tree.css new file mode 100644 index 0000000..ff67aeb --- /dev/null +++ b/coselmar-ui/src/main/webapp/css/d3-collapsible-tree.css @@ -0,0 +1,109 @@ +/** +* Get from https://github.com/kanesee/d3-2way-tree and modified for our case +**/ + +body { + overflow: hidden; + margin: 0; + font-size: 14px; + font-family: "Helvetica Neue", Helvetica; +} + +#chart, #header, #footer { + position: absolute; + top: 0; +} + +#header, #footer { + z-index: 1; + display: block; + font-size: 36px; + font-weight: 300; + text-shadow: 0 1px 0 #fff; +} + +#header.inverted, #footer.inverted { + color: #fff; + text-shadow: 0 1px 4px #000; +} + +#header { + top: 80px; + left: 140px; + width: 1000px; +} + +#footer { + top: 680px; + right: 140px; + text-align: right; +} + +rect { + fill: none; + pointer-events: all; +} + +pre { + font-size: 18px; +} + +line { + stroke: #000; + stroke-width: 1.5px; +} + +.string, .regexp { + color: #f39; +} + +.keyword { + color: #00c; +} + +.comment { + color: #777; + font-style: oblique; +} + +.number { + color: #369; +} + +.class, .special { + color: #1181B8; +} + +a:link, a:visited { + color: #000; + text-decoration: none; +} + +a:hover { + color: #666; +} + +.hint { + position: absolute; + right: 0; + width: 1280px; + font-size: 12px; + color: #999; +} + + .node circle { + cursor: pointer; + fill: #fff; + stroke: steelblue; + stroke-width: 1.5px; + } + + .node text { + font-size: 11px; + } + + path.link { + fill: none; + stroke: #ccc; + stroke-width: 1.5px; + } \ No newline at end of file diff --git a/coselmar-ui/src/main/webapp/index.html b/coselmar-ui/src/main/webapp/index.html index d4b6fd7..08fe120 100644 --- a/coselmar-ui/src/main/webapp/index.html +++ b/coselmar-ui/src/main/webapp/index.html @@ -53,6 +53,7 @@ <script src="webjars/angular-ui-bootstrap/0.14.3/ui-bootstrap-tpls.js"></script> <script src="webjars/jqcloud2/2.0.1/dist/jqcloud.js"></script> <script src="webjars/angular-jqcloud/1.0.2/angular-jqcloud.js"></script> + <script src="webjars/d3js/3.5.12/d3.js"></script> <script src="js/angular-jwt.js"></script> @@ -68,6 +69,8 @@ <script src="js/coselmar-questions-services.js"></script> <script src="js/coselmar-admin-services.js"></script> <script src="js/coselmar-error-services.js"></script> + <script src="js/d3-2waytree-graph.js"></script> + <script src="js/d3.layout.js"></script> </head> <body> diff --git a/coselmar-ui/src/main/webapp/js/coselmar-controllers.js b/coselmar-ui/src/main/webapp/js/coselmar-controllers.js index c007ce9..d830f2e 100644 --- a/coselmar-ui/src/main/webapp/js/coselmar-controllers.js +++ b/coselmar-ui/src/main/webapp/js/coselmar-controllers.js @@ -1627,6 +1627,17 @@ coselmarControllers.controller('ModalQuestionHierarchyCtrl', function ($scope, $ $scope.descendants = []; $scope.hierarchyTree = { name : $scope.question.title, parents : [], children : [] }; + $scope.ancestorsReady = false; + $scope.descendantsReady = false; + + var loadHierarchy = function() { + if ($scope.ancestorsReady && $scope.descendantsReady) { + var tree = CollapsibleTree("#questionHierarchy"); + tree.init($scope.hierarchyTree); + $scope.ancestorsReady = false; + $scope.descendantsReady = false; + } + } $scope.loadAncestors = function() { var searchParams = { questionId : $scope.question.id, depth: $scope.depth}; @@ -1641,6 +1652,8 @@ coselmarControllers.controller('ModalQuestionHierarchyCtrl', function ($scope, $ } this.push(parent); }, $scope.hierarchyTree.parents); + $scope.ancestorsReady = true; + loadHierarchy(); }); }; @@ -1657,6 +1670,8 @@ coselmarControllers.controller('ModalQuestionHierarchyCtrl', function ($scope, $ } this.push(child); }, $scope.hierarchyTree.children); + $scope.descendantsReady = true; + loadHierarchy(); }); }; diff --git a/coselmar-ui/src/main/webapp/js/d3-2waytree-graph.js b/coselmar-ui/src/main/webapp/js/d3-2waytree-graph.js new file mode 100644 index 0000000..56e44e0 --- /dev/null +++ b/coselmar-ui/src/main/webapp/js/d3-2waytree-graph.js @@ -0,0 +1,420 @@ +/** +* Get from https://github.com/kanesee/d3-2way-tree and modified for our case +**/ +var CollapsibleTree = function(elt) { + + var m = [20, 120, 20, 120], + w = 1280 - m[1] - m[3], + h = 580 - m[0] - m[2], + i = 0, + root, + root2; + + var tree = d3.layout.tree().size([w, h]); + + var parentdiagonal = d3.svg.diagonal() + .projection(function(d) { return [d.x, -d.y]; }); + + var childdiagonal = d3.svg.diagonal() + .projection(function(d) { return [d.x, d.y]; }); + + var vis = d3.select(elt).append("svg:svg") + .attr("width", w + m[1] + m[3]) + .attr("height", h + m[0] + m[2]) + .append("svg:g") + // .attr("transform", "translate(" + m[3] + "," + m[0] + ")"); // left-right + // .attr("transform", "translate(" + m[0] + "," + m[3] + ")"); // top-bottom + .attr("transform", "translate(0,"+h/2+")"); // bidirectional-tree + + + var that = { + init: function(data) { + var that = this; + root = data; + + // root.x0 = h / 2; + // root.y0 = 0; + root.x0 = w / 2; + root.y0 = h / 2; + + // Initialize the display all to show a few nodes. + root.children.forEach(that.toggleAll); + // To display some nodes, for example : + // that.toggle(root.children[1]); + // that.toggle(root.children[2].children[1]); + + that.updateBoth(root); + // Or to update part by part + // that.updateParents(root); + // that.updateChildren(root); + }, + + updateBoth: function(source) { + var duration = d3.event && d3.event.altKey ? 5000 : 500; + + // Compute the new tree layout. + var nodes = tree.nodes(root).reverse(); + + // Normalize for fixed-depth. + nodes.forEach(function(d) { d.y = d.depth * 120; }); + + // Update the nodes… + var node = vis.selectAll("g.node") + .data(nodes, function(d) { return d.id || (d.id = ++i); }); + + // Enter any new nodes at the parent's previous position. + var nodeEnter = node.enter().append("svg:g") + .attr("class", "node") + .attr("transform", function(d) { return "translate(" + source.x0 + "," + source.y0 + ")"; }) + .on("click", function(d) { that.toggle(d); that.updateBoth(d); }); + + nodeEnter.append("svg:circle") + .attr("r", 1e-6) + .style("fill", function(d) { return d._children ? "lightsteelblue" : "#fff"; }); + + nodeEnter.append("svg:text") + .attr("x", function(d) { + if( that.isParent(d) ) { + return -10; + } else { + return d.children || d._children ? -10 : 10; + } + }) + .attr("dy", ".35em") + .attr("text-anchor", function(d) { + if( that.isParent(d) ) { + return "end"; + } else { + return d.children || d._children ? "end" : "start"; + } + }) + .attr("transform",function(d) { + if( d != root ) { + if( that.isParent(d) ) { + return "rotate(45)"; + } else { + return "rotate(45)"; + } + } + }) + .text(function(d) { return d.name; }) + .style("fill-opacity", 1e-6); + + // Transition nodes to their new position. + var nodeUpdate = node.transition() + .duration(duration) + .attr("transform", function(d) { + if( that.isParent(d) ) { + return "translate(" + d.x + "," + -d.y + ")"; + } else { + return "translate(" + d.x + "," + d.y + ")"; + } + }); + + nodeUpdate.select("circle") + .attr("r", 4.5) + .style("fill", function(d) { return d._children ? "lightsteelblue" : "#fff"; }); + + nodeUpdate.select("text") + .style("fill-opacity", 1); + + // Transition exiting nodes to the parent's new position. + var nodeExit = node.exit().transition() + .duration(duration) + .attr("transform", function(d) { return "translate(" + source.x + "," + source.y + ")"; }) + .remove(); + + nodeExit.select("circle") + .attr("r", 1e-6); + + nodeExit.select("text") + .style("fill-opacity", 1e-6); + + // Update the links… + var link = vis.selectAll("path.link") + .data(tree.links_parents(nodes).concat(tree.links(nodes)), function(d) { return d.target.id; }); + + // Enter any new links at the parent's previous position. + link.enter().insert("svg:path", "g") + .attr("class", "link") + .attr("d", function(d) { + var o = {x: source.x0, y: source.y0}; + if( that.isParent(d.target) ) { + return parentdiagonal({source: o, target: o}); + } else { + // return parentdiagonal({source: o, target: o}); + return childdiagonal({source: o, target: o}); + } + }) + .transition() + .duration(duration) + // .attr("d", parentdiagonal); + .attr("d", function(d) { + if( that.isParent(d.target) ) { + return parentdiagonal(d); + } else { + // return parentdiagonal(d); + return childdiagonal(d); + } + }) + + // Transition links to their new position. + link.transition() + .duration(duration) + // .attr("d", parentdiagonal); + .attr("d", function(d) { + if( that.isParent(d.target) ) { + return parentdiagonal(d); + } else { + return childdiagonal(d); + } + }) + + // Transition exiting nodes to the parent's new position. + link.exit().transition() + .duration(duration) + .attr("d", function(d) { + var o = {x: source.x, y: source.y}; + // return parentdiagonal({source: o, target: o}); + if( that.isParent(d.target) ) { + return parentdiagonal({source: o, target: o}); + } else { + return childdiagonal({source: o, target: o}); + } + }) + .remove(); + + // Stash the old positions for transition. + nodes.forEach(function(d) { + d.x0 = d.x; + d.y0 = d.y; + }); + }, + updateParents: function(source) { + var duration = d3.event && d3.event.altKey ? 5000 : 500; + + // Compute the new tree layout. + var nodes = tree.nodes(root).reverse(); + + // Normalize for fixed-depth. + nodes.forEach(function(d) { d.y = d.depth * 180; }); + + // Update the nodes… + var node = vis.selectAll("g.node") + .data(nodes, function(d) { return d.id || (d.id = ++i); }); + + // Enter any new nodes at the parent's previous position. + var nodeEnter = node.enter().append("svg:g") + .attr("class", "node") + // .attr("transform", function(d) { return "translate(" + source.y0 + "," + source.x0 + ")"; }) + .attr("transform", function(d) { return "translate(" + source.x0 + "," + source.y0 + ")"; }) + .on("click", function(d) { that.toggle(d); that.updateParents(d); }); + + nodeEnter.append("svg:circle") + .attr("r", 1e-6) + .style("fill", function(d) { return d._children ? "lightsteelblue" : "#fff"; }); + + nodeEnter.append("svg:text") + .attr("x", function(d) { return d.children || d._children ? -10 : 10; }) + .attr("dy", ".35em") + .attr("text-anchor", function(d) { return d.children || d._children ? "end" : "start"; }) + .text(function(d) { return d.name; }) + .style("fill-opacity", 1e-6); + + // Transition nodes to their new position. + var nodeUpdate = node.transition() + .duration(duration) + .attr("transform", function(d) { return "translate(" + d.x + "," + -d.y + ")"; }); + + nodeUpdate.select("circle") + .attr("r", 4.5) + .style("fill", function(d) { return d._children ? "lightsteelblue" : "#fff"; }); + + nodeUpdate.select("text") + .style("fill-opacity", 1); + + // Transition exiting nodes to the parent's new position. + var nodeExit = node.exit().transition() + .duration(duration) + // .attr("transform", function(d) { return "translate(" + source.y + "," + source.x + ")"; }) + .attr("transform", function(d) { return "translate(" + source.x + "," + source.y + ")"; }) + .remove(); + + nodeExit.select("circle") + .attr("r", 1e-6); + + nodeExit.select("text") + .style("fill-opacity", 1e-6); + + // Update the links… + var link = vis.selectAll("path.link") + .data(tree.links(nodes), function(d) { return d.target.id; }); + + // Enter any new links at the parent's previous position. + link.enter().insert("svg:path", "g") + .attr("class", "link") + .attr("d", function(d) { + var o = {x: source.x0, y: source.y0}; + return parentdiagonal({source: o, target: o}); + }) + .transition() + .duration(duration) + .attr("d", parentdiagonal); + + // Transition links to their new position. + link.transition() + .duration(duration) + .attr("d", parentdiagonal); + + // Transition exiting nodes to the parent's new position. + link.exit().transition() + .duration(duration) + .attr("d", function(d) { + var o = {x: source.x, y: source.y}; + return parentdiagonal({source: o, target: o}); + }) + .remove(); + + // Stash the old positions for transition. + nodes.forEach(function(d) { + d.x0 = d.x; + d.y0 = d.y; + }); + }, + updateChildren: function(source) { + var duration = d3.event && d3.event.altKey ? 5000 : 500; + + // Compute the new tree layout. + var nodes = tree.nodes(root2).reverse(); + + // Normalize for fixed-depth. + nodes.forEach(function(d) { d.y = d.depth * 180; }); + + // Update the nodes… + var node = vis.selectAll("g.node") + .data(nodes, function(d) { return d.id || (d.id = ++i); }); + + // Enter any new nodes at the parent's previous position. + var nodeEnter = node.enter().append("svg:g") + .attr("class", "node") + // .attr("transform", function(d) { return "translate(" + source.y0 + "," + source.x0 + ")"; }) + .attr("transform", function(d) { return "translate(" + source.x0 + "," + source.y0 + ")"; }) + .on("click", function(d) { that.toggle(d); that.updateChildren(d); }); + + nodeEnter.append("svg:circle") + .attr("r", 1e-6) + .style("fill", function(d) { return d._children ? "lightsteelblue" : "#fff"; }); + + nodeEnter.append("svg:text") + .attr("x", function(d) { return d.children || d._children ? -10 : 10; }) + .attr("dy", ".35em") + .attr("text-anchor", function(d) { return d.children || d._children ? "end" : "start"; }) + .text(function(d) { return d.name; }) + .style("fill-opacity", 1e-6); + + // Transition nodes to their new position. + var nodeUpdate = node.transition() + .duration(duration) + // .attr("transform", function(d) { return "translate(" + d.y + "," + d.x + ")"; }); + .attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; }); + + nodeUpdate.select("circle") + .attr("r", 4.5) + .style("fill", function(d) { return d._children ? "lightsteelblue" : "#fff"; }); + + nodeUpdate.select("text") + .style("fill-opacity", 1); + + // Transition exiting nodes to the parent's new position. + var nodeExit = node.exit().transition() + .duration(duration) + // .attr("transform", function(d) { return "translate(" + source.y + "," + source.x + ")"; }) + .attr("transform", function(d) { return "translate(" + source.x + "," + source.y + ")"; }) + .remove(); + + nodeExit.select("circle") + .attr("r", 1e-6); + + nodeExit.select("text") + .style("fill-opacity", 1e-6); + + // Update the links… + var link = vis.selectAll("path.link") + .data(tree.links(nodes), function(d) { return d.target.id; }); + + // Enter any new links at the parent's previous position. + link.enter().insert("svg:path", "g") + .attr("class", "link") + .attr("d", function(d) { + var o = {x: source.x0, y: source.y0}; + return childdiagonal({source: o, target: o}); + }) + .transition() + .duration(duration) + .attr("d", childdiagonal); + + // Transition links to their new position. + link.transition() + .duration(duration) + .attr("d", childdiagonal); + + // Transition exiting nodes to the parent's new position. + link.exit().transition() + .duration(duration) + .attr("d", function(d) { + var o = {x: source.x, y: source.y}; + return childdiagonal({source: o, target: o}); + }) + .remove(); + + // Stash the old positions for transition. + nodes.forEach(function(d) { + d.x0 = d.x; + d.y0 = d.y; + }); + }, + + isParent: function(node) { + if( node.parent && node.parent != root ) { + return this.isParent(node.parent); + } else + // if ( node.name == 'data' || node.name == 'scale' || node.name == 'util' ) { + if( node.isparent ) { + return true; + } else { + return false; + } + }, + + // Toggle children. + toggle: function(d) { + if (d.children) { + d._children = d.children; + d.children = null; + } else { + d.children = d._children; + d._children = null; + } + if (d.parents) { + d._parents = d.parents; + d.parents = null; + } else { + d.parents = d._parents; + d._parents = null; + } + }, + toggleAll: function(d) { + if (d.children) { + d.children.forEach(that.toggleAll); + that.toggle(d); + } + if (d.parents) { + d.parents.forEach(that.toggleAll); + that.toggle(d); + } + } + + } + + return that; +} diff --git a/coselmar-ui/src/main/webapp/js/d3.layout.js b/coselmar-ui/src/main/webapp/js/d3.layout.js new file mode 100644 index 0000000..a4e4529 --- /dev/null +++ b/coselmar-ui/src/main/webapp/js/d3.layout.js @@ -0,0 +1,2123 @@ +/** +* Get from https://github.com/kanesee/d3-2way-tree and modified for our case +**/ +(function(){d3.layout = {}; +// Implements hierarchical edge bundling using Holten's algorithm. For each +// input link, a path is computed that travels through the tree, up the parent +// hierarchy to the least common ancestor, and then back down to the destination +// node. Each path is simply an array of nodes. +d3.layout.bundle = function() { + return function(links) { + var paths = [], + i = -1, + n = links.length; + while (++i < n) paths.push(d3_layout_bundlePath(links[i])); + return paths; + }; +}; + +function d3_layout_bundlePath(link) { + var start = link.source, + end = link.target, + lca = d3_layout_bundleLeastCommonAncestor(start, end), + points = [start]; + while (start !== lca) { + start = start.parent; + points.push(start); + } + var k = points.length; + while (end !== lca) { + points.splice(k, 0, end); + end = end.parent; + } + return points; +} + +function d3_layout_bundleAncestors(node) { + var ancestors = [], + parent = node.parent; + while (parent != null) { + ancestors.push(node); + node = parent; + parent = parent.parent; + } + ancestors.push(node); + return ancestors; +} + +function d3_layout_bundleLeastCommonAncestor(a, b) { + if (a === b) return a; + var aNodes = d3_layout_bundleAncestors(a), + bNodes = d3_layout_bundleAncestors(b), + aNode = aNodes.pop(), + bNode = bNodes.pop(), + sharedNode = null; + while (aNode === bNode) { + sharedNode = aNode; + aNode = aNodes.pop(); + bNode = bNodes.pop(); + } + return sharedNode; +} +d3.layout.chord = function() { + var chord = {}, + chords, + groups, + matrix, + n, + padding = 0, + sortGroups, + sortSubgroups, + sortChords; + + function relayout() { + var subgroups = {}, + groupSums = [], + groupIndex = d3.range(n), + subgroupIndex = [], + k, + x, + x0, + i, + j; + + chords = []; + groups = []; + + // Compute the sum. + k = 0, i = -1; while (++i < n) { + x = 0, j = -1; while (++j < n) { + x += matrix[i][j]; + } + groupSums.push(x); + subgroupIndex.push(d3.range(n)); + k += x; + } + + // Sort groups… + if (sortGroups) { + groupIndex.sort(function(a, b) { + return sortGroups(groupSums[a], groupSums[b]); + }); + } + + // Sort subgroups… + if (sortSubgroups) { + subgroupIndex.forEach(function(d, i) { + d.sort(function(a, b) { + return sortSubgroups(matrix[i][a], matrix[i][b]); + }); + }); + } + + // Convert the sum to scaling factor for [0, 2pi]. + // TODO Allow start and end angle to be specified. + // TODO Allow padding to be specified as percentage? + k = (2 * Math.PI - padding * n) / k; + + // Compute the start and end angle for each group and subgroup. + x = 0, i = -1; while (++i < n) { + x0 = x, j = -1; while (++j < n) { + var di = groupIndex[i], + dj = subgroupIndex[i][j], + v = matrix[di][dj]; + subgroups[di + "-" + dj] = { + index: di, + subindex: dj, + startAngle: x, + endAngle: x += v * k, + value: v + }; + } + groups.push({ + index: di, + startAngle: x0, + endAngle: x, + value: (x - x0) / k + }); + x += padding; + } + + // Generate chords for each (non-empty) subgroup-subgroup link. + i = -1; while (++i < n) { + j = i - 1; while (++j < n) { + var source = subgroups[i + "-" + j], + target = subgroups[j + "-" + i]; + if (source.value || target.value) { + chords.push(source.value < target.value + ? {source: target, target: source} + : {source: source, target: target}); + } + } + } + + if (sortChords) resort(); + } + + function resort() { + chords.sort(function(a, b) { + return sortChords(a.target.value, b.target.value); + }); + } + + chord.matrix = function(x) { + if (!arguments.length) return matrix; + n = (matrix = x) && matrix.length; + chords = groups = null; + return chord; + }; + + chord.padding = function(x) { + if (!arguments.length) return padding; + padding = x; + chords = groups = null; + return chord; + }; + + chord.sortGroups = function(x) { + if (!arguments.length) return sortGroups; + sortGroups = x; + chords = groups = null; + return chord; + }; + + chord.sortSubgroups = function(x) { + if (!arguments.length) return sortSubgroups; + sortSubgroups = x; + chords = null; + return chord; + }; + + chord.sortChords = function(x) { + if (!arguments.length) return sortChords; + sortChords = x; + if (chords) resort(); + return chord; + }; + + chord.chords = function() { + if (!chords) relayout(); + return chords; + }; + + chord.groups = function() { + if (!groups) relayout(); + return groups; + }; + + return chord; +}; +// A rudimentary force layout using Gauss-Seidel. +d3.layout.force = function() { + var force = {}, + event = d3.dispatch("tick"), + size = [1, 1], + drag, + alpha, + friction = .9, + linkDistance = d3_layout_forceLinkDistance, + linkStrength = d3_layout_forceLinkStrength, + charge = -30, + gravity = .1, + theta = .8, + interval, + nodes = [], + links = [], + distances, + strengths, + charges; + + function repulse(node) { + return function(quad, x1, y1, x2, y2) { + if (quad.point !== node) { + var dx = quad.cx - node.x, + dy = quad.cy - node.y, + dn = 1 / Math.sqrt(dx * dx + dy * dy); + + /* Barnes-Hut criterion. */ + if ((x2 - x1) * dn < theta) { + var k = quad.charge * dn * dn; + node.px -= dx * k; + node.py -= dy * k; + return true; + } + + if (quad.point && isFinite(dn)) { + var k = quad.pointCharge * dn * dn; + node.px -= dx * k; + node.py -= dy * k; + } + } + return !quad.charge; + }; + } + + function tick() { + var n = nodes.length, + m = links.length, + q, + i, // current index + o, // current object + s, // current source + t, // current target + l, // current distance + k, // current force + x, // x-distance + y; // y-distance + + // gauss-seidel relaxation for links + for (i = 0; i < m; ++i) { + o = links[i]; + s = o.source; + t = o.target; + x = t.x - s.x; + y = t.y - s.y; + if (l = (x * x + y * y)) { + l = alpha * strengths[i] * ((l = Math.sqrt(l)) - distances[i]) / l; + x *= l; + y *= l; + t.x -= x * (k = s.weight / (t.weight + s.weight)); + t.y -= y * k; + s.x += x * (k = 1 - k); + s.y += y * k; + } + } + + // apply gravity forces + if (k = alpha * gravity) { + x = size[0] / 2; + y = size[1] / 2; + i = -1; if (k) while (++i < n) { + o = nodes[i]; + o.x += (x - o.x) * k; + o.y += (y - o.y) * k; + } + } + + // compute quadtree center of mass and apply charge forces + if (charge) { + d3_layout_forceAccumulate(q = d3.geom.quadtree(nodes), alpha, charges); + i = -1; while (++i < n) { + if (!(o = nodes[i]).fixed) { + q.visit(repulse(o)); + } + } + } + + // position verlet integration + i = -1; while (++i < n) { + o = nodes[i]; + if (o.fixed) { + o.x = o.px; + o.y = o.py; + } else { + o.x -= (o.px - (o.px = o.x)) * friction; + o.y -= (o.py - (o.py = o.y)) * friction; + } + } + + event.tick.dispatch({type: "tick", alpha: alpha}); + + // simulated annealing, basically + return (alpha *= .99) < .005; + } + + force.on = function(type, listener) { + event[type].add(listener); + return force; + }; + + force.nodes = function(x) { + if (!arguments.length) return nodes; + nodes = x; + return force; + }; + + force.links = function(x) { + if (!arguments.length) return links; + links = x; + return force; + }; + + force.size = function(x) { + if (!arguments.length) return size; + size = x; + return force; + }; + + force.linkDistance = function(x) { + if (!arguments.length) return linkDistance; + linkDistance = d3.functor(x); + return force; + }; + + // For backwards-compatibility. + force.distance = force.linkDistance; + + force.linkStrength = function(x) { + if (!arguments.length) return linkStrength; + linkStrength = d3.functor(x); + return force; + }; + + force.friction = function(x) { + if (!arguments.length) return friction; + friction = x; + return force; + }; + + force.charge = function(x) { + if (!arguments.length) return charge; + charge = typeof x === "function" ? x : +x; + return force; + }; + + force.gravity = function(x) { + if (!arguments.length) return gravity; + gravity = x; + return force; + }; + + force.theta = function(x) { + if (!arguments.length) return theta; + theta = x; + return force; + }; + + force.start = function() { + var i, + j, + n = nodes.length, + m = links.length, + w = size[0], + h = size[1], + neighbors, + o; + + for (i = 0; i < n; ++i) { + (o = nodes[i]).index = i; + o.weight = 0; + } + + distances = []; + strengths = []; + for (i = 0; i < m; ++i) { + o = links[i]; + if (typeof o.source == "number") o.source = nodes[o.source]; + if (typeof o.target == "number") o.target = nodes[o.target]; + distances[i] = linkDistance.call(this, o, i); + strengths[i] = linkStrength.call(this, o, i); + ++o.source.weight; + ++o.target.weight; + } + + for (i = 0; i < n; ++i) { + o = nodes[i]; + if (isNaN(o.x)) o.x = position("x", w); + if (isNaN(o.y)) o.y = position("y", h); + if (isNaN(o.px)) o.px = o.x; + if (isNaN(o.py)) o.py = o.y; + } + + charges = []; + if (typeof charge === "function") { + for (i = 0; i < n; ++i) { + charges[i] = +charge.call(this, nodes[i], i); + } + } else { + for (i = 0; i < n; ++i) { + charges[i] = charge; + } + } + + // initialize node position based on first neighbor + function position(dimension, size) { + var neighbors = neighbor(i), + j = -1, + m = neighbors.length, + x; + while (++j < m) if (!isNaN(x = neighbors[j][dimension])) return x; + return Math.random() * size; + } + + // initialize neighbors lazily + function neighbor() { + if (!neighbors) { + neighbors = []; + for (j = 0; j < n; ++j) { + neighbors[j] = []; + } + for (j = 0; j < m; ++j) { + var o = links[j]; + neighbors[o.source.index].push(o.target); + neighbors[o.target.index].push(o.source); + } + } + return neighbors[i]; + } + + return force.resume(); + }; + + force.resume = function() { + alpha = .1; + d3.timer(tick); + return force; + }; + + force.stop = function() { + alpha = 0; + return force; + }; + + // use `node.call(force.drag)` to make nodes draggable + force.drag = function() { + if (!drag) drag = d3.behavior.drag() + .on("dragstart", dragstart) + .on("drag", d3_layout_forceDrag) + .on("dragend", d3_layout_forceDragEnd); + + this.on("mouseover.force", d3_layout_forceDragOver) + .on("mouseout.force", d3_layout_forceDragOut) + .call(drag); + }; + + function dragstart(d) { + d3_layout_forceDragOver(d3_layout_forceDragNode = d); + d3_layout_forceDragForce = force; + } + + return force; +}; + +var d3_layout_forceDragForce, + d3_layout_forceDragNode; + +function d3_layout_forceDragOver(d) { + d.fixed |= 2; +} + +function d3_layout_forceDragOut(d) { + if (d !== d3_layout_forceDragNode) d.fixed &= 1; +} + +function d3_layout_forceDragEnd() { + d3_layout_forceDrag(); + d3_layout_forceDragNode.fixed &= 1; + d3_layout_forceDragForce = d3_layout_forceDragNode = null; +} + +function d3_layout_forceDrag() { + d3_layout_forceDragNode.px += d3.event.dx; + d3_layout_forceDragNode.py += d3.event.dy; + d3_layout_forceDragForce.resume(); // restart annealing +} + +function d3_layout_forceAccumulate(quad, alpha, charges) { + var cx = 0, + cy = 0; + quad.charge = 0; + if (!quad.leaf) { + var nodes = quad.nodes, + n = nodes.length, + i = -1, + c; + while (++i < n) { + c = nodes[i]; + if (c == null) continue; + d3_layout_forceAccumulate(c, alpha, charges); + quad.charge += c.charge; + cx += c.charge * c.cx; + cy += c.charge * c.cy; + } + } + if (quad.point) { + // jitter internal nodes that are coincident + if (!quad.leaf) { + quad.point.x += Math.random() - .5; + quad.point.y += Math.random() - .5; + } + var k = alpha * charges[quad.point.index]; + quad.charge += quad.pointCharge = k; + cx += k * quad.point.x; + cy += k * quad.point.y; + } + quad.cx = cx / quad.charge; + quad.cy = cy / quad.charge; +} + +function d3_layout_forceLinkDistance(link) { + return 20; +} + +function d3_layout_forceLinkStrength(link) { + return 1; +} +d3.layout.partition = function() { + var hierarchy = d3.layout.hierarchy(), + size = [1, 1]; // width, height + + function position(node, x, dx, dy) { + var children = node.children; + node.x = x; + node.y = node.depth * dy; + node.dx = dx; + node.dy = dy; + if (children && (n = children.length)) { + var i = -1, + n, + c, + d; + dx = node.value ? dx / node.value : 0; + while (++i < n) { + position(c = children[i], x, d = c.value * dx, dy); + x += d; + } + } + } + + function depth(node) { + var children = node.children, + d = 0; + if (children && (n = children.length)) { + var i = -1, + n; + while (++i < n) d = Math.max(d, depth(children[i])); + } + return 1 + d; + } + + function partition(d, i) { + var nodes = hierarchy.call(this, d, i); + position(nodes[0], 0, size[0], size[1] / depth(nodes[0])); + return nodes; + } + + partition.size = function(x) { + if (!arguments.length) return size; + size = x; + return partition; + }; + + return d3_layout_hierarchyRebind(partition, hierarchy); +}; +d3.layout.pie = function() { + var value = Number, + sort = null, + startAngle = 0, + endAngle = 2 * Math.PI; + + function pie(data, i) { + + // Compute the start angle. + var a = +(typeof startAngle === "function" + ? startAngle.apply(this, arguments) + : startAngle); + + // Compute the angular range (end - start). + var k = (typeof endAngle === "function" + ? endAngle.apply(this, arguments) + : endAngle) - startAngle; + + // Optionally sort the data. + var index = d3.range(data.length); + if (sort != null) index.sort(function(i, j) { + return sort(data[i], data[j]); + }); + + // Compute the numeric values for each data element. + var values = data.map(value); + + // Convert k into a scale factor from value to angle, using the sum. + k /= values.reduce(function(p, d) { return p + d; }, 0); + + // Compute the arcs! + var arcs = index.map(function(i) { + return { + data: data[i], + value: d = values[i], + startAngle: a, + endAngle: a += d * k + }; + }); + + // Return the arcs in the original data's order. + return data.map(function(d, i) { + return arcs[index[i]]; + }); + } + + /** + * Specifies the value function *x*, which returns a nonnegative numeric value + * for each datum. The default value function is `Number`. The value function + * is passed two arguments: the current datum and the current index. + */ + pie.value = function(x) { + if (!arguments.length) return value; + value = x; + return pie; + }; + + /** + * Specifies a sort comparison operator *x*. The comparator is passed two data + * elements from the data array, a and b; it returns a negative value if a is + * less than b, a positive value if a is greater than b, and zero if a equals + * b. + */ + pie.sort = function(x) { + if (!arguments.length) return sort; + sort = x; + return pie; + }; + + /** + * Specifies the overall start angle of the pie chart. Defaults to 0. The + * start angle can be specified either as a constant or as a function; in the + * case of a function, it is evaluated once per array (as opposed to per + * element). + */ + pie.startAngle = function(x) { + if (!arguments.length) return startAngle; + startAngle = x; + return pie; + }; + + /** + * Specifies the overall end angle of the pie chart. Defaults to 2π. The + * end angle can be specified either as a constant or as a function; in the + * case of a function, it is evaluated once per array (as opposed to per + * element). + */ + pie.endAngle = function(x) { + if (!arguments.length) return endAngle; + endAngle = x; + return pie; + }; + + return pie; +}; +// data is two-dimensional array of x,y; we populate y0 +d3.layout.stack = function() { + var values = Object, + order = d3_layout_stackOrders["default"], + offset = d3_layout_stackOffsets["zero"], + out = d3_layout_stackOut, + x = d3_layout_stackX, + y = d3_layout_stackY; + + function stack(data, index) { + + // Convert series to canonical two-dimensional representation. + var series = data.map(function(d, i) { + return values.call(stack, d, i); + }); + + // Convert each series to canonical [[x,y]] representation. + var points = series.map(function(d, i) { + return d.map(function(v, i) { + return [x.call(stack, v, i), y.call(stack, v, i)]; + }); + }); + + // Compute the order of series, and permute them. + var orders = order.call(stack, points, index); + series = d3.permute(series, orders); + points = d3.permute(points, orders); + + // Compute the baseline… + var offsets = offset.call(stack, points, index); + + // And propagate it to other series. + var n = series.length, + m = series[0].length, + i, + j, + o; + for (j = 0; j < m; ++j) { + out.call(stack, series[0][j], o = offsets[j], points[0][j][1]); + for (i = 1; i < n; ++i) { + out.call(stack, series[i][j], o += points[i - 1][j][1], points[i][j][1]); + } + } + + return data; + } + + stack.values = function(x) { + if (!arguments.length) return values; + values = x; + return stack; + }; + + stack.order = function(x) { + if (!arguments.length) return order; + order = typeof x === "function" ? x : d3_layout_stackOrders[x]; + return stack; + }; + + stack.offset = function(x) { + if (!arguments.length) return offset; + offset = typeof x === "function" ? x : d3_layout_stackOffsets[x]; + return stack; + }; + + stack.x = function(z) { + if (!arguments.length) return x; + x = z; + return stack; + }; + + stack.y = function(z) { + if (!arguments.length) return y; + y = z; + return stack; + }; + + stack.out = function(z) { + if (!arguments.length) return out; + out = z; + return stack; + }; + + return stack; +} + +function d3_layout_stackX(d) { + return d.x; +} + +function d3_layout_stackY(d) { + return d.y; +} + +function d3_layout_stackOut(d, y0, y) { + d.y0 = y0; + d.y = y; +} + +var d3_layout_stackOrders = { + + "inside-out": function(data) { + var n = data.length, + i, + j, + max = data.map(d3_layout_stackMaxIndex), + sums = data.map(d3_layout_stackReduceSum), + index = d3.range(n).sort(function(a, b) { return max[a] - max[b]; }), + top = 0, + bottom = 0, + tops = [], + bottoms = []; + for (i = 0; i < n; ++i) { + j = index[i]; + if (top < bottom) { + top += sums[j]; + tops.push(j); + } else { + bottom += sums[j]; + bottoms.push(j); + } + } + return bottoms.reverse().concat(tops); + }, + + "reverse": function(data) { + return d3.range(data.length).reverse(); + }, + + "default": function(data) { + return d3.range(data.length); + } + +}; + +var d3_layout_stackOffsets = { + + "silhouette": function(data) { + var n = data.length, + m = data[0].length, + sums = [], + max = 0, + i, + j, + o, + y0 = []; + for (j = 0; j < m; ++j) { + for (i = 0, o = 0; i < n; i++) o += data[i][j][1]; + if (o > max) max = o; + sums.push(o); + } + for (j = 0; j < m; ++j) { + y0[j] = (max - sums[j]) / 2; + } + return y0; + }, + + "wiggle": function(data) { + var n = data.length, + x = data[0], + m = x.length, + max = 0, + i, + j, + k, + s1, + s2, + s3, + dx, + o, + o0, + y0 = []; + y0[0] = o = o0 = 0; + for (j = 1; j < m; ++j) { + for (i = 0, s1 = 0; i < n; ++i) s1 += data[i][j][1]; + for (i = 0, s2 = 0, dx = x[j][0] - x[j - 1][0]; i < n; ++i) { + for (k = 0, s3 = (data[i][j][1] - data[i][j - 1][1]) / (2 * dx); k < i; ++k) { + s3 += (data[k][j][1] - data[k][j - 1][1]) / dx; + } + s2 += s3 * data[i][j][1]; + } + y0[j] = o -= s1 ? s2 / s1 * dx : 0; + if (o < o0) o0 = o; + } + for (j = 0; j < m; ++j) y0[j] -= o0; + return y0; + }, + + "expand": function(data) { + var n = data.length, + m = data[0].length, + k = 1 / n, + i, + j, + o, + y0 = []; + for (j = 0; j < m; ++j) { + for (i = 0, o = 0; i < n; i++) o += data[i][j][1]; + if (o) for (i = 0; i < n; i++) data[i][j][1] /= o; + else for (i = 0; i < n; i++) data[i][j][1] = k; + } + for (j = 0; j < m; ++j) y0[j] = 0; + return y0; + }, + + "zero": function(data) { + var j = -1, + m = data[0].length, + y0 = []; + while (++j < m) y0[j] = 0; + return y0; + } + +}; + +function d3_layout_stackMaxIndex(array) { + var i = 1, + j = 0, + v = array[0][1], + k, + n = array.length; + for (; i < n; ++i) { + if ((k = array[i][1]) > v) { + j = i; + v = k; + } + } + return j; +} + +function d3_layout_stackReduceSum(d) { + return d.reduce(d3_layout_stackSum, 0); +} + +function d3_layout_stackSum(p, d) { + return p + d[1]; +} +d3.layout.histogram = function() { + var frequency = true, + valuer = Number, + ranger = d3_layout_histogramRange, + binner = d3_layout_histogramBinSturges; + + function histogram(data, i) { + var bins = [], + values = data.map(valuer, this), + range = ranger.call(this, values, i), + thresholds = binner.call(this, range, values, i), + bin, + i = -1, + n = values.length, + m = thresholds.length - 1, + k = frequency ? 1 : 1 / n, + x; + + // Initialize the bins. + while (++i < m) { + bin = bins[i] = []; + bin.dx = thresholds[i + 1] - (bin.x = thresholds[i]); + bin.y = 0; + } + + // Fill the bins, ignoring values outside the range. + i = -1; while(++i < n) { + x = values[i]; + if ((x >= range[0]) && (x <= range[1])) { + bin = bins[d3.bisect(thresholds, x, 1, m) - 1]; + bin.y += k; + bin.push(data[i]); + } + } + + return bins; + } + + // Specifies how to extract a value from the associated data. The default + // value function is `Number`, which is equivalent to the identity function. + histogram.value = function(x) { + if (!arguments.length) return valuer; + valuer = x; + return histogram; + }; + + // Specifies the range of the histogram. Values outside the specified range + // will be ignored. The argument `x` may be specified either as a two-element + // array representing the minimum and maximum value of the range, or as a + // function that returns the range given the array of values and the current + // index `i`. The default range is the extent (minimum and maximum) of the + // values. + histogram.range = function(x) { + if (!arguments.length) return ranger; + ranger = d3.functor(x); + return histogram; + }; + + // Specifies how to bin values in the histogram. The argument `x` may be + // specified as a number, in which case the range of values will be split + // uniformly into the given number of bins. Or, `x` may be an array of + // threshold values, defining the bins; the specified array must contain the + // rightmost (upper) value, thus specifying n + 1 values for n bins. Or, `x` + // may be a function which is evaluated, being passed the range, the array of + // values, and the current index `i`, returning an array of thresholds. The + // default bin function will divide the values into uniform bins using + // Sturges' formula. + histogram.bins = function(x) { + if (!arguments.length) return binner; + binner = typeof x === "number" + ? function(range) { return d3_layout_histogramBinFixed(range, x); } + : d3.functor(x); + return histogram; + }; + + // Specifies whether the histogram's `y` value is a count (frequency) or a + // probability (density). The default value is true. + histogram.frequency = function(x) { + if (!arguments.length) return frequency; + frequency = !!x; + return histogram; + }; + + return histogram; +}; + +function d3_layout_histogramBinSturges(range, values) { + return d3_layout_histogramBinFixed(range, Math.ceil(Math.log(values.length) / Math.LN2 + 1)); +} + +function d3_layout_histogramBinFixed(range, n) { + var x = -1, + b = +range[0], + m = (range[1] - b) / n, + f = []; + while (++x <= n) f[x] = m * x + b; + return f; +} + +function d3_layout_histogramRange(values) { + return [d3.min(values), d3.max(values)]; +} +d3.layout.hierarchy = function() { + var sort = d3_layout_hierarchySort, + parents = d3_layout_hierarchyParents, + children = d3_layout_hierarchyChildren, + value = d3_layout_hierarchyValue; + + // Recursively compute the node depth and value. + // Also converts the data representation into a standard hierarchy structure. + function recurseParents(data, depth, nodes) { + var rents = parents.call(hierarchy, data, depth), + node = d3_layout_hierarchyInline ? data : {data: data}; + node.depth = depth; + nodes.push(node); + if (rents && (n = rents.length)) { + var i = -1, + n, + c = node.parents = [], + v = 0, + j = depth + 1; + while (++i < n) { + d = recurseParents(rents[i], j, nodes); + d.parent = node; // ? + c.push(d); + v += d.value; + } + if (sort) c.sort(sort); + if (value) node.value = v; + } else if (value) { + node.value = +value.call(hierarchy, data, depth) || 0; + } + return node; + } + + function recurse(data, depth, nodes) { + var childs = children.call(hierarchy, data, depth), + node = d3_layout_hierarchyInline ? data : {data: data}; + node.depth = depth; + nodes.push(node); + if (childs && (n = childs.length)) { + var i = -1, + n, + c = node.children = [], + v = 0, + j = depth + 1; + while (++i < n) { + d = recurse(childs[i], j, nodes); + d.parent = node; + c.push(d); + v += d.value; + } + if (sort) c.sort(sort); + if (value) node.value = v; + } else if (value) { + node.value = +value.call(hierarchy, data, depth) || 0; + } + return node; + } + + // Recursively re-evaluates the node value. + function revalue(node, depth) { + var children = node.children, + v = 0; + if (children && (n = children.length)) { + var i = -1, + n, + j = depth + 1; + while (++i < n) v += revalue(children[i], j); + } else if (value) { + v = +value.call(hierarchy, d3_layout_hierarchyInline ? node : node.data, depth) || 0; + } + if (value) node.value = v; + return v; + } + + function hierarchy(d) { + var nodes = []; + recurseParents(d, 0, nodes); // ksee + recurse(d, 0, nodes); + return nodes; + } + + hierarchy.sort = function(x) { + if (!arguments.length) return sort; + sort = x; + return hierarchy; + }; + + hierarchy.children = function(x) { + if (!arguments.length) return children; + children = x; + return hierarchy; + }; + + hierarchy.value = function(x) { + if (!arguments.length) return value; + value = x; + return hierarchy; + }; + + // Re-evaluates the `value` property for the specified hierarchy. + hierarchy.revalue = function(root) { + revalue(root, 0); + return root; + }; + + return hierarchy; +}; + +// A method assignment helper for hierarchy subclasses. +function d3_layout_hierarchyRebind_parent(object, hierarchy) { + object.sort = d3.rebind(object, hierarchy.sort); + object.parents = d3.rebind(object, hierarchy.parents); + object.links_parents = d3_layout_hierarchyLinks_parents; + object.value = d3.rebind(object, hierarchy.value); + + // If the new API is used, enabling inlining. + object.nodes = function(d) { + d3_layout_hierarchyInline = true; + return (object.nodes = object)(d); + }; + + return object; +} + +function d3_layout_hierarchyRebind(object, hierarchy) { + object.sort = d3.rebind(object, hierarchy.sort); + object.children = d3.rebind(object, hierarchy.children); + object.links = d3_layout_hierarchyLinks; + object.value = d3.rebind(object, hierarchy.value); + + // If the new API is used, enabling inlining. + object.nodes = function(d) { + d3_layout_hierarchyInline = true; + return (object.nodes = object)(d); + }; + + return object; +} + +function d3_layout_hierarchyParents(d) { + return d.parents; +} + +function d3_layout_hierarchyChildren(d) { + return d.children; +} + +function d3_layout_hierarchyValue(d) { + return d.value; +} + +function d3_layout_hierarchySort(a, b) { + return b.value - a.value; +} + +// Returns an array source+target objects for the specified nodes. +function d3_layout_hierarchyLinks_parents(nodes) { + return d3.merge(nodes.map(function(parent) { + return (parent.parents || []).map(function(rent) { + return {source: parent, target: rent}; + }); + })); +} + +function d3_layout_hierarchyLinks(nodes) { + return d3.merge(nodes.map(function(parent) { + return (parent.children || []).map(function(child) { + return {source: parent, target: child}; + }); + })); +} + +// For backwards-compatibility, don't enable inlining by default. +var d3_layout_hierarchyInline = false; +d3.layout.pack = function() { + var hierarchy = d3.layout.hierarchy().sort(d3_layout_packSort), + size = [1, 1]; + + function pack(d, i) { + var nodes = hierarchy.call(this, d, i), + root = nodes[0]; + + // Recursively compute the layout. + root.x = 0; + root.y = 0; + d3_layout_packTree(root); + + // Scale the layout to fit the requested size. + var w = size[0], + h = size[1], + k = 1 / Math.max(2 * root.r / w, 2 * root.r / h); + d3_layout_packTransform(root, w / 2, h / 2, k); + + return nodes; + } + + pack.size = function(x) { + if (!arguments.length) return size; + size = x; + return pack; + }; + + return d3_layout_hierarchyRebind(pack, hierarchy); +}; + +function d3_layout_packSort(a, b) { + return a.value - b.value; +} + +function d3_layout_packInsert(a, b) { + var c = a._pack_next; + a._pack_next = b; + b._pack_prev = a; + b._pack_next = c; + c._pack_prev = b; +} + +function d3_layout_packSplice(a, b) { + a._pack_next = b; + b._pack_prev = a; +} + +function d3_layout_packIntersects(a, b) { + var dx = b.x - a.x, + dy = b.y - a.y, + dr = a.r + b.r; + return (dr * dr - dx * dx - dy * dy) > .001; // within epsilon +} + +function d3_layout_packCircle(nodes) { + var xMin = Infinity, + xMax = -Infinity, + yMin = Infinity, + yMax = -Infinity, + n = nodes.length, + a, b, c, j, k; + + function bound(node) { + xMin = Math.min(node.x - node.r, xMin); + xMax = Math.max(node.x + node.r, xMax); + yMin = Math.min(node.y - node.r, yMin); + yMax = Math.max(node.y + node.r, yMax); + } + + // Create node links. + nodes.forEach(d3_layout_packLink); + + // Create first node. + a = nodes[0]; + a.x = -a.r; + a.y = 0; + bound(a); + + // Create second node. + if (n > 1) { + b = nodes[1]; + b.x = b.r; + b.y = 0; + bound(b); + + // Create third node and build chain. + if (n > 2) { + c = nodes[2]; + d3_layout_packPlace(a, b, c); + bound(c); + d3_layout_packInsert(a, c); + a._pack_prev = c; + d3_layout_packInsert(c, b); + b = a._pack_next; + + // Now iterate through the rest. + for (var i = 3; i < n; i++) { + d3_layout_packPlace(a, b, c = nodes[i]); + + // Search for the closest intersection. + var isect = 0, s1 = 1, s2 = 1; + for (j = b._pack_next; j !== b; j = j._pack_next, s1++) { + if (d3_layout_packIntersects(j, c)) { + isect = 1; + break; + } + } + if (isect == 1) { + for (k = a._pack_prev; k !== j._pack_prev; k = k._pack_prev, s2++) { + if (d3_layout_packIntersects(k, c)) { + if (s2 < s1) { + isect = -1; + j = k; + } + break; + } + } + } + + // Update node chain. + if (isect == 0) { + d3_layout_packInsert(a, c); + b = c; + bound(c); + } else if (isect > 0) { + d3_layout_packSplice(a, j); + b = j; + i--; + } else { // isect < 0 + d3_layout_packSplice(j, b); + a = j; + i--; + } + } + } + } + + // Re-center the circles and return the encompassing radius. + var cx = (xMin + xMax) / 2, + cy = (yMin + yMax) / 2, + cr = 0; + for (var i = 0; i < n; i++) { + var node = nodes[i]; + node.x -= cx; + node.y -= cy; + cr = Math.max(cr, node.r + Math.sqrt(node.x * node.x + node.y * node.y)); + } + + // Remove node links. + nodes.forEach(d3_layout_packUnlink); + + return cr; +} + +function d3_layout_packLink(node) { + node._pack_next = node._pack_prev = node; +} + +function d3_layout_packUnlink(node) { + delete node._pack_next; + delete node._pack_prev; +} + +function d3_layout_packTree(node) { + var children = node.children; + if (children && children.length) { + children.forEach(d3_layout_packTree); + node.r = d3_layout_packCircle(children); + } else { + node.r = Math.sqrt(node.value); + } +} + +function d3_layout_packTransform(node, x, y, k) { + var children = node.children; + node.x = (x += k * node.x); + node.y = (y += k * node.y); + node.r *= k; + if (children) { + var i = -1, n = children.length; + while (++i < n) d3_layout_packTransform(children[i], x, y, k); + } +} + +function d3_layout_packPlace(a, b, c) { + var db = a.r + c.r, + dx = b.x - a.x, + dy = b.y - a.y; + if (db && (dx || dy)) { + var da = b.r + c.r, + dc = Math.sqrt(dx * dx + dy * dy), + cos = Math.max(-1, Math.min(1, (db * db + dc * dc - da * da) / (2 * db * dc))), + theta = Math.acos(cos), + x = cos * (db /= dc), + y = Math.sin(theta) * db; + c.x = a.x + x * dx + y * dy; + c.y = a.y + x * dy - y * dx; + } else { + c.x = a.x + db; + c.y = a.y; + } +} +// Implements a hierarchical layout using the cluster (or dendogram) algorithm. +d3.layout.cluster = function() { + var hierarchy = d3.layout.hierarchy().sort(null).value(null), + separation = d3_layout_treeSeparation, + size = [1, 1]; // width, height + + function cluster(d, i) { + var nodes = hierarchy.call(this, d, i), + root = nodes[0], + previousNode, + x = 0, + kx, + ky; + + // First walk, computing the initial x & y values. + d3_layout_treeVisitAfter(root, function(node) { + var children = node.children; + if (children && children.length) { + node.x = d3_layout_clusterX(children); + node.y = d3_layout_clusterY(children); + } else { + node.x = previousNode ? x += separation(node, previousNode) : 0; + node.y = 0; + previousNode = node; + } + }); + + // Compute the left-most, right-most, and depth-most nodes for extents. + var left = d3_layout_clusterLeft(root), + right = d3_layout_clusterRight(root), + x0 = left.x - separation(left, right) / 2, + x1 = right.x + separation(right, left) / 2; + + // Second walk, normalizing x & y to the desired size. + d3_layout_treeVisitAfter(root, function(node) { + node.x = (node.x - x0) / (x1 - x0) * size[0]; + node.y = (1 - node.y / root.y) * size[1]; + }); + + return nodes; + } + + cluster.separation = function(x) { + if (!arguments.length) return separation; + separation = x; + return cluster; + }; + + cluster.size = function(x) { + if (!arguments.length) return size; + size = x; + return cluster; + }; + + return d3_layout_hierarchyRebind(cluster, hierarchy); +}; + +function d3_layout_clusterY(children) { + return 1 + d3.max(children, function(child) { + return child.y; + }); +} + +function d3_layout_clusterX(children) { + return children.reduce(function(x, child) { + return x + child.x; + }, 0) / children.length; +} + +function d3_layout_clusterLeft(node) { + var children = node.children; + return children && children.length ? d3_layout_clusterLeft(children[0]) : node; +} + +function d3_layout_clusterRight(node) { + var children = node.children, n; + return children && (n = children.length) ? d3_layout_clusterRight(children[n - 1]) : node; +} +// Node-link tree diagram using the Reingold-Tilford "tidy" algorithm +d3.layout.tree = function() { + var hierarchy = d3.layout.hierarchy().sort(null).value(null), + separation = d3_layout_treeSeparation, + size = [1, 1]; // width, height + + function tree(d, i) { + var nodes = hierarchy.call(this, d, i), + root = nodes[0]; + + function parentsFirstWalk(node, previousSibling) { + var parents = node.parents, + layout = node._tree; + if (parents && (n = parents.length)) { + var n, + firstParent = parents[0], + previousParent, + ancestor = firstParent, + parent, + i = -1; + while (++i < n) { + parent = parents[i]; + parentsFirstWalk(parent, previousParent); + ancestor = apportionParent(parent, previousParent, ancestor); + previousParent = parent; + } + d3_layout_treeShift_parent(node); + var midpoint = .5 * (firstParent._tree.prelim + parent._tree.prelim); + if (previousSibling) { + layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling); + layout.mod = layout.prelim - midpoint; + } else { + layout.prelim = midpoint; + } + } else { + if (previousSibling) { + layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling); + } + } + } + + function firstWalk(node, previousSibling) { + var children = node.children, + layout = node._tree; + if (children && (n = children.length)) { + var n, + firstChild = children[0], + previousChild, + ancestor = firstChild, + child, + i = -1; + while (++i < n) { + child = children[i]; + firstWalk(child, previousChild); + ancestor = apportion(child, previousChild, ancestor); + previousChild = child; + } + d3_layout_treeShift(node); + var midpoint = .5 * (firstChild._tree.prelim + child._tree.prelim); + if (previousSibling) { + layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling); + layout.mod = layout.prelim - midpoint; + } else { + layout.prelim = midpoint; + } + } else { + if (previousSibling) { + layout.prelim = previousSibling._tree.prelim + separation(node, previousSibling); + } + } + } + + function parentsSecondWalk(node, x) { + node.x = node._tree.prelim + x; + var parents = node.parents; + if (parents && (n = parents.length)) { + var i = -1, + n; + x += node._tree.mod; + while (++i < n) { + parentsSecondWalk(parents[i], x); + } + } + } + + function secondWalk(node, x) { + node.x = node._tree.prelim + x; + var children = node.children; + if (children && (n = children.length)) { + var i = -1, + n; + x += node._tree.mod; + while (++i < n) { + secondWalk(children[i], x); + } + } + } + + function apportionParent(node, previousSibling, ancestor) { + if (previousSibling) { + var vip = node, + vop = node, + vim = previousSibling, + vom = node.parent.parents[0], // ? + sip = vip._tree.mod, + sop = vop._tree.mod, + sim = vim._tree.mod, + som = vom._tree.mod, + shift; + // while (vim = d3_layout_treeRight(vim), vip = d3_layout_treeLeft(vip), vim && vip) { + while (vim = d3_layout_treeRight_parents(vim), vip = d3_layout_treeLeft_parents(vip), vim && vip) { + // vom = d3_layout_treeLeft(vom); + // vop = d3_layout_treeRight(vop); + vom = d3_layout_treeLeft_parents(vom); + vop = d3_layout_treeRight_parents(vop); + vop._tree.ancestor = node; + shift = vim._tree.prelim + sim - vip._tree.prelim - sip + separation(vim, vip); + if (shift > 0) { + d3_layout_treeMove(d3_layout_treeAncestor(vim, node, ancestor), node, shift); + sip += shift; + sop += shift; + } + sim += vim._tree.mod; + sip += vip._tree.mod; + som += vom._tree.mod; + sop += vop._tree.mod; + } + if (vim && !d3_layout_treeRight_parents(vop)) { + vop._tree.thread = vim; + vop._tree.mod += sim - sop; + } + if (vip && !d3_layout_treeLeft_parents(vom)) { + vom._tree.thread = vip; + vom._tree.mod += sip - som; + ancestor = node; + } + } + return ancestor; + } + + function apportion(node, previousSibling, ancestor) { + if (previousSibling) { + var vip = node, + vop = node, + vim = previousSibling, + vom = node.parent.children[0], + sip = vip._tree.mod, + sop = vop._tree.mod, + sim = vim._tree.mod, + som = vom._tree.mod, + shift; + while (vim = d3_layout_treeRight(vim), vip = d3_layout_treeLeft(vip), vim && vip) { + vom = d3_layout_treeLeft(vom); + vop = d3_layout_treeRight(vop); + vop._tree.ancestor = node; + shift = vim._tree.prelim + sim - vip._tree.prelim - sip + separation(vim, vip); + if (shift > 0) { + d3_layout_treeMove(d3_layout_treeAncestor(vim, node, ancestor), node, shift); + sip += shift; + sop += shift; + } + sim += vim._tree.mod; + sip += vip._tree.mod; + som += vom._tree.mod; + sop += vop._tree.mod; + } + if (vim && !d3_layout_treeRight(vop)) { + vop._tree.thread = vim; + vop._tree.mod += sim - sop; + } + if (vip && !d3_layout_treeLeft(vom)) { + vom._tree.thread = vip; + vom._tree.mod += sip - som; + ancestor = node; + } + } + return ancestor; + } + + // Initialize temporary layout variables. + // ksee + d3_layout_treeVisitAfter_parent(root, function(node, previousSibling) { + node._tree = { + ancestor: node, + prelim: 0, + mod: 0, + change: 0, + shift: 0, + number: previousSibling ? previousSibling._tree.number + 1 : 0 + }; + }); + + d3_layout_treeVisitAfter(root, function(node, previousSibling) { + node._tree = { + ancestor: node, + prelim: 0, + mod: 0, + change: 0, + shift: 0, + number: previousSibling ? previousSibling._tree.number + 1 : 0 + }; + }); + + // Compute the layout using Buchheim et al.'s algorithm. + parentsFirstWalk(root); // ksee + parentsSecondWalk(root, -root._tree.prelim); + firstWalk(root); + secondWalk(root, -root._tree.prelim); + + // Compute the left-most, right-most, and depth-most nodes for extents. + // ksee + var leftParent = d3_layout_treeSearch_parents(root, d3_layout_treeLeftmost), + rightParent = d3_layout_treeSearch_parents(root, d3_layout_treeRightmost), + deepParent = d3_layout_treeSearch_parents(root, d3_layout_treeDeepest), + x0_parent = leftParent.x - separation(leftParent, rightParent) / 2, + x1_parent = rightParent.x + separation(rightParent, leftParent) / 2, + y1_parent = deepParent.depth || 1; + left = d3_layout_treeSearch(root, d3_layout_treeLeftmost), + right = d3_layout_treeSearch(root, d3_layout_treeRightmost), + deep = d3_layout_treeSearch(root, d3_layout_treeDeepest), + x0 = left.x - separation(left, right) / 2, + x1 = right.x + separation(right, left) / 2, + y1 = deep.depth || 1; + + // Clear temporary layout variables; transform x and y. + // ksee + d3_layout_treeVisitAfter_parent(root, function(node) { + if( node != root ) { // don't position root node since d3_layout_treeVisitAfter will do it + node.x = (node.x - x0_parent) / (x1_parent - x0_parent) * size[0]; + node.y = node.depth / y1_parent * size[1]; + delete node._tree; + } + }); + + d3_layout_treeVisitAfter(root, function(node) { + node.x = (node.x - x0) / (x1 - x0) * size[0]; + node.y = node.depth / y1 * size[1]; + delete node._tree; + }); + + return nodes; + } + + tree.separation = function(x) { + if (!arguments.length) return separation; + separation = x; + return tree; + }; + + tree.size = function(x) { + if (!arguments.length) return size; + size = x; + return tree; + }; + + var object = d3_layout_hierarchyRebind_parent(tree, hierarchy); // ksee + return d3_layout_hierarchyRebind(tree, hierarchy); +}; + +function d3_layout_treeSeparation(a, b) { + return a.parent == b.parent ? 1 : 2; +} + +// function d3_layout_treeSeparationRadial(a, b) { +// return (a.parent == b.parent ? 1 : 2) / a.depth; +// } + +function d3_layout_treeLeft_parents(node) { + var parents = node.parents; + return parents && parents.length ? parents[0] : node._tree.thread; +} + +function d3_layout_treeLeft(node) { + var children = node.children; + return children && children.length ? children[0] : node._tree.thread; +} + +function d3_layout_treeRight_parents(node) { + var parents = node.parents, + n; + return parents && (n = parents.length) ? parents[n - 1] : node._tree.thread; +} + +function d3_layout_treeRight(node) { + var children = node.children, + n; + return children && (n = children.length) ? children[n - 1] : node._tree.thread; +} + +function d3_layout_treeSearch_parents(node, compare) { + var parents = node.parents; + if (parents && (n = parents.length)) { + var parent, + n, + i = -1; + while (++i < n) { + if (compare(parent = d3_layout_treeSearch_parents(parents[i], compare), node) > 0) { + node = parent; + } + } + } + return node; +} + +function d3_layout_treeSearch(node, compare) { + var children = node.children; + if (children && (n = children.length)) { + var child, + n, + i = -1; + while (++i < n) { + if (compare(child = d3_layout_treeSearch(children[i], compare), node) > 0) { + node = child; + } + } + } + return node; +} + +function d3_layout_treeRightmost(a, b) { + return a.x - b.x; +} + +function d3_layout_treeLeftmost(a, b) { + return b.x - a.x; +} + +function d3_layout_treeDeepest(a, b) { + return a.depth - b.depth; +} + +function d3_layout_treeVisitAfter_parent(node, callback) { + function visit(node, previousSibling) { + var parents = node.parents; + if (parents && (n = parents.length)) { + var parent, + previousParent = null, + i = -1, + n; + while (++i < n) { + parent = parents[i]; + visit(parent, previousParent); + previousParent = parent; + } + } + callback(node, previousSibling); + } + visit(node, null); +} + +function d3_layout_treeVisitAfter(node, callback) { + function visit(node, previousSibling) { + var children = node.children; + if (children && (n = children.length)) { + var child, + previousChild = null, + i = -1, + n; + while (++i < n) { + child = children[i]; + visit(child, previousChild); + previousChild = child; + } + } + callback(node, previousSibling); + } + visit(node, null); +} + +function d3_layout_treeShift_parent(node) { + var shift = 0, + change = 0, + parents = node.parents, + i = parents.length, + parent; + while (--i >= 0) { + parent = parents[i]._tree; + parent.prelim += shift; + parent.mod += shift; + shift += parent.shift + (change += parent.change); + } +} + +function d3_layout_treeShift(node) { + var shift = 0, + change = 0, + children = node.children, + i = children.length, + child; + while (--i >= 0) { + child = children[i]._tree; + child.prelim += shift; + child.mod += shift; + shift += child.shift + (change += child.change); + } +} + +function d3_layout_treeMove(ancestor, node, shift) { + ancestor = ancestor._tree; + node = node._tree; + var change = shift / (node.number - ancestor.number); + ancestor.change += change; + node.change -= change; + node.shift += shift; + node.prelim += shift; + node.mod += shift; +} + +function d3_layout_treeAncestor(vim, node, ancestor) { + return vim._tree.ancestor.parent == node.parent + ? vim._tree.ancestor + : ancestor; +} +// Squarified Treemaps by Mark Bruls, Kees Huizing, and Jarke J. van Wijk +// Modified to support a target aspect ratio by Jeff Heer +d3.layout.treemap = function() { + var hierarchy = d3.layout.hierarchy(), + round = Math.round, + size = [1, 1], // width, height + padding = null, + pad = d3_layout_treemapPadNull, + sticky = false, + stickies, + ratio = 0.5 * (1 + Math.sqrt(5)); // golden ratio + + // Compute the area for each child based on value & scale. + function scale(children, k) { + var i = -1, + n = children.length, + child, + area; + while (++i < n) { + area = (child = children[i]).value * (k < 0 ? 0 : k); + child.area = isNaN(area) || area <= 0 ? 0 : area; + } + } + + // Recursively arranges the specified node's children into squarified rows. + function squarify(node) { + var children = node.children; + if (children && children.length) { + var rect = pad(node), + row = [], + remaining = children.slice(), // copy-on-write + child, + best = Infinity, // the best row score so far + score, // the current row score + u = Math.min(rect.dx, rect.dy), // initial orientation + n; + scale(remaining, rect.dx * rect.dy / node.value); + row.area = 0; + while ((n = remaining.length) > 0) { + row.push(child = remaining[n - 1]); + row.area += child.area; + if ((score = worst(row, u)) <= best) { // continue with this orientation + remaining.pop(); + best = score; + } else { // abort, and try a different orientation + row.area -= row.pop().area; + position(row, u, rect, false); + u = Math.min(rect.dx, rect.dy); + row.length = row.area = 0; + best = Infinity; + } + } + if (row.length) { + position(row, u, rect, true); + row.length = row.area = 0; + } + children.forEach(squarify); + } + } + + // Recursively resizes the specified node's children into existing rows. + // Preserves the existing layout! + function stickify(node) { + var children = node.children; + if (children && children.length) { + var rect = pad(node), + remaining = children.slice(), // copy-on-write + child, + row = []; + scale(remaining, rect.dx * rect.dy / node.value); + row.area = 0; + while (child = remaining.pop()) { + row.push(child); + row.area += child.area; + if (child.z != null) { + position(row, child.z ? rect.dx : rect.dy, rect, !remaining.length); + row.length = row.area = 0; + } + } + children.forEach(stickify); + } + } + + // Computes the score for the specified row, as the worst aspect ratio. + function worst(row, u) { + var s = row.area, + r, + rmax = 0, + rmin = Infinity, + i = -1, + n = row.length; + while (++i < n) { + if (!(r = row[i].area)) continue; + if (r < rmin) rmin = r; + if (r > rmax) rmax = r; + } + s *= s; + u *= u; + return s + ? Math.max((u * rmax * ratio) / s, s / (u * rmin * ratio)) + : Infinity; + } + + // Positions the specified row of nodes. Modifies `rect`. + function position(row, u, rect, flush) { + var i = -1, + n = row.length, + x = rect.x, + y = rect.y, + v = u ? round(row.area / u) : 0, + o; + if (u == rect.dx) { // horizontal subdivision + if (flush || v > rect.dy) v = v ? rect.dy : 0; // over+underflow + while (++i < n) { + o = row[i]; + o.x = x; + o.y = y; + o.dy = v; + x += o.dx = v ? round(o.area / v) : 0; + } + o.z = true; + o.dx += rect.x + rect.dx - x; // rounding error + rect.y += v; + rect.dy -= v; + } else { // vertical subdivision + if (flush || v > rect.dx) v = v ? rect.dx : 0; // over+underflow + while (++i < n) { + o = row[i]; + o.x = x; + o.y = y; + o.dx = v; + y += o.dy = v ? round(o.area / v) : 0; + } + o.z = false; + o.dy += rect.y + rect.dy - y; // rounding error + rect.x += v; + rect.dx -= v; + } + } + + function treemap(d) { + var nodes = stickies || hierarchy(d), + root = nodes[0]; + root.x = 0; + root.y = 0; + root.dx = size[0]; + root.dy = size[1]; + if (stickies) hierarchy.revalue(root); + scale([root], root.dx * root.dy / root.value); + (stickies ? stickify : squarify)(root); + if (sticky) stickies = nodes; + return nodes; + } + + treemap.size = function(x) { + if (!arguments.length) return size; + size = x; + return treemap; + }; + + treemap.padding = function(x) { + if (!arguments.length) return padding; + + function padFunction(node) { + var p = x.call(treemap, node, node.depth); + return p == null + ? d3_layout_treemapPadNull(node) + : d3_layout_treemapPad(node, typeof p === "number" ? [p, p, p, p] : p); + } + + function padConstant(node) { + return d3_layout_treemapPad(node, x); + } + + var type; + pad = (padding = x) == null ? d3_layout_treemapPadNull + : (type = typeof x) === "function" ? padFunction + : type === "number" ? (x = [x, x, x, x], padConstant) + : padConstant; + return treemap; + }; + + treemap.round = function(x) { + if (!arguments.length) return round != Number; + round = x ? Math.round : Number; + return treemap; + }; + + treemap.sticky = function(x) { + if (!arguments.length) return sticky; + sticky = x; + stickies = null; + return treemap; + }; + + treemap.ratio = function(x) { + if (!arguments.length) return ratio; + ratio = x; + return treemap; + }; + + return d3_layout_hierarchyRebind(treemap, hierarchy); +}; + +function d3_layout_treemapPadNull(node) { + return {x: node.x, y: node.y, dx: node.dx, dy: node.dy}; +} + +function d3_layout_treemapPad(node, padding) { + var x = node.x + padding[3], + y = node.y + padding[0], + dx = node.dx - padding[1] - padding[3], + dy = node.dy - padding[0] - padding[2]; + if (dx < 0) { x += dx / 2; dx = 0; } + if (dy < 0) { y += dy / 2; dy = 0; } + return {x: x, y: y, dx: dx, dy: dy}; +} +})(); diff --git a/coselmar-ui/src/main/webapp/views/questions/modalHierarchy.html b/coselmar-ui/src/main/webapp/views/questions/modalHierarchy.html index b76fc29..220931f 100644 --- a/coselmar-ui/src/main/webapp/views/questions/modalHierarchy.html +++ b/coselmar-ui/src/main/webapp/views/questions/modalHierarchy.html @@ -1,3 +1,5 @@ +<link rel="stylesheet" href="css/d3-collapsible-tree.css"> + <div xmlns="http://www.w3.org/1999/html"> <div class="modal-title"> <h2 class="paddingLeft20">{{ 'question.modal.hierarchy.title' | translate }} {{question.title}}</h2> @@ -5,25 +7,15 @@ <div class="modal-body"> - <div id="questionHierarchy">{{hierarchyTree}}</div> - <div> - <ul> - <li ng-repeat="parent in ancestors"> - <a href="#/questions/{{parent.id}}" target="_blank">{{parent.title}}</a> - </li> - </ul> - </td> - <td> - <ul> - <li ng-repeat="child in descendants"> - <a href="#/questions/{{child.id}}" target="_blank">{{child.title}}</a> - </li> - </ul> - </div> + <div id="questionHierarchy"></div> </div> <div class="modal-footer"> <button class="btn btn-action btn-disable" ng-click="cancel()">{{ 'common.button.close' | translate }}</button> </div> -</div> \ No newline at end of file +</div> + + +<script> +</script> \ No newline at end of file diff --git a/pom.xml b/pom.xml index 8e90dc5..92f2c16 100644 --- a/pom.xml +++ b/pom.xml @@ -168,6 +168,7 @@ <httpcore.version>4.2.3</httpcore.version> <jqcloud2Version>2.0.1</jqcloud2Version> <angularJqcloudVersion>1.0.2</angularJqcloudVersion> + <d3JsVersion>3.5.12</d3JsVersion> </properties> <repositories> @@ -496,6 +497,13 @@ <scope>runtime</scope> </dependency> + <dependency> + <groupId>org.webjars</groupId> + <artifactId>d3js</artifactId> + <version>${d3JsVersion}</version> + <scope>runtime</scope> + </dependency> + <!-- Others --> <dependency> <groupId>com.github.spullara.mustache.java</groupId> -- To stop receiving notification emails like this one, please contact codelutin.com SCM administrator <admin+scm@codelutin.com>.