Find the prototypes.

@param dq Distance query
@param cx First set
@param cy Singleton object
@param prototype Prototype output variable
@return New best distance
978501
private static double findPrototypeSingleton(DistanceQuery<?> dq, DBIDs cx, DBIDRef cy, DBIDVar prototype) {
    double maxDisty = 0., minMaxDist = Double.POSITIVE_INFINITY;
    for(DBIDIter i = cx.iter(); i.valid(); i.advance()) {
      // Maximum distance of i to the element in cy
      double maxDist = dq.distance(i, cy);
      // Maximum of distances from cy.
      maxDisty = (maxDist > maxDisty) ? maxDist : maxDisty;
      if(maxDist >= minMaxDist) {
        // We know a better solution already.
        continue;
      }
      // Maximum distance of i to all other elements in cx
      maxDist = findMax(dq, i, cx, maxDist, minMaxDist);

      if(maxDist < minMaxDist) {
        minMaxDist = maxDist;
        prototype.set(i);
      }
    }
    // Singleton point.
    if(maxDisty < minMaxDist) {
      minMaxDist = maxDisty;
      prototype.set(cy);
    }
    return minMaxDist;
  }
1021138
protected void precomputeInterestingRadii(DBIDs ids, RangeQuery<O> rangeQuery, WritableDataStore<DoubleIntArrayList> interestingDistances) {
    FiniteProgress progressPreproc = LOG.isVerbose() ? new FiniteProgress("LOCI preprocessing", ids.size(), LOG) : null;
    for(DBIDIter iditer = ids.iter(); iditer.valid(); iditer.advance()) {
      DoubleDBIDList neighbors = rangeQuery.getRangeForDBID(iditer, rmax);
      // build list of critical distances
      DoubleIntArrayList cdist = new DoubleIntArrayList(neighbors.size() << 1);
      {
        int i = 0;
        DoubleDBIDListIter ni = neighbors.iter();
        while(ni.valid()) {
          final double curdist = ni.doubleValue();
          ++i;
          ni.advance();
          // Skip, if tied to the next object:
          if(ni.valid() && curdist == ni.doubleValue()) {
            continue;
          }
          cdist.append(curdist, i);
          // Scale radius, and reinsert
          if(alpha != 1.) {
            final double ri = curdist / alpha;
            if(ri <= rmax) {
              cdist.append(ri, Integer.MIN_VALUE);
            }
          }
        }
      }
      cdist.sort();

      // fill the gaps to have fast lookups of number of neighbors at a given
      // distance.
      int lastk = 0;
      for(int i = 0, size = cdist.size(); i < size; i++) {
        final int k = cdist.getInt(i);
        if(k == Integer.MIN_VALUE) {
          cdist.setValue(i, lastk);
        }
        else {
          lastk = k;
        }
      }
      // TODO: shrink the list, removing duplicate radii?

      interestingDistances.put(iditer, cdist);
      LOG.incrementProcessed(progressPreproc);
    }
    LOG.ensureCompleted(progressPreproc);
  }
515645
public Coordinate nearest(Coordinate c) {
		double len = this.getLength();

		double u = (c.getX() - this.c1.getX()) * (this.c2.getX() - this.c1.getX()) + (c.getY() - this.c1.getY())
				* (this.c2.getY() - this.c1.getY());
		u = u / (len * len);

		if (u < 0.00001 || u > 1) {
			// Shortest point not within LineSegment, so take closest end-point.
			LineSegment ls1 = new LineSegment(c, this.c1);
			LineSegment ls2 = new LineSegment(c, this.c2);
			double len1 = ls1.getLength();
			double len2 = ls2.getLength();
			if (len1 < len2) {
				return this.c1;
			}
			return this.c2;
		} else {
			// Intersecting point is on the line, use the formula: P = P1 + u (P2 - P1)
			double x1 = this.c1.getX() + u * (this.c2.getX() - this.c1.getX());
			double y1 = this.c1.getY() + u * (this.c2.getY() - this.c1.getY());
			return new Coordinate(x1, y1);
		}
	}
794076
public List<Pair<Double, Integer>> queryWithDistances(INDArray query, int numResults) {
            return RPUtils.queryAllWithDistances(query,X,Arrays.asList(this),numResults,similarityFunction);
    }
880562
public void prepareTriangulation( TriangulationContext<?> tcx )
    {
        int hint = _points.size();
        if(_steinerPoints != null) {
            hint += _steinerPoints.size();
        }
        if( _holes != null ) {
            for (Polygon p : _holes) {
                hint += p.pointCount();
            }
        }
        HashMap<TriangulationPoint, TriangulationPoint> uniquePts = new HashMap<TriangulationPoint, TriangulationPoint>(hint);
        TriangulationPoint.mergeInstances(uniquePts, _points);
        if(_steinerPoints != null) {
            TriangulationPoint.mergeInstances(uniquePts, _steinerPoints);
        }
        if( _holes != null ) {
            for (Polygon p : _holes) {
                TriangulationPoint.mergeInstances(uniquePts, p._points);
            }
        }
        if( m_triangles == null )
        {
            m_triangles = new ArrayList<DelaunayTriangle>( _points.size() );
        }
        else
        {
            m_triangles.clear();
        }

        // Outer constraints
        for( int i = 0; i < _points.size()-1 ; i++ )
        {
            tcx.newConstraint( _points.get( i ), _points.get( i+1 ) );
        }
        tcx.newConstraint( _points.get( 0 ), _points.get( _points.size()-1 ) );

        // Hole constraints
        if( _holes != null )
        {
            for( Polygon p : _holes )
            {
                for( int i = 0; i < p._points.size()-1 ; i++ )
                {
                    tcx.newConstraint( p._points.get( i ), p._points.get( i+1 ) );
                }
                tcx.newConstraint( p._points.get( 0 ), p._points.get( p._points.size()-1 ) );            
            }
        }
        tcx.addPoints(uniquePts.keySet());
    }
1180854
protected void setRegion(float cx, float cy) {
		x0 = cx - radius;
		y0 = cy - radius;

		if( x0 < 0 ) { x0 = 0;}
		else if( x0+width > image.width ) { x0 = image.width-width; }
		if( y0 < 0 ) { y0 = 0;}
		else if( y0+width > image.height ) { y0 = image.height-width; }

	}
227425
protected static void initializeDistanceMatrix(MatrixParadigm mat, DistanceQuery<?> dq, Linkage linkage) {
    final DBIDArrayIter ix = mat.ix, iy = mat.iy;
    final double[] matrix = mat.matrix;
    final boolean issquare = dq.getDistanceFunction().isSquared();
    FiniteProgress prog = LOG.isVerbose() ? new FiniteProgress("Distance matrix computation", matrix.length, LOG) : null;
    int pos = 0;
    for(ix.seek(0); ix.valid(); ix.advance()) {
      final int x = ix.getOffset();
      assert (pos == MatrixParadigm.triangleSize(x));
      for(iy.seek(0); iy.getOffset() < x; iy.advance()) {
        matrix[pos++] = linkage.initial(dq.distance(ix, iy), issquare);
      }
      if(prog != null) {
        prog.setProcessed(pos, LOG);
      }
    }
    // Avoid logging errors in case scratch space was too large:
    if(prog != null) {
      prog.setProcessed(matrix.length, LOG);
    }
    LOG.ensureCompleted(prog);
  }
555804
public StreamVariantsRequest getStreamVariantsRequest(StreamVariantsRequest prototype) {
    return StreamVariantsRequest.newBuilder(prototype)
        .setReferenceName(referenceName)
        .setStart(start)
        .setEnd(end)
        .build();
  }
382856
def _resolve_qualifiers(self, new_quals, inherited_quals, new_class,
                            super_class, obj_name, obj_type, qualifier_repo,
                            propagate=False, verbose=False):
        
        superclassname = super_class.classname if super_class else None

        # TODO Diagnostic we will keep until really sure of this code
        if verbose:
            print("\nRESOLVE sc_name=%s nc_name=%s, obj_name=%s obj_type=%s "
                  "  propagate=%s" %
                  (superclassname, new_class.classname, obj_name, obj_type,
                   propagate))
            print('\nNEW QUAL')
            for q, qv in new_quals.items():
                print('  %s: %r' % (q, qv))
            print('INHERITEDQ:')
            if inherited_quals:
                for q, qv in inherited_quals.items():
                    print('  %s: %r' % (q, qv))

        # If propagate flag not set, initialize the qualfiers
        # by setting flavor defaults and propagated False
        if not propagate:
            for qname, qvalue in new_quals.items():
                self._init_qualifier(qvalue, qualifier_repo)
            return

        # resolve qualifiers not in inherited object
        for qname, qvalue in new_quals.items():
            if not inherited_quals or qname not in inherited_quals:
                self._init_qualifier(qvalue, qualifier_repo)

        # resolve qualifiers from inherited object
        for inh_qname, inh_qvalue in inherited_quals.items():
            if inh_qvalue.tosubclass:
                if inh_qvalue.overridable:
                    # if not in new quals, copy it to the new quals, else ignore
                    if inh_qname not in new_quals:
                        new_quals[inh_qname] = inherited_quals[inh_qname].copy()
                        new_quals[inh_qname].propagated = True
                    else:
                        new_quals[inh_qname].propagated = False
                        self._init_qualifier(new_quals[inh_qname],
                                             qualifier_repo)

                else:  # not overridable
                    if inh_qname in new_quals:
                        # allow for same qualifier def in subclass
                        # TODO should more than value match here.??
                        if new_quals[inh_qname].value != \
                                inherited_quals[inh_qname].value:
                            raise CIMError(
                                CIM_ERR_INVALID_PARAMETER,
                                _format("Invalid new_class {0!A}:{1!A} "
                                        "qualifier {2!A}. "
                                        "in class {3!A}. Not overridable ",
                                        obj_type, obj_name, inh_qname,
                                        new_class.classname))
                        else:
                            new_quals[inh_qname].propagated = True

                    else:  # not in new class, add it
                        new_quals[inh_qname] = inherited_quals[inh_qname].copy()
                        new_quals[inh_qname].propagated = True

            else:  # not tosubclass, i.e. restricted.
                if inh_qname in new_quals:
                    if inh_qvalue.overridable or inh_qvalue.overridable is None:
                        new_quals[inh_qname].propagated = True

                    else:
                        raise CIMError(
                            CIM_ERR_INVALID_PARAMETER,
                            _format("Invalid qualifier object {0!A} qualifier "
                                    "{1!A} . Restricted in super class {2!A}",
                                    obj_name, inh_qname, superclassname))
135515
private Query getFKQuery(Object obj, ClassDescriptor cld, CollectionDescriptor cds)
    {
        Query fkQuery;
        QueryByCriteria fkQueryCrit;

        if (cds.isMtoNRelation())
        {
            fkQueryCrit = getFKQueryMtoN(obj, cld, cds);
        }
        else
        {
            fkQueryCrit = getFKQuery1toN(obj, cld, cds);
        }

        // check if collection must be ordered
        if (!cds.getOrderBy().isEmpty())
        {
            Iterator iter = cds.getOrderBy().iterator();
            while (iter.hasNext())
            {
                fkQueryCrit.addOrderBy((FieldHelper)iter.next());
            }
        }

        // BRJ: customize the query
        if (cds.getQueryCustomizer() != null)
        {
            fkQuery = cds.getQueryCustomizer().customizeQuery(obj, pb, cds, fkQueryCrit);
        }
        else
        {
            fkQuery = fkQueryCrit;
        }

        return fkQuery;
    }
587096
@SuppressWarnings("unchecked")
  public static <O> KNNQuery<O> getLinearScanKNNQuery(DistanceQuery<O> distanceQuery) {
    // Slight optimizations of linear scans
    if(distanceQuery instanceof PrimitiveDistanceQuery) {
      final PrimitiveDistanceQuery<O> pdq = (PrimitiveDistanceQuery<O>) distanceQuery;
      if(EuclideanDistanceFunction.STATIC.equals(pdq.getDistanceFunction())) {
        final PrimitiveDistanceQuery<NumberVector> ndq = (PrimitiveDistanceQuery<NumberVector>) pdq;
        return (KNNQuery<O>) new LinearScanEuclideanDistanceKNNQuery<>(ndq);
      }
      return new LinearScanPrimitiveDistanceKNNQuery<>(pdq);
    }
    return new LinearScanDistanceKNNQuery<>(distanceQuery);
  }
63473
public static Type protoType(Descriptor descriptor) {
    return Type.getType('L' + JavaQualifiedNames.getClassName(descriptor).replace('.', '/') + ';');
  }
218688
public double distanceSqCorner( Point2D_F64 p ) {
		double best = Double.MAX_VALUE;
		for (int i = 0; i < 4; i++) {
			double d = square.get(i).distance2(p);
			if( d < best ) {
				best = d;
			}
		}
		return best;
	}
995579
@Override
    public DMatrixRMaj getQ(DMatrixRMaj Q , boolean compact ) {
        if( compact ) {
            if( Q == null ) {
                Q = CommonOps_DDRM.identity(numRows,minLength);
            } else {
                if( Q.numRows != numRows || Q.numCols != minLength ) {
                    throw new IllegalArgumentException("Unexpected matrix dimension.");
                } else {
                    CommonOps_DDRM.setIdentity(Q);
                }
            }
        } else {
            if( Q == null ) {
                Q = CommonOps_DDRM.identity(numRows);
            } else {
                if( Q.numRows != numRows || Q.numCols != numRows ) {
                    throw new IllegalArgumentException("Unexpected matrix dimension.");
                } else {
                    CommonOps_DDRM.setIdentity(Q);
                }
            }
        }

        // Unlike applyQ() this takes advantage of zeros in the identity matrix
        // by not multiplying across all rows.
        for( int j = minLength-1; j >= 0; j-- ) {
            int diagIndex = j*numRows+j;
            double before = QR.data[diagIndex];
            QR.data[diagIndex] = 1;
            QrHelperFunctions_DDRM.rank1UpdateMultR(Q, QR.data, j * numRows, gammas[j], j, j, numRows, v);
            QR.data[diagIndex] = before;
        }

        return Q;
    }
1273339
public PointerHierarchyRepresentationResult run(Database db, Relation<O> relation) {
    DistanceQuery<O> dq = db.getDistanceQuery(relation, getDistanceFunction());
    ArrayDBIDs ids = DBIDUtil.ensureArray(relation.getDBIDs());
    final int size = ids.size();

    if(size > 0x10000) {
      throw new AbortException("This implementation does not scale to data sets larger than " + 0x10000 + " instances (~17 GB RAM), which results in an integer overflow.");
    }
    if(Linkage.SINGLE.equals(linkage)) {
      LOG.verbose("Notice: SLINK is a much faster algorithm for single-linkage clustering!");
    }

    // Compute the initial (lower triangular) distance matrix.
    double[] scratch = new double[triangleSize(size)];
    DBIDArrayIter ix = ids.iter(), iy = ids.iter(), ij = ids.iter();
    // Position counter - must agree with computeOffset!
    int pos = 0;
    boolean square = Linkage.WARD.equals(linkage) && !getDistanceFunction().isSquared();
    for(int x = 0; ix.valid(); x++, ix.advance()) {
      iy.seek(0);
      for(int y = 0; y < x; y++, iy.advance()) {
        scratch[pos] = dq.distance(ix, iy);
        // Ward uses variances -- i.e. squared values
        if(square) {
          scratch[pos] *= scratch[pos];
        }
        pos++;
      }
    }

    // Initialize space for result:
    WritableDBIDDataStore parent = DataStoreUtil.makeDBIDStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC);
    WritableDoubleDataStore height = DataStoreUtil.makeDoubleStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC);
    WritableIntegerDataStore csize = DataStoreUtil.makeIntegerStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_TEMP);
    for(DBIDIter it = ids.iter(); it.valid(); it.advance()) {
      parent.put(it, it);
      height.put(it, Double.POSITIVE_INFINITY);
      csize.put(it, 1);
    }

    // Repeat until everything merged, except the desired number of clusters:
    FiniteProgress prog = LOG.isVerbose() ? new FiniteProgress("Agglomerative clustering", size - 1, LOG) : null;
    for(int i = 1; i < size; i++) {
      double min = Double.POSITIVE_INFINITY;
      int minx = -1, miny = -1;
      for(ix.seek(0); ix.valid(); ix.advance()) {
        if(height.doubleValue(ix) < Double.POSITIVE_INFINITY) {
          continue;
        }
        final int xbase = triangleSize(ix.getOffset());
        for(iy.seek(0); iy.getOffset() < ix.getOffset(); iy.advance()) {
          if(height.doubleValue(iy) < Double.POSITIVE_INFINITY) {
            continue;
          }
          final int idx = xbase + iy.getOffset();
          if(scratch[idx] <= min) {
            min = scratch[idx];
            minx = ix.getOffset();
            miny = iy.getOffset();
          }
        }
      }
      assert (minx >= 0 && miny >= 0);
      // Avoid allocating memory, by reusing existing iterators:
      ix.seek(minx);
      iy.seek(miny);
      // Perform merge in data structure: x -> y
      // Since y < x, prefer keeping y, dropping x.
      int sizex = csize.intValue(ix), sizey = csize.intValue(iy);
      height.put(ix, min);
      parent.put(ix, iy);
      csize.put(iy, sizex + sizey);

      // Update distance matrix. Note: miny < minx
      final int xbase = triangleSize(minx), ybase = triangleSize(miny);
      // Write to (y, j), with j < y
      for(ij.seek(0); ij.getOffset() < miny; ij.advance()) {
        if(height.doubleValue(ij) < Double.POSITIVE_INFINITY) {
          continue;
        }
        final int sizej = csize.intValue(ij);
        scratch[ybase + ij.getOffset()] = linkage.combine(sizex, scratch[xbase + ij.getOffset()], sizey, scratch[ybase + ij.getOffset()], sizej, min);
      }
      // Write to (j, y), with y < j < x
      for(ij.seek(miny + 1); ij.getOffset() < minx; ij.advance()) {
        if(height.doubleValue(ij) < Double.POSITIVE_INFINITY) {
          continue;
        }
        final int jbase = triangleSize(ij.getOffset());
        final int sizej = csize.intValue(ij);
        scratch[jbase + miny] = linkage.combine(sizex, scratch[xbase + ij.getOffset()], sizey, scratch[jbase + miny], sizej, min);
      }
      // Write to (j, y), with y < x < j
      for(ij.seek(minx + 1); ij.valid(); ij.advance()) {
        if(height.doubleValue(ij) < Double.POSITIVE_INFINITY) {
          continue;
        }
        final int jbase = triangleSize(ij.getOffset());
        final int sizej = csize.intValue(ij);
        scratch[jbase + miny] = linkage.combine(sizex, scratch[jbase + minx], sizey, scratch[jbase + miny], sizej, min);
      }
      LOG.incrementProcessed(prog);
    }
    LOG.ensureCompleted(prog);

    return new PointerHierarchyRepresentationResult(ids, parent, height, dq.getDistanceFunction().isSquared());
  }
1259647
protected void expandClusterOrder(DBID ipt, ClusterOrder order, DistanceQuery<V> dq, FiniteProgress prog) {
    UpdatableHeap<OPTICSHeapEntry> heap = new UpdatableHeap<>();
    heap.add(new OPTICSHeapEntry(ipt, null, Double.POSITIVE_INFINITY));
    while(!heap.isEmpty()) {
      final OPTICSHeapEntry current = heap.poll();
      DBID currPt = current.objectID;
      order.add(currPt, current.reachability, current.predecessorID);
      processed.add(currPt);
      double coredist = inverseDensities.doubleValue(currPt);
      for(DBIDIter it = neighs.get(currPt).iter(); it.valid(); it.advance()) {
        if(processed.contains(it)) {
          continue;
        }
        double nrdist = dq.distance(currPt, it);
        if(coredist > nrdist) {
          nrdist = coredist;
        }
        if(reachDist.doubleValue(it) == UNDEFINED_DISTANCE) {
          reachDist.put(it, nrdist);
        }
        else if(nrdist < reachDist.doubleValue(it)) {
          reachDist.put(it, nrdist);
        }
        heap.add(new OPTICSHeapEntry(DBIDUtil.deref(it), currPt, nrdist));
      }
      LOG.incrementProcessed(prog);
    }
  }
970185
public static Point nearestSegmentPoint(double startX, double startY, double endX, double endY, double pointX, double pointY) {
        double xDiff = endX - startX;
        double yDiff = endY - startY;
        double length2 = xDiff * xDiff + yDiff * yDiff;
        if (length2 == 0) return new Point(startX, startY);
        double t = ((pointX - startX) * (endX - startX) + (pointY - startY) * (endY - startY)) / length2;
        if (t < 0) return new Point(startX, startY);
        if (t > 1) return new Point(endX, endY);
        return new Point(startX + t * (endX - startX), startY + t * (endY - startY));
    }