6 #ifndef TAPKEE_VPTREE_H_
7 #define TAPKEE_VPTREE_H_
20 namespace tapkee_internal
23 template<
class Type,
class RandomAccessIterator,
class DistanceCallback>
26 template<
class RandomAccessIterator,
class DistanceCallback>
30 const RandomAccessIterator
item;
33 inline bool operator()(
const RandomAccessIterator& a,
const RandomAccessIterator& b)
42 template<
class RandomAccessIterator,
class DistanceCallback>
45 inline bool operator()(DistanceCallback& callback,
const RandomAccessIterator& item,
46 const RandomAccessIterator& a,
const RandomAccessIterator& b)
48 return (-2*callback(item,a) + callback(a,a)) < (-2*callback(item,b) + callback(b,b));
54 template<
class RandomAccessIterator,
class DistanceCallback>
57 inline bool operator()(DistanceCallback& callback,
const RandomAccessIterator& item,
58 const RandomAccessIterator& a,
const RandomAccessIterator& b)
60 return callback(item,a) < callback(item,b);
64 template<
class RandomAccessIterator,
class DistanceCallback>
74 for (RandomAccessIterator i=b; i!=e; ++i)
86 std::vector<IndexType>
search(
const RandomAccessIterator& target,
int k)
88 std::vector<IndexType> results;
90 std::priority_queue<HeapItem> heap;
93 tau = std::numeric_limits<double>::max();
100 while(!heap.empty()) {
101 results.push_back(
items[heap.top().index]-
begin);
113 std::vector<RandomAccessIterator>
items;
162 if (upper - lower > 1)
167 int median = (upper + lower) / 2;
168 std::nth_element(
items.begin() + lower + 1,
items.begin() + median,
items.begin() + upper,
180 void search(
Node*
node,
const RandomAccessIterator& target,
int k, std::priority_queue<HeapItem>& heap)
189 if (heap.size() ==
static_cast<size_t>(k))
194 if (heap.size() ==
static_cast<size_t>(k))
195 tau = heap.top().distance;
198 if (node->
left == NULL && node->
right == NULL)
203 if (distance < node->threshold)
ScalarType distance(Callback &cb, const CoverTreePoint< RandomAccessIterator > &l, const CoverTreePoint< RandomAccessIterator > &r, ScalarType upper_bound)
HeapItem(int i, double d)
DistanceCallback callback
bool operator()(DistanceCallback &callback, const RandomAccessIterator &item, const RandomAccessIterator &a, const RandomAccessIterator &b)
bool operator()(DistanceCallback &callback, const RandomAccessIterator &item, const RandomAccessIterator &a, const RandomAccessIterator &b)
DistanceComparator(const DistanceCallback &c, const RandomAccessIterator &i)
DistanceCallback callback
RandomAccessIterator begin
Node & operator=(const Node &)
ScalarType uniform_random()
void search(Node *node, const RandomAccessIterator &target, int k, std::priority_queue< HeapItem > &heap)
Node * buildFromPoints(int lower, int upper)
bool operator()(const RandomAccessIterator &a, const RandomAccessIterator &b)
VantagePointTree & operator=(const VantagePointTree &)
const RandomAccessIterator item
bool operator<(const HeapItem &o) const
std::vector< RandomAccessIterator > items
std::vector< IndexType > search(const RandomAccessIterator &target, int k)
VantagePointTree(RandomAccessIterator b, RandomAccessIterator e, DistanceCallback c)
struct tapkee::tapkee_internal::VantagePointTree::Node * root