/
covertree_point.hpp
174 lines (147 loc) · 4.5 KB
/
covertree_point.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
/* * This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or
* (at your option) any later version.
*
* Written (W) 2012 Fernando José Iglesias García
* Written (W) John Langford and Dinoj Surendran, v_array and its templatization
* Copyright (C) 2012 Fernando José Iglesias García
*/
#ifndef _JL_COVERTREE_POINT_H_
#define _JL_COVERTREE_POINT_H_
/* Tapkee includes */
#include <shogun/lib/tapkee/defines.hpp>
/* End of Tapkee includes */
#include <iostream>
#include <cmath>
namespace tapkee
{
namespace tapkee_internal
{
/** @brief Class v_array taken directly from JL's implementation */
template<class T>
class v_array{
public:
/** Getter for the the last element of the v_array
* @return the last element of the array */
T last() { return elements[index-1];}
/** Decrement the pointer to the last element */
void decr() { index--;}
/** Create an empty v_array */
v_array() : index(0), length(0), elements(NULL) {}
/** Element access operator
* @param i of the element to be read
* @return the corresponding element */
T& operator[](IndexType i) { return elements[i]; }
public:
/** Pointer to the last element of the v_array */
int index;
/** Length of the v_array */
int length;
/** Pointer to the beginning of the v_array elements */
T* elements;
};
/**
* Insert a new element at the end of the vector
*
* @param v vector
* @param new_ele element to insert
*/
template<class T>
void push(v_array<T>& v, const T &new_ele)
{
while(v.index >= v.length)
{
v.length = 2*v.length + 3;
v.elements = (T *)realloc(v.elements,sizeof(T) * v.length);
}
v[v.index++] = new_ele;
}
/**
* Used to modify the capacity of the vector
*
* @param v vector
* @param length the new length of the vector
*/
template<class T>
void alloc(v_array<T>& v, int length)
{
v.elements = (T *)realloc(v.elements, sizeof(T) * length);
v.length = length;
}
/**
* Returns the vector previous to the pointed one in the stack of
* vectors and decrements the index of the stack. No memory is
* freed here. If there are no vectors stored in the stack, create
* and return a new empty vector
*
* @param stack of vectors
* @return the adequate vector according to the previous conditions
*/
template<class T>
v_array<T> pop(v_array<v_array<T> > &stack)
{
if (stack.index > 0)
return stack[--stack.index];
else
return v_array<T>();
}
/** @brief Class Point to use with John Langford's CoverTree. This
* class must have some associated functions defined (distance,
* and print, see below) so it can be used with the CoverTree
* implementation.
*/
template <class RandomAccessIterator>
struct CoverTreePoint
{
CoverTreePoint() : iter_(), norm_(0.0)
{
};
CoverTreePoint(const RandomAccessIterator& iter, ScalarType norm) :
iter_(iter), norm_(norm)
{
};
RandomAccessIterator iter_;
ScalarType norm_;
}; /* struct JLCoverTreePoint */
template <class Type, class RandomAccessIterator, class Callback>
struct distance_impl;
/** Functions declared out of the class definition to respect CoverTree
* structure */
template <class RandomAccessIterator, class Callback>
inline ScalarType distance(Callback& cb, const CoverTreePoint<RandomAccessIterator>& l,
const CoverTreePoint<RandomAccessIterator>& r, ScalarType upper_bound)
{
//assert(upper_bound>=0);
if (l.iter_==r.iter_)
return 0.0;
return distance_impl<typename Callback::type,RandomAccessIterator,Callback>()(cb,l,r,upper_bound);
}
struct KernelType;
template <class RandomAccessIterator, class Callback>
struct distance_impl<KernelType,RandomAccessIterator,Callback>
{
inline ScalarType operator()(Callback& cb, const CoverTreePoint<RandomAccessIterator>& l,
const CoverTreePoint<RandomAccessIterator>& r, ScalarType /*upper_bound*/)
{
return std::sqrt(l.norm_ + r.norm_ - 2*cb(r.iter_,l.iter_));
}
};
struct DistanceType;
template <class RandomAccessIterator, class Callback>
struct distance_impl<DistanceType,RandomAccessIterator,Callback>
{
inline ScalarType operator()(Callback& cb, const CoverTreePoint<RandomAccessIterator>& l,
const CoverTreePoint<RandomAccessIterator>& r, ScalarType /*upper_bound*/)
{
return cb(l.iter_,r.iter_);
}
};
/** Print the information of the CoverTree point */
template <class RandomAccessIterator>
void print(const CoverTreePoint<RandomAccessIterator>&)
{
}
}
}
#endif /* _JL_COVERTREE_POINT_H_*/