// copyright (c) 2006-2008 Franz Inc, Oakland, CA - All rights reserved.
//
// The software, data and information contained herein are proprietary
// to, and comprise valuable trade secrets of, Franz, Inc.  They are
// given in confidence by Franz, Inc. pursuant to a written license
// agreement, and may be stored and used only in accordance with the terms
// of such license.
//
// Restricted Rights Legend
// ------------------------
// Use, duplication, and disclosure of the software, data and information
// contained herein by any agency, department or entity of the U.S.
// Government are subject to restrictions of Restricted Rights for
// Commercial Software developed at private expense as specified in
// DOD FAR Supplement 52.227-7013 (c) (1) (ii), as applicable.

// A very simple spring-magnet simulation for moving graphs into a
// relatively pleasant layout.

// 2d vectors with a few straightforward operations on them.
function Vec(x, y) {
  if (y == undefined) { this.x = x.x; this.y = x.y; }
  else { this.x = x; this.y = y; }
}
Vec.prototype = {
  add: function(other) {return new Vec(this.x + other.x, this.y + other.y);},
  addXY: function(x, y) {return new Vec(this.x + x, this.y + y);},
  inc: function(other) {this.x += other.x; this.y += other.y;},
  sub: function(other) {return new Vec(this.x - other.x, this.y - other.y);},
  scale: function(n) {this.x *= n; this.y *= n;},
  length: function() {return Math.sqrt(this.x * this.x + this.y * this.y);},
  lengthSquared: function() {return this.x * this.x + this.y * this.y;},
  resize: function(size, curLength) {
    if (curLength == undefined) curLength = this.length();
    if (curLength != 0) {
      this.x = size * this.x / curLength;
      this.y = size * this.y / curLength;
    }
  },
  angle: function() {
    if (this.x == 0) return this.y < 0 ? Math.PI : 0;
    var atan = Math.atan(this.y / this.x);
    return this.x < 0 ? atan + Math.PI : atan;
  }
};
Vec.dir = function(dir, length) {
  return new Vec(Math.cos(dir) * length, Math.sin(dir) * length);
}
Vec.randomPos = function(min, max) {
  return new Vec(Math.random() * (max - min) + min, Math.random() * (max - min) + min);
}

// A simulation model.
function GraphModel() {
  this.nodes = []; this.edges = [];
}

GraphModel.prototype = {
  config: {
    edgeLength: 1,
    edgeRigidity: .2,
    maxRepelDistance: 1.8,
    repelStrength: .02,
    maxDisplace: 1,
    frictionFactor: .8,
    frictionBase: .01
  },

  // Add a node to the model. The return value is what you use as the
  // first two arguments of the edge method.
  node: function(data) {
    var node = {edges: [], neighbours: [], pos: null, data: data, speed: new Vec(0, 0)};
    this.nodes.push(node);
    return node;
  },

  // Create an edge between two nodes. Multi-edges are re-used, edge
  // data is added to the forward and backward properties of edges
  // (which are arrays).
  edge: function(from, to, data) {
    // No provision for circular edges.
    if (from == to) return;
    // Don't create multiple edge objects for multi-edges, stuff
    // them all into one object.
    for (var i = 0; i < from.neighbours.length; i++) {
      if (from.neighbours[i] == to) {
        var edge = from.edges[i];
        edge[edge.from == from ? "forward" : "backward"].push(data);
        return;
      }
    }

    var edge = {from: from, to: to, forward: [data], backward: []};
    this.edges.push(edge);
    from.edges.push(edge); to.edges.push(edge);
    from.neighbours.push(to); to.neighbours.push(from);

    if (this.placed) {
      if (!from.placed && !to.placed) this.placeNodeRandom(from);
      if (!from.placed) this.placeNodeRelative(from, to);
      if (!to.placed) this.placeNodeRelative(to, from);
    }
  },

  placeNodeRelative: function(node, origin) {
    var offset = Vec.dir(Math.random() * Math.PI * 2, this.config.edgeLength);
    node.pos = origin.pos.add(offset);
    node.placed = true;
  },

  placeNodeRandom: function(node) {
    if (!node.placed) {
      node.placed = true;
      node.pos = Vec.randomPos(-1, 1);
    }
  },

  // Gives all unplaced nodes a random place.
  placeRandom: function() {
    for (var i = 0; i < this.nodes.length; i++)
      this.placeNodeRandom(this.nodes[i]);
    this.placed = true;
  },

  // Places the nodes in the model in such a way that they form a
  // snowflake-ish branching form, to minimize the amount of crossing
  // edges in the initial state.
  placeSnowflake: function() {
    var nodes = this.nodes;
    var maxValency = 0, maxNode = null;
    for (var i = 0; i < nodes.length; i++) {
      var val = nodes[i].neighbours.length;
      if (val > maxValency) {
        maxValency = val;
        maxNode = nodes[i];
      }
    }
    if (maxNode) {
      maxNode.pos = new Vec(0, 0);
      maxNode.placed = true;
      layout(maxNode, null, 1);
    }
    // Takes care of any nodes not reached from the chosen root.
    this.placeRandom();

    function layout(node, origin, length) {
      var unplaced = [];
      for (var i = 0; i < node.neighbours.length; i++) {
        if (!node.neighbours[i].placed) {
          unplaced.push(node.neighbours[i]);
          node.neighbours[i].placed = true;
        }
      }
      var facets = unplaced.length - (origin ? 1 : 0);
      var totalAngle = Math.PI * (origin ? Math.min(facets / 3, .7) : 2);
      var curAngle = origin ? origin.angle() - totalAngle / 2 : 0;
      for (var i = 0; i < unplaced.length; i++, curAngle += totalAngle / facets) {
        var dir = Vec.dir(curAngle, length);
        unplaced[i].pos = node.pos.add(dir);
        layout(unplaced[i], dir, length * 1);
      }
    }
  },

  // Run one iteration of the simulation. Return the amount of
  // 'unrest' in the model.
  run: function() {
    if (!this.placed) this.placeSnowflake();

    var unrest = 0, repelSquared = this.config.maxRepelDistance * this.config.maxRepelDistance;
    for (var i = 0, l = this.nodes.length; i < l; i++) {
      var node = this.nodes[i], neighbours = node.neighbours;
      if (!node.placed) this.placeNodeRandom(node);
      if (node.fixed) continue;
      var force = new Vec(0, 0);
      for (var j = 0; j < neighbours.length; j++) {
        var diff = node.pos.sub(neighbours[j].pos), len = diff.length(), off = this.config.edgeLength - len;
        diff.resize(off * this.config.edgeRigidity, len);
        force.inc(diff);
      }
      for (var j = 0; j < l; j++) {
        if (j == i) continue;
        var diff = node.pos.sub(this.nodes[j].pos), lenSquared = diff.lengthSquared();
        if (lenSquared > repelSquared) continue;
        var len = Math.sqrt(lenSquared);
        if (len == 0) len = diff.x = .001;
        diff.resize(this.config.repelStrength / len, len);
        force.inc(diff);
      }
      var fLength = force.length();
      if (fLength > this.config.maxDisplace)
        force.resize(this.config.maxDisplace, fLength);
      node.speed.inc(force);
      var sLength = node.speed.length(), newLength = this.config.frictionFactor * Math.max(sLength - this.config.frictionBase, 0);
      node.speed.resize(newLength, sLength);
      unrest += newLength * newLength;
    }
    for (var i = 0; i < l; i++)
      this.nodes[i].pos.inc(this.nodes[i].speed);
    return Math.sqrt(unrest / this.nodes.length);
  },

  // Get a bounding box of the nodes in the model.
  bounds: function() {
    if (!this.nodes.length) return {minX: 0, minY: 0, maxX: 0, maxY: 0};

    var minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
    for (var i = 0, l = this.nodes.length; i < l; i++) {
      var pos = this.nodes[i].pos;
      minX = Math.min(minX, pos.x); minY = Math.min(minY, pos.y);
      maxX = Math.max(maxX, pos.x); maxY = Math.max(maxY, pos.y);
    }
    return {minX: minX, maxX: maxX, minY: minY, maxY: maxY};
  }
};
