the tolerance in the first-found-first-clustered order)
359101
static boolean executeNonReciprocal(EditShape shape, double tolerance) {
		Clusterer clusterer = new Clusterer();
		clusterer.m_shape = shape;
		clusterer.m_tolerance = tolerance;
		clusterer.m_sqr_tolerance = tolerance * tolerance;
		clusterer.m_cell_size = 2 * tolerance;
		clusterer.m_inv_cell_size = 1.0 / clusterer.m_cell_size;
		return clusterer.clusterNonReciprocal_();
	}
1185667
private ConstraintNetwork[] samplingPeakCollection(HashMap<SymbolicVariableActivity, SpatialFluent> aTOsf) {



		Vector<SymbolicVariableActivity> observation = new Vector<SymbolicVariableActivity>();
		Vector<SymbolicVariableActivity> activities = new Vector<SymbolicVariableActivity>();
		for (SymbolicVariableActivity act : aTOsf.keySet()) {
			activities.add(act);
			if(act.getTemporalVariable().getEST() == act.getTemporalVariable().getLST())
				observation.add(act);
		}
		if (activities != null && !activities.isEmpty()) {

			SymbolicVariableActivity[] groundVars = activities.toArray(new SymbolicVariableActivity[activities.size()]);			
			Arrays.sort(groundVars, new ActivityComparator(true));
			Vector<ConstraintNetwork> ret = new Vector<ConstraintNetwork>();
			Vector<Vector<SymbolicVariableActivity>> overlappingAll = new Vector<Vector<SymbolicVariableActivity>>();

			// if an activity is spatially inconsistent even with itself
			for (SymbolicVariableActivity act : activities) {
				if (isConflicting(new SymbolicVariableActivity[] { act }, aTOsf)) {
					ConstraintNetwork temp = new ConstraintNetwork(null);
					temp.addVariable(act);
					ret.add(temp);
				}
			}

			// groundVars are ordered activities
			for (int i = 0; i < groundVars.length; i++) {
				Vector<SymbolicVariableActivity> overlapping = new Vector<SymbolicVariableActivity>();
				overlapping.add(groundVars[i]);
				long start = (groundVars[i]).getTemporalVariable().getEST();
				long end = (groundVars[i]).getTemporalVariable().getEET();
				Bounds intersection = new Bounds(start, end);
				for (int j = 0; j < groundVars.length; j++) {
					if (i != j) {
						start = (groundVars[j]).getTemporalVariable().getEST();
						end = (groundVars[j]).getTemporalVariable().getEET();
						Bounds nextInterval = new Bounds(start, end);
						//						 System.out.println("nextinterval: " + groundVars[j] + " " +nextInterval);
						//						 System.out.println("____________________________________");
						Bounds intersectionNew = intersection.intersectStrict(nextInterval);
						if (intersectionNew != null) {
							overlapping.add(groundVars[j]);
							if (isConflicting(overlapping.toArray(new SymbolicVariableActivity[overlapping.size()]), aTOsf)) {
								overlappingAll.add(overlapping);
								if(overlapping.containsAll(observation))
									break;
							}
							else
								intersection = intersectionNew;
						}
					}
				}
			}
			if(overlappingAll.size() > 0){
				Vector<Vector<SymbolicVariableActivity>> retActivities = new Vector<Vector<SymbolicVariableActivity>>();
				Vector<SymbolicVariableActivity>  current = overlappingAll.get(0);
				for (int i = 1; i < overlappingAll.size(); i++) {
					if(!isEqual(current, overlappingAll.get(i))){
						retActivities.add(current);
						current = overlappingAll.get(i);
					}
				}
				retActivities.add(current);

				for (Vector<SymbolicVariableActivity> actVec : retActivities) {
					ConstraintNetwork tmp = new ConstraintNetwork(null);
					for (SymbolicVariableActivity act : actVec){
						tmp.addVariable(act);
					}
					ret.add(tmp);					
				}

				//				System.out.println("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<");
				//				for (int i = 0; i < ret.size(); i++) {
				//					System.out.println("ret: " + ret);
				//				}
				//				System.out.println("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<");

				//				return new ConstraintNetwork[]{ret.size()};
				return ret.toArray(new ConstraintNetwork[ret.size()]);
			}
		}
		return (new ConstraintNetwork[0]);
	}
980034
@Reference(authors = "D. Pelleg, A. Moore", //
      title = "X-means: Extending K-means with Efficient Estimation on the Number of Clusters", //
      booktitle = "Proc. 17th Int. Conf. on Machine Learning (ICML 2000)", //
      url = "http://www.pelleg.org/shared/hp/download/xmeans.ps", //
      bibkey = "DBLP:conf/icml/PellegM00")
  public static <V extends NumberVector> double logLikelihood(Relation<V> relation, Clustering<? extends MeanModel> clustering, NumberVectorDistanceFunction<? super V> distanceFunction) {
    List<? extends Cluster<? extends MeanModel>> clusters = clustering.getAllClusters();
    // number of clusters
    final int m = clusters.size();

    // number of objects in the clustering
    int n = 0;
    // cluster sizes
    int[] n_i = new int[m];
    // total variance
    double d = 0.;
    // variances
    double[] d_i = new double[m];

    // Iterate over clusters:
    Iterator<? extends Cluster<? extends MeanModel>> it = clusters.iterator();
    for(int i = 0; it.hasNext(); ++i) {
      Cluster<? extends MeanModel> cluster = it.next();
      n += n_i[i] = cluster.size();
      d += d_i[i] = varianceOfCluster(cluster, distanceFunction, relation);
    }

    // No remaining variance, if every point is on its own:
    if(n <= m) {
      return Double.NEGATIVE_INFINITY;
    }

    // Total variance (corrected for bias)
    final double logv = FastMath.log(d / (n - m));

    final int dim = RelationUtil.dimensionality(relation);
    // log likelihood of this clustering
    double logLikelihood = 0.;

    // Aggregate
    for(int i = 0; i < m; i++) {
      logLikelihood += n_i[i] * FastMath.log(n_i[i]) // Post. entropy Rn log Rn
          - n_i[i] * .5 * MathUtil.LOGTWOPI // Rn/2 log2pi
          - n_i[i] * dim * .5 * logv // Rn M/2 log sigma^2
          - (d_i[i] - m) * .5; // (Rn-K)/2
    }
    logLikelihood -= n * FastMath.log(n); // Prior entropy, sum_i Rn log R
    return logLikelihood;
  }
1002829
Node<E> first() {
        restartFromHead:
        for (;;)
            for (Node<E> h = head, p = h, q;;) {
                if ((q = p.prev) != null &&
                    (q = (p = q).prev) != null)
                    // Check for head updates every other hop.
                    // If p == q, we are sure to follow head instead.
                    p = (h != (h = head)) ? h : q;
                else if (p == h
                         // It is possible that p is PREV_TERMINATOR,
                         // but if so, the CAS is guaranteed to fail.
                         || HEAD.compareAndSet(this, h, p))
                    return p;
                else
                    continue restartFromHead;
            }
    }
946297
public static int cusolverSpScsreigvsiHost(
        cusolverSpHandle handle, 
        int m, 
        int nnz, 
        cusparseMatDescr descrA, 
        Pointer csrValA, 
        Pointer csrRowPtrA, 
        Pointer csrColIndA, 
        float mu0, 
        Pointer x0, 
        int maxite, 
        float tol, 
        Pointer mu, 
        Pointer x)
    {
        return checkResult(cusolverSpScsreigvsiHostNative(handle, m, nnz, descrA, csrValA, csrRowPtrA, csrColIndA, mu0, x0, maxite, tol, mu, x));
    }
329343
private int[] priority(int focus, IAtom[] atoms, int n) {
        int[] rank = new int[n];
        for (int i = 0; i < n; i++)
            rank[i] = i;
        for (int j = 1; j < n; j++) {
            int v = rank[j];
            int i = j - 1;
            while ((i >= 0) && hasPriority(focus, atomToIndex.get(atoms[v]), atomToIndex.get(atoms[rank[i]]))) {
                rank[i + 1] = rank[i--];
            }
            rank[i + 1] = v;
        }
        return rank;
    }
333782
def robust_partition_all(n, iterable):
    
    it = iter(iterable)
    while True:
        x = []
        for _ in range(n):
            try:
                x.append(next(it))
            except StopIteration:
                yield x
                # Omitting this StopIteration results in a segfault!
                raise StopIteration
        yield x
1171464
function(array, nodesToMove,
                                                   insertDepth) {
    var firstNode = array.length - 2;
    var nextNode = array.length - 1;
    var currentDepth = (insertDepth == 1) ? 2 : 1;
    var nodesLeftToMove = (insertDepth == 1) ? nodesToMove - 2 : nodesToMove;
    var availableNodes, lastNode, offset, i;

    for (availableNodes = currentDepth << 1;
         availableNodes > 0;
         currentDepth++) {
      lastNode = firstNode;
      firstNode = (firstNode <= nodesToMove) ? firstNode : first (array, lastNode - 1, nodesToMove);

      offset = 0;
      if (currentDepth >= insertDepth) {
        offset = Math.min (nodesLeftToMove, 1 << (currentDepth - insertDepth));
      } else if (currentDepth == (insertDepth - 1)) {
        offset = 1;
        if ((array[firstNode]) == lastNode) {
          firstNode++;
        }
      }

      for (i = availableNodes - (lastNode - firstNode + offset); i > 0; i--) {
        array[nextNode--] = currentDepth;
      }

      nodesLeftToMove -= offset;
      availableNodes = (lastNode - firstNode + offset) << 1;
    }
  }
244623
private double evaluateClusters(ArrayList<PROCLUSCluster> clusters, long[][] dimensions, Relation<V> database) {
    double result = 0;
    for(int i = 0; i < dimensions.length; i++) {
      PROCLUSCluster c_i = clusters.get(i);
      double[] centroid_i = c_i.centroid;

      long[] dims_i = dimensions[i];
      double w_i = 0;
      for(int d = BitsUtil.nextSetBit(dims_i, 0); d >= 0; d = BitsUtil.nextSetBit(dims_i, d + 1)) {
        w_i += avgDistance(centroid_i, c_i.objectIDs, database, d);
      }

      w_i /= dimensions.length;
      result += c_i.objectIDs.size() * w_i;
    }

    return result / database.size();
  }
1092413
private Clustering<SubspaceModel> computeClusters(Relation<V> database, DiSHClusterOrder clusterOrder) {
    final int dimensionality = RelationUtil.dimensionality(database);

    // extract clusters
    Object2ObjectOpenCustomHashMap<long[], List<ArrayModifiableDBIDs>> clustersMap = extractClusters(database, clusterOrder);
    logClusterSizes("Step 1: extract clusters", dimensionality, clustersMap);

    // check if there are clusters < minpts
    checkClusters(database, clustersMap);
    logClusterSizes("Step 2: check clusters", dimensionality, clustersMap);

    // sort the clusters
    List<Cluster<SubspaceModel>> clusters = sortClusters(database, clustersMap);
    if(LOG.isVerbose()) {
      StringBuilder msg = new StringBuilder("Step 3: sort clusters");
      for(Cluster<SubspaceModel> c : clusters) {
        msg.append('\n').append(BitsUtil.toStringLow(c.getModel().getSubspace().getDimensions(), dimensionality)).append(" ids ").append(c.size());
      }
      LOG.verbose(msg.toString());
    }

    // build the hierarchy
    Clustering<SubspaceModel> clustering = new Clustering<>("DiSH clustering", "dish-clustering");
    buildHierarchy(database, clustering, clusters, dimensionality);
    if(LOG.isVerbose()) {
      StringBuilder msg = new StringBuilder("Step 4: build hierarchy");
      for(Cluster<SubspaceModel> c : clusters) {
        msg.append('\n').append(BitsUtil.toStringLow(c.getModel().getSubspace().getDimensions(), dimensionality)).append(" ids ").append(c.size());
        for(It<Cluster<SubspaceModel>> iter = clustering.getClusterHierarchy().iterParents(c); iter.valid(); iter.advance()) {
          msg.append("\n   parent ").append(iter.get());
        }
        for(It<Cluster<SubspaceModel>> iter = clustering.getClusterHierarchy().iterChildren(c); iter.valid(); iter.advance()) {
          msg.append("\n   child ").append(iter.get());
        }
      }
      LOG.verbose(msg.toString());
    }

    // build result
    for(Cluster<SubspaceModel> c : clusters) {
      if(clustering.getClusterHierarchy().numParents(c) == 0) {
        clustering.addToplevelCluster(c);
      }
    }
    return clustering;
  }
1053771
function(points, firstPoint, lastPoint, tolerance){
                var maxDistance = 0;
                var indexFarthest = 0;
    
                for (var index = firstPoint, distance; index < lastPoint; index++) {
                    distance = perpendicularDistance(points[firstPoint], points[lastPoint], points[index]);
                    if (distance > maxDistance) {
                        maxDistance = distance;
                        indexFarthest = index;
                    }
                }
    
                if (maxDistance > tolerance && indexFarthest != firstPoint) {
                    //Add the largest point that exceeds the tolerance
                    pointIndexsToKeep.push(indexFarthest);
                    douglasPeuckerReduction(points, firstPoint, indexFarthest, tolerance);
                    douglasPeuckerReduction(points, indexFarthest, lastPoint, tolerance);
                }
            }
664698
private void moveAtFirst(int n_from) {
		int eT = elements[0];
		int eF = elements[n_from];
		positions[eT] = -1;
		positions[eF] = 0;
		elements[0] = eF;
		elements[n_from] = -1;
	}
127092
def k_modes(X, n_clusters, max_iter, dissim, init, n_init, verbose, random_state, n_jobs):
    """"""
    random_state = check_random_state(random_state)
    if sparse.issparse(X):
        raise TypeError("k-modes does not support sparse data.")

    X = check_array(X, dtype=None)

    # Convert the categorical values in X to integers for speed.
    # Based on the unique values in X, we can make a mapping to achieve this.
    X, enc_map = encode_features(X)

    n_points, n_attrs = X.shape
    assert n_clusters <= n_points, "Cannot have more clusters ({}) " \
                                   "than data points ({}).".format(n_clusters, n_points)

    # Are there more n_clusters than unique rows? Then set the unique
    # rows as initial values and skip iteration.
    unique = get_unique_rows(X)
    n_unique = unique.shape[0]
    if n_unique <= n_clusters:
        max_iter = 0
        n_init = 1
        n_clusters = n_unique
        init = unique

    results = []
    seeds = random_state.randint(np.iinfo(np.int32).max, size=n_init)
    if n_jobs == 1:
        for init_no in range(n_init):
            results.append(k_modes_single(X, n_clusters, n_points, n_attrs, max_iter,
                                          dissim, init, init_no, verbose, seeds[init_no]))
    else:
        results = Parallel(n_jobs=n_jobs, verbose=0)(
            delayed(k_modes_single)(X, n_clusters, n_points, n_attrs, max_iter,
                                    dissim, init, init_no, verbose, seed)
            for init_no, seed in enumerate(seeds))
    all_centroids, all_labels, all_costs, all_n_iters = zip(*results)

    best = np.argmin(all_costs)
    if n_init > 1 and verbose:
        print("Best run was number {}".format(best + 1))

    return all_centroids[best], enc_map, all_labels[best], \
        all_costs[best], all_n_iters[best]
938951
public void process(Clustering<?> result1, Clustering<?> result2) {
    // Get the clusters
    final List<? extends Cluster<?>> cs1 = result1.getAllClusters();
    final List<? extends Cluster<?>> cs2 = result2.getAllClusters();

    // Initialize
    size1 = cs1.size();
    size2 = cs2.size();
    contingency = new int[size1 + 2][size2 + 2];
    noise1 = BitsUtil.zero(size1);
    noise2 = BitsUtil.zero(size2);

    // Fill main part of matrix
    {
      final Iterator<? extends Cluster<?>> it2 = cs2.iterator();
      for(int i2 = 0; it2.hasNext(); i2++) {
        final Cluster<?> c2 = it2.next();
        if(c2.isNoise()) {
          BitsUtil.setI(noise2, i2);
        }
        contingency[size1 + 1][i2] = c2.size();
        contingency[size1 + 1][size2] += c2.size();
      }
    }
    final Iterator<? extends Cluster<?>> it1 = cs1.iterator();
    for(int i1 = 0; it1.hasNext(); i1++) {
      final Cluster<?> c1 = it1.next();
      if(c1.isNoise()) {
        BitsUtil.setI(noise1, i1);
      }
      final DBIDs ids = DBIDUtil.ensureSet(c1.getIDs());
      contingency[i1][size2 + 1] = c1.size();
      contingency[size1][size2 + 1] += c1.size();

      final Iterator<? extends Cluster<?>> it2 = cs2.iterator();
      for(int i2 = 0; it2.hasNext(); i2++) {
        final Cluster<?> c2 = it2.next();
        int count = DBIDUtil.intersectionSize(ids, c2.getIDs());
        contingency[i1][i2] = count;
        contingency[i1][size2] += count;
        contingency[size1][i2] += count;
        contingency[size1][size2] += count;
      }
    }
  }
45809
private static boolean cs_vcount(Dcs A, Dcss S) {
        int i, k, p, pa, n = A.n, m = A.m, Ap[] = A.p, Ai[] = A.i, next[], head[], tail[], nque[], pinv[], leftmost[], w[], parent[] = S.parent;
        S.pinv = pinv = new int[m + n]; /* allocate pinv, */
        S.leftmost = leftmost = new int[m]; /* and leftmost */
        w = new int[m + 3 * n]; /* get workspace */
        next = w;
        head = w;
        int head_offset = m;
        tail = w;
        int tail_offset = m + n;
        nque = w;
        int nque_offset = m + 2 * n;
        for (k = 0; k < n; k++)
            head[head_offset + k] = -1; /* queue k is empty */
        for (k = 0; k < n; k++)
            tail[tail_offset + k] = -1;
        for (k = 0; k < n; k++)
            nque[nque_offset + k] = 0;
        for (i = 0; i < m; i++)
            leftmost[i] = -1;
        for (k = n - 1; k >= 0; k--) {
            for (p = Ap[k]; p < Ap[k + 1]; p++) {
                leftmost[Ai[p]] = k; /* leftmost[i] = min(find(A(i,:)))*/
            }
        }
        for (i = m - 1; i >= 0; i--) /* scan rows in reverse order */
        {
            pinv[i] = -1; /* row i is not yet ordered */
            k = leftmost[i];
            if (k == -1)
                continue; /* row i is empty */
            if (nque[nque_offset + k]++ == 0)
                tail[tail_offset + k] = i; /* first row in queue k */
            next[i] = head[head_offset + k]; /* put i at head of queue k */
            head[head_offset + k] = i;
        }
        S.lnz = 0;
        S.m2 = m;
        for (k = 0; k < n; k++) /* find row permutation and nnz(V)*/
        {
            i = head[head_offset + k]; /* remove row i from queue k */
            S.lnz++; /* count V(k,k) as nonzero */
            if (i < 0)
                i = S.m2++; /* add a fictitious row */
            pinv[i] = k; /* associate row i with V(:,k) */
            if (--nque[nque_offset + k] <= 0)
                continue; /* skip if V(k+1:m,k) is empty */
            S.lnz += nque[nque_offset + k]; /* nque [nque_offset+k] is nnz (V(k+1:m,k)) */
            if ((pa = parent[k]) != -1) /* move all rows to parent of k */
            {
                if (nque[nque_offset + pa] == 0)
                    tail[tail_offset + pa] = tail[tail_offset + k];
                next[tail[tail_offset + k]] = head[head_offset + pa];
                head[head_offset + pa] = next[i];
                nque[nque_offset + pa] += nque[nque_offset + k];
            }
        }
        for (i = 0; i < m; i++)
            if (pinv[i] < 0)
                pinv[i] = k++;
        w = null;
        return (true);
    }
115094
private static int[] allocateShardsToNodes(int numShards, int numNodes, List<Set<Integer>> weightPerServer) {
      int[] shardsPerServer = new int[numNodes];
      Iterator<Integer> cyclicNodeIterator = Stream.iterate(0, i -> (i + 1) % numNodes).iterator();
      while (numShards > 0) {
         int slot = cyclicNodeIterator.next();
         if (!weightPerServer.get(slot).isEmpty()) {
            shardsPerServer[slot]++;
            numShards--;
         }
      }
      return shardsPerServer;
   }
756883
private void setInitialPartitions(double[][] pointArray, int k) {
		if (pointArray.length < k) {
			System.err.println("cannot cluster less than k points into k clusters...");
			System.exit(0);
		}
		
		// select randomly k initial means
		// TODO: choose more stable initialization (comment: this is run several times (with different random seeds), i.e. the worst case should not occur)
        Random random = new Random(randomSeed);
		TreeSet<Integer> usedPoints = new TreeSet<Integer>();
		int nextIndex;
		for (int i = 0; i < k; i++) {
			nextIndex = ((Double)(Math.floor(random.nextDouble() * n))).intValue();
			if (usedPoints.contains(nextIndex)) {
				i--;
				continue;
			} else {
				for (int d = 0; d < dim; d++) {
					clusterMeans[i][d] = pointArray[nextIndex][d];
				}
			}
		}
		
		// set pCgivenX=1 for the closest C for each point
		int minDistIndex = 0;
		double minDist, currentDist;
		for (int x = 0; x < pointArray.length; x++) {
			minDist = Double.MAX_VALUE;
			for (int i = 0; i < k; i++) {
				currentDist = euclideanDistance(clusterMeans[i], pointArray[x]);
				if (currentDist < minDist) {
					minDist = currentDist;
					minDistIndex = i;
				}
			}
			pCgivenX[minDistIndex][x] = 1.0;
		}
	}