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...
T	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

Enumerator
DIMENSION
LT
GEQ
PARENT

Definition at line 351 of file GaussianProcess.h.

{DIMENSION,LT,GEQ,PARENT};

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]	where	the node you are currently on
[in,out]	*ct	keeps track of how many nodes you have encountered as you descend the tree

Definition at line 676 of file GaussianProcess.cc.

{
    //a way to count the number of vital elements on a given branch

    if(_tree[where][LT] >= 0) {
        ct[0]++;
        _count(_tree[where][LT], ct);
    }
    if(_tree[where][GEQ] >= 0) {
        ct[0]++;
        _count(_tree[where][GEQ], ct);
    }
}

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

root	the index of the node where you are currently

Definition at line 718 of file GaussianProcess.cc.

{

    if(_tree[root][LT] >= 0) _descend(_tree[root][LT]);
    if(_tree[root][GEQ] >= 0) _descend(_tree[root][GEQ]);

    _reassign(root);
}

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.

{

    int i,dd;
    double ans;
    ans = 0.0;
    dd = p1.template getSize< 0 >();

    for(i = 0;i < dd;i++ ) ans += (p1[i] - p2[i])*(p1[i] - p2[i]);

    return ::sqrt(ans);

}

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]

v

the points whose prospective parent you want to find

Definition at line 435 of file GaussianProcess.cc.

{
    int consider,next,dim;

    dim = _tree[_masterParent][DIMENSION];

    if(v[dim] < _data[_masterParent][dim]) consider = _tree[_masterParent][LT];
    else consider = _tree[_masterParent][GEQ];

    next = consider;

    while(next >= 0){

        consider = next;

        dim = _tree[consider][DIMENSION];
        if(v[dim] < _data[consider][dim]) next = _tree[consider][LT];
        else next = _tree[consider][GEQ];

    }

    return consider;
}

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]	v	the point whose neighbors you are looking for
[in]	consider	the index of the data point you are considering as a possible nearest neighbor
[in]	from	the 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.

{

    int i,j,going;
    double dd;

    dd = _distance(v, _data[consider]);

    if(_neighborsFound < _neighborsWanted || dd < _neighborDistances[_neighborsWanted -1]) {

        for(j = 0; j < _neighborsFound && _neighborDistances[j] < dd; j++ );

        for(i = _neighborsWanted - 1; i > j; i-- ){
            _neighborDistances[i] = _neighborDistances[i - 1];
            _neighborCandidates[i] = _neighborCandidates[i - 1];
        }

        _neighborDistances[j] = dd;
        _neighborCandidates[j] = consider;

        if(_neighborsFound < _neighborsWanted) _neighborsFound++;
    }

    if(_tree[consider][PARENT] == from){
    //you came here from the parent

        i = _tree[consider][DIMENSION];
        dd = v[i] - _data[consider][i];
        if((dd <= _neighborDistances[_neighborsFound - 1] || _neighborsFound < _neighborsWanted)
            && _tree[consider][LT] >= 0){

              _lookForNeighbors(v, _tree[consider][LT], consider);
        }

        dd = _data[consider][i] - v[i];
        if((dd <= _neighborDistances[_neighborsFound - 1] || _neighborsFound < _neighborsWanted)
            && _tree[consider][GEQ] >= 0){

            _lookForNeighbors(v, _tree[consider][GEQ], consider);
        }
    }
    else{
    //you came here from one of the branches

        //descend the other branch
        if(_tree[consider][LT] == from){
            going = GEQ;
        }
        else{
            going = LT;
        }

        j = _tree[consider][going];

        if(j >= 0){
            i = _tree[consider][DIMENSION];

            if(going == 1) dd = v[i] - _data[consider][i];
            else dd = _data[consider][i] - v[i];

            if(dd <= _neighborDistances[_neighborsFound - 1] || _neighborsFound < _neighborsWanted) {
                  _lookForNeighbors(v, j, consider);
            }
        }

        //ascend to the parent
        if(_tree[consider][PARENT] >= 0) {
              _lookForNeighbors(v, _tree[consider][PARENT], consider);
        }
    }
}

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]	use	the indices of the data points being considered as possible daughters
[in]	ct	the number of possible daughters
[in]	parent	the index of the parent whose daughter we are chosing
[in]	dir	which 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.

{

    int i,j,k,l,idim,daughter;
    T mean,var,varbest;


    std::vector <  std::vector < T >   >  toSort;
    std::vector < T >  toSortElement;

    if(ct > 1){
      //below is code to choose the dimension on which the available points
      //have the greates variance.  This will be the dimension on which
      //the daughter node splits the data
        idim=0;
        varbest=-1.0;
        for (i = 0; i < _dimensions; i++ ) {
            mean = 0.0;
            var = 0.0;
            for (j = 0; j < ct; j++ ) {
                mean += _data[use[j]][i];
                var += _data[use[j]][i]*_data[use[j]][i];
            }
            mean = mean/double(ct);
            var = var/double(ct) - mean*mean;
            if(i == 0 || var > varbest || 
               (var == varbest && parent >= 0 && i > _tree[parent][DIMENSION])) {
                    idim = i;
                    varbest = var;
            }
        }//for(i = 0;i < _dimensions;i++ )

        //we need to sort the available data points according to their idim - th element
        //but we need to keep track of their original indices, so we can refer back to
        //their positions in _data.  Therefore, the code constructs a 2 - dimensional
        //std::vector.  The first dimension contains the element to be sorted.
        //The second dimension contains the original index information.
        //After sorting, the (rearranged) index information will be stored back in the
        //ndarray use[]

        toSortElement.push_back(_data[use[0]][idim]);
        toSortElement.push_back(T(use[0]));
        toSort.push_back(toSortElement);
        for(i = 1; i < ct; i++ ) {
            toSortElement[0] = _data[use[i]][idim];
            toSortElement[1] = T(use[i]);
            toSort.push_back(toSortElement);
        }

        std::stable_sort(toSort.begin(), toSort.end());

        k = ct/2;
        l = ct/2;
        while(k > 0 && toSort[k][0] == toSort[k - 1][0]) k--;

        while(l < ct - 1 && toSort[l][0] == toSort[ct/2][0]) l++;

        if((ct/2 - k) < (l - ct/2) || l == ct - 1) j = k;
        else j = l;

        for(i = 0; i < ct; i++ ) {
            use[i] = int(toSort[i][1]);
        }
        daughter = use[j];

        if(parent >= 0)_tree[parent][dir] = daughter;
        _tree[daughter][DIMENSION] = idim;
        _tree[daughter][PARENT] = parent;

        if(j < ct - 1){
            _organize(use[ndarray::view(j + 1,use.getSize < 0 > ())], ct - j - 1, daughter, GEQ);
        }
        else _tree[daughter][GEQ] =  -1;

        if(j > 0){
            _organize(use, j, daughter, LT);
        }
        else _tree[daughter][LT] =  -1;

    }//if(ct > 1)
    else{
        daughter = use[0];

        if(parent >= 0) _tree[parent][dir] = daughter;

        idim = _tree[parent][DIMENSION] + 1;

        if(idim >= _dimensions)idim = 0;

        _tree[daughter][DIMENSION] = idim;
        _tree[daughter][LT] =  - 1;
        _tree[daughter][GEQ] =  - 1;
        _tree[daughter][PARENT] = parent;

    }

    if(parent ==  - 1){
        _masterParent = daughter;
    }

}

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

target

the node you are reassigning

Definition at line 691 of file GaussianProcess.cc.

{

    int where,dir,k;

    where = _masterParent;
    if(_data[target][_tree[where][DIMENSION]] < _data[where][_tree[where][DIMENSION]]) dir = LT;
    else dir = GEQ;

    k = _tree[where][dir];
    while(k >= 0) {
        where = k;
        if(_data[target][_tree[where][DIMENSION]] < _data[where][_tree[where][DIMENSION]]) dir = LT;
        else dir = GEQ;
        k = _tree[where][dir];
    }

    _tree[where][dir] = target;
    _tree[target][PARENT] = where;
    _tree[target][LT] =  - 1;
    _tree[target][GEQ] =  - 1;
    _tree[target][DIMENSION] = _tree[where][DIMENSION] + 1;

    if(_tree[target][DIMENSION] == _dimensions) _tree[target][DIMENSION] = 0;
}

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.

                                  {

    int i,j,output;
    std::vector < int >  isparent;
    
    output=1;
    
    for (i = 0; i < _pts; i++ ) isparent.push_back(0);

    j = 0;
    for (i = 0; i < _pts; i++ ) {
        if(_tree[i][PARENT] < 0)j++;
    }
    if(j != 1){
        std::cout << "_tree FAILURE " << j << " _masterParents\n";
        return 0;
    }

    for (i = 0; i < _pts; i++ ) {
        if(_tree[i][PARENT] >= 0){
            isparent[_tree[i][PARENT]]++;
        }
    }

    for (i = 0; i < _pts; i++ ) {
        if(isparent[i] > 2){
            std::cout << "_tree FAILURE " << i << " is parent to " << isparent[i] << "\n";
            return 0;
        }
    }


    for (i = 0; i < _pts; i++ ) {
        if(_tree[i][PARENT] >= 0) {
            if(_tree[_tree[i][PARENT]][LT] == i)j = LT;
            else j = GEQ;
            output = _walkUpTree(_tree[i][PARENT], j, i);

            if(output != _masterParent){
                return 0;
            }
        }
    }

    if(output != _masterParent) return 0;
    else return 1;
}

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]	target	is the index of the node you are looking at
[in]	dir	is the direction (1,2) of the branch you ascended from root
[in]	root	is 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.

{
    //target is the node that you are examining now
    //dir is where you came from
    //root is the ultimate point from which you started

    int i,output;

    output = 1;

    if(dir == LT){
        if(_data[root][_tree[target][DIMENSION]] >= _data[target][_tree[target][DIMENSION]]){
            return 0;
        }
    }
    else{
        if(_data[root][_tree[target][DIMENSION]] < _data[target][_tree[target][DIMENSION]]) {
            return 0;
        }
    }

    if(_tree[target][PARENT] >= 0){
        if(_tree[_tree[target][PARENT]][LT] == target)i = LT;
        else i = GEQ;
        output = output*_walkUpTree(_tree[target][PARENT],i,root);

    }
    else{
        output = output*target;
        //so that it will return _masterParent
        //make sure everything is connected to _masterParent
    }
    return output;

}

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]

v

the point you are adding to the tree

Exceptions

pex_exceptions

RuntimeError if the branch ending in the new point is not properly constructed

Definition at line 196 of file GaussianProcess.cc.

{

    int i,j,node,dim,dir;

    node = _findNode(v);
    dim = _tree[node][DIMENSION] + 1;
    if(dim == _dimensions)dim = 0;

    if(_pts == _room){

        ndarray::Array < T,2,2 >  dbuff = allocate(ndarray::makeVector(_pts, _dimensions));
        ndarray::Array < int,2,2 >  tbuff = allocate(ndarray::makeVector(_pts, 4));

        dbuff.deep() = _data;
        tbuff.deep() = _tree;

        _room += _roomStep;
   
        _tree = allocate(ndarray::makeVector(_room, 4));
        _data = allocate(ndarray::makeVector(_room, _dimensions));


        for (i = 0; i < _pts; i++ ) {
            for (j = 0; j < _dimensions; j++ ) _data[i][j] = dbuff[i][j];
            for (j = 0; j < 4; j++ ) _tree[i][j] = tbuff[i][j];
        }
    }

    _tree[_pts][DIMENSION] = dim;
    _tree[_pts][PARENT] = node;
    i = _tree[node][DIMENSION];

    if(_data[node][i] > v[i]){
        if(_tree[node][LT] >= 0){
            throw LSST_EXCEPT(lsst::pex::exceptions::RuntimeError,
            "Trying to add to KdTree in a node that is already occupied\n");
        }
        _tree[node][LT] = _pts;
        dir=LT;
    }
    else{
        if(_tree[node][GEQ] >= 0){
            throw LSST_EXCEPT(lsst::pex::exceptions::RuntimeError,
            "Trying to add to KdTree in a node that is already occupied\n");
        }
        _tree[node][GEQ] = _pts;
        dir=GEQ;
    }
    _tree[_pts][LT] =  -1;
    _tree[_pts][GEQ] =  -1;
    for (i = 0; i < _dimensions; i++ ) {
        _data[_pts][i] = v[i];
    }

    _pts++;


    i = _walkUpTree(_tree[_pts-1][PARENT], dir, _pts-1);
    if (i != _masterParent){
        throw LSST_EXCEPT(lsst::pex::exceptions::RuntimeError,
        "Adding to KdTree failed\n");
    }

}

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]	neighdex	this is where the indices of the nearest neighbor points will be stored
[out]	dd	this is where the distances to the nearest neighbors will be stored
[in]	v	the point whose neighbors you want to find
[in]	n_nn	the 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.

{
    int i,start;

    _neighborCandidates = allocate(ndarray::makeVector(n_nn));
    _neighborDistances = allocate(ndarray::makeVector(n_nn));
    _neighborsFound = 0;
    _neighborsWanted = n_nn;

    for (i = 0; i < n_nn; i++ ) _neighborDistances[i] =  -1.0;

    start = _findNode(v);

    _neighborDistances[0] = _distance(v,_data[start]);
    _neighborCandidates[0] = start;
    _neighborsFound = 1;


    for (i = 1; i < 4; i++ ) {
        if(_tree[start][i] >= 0){
            _lookForNeighbors(v,_tree[start][i], start);
        }
    }

    for (i = 0 ; i < n_nn ; i++ ) {
        neighdex[i] = _neighborCandidates[i];
        dd[i] = _neighborDistances[i];
    }
}

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]	ipt	the index of the node to return
[in]	idim	the index of the dimension to return

Definition at line 184 of file GaussianProcess.cc.

{
    return _data[ipt][idim];
}

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]

ipt

the 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.

{
    return _data[ipt];
}

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.

{
    return _pts;
}

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]	v	the array in which to store the entry from _tree
[in]	dex	the index of the node whose information you are requesting

Definition at line 269 of file GaussianProcess.cc.

{
    v[0] = _tree[dex][DIMENSION];
    v[1] = _tree[dex][LT];
    v[2] = _tree[dex][GEQ];
    v[3] = _tree[dex][PARENT];
}

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]

dt

an array, the rows of which are the data points (dt[i][j] is the jth component of the ith data point)

Exceptions

pex_exceptions

RuntimeError if the tree is not properly constructed

Definition at line 115 of file GaussianProcess.cc.

{
    int i;

    _pts = dt.template getSize < 0 > ();
    _dimensions = dt.template getSize < 1 > ();

    //a buffer to use when first building the tree
    _inn = allocate(ndarray::makeVector(_pts));

    _roomStep = 5000;
    _room = _pts;

    _data = allocate(ndarray::makeVector(_room,_dimensions));

    _data.deep() = dt;

    _tree = allocate(ndarray::makeVector(_room,4));

    for (i = 0 ; i < _pts ; i++ ) {
      _inn[i] = i;
    }

    _organize(_inn,_pts, -1, -1);


    i = _testTree();
    if (i == 0) {
        throw LSST_EXCEPT(lsst::pex::exceptions::RuntimeError,
                          "Failed to properly initialize KdTree\n");
    }

}

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]

dex

the index of the point you want to remove from the tree

Exceptions

pex_exceptions

RuntimeError if the entire tree is not poperly constructed after the point has been removed

Definition at line 574 of file GaussianProcess.cc.

{

    int nl,nr,i,j,k,side;
    int root;

    nl = 0;
    nr = 0;
    if(_tree[target][LT] >= 0){
        nl++ ;
        _count(_tree[target][LT], &nl);
    }

    if(_tree[target][GEQ] >= 0){
        nr++;
        _count(_tree[target][GEQ], &nr);
    }

    if(nl == 0 && nr == 0){

        k = _tree[target][PARENT];

          if(_tree[k][LT] == target) _tree[k][LT] =  - 1;
          else if(_tree[k][GEQ] == target) _tree[k][GEQ] =  - 1;

    }//if target is terminal
    else if((nl == 0 && nr > 0) || (nr == 0 && nl > 0)){

         if(nl == 0) side = GEQ;
         else side = LT;

         k = _tree[target][PARENT];
         if(k >= 0){

             if(_tree[k][LT] == target){
                 _tree[k][LT] = _tree[target][side];
                 _tree[_tree[k][LT]][PARENT] = k;

         }
             else{
                 _tree[k][GEQ] = _tree[target][side];
                 _tree[_tree[k][GEQ]][PARENT] = k;
             }
        }
        else{
            _masterParent = _tree[target][side];
            _tree[_tree[target][side]][PARENT] =  - 1;
        }
    }//if only one side is populated
    else{

        if(nl > nr)side = LT;
        else side = GEQ;

         k = _tree[target][PARENT];
         if(k < 0){
             _masterParent = _tree[target][side];
             _tree[_masterParent][PARENT] =  - 1;
          }
          else{
              if(_tree[k][LT] == target){
                  _tree[k][LT] = _tree[target][side];
                  _tree[_tree[k][LT]][PARENT] = k;
              }
              else{
                   _tree[k][GEQ] = _tree[target][side];
                   _tree[_tree[k][GEQ]][PARENT] = k;
              }
          }

         root = _tree[target][3 - side];

         _descend(root);
    }//if both sides are populated

    if(target < _pts - 1){
         for(i = target + 1;i < _pts;i++ ){
             for(j = 0; j < 4; j++ ) _tree[i - 1][j] = _tree[i][j];

             for(j = 0; j < _dimensions; j++ ) _data[i - 1][j] = _data[i][j];
        }

        for(i = 0; i < _pts; i++ ){
            for(j = 1; j < 4; j++ ){
                if(_tree[i][j] > target) _tree[i][j]--;
             }
        }

        if(_masterParent > target)_masterParent-- ;
    }
    _pts--;

    i = _testTree();
    if (i == 0) {
        throw LSST_EXCEPT(lsst::pex::exceptions::RuntimeError,
        "Subtracting from KdTree failed\n");
    }


}

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:

• /home/lsstsw/stack/Linux64/afw/11.0-2-g04d2804/include/lsst/afw/math/GaussianProcess.h
• /home/lsstsw/stack/Linux64/afw/11.0-2-g04d2804/src/math/GaussianProcess.cc