<commit_before>package de.lmu.ifi.dbs.elki.index.preprocessed.snn;

import java.util.Iterator;
import java.util.List;

import de.lmu.ifi.dbs.elki.data.DatabaseObject;
import de.lmu.ifi.dbs.elki.database.Database;
import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory;
import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil;
import de.lmu.ifi.dbs.elki.database.ids.DBID;
import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil;
import de.lmu.ifi.dbs.elki.database.ids.SetDBIDs;
import de.lmu.ifi.dbs.elki.database.ids.TreeSetDBIDs;
import de.lmu.ifi.dbs.elki.database.ids.TreeSetModifiableDBIDs;
import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair;
import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery;
import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction;
import de.lmu.ifi.dbs.elki.distance.distancefunction.EuclideanDistanceFunction;
import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance;
import de.lmu.ifi.dbs.elki.index.preprocessed.AbstractPreprocessorIndex;
import de.lmu.ifi.dbs.elki.index.preprocessed.knn.MaterializeKNNPreprocessor;
import de.lmu.ifi.dbs.elki.logging.Logging;
import de.lmu.ifi.dbs.elki.logging.progress.FiniteProgress;
import de.lmu.ifi.dbs.elki.utilities.documentation.Description;
import de.lmu.ifi.dbs.elki.utilities.documentation.Title;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter;

/**
 * A preprocessor for annotation of the ids of nearest neighbors to each
 * database object.
 * <p/>
 * The k nearest neighbors are assigned based on an arbitrary distance function.
 * 
 * This functionality is similar but not identical to
 * {@link MaterializeKNNPreprocessor}: While it also computes the k nearest
 * neighbors, it does not keep the actual distances, but organizes the NN set in
 * a TreeSet for fast set operations.
 * 
 * @author <NAME>
 * @author <NAME>
 * 
 * @apiviz.has DistanceFunction
 * 
 * @param <O> the type of database objects the preprocessor can be applied to
 * @param <D> the type of distance the used distance function will return
 */
@Title("Shared nearest neighbor Preprocessor")
@Description("Computes the k nearest neighbors of objects of a certain database.")
public class SharedNearestNeighborPreprocessor<O extends DatabaseObject, D extends Distance<D>> extends AbstractPreprocessorIndex<O, TreeSetDBIDs> implements SharedNearestNeighborIndex<O> {
  /**
   * Get a logger for this class.
   */
  private static final Logging logger = Logging.getLogger(SharedNearestNeighborPreprocessor.class);

  /**
   * Database we are attached to
   */
  final protected Database<O> database;

  /**
   * Holds the number of nearest neighbors to be used.
   */
  protected int numberOfNeighbors;

  /**
   * Hold the distance function to be used.
   */
  protected DistanceFunction<O, D> distanceFunction;

  /**
   * Constructor.
   * 
   * @param database Database to use
   * @param numberOfNeighbors Number of neighbors
   * @param distanceFunction Distance function
   */
  public SharedNearestNeighborPreprocessor(Database<O> database, int numberOfNeighbors, DistanceFunction<O, D> distanceFunction) {
    super();
    this.database = database;
    this.numberOfNeighbors = numberOfNeighbors;
    this.distanceFunction = distanceFunction;
  }

  /**
   * Preprocessing step.
   */
  protected void preprocess() {
    if(getLogger().isVerbose()) {
      getLogger().verbose("Assigning nearest neighbor lists to database objects");
    }
    storage = DataStoreUtil.makeStorage(database.getIDs(), DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_TEMP, SetDBIDs.class);
    KNNQuery<O, D> knnquery = database.getKNNQuery(distanceFunction, numberOfNeighbors + 1);

    FiniteProgress progress = getLogger().isVerbose() ? new FiniteProgress("assigning nearest neighbor lists", database.size(), getLogger()) : null;
    int count = 0;
    for(Iterator<DBID> iter = database.iterator(); iter.hasNext();) {
      count++;
      DBID id = iter.next();
      TreeSetModifiableDBIDs neighbors = DBIDUtil.newTreeSet(numberOfNeighbors);
      List<DistanceResultPair<D>> kNN = knnquery.getKNNForDBID(id, numberOfNeighbors + 1);
      for(int i = 0; i < kNN.size(); i++) {
        final DBID nid = kNN.get(i).getID();
        if(!id.equals(nid)) {
          neighbors.add(nid);
        }
      }
      storage.put(id, neighbors);
      if(progress != null) {
        progress.incrementProcessed(getLogger());
      }
    }
    if(progress != null) {
      progress.ensureCompleted(getLogger());
    }<commit_msg>Fix SNN distances that in rare cases would become negative.<commit_after>package de.lmu.ifi.dbs.elki.index.preprocessed.snn;

import java.util.Iterator;
import java.util.List;

import de.lmu.ifi.dbs.elki.data.DatabaseObject;
import de.lmu.ifi.dbs.elki.database.Database;
import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory;
import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil;
import de.lmu.ifi.dbs.elki.database.ids.DBID;
import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil;
import de.lmu.ifi.dbs.elki.database.ids.SetDBIDs;
import de.lmu.ifi.dbs.elki.database.ids.TreeSetDBIDs;
import de.lmu.ifi.dbs.elki.database.ids.TreeSetModifiableDBIDs;
import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair;
import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery;
import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction;
import de.lmu.ifi.dbs.elki.distance.distancefunction.EuclideanDistanceFunction;
import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance;
import de.lmu.ifi.dbs.elki.index.preprocessed.AbstractPreprocessorIndex;
import de.lmu.ifi.dbs.elki.index.preprocessed.knn.MaterializeKNNPreprocessor;
import de.lmu.ifi.dbs.elki.logging.Logging;
import de.lmu.ifi.dbs.elki.logging.progress.FiniteProgress;
import de.lmu.ifi.dbs.elki.utilities.documentation.Description;
import de.lmu.ifi.dbs.elki.utilities.documentation.Title;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter;

/**
 * A preprocessor for annotation of the ids of nearest neighbors to each
 * database object.
 * <p/>
 * The k nearest neighbors are assigned based on an arbitrary distance function.
 * 
 * This functionality is similar but not identical to
 * {@link MaterializeKNNPreprocessor}: While it also computes the k nearest
 * neighbors, it does not keep the actual distances, but organizes the NN set in
 * a TreeSet for fast set operations.
 * 
 * @author <NAME>
 * @author <NAME>
 * 
 * @apiviz.has DistanceFunction
 * 
 * @param <O> the type of database objects the preprocessor can be applied to
 * @param <D> the type of distance the used distance function will return
 */
@Title("Shared nearest neighbor Preprocessor")
@Description("Computes the k nearest neighbors of objects of a certain database.")
public class SharedNearestNeighborPreprocessor<O extends DatabaseObject, D extends Distance<D>> extends AbstractPreprocessorIndex<O, TreeSetDBIDs> implements SharedNearestNeighborIndex<O> {
  /**
   * Get a logger for this class.
   */
  private static final Logging logger = Logging.getLogger(SharedNearestNeighborPreprocessor.class);

  /**
   * Database we are attached to
   */
  final protected Database<O> database;

  /**
   * Holds the number of nearest neighbors to be used.
   */
  protected int numberOfNeighbors;

  /**
   * Hold the distance function to be used.
   */
  protected DistanceFunction<O, D> distanceFunction;

  /**
   * Constructor.
   * 
   * @param database Database to use
   * @param numberOfNeighbors Number of neighbors
   * @param distanceFunction Distance function
   */
  public SharedNearestNeighborPreprocessor(Database<O> database, int numberOfNeighbors, DistanceFunction<O, D> distanceFunction) {
    super();
    this.database = database;
    this.numberOfNeighbors = numberOfNeighbors;
    this.distanceFunction = distanceFunction;
  }

  /**
   * Preprocessing step.
   */
  protected void preprocess() {
    if(getLogger().isVerbose()) {
      getLogger().verbose("Assigning nearest neighbor lists to database objects");
    }
    storage = DataStoreUtil.makeStorage(database.getIDs(), DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_TEMP, SetDBIDs.class);
    KNNQuery<O, D> knnquery = database.getKNNQuery(distanceFunction, numberOfNeighbors + 1);

    FiniteProgress progress = getLogger().isVerbose() ? new FiniteProgress("assigning nearest neighbor lists", database.size(), getLogger()) : null;
    int count = 0;
    for(Iterator<DBID> iter = database.iterator(); iter.hasNext();) {
      count++;
      DBID id = iter.next();
      TreeSetModifiableDBIDs neighbors = DBIDUtil.newTreeSet(numberOfNeighbors);
      List<DistanceResultPair<D>> kNN = knnquery.getKNNForDBID(id, numberOfNeighbors + 1);
      for(int i = 0; i < kNN.size(); i++) {
        final DBID nid = kNN.get(i).getID();
        if(!id.equals(nid)) {
          neighbors.add(nid);
        }
        // Size limitation to exaclty numberOfNeighbors
        if (neighbors.size() >= numberOfNeighbors) {
          break;
        }
      }
      storage.put(id, neighbors);
      if(progress != null) {
        progress.incrementProcessed(getLogger());
      }
    }
    if(progress != null) {
      progress.ensureCompleted(getLogger());
    }
{'fraction_non_alphanumeric': 0.11125549780087965, 'fraction_numerical': 0.0007996801279488205, 'mean_word_length': 4.230005227391532, 'pattern_counts': {'":': 0, '<': 39, '<?xml version=': 0, '>': 38, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6444116', 'n_tokens_mistral': 3247, 'n_tokens_neox': 3152, 'n_words': 676}