#include "BarnesHutTree.hpp"
#include "Node.hpp"
#include <iostream>
namespace nbody {
using namespace std;
BarnesHutTree::BarnesHutTree() {
this->maxLeafBodies = 16;
}
BarnesHutTree::~BarnesHutTree() {
}
vector<Box> BarnesHutTree::splitBB(Node* node) {
return node->getBB().octreeSplit();
}
int BarnesHutTree::numberOfChildren() {
return 8;
}
void BarnesHutTree::update() {
//iterate for updating representatives
Node* current = this->nodes->prev;
while (current != this->nodes) {
current->representative.mass = 0.0;
current->representative.position[0] = 0.0;
current->representative.position[1] = 0.0;
current->representative.position[2] = 0.0;
if (current->leaf) {
for (unsigned int i = 0; i < current->bodies.size(); i++) {
current->representative.mass += current->bodies[i].mass;
for (int j = 0; j < 3; j++) {
current->representative.position[j] += current->bodies[i].position[j] * current->bodies[i].mass;
}
}
} else {
Node* child = current->next;
do {
current->representative.mass += child->representative.mass;
for (int j = 0; j < 3; j++) {
current->representative.position[j] += child->representative.position[j] * child->representative.mass;
}
child = child->nextSibling;
} while (child != NULL);
}
for (int j = 0; j < 3; j++) {
current->representative.position[j] /= current->representative.mass;
}
current = current->prev;
}
}
void BarnesHutTree::split(Node* current) {
vector<Box> subboxes = BarnesHutTree::splitBB(current);
current->leaf = false;
Node* after = current->next;
for (vector<Box>::iterator it = subboxes.begin(); it != subboxes.end(); it++) {
Node* child = new Node(current->tree);
pthread_rwlock_wrlock(&child->lock);
child->parent = current;
child->bb = *it;
child->bodies = it->copyBodies(current->bodies);
child->nextSibling = NULL;
child->prevSibling = NULL;
after->insertBefore(child);
if (it != subboxes.begin()) {
child->prev->nextSibling = child;
child->prevSibling = child->prev;
child->prev->afterSubtree = child;
}
//this->control.toProcess.push(child);
//cout << "storing " << child << endl;
}
after->prev->afterSubtree = current->afterSubtree;
current->bodies.clear();
for (Node* n = current->next; n != NULL; n = n->nextSibling) {
pthread_rwlock_unlock(&n->lock);
}
}
void BarnesHutTree::splitNode(Node* current) {
//this->control.toProcess.pop();
//cout << "storing " << current << endl;
if (current->isSplitable()) {
split(current);
}
//cout << "removing " << this->control.toProcess.top() << endl;
//this->control.toProcess.pop();
}
void BarnesHutTree::build(vector<Body> bodies, Box domain) {
Node* current;
this->clean();
if (bodies.empty()) return;
//insert root node
this->nodes->insertAfter(new Node(this));
current = this->nodes->next;
//assign bodies to root node
current->bodies = bodies;
//setup proper bounding box
current->bb = domain;
current->extendBBforBodies();
current->extendBBtoCube();
current->afterSubtree = current->next;
//this->control.toProcess.push(current);
//iterate over existing boxes and split if it contains too much bodies
/*
while (current != this->nodes) {
this->splitNode(current);
current = current->next;
}
*/
BarnesHutTree::splitTree(this->nodes->next);
this->update();
}
void BarnesHutTree::build(vector<Body> bodies) {
Box bb;
bb.extendForBodies(bodies);
this->build(bodies, bb);
}
void BarnesHutTree::mergeLET(vector<Body> bodies) {
//put all new bodies into fitting leaves, walk through tree and split
Node* current;
for (vector<Body>::iterator it = bodies.begin(); it != bodies.end(); it++) {
current = this->nodes->next;
while (!current->leaf) {
Node* child = current->next;
while (child != NULL && !child->getBB().contained(it->position)) {
child = child->nextSibling;
}
if (child == NULL) {
cout << it - bodies.begin() << " Error: not contained: " << it->position[0] << " " << it->position[1] << " " << it->position[2] << endl;
} else {
current = child;
}
}
current->bodies.push_back(*it);
current->bodies.back().refinement = true;
}
current = this->nodes->next;
//this->control.toProcess.push(current);
while (current != this->nodes) {
this->splitNode(current);
current = current->next;
}
this->update();
}
/*
void BarnesHutTree::splitTree(Node* root) {
bool toSplitLeft = false;
Node* current = root;
do {
toSplitLeft = false;
while (current != root->prev) {
if (!pthread_rwlock_tryrdlock(¤t->lock)) {
//read lock acquired
if (current->isSplitable()) {
pthread_rwlock_unlock(¤t->lock);
if (!pthread_rwlock_trywrlock(¤t->lock)) {
//write lock acquired
split(current);
pthread_rwlock_unlock(¤t->lock);
}
toSplitLeft = true;
} else {
pthread_rwlock_unlock(¤t->lock);
}
} else {
toSplitLeft = true;
}
}
} while (toSplitLeft);
}
*/
void BarnesHutTree::splitTree(Node* root) {
bool toSplitLeft = false;
Node* current = root;
do {
toSplitLeft = false;
while (current != root->prev) {
if (current->isSplitable()) {
split(current);
toSplitLeft = true;
}
current = current->next;
}
} while (toSplitLeft);
}
}