35 #ifndef SHARK_ALGORITHMS_NEARESTNEIGHBORS_BINARYTREE_H 36 #define SHARK_ALGORITHMS_NEARESTNEIGHBORS_BINARYTREE_H 44 #include <boost/range/algorithm_ext/iota.hpp> 45 #include <boost/range/iterator_range.hpp> 46 #include <boost/math/special_functions/fpclassify.hpp> 127 template <
class InputT>
131 typedef InputT value_type;
150 mp_indexList =
new std::size_t[m_size];
151 boost::iota(boost::make_iterator_range(mp_indexList,mp_indexList+m_size),0);
157 if (mp_left != NULL)
delete mp_left;
158 if (mp_right != NULL)
delete mp_right;
159 if (mep_parent == NULL)
delete [] mp_indexList;
167 {
return mep_parent; }
170 {
return mep_parent; }
175 {
return (mp_left != NULL); }
180 {
return (mp_left == NULL); }
204 std::size_t
index(std::size_t point)
const{
205 return mp_indexList[point];
225 return funct(point) - m_threshold;
235 bool isLeft(value_type
const& point)
const 236 {
return (funct(point) < m_threshold); }
241 {
return (funct(point) >= m_threshold); }
259 virtual double squaredDistanceLowerBound(value_type
const& point)
const = 0;
263 void print(
unsigned int ident = 0)
const 267 for (
unsigned int j=0; j<
size(); j++)
269 for (
unsigned int i=0; i<ident; i++) printf(
" ");
270 printf(
"index: %d\n", (
int)index(j));
275 for (
unsigned int i=0; i<ident; i++) printf(
" ");
276 printf(
"[%d]\n", (
int)mp_left->size());
277 mp_left->print(ident + 1);
278 for (
unsigned int i=0; i<ident; i++) printf(
" ");
279 printf(
"[%d]\n", (
int)mp_right->size());
280 mp_right->print(ident + 1);
320 virtual double funct(value_type
const& point)
const = 0;
329 template<
class Range1,
class Range2>
330 typename boost::range_iterator<Range2>::type
splitList (Range1& values, Range2& points){
331 typedef typename boost::range_iterator<Range1>::type iterator1;
332 typedef typename boost::range_iterator<Range2>::type iterator2;
334 iterator1 valuesBegin = boost::begin(values);
335 iterator1 valuesEnd = boost::end(values);
339 iterator1 valuesSplitpoint = splitpoint.first;
340 iterator2 pointsSplitpoint = splitpoint.second;
341 if (valuesSplitpoint == valuesEnd) {
343 m_threshold = *valuesBegin;
344 return splitpoint.second;
351 double maximum = *std::max_element(valuesBegin, valuesSplitpoint);
352 m_threshold = 0.5*(maximum + *valuesSplitpoint);
354 return pointsSplitpoint;