#include <KDDTree.hpp>

Inheritance diagram for KDDTree< Z >:

Public Types
typedef double(*	DistSqFunc )(CubitVector &a, Z &b)
Public Member Functions
	KDDTree (double tol=GEOMETRY_RESABS, CubitBoolean selfBalancingOn=CUBIT_TRUE, double selfBalancingDeletionTolerance=KDDTREE_DEFAULT_SELF_BALANCING_DELETION_TOLERANCE, CubitBoolean randomOn=CUBIT_FALSE)
	~KDDTree ()
int	find_max_height ()
void	set_tol (double tol)
double	get_tol ()
CubitStatus	add (Z data)
CubitBoolean	remove (Z data)
CubitStatus	balance ()
CubitStatus	find (const CubitBox &range_box, DLIList< Z > &range_members)
CubitStatus	k_nearest_neighbor (CubitVector &q, int k, double &closest_dist, DLIList< Z > &nearest_neighbors, DistSqFunc dist_sq_point_data)
Static Public Member Functions
static bool	less_than_func (KDDTreeNode< Z > &node_a, KDDTreeNode< Z > &node_b)
Public Attributes
DLIList< KDDTreeNode< Z > * >	myNodeList
KDDTreeNode< Z > *	root
Private Member Functions
double	min_dist_sq (CubitVector &q, CubitBox &b_box)
void	recursive_find_max_height (KDDTreeNode< Z > root, int depth, int maxdepth)
KDDTreeNode< Z > *	recursive_balance (DIMENSION dim, int left, int right, KDDTreeNode< Z > array[], KDDTreeNode< Z > parent)
void	recursive_find (KDDTreeNode< Z > *rect_tree, const CubitBox &range_box, DLIList< Z > &range_members)
KDDTreeNode< Z > *	find_node_containing_data (KDDTreeNode< Z > *subtreeRoot, Z data)
KDDTreeNode< Z > *	find_minimum_node_of_dimension (KDDTreeNode< Z > *P, DIMENSION D)
CubitStatus	insert_node (KDDTreeNode< Z > *P)
CubitStatus	dump_list ()
int	modifind (DIMENSION dim, int left, int right, KDDTreeNode< Z > *array[])
Private Attributes
CubitBoolean	mySelfBalancingOn
double	myTolerance
DLIList< KDDTreeNode< Z > * >	myAddList
KDDTreeNode< Z > *	myDeepestLeaf
int	myMarkedNodes
double	myDeletionTolerance
CubitBoolean	myRandomOn

Detailed Description

template<class Z>
class KDDTree< Z >

Definition at line 38 of file KDDTree.hpp.

Member Typedef Documentation

template<class Z>

typedef double(* KDDTree< Z >::DistSqFunc)(CubitVector &a, Z &b)

Reimplemented from AbstractTree< Z >.

Definition at line 112 of file KDDTree.hpp.

Constructor & Destructor Documentation

template<class Z >

KDDTree< Z >::KDDTree	(	double	tol = `GEOMETRY_RESABS`,
		CubitBoolean	selfBalancingOn = `CUBIT_TRUE`,
		double	selfBalancingDeletionTolerance = `KDDTREE_DEFAULT_SELF_BALANCING_DELETION_TOLERANCE`,
		CubitBoolean	randomOn = `CUBIT_FALSE`
	)

Definition at line 46 of file KDDTree.cpp.

{
  root = NULL;

  myTolerance = tol;
  mySelfBalancingOn = selfBalancingOn;
  myDeletionTolerance = selfBalancingDeletionTolerance;
  myMarkedNodes = 0;
  myRandomOn = randomOn;

  if (myRandomOn)
  {
    srand( (unsigned)time( NULL ) );
  }
}

template<class Z >

KDDTree< Z >::~KDDTree ( )

Definition at line 66 of file KDDTree.cpp.

{
  int i;
  for (i = myAddList.size(); i > 0; i--)
  {
    delete myAddList.pop();
  }
  for (i = myNodeList.size(); i > 0; i--)
  {
    KDDTreeNode<Z> *node = myNodeList.pop();
    delete node;
  }
}

Member Function Documentation

template<class Z >

CubitStatus KDDTree< Z >::add ( Z data ) [virtual]

Implements AbstractTree< Z >.

Definition at line 391 of file KDDTree.cpp.

{
  KDDTreeNode<Z> *P = new KDDTreeNode<Z> (data);
  P->safetyBox.reset (data->bounding_box());

  myAddList.push (P);

  return CUBIT_SUCCESS;
}

template<class Z >

CubitStatus KDDTree< Z >::balance ( ) [virtual]

Reimplemented from AbstractTree< Z >.

Definition at line 266 of file KDDTree.cpp.

{
  int arraypos = 0;
  KDDTreeNode<Z> ** array = new KDDTreeNode<Z>*[myAddList.size () + myNodeList.size ()];

  root = NULL;

  while (myAddList.size () > 0)
  {
    array[arraypos] = myAddList.pop();
    arraypos++;
  }
  while (myNodeList.size () > 0)
  {
    array[arraypos] = myNodeList.pop();

    if (array[arraypos]->valid == CUBIT_FALSE)
    {
      array[arraypos]->left = NULL;
      array[arraypos]->right = NULL;
      delete array[arraypos];
    }
    else
    {
      arraypos++;
    }
  }

  int left = 0;
  int right = (arraypos - 1);
  root = recursive_balance (DIMX, left, right, array, NULL);

  myMarkedNodes = 0;

  delete [] array;
  return CUBIT_SUCCESS;
}

template<class Z >

CubitStatus KDDTree< Z >::dump_list ( ) [private]

Definition at line 81 of file KDDTree.cpp.

{
  while (myAddList.size() > 0)
  {
    KDDTreeNode<Z> *node = myAddList.pop();
    insert_node (node);
  }

  return CUBIT_SUCCESS;
}

template<class Z >

CubitStatus KDDTree< Z >::find	(	const CubitBox &	range_box,
		DLIList< Z > &	range_members
	)		`[virtual]`

Implements AbstractTree< Z >.

Definition at line 510 of file KDDTree.cpp.

{
  if (myAddList.size() > 0)
  {
    if (mySelfBalancingOn == CUBIT_TRUE) // self-balancing is on, so rebalance the tree
    {
      balance ();
    }
    else // self-balancing is off, so put everything in the Add List onto the tree
    {
      dump_list ();
    }
  }

  if (root != NULL)
  {
    recursive_find (root, range_box, range_members);
  }

  return CUBIT_SUCCESS;
}

template<class Z >

int KDDTree< Z >::find_max_height ( )

Definition at line 366 of file KDDTree.cpp.

{
  int depth = 0, maxdepth = 0;
  recursive_find_max_height (root, depth, &maxdepth);

  return maxdepth;
}

template<class Z>

KDDTreeNode<Z>* KDDTree< Z >::find_minimum_node_of_dimension	(	KDDTreeNode< Z > *	P,
		DIMENSION	D
	)		`[private]`

template<class Z >

KDDTreeNode< Z > * KDDTree< Z >::find_node_containing_data	(	KDDTreeNode< Z > *	subtreeRoot,
		Z	data
	)		`[private]`

Definition at line 402 of file KDDTree.cpp.

{
  KDDTreeNode<Z> *T = new KDDTreeNode<Z>(data); // temp node to use in searching
  KDDTreeNode<Z> *P = subtreeRoot;              // node to delete
  DIRECTION D;

  while (P != NULL)
  {
    if ((P->boundingBox.minimum() == T->boundingBox.minimum()) &&
        (P->boundingBox.maximum() == T->boundingBox.maximum()))
    {
      if (P->valid == CUBIT_TRUE)
      {
        break; // the bounding boxes match and this node has not been deleted
      }
    }

    D = T->compare_with_equality (P);

    if (D == DIR_EITHER)
    {
      KDDTreeNode<Z> *leftResult = find_node_containing_data (P->get_child (DIR_LEFT), data);

      if (leftResult != NULL)
      {
        P = leftResult;
        break;
      }

      KDDTreeNode<Z> *rightResult = find_node_containing_data (P->get_child (DIR_RIGHT), data);
      
      if (rightResult != NULL)
      {
        P = rightResult;
        break;
      }

      P = NULL;
    }
    else
    {
      P = P->get_child (D);
    }
  }

  delete T;

  return P;
}

template<class Z>

double KDDTree< Z >::get_tol ( ) [inline, virtual]

Implements AbstractTree< Z >.

Definition at line 95 of file KDDTree.hpp.

{ return myTolerance; }

template<class Z >

CubitStatus KDDTree< Z >::insert_node ( KDDTreeNode< Z > * P ) [private]

Definition at line 113 of file KDDTree.cpp.

{
  KDDTreeNode<Z> *F = NULL;      // father node
  KDDTreeNode<Z> *T;             // temp node

  if (root == NULL)
  {
    root = P;
    P->set_disc (DIMX);
  }
  else
  {
    T = root;
    DIRECTION direction = DIR_NULL;

    while (T != NULL)
    {
      F = T; // remember the father
      direction = P->compare (T);

      CubitVector tmin = T->safetyBox.minimum();
      CubitVector tmax = T->safetyBox.maximum();
      CubitVector pmin = P->safetyBox.minimum();
      CubitVector pmax = P->safetyBox.maximum();

      if (pmin.x() < tmin.x()) tmin.x (pmin.x());
      if (pmin.y() < tmin.y()) tmin.y (pmin.y());
      if (pmin.z() < tmin.z()) tmin.z (pmin.z());
      if (pmax.x() > tmax.x()) tmax.x (pmax.x());
      if (pmax.y() > tmax.y()) tmax.y (pmax.y());
      if (pmax.z() > tmax.z()) tmax.z (pmax.z());

      T->safetyBox.reset (tmin, tmax);

      T = T->get_child (direction);
    }

    F->set_child (P, direction);
    P->set_disc (F->next_disc());
    P->parent = F;
  }
  myNodeList.push (P);

  return CUBIT_SUCCESS;      
}

template<class Z>

CubitStatus KDDTree< Z >::k_nearest_neighbor	(	CubitVector &	q,
		int	k,
		double &	closest_dist,
		DLIList< Z > &	nearest_neighbors,
		DistSqFunc	dist_sq_point_data
	)		`[virtual]`

Implements AbstractTree< Z >.

Definition at line 646 of file KDDTree.cpp.

{
  PriorityQueue<KDDTreeNode<Z>*> *queue = new PriorityQueue<KDDTreeNode<Z>*> (KDDTree<Z>::less_than_func);
  PriorityQueue<KDDTreeNode<Z>*> *queueTemp = new PriorityQueue<KDDTreeNode<Z>*> (KDDTree<Z>::less_than_func);


  KDDTreeNode<Z> *element = root;

  // push this node on the queue
  element->set_dist (min_dist_sq (q, element->safetyBox));
  element->set_dist_data (DD_SAFETY);
  queue->push (element);
  

  // if the k closest nodes on the tree are not leaf-nodes, expand the closest
  //   non-leaf node
  while ( !queue->empty() )
  {
    element = queue->top();
    queue->pop();

    if (element->get_dist_data() == DD_LEAF)
    {
      // this node is a leaf, so it can be pushed onto the temporary queue
      queueTemp->push (element);
    }
    else
    {
      // one of the top k nodes is a non-leaf node, so expand it
      if (element->left)
      {
        element->left->set_dist (min_dist_sq (q, element->left->safetyBox));
        element->left->set_dist_data (DD_SAFETY);
        queue->push (element->left);
      }
      if (element->right)
      {
        element->right->set_dist (min_dist_sq (q, element->right->safetyBox));
        element->right->set_dist_data (DD_SAFETY);
        queue->push (element->right);
      }
      element->set_dist (dist_sq_point_data (q, element->data));
      element->set_dist_data (DD_LEAF);
      queue->push (element);

      // take all the elements in the temporary queue and reinsert them into
      //   the actual queue
      while ( !queueTemp->empty() )
      {
        queue->push ( queueTemp->top() );
        queueTemp->pop ();
      }
    }

    if (queueTemp->size() == k)
    {
      // success-- place the k nodes into the nearest_neighbors list
      element = queueTemp->top();
      queueTemp->pop();
      closest_dist = element->get_dist();
      nearest_neighbors.append (element->data);

      while ( !queueTemp->empty() )
      {
        nearest_neighbors.append ( queueTemp->top()->data );
        queueTemp->pop();
      }
     
      return CUBIT_SUCCESS;
    }
  }
  return CUBIT_FAILURE;
}

template<class Z >

bool KDDTree< Z >::less_than_func	(	KDDTreeNode< Z > *&	node_a,
		KDDTreeNode< Z > *&	node_b
	)		`[static]`

Definition at line 623 of file KDDTree.cpp.

{
  if (node_a->get_dist() < node_b->get_dist ())
  {
    return true;
  }
  else
  {
    return false;
  }
}

template<class Z >

double KDDTree< Z >::min_dist_sq	(	CubitVector &	q,
		CubitBox &	b_box
	)		`[private]`

Definition at line 570 of file KDDTree.cpp.

{
  CubitVector b_min = b_box.minimum();
  CubitVector b_max = b_box.maximum();
  CubitVector r;

  if (q.x () < b_min.x ())
  {
    r.x (b_min.x ());
  }
  else if (q.x () > b_max.x ())
  {
    r.x (b_max.x ());
  }
  else
  {
    r.x (q.x ());
  }
  
  if (q.y () < b_min.y ())
  {
    r.y (b_min.y ());
  }
  else if (q.y () > b_max.y ())
  {
    r.y (b_max.y ());
  }
  else
  {
    r.y (q.y ());
  }
  
  if (q.z () < b_min.z ())
  {
    r.z (b_min.z ());
  }
  else if (q.z () > b_max.z ())
  {
    r.z (b_max.z ());
  }
  else
  {
    r.z (q.z ());
  }
  
  double dist = (q-r).length_squared();

  return dist;
}

template<class Z >

int KDDTree< Z >::modifind	(	DIMENSION	dim,
		int	left,
		int	right,
		KDDTreeNode< Z > *	array[]
	)		`[private]`

Definition at line 175 of file KDDTree.cpp.

{
  int K = ((right - left + 1) / 2) + left + 1;
  int L = left + 1;
  int R = right + 1;
  int I, J;
  KDDTreeNode<Z>* node; // "X" in MODIFIND
  KDDTreeNode<Z>* temp; // temp for swapping; "W" in MODIFIND

  if (myRandomOn == CUBIT_TRUE)
  {
    int pivot = ( rand() % (right - left) ) + left; // create random pivot between left and right

    temp = array[pivot];
    array[pivot] = array[K - 1];
    array[K - 1] = temp;
  }

  while (L < R)
  {
    node = array[K - 1];
    I = L;
    J = R;
    while (! ((J < K) || (K < I)) )
    {
      if (dim == DIMX)
      {
        while (array[I - 1]->x < node->x) {
          I++;
        }
        while (node->x < array[J - 1]->x) {
          J--;
        }
      }
      else if (dim == DIMY)
      {
        while (array[I - 1]->y < node->y) {
          I++;
        }
        while (node->y < array[J - 1]->y) {
          J--;
        }
      }
      else
      {
        while (array[I - 1]->z < node->z) {
          I++;
        }
        while (node->z < array[J - 1]->z) { 
          J--; 
        }
      }

      temp = array[I - 1];
      array[I - 1] = array[J - 1];
      array[J - 1] = temp;

      I++;
      J--;
    }

    if (J < K)
    {
      L = I;
    }
    if (K < I)
    {
      R = J;
    }
  }

  return K - 1;
}

template<class Z>

KDDTreeNode< Z > * KDDTree< Z >::recursive_balance	(	DIMENSION	dim,
		int	left,
		int	right,
		KDDTreeNode< Z > *	array[],
		KDDTreeNode< Z > *	parent
	)		`[private]`

Definition at line 305 of file KDDTree.cpp.

{
  if (left > right)
  {
    return NULL;
  }
  else
  {
    KDDTreeNode<Z>* P;
    int K;

    if (left != right)
    {
      K = modifind (dim, left, right, array);
      P = array[K];
    }
    else
    {
      K = left;
      P = array[left];
    }

    myNodeList.push (P);

    P->safetyBox.reset (P->boundingBox);
    for (int i = left; i <= right; i++)
    {
      CubitVector imin = array[i]->safetyBox.minimum();
      CubitVector imax = array[i]->safetyBox.maximum();
      CubitVector pmin = P->safetyBox.minimum();
      CubitVector pmax = P->safetyBox.maximum();

      if (imin.x() < pmin.x()) pmin.x (imin.x());
      if (imin.y() < pmin.y()) pmin.y (imin.y());
      if (imin.z() < pmin.z()) pmin.z (imin.z());
      if (imax.x() > pmax.x()) pmax.x (imax.x());
      if (imax.y() > pmax.y()) pmax.y (imax.y());
      if (imax.z() > pmax.z()) pmax.z (imax.z());

      P->safetyBox.reset (pmin, pmax);
    }

    DIMENSION nextDim;
    switch (dim)
    {
      case DIMX: nextDim = DIMY; break;
      case DIMY: nextDim = DIMZ; break;
      default:   nextDim = DIMX;
    }

    P->set_disc (dim);
    P->parent = parent;

    P->left = recursive_balance (nextDim, left, K - 1, array, P);
    P->right = recursive_balance (nextDim, K + 1, right, array, P);

    return P;
  }
}

template<class Z >

void KDDTree< Z >::recursive_find	(	KDDTreeNode< Z > *	rect_tree,
		const CubitBox &	range_box,
		DLIList< Z > &	range_members
	)		`[private]`

Definition at line 536 of file KDDTree.cpp.

{
  if ( ! range_box.overlap (myTolerance, rect_tree->safetyBox) )
  {
    return; // no overlap, return
  }

  if ( range_box.overlap (myTolerance, rect_tree->boundingBox) )
  {
    if (rect_tree->valid == CUBIT_TRUE)
    {
      range_members.append (rect_tree->data); // append the data to the list.
    }
  }

  if (rect_tree->left != NULL)
  {
    recursive_find (rect_tree->left, range_box, range_members);
  }
  if (rect_tree->right != NULL)
  {
    recursive_find (rect_tree->right, range_box, range_members);
  }

  return;
}

template<class Z >

void KDDTree< Z >::recursive_find_max_height	(	KDDTreeNode< Z > *	root,
		int	depth,
		int *	maxdepth
	)		`[private]`

Definition at line 376 of file KDDTree.cpp.

{
  if (root)
  {
    depth++;
    if (depth > *maxdepth)
    {
      *maxdepth = depth;
    }
    recursive_find_max_height (root->left, depth, maxdepth);
    recursive_find_max_height (root->right, depth, maxdepth);
  }
}

template<class Z >

CubitBoolean KDDTree< Z >::remove ( Z data ) [virtual]

Implements AbstractTree< Z >.

Definition at line 455 of file KDDTree.cpp.

{
  if (myAddList.size() > 0)
  {
    if (mySelfBalancingOn == CUBIT_TRUE) // self-balancing is on, so rebalance the tree
    {
      balance ();
    }
    else // self-balancing is off, so put everything in the Add List onto the tree
    {
      dump_list ();
    }
  }

  if (root == NULL)
  {
    return CUBIT_FALSE;
  }
  else
  {
    KDDTreeNode<Z> *P = find_node_containing_data (root, data);

    if (P == NULL) // no matching node was found
    {
      return CUBIT_FALSE;
    }
    else // mark the matching node for deletion
    {
      if (P->valid == CUBIT_FALSE)
      {
        return CUBIT_FALSE; // this node was already deleted
      }

      P->valid = CUBIT_FALSE; // set the node to be deleted

      myMarkedNodes++;
      if (myDeletionTolerance != 0)
      {
        if ( (((double)myMarkedNodes / myNodeList.size()) > myDeletionTolerance) &&
             (myMarkedNodes > 1)
           )
        {
          balance ();
        }
      }

      return CUBIT_TRUE;
    }
  }
}