/*
 * Copyright 2012 LinkedIn Corp.
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */

var maxTextSize = 32;
var reductionSize = 26;
var degreeRatio = 1 / 8;
var maxHeight = 200;
var cornerGap = 10;

var idSort = function (a, b) {
  if (a.id < b.id) {
    return -1;
  }
  else if (a.id > b.id) {
    return 1;
  }
  else {
    return 0;
  }
}

function prepareLayout(nodes, hmargin, layers, nodeMap) {
  var maxLayer = 0;
  var nodeQueue = new Array();
  // Find start layers first
  for (var i = 0; i < nodes.length; ++i) {
    var node = nodes[i];
    if (node.inNodes) {
      // We sort here. Why? To keep the node drawing consistent
      node.in.sort(idSort);
    }
    else {
      // We sort here. Why? To keep it up and running.
      nodeQueue.push(node);
    }
  }
  // Sort here. To keep the node drawing consistent
  nodes.sort(idSort);

  // calculate level
  // breath first search the sucker
  var index = 0;
  while (index < nodeQueue.length) {
    var node = nodeQueue[index];
    if (node.inNodes) {
      var level = 0;
      for (var key in node.inNodes) {
        level = Math.max(level, node.inNodes[key].level);
      }
      node.level = level + 1;
    }
    else {
      node.level = 0;
    }

    if (node.outNodes) {
      for (var key in node.outNodes) {
        nodeQueue.push(node.outNodes[key]);
      }
    }
    index++;
  }

  // Assign to layers
  for (var i = 0; i < nodes.length; ++i) {
    var width = nodes[i].width ? nodes[i].width : nodes[i].label.length * 11.5
        + 4;
    var height = nodes[i].height ? nodes[i].height : 1;
    var node = {
      id: nodes[i].id,
      node: nodes[i],
      level: nodes[i].level,
      in: [],
      out: [],
      width: width + hmargin,
      x: 0,
      height: height
    };
    nodeMap[nodes[i].id] = node;
    maxLayer = Math.max(node.level, maxLayer);
    if (!layers[node.level]) {
      layers[node.level] = [];
    }

    layers[node.level].push(node);
  }

  layers.maxLayer = maxLayer;
}

function respaceGraph(nodes, edges) {

}

function layoutGraph(nodes, edges, hmargin) {
  var startLayer = [];

  var nodeMap = {};
  var layers = {};

  if (!hmargin) {
    hmargin = 8;
  }

  prepareLayout(nodes, hmargin, layers, nodeMap);
  var maxLayer = layers.maxLayer;

  // Create dummy nodes
  var edgeDummies = {};
  for (var i = 0; i < edges.length; ++i) {
    var edge = edges[i];
    var src = edges[i].from;
    var dest = edges[i].to;

    var edgeId = src + ">>" + dest;

    var srcNode = nodeMap[src];
    var destNode = nodeMap[dest];

    var lastNode = srcNode;

    var guides = [];

    for (var j = srcNode.level + 1; j < destNode.level; ++j) {
      var dummyNode = {
        level: j,
        in: [],
        x: lastNode.x,
        out: [],
        realSrc: srcNode,
        realDest: destNode,
        width: 10,
        height: 10
      };
      layers[j].push(dummyNode);
      dummyNode.in.push(lastNode);
      lastNode.out.push(dummyNode);
      lastNode = dummyNode;

      guides.push(dummyNode);
    }

    destNode.in.push(lastNode);
    lastNode.out.push(destNode);

    if (edgeDummies.length != 0) {
      edgeDummies[edgeId] = guides;
    }
  }

  spreadLayerSmart(layers[maxLayer]);
  sort(layers[maxLayer]);
  for (var i = maxLayer - 1; i >= 0; --i) {
    uncrossWithOut(layers[i]);
    sort(layers[i]);

    spreadLayerSmart(layers[i]);
  }

  // The top level can get out of alignment, so we do this kick back
  // manouver before we seriously get started sorting.
  if (maxLayer > 1) {
    uncrossWithIn(layers[1]);
    sort(layers[1]);
    spreadLayerSmart(layers[1]);

    uncrossWithOut(layers[0]);
    sort(layers[0]);
    spreadLayerSmart(layers[0]);
  }

  // Uncross down
  for (var i = 1; i <= maxLayer; ++i) {
    uncrossWithIn(layers[i]);
    sort(layers[i]);
    spreadLayerSmart(layers[i]);
  }

  // Space it vertically
  spaceVertically(layers, maxLayer);

  // Assign points to nodes
  for (var i = 0; i < nodes.length; ++i) {
    var node = nodes[i];
    var layerNode = nodeMap[node.id];
    node.x = layerNode.x;
    node.y = layerNode.y;
  }

  // Dummy node for more points.
  for (var i = 0; i < edges.length; ++i) {
    var edge = edges[i];
    var src = edges[i].from;
    var dest = edges[i].to;

    var edgeId = src + ">>" + dest;
    if (edgeDummies[edgeId] && edgeDummies[edgeId].length > 0) {
      var prevX = nodeMap[src].x;
      var destX = nodeMap[dest].x;

      var guides = [];
      var pointArray = new Array();
      pointArray.push([nodeMap[src].x, nodeMap[src].y]);
      var dummies = edgeDummies[edgeId];
      for (var j = 0; j < dummies.length; ++j) {
        var point = {x: dummies[j].x, y: dummies[j].y};
        guides.push(point);
        pointArray.push([point.x, point.y]);

        var nextX = j == dummies.length - 1 ? destX : dummies[j + 1].x;
        if (point.x != prevX && point.x != nextX) {
          // Add gap
          if ((point.x > prevX) == (point.x > nextX)) {
            guides.push({x: point.x, y: point.y + cornerGap});
            pointArray.push([point.x, point.y + cornerGap]);
          }
        }
        prevX = point.x;
      }

      pointArray.push([nodeMap[dest].x, nodeMap[dest].y]);
      edge.guides = guides;
      edge.oldpoints = pointArray;
    }
    else {
      edge.guides = null;
    }
  }
}

function spreadLayerSmart(layer) {
  var ranges = [];
  ranges.push({
    start: 0,
    end: 0,
    width: layer[0].width,
    x: layer[0].x,
    index: 0
  });
  var largestRangeIndex = -1;

  var totalX = layer[0].x;
  var totalWidth = layer[0].width;
  var count = 1;

  for (var i = 1; i < layer.length; ++i) {
    var prevRange = ranges[ranges.length - 1];
    var delta = layer[i].x - prevRange.x;

    if (delta == 0) {
      prevRange.end = i;
      prevRange.width += layer[i].width;
      totalWidth += layer[i].width;
    }
    else {
      totalWidth += Math.max(layer[i].width, delta);
      ranges.push({
        start: i,
        end: i,
        width: layer[i].width,
        x: layer[i].x,
        index: ranges.length
      });
    }

    totalX += layer[i].x;
    count++;
  }

  // Space the ranges, but place the left and right most last
  var startIndex = 0;
  var endIndex = 0;
  if (ranges.length == 1) {
    startIndex = -1;
    endIndex = 1;
  }
  else if ((ranges.length % 2) == 1) {
    var index = Math.ceil(ranges.length / 2);
    startIndex = index - 1;
    endIndex = index + 1;
  }
  else {
    var e = ranges.length / 2;
    var s = e - 1;

    var crossPointS = ranges[s].x + ranges[s].width / 2;
    var crossPointE = ranges[e].x - ranges[e].width / 2;

    if (crossPointS > crossPointE) {
      var midPoint = (ranges[s].x + ranges[e].x) / 2;
      ranges[s].x = midPoint - ranges[s].width / 2;
      ranges[e].x = midPoint + ranges[e].width / 2;
    }

    startIndex = s - 1;
    endIndex = e + 1;
  }

  for (var i = startIndex; i >= 0; --i) {
    var range = ranges[i];
    var crossPointS = range.x + range.width / 2;
    var crossPointE = ranges[i + 1].x - ranges[i + 1].width / 2;
    if (crossPointE < crossPointS) {
      range.x -= crossPointS - crossPointE;
    }
  }

  for (var i = endIndex; i < ranges.length; ++i) {
    var range = ranges[i];
    var crossPointE = range.x - range.width / 2;
    var crossPointS = ranges[i - 1].x + ranges[i - 1].width / 2;
    if (crossPointE < crossPointS) {
      range.x += crossPointS - crossPointE;
    }
  }

  for (var i = 0; i < ranges.length; ++i) {
    var range = ranges[i];
    if (range.start == range.end) {
      layer[range.start].x = range.x;
    }
    else {
      var start = range.x - range.width / 2;
      for (var j = range.start; j <= range.end; ++j) {
        layer[j].x = start + layer[j].width / 2;
        start += layer[j].width;
      }
    }
  }
}

function spaceVertically(layers, maxLayer) {
  var startY = 0;
  var startLayer = layers[0];
  var startMaxHeight = 1;
  for (var i = 0; i < startLayer.length; ++i) {
    startLayer[i].y = startY;
    startMaxHeight = Math.max(startMaxHeight, startLayer[i].height);
  }

  var minHeight = 40;
  for (var a = 1; a <= maxLayer; ++a) {
    var maxDelta = 0;
    var layer = layers[a];

    var layerMaxHeight = 1;
    for (var i = 0; i < layer.length; ++i) {
      layerMaxHeight = Math.max(layerMaxHeight, layer[i].height);

      for (var j = 0; j < layer[i].in.length; ++j) {
        var upper = layer[i].in[j];
        var delta = Math.abs(upper.x - layer[i].x);
        maxDelta = Math.max(maxDelta, delta);
      }
    }

    console.log("Max " + maxDelta);
    var calcHeight = maxDelta * degreeRatio;

    var newMinHeight = minHeight + startMaxHeight / 2 + layerMaxHeight / 2;
    startMaxHeight = layerMaxHeight;

    startY += Math.max(calcHeight, newMinHeight);
    for (var i = 0; i < layer.length; ++i) {
      layer[i].y = startY;
    }
  }
}

function uncrossWithIn(layer) {
  for (var i = 0; i < layer.length; ++i) {
    var pos = findAverage(layer[i].in);
    layer[i].x = pos;
  }
}

function findAverage(nodes) {
  var sum = 0;
  for (var i = 0; i < nodes.length; ++i) {
    sum += nodes[i].x;
  }
  return nodes.length != 0 ? sum / nodes.length : 0;
}

function uncrossWithOut(layer) {
  for (var i = 0; i < layer.length; ++i) {
    var pos = findAverage(layer[i].out);
    layer[i].x = pos;
  }
}

function sort(layer) {
  layer.sort(function (a, b) {
    return a.x - b.x;
  });
}
