53 DataPoint(
int Dv,
int indv,
double* xv) : _D(Dv), _ind(indv), _x(NULL)
55 _x = (
double*) malloc(_D *
sizeof(
double));
56 for(
int d = 0; d <
_D; d++) _x[d] = xv[d];
63 _x = (
double*) malloc(_D *
sizeof(
double));
64 for(
int d = 0; d <
_D; d++) _x[d] = other.
x(d);
70 if(_x != NULL) free(_x);
73 _x = (
double*) malloc(_D *
sizeof(
double));
74 for(
int d = 0; d <
_D; d++) _x[d] = other.
x(d);
80 double x(
int d)
const {
return _x[d]; }
86 for(
int d = 0; d < t1.
dimensionality(); d++) dd += (t1.
x(d) - t2.
x(d)) * (t1.
x(d) - t2.
x(d));
91 template<
typename T,
double (*distance)( const T&, const T& )>
97 VpTree() : _items(), _tau(0.0), _root(0) {}
105 void create(
const std::vector<T>& items) {
108 _root = buildFromPoints(0, items.size());
112 void search(
const T& target,
int k, std::vector<T>* results, std::vector<double>* distances)
116 std::priority_queue<HeapItem> heap;
122 search(_root, target, k, heap);
125 results->clear(); distances->clear();
126 while(!heap.empty()) {
127 results->push_back(_items[heap.top().index]);
128 distances->push_back(heap.top().dist);
133 std::reverse(results->begin(), results->end());
134 std::reverse(distances->begin(), distances->end());
153 Node() : index(0), threshold(0.), left(0), right(0) {}
170 index(indexv), dist(distv) {}
174 return dist < o.
dist;
191 if (upper == lower) {
199 if (upper - lower > 1) {
203 std::swap(_items[lower], _items[i]);
206 int median = (upper + lower) / 2;
207 std::nth_element(_items.begin() + lower + 1,
208 _items.begin() + median,
209 _items.begin() + upper,
217 node->
left = buildFromPoints(lower + 1, median);
218 node->
right = buildFromPoints(median, upper);
226 void search(
Node* node,
const T& target,
int k, std::priority_queue<HeapItem>& heap)
228 if(node == NULL)
return;
235 if(heap.size() ==
static_cast<size_t>(k)) heap.pop();
237 if(heap.size() ==
static_cast<size_t>(k)) _tau = heap.top().dist;
241 if(node->
left == NULL && node->
right == NULL) {
246 if(dist < node->threshold) {
247 if(dist - _tau <= node->threshold) {
248 search(node->
left, target, k, heap);
252 search(node->
right, target, k, heap);
258 search(node->
right, target, k, heap);
261 if (dist - _tau <= node->threshold) {
262 search(node->
left, target, k, heap);
ScalarType distance(Callback &cb, const CoverTreePoint< RandomAccessIterator > &l, const CoverTreePoint< RandomAccessIterator > &r, ScalarType upper_bound)
void search(const T &target, int k, std::vector< T > *results, std::vector< double > *distances)
Namespace containing implementation of t-SNE algorithm.
bool operator()(const T &a, const T &b)
double euclidean_distance(const DataPoint &t1, const DataPoint &t2)
DataPoint(const DataPoint &other)
ScalarType uniform_random()
DataPoint(int Dv, int indv, double *xv)
HeapItem(int indexv, double distv)
DistanceComparator(const T &itemv)
void search(Node *node, const T &target, int k, std::priority_queue< HeapItem > &heap)
void create(const std::vector< T > &items)
bool operator<(const HeapItem &o) const
int dimensionality() const
Covertree-based method with approximate time complexity. Recommended to be used as a default method...
DataPoint & operator=(const DataPoint &other)
Node * buildFromPoints(int lower, int upper)