/*
        AUTOMATICALLY GENERATED BY jTemp FROM
        /Users/jsh2/Work/openimaj/target/checkout/machine-learning/nearest-neighbour/src/main/jtemp/org/openimaj/knn/approximate/#T#NearestNeighboursKDTree.jtemp
*/
/**
 * Copyright (c) 2011, The University of Southampton and the individual contributors.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 *
 *   *  Redistributions of source code must retain the above copyright notice,
 *      this list of conditions and the following disclaimer.
 *
 *   *  Redistributions in binary form must reproduce the above copyright notice,
 *      this list of conditions and the following disclaimer in the documentation
 *      and/or other materials provided with the distribution.
 *
 *   *  Neither the name of the University of Southampton nor the names of its
 *      contributors may be used to endorse or promote products derived from this
 *      software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.openimaj.knn.approximate;

import java.util.Arrays;
import java.util.List;

import org.openimaj.citation.annotation.Reference;
import org.openimaj.citation.annotation.ReferenceType;
import org.openimaj.knn.FloatNearestNeighbours;
import org.openimaj.knn.NearestNeighboursFactory;
import org.openimaj.util.pair.*;

/**
 * Fast Nearest-Neighbours for float data using an ensemble of Best-Bin-First KDTrees. 
 * <p>
 * Implementation inspired by http://www.robots.ox.ac.uk/~vgg/software/fastann/
 * 
 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
 * @author Sina Samangooei (ss@ecs.soton.ac.uk)
 */
@Reference(
        type = ReferenceType.Inproceedings,
        author = { "Marius Muja", "David G. Lowe" },
        title = "Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration",
        year = "2009",
        booktitle = "International Conference on Computer Vision Theory and Application VISSAPP'09)",
        pages = { "331", "340" },
        publisher = "INSTICC Press"
)
public class FloatNearestNeighboursKDTree extends FloatNearestNeighbours {
    /**
         * {@link NearestNeighboursFactory} for producing
         * {@link FloatNearestNeighboursKDTree}s.
         * 
         * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
         */
    public static final class Factory implements NearestNeighboursFactory<FloatNearestNeighboursKDTree, float[]> {
        int ntrees;
        int nchecks;
        
        /**
         * Construct the factory the default number of trees and checks.
         */
        public Factory() {
            this.ntrees = FloatNearestNeighboursKDTree.DEFAULT_NTREES;
            this.nchecks = FloatNearestNeighboursKDTree.DEFAULT_NCHECKS;
        }
        
        /**
         * Construct the factory the given number of trees and checks.
         * 
                 * @param ntrees 
                 *          the number of trees 
         * @param nchecks 
         *          the number of checks during search
         */
        public Factory(int ntrees, int nchecks) {
            this.ntrees = ntrees;
            this.nchecks = nchecks;
        }
        
        @Override
        public FloatNearestNeighboursKDTree create(float[][] data) {
            return new FloatNearestNeighboursKDTree(data, ntrees, nchecks);
        }
    }
    
    /**
         * The default number of checks performed during search when in exact mode.
         */
        public static final int DEFAULT_NCHECKS = 768;

        /**
         * The default number of kdtrees when not in exact mode.
         */
        public static final int DEFAULT_NTREES = 8;
    
        /** The ensemble of KDTrees */
        public final FloatKDTreeEnsemble kdt;
        
        /** The number of checks */
    public final int nchecks;
        
        /** 
         * Construct the FloatNearestNeighboursKDTree with the given options.
         * 
         * @param pnts the data
         * @param ntrees the number of trees 
         * @param nchecks the number of checks during search
         */
    public FloatNearestNeighboursKDTree(final float [][] pnts, int ntrees, int nchecks) {
        kdt = new FloatKDTreeEnsemble(pnts, ntrees);
        this.nchecks = nchecks;
    }
    
        @Override
        public int numDimensions() {
                return kdt.pnts[0].length;
        }

        @Override
        public int size() {
                return kdt.pnts.length;
        }

        @Override
        public void searchKNN(float[][] qus, int K, int[][] argmins, float[][] mins) {
                // Fix for when the user asks for too many points.
        K = Math.min(K, kdt.pnts.length);
     
        IntFloatPair[] nns = new IntFloatPair[K];
        final int N = qus.length;
        
        for (int n=0; n < N; ++n) {
            kdt.search(qus[n], K, nns, nchecks);
            for (int k=0; k < K; ++k) {
                argmins[n][k] = nns[k].first;
                mins[n][k] = nns[k].second;
            }
        }
        }

        @Override
        public void searchNN(float[][] qus, int[] argmins, float[] mins) {
                final int N = qus.length;
                IntFloatPair [] nn = new IntFloatPair[1];
                
                for (int n=0; n < N; ++n) {
            kdt.search(qus[n], 1, nn, nchecks);
            
            argmins[n] = nn[0].first;
            mins[n] = nn[0].second;
        }
        }
        
        @Override
        public void searchKNN(List<float[]> qus, int K, int[][] argmins, float[][] mins) {
                // Fix for when the user asks for too many points.
        K = Math.min(K, kdt.pnts.length);
     
        IntFloatPair[] nns = new IntFloatPair[K];
        final int N = qus.size();
        
        for (int n=0; n < N; ++n) {
            kdt.search(qus.get(n), K, nns, nchecks);
            for (int k=0; k < K; ++k) {
                argmins[n][k] = nns[k].first;
                mins[n][k] = nns[k].second;
            }
        }
        }

        @Override
        public void searchNN(List<float[]> qus, int[] argmins, float[] mins) {
                final int N = qus.size();
                IntFloatPair [] nn = new IntFloatPair[1];
                
                for (int n=0; n < N; ++n) {
            kdt.search(qus.get(n), 1, nn, nchecks);
            
            argmins[n] = nn[0].first;
            mins[n] = nn[0].second;
        }
        }
        
        @Override
        public List<IntFloatPair> searchKNN(float[] query, int K) {
                // Fix for when the user asks for too many points.
                K = Math.min(K, kdt.pnts.length);

                final IntFloatPair[] nns = new IntFloatPair[K];

                kdt.search(query, K, nns, nchecks);

                return Arrays.asList(nns);
        }

        @Override
        public IntFloatPair searchNN(float[] query) {
                final IntFloatPair[] nn = new IntFloatPair[1];

                kdt.search(query, 1, nn, nchecks);
                
                return nn[0];
        }
}