<commit_before>#ifndef __NBODY_OCTREE_TPP_
#define __NBODY_OCTREE_TPP_

#include <algorithm>
#include <climits>
#include <cstddef>
#include <tuple>
#include <utility>
#include <vector>

using namespace nbody;

// *----------------*
// | Octree methods |
// *----------------*

template<typename L, typename N, std::size_t Dim>
Octree<L, N, Dim>::Octree(
		Vector<Dim> position,
		Vector<Dim> dimensions,
		std::size_t nodeCapacity,
		std::size_t maxDepth,
		bool adjust) :
		_leafs(),
		_nodes(),
		_nodeCapacity(nodeCapacity),
		_maxDepth(maxDepth),
		_adjust(adjust) {
	Node root;
	root.position = position;
	root.dimensions = dimensions;
	_nodes.insert(_nodes.begin(), root);
}

template<typename L, typename N, std::size_t Dim>
typename Octree<L, N, Dim>::NodeIterator Octree<L, N, Dim>::createChildren(
		NodeIterator node) {
	// Create the 2^Dim child nodes inside the list of nodes. This will not
	// invalidate the node iterator.
	_nodes.insert(node.listIt() + 1, 1 << Dim, Node());
	
	// Loop through the new children, and set up their various properties.
	Vector<Dim> childDimensions = node.listRef().dimensions / 2;
	Vector<Dim> midpoint = node.listRef().position + childDimensions;
	for (std::size_t index = 0; index < (1 << Dim); ++index) {
		Node& child = *(node.listIt() + index + 1);
		child.depth = node.listRef().depth + 1;
		child.hasParent = true;
		child.parentIndex = -((typename NodeRange::difference_type) index + 1);
		child.siblingIndex = index;
		child.leafIndex = node.listRef().leafIndex + node.listRef().leafCount;
		child.dimensions = childDimensions;
		child.position = node.position();
		// Shift the child position depending on which child it is.
		for (std::size_t dim = 0; dim < Dim; ++dim) {
			if ((1 << dim) & index) {
				child.position[dim] = midpoint[dim];
			}
		}
		
		// Add the child to this node.
		node.listRef().childIndices[index] = index + 1;
	}
	node.listRef().childIndices[1 << Dim] = (1 << Dim) + 1;
	node.listRef().hasChildren = true;
	
	// Go through the parent, grandparent, great-grandparent, ...  of this
	// node and update their child indices.
	NodeIterator parent = node;
	while (parent.hasParent()) {
		std::size_t siblingIndex = parent.listRef().siblingIndex;
		parent = parent.parent();
		while (++siblingIndex <= (1 << Dim)) {
			parent.listRef().childIndices[siblingIndex] += (1 << Dim);
			NodeIterator child = parent.child(siblingIndex);
			child.listRef().parentIndex -= (1 << Dim);
		}
	}
	
	// Distribute the leaves of this node to the children.
	for (std::size_t index = node.leafs().size(); index-- > 0; ) {
		// Figure out which node the leaf belongs to.
		std::size_t childIndex = 0;
		LeafIterator leaf = node.leafs().begin() + index;
		Vector<Dim> const& position = leaf.position();
		for (std::size_t dim = 0; dim < Dim; ++dim) {
			if (position[dim] >= midpoint[dim]) {
				childIndex += (1 << dim);
			}
		}
		moveAt(node, node.child(childIndex), leaf);
	}
	
	return node;
}

template<typename L, typename N, std::size_t Dim>
typename Octree<L, N, Dim>::NodeIterator Octree<L, N, Dim>::destroyChildren(
		NodeIterator node) {
	// Determine how many children, grandchildren, great-grandchildren, ...
	// of this node.
	std::size_t numDescendants = node.children().size();
	<commit_msg>Fixed a minor bug where leafs would get their order scrambled when a node was splitting into child nodes<commit_after>#ifndef __NBODY_OCTREE_TPP_
#define __NBODY_OCTREE_TPP_

#include <algorithm>
#include <climits>
#include <cstddef>
#include <tuple>
#include <utility>
#include <vector>

using namespace nbody;

// *----------------*
// | Octree methods |
// *----------------*

template<typename L, typename N, std::size_t Dim>
Octree<L, N, Dim>::Octree(
		Vector<Dim> position,
		Vector<Dim> dimensions,
		std::size_t nodeCapacity,
		std::size_t maxDepth,
		bool adjust) :
		_leafs(),
		_nodes(),
		_nodeCapacity(nodeCapacity),
		_maxDepth(maxDepth),
		_adjust(adjust) {
	Node root;
	root.position = position;
	root.dimensions = dimensions;
	_nodes.insert(_nodes.begin(), root);
}

template<typename L, typename N, std::size_t Dim>
typename Octree<L, N, Dim>::NodeIterator Octree<L, N, Dim>::createChildren(
		NodeIterator node) {
	// Create the 2^Dim child nodes inside the list of nodes. This will not
	// invalidate the node iterator.
	_nodes.insert(node.listIt() + 1, 1 << Dim, Node());
	
	// Loop through the new children, and set up their various properties.
	Vector<Dim> childDimensions = node.listRef().dimensions / 2;
	Vector<Dim> midpoint = node.listRef().position + childDimensions;
	for (std::size_t index = 0; index < (1 << Dim); ++index) {
		Node& child = *(node.listIt() + index + 1);
		child.depth = node.listRef().depth + 1;
		child.hasParent = true;
		child.parentIndex = -((typename NodeRange::difference_type) index + 1);
		child.siblingIndex = index;
		child.leafIndex = node.listRef().leafIndex + node.listRef().leafCount;
		child.dimensions = childDimensions;
		child.position = node.position();
		// Shift the child position depending on which child it is.
		for (std::size_t dim = 0; dim < Dim; ++dim) {
			if ((1 << dim) & index) {
				child.position[dim] = midpoint[dim];
			}
		}
		
		// Add the child to this node.
		node.listRef().childIndices[index] = index + 1;
	}
	node.listRef().childIndices[1 << Dim] = (1 << Dim) + 1;
	node.listRef().hasChildren = true;
	
	// Go through the parent, grandparent, great-grandparent, ...  of this
	// node and update their child indices.
	NodeIterator parent = node;
	while (parent.hasParent()) {
		std::size_t siblingIndex = parent.listRef().siblingIndex;
		parent = parent.parent();
		while (++siblingIndex <= (1 << Dim)) {
			parent.listRef().childIndices[siblingIndex] += (1 << Dim);
			NodeIterator child = parent.child(siblingIndex);
			child.listRef().parentIndex -= (1 << Dim);
		}
	}
	
	// Distribute the leaves of this node to the children.
	for (std::size_t index = 0; index < node.leafs().size(); ++index) {
		// Figure out which node the leaf belongs to.
		std::size_t childIndex = 0;
		LeafIterator leaf = node.leafs().begin();
		Vector<Dim> const& position = leaf.position();
		for (std::size_t dim = 0; dim < Dim; ++dim) {
			if (position[dim] >= midpoint[dim]) {
				childIndex += (1 << dim);
			}
		}
		moveAt(node, node.child(childIndex), leaf);
	}
	
	return node;
}

template<typename L, typename N, std::size_t Dim>
typename Octree<L, N, Dim>::NodeIterator Octree<L, N, Dim>::destroyChildren(
		NodeIterator node) {
	// Determine how many children, grandchildren, great-grandchildren, ...
	// of this node.
	std::size_t numDescendants = node.children().size();
	
{'fraction_non_alphanumeric': 0.1597159262617105, 'fraction_numerical': 0.006648534300392868, 'mean_word_length': 3.856199559794571, 'pattern_counts': {'":': 0, '<': 86, '<?xml version=': 0, '>': 44, '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': '4767804', 'n_tokens_mistral': 2374, 'n_tokens_neox': 2186, 'n_words': 610}