1 /*********************************************************************** 2 * Software License Agreement (BSD License) 3 * 4 * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. 5 * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved. 6 * 7 * THE BSD LICENSE 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 *************************************************************************/ 30 31 #ifndef FLANN_LINEAR_INDEX_H_ 32 #define FLANN_LINEAR_INDEX_H_ 33 34 #include "flann/general.h" 35 #include "flann/algorithms/nn_index.h" 36 37 namespace flann 38 { 39 40 struct LinearIndexParams : public IndexParams 41 { LinearIndexParamsLinearIndexParams42 LinearIndexParams() 43 { 44 (* this)["algorithm"] = FLANN_INDEX_LINEAR; 45 } 46 }; 47 48 template <typename Distance> 49 class LinearIndex : public NNIndex<Distance> 50 { 51 public: 52 53 typedef typename Distance::ElementType ElementType; 54 typedef typename Distance::ResultType DistanceType; 55 56 typedef NNIndex<Distance> BaseClass; 57 58 LinearIndex(const IndexParams& params = LinearIndexParams(), Distance d = Distance()) : BaseClass(params,d)59 BaseClass(params, d) 60 { 61 } 62 63 LinearIndex(const Matrix<ElementType>& input_data, const IndexParams& params = LinearIndexParams(), Distance d = Distance()) : BaseClass(params,d)64 BaseClass(params, d) 65 { 66 setDataset(input_data); 67 } 68 LinearIndex(const LinearIndex & other)69 LinearIndex(const LinearIndex& other) : BaseClass(other) 70 { 71 } 72 73 LinearIndex& operator=(LinearIndex other) 74 { 75 this->swap(other); 76 return *this; 77 } 78 ~LinearIndex()79 virtual ~LinearIndex() 80 { 81 } 82 clone()83 BaseClass* clone() const 84 { 85 return new LinearIndex(*this); 86 } 87 88 void addPoints(const Matrix<ElementType>& points, float rebuild_threshold = 2) 89 { 90 assert(points.cols==veclen_); 91 extendDataset(points); 92 } 93 getType()94 flann_algorithm_t getType() const 95 { 96 return FLANN_INDEX_LINEAR; 97 } 98 99 usedMemory()100 int usedMemory() const 101 { 102 return 0; 103 } 104 105 template<typename Archive> serialize(Archive & ar)106 void serialize(Archive& ar) 107 { 108 ar.setObject(this); 109 110 ar & *static_cast<NNIndex<Distance>*>(this); 111 112 if (Archive::is_loading::value) { 113 index_params_["algorithm"] = getType(); 114 } 115 } 116 saveIndex(FILE * stream)117 void saveIndex(FILE* stream) 118 { 119 serialization::SaveArchive sa(stream); 120 sa & *this; 121 } 122 loadIndex(FILE * stream)123 void loadIndex(FILE* stream) 124 { 125 serialization::LoadArchive la(stream); 126 la & *this; 127 } 128 findNeighbors(ResultSet<DistanceType> & resultSet,const ElementType * vec,const SearchParams &)129 void findNeighbors(ResultSet<DistanceType>& resultSet, const ElementType* vec, const SearchParams& /*searchParams*/) const 130 { 131 if (removed_) { 132 for (size_t i = 0; i < points_.size(); ++i) { 133 if (removed_points_.test(i)) continue; 134 DistanceType dist = distance_(points_[i], vec, veclen_); 135 resultSet.addPoint(dist, i); 136 } 137 } 138 else { 139 for (size_t i = 0; i < points_.size(); ++i) { 140 DistanceType dist = distance_(points_[i], vec, veclen_); 141 resultSet.addPoint(dist, i); 142 } 143 } 144 } 145 protected: buildIndexImpl()146 void buildIndexImpl() 147 { 148 /* nothing to do here for linear search */ 149 } 150 freeIndex()151 void freeIndex() 152 { 153 /* nothing to do here for linear search */ 154 } 155 156 private: 157 158 USING_BASECLASS_SYMBOLS 159 }; 160 161 } 162 163 #endif // FLANN_LINEAR_INDEX_H_ 164