LSSTApplications  10.0-2-g4f67435,11.0.rc2+1,11.0.rc2+12,11.0.rc2+3,11.0.rc2+4,11.0.rc2+5,11.0.rc2+6,11.0.rc2+7,11.0.rc2+8
LSSTDataManagementBasePackage
Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
lsst.afw.math::KdTree< T > Class Template Reference

The data for GaussianProcess is stored in a KD tree to facilitate nearest-neighbor searches. More...

#include <GaussianProcess.h>

Inheritance diagram for lsst.afw.math::KdTree< T >:

Public Member Functions

void Initialize (ndarray::Array< T, 2, 2 > const &dt)
 Build a KD Tree to store the data for GaussianProcess. More...
 
void findNeighbors (ndarray::Array< int, 1, 1 > neighdex, ndarray::Array< double, 1, 1 > dd, ndarray::Array< const T, 1, 1 > const &v, int n_nn) const
 Find the nearest neighbors of a point. More...
 
getData (int ipt, int idim) const
 Return one element of one node on the tree. More...
 
ndarray::Array< T, 1, 1 > getData (int ipt) const
 Return an entire node from the tree. More...
 
void addPoint (ndarray::Array< const T, 1, 1 > const &v)
 Add a point to the tree. Allot more space in _tree and data if needed. More...
 
void removePoint (int dex)
 Remove a point from the tree. Reorganize what remains so that the tree remains self-consistent. More...
 
int getPoints () const
 return the number of data points stored in the tree More...
 
void getTreeNode (ndarray::Array< int, 1, 1 > const &v, int dex) const
 Return the _tree information for a given data point. More...
 

Private Types

enum  { DIMENSION, LT, GEQ, PARENT }
 

Private Member Functions

void _organize (ndarray::Array< int, 1, 1 > const &use, int ct, int parent, int dir)
 Find the daughter point of a node in the tree and segregate the points around it. More...
 
int _findNode (ndarray::Array< const T, 1, 1 > const &v) const
 Find the point already in the tree that would be the parent of a point not in the tree. More...
 
void _lookForNeighbors (ndarray::Array< const T, 1, 1 > const &v, int consider, int from) const
 This method actually looks for the neighbors, determining whether or not to descend branches of the tree. More...
 
int _testTree () const
 Make sure that the tree is properly constructed. Returns 1 of it is. Return zero if not. More...
 
int _walkUpTree (int target, int dir, int root) const
 A method to make sure that every data point in the tree is in the correct position relative to its parents. More...
 
void _count (int where, int *ct) const
 A method which counts the number of nodes descended from a given node (used by removePoint(int)) More...
 
void _descend (int root)
 Descend the tree from a node which has been removed, reassigning severed nodes as you go. More...
 
void _reassign (int target)
 Reassign nodes to the tree that were severed by a call to removePoint(int) More...
 
double _distance (ndarray::Array< const T, 1, 1 > const &p1, ndarray::Array< const T, 1, 1 > const &p2) const
 calculate the Euclidean distance between the points p1 and p2 More...
 

Private Attributes

ndarray::Array< int, 2, 2 > _tree
 
ndarray::Array< int, 1, 1 > _inn
 
ndarray::Array< T, 2, 2 > _data
 
int _pts
 
int _dimensions
 
int _room
 
int _roomStep
 
int _masterParent
 
int _neighborsFound
 
int _neighborsWanted
 
ndarray::Array< double, 1, 1 > _neighborDistances
 
ndarray::Array< int, 1, 1 > _neighborCandidates
 

Detailed Description

template<typename T>
class lsst.afw.math::KdTree< T >

The data for GaussianProcess is stored in a KD tree to facilitate nearest-neighbor searches.

Note: I have removed the ability to arbitrarily specify a distance function. The KD Tree nearest neighbor search algorithm only makes sense in the case of Euclidean distances, so I have forced KdTree to use Euclidean distances.

Definition at line 241 of file GaussianProcess.h.

Member Enumeration Documentation

template<typename T >
anonymous enum
private

Member Function Documentation

template<typename T >
void lsst.afw.math::KdTree< T >::_count ( int  where,
int *  ct 
) const
private

A method which counts the number of nodes descended from a given node (used by removePoint(int))

Parameters
[in]wherethe node you are currently on
[in,out]*ctkeeps track of how many nodes you have encountered as you descend the tree

Definition at line 676 of file GaussianProcess.cc.

677 {
678  //a way to count the number of vital elements on a given branch
679 
680  if(_tree[where][LT] >= 0) {
681  ct[0]++;
682  _count(_tree[where][LT], ct);
683  }
684  if(_tree[where][GEQ] >= 0) {
685  ct[0]++;
686  _count(_tree[where][GEQ], ct);
687  }
688 }
void _count(int where, int *ct) const
A method which counts the number of nodes descended from a given node (used by removePoint(int)) ...
ndarray::Array< int, 2, 2 > _tree
template<typename T >
void lsst.afw.math::KdTree< T >::_descend ( int  root)
private

Descend the tree from a node which has been removed, reassigning severed nodes as you go.

Parameters
rootthe index of the node where you are currently

Definition at line 718 of file GaussianProcess.cc.

719 {
720 
721  if(_tree[root][LT] >= 0) _descend(_tree[root][LT]);
722  if(_tree[root][GEQ] >= 0) _descend(_tree[root][GEQ]);
723 
724  _reassign(root);
725 }
ndarray::Array< int, 2, 2 > _tree
void _reassign(int target)
Reassign nodes to the tree that were severed by a call to removePoint(int)
void _descend(int root)
Descend the tree from a node which has been removed, reassigning severed nodes as you go...
template<typename T >
double lsst.afw.math::KdTree< T >::_distance ( ndarray::Array< const T, 1, 1 > const &  p1,
ndarray::Array< const T, 1, 1 > const &  p2 
) const
private

calculate the Euclidean distance between the points p1 and p2

Definition at line 728 of file GaussianProcess.cc.

730 {
731 
732  int i,dd;
733  double ans;
734  ans = 0.0;
735  dd = p1.template getSize< 0 >();
736 
737  for(i = 0;i < dd;i++ ) ans += (p1[i] - p2[i])*(p1[i] - p2[i]);
738 
739  return ::sqrt(ans);
740 
741 }
template<typename T >
int lsst.afw.math::KdTree< T >::_findNode ( ndarray::Array< const T, 1, 1 > const &  v) const
private

Find the point already in the tree that would be the parent of a point not in the tree.

Parameters
[in]vthe points whose prospective parent you want to find

Definition at line 435 of file GaussianProcess.cc.

436 {
437  int consider,next,dim;
438 
439  dim = _tree[_masterParent][DIMENSION];
440 
441  if(v[dim] < _data[_masterParent][dim]) consider = _tree[_masterParent][LT];
442  else consider = _tree[_masterParent][GEQ];
443 
444  next = consider;
445 
446  while(next >= 0){
447 
448  consider = next;
449 
450  dim = _tree[consider][DIMENSION];
451  if(v[dim] < _data[consider][dim]) next = _tree[consider][LT];
452  else next = _tree[consider][GEQ];
453 
454  }
455 
456  return consider;
457 }
ndarray::Array< T, 2, 2 > _data
ndarray::Array< int, 2, 2 > _tree
template<typename T >
void lsst.afw.math::KdTree< T >::_lookForNeighbors ( ndarray::Array< const T, 1, 1 > const &  v,
int  consider,
int  from 
) const
private

This method actually looks for the neighbors, determining whether or not to descend branches of the tree.

Parameters
[in]vthe point whose neighbors you are looking for
[in]considerthe index of the data point you are considering as a possible nearest neighbor
[in]fromthe index of the point you last considered as a nearest neighbor (so the search does not backtrack along the tree)

The class KdTree keeps track of how many neighbors you want and how many neighbors you have found and what their distances from v are in the class member variables _neighborsWanted, _neighborsFound, _neighborCandidates, and _neighborDistances

Definition at line 460 of file GaussianProcess.cc.

463 {
464 
465  int i,j,going;
466  double dd;
467 
468  dd = _distance(v, _data[consider]);
469 
471 
472  for(j = 0; j < _neighborsFound && _neighborDistances[j] < dd; j++ );
473 
474  for(i = _neighborsWanted - 1; i > j; i-- ){
477  }
478 
479  _neighborDistances[j] = dd;
480  _neighborCandidates[j] = consider;
481 
483  }
484 
485  if(_tree[consider][PARENT] == from){
486  //you came here from the parent
487 
488  i = _tree[consider][DIMENSION];
489  dd = v[i] - _data[consider][i];
491  && _tree[consider][LT] >= 0){
492 
493  _lookForNeighbors(v, _tree[consider][LT], consider);
494  }
495 
496  dd = _data[consider][i] - v[i];
498  && _tree[consider][GEQ] >= 0){
499 
500  _lookForNeighbors(v, _tree[consider][GEQ], consider);
501  }
502  }
503  else{
504  //you came here from one of the branches
505 
506  //descend the other branch
507  if(_tree[consider][LT] == from){
508  going = GEQ;
509  }
510  else{
511  going = LT;
512  }
513 
514  j = _tree[consider][going];
515 
516  if(j >= 0){
517  i = _tree[consider][DIMENSION];
518 
519  if(going == 1) dd = v[i] - _data[consider][i];
520  else dd = _data[consider][i] - v[i];
521 
523  _lookForNeighbors(v, j, consider);
524  }
525  }
526 
527  //ascend to the parent
528  if(_tree[consider][PARENT] >= 0) {
529  _lookForNeighbors(v, _tree[consider][PARENT], consider);
530  }
531  }
532 }
ndarray::Array< T, 2, 2 > _data
ndarray::Array< int, 2, 2 > _tree
void _lookForNeighbors(ndarray::Array< const T, 1, 1 > const &v, int consider, int from) const
This method actually looks for the neighbors, determining whether or not to descend branches of the t...
double _distance(ndarray::Array< const T, 1, 1 > const &p1, ndarray::Array< const T, 1, 1 > const &p2) const
calculate the Euclidean distance between the points p1 and p2
ndarray::Array< int, 1, 1 > _neighborCandidates
ndarray::Array< double, 1, 1 > _neighborDistances
template<typename T >
void lsst.afw.math::KdTree< T >::_organize ( ndarray::Array< int, 1, 1 > const &  use,
int  ct,
int  parent,
int  dir 
)
private

Find the daughter point of a node in the tree and segregate the points around it.

Parameters
[in]usethe indices of the data points being considered as possible daughters
[in]ctthe number of possible daughters
[in]parentthe index of the parent whose daughter we are chosing
[in]dirwhich side of the parent are we on? dir==1 means that we are on the left side; dir==2 means the right side.

Definition at line 328 of file GaussianProcess.cc.

333 {
334 
335  int i,j,k,l,idim,daughter;
336  T mean,var,varbest;
337 
338 
339  std::vector < std::vector < T > > toSort;
340  std::vector < T > toSortElement;
341 
342  if(ct > 1){
343  //below is code to choose the dimension on which the available points
344  //have the greates variance. This will be the dimension on which
345  //the daughter node splits the data
346  idim=0;
347  varbest=-1.0;
348  for (i = 0; i < _dimensions; i++ ) {
349  mean = 0.0;
350  var = 0.0;
351  for (j = 0; j < ct; j++ ) {
352  mean += _data[use[j]][i];
353  var += _data[use[j]][i]*_data[use[j]][i];
354  }
355  mean = mean/double(ct);
356  var = var/double(ct) - mean*mean;
357  if(i == 0 || var > varbest ||
358  (var == varbest && parent >= 0 && i > _tree[parent][DIMENSION])) {
359  idim = i;
360  varbest = var;
361  }
362  }//for(i = 0;i < _dimensions;i++ )
363 
364  //we need to sort the available data points according to their idim - th element
365  //but we need to keep track of their original indices, so we can refer back to
366  //their positions in _data. Therefore, the code constructs a 2 - dimensional
367  //std::vector. The first dimension contains the element to be sorted.
368  //The second dimension contains the original index information.
369  //After sorting, the (rearranged) index information will be stored back in the
370  //ndarray use[]
371 
372  toSortElement.push_back(_data[use[0]][idim]);
373  toSortElement.push_back(T(use[0]));
374  toSort.push_back(toSortElement);
375  for(i = 1; i < ct; i++ ) {
376  toSortElement[0] = _data[use[i]][idim];
377  toSortElement[1] = T(use[i]);
378  toSort.push_back(toSortElement);
379  }
380 
381  std::stable_sort(toSort.begin(), toSort.end());
382 
383  k = ct/2;
384  l = ct/2;
385  while(k > 0 && toSort[k][0] == toSort[k - 1][0]) k--;
386 
387  while(l < ct - 1 && toSort[l][0] == toSort[ct/2][0]) l++;
388 
389  if((ct/2 - k) < (l - ct/2) || l == ct - 1) j = k;
390  else j = l;
391 
392  for(i = 0; i < ct; i++ ) {
393  use[i] = int(toSort[i][1]);
394  }
395  daughter = use[j];
396 
397  if(parent >= 0)_tree[parent][dir] = daughter;
398  _tree[daughter][DIMENSION] = idim;
399  _tree[daughter][PARENT] = parent;
400 
401  if(j < ct - 1){
402  _organize(use[ndarray::view(j + 1,use.getSize < 0 > ())], ct - j - 1, daughter, GEQ);
403  }
404  else _tree[daughter][GEQ] = -1;
405 
406  if(j > 0){
407  _organize(use, j, daughter, LT);
408  }
409  else _tree[daughter][LT] = -1;
410 
411  }//if(ct > 1)
412  else{
413  daughter = use[0];
414 
415  if(parent >= 0) _tree[parent][dir] = daughter;
416 
417  idim = _tree[parent][DIMENSION] + 1;
418 
419  if(idim >= _dimensions)idim = 0;
420 
421  _tree[daughter][DIMENSION] = idim;
422  _tree[daughter][LT] = - 1;
423  _tree[daughter][GEQ] = - 1;
424  _tree[daughter][PARENT] = parent;
425 
426  }
427 
428  if(parent == - 1){
429  _masterParent = daughter;
430  }
431 
432 }
View< boost::fusion::vector1< index::Full > > view()
Start a view definition that includes the entire first dimension.
Definition: views.h:131
void _organize(ndarray::Array< int, 1, 1 > const &use, int ct, int parent, int dir)
Find the daughter point of a node in the tree and segregate the points around it. ...
ndarray::Array< T, 2, 2 > _data
ndarray::Array< int, 2, 2 > _tree
template<typename T >
void lsst.afw.math::KdTree< T >::_reassign ( int  target)
private

Reassign nodes to the tree that were severed by a call to removePoint(int)

Parameters
targetthe node you are reassigning

Definition at line 691 of file GaussianProcess.cc.

692 {
693 
694  int where,dir,k;
695 
696  where = _masterParent;
697  if(_data[target][_tree[where][DIMENSION]] < _data[where][_tree[where][DIMENSION]]) dir = LT;
698  else dir = GEQ;
699 
700  k = _tree[where][dir];
701  while(k >= 0) {
702  where = k;
703  if(_data[target][_tree[where][DIMENSION]] < _data[where][_tree[where][DIMENSION]]) dir = LT;
704  else dir = GEQ;
705  k = _tree[where][dir];
706  }
707 
708  _tree[where][dir] = target;
709  _tree[target][PARENT] = where;
710  _tree[target][LT] = - 1;
711  _tree[target][GEQ] = - 1;
712  _tree[target][DIMENSION] = _tree[where][DIMENSION] + 1;
713 
714  if(_tree[target][DIMENSION] == _dimensions) _tree[target][DIMENSION] = 0;
715 }
ndarray::Array< T, 2, 2 > _data
ndarray::Array< int, 2, 2 > _tree
template<typename T >
int lsst.afw.math::KdTree< T >::_testTree ( ) const
private

Make sure that the tree is properly constructed. Returns 1 of it is. Return zero if not.

Definition at line 279 of file GaussianProcess.cc.

279  {
280 
281  int i,j,output;
282  std::vector < int > isparent;
283 
284  output=1;
285 
286  for (i = 0; i < _pts; i++ ) isparent.push_back(0);
287 
288  j = 0;
289  for (i = 0; i < _pts; i++ ) {
290  if(_tree[i][PARENT] < 0)j++;
291  }
292  if(j != 1){
293  std::cout << "_tree FAILURE " << j << " _masterParents\n";
294  return 0;
295  }
296 
297  for (i = 0; i < _pts; i++ ) {
298  if(_tree[i][PARENT] >= 0){
299  isparent[_tree[i][PARENT]]++;
300  }
301  }
302 
303  for (i = 0; i < _pts; i++ ) {
304  if(isparent[i] > 2){
305  std::cout << "_tree FAILURE " << i << " is parent to " << isparent[i] << "\n";
306  return 0;
307  }
308  }
309 
310 
311  for (i = 0; i < _pts; i++ ) {
312  if(_tree[i][PARENT] >= 0) {
313  if(_tree[_tree[i][PARENT]][LT] == i)j = LT;
314  else j = GEQ;
315  output = _walkUpTree(_tree[i][PARENT], j, i);
316 
317  if(output != _masterParent){
318  return 0;
319  }
320  }
321  }
322 
323  if(output != _masterParent) return 0;
324  else return 1;
325 }
ndarray::Array< int, 2, 2 > _tree
int _walkUpTree(int target, int dir, int root) const
A method to make sure that every data point in the tree is in the correct position relative to its pa...
template<typename T >
int lsst.afw.math::KdTree< T >::_walkUpTree ( int  target,
int  dir,
int  root 
) const
private

A method to make sure that every data point in the tree is in the correct position relative to its parents.

Parameters
[in]targetis the index of the node you are looking at
[in]diris the direction (1,2) of the branch you ascended from root
[in]rootis the node you started walking up from

This method returns the value of _masterParent if the branch is correctly contructed. It returns zero otherwise

Definition at line 535 of file GaussianProcess.cc.

538 {
539  //target is the node that you are examining now
540  //dir is where you came from
541  //root is the ultimate point from which you started
542 
543  int i,output;
544 
545  output = 1;
546 
547  if(dir == LT){
548  if(_data[root][_tree[target][DIMENSION]] >= _data[target][_tree[target][DIMENSION]]){
549  return 0;
550  }
551  }
552  else{
553  if(_data[root][_tree[target][DIMENSION]] < _data[target][_tree[target][DIMENSION]]) {
554  return 0;
555  }
556  }
557 
558  if(_tree[target][PARENT] >= 0){
559  if(_tree[_tree[target][PARENT]][LT] == target)i = LT;
560  else i = GEQ;
561  output = output*_walkUpTree(_tree[target][PARENT],i,root);
562 
563  }
564  else{
565  output = output*target;
566  //so that it will return _masterParent
567  //make sure everything is connected to _masterParent
568  }
569  return output;
570 
571 }
ndarray::Array< T, 2, 2 > _data
ndarray::Array< int, 2, 2 > _tree
int _walkUpTree(int target, int dir, int root) const
A method to make sure that every data point in the tree is in the correct position relative to its pa...
template<typename T >
void lsst.afw.math::KdTree< T >::addPoint ( ndarray::Array< const T, 1, 1 > const &  v)

Add a point to the tree. Allot more space in _tree and data if needed.

Parameters
[in]vthe point you are adding to the tree
Exceptions
pex_exceptionsRuntimeError if the branch ending in the new point is not properly constructed

Definition at line 196 of file GaussianProcess.cc.

197 {
198 
199  int i,j,node,dim,dir;
200 
201  node = _findNode(v);
202  dim = _tree[node][DIMENSION] + 1;
203  if(dim == _dimensions)dim = 0;
204 
205  if(_pts == _room){
206 
209 
210  dbuff.deep() = _data;
211  tbuff.deep() = _tree;
212 
213  _room += _roomStep;
214 
217 
218 
219  for (i = 0; i < _pts; i++ ) {
220  for (j = 0; j < _dimensions; j++ ) _data[i][j] = dbuff[i][j];
221  for (j = 0; j < 4; j++ ) _tree[i][j] = tbuff[i][j];
222  }
223  }
224 
225  _tree[_pts][DIMENSION] = dim;
226  _tree[_pts][PARENT] = node;
227  i = _tree[node][DIMENSION];
228 
229  if(_data[node][i] > v[i]){
230  if(_tree[node][LT] >= 0){
231  throw LSST_EXCEPT(lsst::pex::exceptions::RuntimeError,
232  "Trying to add to KdTree in a node that is already occupied\n");
233  }
234  _tree[node][LT] = _pts;
235  dir=LT;
236  }
237  else{
238  if(_tree[node][GEQ] >= 0){
239  throw LSST_EXCEPT(lsst::pex::exceptions::RuntimeError,
240  "Trying to add to KdTree in a node that is already occupied\n");
241  }
242  _tree[node][GEQ] = _pts;
243  dir=GEQ;
244  }
245  _tree[_pts][LT] = -1;
246  _tree[_pts][GEQ] = -1;
247  for (i = 0; i < _dimensions; i++ ) {
248  _data[_pts][i] = v[i];
249  }
250 
251  _pts++;
252 
253 
254  i = _walkUpTree(_tree[_pts-1][PARENT], dir, _pts-1);
255  if (i != _masterParent){
256  throw LSST_EXCEPT(lsst::pex::exceptions::RuntimeError,
257  "Adding to KdTree failed\n");
258  }
259 
260 }
ndarray::Array< T, 2, 2 > _data
int _findNode(ndarray::Array< const T, 1, 1 > const &v) const
Find the point already in the tree that would be the parent of a point not in the tree...
ndarray::Array< int, 2, 2 > _tree
Vector< T, N > makeVector(T v1, T v2,..., T vN)
Variadic constructor for Vector.
detail::SimpleInitializer< N > allocate(Vector< int, N > const &shape)
Create an expression that allocates uninitialized memory for an array.
#define LSST_EXCEPT(type,...)
Definition: Exception.h:46
Deep const deep() const
Return an ArrayRef view to this.
Definition: ArrayBase.h:178
int _walkUpTree(int target, int dir, int root) const
A method to make sure that every data point in the tree is in the correct position relative to its pa...
template<typename T >
void lsst.afw.math::KdTree< T >::findNeighbors ( ndarray::Array< int, 1, 1 >  neighdex,
ndarray::Array< double, 1, 1 >  dd,
ndarray::Array< const T, 1, 1 > const &  v,
int  n_nn 
) const

Find the nearest neighbors of a point.

Parameters
[out]neighdexthis is where the indices of the nearest neighbor points will be stored
[out]ddthis is where the distances to the nearest neighbors will be stored
[in]vthe point whose neighbors you want to find
[in]n_nnthe number of nearest neighbors you want to find

neighbors will be returned in ascending order of distance

note that distance is forced to be the Euclidean distance

Definition at line 150 of file GaussianProcess.cc.

154 {
155  int i,start;
156 
159  _neighborsFound = 0;
160  _neighborsWanted = n_nn;
161 
162  for (i = 0; i < n_nn; i++ ) _neighborDistances[i] = -1.0;
163 
164  start = _findNode(v);
165 
166  _neighborDistances[0] = _distance(v,_data[start]);
167  _neighborCandidates[0] = start;
168  _neighborsFound = 1;
169 
170 
171  for (i = 1; i < 4; i++ ) {
172  if(_tree[start][i] >= 0){
173  _lookForNeighbors(v,_tree[start][i], start);
174  }
175  }
176 
177  for (i = 0 ; i < n_nn ; i++ ) {
178  neighdex[i] = _neighborCandidates[i];
179  dd[i] = _neighborDistances[i];
180  }
181 }
ndarray::Array< T, 2, 2 > _data
int _findNode(ndarray::Array< const T, 1, 1 > const &v) const
Find the point already in the tree that would be the parent of a point not in the tree...
ndarray::Array< int, 2, 2 > _tree
Vector< T, N > makeVector(T v1, T v2,..., T vN)
Variadic constructor for Vector.
detail::SimpleInitializer< N > allocate(Vector< int, N > const &shape)
Create an expression that allocates uninitialized memory for an array.
void _lookForNeighbors(ndarray::Array< const T, 1, 1 > const &v, int consider, int from) const
This method actually looks for the neighbors, determining whether or not to descend branches of the t...
double _distance(ndarray::Array< const T, 1, 1 > const &p1, ndarray::Array< const T, 1, 1 > const &p2) const
calculate the Euclidean distance between the points p1 and p2
ndarray::Array< int, 1, 1 > _neighborCandidates
ndarray::Array< double, 1, 1 > _neighborDistances
template<typename T >
T lsst.afw.math::KdTree< T >::getData ( int  ipt,
int  idim 
) const

Return one element of one node on the tree.

Parameters
[in]iptthe index of the node to return
[in]idimthe index of the dimension to return

Definition at line 184 of file GaussianProcess.cc.

185 {
186  return _data[ipt][idim];
187 }
ndarray::Array< T, 2, 2 > _data
template<typename T >
ndarray::Array< T, 1, 1 > lsst.afw.math::KdTree< T >::getData ( int  ipt) const

Return an entire node from the tree.

Parameters
[in]iptthe index of the node to return

I currently have this as a return-by-value method. When I tried it as a return-by-reference, the compiler gave me

warning: returning reference to local temporary object

Based on my reading of Stack Overflow, this is because ndarray was implicitly creating a new ndarray::Array<T,1,1> object and passing a reference thereto. It is unclear to me whether or not this object would be destroyed once the call to getData was complete.

The code still compiled, ran, and passed the unit tests, but the above behavior seemed to me like it could be dangerous (and, because ndarray was still creating a new object, it did not seem like we were saving any time), so I reverted to return-by-value.

Definition at line 190 of file GaussianProcess.cc.

191 {
192  return _data[ipt];
193 }
ndarray::Array< T, 2, 2 > _data
template<typename T >
int lsst.afw.math::KdTree< T >::getPoints ( ) const

return the number of data points stored in the tree

Definition at line 263 of file GaussianProcess.cc.

264 {
265  return _pts;
266 }
template<typename T >
void lsst.afw.math::KdTree< T >::getTreeNode ( ndarray::Array< int, 1, 1 > const &  v,
int  dex 
) const

Return the _tree information for a given data point.

Parameters
[out]vthe array in which to store the entry from _tree
[in]dexthe index of the node whose information you are requesting

Definition at line 269 of file GaussianProcess.cc.

271 {
272  v[0] = _tree[dex][DIMENSION];
273  v[1] = _tree[dex][LT];
274  v[2] = _tree[dex][GEQ];
275  v[3] = _tree[dex][PARENT];
276 }
ndarray::Array< int, 2, 2 > _tree
template<typename T >
void lsst.afw.math::KdTree< T >::Initialize ( ndarray::Array< T, 2, 2 > const &  dt)

Build a KD Tree to store the data for GaussianProcess.

Parameters
[in]dtan array, the rows of which are the data points (dt[i][j] is the jth component of the ith data point)
Exceptions
pex_exceptionsRuntimeError if the tree is not properly constructed

Definition at line 115 of file GaussianProcess.cc.

116 {
117  int i;
118 
119  _pts = dt.template getSize < 0 > ();
120  _dimensions = dt.template getSize < 1 > ();
121 
122  //a buffer to use when first building the tree
124 
125  _roomStep = 5000;
126  _room = _pts;
127 
128  _data = allocate(ndarray::makeVector(_room,_dimensions));
129 
130  _data.deep() = dt;
131 
133 
134  for (i = 0 ; i < _pts ; i++ ) {
135  _inn[i] = i;
136  }
137 
138  _organize(_inn,_pts, -1, -1);
139 
140 
141  i = _testTree();
142  if (i == 0) {
143  throw LSST_EXCEPT(lsst::pex::exceptions::RuntimeError,
144  "Failed to properly initialize KdTree\n");
145  }
146 
147 }
void _organize(ndarray::Array< int, 1, 1 > const &use, int ct, int parent, int dir)
Find the daughter point of a node in the tree and segregate the points around it. ...
int _testTree() const
Make sure that the tree is properly constructed. Returns 1 of it is. Return zero if not...
ndarray::Array< T, 2, 2 > _data
ndarray::Array< int, 2, 2 > _tree
Vector< T, N > makeVector(T v1, T v2,..., T vN)
Variadic constructor for Vector.
detail::SimpleInitializer< N > allocate(Vector< int, N > const &shape)
Create an expression that allocates uninitialized memory for an array.
#define LSST_EXCEPT(type,...)
Definition: Exception.h:46
Deep const deep() const
Return an ArrayRef view to this.
Definition: ArrayBase.h:178
ndarray::Array< int, 1, 1 > _inn
template<typename T >
void lsst.afw.math::KdTree< T >::removePoint ( int  dex)

Remove a point from the tree. Reorganize what remains so that the tree remains self-consistent.

Parameters
[in]dexthe index of the point you want to remove from the tree
Exceptions
pex_exceptionsRuntimeError if the entire tree is not poperly constructed after the point has been removed

Definition at line 574 of file GaussianProcess.cc.

575 {
576 
577  int nl,nr,i,j,k,side;
578  int root;
579 
580  nl = 0;
581  nr = 0;
582  if(_tree[target][LT] >= 0){
583  nl++ ;
584  _count(_tree[target][LT], &nl);
585  }
586 
587  if(_tree[target][GEQ] >= 0){
588  nr++;
589  _count(_tree[target][GEQ], &nr);
590  }
591 
592  if(nl == 0 && nr == 0){
593 
594  k = _tree[target][PARENT];
595 
596  if(_tree[k][LT] == target) _tree[k][LT] = - 1;
597  else if(_tree[k][GEQ] == target) _tree[k][GEQ] = - 1;
598 
599  }//if target is terminal
600  else if((nl == 0 && nr > 0) || (nr == 0 && nl > 0)){
601 
602  if(nl == 0) side = GEQ;
603  else side = LT;
604 
605  k = _tree[target][PARENT];
606  if(k >= 0){
607 
608  if(_tree[k][LT] == target){
609  _tree[k][LT] = _tree[target][side];
610  _tree[_tree[k][LT]][PARENT] = k;
611 
612  }
613  else{
614  _tree[k][GEQ] = _tree[target][side];
615  _tree[_tree[k][GEQ]][PARENT] = k;
616  }
617  }
618  else{
619  _masterParent = _tree[target][side];
620  _tree[_tree[target][side]][PARENT] = - 1;
621  }
622  }//if only one side is populated
623  else{
624 
625  if(nl > nr)side = LT;
626  else side = GEQ;
627 
628  k = _tree[target][PARENT];
629  if(k < 0){
630  _masterParent = _tree[target][side];
631  _tree[_masterParent][PARENT] = - 1;
632  }
633  else{
634  if(_tree[k][LT] == target){
635  _tree[k][LT] = _tree[target][side];
636  _tree[_tree[k][LT]][PARENT] = k;
637  }
638  else{
639  _tree[k][GEQ] = _tree[target][side];
640  _tree[_tree[k][GEQ]][PARENT] = k;
641  }
642  }
643 
644  root = _tree[target][3 - side];
645 
646  _descend(root);
647  }//if both sides are populated
648 
649  if(target < _pts - 1){
650  for(i = target + 1;i < _pts;i++ ){
651  for(j = 0; j < 4; j++ ) _tree[i - 1][j] = _tree[i][j];
652 
653  for(j = 0; j < _dimensions; j++ ) _data[i - 1][j] = _data[i][j];
654  }
655 
656  for(i = 0; i < _pts; i++ ){
657  for(j = 1; j < 4; j++ ){
658  if(_tree[i][j] > target) _tree[i][j]--;
659  }
660  }
661 
662  if(_masterParent > target)_masterParent-- ;
663  }
664  _pts--;
665 
666  i = _testTree();
667  if (i == 0) {
668  throw LSST_EXCEPT(lsst::pex::exceptions::RuntimeError,
669  "Subtracting from KdTree failed\n");
670  }
671 
672 
673 }
void _count(int where, int *ct) const
A method which counts the number of nodes descended from a given node (used by removePoint(int)) ...
int _testTree() const
Make sure that the tree is properly constructed. Returns 1 of it is. Return zero if not...
ndarray::Array< T, 2, 2 > _data
ndarray::Array< int, 2, 2 > _tree
void _descend(int root)
Descend the tree from a node which has been removed, reassigning severed nodes as you go...
#define LSST_EXCEPT(type,...)
Definition: Exception.h:46

Member Data Documentation

template<typename T >
ndarray::Array<T,2,2> lsst.afw.math::KdTree< T >::_data
private

Definition at line 349 of file GaussianProcess.h.

template<typename T >
int lsst.afw.math::KdTree< T >::_dimensions
private

Definition at line 367 of file GaussianProcess.h.

template<typename T >
ndarray::Array<int,1,1> lsst.afw.math::KdTree< T >::_inn
private

Definition at line 348 of file GaussianProcess.h.

template<typename T >
int lsst.afw.math::KdTree< T >::_masterParent
private

Definition at line 367 of file GaussianProcess.h.

template<typename T >
ndarray::Array<int,1,1> lsst.afw.math::KdTree< T >::_neighborCandidates
mutableprivate

Definition at line 375 of file GaussianProcess.h.

template<typename T >
ndarray::Array<double,1,1> lsst.afw.math::KdTree< T >::_neighborDistances
mutableprivate

Definition at line 374 of file GaussianProcess.h.

template<typename T >
int lsst.afw.math::KdTree< T >::_neighborsFound
mutableprivate

Definition at line 368 of file GaussianProcess.h.

template<typename T >
int lsst.afw.math::KdTree< T >::_neighborsWanted
mutableprivate

Definition at line 368 of file GaussianProcess.h.

template<typename T >
int lsst.afw.math::KdTree< T >::_pts
private

Definition at line 367 of file GaussianProcess.h.

template<typename T >
int lsst.afw.math::KdTree< T >::_room
private

Definition at line 367 of file GaussianProcess.h.

template<typename T >
int lsst.afw.math::KdTree< T >::_roomStep
private

Definition at line 367 of file GaussianProcess.h.

template<typename T >
ndarray::Array<int,2,2> lsst.afw.math::KdTree< T >::_tree
private

Definition at line 347 of file GaussianProcess.h.


The documentation for this class was generated from the following files: