Distributed version of tree_distance.eucdist
    Parameters: two valid newick strings and a boolean
160291
def eucdist_task(newick_string_a, newick_string_b, normalise, min_overlap=4, overlap_fail_value=0):
    
    tree_a = Tree(newick_string_a)
    tree_b = Tree(newick_string_b)
    return treedist.eucdist(tree_a, tree_b, normalise, min_overlap, overlap_fail_value)
393564
function hierarchicalClustering(options) {
  var cy = this.cy();
  var nodes = this.nodes(); // Set parameters of algorithm: linkage type, distance metric, etc.

  var opts = setOptions$2(options);
  var attrs = opts.attributes;

  var getDist = function getDist(n1, n2) {
    return clusteringDistance(opts.distance, attrs.length, function (i) {
      return attrs[i](n1);
    }, function (i) {
      return attrs[i](n2);
    });
  }; // Begin hierarchical algorithm


  var clusters = [];
  var dists = []; // distances between each pair of clusters

  var mins = []; // closest cluster for each cluster

  var index = []; // hash of all clusters by key
  // In agglomerative (bottom-up) clustering, each node starts as its own cluster

  for (var n = 0; n < nodes.length; n++) {
    var cluster = {
      value: opts.mode === 'dendrogram' ? nodes[n] : [nodes[n]],
      key: n,
      index: n
    };
    clusters[n] = cluster;
    index[n] = cluster;
    dists[n] = [];
    mins[n] = 0;
  } // Calculate the distance between each pair of clusters


  for (var i = 0; i < clusters.length; i++) {
    for (var j = 0; j <= i; j++) {
      var dist = void 0;

      if (opts.mode === 'dendrogram') {
        // modes store cluster values differently
        dist = i === j ? Infinity : getDist(clusters[i].value, clusters[j].value);
      } else {
        dist = i === j ? Infinity : getDist(clusters[i].value[0], clusters[j].value[0]);
      }

      dists[i][j] = dist;
      dists[j][i] = dist;

      if (dist < dists[i][mins[i]]) {
        mins[i] = j; // Cache mins: closest cluster to cluster i is cluster j
      }
    }
  } // Find the closest pair of clusters and merge them into a single cluster.
  // Update distances between new cluster and each of the old clusters, and loop until threshold reached.


  var merged = mergeClosest(clusters, index, dists, mins, opts);

  while (merged) {
    merged = mergeClosest(clusters, index, dists, mins, opts);
  }

  var retClusters; // Dendrogram mode builds the hierarchy and adds intermediary nodes + edges
  // in addition to returning the clusters.

  if (opts.mode === 'dendrogram') {
    retClusters = buildClustersFromTree(clusters[0], opts.dendrogramDepth, cy);
    if (opts.addDendrogram) buildDendrogram(clusters[0], cy);
  } else {
    // Regular mode simply returns the clusters
    retClusters = new Array(clusters.length);
    clusters.forEach(function (cluster, i) {
      // Clean up meta data used for clustering
      cluster.key = cluster.index = null;
      retClusters[i] = cy.collection(cluster.value);
    });
  }

  return retClusters;
}
1093664
def _scrub_composite_distance_features(distance, feature_blacklist):
    
    dist_out = []

    for i, d in enumerate(distance):
        ftrs, dist, weight = d
        new_ftrs = [x for x in ftrs if x not in feature_blacklist]
        if len(new_ftrs) > 0:
            dist_out.append([new_ftrs, dist, weight])

    return dist_out
1266863
def iter_nearest_neighbours(umis, substr_idx):
    '''
    
    '''
    for i, u in enumerate(umis, 1):
        neighbours = set()
        for idx, substr_map in substr_idx.items():
            u_sub = u[slice(*idx)]
            neighbours = neighbours.union(substr_map[u_sub])
        neighbours.difference_update(umis[:i])
        for nbr in neighbours:
            yield u, nbr
997108
def k_closest(points, k, origin=(0, 0)):
    # Time: O(k+(n-k)logk)
    # Space: O(k)
    
    heap = [(-distance(p, origin), p) for p in points[:k]]
    heapify(heap)

    """
    For every point p in points[k:],
    check if p is smaller than the root of the max heap;
    if it is, add p to heap and remove root. Reheapify.
    """
    for p in points[k:]:
        d = distance(p, origin)

        heappushpop(heap, (-d, p))  # heappushpop does conditional check
        """Same as:
            if d < -heap[0][0]:
                heappush(heap, (-d,p))
                heappop(heap)

        Note: heappushpop is more efficient than separate push and pop calls.
        Each heappushpop call takes O(logk) time.
        """

    return [p for nd, p in heap]
677850
protected void batchNN(AbstractRStarTreeNode<?, ?> node, Map<DBID, KNNHeap> knnLists) {
    if(node.isLeaf()) {
      for(int i = 0; i < node.getNumEntries(); i++) {
        SpatialEntry p = node.getEntry(i);
        for(Entry<DBID, KNNHeap> ent : knnLists.entrySet()) {
          final DBID q = ent.getKey();
          final KNNHeap knns_q = ent.getValue();
          double knn_q_maxDist = knns_q.getKNNDistance();

          DBID pid = ((LeafEntry) p).getDBID();
          // FIXME: objects are NOT accessible by DBID in a plain R-tree
          // context!
          double dist_pq = distanceFunction.distance(relation.get(pid), relation.get(q));
          tree.statistics.countDistanceCalculation();
          if(dist_pq <= knn_q_maxDist) {
            knns_q.insert(dist_pq, pid);
          }
        }
      }
    }
    else {
      ModifiableDBIDs ids = DBIDUtil.newArray(knnLists.size());
      for(DBID id : knnLists.keySet()) {
        ids.add(id);
      }
      List<DoubleDistanceEntry> entries = getSortedEntries(node, ids);
      for(DoubleDistanceEntry distEntry : entries) {
        double minDist = distEntry.distance;
        for(Entry<DBID, KNNHeap> ent : knnLists.entrySet()) {
          final KNNHeap knns_q = ent.getValue();
          double knn_q_maxDist = knns_q.getKNNDistance();

          if(minDist <= knn_q_maxDist) {
            SpatialEntry entry = distEntry.entry;
            AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID());
            batchNN(child, knnLists);
            break;
          }
        }
      }
    }
  }
1338592
function getUnicodeRange() {
  const type = NodeType.UnicodeRangeType;
  const token = tokens[pos];
  const line = token.ln;
  const column = token.col;
  let content = [];

  while (pos < tokensLength) {
    if (checkSC(pos)) content = content.concat(getSC());
    else if (checkDelim(pos)) content.push(getDelim());
    else if (checkUrange(pos)) content.push(getUrange());
    else break;
  }

  return newNode(type, content, line, column);
}
388593
def rfdist_task(newick_string_a, newick_string_b, normalise, min_overlap=4, overlap_fail_value=0):
    
    tree_a = Tree(newick_string_a)
    tree_b = Tree(newick_string_b)
    return treedist.rfdist(tree_a, tree_b, normalise, min_overlap, overlap_fail_value)
426691
def makeRandomBinaryTree(leafNodeNumber=None):
    
    while True:
        nodeNo = [-1]
        def fn():
            nodeNo[0] += 1
            if random.random() > 0.6:
                i = str(nodeNo[0])
                return BinaryTree(0.00001 + random.random()*0.8, True, fn(), fn(), i)
            else:
                return BinaryTree(0.00001 + random.random()*0.8, False, None, None, str(nodeNo[0]))
        tree = fn()
        def fn2(tree):
            if tree.internal:
                return fn2(tree.left) + fn2(tree.right)
            return 1
        if leafNodeNumber is None or fn2(tree) == leafNodeNumber:
            return tree
478777
def calculateProbableRootOfGeneTree(speciesTree, geneTree, processID=lambda x : x):
    
    #get all rooted trees
    #run dup calc on each tree
    #return tree with fewest number of dups
    if geneTree.traversalID.midEnd <= 3:
        return (0, 0, geneTree)
    checkGeneTreeMatchesSpeciesTree(speciesTree, geneTree, processID)
    l = []
    def fn(tree):
        if tree.traversalID.mid != geneTree.left.traversalID.mid and tree.traversalID.mid != geneTree.right.traversalID.mid:
            newGeneTree = moveRoot(geneTree, tree.traversalID.mid)
            binaryTree_depthFirstNumbers(newGeneTree)
            dupCount, lossCount = calculateDupsAndLossesByReconcilingTrees(speciesTree, newGeneTree, processID)
            l.append((dupCount, lossCount, newGeneTree))
        if tree.internal:
            fn(tree.left)
            fn(tree.right)
    fn(geneTree)
    l.sort()
    return l[0][2], l[0][0], l[0][1]
554230
def hamming_distance(s1, s2):
    
    if len(s1) != len(s2):
        raise ValueError("Undefined for sequences of unequal length")
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))
1141000
function distance(str1, str2, options_p) {
        /**
         * Calculate levenshtein distance of the two strings.
         *
         * @function distance
         * @param {string} str1 - the first string.
         * @param {string} str2 - the second string.
         * @param {Object} [options_p] - Additional options.
         * @param {boolean} [options_p.useCollator] - Use `Intl.Collator` for locale-sensitive string comparison.
         * @param {boolean} [options_p.full_process] - Apply basic cleanup, non-alphanumeric to whitespace etc. if true. default true
         * @param {boolean} [options_p.force_ascii] - Strip non-ascii in full_process if true (non-ascii will not become whtespace), only applied if full_process is true as well, default true
         * @param {boolean} [options_p.collapseWhitespace] - Collapse consecutive white space during full_process, default true
         * @param {string} [options_p.wildcards] - characters that will be used as wildcards if provided
         * @returns {number} - the levenshtein distance (0 and above).
         */
        var options = _clone_and_set_option_defaults(options_p);
        str1 = options.full_process ? full_process(str1, options) : str1;
        str2 = options.full_process ? full_process(str2, options) : str2;
        if (typeof options.subcost === "undefined") options.subcost = 1;
        if (options.astral) return _iLeven(str1, str2, options, _toArray);
        else return _wildLeven(str1, str2, options, _leven); // falls back to _leven if no wildcards
    }
54038
def hamming_distance(s1, s2, equality_function=operator.eq):
    
    if not len(s1) == len(s2):
        raise ValueError("String lengths are not equal")

    # Number of non-matching characters:
    return sum(not equality_function(c1, c2) for c1, c2 in zip(s1, s2))
52268
def update_sibling_distance(self, sibling_distance, dest, topic):
        """"""
        for source in six.iterkeys(sibling_distance[dest]):
            sibling_distance[dest][source][topic] = \
                dest.count_partitions(topic) - \
                source.count_partitions(topic)
        return sibling_distance
973933
private void stepClosest(KdTree.Node node , FastQueue<KdTreeResult> neighbors ) {

		if( node == null )
			return;

		checkBestDistance(node, neighbors);

		if( node.isLeaf() ) {
			return;
		}

		// select the most promising branch to investigate first
		KdTree.Node nearer,further;

		double splitValue = distance.valueAt((P)node.point, node.split );

		double targetAtSplit = distance.valueAt(target,node.split);
		if( targetAtSplit<= splitValue ) {
			nearer = node.left;
			further = node.right;
		} else {
			nearer = node.right;
			further = node.left;
		}

		stepClosest(nearer,neighbors);

		// See if it is possible for 'further' to contain a better node
		// Or if N matches have yet to be find, if it is possible to meet the maximum distance requirement
		double dx = splitValue - targetAtSplit;
		if( dx*dx <= mostDistantNeighborSq) {
			if( neighbors.size() < searchN || dx*dx < mostDistantNeighborSq) {
				stepClosest(further,neighbors);
			}
		}
	}
941202
private double getDistance(TreeNode v, TreeNode w) {
		double sizeOfNodes = getNodeSize(v) + getNodeSize(w);

		double distance = sizeOfNodes / 2
				+ configuration.getGapBetweenNodes(v, w);
		return distance;
	}
1012699
def write_newick(rootnode, 
	features=None, 
	format=1, 
	format_root_node=True,
    is_leaf_fn=None, 
    dist_formatter=None,
    support_formatter=None,
    name_formatter=None):
    
    newick = []
    leaf = is_leaf_fn if is_leaf_fn else lambda n: not bool(n.children)
    for postorder, node in rootnode.iter_prepostorder(is_leaf_fn=is_leaf_fn):
        if postorder:
            newick.append(")")
            if node.up is not None or format_root_node:
                newick.append(format_node(node, "internal", format,
                                          dist_formatter=dist_formatter,
                                          support_formatter=support_formatter,
                                          name_formatter=name_formatter))
                newick.append(_get_features_string(node, features))
        else:
            if node is not rootnode and node != node.up.children[0]:
                newick.append(",")

            if leaf(node):
                safe_name = re.sub("["+_ILEGAL_NEWICK_CHARS+"]", "_", \
                               str(getattr(node, "name")))
                newick.append(format_node(node, "leaf", format,
                              dist_formatter=dist_formatter,
                              support_formatter=support_formatter,
                              name_formatter=name_formatter))
                newick.append(_get_features_string(node, features))
            else:
                newick.append("(")

    newick.append(";")
    return ''.join(newick)