kdtreeinternalnode.cpp

dysii是一款非常出色的滤波函数库

#include "KDTreeInternalNode.hpp"

using namespace indii::ml::aux;

KDTreeInternalNode::KDTreeInternalNode() : left(NULL), right(NULL),
    lower(NULL), upper(NULL), ownLower(false), ownUpper(false),
    haveWeight(false) {
  //
}

KDTreeInternalNode::KDTreeInternalNode(KDTreeNode* left, KDTreeNode* right)
    : left(left), right(right), lower(NULL), upper(NULL), ownLower(false),
    ownUpper(false), haveWeight(false) {
  unsigned int i;
  
  /* calculate lower bound */
  vector& l1(left->getLower());
  vector& l2(right->getLower());
  assert (l1.size() == l2.size());
  lower = new vector(l1);
  ownLower = false;
  
  for (i = 0; i < l2.size(); i++) {
    if (l2(i) < (*lower)(i)) {
      (*lower)(i) = l2(i);
      ownLower = true;
    }
  }
  if (!ownLower) {
    /* lower bound same as left child, so just store pointer to it */
    delete lower;
    lower = &l1;
  }

  /* calculate upper bound */
  vector& u1(left->getUpper());
  vector& u2(right->getUpper());
  assert (u1.size() == u2.size());
  upper = new vector(u2);
  ownUpper = false;
  
  for (i = 0; i < u1.size(); i++) {
    if (u1(i) > (*upper)(i)) {
      (*upper)(i) = u1(i);
      ownUpper = true;
    }
  }
  if (!ownUpper) {
    /* upper bound same as right child, so just store pointer to it */
    delete upper;
    upper = &u2;
  }

  /* post-condition */
  assert (lower->size() == upper->size());
}

KDTreeInternalNode::~KDTreeInternalNode() {
  if (ownLower) {
    delete lower;
  }
  if (ownUpper) {
    delete upper;
  }
  delete left;
  delete right;
}

double KDTreeInternalNode::getWeight() {
  if (!haveWeight) {
    weight = left->getWeight() + right->getWeight();
    haveWeight = true;
  }
  return weight;
}

vector& KDTreeInternalNode::getLower() {
  return *lower;
}

vector& KDTreeInternalNode::getUpper() {
  return *upper;
}

vector KDTreeInternalNode::nearestTo(const vector& x) {
  /* pre-condition */
  assert (x.size() == lower->size());

  const unsigned int N = lower->size();
  vector nearest(N);
  unsigned int i;

  for (i = 0; i < N; i++) {
    if (x(i) < (*lower)(i)) {
      nearest(i) = (*lower)(i);
    } else if (x(i) > (*upper)(i)) {
      nearest(i) = (*upper)(i);
    } else {
      nearest(i) = x(i);
    }
  }
  
  return nearest;
}

double KDTreeInternalNode::densityAt(const vector& x, Norm& N, Kernel& K) {
  double result = 0.0;

  /* should we recurse? */
  if (K(N(x - nearestTo(x))) > 0.0) {
    result = left->densityAt(x, N, K) + right->densityAt(x, N, K);
  }

  return result;
}

vector KDTreeInternalNode::sample(const double u, Norm& N, Kernel& K) {
  /* pre-condition */
  assert (u >= 0.0 && u <= getWeight());
  
  if (u <= left->getWeight()) {
    return left->sample(u, N, K);
  } else {
    return right->sample(u - left->getWeight(), N, K);
  }
}