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.ml.clustering.kdtree;
031
032import java.io.DataInput;
033import java.io.DataOutput;
034import java.io.IOException;
035import java.io.PrintWriter;
036import java.util.HashMap;
037import java.util.List;
038import java.util.Map;
039import java.util.Scanner;
040
041import org.openimaj.ml.clustering.IndexClusters;
042import org.openimaj.ml.clustering.SpatialClusters;
043import org.openimaj.ml.clustering.assignment.HardAssigner;
044import org.openimaj.util.pair.IntDoublePair;
045import org.openimaj.util.tree.DoubleKDTree;
046import org.openimaj.util.tree.DoubleKDTree.KDTreeNode;
047
048/**
049 *
050 * @author Sina Samangooei (ss@ecs.soton.ac.uk)
051 */
052public class KDTreeClusters extends IndexClusters implements SpatialClusters<double[]> {
053
054
055        private final class KDHardTreeAssigner implements HardAssigner<double[], double[], IntDoublePair> {
056                
057                private Map<int[], Integer> clusterToIndex;
058
059                public KDHardTreeAssigner() {
060                        this.clusterToIndex = new HashMap<int[],Integer>();
061                        for (int i = 0; i < KDTreeClusters.this.leaves.size(); i++) {
062                                this.clusterToIndex.put(leaves.get(i), i);
063                        }
064                }
065                
066                @Override
067                public int numDimensions() {
068                        return dims;
069                }
070
071                @Override
072                public int[] assign(double[][] data) {
073                        int[] ret = new int[data.length];
074                        for (int i = 0; i < ret.length; i++) {
075                                ret[i] = assign(data[i]);
076                        }
077                        return ret;
078                }
079
080                @Override
081                public int assign(double[] data) {
082                        KDTreeNode toFollow = tree.root;
083                        while(toFollow.indices == null){
084                                if(data[toFollow.discriminantDimension] < toFollow.discriminant){
085                                        toFollow = toFollow.left;
086                                }
087                                else{
088                                        toFollow = toFollow.right;
089                                }
090                        }
091                        return this.clusterToIndex.get(toFollow.indices);
092                }
093
094                @Override
095                public void assignDistance(double[][] data, int[] indices, double[] distances) {
096                        throw new UnsupportedOperationException();
097                }
098
099                @Override
100                public IntDoublePair assignDistance(double[] data) {
101                        throw new UnsupportedOperationException();
102                }
103
104                @Override
105                public int size() {
106                        return numClusters();
107                }
108        }
109
110        private List<int[]> leaves;
111        private int dims;
112        private DoubleKDTree tree;
113
114        /**
115         * @param tree the KDTree which represents the clusters
116         * @param dims 
117         */
118        public KDTreeClusters(DoubleKDTree tree, int dims) {
119                this.tree = tree;
120                this.leaves = tree.leafIndices();
121                this.dims = dims;
122                this.clusters = new int[leaves.size()][];
123                for (int i = 0; i < clusters.length; i++) {
124                        clusters[i] = leaves.get(i);
125                        this.nEntries += this.clusters[i].length;
126                }
127                
128        }
129
130        @Override
131        public int numDimensions() {
132                return dims;
133        }
134
135        @Override
136        public int numClusters() {
137                return leaves.size();
138        }
139
140        @Override
141        public HardAssigner<double[], ?, ?> defaultHardAssigner() {
142                return new KDHardTreeAssigner();
143        }
144        @Override
145        public void readASCII(Scanner in) throws IOException { throw new UnsupportedOperationException(); }
146        
147        @Override
148        public String asciiHeader() { throw new UnsupportedOperationException(); }
149        
150        @Override
151        public void readBinary(DataInput in) throws IOException{ throw new UnsupportedOperationException(); }
152        
153        @Override
154        public byte[] binaryHeader() { throw new UnsupportedOperationException(); }
155        
156        @Override
157        public void writeASCII(PrintWriter out) throws IOException { throw new UnsupportedOperationException(); }
158        
159        @Override
160        public void writeBinary(DataOutput out) throws IOException { throw new UnsupportedOperationException(); }
161
162}