package jsat.linear.vectorcollection;

import java.io.Serializable;
import static java.lang.Math.max;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import jsat.linear.Vec;
import jsat.linear.VecPaired;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.utils.DoubleList;
import jsat.utils.FibHeap;
import jsat.utils.IntList;
import jsat.utils.Tuple3;
import jsat.utils.concurrent.ParallelUtils;

/**
 * A Vector Collection is a collection of vectors that is meant to be used to 
 * obtain a subset of the collection via a query vector. A query can be for 
 * the nearest neighbors, or for all vectors within a given range. 
 * 
* Different vector collections have different performance properties for both training and execution time. * * @author Edward Raff * @param */ public interface VectorCollection extends Cloneable, Serializable { /** * Builds this metric index from the given collection of points using * whatever distance metric is currently set for the metric index. * * @param collection the list of vectors to put into the index */ default public void build(List collection) { build(false, collection); } /** * Builds this metric index from the given collection of points using the * given distance metric. * * @param collection the list of vectors to put into the index * @param dm the distance metric to build the index using. */ default public void build(List collection, DistanceMetric dm) { build(false, collection, dm); } /** * Builds this metric index from the given collection of points using * whatever distance metric is currently set for the metric index. * * @param parallel {@code true} if the index should be built in parallel, or * {@code false} if it should be done in a single thread. * @param collection the list of vectors to put into the index */ default public void build(boolean parallel, List collection) { build(parallel, collection, getDistanceMetric()); } /** * Builds this metric index from the given collection of points using the * given distance metric. * * @param parallel {@code true} if the index should be built in parallel, or * {@code false} if it should be done in a single thread. * @param collection the list of vectors to put into the index * @param dm the distance metric to build the index using. */ public void build(boolean parallel, List collection, DistanceMetric dm); /** * Sets the distance metric used for this collection. * @param dm the distance metric to use */ public void setDistanceMetric(DistanceMetric dm); /** * * @return the distance metric to use */ public DistanceMetric getDistanceMetric(); /** * Searches the space for all vectors that are within a given range of the query vector. * @param query the vector we want to find others near * @param range the search range around our query * @return the list of all vectors within the range of our query. The paired value contains the distance to the query vector. * @deprecated This API is from the original JSAT interface. It will be removed in the future. */ default public List> search(Vec query, double range) { IntList neighbors = new IntList(); DoubleList distances = new DoubleList(); search(query, range, neighbors, distances); List> toRet = new ArrayList<>(); for(int i = 0; i < neighbors.size(); i++) toRet.add(new VecPaired<>(get(neighbors.getI(i)), distances.getD(i))); return toRet; } /** * Searches the space for the k neighbors that are closest to the given query vector * @param query the vector we want to find neighbors of * @param num_neighbors the maximum number of neighbors to return * @return the list the k nearest neighbors, in sorted order from closest to farthest. The paired value contains the distance to the query vector * @deprecated This API is from the original JSAT interface. It will be removed in the future. */ default public List> search(Vec query, int num_neighbors) { IntList neighbors = new IntList(); DoubleList distances = new DoubleList(); search(query, num_neighbors, neighbors, distances); List> toRet = new ArrayList<>(); for(int i = 0; i < neighbors.size(); i++) toRet.add(new VecPaired<>(get(neighbors.getI(i)), distances.getD(i))); return toRet; } /** * Performs a range search of the current collection. The index and distance * of each found neighbor will be placed into the given Lists. * * @param query the point to search for the neighbors within a given radius. * @param range the radius to search for all the neighbors with a distance * ≤ range. * @param neighbors the list to store the index of the neighbors in. Will be * sorted by distance to the query, and paired with the values in * distances. * @param distances the list to store the distance of the neighbors to the * query in. Will be sorted, and paired with the values in * neighbors. */ public void search(Vec query, double range, List neighbors, List distances); /** * Performs k-Nearest Neighbor search of the current collection. The index * and distance of each found neighbor will be placed into the given Lists. * * @param query the point to search for the k-nearest neighbors of * @param numNeighbors the number of neighbors k to search for. * @param neighbors the list to store the index of the neighbors in. Will be * sorted by distance to the query, and paired with the values in * distances. * @param distances the list to store the distance of the neighbors to the * query in. Will be sorted, and paired with the values in * neighbors. */ public void search(Vec query, int numNeighbors, List neighbors, List distances); /** * Accesses a vector from this collection via index. * @param indx the index in [0, {@link #size() }) of the vector to access * @return the vector from the collection */ public V get(int indx); public List getAccelerationCache(); /** * Returns the number of vectors stored in the collection * @return the size of the collection */ public int size(); default public void search(List Q, double r_min, double r_max, List> neighbors, List> distances , boolean parallel) { VectorCollection vc = new VectorArray<>(getDistanceMetric(), Q); search(vc, r_min, r_max, neighbors, distances, parallel); } default public void search(VectorCollection Q, double r_min, double r_max, List> neighbors, List> distances , boolean parallel) { neighbors.clear(); distances.clear(); for(int i = 0; i < Q.size(); i++) { neighbors.add(new ArrayList<>()); distances.add(new ArrayList<>()); } ParallelUtils.range(Q.size(), parallel).forEach(i-> { //this gets everything up to max this.search(Q.get(i), r_max, neighbors.get(i), distances.get(i)); //now lets remove the things below min int indx = Collections.binarySearch(distances.get(i), r_min); if(indx < 0) indx = -indx-1; neighbors.get(i).subList(0, indx).clear(); distances.get(i).subList(0, indx).clear(); }); } default public void search(List Q, int numNeighbors, List> neighbors, List> distances, boolean parallel) { VectorCollection vc = new VectorArray<>(getDistanceMetric(), Q); search(vc, numNeighbors, neighbors, distances, parallel); } default public void search(VectorCollection Q, int numNeighbors, List> neighbors, List> distances, boolean parallel) { neighbors.clear(); distances.clear(); for(int i = 0; i < Q.size(); i++) { neighbors.add(new ArrayList<>()); distances.add(new ArrayList<>()); } ParallelUtils.range(Q.size(), parallel).forEach(i-> { //this gets everything up to max this.search(Q.get(i), numNeighbors, neighbors.get(i), distances.get(i)); }); } public VectorCollection clone(); public default List getVecs() { return IntStream.range(0, size()) .mapToObj(this::get) .collect(Collectors.toList()); } }

Ads help maintain this website.