kdtree.h File Reference

Go to the source code of this file.

Classes
struct	Boxnode< DIM >
struct	KDtree< DIM >

Functions
template<class T >
void	SWAP (T &a, T &b)
template<MInt DIM>
MInt	selecti (const MInt k, MInt *indx, MInt n, MFloat *arr)

Function Documentation

selecti()

template<MInt DIM>

MInt selecti	(	const MInt	k,
		MInt *	indx,
		MInt	n,
		MFloat *	arr
	)

Definition at line 35 of file kdtree.h.

                                                            {
  MInt i, ia, ir, j, l, mid;
  MFloat a;
 
  l = 0;
  ir = n - 1;
  for(;;) {
    if(ir <= l + 1) {
      if(ir == l + 1 && arr[indx[ir]] < arr[indx[l]]) SWAP(indx[l], indx[ir]);
      return indx[k];
    } else {
      mid = (l + ir) >> 1;
      SWAP(indx[mid], indx[l + 1]);
      if(arr[indx[l]] > arr[indx[ir]]) SWAP(indx[l], indx[ir]);
      if(arr[indx[l + 1]] > arr[indx[ir]]) SWAP(indx[l + 1], indx[ir]);
      if(arr[indx[l]] > arr[indx[l + 1]]) SWAP(indx[l], indx[l + 1]);
      i = l + 1;
      j = ir;
      ia = indx[l + 1];
      a = arr[ia];
      for(;;) {
        do
          i++;
        while(arr[indx[i]] < a);
        do
          j--;
        while(arr[indx[j]] > a);
        if(j < i) break;
        SWAP(indx[i], indx[j]);
      }
      indx[l + 1] = indx[j];
      indx[j] = ia;
      if(j >= k) ir = j - 1;
      if(j <= k) l = i;
    }
  }
}

SWAP()

template<class T >

void SWAP ( T &  a, T &  b  )

inline

Building a K-D-tree Numercial Recipies in C: The Art of Scientific Computing Thrid Edition Authors:

Definition at line 21 of file kdtree.h.

                             {
  T dum = a;
  a = b;
  b = dum;
}