32 #ifndef __INDEX_HEAP_H 33 #define __INDEX_HEAP_H 51 template<
typename IT,
typename VT>
66 Entry(
const IT index,
const VT value): index(index), value(value) {}
73 typedef typename Eigen::Matrix<Index, Eigen::Dynamic, 1>
IndexVector;
75 typedef typename Eigen::Matrix<Value, Eigen::Dynamic, 1>
ValueVector;
86 data(1,
Entry(invalidIndex<IT>(), invalidValue<VT>())),
96 data.push_back(
Entry(invalidIndex<IT>(), invalidValue<VT>()));
101 inline const VT&
headValue()
const {
return data.front().value; }
111 pop_heap(data.begin(), data.end());
112 data.back() =
Entry(index, value);
116 data.push_back(
Entry(index, value));
119 push_heap(data.begin(), data.end());
125 sort_heap (data.begin(), data.end());
131 template<
typename DI,
typename DV>
132 inline void getData(
const Eigen::MatrixBase<DI>& indices,
const Eigen::MatrixBase<DV> & values)
const 139 for (; i < data.size(); ++i)
141 const_cast<Eigen::MatrixBase<DI>&
>(indices).coeffRef(i) = data[i].index;
142 const_cast<Eigen::MatrixBase<DV>&
>(values).coeffRef(i) = data[i].value;
146 const_cast<Eigen::MatrixBase<DI>&
>(indices).coeffRef(i) = invalidIndex<IT>();
147 const_cast<Eigen::MatrixBase<DV>&
>(values).coeffRef(i) = invalidValue<VT>();
154 inline IndexVector getIndexes()
const 156 IndexVector indexes(data.capacity());
158 for (; i < data.size(); ++i)
159 indexes.coeffRef(i) = data[i].index;
160 for (; i < data.capacity(); ++i)
161 indexes.coeffRef(i) = 0;
171 template<
typename IT,
typename VT>
191 typedef std::vector<Entry>
Entries;
193 typedef typename Eigen::Matrix<Index, Eigen::Dynamic, 1>
IndexVector;
198 const VT& headValueRef;
200 const size_t sizeMinusOne;
205 data(size,
Entry(0, std::numeric_limits<VT>::infinity())),
206 headValueRef((data.end() - 1)->
value),
207 sizeMinusOne(data.size() - 1)
214 for (
typename Entries::iterator it(data.begin()); it != data.end(); ++it)
216 it->value = std::numeric_limits<VT>::infinity();
223 inline const VT&
headValue()
const {
return data[0].value; }
231 for (; i < sizeMinusOne; ++i)
233 if (data[i + 1].value > value)
234 data[i] = data[i + 1];
238 data[i].value =
value;
239 data[i].index =
index;
250 inline IndexVector getIndexes()
const 252 IndexVector indexes(data.size());
253 for (
size_t i = 0; i < data.size(); ++i)
254 indexes.coeffRef(i) = data[sizeMinusOne-i].index;
263 template<
typename IT,
typename VT>
278 Entry(
const IT index,
const VT value): index(index), value(value) {}
285 typedef typename Eigen::Matrix<Index, Eigen::Dynamic, 1>
IndexVector;
287 typedef typename Eigen::Matrix<Value, Eigen::Dynamic, 1>
ValueVector;
299 data(size,
Entry(invalidIndex<IT>(), invalidValue<VT>())),
300 headValueRef((data.end() - 1)->
value),
301 sizeMinusOne(data.size() - 1)
308 for (
typename Entries::iterator it(data.begin()); it != data.end(); ++it)
310 it->value = invalidValue<VT>();
311 it->index = invalidIndex<IT>();
317 inline const VT&
headValue()
const {
return headValueRef; }
325 for (i = sizeMinusOne; i > 0; --i)
327 if (data[i-1].value > value)
332 data[i].value =
value;
333 data[i].index =
index;
345 template<
typename DI,
typename DV>
346 inline void getData(
const Eigen::MatrixBase<DI>& indices,
const Eigen::MatrixBase<DV> & values)
const 352 for (
size_t i = 0; i < data.size(); ++i)
354 const_cast<Eigen::MatrixBase<DI>&
>(indices).coeffRef(i) = data[i].index;
355 const_cast<Eigen::MatrixBase<DV>&
>(values).coeffRef(i) = data[i].value;
361 inline IndexVector getIndexes()
const 363 IndexVector indexes(data.size());
364 for (
size_t i = 0; i < data.size(); ++i)
365 indexes.coeffRef(i) = data[i].index;
372 #endif // __INDEX_HEAP_H IndexHeapBruteForceVector(const size_t size)
Constructor.
Definition: index_heap.h:298
friend bool operator<(const Entry &e0, const Entry &e1)
return true if e0 is smaller than e1, false otherwise
Definition: index_heap.h:280
void replaceHead(const Index index, const Value value)
replace the largest value of the heap
Definition: index_heap.h:322
void sort()
sort the entries, from the smallest to the largest
Definition: index_heap.h:337
void sort()
sort the entries, from the smallest to the largest
Definition: index_heap.h:123
an entry of the heap vector
Definition: index_heap.h:272
Eigen::Matrix< Value, Eigen::Dynamic, 1 > ValueVector
vector of values
Definition: index_heap.h:75
IT index
index of point
Definition: index_heap.h:62
std::vector< Entry > Entries
vector of entry, type for the storage of the tree
Definition: index_heap.h:71
void getData(const Eigen::MatrixBase< DI > &indices, const Eigen::MatrixBase< DV > &values) const
get the data from the heap
Definition: index_heap.h:132
const VT & headValue() const
get the largest value of the heap
Definition: index_heap.h:101
const VT & headValueRef
reference to the largest value in the tree, to optimise access speed
Definition: index_heap.h:292
VT value
distance for this point
Definition: index_heap.h:275
Eigen::Matrix< Index, Eigen::Dynamic, 1 > IndexVector
vector of indices
Definition: index_heap.h:285
std::vector< Entry > Entries
vector of entry, type for the storage of the tree
Definition: index_heap.h:283
Entries data
storage for the tree
Definition: index_heap.h:290
Entry(const IT index, const VT value)
create a new entry
Definition: index_heap.h:278
const VT & headValue() const
get the largest value of the heap
Definition: index_heap.h:317
Eigen::Matrix< Value, Eigen::Dynamic, 1 > ValueVector
vector of values
Definition: index_heap.h:287
const size_t nbNeighbours
number of neighbours requested
Definition: index_heap.h:80
VT Value
type of a value
Definition: index_heap.h:57
const size_t sizeMinusOne
pre-competed size minus one, to optimise access speed
Definition: index_heap.h:294
Entries data
storage for the tree
Definition: index_heap.h:78
void reset()
reset to the empty heap
Definition: index_heap.h:93
an entry of the heap tree
Definition: index_heap.h:60
void replaceHead(const Index index, const Value value)
put value into heap, replace the largest value if full
Definition: index_heap.h:106
balanced-tree implementation of heap
Definition: index_heap.h:52
IndexHeapSTL(const size_t size)
Constructor.
Definition: index_heap.h:85
Namespace for Nabo.
Definition: brute_force_cpu.cpp:40
IT Index
type of an index
Definition: index_heap.h:267
void reset()
reset to the empty heap
Definition: index_heap.h:306
IT index
index of point
Definition: index_heap.h:274
void getData(const Eigen::MatrixBase< DI > &indices, const Eigen::MatrixBase< DV > &values) const
get the data from the heap
Definition: index_heap.h:346
Entry(const IT index, const VT value)
create a new entry
Definition: index_heap.h:66
brute-force implementation of heap
Definition: index_heap.h:264
VT Value
type of a value
Definition: index_heap.h:269
VT value
distance for this point
Definition: index_heap.h:63
Eigen::Matrix< Index, Eigen::Dynamic, 1 > IndexVector
vector of indices
Definition: index_heap.h:73
friend bool operator<(const Entry &e0, const Entry &e1)
return true if e0 is of lower value than e1, false otherwise
Definition: index_heap.h:68
IT Index
type of an index
Definition: index_heap.h:55