import disjointSet from './disjoint-set';

// Tests whether the given array of edge objects contains an edge with
// the given endpoints (undirected). Pure function, no side effects.
export function containsEdge (array, edge) {
  for (let i = 0; i < array.length; i++) {
    const elem = array[i];
    const sameEdge = elem.nodeA === edge.nodeA && elem.nodeB === edge.nodeB;
    const symetricalEdge = elem.nodeA === edge.nodeB && elem.nodeB === edge.nodeA;

    if (sameEdge || symetricalEdge) {
      return true;
    }
  }
  return false;
}


// Returns a new array of edge objects that is a minimal spanning tree on the given set
// of nodes, with edges in ascending order of weight. Note that the returned edge objects
// are missing the opacity property. Pure function, no side effects.
export function calcSpanningTree (allEdges, nodes) {

  // Kruskal's MST algorithm
  const result = [];
  const ds = disjointSet.create(nodes.length);

  for (let i = 0; i < allEdges.length && result.length < nodes.length - 1; i++) {
    const edge = allEdges[i];
    const [, j, k] = edge;

    if (ds.mergeSets(j, k)) {
      result.push({ nodeA: nodes[j], nodeB: nodes[k] });
    }
  }

  return result;
}

// Returns a sorted array of edges with weights, for all unique edge pairs. Pure function, no side effects.
export function calcAllEdgeWeights (nodes, radiiWeightPower) {

  // Each entry has the form [weight, nodeAIndex, nodeBIndex], where nodeAIndex < nodeBIndex
  const result = [];

  for (let i = 0; i < nodes.length; i++) {  // Calculate all n * (n - 1) / 2 edges
    const nodeA = nodes[i];

    for (let j = 0; j < i; j++) {
      const nodeB = nodes[j];
      let weight = Math.hypot(nodeA.posX - nodeB.posX, nodeA.posY - nodeB.posY);  // Euclidean distance
      weight /= Math.pow(nodeA.radius * nodeB.radius, radiiWeightPower);  // Give discount based on node radii
      result.push([weight, i, j]);
    }
  }

  // Sort array by ascending weight
  return result.sort(([x], [y]) => x < y ? -1 : (x > y ? 1 : 0));
}

@@ -37,17 +37,21 @@
 set';%0A%0A/
-/
+**%0A *
  Tests w
@@ -111,18 +111,18 @@
 ge with%0A
-//
+ *
  the giv
@@ -172,32 +172,76 @@
 o side effects.%0A
+ *%0A * @type Function%0A * @return Boolean%0A */%0A
 export function 
@@ -588,17 +588,21 @@
 e;%0A%7D%0A%0A%0A/
-/
+**%0A *
  Returns
@@ -679,18 +679,18 @@
 ven set%0A
-//
+ *
  of node
@@ -769,18 +769,18 @@
 objects%0A
-//
+ *
  are mis
@@ -830,32 +830,74 @@
 o side effects.%0A
+ *%0A * @type Function%0A * @return Array%0A */%0A
 export function 
@@ -1291,17 +1291,21 @@
 lt;%0A%7D%0A%0A/
-/
+**%0A *
  Returns
@@ -1402,16 +1402,58 @@
 ffects.%0A
+ *%0A * @type Function%0A * @return Array%0A */%0A
 export f

add util docs