Split the current block using the invariants calculated in getInvariants.

@param invariants a map of neighbor counts to elements
@param partition the partition that is being refined
431161
private void split(Map<Invariant, SortedSet<Integer>> invariants, Partition partition) {
        int nonEmptyInvariants = invariants.keySet().size();
        if (nonEmptyInvariants > 1) {
            List<Invariant> invariantKeys = 
                    new ArrayList<Invariant>(invariants.keySet());
            partition.removeCell(currentBlockIndex);
            int k = currentBlockIndex;
            if (splitOrder == SplitOrder.REVERSE) {
                Collections.sort(invariantKeys);
            } else {
                Collections.sort(invariantKeys, Collections.reverseOrder());
            }
            for (Invariant h : invariantKeys) {
                SortedSet<Integer> setH = invariants.get(h);
                partition.insertCell(k, setH);
                blocksToRefine.add(setH);
                k++;

            }
            // skip over the newly added blocks
            currentBlockIndex += nonEmptyInvariants - 1;
        }
    }
476077
public static <T> List<Collection<T>> partitionIntoFolds(List<T> values, int numFolds) {
    List<Collection<T>> folds = new ArrayList<Collection<T>>();
    int numValues = values.size();
    int foldSize = numValues / numFolds;
    int remainder = numValues % numFolds;
    
    int start = 0;
    int end = foldSize;
    for (int foldNum = 0; foldNum < numFolds; foldNum++) {
      // if we're in the first 'remainder' folds, we get an extra item
      if (foldNum < remainder) {
        end++;
      }
      folds.add(values.subList(start, end));
      
      start = end;
      end += foldSize;
    }
    
    return folds;
  }
881017
private void getMoreSplits(Configuration conf, Path[] paths, 
                             long maxSize, long minSizeNode, long minSizeRack,
                             List<InputSplit> splits)
    throws IOException {

    // all blocks for all the files in input set
    OneFileInfo[] files;
  
    // mapping from a rack name to the list of blocks it has
    HashMap<String, List<OneBlockInfo>> rackToBlocks = 
                              new HashMap<String, List<OneBlockInfo>>();

    // mapping from a block to the nodes on which it has replicas
    HashMap<OneBlockInfo, String[]> blockToNodes = 
                              new HashMap<OneBlockInfo, String[]>();

    // mapping from a node to the list of blocks that it contains
    HashMap<String, List<OneBlockInfo>> nodeToBlocks = 
                              new HashMap<String, List<OneBlockInfo>>();
    
    files = new OneFileInfo[paths.length];
    if (paths.length == 0) {
      return; 
    }

    // populate all the blocks for all files
    long totLength = 0;
    for (int i = 0; i < paths.length; i++) {
      files[i] = new OneFileInfo(paths[i], conf, 
                                 rackToBlocks, blockToNodes, nodeToBlocks, rackToNodes);
      totLength += files[i].getLength();
    }

    ArrayList<OneBlockInfo> validBlocks = new ArrayList<OneBlockInfo>();
    ArrayList<String> nodes = new ArrayList<String>();
    long curSplitSize = 0;

    // process all nodes and create splits that are local
    // to a node. 
    for (Iterator<Map.Entry<String, 
         List<OneBlockInfo>>> iter = nodeToBlocks.entrySet().iterator(); 
         iter.hasNext();) {

      Map.Entry<String, List<OneBlockInfo>> one = iter.next();
      nodes.add(one.getKey());
      List<OneBlockInfo> blocksInNode = one.getValue();

      // for each block, copy it into validBlocks. Delete it from 
      // blockToNodes so that the same block does not appear in 
      // two different splits.
      for (OneBlockInfo oneblock : blocksInNode) {
        if (blockToNodes.containsKey(oneblock)) {
          validBlocks.add(oneblock);
          blockToNodes.remove(oneblock);
          curSplitSize += oneblock.length;

          // if the accumulated split size exceeds the maximum, then 
          // create this split.
          if (maxSize != 0 && curSplitSize >= maxSize) {
            // create an input split and add it to the splits array
            addCreatedSplit(splits, nodes, validBlocks);
            curSplitSize = 0;
            validBlocks.clear();
          }
        }
      }
      // if there were any blocks left over and their combined size is
      // larger than minSplitNode, then combine them into one split.
      // Otherwise add them back to the unprocessed pool. It is likely 
      // that they will be combined with other blocks from the 
      // same rack later on.
      if (minSizeNode != 0 && curSplitSize >= minSizeNode) {
        // create an input split and add it to the splits array
        addCreatedSplit(splits, nodes, validBlocks);
      } else {
        for (OneBlockInfo oneblock : validBlocks) {
          blockToNodes.put(oneblock, oneblock.hosts);
        }
      }
      validBlocks.clear();
      nodes.clear();
      curSplitSize = 0;
    }

    // if blocks in a rack are below the specified minimum size, then keep them
    // in 'overflow'. After the processing of all racks is complete, these 
    // overflow blocks will be combined into splits.
    ArrayList<OneBlockInfo> overflowBlocks = new ArrayList<OneBlockInfo>();
    ArrayList<String> racks = new ArrayList<String>();

    // Process all racks over and over again until there is no more work to do.
    while (blockToNodes.size() > 0) {

      // Create one split for this rack before moving over to the next rack. 
      // Come back to this rack after creating a single split for each of the 
      // remaining racks.
      // Process one rack location at a time, Combine all possible blocks that
      // reside on this rack as one split. (constrained by minimum and maximum
      // split size).

      // iterate over all racks 
      for (Iterator<Map.Entry<String, List<OneBlockInfo>>> iter = 
           rackToBlocks.entrySet().iterator(); iter.hasNext();) {

        Map.Entry<String, List<OneBlockInfo>> one = iter.next();
        racks.add(one.getKey());
        List<OneBlockInfo> blocks = one.getValue();

        // for each block, copy it into validBlocks. Delete it from 
        // blockToNodes so that the same block does not appear in 
        // two different splits.
        boolean createdSplit = false;
        for (OneBlockInfo oneblock : blocks) {
          if (blockToNodes.containsKey(oneblock)) {
            validBlocks.add(oneblock);
            blockToNodes.remove(oneblock);
            curSplitSize += oneblock.length;
      
            // if the accumulated split size exceeds the maximum, then 
            // create this split.
            if (maxSize != 0 && curSplitSize >= maxSize) {
              // create an input split and add it to the splits array
              addCreatedSplit(splits, getHosts(racks), validBlocks);
              createdSplit = true;
              break;
            }
          }
        }

        // if we created a split, then just go to the next rack
        if (createdSplit) {
          curSplitSize = 0;
          validBlocks.clear();
          racks.clear();
          continue;
        }

        if (!validBlocks.isEmpty()) {
          if (minSizeRack != 0 && curSplitSize >= minSizeRack) {
            // if there is a minimum size specified, then create a single split
            // otherwise, store these blocks into overflow data structure
            addCreatedSplit(splits, getHosts(racks), validBlocks);
          } else {
            // There were a few blocks in this rack that 
        	// remained to be processed. Keep them in 'overflow' block list. 
        	// These will be combined later.
            overflowBlocks.addAll(validBlocks);
          }
        }
        curSplitSize = 0;
        validBlocks.clear();
        racks.clear();
      }
    }

    assert blockToNodes.isEmpty();
    assert curSplitSize == 0;
    assert validBlocks.isEmpty();
    assert racks.isEmpty();

    // Process all overflow blocks
    for (OneBlockInfo oneblock : overflowBlocks) {
      validBlocks.add(oneblock);
      curSplitSize += oneblock.length;

      // This might cause an exiting rack location to be re-added,
      // but it should be ok.
      for (int i = 0; i < oneblock.racks.length; i++) {
        racks.add(oneblock.racks[i]);
      }

      // if the accumulated split size exceeds the maximum, then 
      // create this split.
      if (maxSize != 0 && curSplitSize >= maxSize) {
        // create an input split and add it to the splits array
        addCreatedSplit(splits, getHosts(racks), validBlocks);
        curSplitSize = 0;
        validBlocks.clear();
        racks.clear();
      }
    }

    // Process any remaining blocks, if any.
    if (!validBlocks.isEmpty()) {
      addCreatedSplit(splits, getHosts(racks), validBlocks);
    }
  }
721457
public void factorize(boolean checkSymmetry) throws Exception{
		if (checkSymmetry && !Property.TWELVE.isSymmetric(Q)) {
			throw new Exception("Matrix is not symmetric");
		}
		
		if(this.rescaler != null){
			double[] cn_00_original = null;
			double[] cn_2_original = null;
			double[] cn_00_scaled = null;
			double[] cn_2_scaled = null;
			if(log.isDebugEnabled()){
				cn_00_original = ColtUtils.getConditionNumberRange(new Array2DRowRealMatrix(ColtUtils.fillSubdiagonalSymmetricMatrix(Q).toArray()), Integer.MAX_VALUE);
				log.debug("cn_00_original Q before scaling: " + ArrayUtils.toString(cn_00_original));
				cn_2_original = ColtUtils.getConditionNumberRange(new Array2DRowRealMatrix(ColtUtils.fillSubdiagonalSymmetricMatrix(Q).toArray()), 2);
				log.debug("cn_2_original Q before scaling : " + ArrayUtils.toString(cn_2_original));
			}
			//scaling the Q matrix, we have:
			//Q1 = U.Q.U[T] = U.L.L[T].U[T] = (U.L).(U.L)[T] 
			//and because U is diagonal it preserves the triangular form of U.L, so
			//Q1 = U.Q.U[T] = L1.L1[T] is the new Cholesky decomposition  
			DoubleMatrix1D Uv = rescaler.getMatrixScalingFactorsSymm(Q);
			if(log.isDebugEnabled()){
				boolean checkOK = rescaler.checkScaling(ColtUtils.fillSubdiagonalSymmetricMatrix(Q), Uv, Uv);
				if(!checkOK){
					log.warn("Scaling failed (checkScaling = false)");
				}
			}
			this.U = Uv;
			this.Q = ColtUtils.diagonalMatrixMult(Uv, Q, Uv);
			if(log.isDebugEnabled()){
				cn_00_scaled = ColtUtils.getConditionNumberRange(new Array2DRowRealMatrix(ColtUtils.fillSubdiagonalSymmetricMatrix(Q).toArray()), Integer.MAX_VALUE);
				log.debug("cn_00_scaled Q after scaling : " + ArrayUtils.toString(cn_00_scaled));
				cn_2_scaled = ColtUtils.getConditionNumberRange(new Array2DRowRealMatrix(ColtUtils.fillSubdiagonalSymmetricMatrix(Q).toArray()), 2);
				log.debug("cn_2_scaled Q after scaling  : " + ArrayUtils.toString(cn_2_scaled));
				
				if(cn_00_original[0] < cn_00_scaled[0] || cn_2_original[0] < cn_2_scaled[0]){
					//log.info("Q: " + ArrayUtils.toString(ColtUtils.fillSubdiagonalSymmetricMatrix(Q).toArray()));
					log.warn("Problematic scaling");
					//throw new RuntimeException("Scaling failed");
				}
			}
		}
		
		//double threshold = Math.pow(Utils.getDoubleMachineEpsilon(), 2);
		double threshold = Utils.getDoubleMachineEpsilon();
		this.LData = new double[dim][];

		for (int i = 0; i < dim; i++) {
			LData[i] = new double[i+1];
			//DoubleMatrix1D QI = Q.viewRow(i);
			double[] LDataI = LData[i];
			//j < i
			for (int j = 0; j < i; j++) {
				double[] LDataJ = LData[j];
				double sum = 0.0;
				for (int k = 0; k < j; k++) {
					sum += LDataI[k] * LDataJ[k];
				}
				LDataI[j] = 1.0 / LDataJ[j] * (Q.getQuick(i, j) - sum);
			}
			//j==i
			double sum = 0.0;
			for (int k = 0; k < i; k++) {
				sum += Math.pow(LDataI[k], 2);
			}
			double d = Q.getQuick(i, i) - sum;
			if(!(d > threshold)){
				throw new Exception("not positive definite matrix");
			}
			LDataI[i] = Math.sqrt(d);
		}
	}
240776
private Result runOnAllPartitions(Query query) {
        PartitionIdSet mutablePartitionIds = getAllPartitionIds();

        Result result = doRunOnQueryThreads(query, mutablePartitionIds, ALL_NODES);
        if (isResultFromAnyPartitionMissing(mutablePartitionIds)) {
            doRunOnPartitionThreads(query, mutablePartitionIds, result);
        }
        assertAllPartitionsQueried(mutablePartitionIds);

        return result;
    }
717102
protected void matchPointsToClusters(List<double[]> points) {
		sumDistance = 0;
		for (int i = 0; i < points.size(); i++) {
			double[]p = points.get(i);

			// find the cluster which is closest to the point
			int bestCluster = findBestMatch(p);

			// sum up all the points which are members of this cluster
			double[] c = workClusters.get(bestCluster);
			for (int j = 0; j < c.length; j++) {
				c[j] += p[j];
			}
			memberCount.data[bestCluster]++;
			labels.data[i] = bestCluster;
			sumDistance += bestDistance;
		}
	}
747673
public int partition(int k, int minPts) {
        ArrayList<Leaf> leaves = new ArrayList<>();
        ArrayList<double[]> centers = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        for (Node node = queue.poll(); node != null; node = queue.poll()) {
            if (node.numChildren == 0) {
                if (node.n >= minPts) {
                    double[] x = new double[d];
                    for (int i = 0; i < d; i++) {
                        x[i] = node.sum[i] / node.n;
                    }
                    centers.add(x);
                    leaves.add((Leaf) node);
                } else {
                    Leaf leaf = (Leaf) node;
                    leaf.y = OUTLIER;
                }
            } else {
                for (int i = 0; i < node.numChildren; i++) {
                    queue.offer(node.children[i]);
                }
            }
        }

        int n = centers.size();
        centroids = centers.toArray(new double[n][]);

        if (n > k) {
            double[][] proximity = new double[n][];
            for (int i = 0; i < n; i++) {
                proximity[i] = new double[i + 1];
                for (int j = 0; j < i; j++) {
                    proximity[i][j] = Math.distance(centroids[i], centroids[j]);
                }
            }

            Linkage linkage = new WardLinkage(proximity);
            HierarchicalClustering hc = new HierarchicalClustering(linkage);

            int[] y = hc.partition(k);

            // recalculate the centroids of each cluster
            centroids = new double[k][d];
            int[] nc = new int[k];
            for (int i = 0; i < n; i++) {
                Leaf leaf = leaves.get(i);
                int yi = y[i];
                leaf.y = yi;
                nc[yi] += leaf.n;
                for (int j = 0; j < d; j++) {
                    centroids[yi][j] += leaf.sum[j];
                }
            }
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < d; j++) {
                    centroids[i][j] /= nc[i];
                }
            }
        } else {
            for (int i = 0; i < n; i++) {
                leaves.get(i).y = i;
            }
        }

        return n;
    }
974648
public void setPartitions(java.util.Collection<Partition> partitions) {
        if (partitions == null) {
            this.partitions = null;
            return;
        }

        this.partitions = new java.util.ArrayList<Partition>(partitions);
    }
555511
@Override
  public NumberedSplit<InputSplit> getInputSplit(final NodeDescriptor nodeDescriptor, final String evaluatorId) {
    synchronized (evaluatorToSplits) {
      if (evaluatorToSplits.containsKey(evaluatorId)) {
        LOG.log(Level.FINE, "Found an already allocated split, {0}", evaluatorToSplits.toString());
        return evaluatorToSplits.get(evaluatorId);
      }
    }
    // always first try to allocate based on the hostName
    final String hostName = nodeDescriptor.getName();
    LOG.log(Level.FINE, "Allocated split not found, trying on {0}", hostName);
    if (locationToSplits.containsKey(hostName)) {
      LOG.log(Level.FINE, "Found splits possibly hosted for {0} at {1}", new Object[] {evaluatorId, hostName});
      final NumberedSplit<InputSplit> split = allocateSplit(evaluatorId, locationToSplits.get(hostName));
      if (split != null) {
        return split;
      }
    }
    LOG.log(Level.FINE, "{0} does not host any splits or someone else took splits hosted here. Picking other ones",
        hostName);
    final NumberedSplit<InputSplit> split = tryAllocate(nodeDescriptor, evaluatorId);
    if (split == null) {
      throw new RuntimeException("Unable to find an input split to evaluator " + evaluatorId);
    } else {
      LOG.log(Level.FINE, evaluatorToSplits.toString());
    }
    return split;
  }
357091
private IntIterator getCommonSplitDimensions(N node) {
    Collection<SplitHistory> splitHistories = new ArrayList<>(node.getNumEntries());
    for(int i = 0; i < node.getNumEntries(); i++) {
      SpatialEntry entry = node.getEntry(i);
      if(!(entry instanceof XTreeDirectoryEntry)) {
        throw new RuntimeException("Wrong entry type to derive split dimension from: " + entry.getClass().getName());
      }
      splitHistories.add(((XTreeDirectoryEntry) entry).getSplitHistory());
    }
    return SplitHistory.getCommonDimensions(splitHistories);
  }
105004
public void setPartitions(java.util.Collection<String> partitions) {
        if (partitions == null) {
            this.partitions = null;
            return;
        }

        this.partitions = new com.amazonaws.internal.SdkInternalList<String>(partitions);
    }
784597
public Spliterator.OfInt statesInBlockSpliterator(Block b) {
        return Arrays.spliterator(blockData, b.low, b.high);
    }
546266
void splitEdge_(int edge1, int edge2, int intersectionCluster,
			SegmentIntersector intersector) {

		disconnectEdge_(edge1);// disconnects the edge from the clusters. The
								// edge still remembers the clusters.
		if (edge2 != -1)
			disconnectEdge_(edge2);// disconnects the edge from the clusters.
									// The edge still remembers the clusters.

		// Collect all edges that are affected when the clusters change position
		// due to snapping
		// The edges are collected in 
		// Collect the modified clusters in m_modified_clusters.
		processSplitHelper1_(0, edge1, intersector);
		if (edge2 != -1)
			processSplitHelper1_(1, edge2, intersector);

		if (intersectionCluster != -1) {
			intersector.getResultPoint().getXY(pt_1);
			getClusterXY(intersectionCluster, pt_2);
			if (!pt_2.isEqual(pt_1))
				m_modified_clusters.add(intersectionCluster);
		}

		// remove modified clusters from the event queue. We'll reincert them
		// later
		for (int i = 0, n = m_modified_clusters.size(); i < n; i++) {
			int cluster = m_modified_clusters.get(i);
			int eventQnode = getClusterEventQNode(cluster);
			if (eventQnode != -1) {
				m_event_q.deleteNode(eventQnode, -1);
				setClusterEventQNode_(cluster, -1);
			}
		}

		int edgeOrigins1 = getEdgeOriginVertices(edge1);
		int edgeOrigins2 = (edge2 != -1) ? getEdgeOriginVertices(edge2) : -1;

		// Adjust the vertex coordinates and split the segments in the the edit
		// shape.
		applyIntersectorToEditShape_(edgeOrigins1, intersector, 0);
		if (edge2 != -1)
			applyIntersectorToEditShape_(edgeOrigins2, intersector, 1);

		// Produce clusters, and new edges. The new edges are added to
		// 
		createEdgesAndClustersFromSplitEdge_(edge1, intersector, 0);
		if (edge2 != -1)
			createEdgesAndClustersFromSplitEdge_(edge2, intersector, 1);

		m_edge_vertices.deleteList(edgeOrigins1);
		deleteEdge_(edge1);

		if (edge2 != -1) {
			m_edge_vertices.deleteList(edgeOrigins2);
			deleteEdge_(edge2);
		}

		// insert clusters into the event queue and the edges into the sweep
		// structure.
		for (int i = 0, n = m_modified_clusters.size(); i < n; i++) {
			int cluster = m_modified_clusters.get(i);
			if (cluster == m_sweep_point_cluster)
				m_b_sweep_point_cluster_was_modified = true;

			int eventQnode = getClusterEventQNode(cluster);
			if (eventQnode == -1) {
				int vertex = getClusterFirstVertex(cluster);
				assert (getClusterFromVertex(vertex) == cluster);

				eventQnode = m_event_q.addUniqueElement(vertex, -1);// O(logN)
																	// operation
				if (eventQnode == -1) {// the cluster is coinciding with another
										// one. merge.
					int existingNode = m_event_q.getDuplicateElement(-1);
					int v = m_event_q.getElement(existingNode);
					assert (m_shape.isEqualXY(vertex, v));
					int existingCluster = getClusterFromVertex(v);
					mergeClusters_(existingCluster, cluster);
				} else {
					setClusterEventQNode_(cluster, eventQnode);
				}
			} else {
				// if already inserted (probably impossible) case
			}
		}

		m_modified_clusters.clear(false);
	}
647217
public static <T> Partition<T> singletons(Collection<T> nodes) {
        final Map<T, T> parents = Maps.newHashMap();
        final Map<T, Integer> ranks = Maps.newHashMap();
        for (T node : nodes) {
            parents.put(node, node); // each node is its own head
            ranks.put(node, 0); // every node has depth 0 to start
        }
        return new Partition<T>(parents, ranks);
    }
445510
public Assignments cluster(Matrix matrix, Properties props) {
        int endSize = Integer.parseInt(props.getProperty(
                NUM_CLUSTERS_END, DEFAULT_NUM_CLUSTERS_END));
        return cluster(matrix, endSize, props);
    }
806310
private void split(List<Component> mixture) {
        // Find most dispersive cluster (biggest sigma)
        Component componentToSplit = null;

        double maxSigma = 0.0;
        for (Component c : mixture) {
            if (c.distribution.sd() > maxSigma) {
                maxSigma = c.distribution.sd();
                componentToSplit = c;
            }
        }

        // Splits the component
        double delta = componentToSplit.distribution.sd();
        double mu = componentToSplit.distribution.mean();
        
        Component c = new Component();
        c.priori = componentToSplit.priori / 2;
        c.distribution = new GaussianDistribution(mu + delta/2, delta);
        mixture.add(c);
        
        c = new Component();
        c.priori = componentToSplit.priori / 2;
        c.distribution = new GaussianDistribution(mu - delta/2, delta);
        mixture.add(c);

        mixture.remove(componentToSplit);
    }
1045400
@Override
    public org.apache.hadoop.mapred.InputSplit[] getSplits(JobConf job, int numSplits) throws IOException {

        Settings settings = HadoopSettingsManager.loadFrom(job);
        Collection<PartitionDefinition> partitions = RestService.findPartitions(settings, log);
        EsInputSplit[] splits = new EsInputSplit[partitions.size()];

        int index = 0;
        for (PartitionDefinition part : partitions) {
            splits[index++] = new EsInputSplit(part);
        }
        log.info(String.format("Created [%d] splits", splits.length));
        return splits;
    }