<commit_before>/*
 * Quadtree.h
 *
 *  Created on: 21.05.2014
 *      Author: <NAME> (<EMAIL>)
 */

#ifndef QUADTREE_H_
#define QUADTREE_H_

#include <vector>
#include <memory>
#include <cmath>
#include <omp.h>
#include "QuadNode.h"
#include "../../geometric/HyperbolicSpace.h"

namespace NetworKit {

template <class T>
class Quadtree {
	friend class QuadTreeGTest;
public:
	Quadtree() {
		root = QuadNode<T>();
		this->maxRadius = 1;
	}

	/**
	 * @param maxR Radius of the managed area. Must be smaller than 1.
	 * @param theoreticalSplit If true, split cells to get the same area in each child cell. Default is false
	 * @param alpha dispersion Parameter of the point distribution. Only has an effect if theoretical split is true
	 * @param capacity How many points can inhabit a leaf cell before it is split up?
	 *
	 */
	Quadtree(double maxR,bool theoreticalSplit=false, double alpha=1, count capacity=1000, double balance = 0.5) {
		root = QuadNode<T>(0, 0, 2*M_PI, maxR, capacity, 0,theoreticalSplit,alpha,balance);
		this->maxRadius = maxR;
	}

	count fillInParallel(count l, double alpha, count seqThreshold, count offset, QuadNode<T> &currentNode) {
		if (l > seqThreshold) {
			if (currentNode.height() == 1) currentNode.split();
			double treeArea = HyperbolicSpace::effectiveAreaInCell(currentNode.getLeftAngle(), currentNode.getRightAngle(), currentNode.getMinR(), currentNode.getMaxR(), alpha);
			count coveredPoints = 0;
			double coveredArea = 0;
			for (int i = 0; i < currentNode.children.size(); i++) {
				count pointsInSubtree;
				if (i < currentNode.children.size()-1) {
					double subTreeArea = HyperbolicSpace::effectiveAreaInCell(currentNode.children[i].getLeftAngle(), currentNode.children[i].getRightAngle(), currentNode.children[i].getMinR(), currentNode.children[i].getMaxR(), alpha);
					assert(treeArea-coveredArea >= subTreeArea);
					std::binomial_distribution<int> distribution(l-coveredPoints,subTreeArea/(treeArea-coveredArea));
					pointsInSubtree = distribution(Aux::Random::getURNG());
					coveredArea += subTreeArea;
				} else {
					pointsInSubtree = l-coveredPoints;
				}
				coveredPoints += pointsInSubtree;
				offset = fillInParallel(pointsInSubtree, alpha, seqThreshold, offset, currentNode.children[i]);
				//offset += pointsInSubtree;
			}
		} else {
				#pragma omp task shared(currentNode) firstprivate(offset)
				{
					vector<double> angles(l);
					vector<double> radii(l);
					HyperbolicSpace::fillPoints(angles, radii, currentNode.getLeftAngle(), currentNode.getRightAngle(),
							HyperbolicSpace::EuclideanRadiusToHyperbolic(currentNode.getMinR()),
							HyperbolicSpace::EuclideanRadiusToHyperbolic(currentNode.getMaxR()), alpha);
					for (index i = 0; i < l; i++) {
						currentNode.addContent(i+offset, angles[i], radii[i]);
					}
				}
				offset += l;
			}
			return offset;
		}

	Quadtree(count n, double stretch, bool theoreticalSplit=false, double alpha=1, count capacity=1000, double balance = 0.5) {
		double R = stretch*HyperbolicSpace::hyperbolicAreaToRadius(n);
		double r = HyperbolicSpace::hyperbolicRadiusToEuclidean(R);
		count numberOfThreads = omp_get_max_threads();
		//double k = ceil(log(numberOfThreads)/log(4));
		root = QuadNode<T>(0, 0, 2*M_PI, r, capacity, 0,theoreticalSplit,alpha,balance);
		count result;
		#pragma omp parallel
		{
			#pragma omp single nowait
			{
				result = fillInParallel(n, alpha, n/numberOfThreads, 0, root);
			}
		}
		assert(result == n);
		vector<double> missingAngles(n-result);
		vector<double> missingRadii(n-result);
		HyperbolicSpace::fillPoints(missingAngles, missingRadii, stretch, alpha);
		for (index i = result; i < n; i++) {
			root.addContent(i, missingAngles[i-result], missingRadii[i-result]);
		}
		//bernoulli to distribute
	}

	/**
	 * @param newcomer content to be added at point x
	 * @param angle angular coordinate of x
	 * @param R radial coordinate of x
	 */
	void addContent(T newcomer, double angle, double r) {
		root.addContent(newcomer, angle, r);<commit_msg>removed error handling, instead asserting that error cannot occur<commit_after>/*
 * Quadtree.h
 *
 *  Created on: 21.05.2014
 *      Author: <NAME> (<EMAIL>)
 */

#ifndef QUADTREE_H_
#define QUADTREE_H_

#include <vector>
#include <memory>
#include <cmath>
#include <omp.h>
#include "QuadNode.h"
#include "../../geometric/HyperbolicSpace.h"

namespace NetworKit {

template <class T>
class Quadtree {
	friend class QuadTreeGTest;
public:
	Quadtree() {
		root = QuadNode<T>();
		this->maxRadius = 1;
	}

	/**
	 * @param maxR Radius of the managed area. Must be smaller than 1.
	 * @param theoreticalSplit If true, split cells to get the same area in each child cell. Default is false
	 * @param alpha dispersion Parameter of the point distribution. Only has an effect if theoretical split is true
	 * @param capacity How many points can inhabit a leaf cell before it is split up?
	 *
	 */
	Quadtree(double maxR,bool theoreticalSplit=false, double alpha=1, count capacity=1000, double balance = 0.5) {
		root = QuadNode<T>(0, 0, 2*M_PI, maxR, capacity, 0,theoreticalSplit,alpha,balance);
		this->maxRadius = maxR;
	}

	count fillInParallel(count l, double alpha, count seqThreshold, count offset, QuadNode<T> &currentNode) {
		if (l > seqThreshold) {
			if (currentNode.height() == 1) currentNode.split();
			double treeArea = HyperbolicSpace::effectiveAreaInCell(currentNode.getLeftAngle(), currentNode.getRightAngle(), currentNode.getMinR(), currentNode.getMaxR(), alpha);
			count coveredPoints = 0;
			double coveredArea = 0;
			for (int i = 0; i < currentNode.children.size(); i++) {
				count pointsInSubtree;
				if (i < currentNode.children.size()-1) {
					double subTreeArea = HyperbolicSpace::effectiveAreaInCell(currentNode.children[i].getLeftAngle(), currentNode.children[i].getRightAngle(), currentNode.children[i].getMinR(), currentNode.children[i].getMaxR(), alpha);
					assert(treeArea-coveredArea >= subTreeArea);
					std::binomial_distribution<int> distribution(l-coveredPoints,subTreeArea/(treeArea-coveredArea));
					pointsInSubtree = distribution(Aux::Random::getURNG());
					coveredArea += subTreeArea;
				} else {
					pointsInSubtree = l-coveredPoints;
				}
				coveredPoints += pointsInSubtree;
				offset = fillInParallel(pointsInSubtree, alpha, seqThreshold, offset, currentNode.children[i]);
				//offset += pointsInSubtree;
			}
		} else {
				#pragma omp task shared(currentNode) firstprivate(offset)
				{
					vector<double> angles(l);
					vector<double> radii(l);
					HyperbolicSpace::fillPoints(angles, radii, currentNode.getLeftAngle(), currentNode.getRightAngle(),
							HyperbolicSpace::EuclideanRadiusToHyperbolic(currentNode.getMinR()),
							HyperbolicSpace::EuclideanRadiusToHyperbolic(currentNode.getMaxR()), alpha);
					for (index i = 0; i < l; i++) {
						currentNode.addContent(i+offset, angles[i], radii[i]);
					}
				}
				offset += l;
			}
			return offset;
		}

	Quadtree(count n, double stretch, bool theoreticalSplit=false, double alpha=1, count capacity=1000, double balance = 0.5) {
		double R = stretch*HyperbolicSpace::hyperbolicAreaToRadius(n);
		double r = HyperbolicSpace::hyperbolicRadiusToEuclidean(R);
		count numberOfThreads = omp_get_max_threads();
		//double k = ceil(log(numberOfThreads)/log(4));
		root = QuadNode<T>(0, 0, 2*M_PI, r, capacity, 0,theoreticalSplit,alpha,balance);
		count result;
		#pragma omp parallel
		{
			#pragma omp single nowait
			{
				result = fillInParallel(n, alpha, n/numberOfThreads, 0, root);
			}
		}
		assert(result == n);
	}

	/**
	 * @param newcomer content to be added at point x
	 * @param angle angular coordinate of x
	 * @param R radial coordinate of x
	 */
	void addContent(T newcomer, double angle, double r) {
		root.addContent(newcomer, angle, r);
{'fraction_non_alphanumeric': 0.1256739409499358, 'fraction_numerical': 0.010269576379974325, 'mean_word_length': 4.455882352941177, 'pattern_counts': {'":': 0, '<': 40, '<?xml version=': 0, '>': 41, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1450050', 'n_tokens_mistral': 2899, 'n_tokens_neox': 2461, 'n_words': 635}