Skip to content
Snippets Groups Projects
Node.hpp 3.28 KiB
Newer Older
#ifndef TREE_NODE_HPP
#define TREE_NODE_HPP

#include <cstdlib>
Thomas Steinreiter's avatar
Thomas Steinreiter committed
#include <iterator>
Thomas Steinreiter's avatar
Thomas Steinreiter committed
#include "Body.hpp"
#include "Box.hpp"

// utilities for reverse iteration
template <typename T>
struct reversion_wrapper { T& iterable; };

template <typename T>
auto begin(reversion_wrapper<T> w) { using std::rbegin;	return rbegin(w.iterable); }

template <typename T>
auto end(reversion_wrapper<T> w) { using std::rend; return rend(w.iterable); }

template <typename T>
reversion_wrapper<T> reverse(T&& iterable) { return{ iterable }; }

namespace nbody {
	//class for storing node information
	class Node {
		friend class Tree;
		friend class NodeIterator;
		friend class BarnesHutTree;
	protected:
		std::vector<Body> bodies;
		Box bb;
		Node* prev{ this };
		Node* next{ this };
		Node* nextSibling{ nullptr };
		Node* prevSibling{ nullptr };
		Node* afterSubtree{ nullptr };
		bool leaf{ true };
		Tree* tree{ nullptr };
		Body representative;
		Node(Tree* _tree);
		Node(const Box& bb_, std::vector<Body> bodies_, Tree* tree_);
		Node(std::vector<Body> bodies_, Tree* tree_);
		~Node() = default;
		bool isSplitable() const;
		void extendBBforBodies();
		void extendBBtoCube();
		Box getBB() const;
		std::vector<Body> getBodies() const;
		void insertBefore(Node* node);
		void insertAfter(Node* node);
		void unlink();
		void update();
		double getL() const;
		bool isCorrect() const;
		void print(std::size_t parallelId) const;
		bool sufficientForBody(const Body& body) const;
		bool sufficientForBox(const Box& box) const;
		void extractLocalBodiesTo(std::vector<Body>& result);

		// iterator classes for traversing of pointered node data structures
		template<typename Derived>
		class BaseNodeIterator {
		protected:
			Node* node_{ nullptr };
			BaseNodeIterator(Node * node) :node_(node) {};
		public:
			typedef std::ptrdiff_t difference_type;
			typedef Node value_type;
			typedef Node& reference;
			typedef Node* pointer;
			typedef std::bidirectional_iterator_tag iterator_category;

			const BaseNodeIterator& operator++() {
				return static_cast<Derived*>(this)->operator++();
			}
			BaseNodeIterator operator++(int) {
				auto result = *this; ++(*this); return result;
			}
			BaseNodeIterator& operator--() { 
				return static_cast<Derived*>(this)->operator--(); 
			}
			BaseNodeIterator operator--(int) {
				auto result = *this; --(*this); return result;
			}

			reference operator*() const { return *node_; }
			pointer operator->() const { return node_; }
			friend bool operator==(const BaseNodeIterator& lhs, const BaseNodeIterator& rhs) { return lhs.node_ == rhs.node_; }
			friend bool operator!=(const BaseNodeIterator& lhs, const BaseNodeIterator& rhs) { return !(lhs == rhs); }
		};
		struct NodeIterator : BaseNodeIterator<NodeIterator>{
			NodeIterator(Node * node) : BaseNodeIterator(node) {};
			const BaseNodeIterator& operator++() { node_ = node_->next; return *this; }
			BaseNodeIterator& operator--() { node_ = node_->prev; return *this; }

		};
		struct SiblingNodeIterator : BaseNodeIterator<SiblingNodeIterator>{
			SiblingNodeIterator(Node * node) : BaseNodeIterator(node) {};
			const BaseNodeIterator& operator++() { node_ = node_->nextSibling; return *this; }
			BaseNodeIterator& operator--() { node_ = node_->prevSibling; return *this; }
		};
} // namespace nbody