001/**
002 * Copyright (c) 2011, The University of Southampton and the individual contributors.
003 * All rights reserved.
004 *
005 * Redistribution and use in source and binary forms, with or without modification,
006 * are permitted provided that the following conditions are met:
007 *
008 *   *  Redistributions of source code must retain the above copyright notice,
009 *      this list of conditions and the following disclaimer.
010 *
011 *   *  Redistributions in binary form must reproduce the above copyright notice,
012 *      this list of conditions and the following disclaimer in the documentation
013 *      and/or other materials provided with the distribution.
014 *
015 *   *  Neither the name of the University of Southampton nor the names of its
016 *      contributors may be used to endorse or promote products derived from this
017 *      software without specific prior written permission.
018 *
019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029 */
030package org.openimaj.knn;
031
032import java.util.ArrayList;
033import java.util.Collection;
034import java.util.List;
035import java.util.PriorityQueue;
036
037import org.openimaj.math.geometry.point.Coordinate;
038
039/**
040 * Implementation of a {@link CoordinateIndex} that performs
041 * searching by brute-force comparison over the indexed coordinates.
042 * 
043 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
044 *
045 * @param <T> the type of Coordinate 
046 */
047public class CoordinateBruteForce<T extends Coordinate> implements CoordinateIndex<T> {
048        List<T> data = new ArrayList<T>();
049        
050        /**
051         * Default constructor. Creates an empty index.
052         */
053        public CoordinateBruteForce() {}
054        
055        /**
056         * Construct the index and populate it with the given data.
057         * @param data the data to add to the index.
058         */
059        public CoordinateBruteForce(List<T> data) {
060                this.data = data;
061        }
062        
063        @Override
064        public void insert(T point) {
065                data.add(point);
066        }
067        
068        @Override
069        public void rangeSearch(Collection<T> results, Coordinate lowerExtreme, Coordinate upperExtreme) {
070                for (T d : data) {
071                        if (CoordinateKDTree.isContained(d, lowerExtreme, upperExtreme))
072                                results.add(d);
073                }
074        }
075        
076        @Override
077        public T nearestNeighbour(Coordinate query) {
078                float minDist = Float.MAX_VALUE;
079                T best = null;
080                
081                for (T d : data) {
082                        float dist = CoordinateKDTree.distance(d, query);
083                        if (dist < minDist) {
084                                minDist = dist;
085                                best = d;
086                        }
087                }
088                
089                return best;
090        }
091
092        class Match implements Comparable<Match> {
093                float distance;
094                T coord;
095                @Override public int compareTo(Match o) {
096                        if (distance > o.distance) return 1;
097                        if (distance < o.distance) return -1;
098                        return 0;
099                }
100                @Override
101                public String toString() { return distance + ""; }
102        }
103        
104        @Override
105        public void kNearestNeighbour(Collection<T> result, Coordinate query, int k) {
106                PriorityQueue<Match> queue = new PriorityQueue<Match>(data.size());
107                
108                for (T d : data) {
109                        Match m = new Match();
110                        m.coord = d;
111                        m.distance = CoordinateKDTree.distance(query, d);
112                        queue.add(m);
113                }
114                
115                for (int i=0; i<k; i++)
116                        result.add(queue.poll().coord);
117        }
118}