'use strict';

var d3Force = require('d3-force');
var interpolateNumber = require('d3-interpolate').interpolateNumber;
var d3 = require('@plotly/d3');
var d3Sankey = require('@plotly/d3-sankey');
var d3SankeyCircular = require('@plotly/d3-sankey-circular');

var c = require('./constants');
var tinycolor = require('tinycolor2');
var Color = require('../../components/color');
var Drawing = require('../../components/drawing');
var Lib = require('../../lib');
var strTranslate = Lib.strTranslate;
var strRotate = Lib.strRotate;
var gup = require('../../lib/gup');
var keyFun = gup.keyFun;
var repeat = gup.repeat;
var unwrap = gup.unwrap;
var svgTextUtils = require('../../lib/svg_text_utils');

var Registry = require('../../registry');

var alignmentConstants = require('../../constants/alignment');
var CAP_SHIFT = alignmentConstants.CAP_SHIFT;
var LINE_SPACING = alignmentConstants.LINE_SPACING;
var TEXTPAD = 3;

// view models

function sankeyModel(layout, d, traceIndex) {
    var calcData = unwrap(d);
    var trace = calcData.trace;
    var domain = trace.domain;
    var horizontal = trace.orientation === 'h';
    var nodePad = trace.node.pad;
    var nodeThickness = trace.node.thickness;
    var nodeAlign = {
        justify: d3Sankey.sankeyJustify,
        left: d3Sankey.sankeyLeft,
        right: d3Sankey.sankeyRight,
        center: d3Sankey.sankeyCenter
    }[trace.node.align];

    var width = layout.width * (domain.x[1] - domain.x[0]);
    var height = layout.height * (domain.y[1] - domain.y[0]);

    var nodes = calcData._nodes;
    var links = calcData._links;
    var circular = calcData.circular;

    // Select Sankey generator
    var sankey;
    if(circular) {
        sankey = d3SankeyCircular
            .sankeyCircular()
            .circularLinkGap(0);
    } else {
        sankey = d3Sankey.sankey();
    }

    sankey
      .iterations(c.sankeyIterations)
      .size(horizontal ? [width, height] : [height, width])
      .nodeWidth(nodeThickness)
      .nodePadding(nodePad)
      .nodeId(function(d) {
          return d.pointNumber;
      })
      .nodeAlign(nodeAlign)
      .nodes(nodes)
      .links(links);

    var graph = sankey();

    if(sankey.nodePadding() < nodePad) {
        Lib.warn('node.pad was reduced to ', sankey.nodePadding(), ' to fit within the figure.');
    }

    // Counters for nested loops
    var i, j, k;

    // Create transient nodes for animations
    for(var nodePointNumber in calcData._groupLookup) {
        var groupIndex = parseInt(calcData._groupLookup[nodePointNumber]);

        // Find node representing groupIndex
        var groupingNode;

        for(i = 0; i < graph.nodes.length; i++) {
            if(graph.nodes[i].pointNumber === groupIndex) {
                groupingNode = graph.nodes[i];
                break;
            }
        }
        // If groupinNode is undefined, no links are targeting this group
        if(!groupingNode) continue;

        var child = {
            pointNumber: parseInt(nodePointNumber),
            x0: groupingNode.x0,
            x1: groupingNode.x1,
            y0: groupingNode.y0,
            y1: groupingNode.y1,
            partOfGroup: true,
            sourceLinks: [],
            targetLinks: []
        };

        graph.nodes.unshift(child);
        groupingNode.childrenNodes.unshift(child);
    }

    function computeLinkConcentrations() {
        for(i = 0; i < graph.nodes.length; i++) {
            var node = graph.nodes[i];
            // Links connecting the same two nodes are part of a flow
            var flows = {};
            var flowKey;
            var link;
            for(j = 0; j < node.targetLinks.length; j++) {
                link = node.targetLinks[j];
                flowKey = link.source.pointNumber + ':' + link.target.pointNumber;
                if(!flows.hasOwnProperty(flowKey)) flows[flowKey] = [];
                flows[flowKey].push(link);
            }

            // Compute statistics for each flow
            var keys = Object.keys(flows);
            for(j = 0; j < keys.length; j++) {
                flowKey = keys[j];
                var flowLinks = flows[flowKey];

                // Find the total size of the flow and total size per label
                var total = 0;
                var totalPerLabel = {};
                for(k = 0; k < flowLinks.length; k++) {
                    link = flowLinks[k];
                    if(!totalPerLabel[link.label]) totalPerLabel[link.label] = 0;
                    totalPerLabel[link.label] += link.value;
                    total += link.value;
                }

                // Find the ratio of the link's value and the size of the flow
                for(k = 0; k < flowLinks.length; k++) {
                    link = flowLinks[k];
                    link.flow = {
                        value: total,
                        labelConcentration: totalPerLabel[link.label] / total,
                        concentration: link.value / total,
                        links: flowLinks
                    };
                    if(link.concentrationscale) {
                        link.color = tinycolor(link.concentrationscale(link.flow.labelConcentration));
                    }
                }
            }

            // Gather statistics of all links at current node
            var totalOutflow = 0;
            for(j = 0; j < node.sourceLinks.length; j++) {
                totalOutflow += node.sourceLinks[j].value;
            }
            for(j = 0; j < node.sourceLinks.length; j++) {
                link = node.sourceLinks[j];
                link.concentrationOut = link.value / totalOutflow;
            }

            var totalInflow = 0;
            for(j = 0; j < node.targetLinks.length; j++) {
                totalInflow += node.targetLinks[j].value;
            }

            for(j = 0; j < node.targetLinks.length; j++) {
                link = node.targetLinks[j];
                link.concenrationIn = link.value / totalInflow;
            }
        }
    }
    computeLinkConcentrations();

    // Push any overlapping nodes down.
    function resolveCollisionsTopToBottom(columns) {
        columns.forEach(function(nodes) {
            var node;
            var dy;
            var y = 0;
            var n = nodes.length;
            var i;
            nodes.sort(function(a, b) {
                return a.y0 - b.y0;
            });
            for(i = 0; i < n; ++i) {
                node = nodes[i];
                if(node.y0 >= y) {
                    // No overlap
                } else {
                    dy = (y - node.y0);
                    if(dy > 1e-6) node.y0 += dy, node.y1 += dy;
                }
                y = node.y1 + nodePad;
            }
        });
    }

    // Group nodes into columns based on their x position
    function snapToColumns(nodes) {
        // Sort nodes by x position
        var orderedNodes = nodes.map(function(n, i) {
            return {
                x0: n.x0,
                index: i
            };
        })
        .sort(function(a, b) {
            return a.x0 - b.x0;
        });

        var columns = [];
        var colNumber = -1;
        var colX; // Position of column
        var lastX = -Infinity; // Position of last node
        var dx;
        for(i = 0; i < orderedNodes.length; i++) {
            var node = nodes[orderedNodes[i].index];
            // If the node does not overlap with the last one
            if(node.x0 > lastX + nodeThickness) {
                // Start a new column
                colNumber += 1;
                colX = node.x0;
            }
            lastX = node.x0;

            // Add node to its associated column
            if(!columns[colNumber]) columns[colNumber] = [];
            columns[colNumber].push(node);

            // Change node's x position to align it with its column
            dx = colX - node.x0;
            node.x0 += dx, node.x1 += dx;
        }
        return columns;
    }

    // Force node position
    if(trace.node.x.length && trace.node.y.length) {
        for(i = 0; i < Math.min(trace.node.x.length, trace.node.y.length, graph.nodes.length); i++) {
            if(trace.node.x[i] && trace.node.y[i]) {
                var pos = [trace.node.x[i] * width, trace.node.y[i] * height];
                graph.nodes[i].x0 = pos[0] - nodeThickness / 2;
                graph.nodes[i].x1 = pos[0] + nodeThickness / 2;

                var nodeHeight = graph.nodes[i].y1 - graph.nodes[i].y0;
                graph.nodes[i].y0 = pos[1] - nodeHeight / 2;
                graph.nodes[i].y1 = pos[1] + nodeHeight / 2;
            }
        }
        if(trace.arrangement === 'snap') {
            nodes = graph.nodes;
            var columns = snapToColumns(nodes);
            resolveCollisionsTopToBottom(columns);
        }
        // Update links
        sankey.update(graph);
    }


    return {
        circular: circular,
        key: traceIndex,
        trace: trace,
        guid: Lib.randstr(),
        horizontal: horizontal,
        width: width,
        height: height,
        nodePad: trace.node.pad,
        nodeLineColor: trace.node.line.color,
        nodeLineWidth: trace.node.line.width,
        linkLineColor: trace.link.line.color,
        linkLineWidth: trace.link.line.width,
        linkArrowLength: trace.link.arrowlen,
        valueFormat: trace.valueformat,
        valueSuffix: trace.valuesuffix,
        textFont: trace.textfont,
        translateX: domain.x[0] * layout.width + layout.margin.l,
        translateY: layout.height - domain.y[1] * layout.height + layout.margin.t,
        dragParallel: horizontal ? height : width,
        dragPerpendicular: horizontal ? width : height,
        arrangement: trace.arrangement,
        sankey: sankey,
        graph: graph,
        forceLayouts: {},
        interactionState: {
            dragInProgress: false,
            hovered: false
        }
    };
}

function linkModel(d, l, i) {
    var tc = tinycolor(l.color);
    var htc = tinycolor(l.hovercolor);
    var basicKey = l.source.label + '|' + l.target.label;
    var key = basicKey + '__' + i;

    // for event data
    l.trace = d.trace;
    l.curveNumber = d.trace.index;

    return {
        circular: d.circular,
        key: key,
        traceId: d.key,
        pointNumber: l.pointNumber,
        link: l,
        tinyColorHue: Color.tinyRGB(tc),
        tinyColorAlpha: tc.getAlpha(),
        tinyColorHoverHue: Color.tinyRGB(htc),
        tinyColorHoverAlpha: htc.getAlpha(),
        linkPath: linkPath,
        linkLineColor: d.linkLineColor,
        linkLineWidth: d.linkLineWidth,
        linkArrowLength: d.linkArrowLength,
        valueFormat: d.valueFormat,
        valueSuffix: d.valueSuffix,
        sankey: d.sankey,
        parent: d,
        interactionState: d.interactionState,
        flow: l.flow
    };
}

function createCircularClosedPathString(link, arrowLen) {
    // Using coordinates computed by d3-sankey-circular
    var pathString = '';
    var offset = link.width / 2;
    var coords = link.circularPathData;
    if(link.circularLinkType === 'top') {
        // Top path
        pathString =
          // start at the left of the target node
          'M ' +
          (coords.targetX - arrowLen) + ' ' + (coords.targetY + offset) + ' ' +
          'L' +
          (coords.rightInnerExtent - arrowLen) + ' ' + (coords.targetY + offset) +
          'A' +
          (coords.rightLargeArcRadius + offset) + ' ' + (coords.rightSmallArcRadius + offset) + ' 0 0 1 ' +
          (coords.rightFullExtent - offset - arrowLen) + ' ' + (coords.targetY - coords.rightSmallArcRadius) +
          'L' +
          (coords.rightFullExtent - offset - arrowLen) + ' ' + coords.verticalRightInnerExtent +
          'A' +
          (coords.rightLargeArcRadius + offset) + ' ' + (coords.rightLargeArcRadius + offset) + ' 0 0 1 ' +
          (coords.rightInnerExtent - arrowLen) + ' ' + (coords.verticalFullExtent - offset) +
          'L' +
          coords.leftInnerExtent + ' ' + (coords.verticalFullExtent - offset) +
          'A' +
          (coords.leftLargeArcRadius + offset) + ' ' + (coords.leftLargeArcRadius + offset) + ' 0 0 1 ' +
          (coords.leftFullExtent + offset) + ' ' + coords.verticalLeftInnerExtent +
          'L' +
          (coords.leftFullExtent + offset) + ' ' + (coords.sourceY - coords.leftSmallArcRadius) +
          'A' +
          (coords.leftLargeArcRadius + offset) + ' ' + (coords.leftSmallArcRadius + offset) + ' 0 0 1 ' +
          coords.leftInnerExtent + ' ' + (coords.sourceY + offset) +
          'L' +
          coords.sourceX + ' ' + (coords.sourceY + offset) +

          // Walking back
          'L' +
          coords.sourceX + ' ' + (coords.sourceY - offset) +
          'L' +
          coords.leftInnerExtent + ' ' + (coords.sourceY - offset) +
          'A' +
          (coords.leftLargeArcRadius - offset) + ' ' + (coords.leftSmallArcRadius - offset) + ' 0 0 0 ' +
          (coords.leftFullExtent - offset) + ' ' + (coords.sourceY - coords.leftSmallArcRadius) +
          'L' +
          (coords.leftFullExtent - offset) + ' ' + coords.verticalLeftInnerExtent +
          'A' +
          (coords.leftLargeArcRadius - offset) + ' ' + (coords.leftLargeArcRadius - offset) + ' 0 0 0 ' +
          coords.leftInnerExtent + ' ' + (coords.verticalFullExtent + offset) +
          'L' +
          (coords.rightInnerExtent - arrowLen) + ' ' + (coords.verticalFullExtent + offset) +
          'A' +
          (coords.rightLargeArcRadius - offset) + ' ' + (coords.rightLargeArcRadius - offset) + ' 0 0 0 ' +
          (coords.rightFullExtent + offset - arrowLen) + ' ' + coords.verticalRightInnerExtent +
          'L' +
          (coords.rightFullExtent + offset - arrowLen) + ' ' + (coords.targetY - coords.rightSmallArcRadius) +
          'A' +
          (coords.rightLargeArcRadius - offset) + ' ' + (coords.rightSmallArcRadius - offset) + ' 0 0 0 ' +
          (coords.rightInnerExtent - arrowLen) + ' ' + (coords.targetY - offset) +
          'L' +
          (coords.targetX - arrowLen) + ' ' + (coords.targetY - offset) +
          (arrowLen > 0 ? 'L' + coords.targetX + ' ' + (coords.targetY) : '') +
          'Z';
    } else {
        // Bottom path
        pathString =
          // start at the left of the target node
          'M ' +
          (coords.targetX - arrowLen) + ' ' + (coords.targetY - offset) + ' ' +
          'L' +
          (coords.rightInnerExtent - arrowLen) + ' ' + (coords.targetY - offset) +
          'A' +
          (coords.rightLargeArcRadius + offset) + ' ' + (coords.rightSmallArcRadius + offset) + ' 0 0 0 ' +
          (coords.rightFullExtent - offset - arrowLen) + ' ' + (coords.targetY + coords.rightSmallArcRadius) +
          'L' +
          (coords.rightFullExtent - offset - arrowLen) + ' ' + coords.verticalRightInnerExtent +
          'A' +
          (coords.rightLargeArcRadius + offset) + ' ' + (coords.rightLargeArcRadius + offset) + ' 0 0 0 ' +
          (coords.rightInnerExtent - arrowLen) + ' ' + (coords.verticalFullExtent + offset) +
          'L' +
          coords.leftInnerExtent + ' ' + (coords.verticalFullExtent + offset) +
          'A' +
          (coords.leftLargeArcRadius + offset) + ' ' + (coords.leftLargeArcRadius + offset) + ' 0 0 0 ' +
          (coords.leftFullExtent + offset) + ' ' + coords.verticalLeftInnerExtent +
          'L' +
          (coords.leftFullExtent + offset) + ' ' + (coords.sourceY + coords.leftSmallArcRadius) +
          'A' +
          (coords.leftLargeArcRadius + offset) + ' ' + (coords.leftSmallArcRadius + offset) + ' 0 0 0 ' +
          coords.leftInnerExtent + ' ' + (coords.sourceY - offset) +
          'L' +
          coords.sourceX + ' ' + (coords.sourceY - offset) +

          // Walking back
          'L' +
          coords.sourceX + ' ' + (coords.sourceY + offset) +
          'L' +
          coords.leftInnerExtent + ' ' + (coords.sourceY + offset) +
          'A' +
          (coords.leftLargeArcRadius - offset) + ' ' + (coords.leftSmallArcRadius - offset) + ' 0 0 1 ' +
          (coords.leftFullExtent - offset) + ' ' + (coords.sourceY + coords.leftSmallArcRadius) +
          'L' +
          (coords.leftFullExtent - offset) + ' ' + coords.verticalLeftInnerExtent +
          'A' +
          (coords.leftLargeArcRadius - offset) + ' ' + (coords.leftLargeArcRadius - offset) + ' 0 0 1 ' +
          coords.leftInnerExtent + ' ' + (coords.verticalFullExtent - offset) +
          'L' +
          (coords.rightInnerExtent - arrowLen) + ' ' + (coords.verticalFullExtent - offset) +
          'A' +
          (coords.rightLargeArcRadius - offset) + ' ' + (coords.rightLargeArcRadius - offset) + ' 0 0 1 ' +
          (coords.rightFullExtent + offset - arrowLen) + ' ' + coords.verticalRightInnerExtent +
          'L' +
          (coords.rightFullExtent + offset - arrowLen) + ' ' + (coords.targetY + coords.rightSmallArcRadius) +
          'A' +
          (coords.rightLargeArcRadius - offset) + ' ' + (coords.rightSmallArcRadius - offset) + ' 0 0 1 ' +
          (coords.rightInnerExtent - arrowLen) + ' ' + (coords.targetY + offset) +
          'L' +
          (coords.targetX - arrowLen) + ' ' + (coords.targetY + offset) +
          (arrowLen > 0 ? 'L' + coords.targetX + ' ' + (coords.targetY) : '') +
          'Z';
    }
    return pathString;
}

function linkPath() {
    var curvature = 0.5;
    function path(d) {
        var arrowLen = d.linkArrowLength;
        if(d.link.circular) {
            return createCircularClosedPathString(d.link, arrowLen);
        } else {
            var maxArrowLength = Math.abs((d.link.target.x0 - d.link.source.x1) / 2);
            if(arrowLen > maxArrowLength) {
                arrowLen = maxArrowLength;
            }
            var x0 = d.link.source.x1;
            var x1 = d.link.target.x0 - arrowLen;
            var xi = interpolateNumber(x0, x1);
            var x2 = xi(curvature);
            var x3 = xi(1 - curvature);
            var y0a = d.link.y0 - d.link.width / 2;
            var y0b = d.link.y0 + d.link.width / 2;
            var y1a = d.link.y1 - d.link.width / 2;
            var y1b = d.link.y1 + d.link.width / 2;
            var start = 'M' + x0 + ',' + y0a;
            var upperCurve = 'C' + x2 + ',' + y0a +
                ' ' + x3 + ',' + y1a +
                ' ' + x1 + ',' + y1a;
            var lowerCurve = 'C' + x3 + ',' + y1b +
                ' ' + x2 + ',' + y0b +
                ' ' + x0 + ',' + y0b;

            var rightEnd = arrowLen > 0 ? 'L' + (x1 + arrowLen) + ',' + (y1a + d.link.width / 2) : '';
            rightEnd += 'L' + x1 + ',' + y1b;
            return start + upperCurve + rightEnd + lowerCurve + 'Z';
        }
    }
    return path;
}

function nodeModel(d, n) {
    var tc = tinycolor(n.color);
    var zoneThicknessPad = c.nodePadAcross;
    var zoneLengthPad = d.nodePad / 2;
    n.dx = n.x1 - n.x0;
    n.dy = n.y1 - n.y0;
    var visibleThickness = n.dx;
    var visibleLength = Math.max(0.5, n.dy);

    var key = 'node_' + n.pointNumber;
    // If it's a group, it's mutable and should be unique
    if(n.group) {
        key = Lib.randstr();
    }

    // for event data
    n.trace = d.trace;
    n.curveNumber = d.trace.index;

    return {
        index: n.pointNumber,
        key: key,
        partOfGroup: n.partOfGroup || false,
        group: n.group,
        traceId: d.key,
        trace: d.trace,
        node: n,
        nodePad: d.nodePad,
        nodeLineColor: d.nodeLineColor,
        nodeLineWidth: d.nodeLineWidth,
        textFont: d.textFont,
        size: d.horizontal ? d.height : d.width,
        visibleWidth: Math.ceil(visibleThickness),
        visibleHeight: visibleLength,
        zoneX: -zoneThicknessPad,
        zoneY: -zoneLengthPad,
        zoneWidth: visibleThickness + 2 * zoneThicknessPad,
        zoneHeight: visibleLength + 2 * zoneLengthPad,
        labelY: d.horizontal ? n.dy / 2 + 1 : n.dx / 2 + 1,
        left: n.originalLayer === 1,
        sizeAcross: d.width,
        forceLayouts: d.forceLayouts,
        horizontal: d.horizontal,
        darkBackground: tc.getBrightness() <= 128,
        tinyColorHue: Color.tinyRGB(tc),
        tinyColorAlpha: tc.getAlpha(),
        valueFormat: d.valueFormat,
        valueSuffix: d.valueSuffix,
        sankey: d.sankey,
        graph: d.graph,
        arrangement: d.arrangement,
        uniqueNodeLabelPathId: [d.guid, d.key, key].join('_'),
        interactionState: d.interactionState,
        figure: d
    };
}

// rendering snippets

function updateNodePositions(sankeyNode) {
    sankeyNode
        .attr('transform', function(d) {
            return strTranslate(d.node.x0.toFixed(3), (d.node.y0).toFixed(3));
        });
}

function updateNodeShapes(sankeyNode) {
    sankeyNode.call(updateNodePositions);
}

function updateShapes(sankeyNode, sankeyLink) {
    sankeyNode.call(updateNodeShapes);
    sankeyLink.attr('d', linkPath());
}

function sizeNode(rect) {
    rect
      .attr('width', function(d) {return d.node.x1 - d.node.x0;})
      .attr('height', function(d) {return d.visibleHeight;});
}

function salientEnough(d) {return (d.link.width > 1 || d.linkLineWidth > 0);}

function sankeyTransform(d) {
    var offset = strTranslate(d.translateX, d.translateY);
    return offset + (d.horizontal ? 'matrix(1 0 0 1 0 0)' : 'matrix(0 1 1 0 0 0)');
}

// event handling

function attachPointerEvents(selection, sankey, eventSet) {
    selection
        .on('.basic', null) // remove any preexisting handlers
        .on('mouseover.basic', function(d) {
            if(!d.interactionState.dragInProgress && !d.partOfGroup) {
                eventSet.hover(this, d, sankey);
                d.interactionState.hovered = [this, d];
            }
        })
        .on('mousemove.basic', function(d) {
            if(!d.interactionState.dragInProgress && !d.partOfGroup) {
                eventSet.follow(this, d);
                d.interactionState.hovered = [this, d];
            }
        })
        .on('mouseout.basic', function(d) {
            if(!d.interactionState.dragInProgress && !d.partOfGroup) {
                eventSet.unhover(this, d, sankey);
                d.interactionState.hovered = false;
            }
        })
        .on('click.basic', function(d) {
            if(d.interactionState.hovered) {
                eventSet.unhover(this, d, sankey);
                d.interactionState.hovered = false;
            }
            if(!d.interactionState.dragInProgress && !d.partOfGroup) {
                eventSet.select(this, d, sankey);
            }
        });
}

function attachDragHandler(sankeyNode, sankeyLink, callbacks, gd) {
    var dragBehavior = d3.behavior.drag()
        .origin(function(d) {
            return {
                x: d.node.x0 + d.visibleWidth / 2,
                y: d.node.y0 + d.visibleHeight / 2
            };
        })

        .on('dragstart', function(d) {
            if(d.arrangement === 'fixed') return;
            Lib.ensureSingle(gd._fullLayout._infolayer, 'g', 'dragcover', function(s) {
                gd._fullLayout._dragCover = s;
            });
            Lib.raiseToTop(this);
            d.interactionState.dragInProgress = d.node;

            saveCurrentDragPosition(d.node);
            if(d.interactionState.hovered) {
                callbacks.nodeEvents.unhover.apply(0, d.interactionState.hovered);
                d.interactionState.hovered = false;
            }
            if(d.arrangement === 'snap') {
                var forceKey = d.traceId + '|' + d.key;
                if(d.forceLayouts[forceKey]) {
                    d.forceLayouts[forceKey].alpha(1);
                } else { // make a forceLayout if needed
                    attachForce(sankeyNode, forceKey, d, gd);
                }
                startForce(sankeyNode, sankeyLink, d, forceKey, gd);
            }
        })

        .on('drag', function(d) {
            if(d.arrangement === 'fixed') return;
            var x = d3.event.x;
            var y = d3.event.y;
            if(d.arrangement === 'snap') {
                d.node.x0 = x - d.visibleWidth / 2;
                d.node.x1 = x + d.visibleWidth / 2;
                d.node.y0 = y - d.visibleHeight / 2;
                d.node.y1 = y + d.visibleHeight / 2;
            } else {
                if(d.arrangement === 'freeform') {
                    d.node.x0 = x - d.visibleWidth / 2;
                    d.node.x1 = x + d.visibleWidth / 2;
                }
                y = Math.max(0, Math.min(d.size - d.visibleHeight / 2, y));
                d.node.y0 = y - d.visibleHeight / 2;
                d.node.y1 = y + d.visibleHeight / 2;
            }

            saveCurrentDragPosition(d.node);
            if(d.arrangement !== 'snap') {
                d.sankey.update(d.graph);
                updateShapes(sankeyNode.filter(sameLayer(d)), sankeyLink);
            }
        })

        .on('dragend', function(d) {
            if(d.arrangement === 'fixed') return;
            d.interactionState.dragInProgress = false;
            for(var i = 0; i < d.node.childrenNodes.length; i++) {
                d.node.childrenNodes[i].x = d.node.x;
                d.node.childrenNodes[i].y = d.node.y;
            }
            if(d.arrangement !== 'snap') persistFinalNodePositions(d, gd);
        });

    sankeyNode
        .on('.drag', null) // remove possible previous handlers
        .call(dragBehavior);
}

function attachForce(sankeyNode, forceKey, d, gd) {
    // Attach force to nodes in the same column (same x coordinate)
    switchToForceFormat(d.graph.nodes);
    var nodes = d.graph.nodes
        .filter(function(n) {return n.originalX === d.node.originalX;})
        // Filter out children
        .filter(function(n) {return !n.partOfGroup;});
    d.forceLayouts[forceKey] = d3Force.forceSimulation(nodes)
        .alphaDecay(0)
        .force('collide', d3Force.forceCollide()
            .radius(function(n) {return n.dy / 2 + d.nodePad / 2;})
            .strength(1)
            .iterations(c.forceIterations))
        .force('constrain', snappingForce(sankeyNode, forceKey, nodes, d, gd))
        .stop();
}

function startForce(sankeyNode, sankeyLink, d, forceKey, gd) {
    window.requestAnimationFrame(function faster() {
        var i;
        for(i = 0; i < c.forceTicksPerFrame; i++) {
            d.forceLayouts[forceKey].tick();
        }

        var nodes = d.graph.nodes;
        switchToSankeyFormat(nodes);

        d.sankey.update(d.graph);
        updateShapes(sankeyNode.filter(sameLayer(d)), sankeyLink);

        if(d.forceLayouts[forceKey].alpha() > 0) {
            window.requestAnimationFrame(faster);
        } else {
            // Make sure the final x position is equal to its original value
            // because the force simulation will have numerical error
            var x = d.node.originalX;
            d.node.x0 = x - d.visibleWidth / 2;
            d.node.x1 = x + d.visibleWidth / 2;

            persistFinalNodePositions(d, gd);
        }
    });
}

function snappingForce(sankeyNode, forceKey, nodes, d) {
    return function _snappingForce() {
        var maxVelocity = 0;
        for(var i = 0; i < nodes.length; i++) {
            var n = nodes[i];
            if(n === d.interactionState.dragInProgress) { // constrain node position to the dragging pointer
                n.x = n.lastDraggedX;
                n.y = n.lastDraggedY;
            } else {
                n.vx = (n.originalX - n.x) / c.forceTicksPerFrame; // snap to layer
                n.y = Math.min(d.size - n.dy / 2, Math.max(n.dy / 2, n.y)); // constrain to extent
            }
            maxVelocity = Math.max(maxVelocity, Math.abs(n.vx), Math.abs(n.vy));
        }
        if(!d.interactionState.dragInProgress && maxVelocity < 0.1 && d.forceLayouts[forceKey].alpha() > 0) {
            d.forceLayouts[forceKey].alpha(0); // This will stop the animation loop
        }
    };
}

// basic data utilities

function persistFinalNodePositions(d, gd) {
    var x = [];
    var y = [];
    for(var i = 0; i < d.graph.nodes.length; i++) {
        var nodeX = (d.graph.nodes[i].x0 + d.graph.nodes[i].x1) / 2;
        var nodeY = (d.graph.nodes[i].y0 + d.graph.nodes[i].y1) / 2;
        x.push(nodeX / d.figure.width);
        y.push(nodeY / d.figure.height);
    }
    Registry.call('_guiRestyle', gd, {
        'node.x': [x],
        'node.y': [y]
    }, d.trace.index)
    .then(function() {
        if(gd._fullLayout._dragCover) gd._fullLayout._dragCover.remove();
    });
}

function persistOriginalPlace(nodes) {
    var distinctLayerPositions = [];
    var i;
    for(i = 0; i < nodes.length; i++) {
        nodes[i].originalX = (nodes[i].x0 + nodes[i].x1) / 2;
        nodes[i].originalY = (nodes[i].y0 + nodes[i].y1) / 2;
        if(distinctLayerPositions.indexOf(nodes[i].originalX) === -1) {
            distinctLayerPositions.push(nodes[i].originalX);
        }
    }
    distinctLayerPositions.sort(function(a, b) {return a - b;});
    for(i = 0; i < nodes.length; i++) {
        nodes[i].originalLayerIndex = distinctLayerPositions.indexOf(nodes[i].originalX);
        nodes[i].originalLayer = nodes[i].originalLayerIndex / (distinctLayerPositions.length - 1);
    }
}

function saveCurrentDragPosition(d) {
    d.lastDraggedX = d.x0 + d.dx / 2;
    d.lastDraggedY = d.y0 + d.dy / 2;
}

function sameLayer(d) {
    return function(n) {return n.node.originalX === d.node.originalX;};
}

function switchToForceFormat(nodes) {
    // force uses x, y as centers
    for(var i = 0; i < nodes.length; i++) {
        nodes[i].y = (nodes[i].y0 + nodes[i].y1) / 2;
        nodes[i].x = (nodes[i].x0 + nodes[i].x1) / 2;
    }
}

function switchToSankeyFormat(nodes) {
    // sankey uses x0, x1, y0, y1
    for(var i = 0; i < nodes.length; i++) {
        nodes[i].y0 = nodes[i].y - nodes[i].dy / 2;
        nodes[i].y1 = nodes[i].y0 + nodes[i].dy;

        nodes[i].x0 = nodes[i].x - nodes[i].dx / 2;
        nodes[i].x1 = nodes[i].x0 + nodes[i].dx;
    }
}

// scene graph
module.exports = function(gd, svg, calcData, layout, callbacks) {
    var isStatic = gd._context.staticPlot;

    // To prevent animation on first render
    var firstRender = false;
    Lib.ensureSingle(gd._fullLayout._infolayer, 'g', 'first-render', function() {
        firstRender = true;
    });

    // To prevent animation on dragging
    var dragcover = gd._fullLayout._dragCover;

    var styledData = calcData
            .filter(function(d) {return unwrap(d).trace.visible;})
            .map(sankeyModel.bind(null, layout));

    var sankey = svg.selectAll('.' + c.cn.sankey)
        .data(styledData, keyFun);

    sankey.exit()
        .remove();

    sankey.enter()
        .append('g')
        .classed(c.cn.sankey, true)
        .style('box-sizing', 'content-box')
        .style('position', 'absolute')
        .style('left', 0)
        .style('shape-rendering', 'geometricPrecision')
        .style('pointer-events', isStatic ? 'none' : 'auto')
        .attr('transform', sankeyTransform);

    sankey.each(function(d, i) {
        gd._fullData[i]._sankey = d;
        // Create dragbox if missing
        var dragboxClassName = 'bgsankey-' + d.trace.uid + '-' + i;
        Lib.ensureSingle(gd._fullLayout._draggers, 'rect', dragboxClassName);

        gd._fullData[i]._bgRect = d3.select('.' + dragboxClassName);

        // Style dragbox
        gd._fullData[i]._bgRect
          .style('pointer-events', isStatic ? 'none' : 'all')
          .attr('width', d.width)
          .attr('height', d.height)
          .attr('x', d.translateX)
          .attr('y', d.translateY)
          .classed('bgsankey', true)
          .style({fill: 'transparent', 'stroke-width': 0});
    });

    sankey.transition()
        .ease(c.ease).duration(c.duration)
        .attr('transform', sankeyTransform);

    var sankeyLinks = sankey.selectAll('.' + c.cn.sankeyLinks)
        .data(repeat, keyFun);

    sankeyLinks.enter()
        .append('g')
        .classed(c.cn.sankeyLinks, true)
        .style('fill', 'none');

    var sankeyLink = sankeyLinks.selectAll('.' + c.cn.sankeyLink)
          .data(function(d) {
              var links = d.graph.links;
              return links
                .filter(function(l) {return l.value;})
                .map(linkModel.bind(null, d));
          }, keyFun);

    sankeyLink
          .enter().append('path')
          .classed(c.cn.sankeyLink, true)
          .call(attachPointerEvents, sankey, callbacks.linkEvents);

    sankeyLink
        .style('stroke', function(d) {
            return salientEnough(d) ? Color.tinyRGB(tinycolor(d.linkLineColor)) : d.tinyColorHue;
        })
        .style('stroke-opacity', function(d) {
            return salientEnough(d) ? Color.opacity(d.linkLineColor) : d.tinyColorAlpha;
        })
        .style('fill', function(d) {
            return d.tinyColorHue;
        })
        .style('fill-opacity', function(d) {
            return d.tinyColorAlpha;
        })
        .style('stroke-width', function(d) {
            return salientEnough(d) ? d.linkLineWidth : 1;
        })
        .attr('d', linkPath());

    sankeyLink
        .style('opacity', function() { return (gd._context.staticPlot || firstRender || dragcover) ? 1 : 0;})
        .transition()
        .ease(c.ease).duration(c.duration)
        .style('opacity', 1);

    sankeyLink.exit()
        .transition()
        .ease(c.ease).duration(c.duration)
        .style('opacity', 0)
        .remove();

    var sankeyNodeSet = sankey.selectAll('.' + c.cn.sankeyNodeSet)
        .data(repeat, keyFun);

    sankeyNodeSet.enter()
        .append('g')
        .classed(c.cn.sankeyNodeSet, true);

    sankeyNodeSet
        .style('cursor', function(d) {
            switch(d.arrangement) {
                case 'fixed': return 'default';
                case 'perpendicular': return 'ns-resize';
                default: return 'move';
            }
        });

    var sankeyNode = sankeyNodeSet.selectAll('.' + c.cn.sankeyNode)
        .data(function(d) {
            var nodes = d.graph.nodes;
            persistOriginalPlace(nodes);
            return nodes
              .map(nodeModel.bind(null, d));
        }, keyFun);

    sankeyNode.enter()
        .append('g')
        .classed(c.cn.sankeyNode, true)
        .call(updateNodePositions)
        .style('opacity', function(n) { return ((gd._context.staticPlot || firstRender) && !n.partOfGroup) ? 1 : 0;});

    sankeyNode
        .call(attachPointerEvents, sankey, callbacks.nodeEvents)
        .call(attachDragHandler, sankeyLink, callbacks, gd); // has to be here as it binds sankeyLink

    sankeyNode
        .transition()
        .ease(c.ease).duration(c.duration)
        .call(updateNodePositions)
        .style('opacity', function(n) { return n.partOfGroup ? 0 : 1;});

    sankeyNode.exit()
        .transition()
        .ease(c.ease).duration(c.duration)
        .style('opacity', 0)
        .remove();

    var nodeRect = sankeyNode.selectAll('.' + c.cn.nodeRect)
        .data(repeat);

    nodeRect.enter()
        .append('rect')
        .classed(c.cn.nodeRect, true)
        .call(sizeNode);

    nodeRect
        .style('stroke-width', function(d) {return d.nodeLineWidth;})
        .style('stroke', function(d) {return Color.tinyRGB(tinycolor(d.nodeLineColor));})
        .style('stroke-opacity', function(d) {return Color.opacity(d.nodeLineColor);})
        .style('fill', function(d) {return d.tinyColorHue;})
        .style('fill-opacity', function(d) {return d.tinyColorAlpha;});

    nodeRect.transition()
        .ease(c.ease).duration(c.duration)
        .call(sizeNode);

    var nodeLabel = sankeyNode.selectAll('.' + c.cn.nodeLabel)
        .data(repeat);

    nodeLabel.enter()
        .append('text')
        .classed(c.cn.nodeLabel, true)
        .style('cursor', 'default');

    nodeLabel
        .attr('data-notex', 1) // prohibit tex interpretation until we can handle tex and regular text together
        .text(function(d) { return d.node.label; })
        .each(function(d) {
            var e = d3.select(this);
            Drawing.font(e, d.textFont);
            svgTextUtils.convertToTspans(e, gd);
        })
        .attr('text-anchor', function(d) {
            return (d.horizontal && d.left) ? 'end' : 'start';
        })
        .attr('transform', function(d) {
            var e = d3.select(this);
            // how much to shift a multi-line label to center it vertically.
            var nLines = svgTextUtils.lineCount(e);
            var blockHeight = d.textFont.size * (
                (nLines - 1) * LINE_SPACING - CAP_SHIFT
            );

            var posX = d.nodeLineWidth / 2 + TEXTPAD;
            var posY = ((d.horizontal ? d.visibleHeight : d.visibleWidth) - blockHeight) / 2;
            if(d.horizontal) {
                if(d.left) {
                    posX = -posX;
                } else {
                    posX += d.visibleWidth;
                }
            }

            var flipText = d.horizontal ? '' : (
                'scale(-1,1)' + strRotate(90)
            );

            return strTranslate(
                d.horizontal ? posX : posY,
                d.horizontal ? posY : posX
            ) + flipText;
        });

    nodeLabel
        .transition()
        .ease(c.ease).duration(c.duration);
};