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