[mlpack-git] master: First pass: try to make things 80 characters (I didn't touch the big long type lines...). (90af07d)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Thu Mar 5 21:58:05 EST 2015
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40
>---------------------------------------------------------------
commit 90af07df34cc1293a739c5f2548ad00cc9f2fdad
Author: Ryan Curtin <ryan at ratml.org>
Date: Sun Aug 17 04:37:09 2014 +0000
First pass: try to make things 80 characters (I didn't touch the big long type
lines...).
>---------------------------------------------------------------
90af07df34cc1293a739c5f2548ad00cc9f2fdad
.../core/tree/rectangle_tree/r_tree_split.hpp | 126 +++---
.../core/tree/rectangle_tree/r_tree_split_impl.hpp | 450 ++++++++++++---------
2 files changed, 321 insertions(+), 255 deletions(-)
diff --git a/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp b/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp
index 0397e04..9750213 100644
--- a/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp
@@ -2,8 +2,8 @@
* @file r_tree_split.hpp
* @author Andrew Wells
*
- * Defintion of the RTreeSplit class, a class that splits the nodes of an R tree, starting
- * at a leaf node and moving upwards if necessary.
+ * Defintion of the RTreeSplit class, a class that splits the nodes of an R
+ * tree, starting at a leaf node and moving upwards if necessary.
*/
#ifndef __MLPACK_CORE_TREE_RECTANGLE_TREE_R_TREE_SPLIT_HPP
#define __MLPACK_CORE_TREE_RECTANGLE_TREE_R_TREE_SPLIT_HPP
@@ -19,64 +19,72 @@ namespace tree /** Trees and tree-building procedures. */ {
* as necessary.
*/
template<typename DescentType,
- typename StatisticType,
- typename MatType>
+ typename StatisticType,
+ typename MatType>
class RTreeSplit
{
-public:
-
-/**
- * Split a leaf node using the "default" algorithm. If necessary, this split will propagate
- * upwards through the tree.
- */
-static void SplitLeafNode(RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* tree,
- std::vector<bool>& relevels);
-
-/**
- * Split a non-leaf node using the "default" algorithm. If this is a root node, the
- * tree increases in depth.
- */
-static bool SplitNonLeafNode(RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* tree,
- std::vector<bool>& relevels);
-
-private:
-
-/**
- * Get the seeds for splitting a leaf node.
- */
-static void GetPointSeeds(const RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>& tree, int *i, int *j);
-
-/**
- * Get the seeds for splitting a non-leaf node.
- */
-static void GetBoundSeeds(const RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>& tree, int *i, int *j);
-
-/**
- * Assign points to the two new nodes.
- */
-static void AssignPointDestNode(
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* oldTree,
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeOne,
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeTwo,
- const int intI,
- const int intJ);
-
-/**
- * Assign nodes to the two new nodes.
- */
-static void AssignNodeDestNode(
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* oldTree,
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType> *treeOne,
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType> *treeTwo,
- const int intI,
- const int intJ);
-
-/**
- * Insert a node into another node.
- */
-static void InsertNodeIntoTree(
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* destTree,
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* srcNode);
+ public:
+ /**
+ * Split a leaf node using the "default" algorithm. If necessary, this split
+ * will propagate upwards through the tree.
+ */
+ static void SplitLeafNode(
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>,
+ DescentType, StatisticType, MatType>* tree,
+ std::vector<bool>& relevels);
+
+ /**
+ * Split a non-leaf node using the "default" algorithm. If this is a root
+ * node, the tree increases in depth.
+ */
+ static bool SplitNonLeafNode(
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>,
+ DescentType, StatisticType, MatType>* tree,
+ std::vector<bool>& relevels);
+
+ private:
+ /**
+ * Get the seeds for splitting a leaf node.
+ */
+ static void GetPointSeeds(
+ const RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>& tree,
+ int *i,
+ int *j);
+
+ /**
+ * Get the seeds for splitting a non-leaf node.
+ */
+ static void GetBoundSeeds(
+ const RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>& tree,
+ int *i,
+ int *j);
+
+ /**
+ * Assign points to the two new nodes.
+ */
+ static void AssignPointDestNode(
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* oldTree,
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeOne,
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeTwo,
+ const int intI,
+ const int intJ);
+
+ /**
+ * Assign nodes to the two new nodes.
+ */
+ static void AssignNodeDestNode(
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* oldTree,
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType> *treeOne,
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType> *treeTwo,
+ const int intI,
+ const int intJ);
+
+ /**
+ * Insert a node into another node.
+ */
+ static void InsertNodeIntoTree(
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* destTree,
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* srcNode);
};
}; // namespace tree
@@ -86,5 +94,3 @@ static void InsertNodeIntoTree(
#include "r_tree_split_impl.hpp"
#endif
-
-
diff --git a/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp b/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
index 18cfcec..03d43c4 100644
--- a/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
@@ -15,38 +15,41 @@ namespace mlpack {
namespace tree {
/**
- * We call GetPointSeeds to get the two points which will be the initial points in the new nodes
- * We then call AssignPointDestNode to assign the remaining points to the two new nodes.
- * Finally, we delete the old node and insert the new nodes into the tree, spliting the parent
- * if necessary.
+ * We call GetPointSeeds to get the two points which will be the initial points
+ * in the new nodes We then call AssignPointDestNode to assign the remaining
+ * points to the two new nodes. Finally, we delete the old node and insert the
+ * new nodes into the tree, spliting the parent if necessary.
*/
template<typename DescentType,
typename StatisticType,
typename MatType>
void RTreeSplit<DescentType, StatisticType, MatType>::SplitLeafNode(
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* tree,
- std::vector<bool>& relevels)
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* tree,
+ std::vector<bool>& relevels)
{
- // If we are splitting the root node, we need will do things differently so that the constructor
- // and other methods don't confuse the end user by giving an address of another node.
- if (tree->Parent() == NULL) {
-
-// RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* copy = tree->ExactClone(); // We actually want to copy this way. Pointers and everything.
+ // If we are splitting the root node, we need will do things differently so
+ // that the constructor and other methods don't confuse the end user by giving
+ // an address of another node.
+ if (tree->Parent() == NULL)
+ {
+ // We actually want to copy this way. Pointers and everything.
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* copy =
- new RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(*tree, false); // We actually want to copy this way. Pointers and everything.
-
+ new RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(*tree, false);
copy->Parent() = tree;
tree->Count() = 0;
tree->NullifyData();
- tree->Children()[(tree->NumChildren())++] = copy; // Because this was a leaf node, numChildren must be 0.
- RTreeSplit<DescentType, StatisticType, MatType>::SplitLeafNode(copy, relevels);
+ // Because this was a leaf node, numChildren must be 0.
+ tree->Children()[(tree->NumChildren())++] = copy;
+ RTreeSplit<DescentType, StatisticType, MatType>::SplitLeafNode(copy,
+ relevels);
return;
}
+
assert(tree->Parent()->NumChildren() <= tree->Parent()->MaxNumChildren());
- // Use the quadratic split method from: Guttman "R-Trees: A Dynamic Index Structure for
- // Spatial Searching" It is simplified since we don't handle rectangles, only points.
- // We assume that the tree uses Euclidean Distance.
+ // Use the quadratic split method from: Guttman "R-Trees: A Dynamic Index
+ // Structure for Spatial Searching" It is simplified since we don't handle
+ // rectangles, only points. We assume that the tree uses Euclidean Distance.
int i = 0;
int j = 0;
GetPointSeeds(*tree, &i, &j);
@@ -62,8 +65,10 @@ void RTreeSplit<DescentType, StatisticType, MatType>::SplitLeafNode(
//Remove this node and insert treeOne and treeTwo
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* par = tree->Parent();
int index = 0;
- for (int i = 0; i < par->NumChildren(); i++) {
- if (par->Children()[i] == tree) {
+ for (int i = 0; i < par->NumChildren(); i++)
+ {
+ if (par->Children()[i] == tree)
+ {
index = i;
break;
}
@@ -71,12 +76,11 @@ void RTreeSplit<DescentType, StatisticType, MatType>::SplitLeafNode(
par->Children()[index] = treeOne;
par->Children()[par->NumChildren()++] = treeTwo;
- // we only add one at a time, so we should only need to test for equality
+ // We only add one at a time, so we should only need to test for equality
// just in case, we use an assert.
- assert(par->NumChildren() <= par->MaxNumChildren()+1);
- if (par->NumChildren() == par->MaxNumChildren()+1) {
+ assert(par->NumChildren() <= par->MaxNumChildren() + 1);
+ if (par->NumChildren() == par->MaxNumChildren() + 1)
SplitNonLeafNode(par, relevels);
- }
assert(treeOne->Parent()->NumChildren() <= treeOne->MaxNumChildren());
assert(treeOne->Parent()->NumChildren() >= treeOne->MinNumChildren());
@@ -85,29 +89,29 @@ void RTreeSplit<DescentType, StatisticType, MatType>::SplitLeafNode(
// We need to delete this carefully since references to points are used.
tree->SoftDelete();
-
- return;
}
/**
* We call GetBoundSeeds to get the two new nodes that this one will be broken
- * into. Then we call AssignNodeDestNode to move the children of this node
- * into either of those two nodes. Finally, we delete the now unused information
- * and recurse up the tree if necessary. We don't need to worry about the bounds
+ * into. Then we call AssignNodeDestNode to move the children of this node into
+ * either of those two nodes. Finally, we delete the now unused information and
+ * recurse up the tree if necessary. We don't need to worry about the bounds
* higher up the tree because they were already updated if necessary.
*/
template<typename DescentType,
-typename StatisticType,
-typename MatType>
+ typename StatisticType,
+ typename MatType>
bool RTreeSplit<DescentType, StatisticType, MatType>::SplitNonLeafNode(
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* tree,
std::vector<bool>& relevels)
{
- // If we are splitting the root node, we need will do things differently so that the constructor
- // and other methods don't confuse the end user by giving an address of another node.
- if (tree->Parent() == NULL) {
+ // If we are splitting the root node, we need will do things differently so
+ // that the constructor and other methods don't confuse the end user by giving
+ // an address of another node.
+ if (tree->Parent() == NULL)
+ {
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* copy =
- new RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(*tree, false); // We actually want to copy this way. Pointers and everything.
+ new RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(*tree, false); // We actually want to copy this way. Pointers and everything.
copy->Parent() = tree;
tree->NumChildren() = 0;
@@ -124,9 +128,9 @@ bool RTreeSplit<DescentType, StatisticType, MatType>::SplitNonLeafNode(
assert(i != j);
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeOne = new
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(tree->Parent());
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(tree->Parent());
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeTwo = new
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(tree->Parent());
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>(tree->Parent());
// This will assign the ith and jth rectangles appropriately.
AssignNodeDestNode(tree, treeOne, treeTwo, i, j);
@@ -134,8 +138,10 @@ bool RTreeSplit<DescentType, StatisticType, MatType>::SplitNonLeafNode(
//Remove this node and insert treeOne and treeTwo
RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* par = tree->Parent();
int index = -1;
- for (int i = 0; i < par->NumChildren(); i++) {
- if (par->Children()[i] == tree) {
+ for (int i = 0; i < par->NumChildren(); i++)
+ {
+ if (par->Children()[i] == tree)
+ {
index = i;
break;
}
@@ -144,26 +150,23 @@ bool RTreeSplit<DescentType, StatisticType, MatType>::SplitNonLeafNode(
par->Children()[index] = treeOne;
par->Children()[par->NumChildren()++] = treeTwo;
- for (int i = 0; i < par->NumChildren(); i++) {
+ for (int i = 0; i < par->NumChildren(); i++)
assert(par->Children()[i] != tree);
- }
- // we only add one at a time, so should only need to test for equality
- // just in case, we use an assert.
- assert(par->NumChildren() <= par->MaxNumChildren()+1);
+ // We only add one at a time, so should only need to test for equality just in
+ // case, we use an assert.
+ assert(par->NumChildren() <= par->MaxNumChildren() + 1);
- if (par->NumChildren() == par->MaxNumChildren()+1) {
+ if (par->NumChildren() == par->MaxNumChildren() + 1)
SplitNonLeafNode(par, relevels);
- }
- // We have to update the children of each of these new nodes so that they record the
- // correct parent.
- for (int i = 0; i < treeOne->NumChildren(); i++) {
+ // We have to update the children of each of these new nodes so that they
+ // record the correct parent.
+ for (int i = 0; i < treeOne->NumChildren(); i++)
treeOne->Children()[i]->Parent() = treeOne;
- }
- for (int i = 0; i < treeTwo->NumChildren(); i++) {
+
+ for (int i = 0; i < treeTwo->NumChildren(); i++)
treeTwo->Children()[i]->Parent() = treeTwo;
- }
assert(treeOne->NumChildren() <= treeOne->MaxNumChildren());
assert(treeTwo->NumChildren() <= treeTwo->MaxNumChildren());
@@ -181,26 +184,34 @@ bool RTreeSplit<DescentType, StatisticType, MatType>::SplitNonLeafNode(
* The indices of these points will be stored in iRet and jRet.
*/
template<typename DescentType,
-typename StatisticType,
-typename MatType>
+ typename StatisticType,
+ typename MatType>
void RTreeSplit<DescentType, StatisticType, MatType>::GetPointSeeds(
- const RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>& tree,
- int* iRet,
- int* jRet)
+ const RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>& tree,
+ int* iRet,
+ int* jRet)
{
- // Here we want to find the pair of points that it is worst to place in the same
- // node. Because we are just using points, we will simply choose the two that would
- // create the most voluminous hyperrectangle.
+ // Here we want to find the pair of points that it is worst to place in the
+ // same node. Because we are just using points, we will simply choose the two
+ // that would create the most voluminous hyperrectangle.
double worstPairScore = -1.0;
int worstI = 0;
int worstJ = 0;
- for (int i = 0; i < tree.Count(); i++) {
- for (int j = i + 1; j < tree.Count(); j++) {
+ for (int i = 0; i < tree.Count(); i++)
+ {
+ for (int j = i + 1; j < tree.Count(); j++)
+ {
double score = 1.0;
- for (int k = 0; k < tree.Bound().Dim(); k++) {
- score *= std::abs(tree.LocalDataset().at(k, i) - tree.LocalDataset().at(k, j)); // Points (in the dataset) are stored by column, but this function takes (row, col).
+ for (int k = 0; k < tree.Bound().Dim(); k++)
+ {
+ // Points (in the dataset) are stored by column, but this function takes
+ // (row, col).
+ score *= std::abs(tree.LocalDataset().at(k, i) -
+ tree.LocalDataset().at(k, j));
}
- if (score > worstPairScore) {
+
+ if (score > worstPairScore)
+ {
worstPairScore = score;
worstI = i;
worstJ = j;
@@ -210,32 +221,38 @@ void RTreeSplit<DescentType, StatisticType, MatType>::GetPointSeeds(
*iRet = worstI;
*jRet = worstJ;
- return;
}
/**
- * Get the two bounds that will be used as seeds for the split of the node.
- * The indices of the bounds will be stored in iRet and jRet.
+ * Get the two bounds that will be used as seeds for the split of the node. The
+ * indices of the bounds will be stored in iRet and jRet.
*/
template<typename DescentType,
-typename StatisticType,
-typename MatType>
+ typename StatisticType,
+ typename MatType>
void RTreeSplit<DescentType, StatisticType, MatType>::GetBoundSeeds(
- const RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>& tree,
- int* iRet,
- int* jRet)
+ const RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>& tree,
+ int* iRet,
+ int* jRet)
{
double worstPairScore = -1.0;
int worstI = 0;
int worstJ = 0;
- for (int i = 0; i < tree.NumChildren(); i++) {
- for (int j = i + 1; j < tree.NumChildren(); j++) {
+ for (int i = 0; i < tree.NumChildren(); i++)
+ {
+ for (int j = i + 1; j < tree.NumChildren(); j++)
+ {
double score = 1.0;
- for (int k = 0; k < tree.Bound().Dim(); k++) {
- score *= std::max(tree.Children()[i]->Bound()[k].Hi(), tree.Children()[j]->Bound()[k].Hi()) -
- std::min(tree.Children()[i]->Bound()[k].Lo(), tree.Children()[j]->Bound()[k].Lo());
+ for (int k = 0; k < tree.Bound().Dim(); k++)
+ {
+ score *= std::max(tree.Children()[i]->Bound()[k].Hi(),
+ tree.Children()[j]->Bound()[k].Hi()) -
+ std::min(tree.Children()[i]->Bound()[k].Lo(),
+ tree.Children()[j]->Bound()[k].Lo());
}
- if (score > worstPairScore) {
+
+ if (score > worstPairScore)
+ {
worstPairScore = score;
worstI = i;
worstJ = j;
@@ -245,20 +262,18 @@ void RTreeSplit<DescentType, StatisticType, MatType>::GetBoundSeeds(
*iRet = worstI;
*jRet = worstJ;
- return;
}
template<typename DescentType,
-typename StatisticType,
-typename MatType>
+ typename StatisticType,
+ typename MatType>
void RTreeSplit<DescentType, StatisticType, MatType>::AssignPointDestNode(
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* oldTree,
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeOne,
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeTwo,
- const int intI,
- const int intJ)
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* oldTree,
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeOne,
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeTwo,
+ const int intI,
+ const int intJ)
{
-
int end = oldTree->Count();
assert(end > 1); // If this isn't true, the tree is really weird.
@@ -271,66 +286,85 @@ void RTreeSplit<DescentType, StatisticType, MatType>::AssignPointDestNode(
treeOne->InsertPoint(oldTree->Points()[intI]);
treeTwo->InsertPoint(oldTree->Points()[intJ]);
- // If intJ is the last point in the tree, we need to switch the order so that we remove the correct points.
- if (intI > intJ) {
- oldTree->Points()[intI] = oldTree->Points()[--end]; // decrement end
+ // If intJ is the last point in the tree, we need to switch the order so that
+ // we remove the correct points.
+ if (intI > intJ)
+ {
+ oldTree->Points()[intI] = oldTree->Points()[--end]; // Decrement end.
oldTree->LocalDataset().col(intI) = oldTree->LocalDataset().col(end);
- oldTree->Points()[intJ] = oldTree->Points()[--end]; // decrement end
+ oldTree->Points()[intJ] = oldTree->Points()[--end]; // Decrement end.
oldTree->LocalDataset().col(intJ) = oldTree->LocalDataset().col(end);
- } else {
- oldTree->Points()[intJ] = oldTree->Points()[--end]; // decrement end
+ }
+ else
+ {
+ oldTree->Points()[intJ] = oldTree->Points()[--end]; // Decrement end.
oldTree->LocalDataset().col(intJ) = oldTree->LocalDataset().col(end);
- oldTree->Points()[intI] = oldTree->Points()[--end]; // decrement end
+ oldTree->Points()[intI] = oldTree->Points()[--end]; // Decrement end.
oldTree->LocalDataset().col(intI) = oldTree->LocalDataset().col(end);
}
int numAssignedOne = 1;
int numAssignedTwo = 1;
- // In each iteration, we go through all points and find the one that causes the least
- // increase of volume when added to one of the rectangles. We then add it to that
- // rectangle. We stop when we run out of points or when all of the remaining points
- // need to be assigned to the same rectangle to satisfy the minimum fill requirement.
-
- // The below is safe because if end decreases and the right hand side of the second part of the conjunction changes
- // on the same iteration, we added the point to the node with fewer points anyways.
- while (end > 0 && end > oldTree->MinLeafSize() - std::min(numAssignedOne, numAssignedTwo)) {
+ // In each iteration, we go through all points and find the one that causes
+ // the least increase of volume when added to one of the rectangles. We then
+ // add it to that rectangle. We stop when we run out of points or when all of
+ // the remaining points need to be assigned to the same rectangle to satisfy
+ // the minimum fill requirement.
+
+ // The below is safe because if end decreases and the right hand side of the
+ // second part of the conjunction changes on the same iteration, we added the
+ // point to the node with fewer points anyways.
+ while ((end > 0) && (end > oldTree->MinLeafSize() -
+ std::min(numAssignedOne, numAssignedTwo)))
+ {
int bestIndex = 0;
double bestScore = DBL_MAX;
int bestRect = 1;
- // Calculate the increase in volume for assigning this point to each rectangle.
+ // Calculate the increase in volume for assigning this point to each
+ // rectangle.
// First, calculate the starting volume.
double volOne = 1.0;
double volTwo = 1.0;
- for (int i = 0; i < oldTree->Bound().Dim(); i++) {
+ for (int i = 0; i < oldTree->Bound().Dim(); i++)
+ {
volOne *= treeOne->Bound()[i].Width();
volTwo *= treeTwo->Bound()[i].Width();
}
- // Find the point that, when assigned to one of the two new rectangles, minimizes the increase
- // in volume.
- for (int index = 0; index < end; index++) {
+ // Find the point that, when assigned to one of the two new rectangles,
+ // minimizes the increase in volume.
+ for (int index = 0; index < end; index++)
+ {
double newVolOne = 1.0;
double newVolTwo = 1.0;
- for (int i = 0; i < oldTree->Bound().Dim(); i++) {
+ for (int i = 0; i < oldTree->Bound().Dim(); i++)
+ {
double c = oldTree->LocalDataset().col(index)[i];
- newVolOne *= treeOne->Bound()[i].Contains(c) ? treeOne->Bound()[i].Width() :
- (c < treeOne->Bound()[i].Lo() ? (treeOne->Bound()[i].Hi() - c) : (c - treeOne->Bound()[i].Lo()));
- newVolTwo *= treeTwo->Bound()[i].Contains(c) ? treeTwo->Bound()[i].Width() :
- (c < treeTwo->Bound()[i].Lo() ? (treeTwo->Bound()[i].Hi() - c) : (c - treeTwo->Bound()[i].Lo()));
+ newVolOne *= treeOne->Bound()[i].Contains(c) ?
+ treeOne->Bound()[i].Width() : (c < treeOne->Bound()[i].Lo() ?
+ (treeOne->Bound()[i].Hi() - c) : (c - treeOne->Bound()[i].Lo()));
+ newVolTwo *= treeTwo->Bound()[i].Contains(c) ?
+ treeTwo->Bound()[i].Width() : (c < treeTwo->Bound()[i].Lo() ?
+ (treeTwo->Bound()[i].Hi() - c) : (c - treeTwo->Bound()[i].Lo()));
}
// Choose the rectangle that requires the lesser increase in volume.
- if ((newVolOne - volOne) < (newVolTwo - volTwo)) {
- if (newVolOne - volOne < bestScore) {
+ if ((newVolOne - volOne) < (newVolTwo - volTwo))
+ {
+ if (newVolOne - volOne < bestScore)
+ {
bestScore = newVolOne - volOne;
bestIndex = index;
bestRect = 1;
}
- } else {
- if (newVolTwo - volTwo < bestScore) {
+ }
+ else
+ {
+ if (newVolTwo - volTwo < bestScore)
+ {
bestScore = newVolTwo - volTwo;
bestIndex = index;
bestRect = 2;
@@ -340,41 +374,46 @@ void RTreeSplit<DescentType, StatisticType, MatType>::AssignPointDestNode(
// Assign the point that causes the least increase in volume
// to the appropriate rectangle.
- if (bestRect == 1) {
+ if (bestRect == 1)
+ {
treeOne->InsertPoint(oldTree->Points()[bestIndex]);
numAssignedOne++;
- } else {
+ }
+ else
+ {
treeTwo->InsertPoint(oldTree->Points()[bestIndex]);
numAssignedTwo++;
}
- oldTree->Points()[bestIndex] = oldTree->Points()[--end]; // decrement end.
+ oldTree->Points()[bestIndex] = oldTree->Points()[--end]; // Decrement end.
oldTree->LocalDataset().col(bestIndex) = oldTree->LocalDataset().col(end);
}
// See if we need to satisfy the minimum fill.
- if (end > 0) {
- if (numAssignedOne < numAssignedTwo) {
- for (int i = 0; i < end; i++) {
+ if (end > 0)
+ {
+ if (numAssignedOne < numAssignedTwo)
+ {
+ for (int i = 0; i < end; i++)
treeOne->InsertPoint(oldTree->Points()[i]);
- }
- } else {
- for (int i = 0; i < end; i++) {
+ }
+ else
+ {
+ for (int i = 0; i < end; i++)
treeTwo->InsertPoint(oldTree->Points()[i]);
- }
}
}
}
template<typename DescentType,
-typename StatisticType,
-typename MatType>
+ typename StatisticType,
+ typename MatType>
void RTreeSplit<DescentType, StatisticType, MatType>::AssignNodeDestNode(
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* oldTree,
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeOne,
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeTwo,
- const int intI,
- const int intJ)
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* oldTree,
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeOne,
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* treeTwo,
+ const int intI,
+ const int intJ)
{
int end = oldTree->NumChildren();
@@ -382,85 +421,98 @@ void RTreeSplit<DescentType, StatisticType, MatType>::AssignNodeDestNode(
assert(intI != intJ);
- for (int i = 0; i < oldTree->NumChildren(); i++) {
- for (int j = i + 1; j < oldTree->NumChildren(); j++) {
+ for (int i = 0; i < oldTree->NumChildren(); i++)
+ for (int j = i + 1; j < oldTree->NumChildren(); j++)
assert(oldTree->Children()[i] != oldTree->Children()[j]);
- }
- }
InsertNodeIntoTree(treeOne, oldTree->Children()[intI]);
InsertNodeIntoTree(treeTwo, oldTree->Children()[intJ]);
- // If intJ is the last node in the tree, we need to switch the order so that we remove the correct nodes.
- if (intI > intJ) {
- oldTree->Children()[intI] = oldTree->Children()[--end]; // decrement end
- oldTree->Children()[intJ] = oldTree->Children()[--end]; // decrement end
- } else {
- oldTree->Children()[intJ] = oldTree->Children()[--end]; // decrement end
- oldTree->Children()[intI] = oldTree->Children()[--end]; // decrement end
+ // If intJ is the last node in the tree, we need to switch the order so that
+ // we remove the correct nodes.
+ if (intI > intJ)
+ {
+ oldTree->Children()[intI] = oldTree->Children()[--end];
+ oldTree->Children()[intJ] = oldTree->Children()[--end];
+ }
+ else
+ {
+ oldTree->Children()[intJ] = oldTree->Children()[--end];
+ oldTree->Children()[intI] = oldTree->Children()[--end];
}
assert(treeOne->NumChildren() == 1);
assert(treeTwo->NumChildren() == 1);
- for (int i = 0; i < end; i++) {
- for (int j = i + 1; j < end; j++) {
+ for (int i = 0; i < end; i++)
+ for (int j = i + 1; j < end; j++)
assert(oldTree->Children()[i] != oldTree->Children()[j]);
- }
- }
- for (int i = 0; i < end; i++) {
+ for (int i = 0; i < end; i++)
assert(oldTree->Children()[i] != treeOne->Children()[0]);
- }
- for (int i = 0; i < end; i++) {
+ for (int i = 0; i < end; i++)
assert(oldTree->Children()[i] != treeTwo->Children()[0]);
- }
-
int numAssignTreeOne = 1;
int numAssignTreeTwo = 1;
- // In each iteration, we go through all of the nodes and find the one that causes the least
- // increase of volume when added to one of the two new rectangles. We then add it to that
- // rectangle.
- while (end > 0 && end > oldTree->MinNumChildren() - std::min(numAssignTreeOne, numAssignTreeTwo)) {
+ // In each iteration, we go through all of the nodes and find the one that
+ // causes the least increase of volume when added to one of the two new
+ // rectangles. We then add it to that rectangle.
+ while ((end > 0) && (end > oldTree->MinNumChildren() -
+ std::min(numAssignTreeOne, numAssignTreeTwo)))
+ {
int bestIndex = 0;
double bestScore = DBL_MAX;
int bestRect = 0;
- // Calculate the increase in volume for assigning this node to each of the new rectangles.
+ // Calculate the increase in volume for assigning this node to each of the
+ // new rectangles.
double volOne = 1.0;
double volTwo = 1.0;
- for (int i = 0; i < oldTree->Bound().Dim(); i++) {
+ for (int i = 0; i < oldTree->Bound().Dim(); i++)
+ {
volOne *= treeOne->Bound()[i].Width();
volTwo *= treeTwo->Bound()[i].Width();
}
- for (int index = 0; index < end; index++) {
+ for (int index = 0; index < end; index++)
+ {
double newVolOne = 1.0;
double newVolTwo = 1.0;
- for (int i = 0; i < oldTree->Bound().Dim(); i++) {
- // For each of the new rectangles, find the width in this dimension if we add the rectangle at index to
- // the new rectangle.
+ for (int i = 0; i < oldTree->Bound().Dim(); i++)
+ {
+ // For each of the new rectangles, find the width in this dimension if
+ // we add the rectangle at index to the new rectangle.
math::Range range = oldTree->Children()[index]->Bound()[i];
- newVolOne *= treeOne->Bound()[i].Contains(range) ? treeOne->Bound()[i].Width() :
- (range.Contains(treeOne->Bound()[i]) ? range.Width() : (range.Lo() < treeOne->Bound()[i].Lo() ? (treeOne->Bound()[i].Hi() - range.Lo()) :
- (range.Hi() - treeOne->Bound()[i].Lo())));
- newVolTwo *= treeTwo->Bound()[i].Contains(range) ? treeTwo->Bound()[i].Width() :
- (range.Contains(treeTwo->Bound()[i]) ? range.Width() : (range.Lo() < treeTwo->Bound()[i].Lo() ? (treeTwo->Bound()[i].Hi() - range.Lo()) :
- (range.Hi() - treeTwo->Bound()[i].Lo())));
+ newVolOne *= treeOne->Bound()[i].Contains(range) ?
+ treeOne->Bound()[i].Width() : (range.Contains(treeOne->Bound()[i]) ?
+ range.Width() : (range.Lo() < treeOne->Bound()[i].Lo() ?
+ (treeOne->Bound()[i].Hi() - range.Lo()) : (range.Hi() -
+ treeOne->Bound()[i].Lo())));
+
+ newVolTwo *= treeTwo->Bound()[i].Contains(range) ?
+ treeTwo->Bound()[i].Width() : (range.Contains(treeTwo->Bound()[i]) ?
+ range.Width() : (range.Lo() < treeTwo->Bound()[i].Lo() ?
+ (treeTwo->Bound()[i].Hi() - range.Lo()) : (range.Hi() -
+ treeTwo->Bound()[i].Lo())));
}
// Choose the rectangle that requires the lesser increase in volume.
- if ((newVolOne - volOne) < (newVolTwo - volTwo)) {
- if (newVolOne - volOne < bestScore) {
+ if ((newVolOne - volOne) < (newVolTwo - volTwo))
+ {
+ if (newVolOne - volOne < bestScore)
+ {
bestScore = newVolOne - volOne;
bestIndex = index;
bestRect = 1;
}
- } else {
- if (newVolTwo - volTwo < bestScore) {
+ }
+ else
+ {
+ if (newVolTwo - volTwo < bestScore)
+ {
bestScore = newVolTwo - volTwo;
bestIndex = index;
bestRect = 2;
@@ -470,52 +522,60 @@ void RTreeSplit<DescentType, StatisticType, MatType>::AssignNodeDestNode(
// Assign the rectangle that causes the least increase in volume
// to the appropriate rectangle.
- if (bestRect == 1) {
+ if (bestRect == 1)
+ {
InsertNodeIntoTree(treeOne, oldTree->Children()[bestIndex]);
numAssignTreeOne++;
- } else {
+ }
+ else
+ {
InsertNodeIntoTree(treeTwo, oldTree->Children()[bestIndex]);
numAssignTreeTwo++;
}
- oldTree->Children()[bestIndex] = oldTree->Children()[--end]; // Decrement end.
+ oldTree->Children()[bestIndex] = oldTree->Children()[--end];
}
+
// See if we need to satisfy the minimum fill.
- if (end > 0) {
- if (numAssignTreeOne < numAssignTreeTwo) {
- for (int i = 0; i < end; i++) {
+ if (end > 0)
+ {
+ if (numAssignTreeOne < numAssignTreeTwo)
+ {
+ for (int i = 0; i < end; i++)
+ {
InsertNodeIntoTree(treeOne, oldTree->Children()[i]);
numAssignTreeOne++;
}
- } else {
- for (int i = 0; i < end; i++) {
+ }
+ else
+ {
+ for (int i = 0; i < end; i++)
+ {
InsertNodeIntoTree(treeTwo, oldTree->Children()[i]);
numAssignTreeTwo++;
}
}
}
- for (int i = 0; i < treeOne->NumChildren(); i++) {
- for (int j = i + 1; j < treeOne->NumChildren(); j++) {
+ for (int i = 0; i < treeOne->NumChildren(); i++)
+ for (int j = i + 1; j < treeOne->NumChildren(); j++)
assert(treeOne->Children()[i] != treeOne->Children()[j]);
- }
- }
- for (int i = 0; i < treeTwo->NumChildren(); i++) {
- for (int j = i + 1; j < treeTwo->NumChildren(); j++) {
+
+ for (int i = 0; i < treeTwo->NumChildren(); i++)
+ for (int j = i + 1; j < treeTwo->NumChildren(); j++)
assert(treeTwo->Children()[i] != treeTwo->Children()[j]);
- }
- }
}
/**
- * Insert a node into another node. Expanding the bounds and updating the numberOfChildren.
+ * Insert a node into another node. Expanding the bounds and updating the
+ * numberOfChildren.
*/
template<typename DescentType,
-typename StatisticType,
-typename MatType>
+ typename StatisticType,
+ typename MatType>
void RTreeSplit<DescentType, StatisticType, MatType>::InsertNodeIntoTree(
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* destTree,
- RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* srcNode)
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* destTree,
+ RectangleTree<RTreeSplit<DescentType, StatisticType, MatType>, DescentType, StatisticType, MatType>* srcNode)
{
destTree->Bound() |= srcNode->Bound();
destTree->Children()[destTree->NumChildren()++] = srcNode;
More information about the mlpack-git
mailing list